Skip navigation
Use este identificador para citar ou linkar para este item: http://repositorio.unb.br/handle/10482/40262
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2020_RafaelAlvaresdaSilvaLopes.pdf4,85 MBAdobe PDFVisualizar/Abrir
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorMelo, Alba Cristina Magalhães Alves de-
dc.contributor.authorLopes, Rafael Alvares da Silva-
dc.date.accessioned2021-03-19T10:54:12Z-
dc.date.available2021-03-19T10:54:12Z-
dc.date.issued2021-03-19-
dc.date.submitted2020-09-24-
dc.identifier.citationLOPES, Rafael Alvares da Silva. Masa-StarPU : estratégia com múltiplas políticas de escalonamento de tarefas para alinhamento de sequências com pruning. 2020. xi, 78 f., il. Dissertação (Mestrado em Informática)—Universidade de Brasília, Brasília, 2020.pt_BR
dc.identifier.urihttps://repositorio.unb.br/handle/10482/40262-
dc.descriptionDissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2020.pt_BR
dc.description.abstractA 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).pt_BR
dc.language.isoPortuguêspt_BR
dc.rightsAcesso Abertopt_BR
dc.titleMasa-StarPU : estratégia com múltiplas políticas de escalonamento de tarefas para alinhamento de sequências com pruningpt_BR
dc.typeDissertaçãopt_BR
dc.subject.keywordSequências biológicas - comparaçãopt_BR
dc.subject.keywordProgramação paralela (Computação)pt_BR
dc.subject.keywordEscalonamento de tarefaspt_BR
dc.rights.licenseA 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.pt_BR
dc.description.abstract1The 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).pt_BR
dc.description.unidadeInstituto de Ciências Exatas (IE)pt_BR
dc.description.unidadeDepartamento de Ciência da Computação (IE CIC)pt_BR
dc.description.ppgPrograma de Pós-Graduação em Informáticapt_BR
Aparece nas coleções:Teses, dissertações e produtos pós-doutorado

Mostrar registro simples do item Visualizar estatísticas



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.