Masa-StarPU : estratégia com múltiplas políticas de escalonamento de tarefas para alinhamento de sequências com pruning

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorMelo, Alba Cristina Magalhães Alves de-
Autor(es): dc.creatorLopes, Rafael Alvares da Silva-
Data de aceite: dc.date.accessioned2021-10-14T17:54:33Z-
Data de disponibilização: dc.date.available2021-10-14T17:54:33Z-
Data de envio: dc.date.issued2021-03-19-
Data de envio: dc.date.issued2021-03-19-
Data de envio: dc.date.issued2021-03-19-
Data de envio: dc.date.issued2020-09-24-
Fonte completa do material: dc.identifierhttps://repositorio.unb.br/handle/10482/40262-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/619030-
Descrição: dc.descriptionDissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2020.-
Descrição: dc.descriptionA comparação de sequências biológicas é uma tarefa importante executada com frequência na análise genética de organismos. Algoritmos que realizam este procedimento utilizando um método exato possuem complexidade quadrática de tempo, demandando alto poder computacional e uso de técnicas de paralelização. Muitas soluções têm sido propostas para tratar este problema utilizam aceleradores como GPUs e FPGAs, porém poucas soluções utilizam apenas CPUs. O MASA é uma ferramenta multiplataforma específica para realizar a comparação de sequências biológicas. Uma de suas maiores virtudes é a otimização block pruning que realiza a poda da matriz de programação dinâmica em tempo de execução acelerando o processamento, porém introduzindo um problema de desbalanceamento de carga. O StarPU é uma ferramenta de programação paralela que possui implementações de diversas políticas de escalonamento dinâmico de tarefas. Neste trabalho, propomos e avaliamos o MASA-StarPU, uma ferramenta que utiliza a estrutura do MASA para realizar a comparação de sequências biológicas e as políticas do StarPU adequadas ao block pruning com o objetivo de eliminar o problema de desbalanceamento de carga. O MASA-StarPU foi testado em dois ambientes, avaliando pares de sequências de DNA cujos tamanhos variam entre 10 KBP (milhares de pares de bases) e 47 MBP (milhões de pares de bases), e as políticas de escalonamento de tarefas foram avaliadas em diferentes casos. Quando comparado com outras soluções da literatura que utilizam apenas CPU, o MASA-StarPU obteve o melhor resultado para todas as comparações. O MASA-StarPU atingiu o máximo de 18,4 GCUPS (bilhões de células atualizadas por segundo).-
Descrição: dc.descriptionThe comparison of biological sequences is an important task performed frequently in the genetic analysis of organisms. Algorithms that perform this procedure using an exact method have quadratic time complexity, demanding high computational power and, consequently parallelization techniques. Many solutions have been proposed to address this problem using accelerators such as GPUs and FPGAs, but few solutions use only CPUs. MASA is a domain-specific platform for performing biological sequence comparison. One of its greatest virtues is the optimization block pruning. Which prunes the dynamic programming matrix at run time introducing load imbalance. StarPU is a generic parallel programming tool that provides several dynamic task scheduling policies. In this work, we propose and evaluate MASA-StarPU, a tool that uses the MASA structure to carry out the comparison of biological sequences and uses the StarPU policies to accelerate the computation. MASA-StarPU was tested in two environments, evaluating pairs of DNA sequences whose sizes vary between 10 KBP (thousands of base pairs) and 47 MBP (millions of pairs of bases), and multiple task scheduling policies were evaluated in different cases. When compared to other solutions in the literature that use only CPU, MASA-StarPU obtained the best result for all comparisons and reached a maximum of 18.4 GCUPS (billions of cells updated by second).-
Formato: dc.formatapplication/pdf-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsA concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.-
Palavras-chave: dc.subjectSequências biológicas - comparação-
Palavras-chave: dc.subjectProgramação paralela (Computação)-
Palavras-chave: dc.subjectEscalonamento de tarefas-
Título: dc.titleMasa-StarPU : estratégia com múltiplas políticas de escalonamento de tarefas para alinhamento de sequências com pruning-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional – UNB

Não existem arquivos associados a este item.