Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/330850
Type: TESE DIGITAL
Degree Level: Doutorado
Title: The batched DOACROSS algorithm = O algoritmo batched DOACROSS
Title Alternative: O algoritmo batched DOACROSS
Author: Lucas, Divino César Soares, 1985-
Advisor: Araújo, Guido Costa Souza de, 1962-
Abstract: Resumo: A paralelização de laços de programas contendo loop-carried dependences é considerada uma tarefa bastante difícil, principalmente devido ao sobrecusto imposto pela comunicação de dependências de dados entre iterações do laço paralelizado. Apesar do grande empenho em décadas recentes para criar algoritmos efetivos para paralelização deste tipo de laço o problema ainda é considerado longe de estar resolvido. Para muitos laços, antigos algoritmos, como o DOACROSS, bem como novos algoritmos, como Decoupled Software Pipeline (DSWP), não foram capazes de oferecer uma solução eficiente para o problema. Esta tese discute em detalhes dois (DOACROSS e DSWP) dos algoritmos mais proeminentes para a paralelização de tais laços e também mostra uma análise do desempenho de programas paralelizados usando estes algoritmos em diferentes arquiteturas de processadores. A partir desta análise surgiu o projeto de um novo algoritmo, chamado Batched DOACROSS (BDX), para fazer a paralelização deste tipo de laço. Este algoritmo foi pensado de forma a utilizar as melhores características destes algoritmos anteriores e ao mesmo tempo evitar o uso de propriedades que se mostraram ineficientes no passado. O algoritmo Batched DOACROSS não requer suporte de hardware (como é exigido por DSWP) e faz uso de estruturas locais às linhas de execução para reduzir o sobrecusto com sincronização entre elas. Uma extensão para o algoritmo BDX também é proposta, chamada Parallel Stage Batched DOACROSS (PS-BDX), e os resultados indicaram que para alguns casos esta extensão é capaz de produzir aumentos significativos de desempenho. BDX e PS-BDX são algoritmos que transformam o laço serial para executar paralelamente seguindo um formato de pipeline, além disso estes algoritmos empregam a execução de lotes de iterações para reduzir o custo de comunicação entre núcleos. Resultados de análise de sensibilidade mostram que estes novos algoritmos são capazes de produzir bons resultados até mesmo para laços pequenos (contendo em torno de 40 instruções) quando configurados em lotes com ao menos 100 iterações. A análise do algoritmo PS-BDX usando sete programas mostrou uma média de aumento de 1.85x no desempenho dos programas quando estes foram paralelizados usando 2 linhas de execução, 2.95x quando paralelizados com 4 linhas de execução e por fim 3.11x quando estes programas foram paralelizados usando 8 linhas de execução. Em todos estes casos o desempenho da versão paralelizada com PS-BDX foi melhor que o segundo melhor algoritmo experimentado (PS-DSWP). Uma análise quantitativa e qualitativa dos custo de sincronização em programas paralelizados usando os algoritmos acima também foi realizada. Os resultados indicaram que em média 30% do tempo de execução dos programas paralelos é gasto com sincronização de acesso a regiões críticas e a dados compartilhados. Também são mostrados resultados que indicam que as arquiteturas de computadores Intel Ivy Bridge e ARM A9 MPCore se encontram em extremos opostos em se tratando de requisitos para a paralelização de laços. Em consequência disto todos os algoritmos analisados enfretam dificuldades para melhorar o desempenho dos programas seriais

Abstract: Parallelizing loops containing loop-carried dependences has been considered a very difficult task, mainly due to the overhead imposed by communicating dependences between iterations. Despite the huge efforts in the past few decades to devise effective parallelization algorithms for such loops, the problem is still far from solved. For many loops, old DOACROSS, and new Decoupled Software Pipeline (DSWP), algorithms have not been able to offer a solution to this problem. This thesis discuss in detail two of the most prominent algorithms for parallelizing such loops and also present an analysis of the performance of the parallelized programs across different multicore architectures. Based on insights from this analyze a new algorithm, called Batched DOACROSS, for parallelizing these loops is proposed. Batched DOACROSS (BDX) capitalizes on the advantages of DSWP and DOACROSS, while minimizing their deficiencies. BDX does not require new hardware mechanisms (as DSWP does) and makes use of thread local buffers to reduce DOACROSS synchronization overheads. An extension to the baseline algorithm is proposed, named Parallel-Stage BDX (PS-BDX), and show that in some cases it can considerably improve the performance of the parallel loop. BDX and PS-BDX are pipelining multithreading algorithms that employs batching to amortize communication overheads. We provide results for a sensibility analysis and show that for small balanced loops (about 40 instructions), a batch size of only 100 iterations is sufficient to provide good speedups. Our analyze of PS-BDX for seven benchmarks showed an average of 1.85x speedup for 2 threads, 2.95x for 4 threads and 3.11x for 8 threads which was larger than the other best algorithm that we compared. A qualitative and quantitative analysis of synchronization costs of the three aforementioned loop parallelization algorithms (BDX, DOACROSS and DSWP) is performed for two modern computer architectures (ARM A9 MPCore and Intel Ivy Bridge). Our results show that at least 30% of the execution time of the programs we parallelized are spent on synchronization/data communication. We also show that, besides the problem being hard, Intel Ivy Bridge and ARM A9 MPCore are on opposite endpoints along the axis of commonly accepted requisites for efficient loop parallelization. As a consequence, all three algorithms struggle to effectively speedup several programs
Subject: Processamento paralelo (Computadores)
Programação paralela (Computação)
Processadores multicore
Algoritmos paralelos
Compiladores (Computadores)
Language: Inglês
Editor: [s.n.]
Citation: LUCAS, Divino César Soares. The batched DOACROSS algorithm = O algoritmo batched DOACROSS. 2017. 1 recurso online (91 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/330850>. Acesso em: 2 set. 2018.
Date Issue: 2017
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Lucas_DivinoCesarSoares_D.pdf1.21 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.