Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLSC-BBKGHV
Type: | Dissertação de Mestrado |
Title: | Automatic mining of tasks in structured programs |
Authors: | Pedro Henrique Ramos Costa |
First Advisor: | Fernando Magno Quintao Pereira |
First Referee: | Dorgival Olavo Guedes Neto |
Second Referee: | Luis Fabricio Wanderley Goes |
Abstract: | Esta dissertação descreve o desenvolvimento e implementação de um conjunto de análises estáticas para descobrir paralelismo de tarefas em programas originalmente escritos em um paradigma sequencial. As análises foram implementadas em uma ferramenta chamada TaskMiner, um compilador fonte-a-fonte que insere pragmas OpenMP em programas C/C++ sem intervenção humana. Taskminer determina intervalos de memória cobertos pela região de código a ser paralelizada, limita o número de tarefas recursivas ativas, estima a lucratividade de tarefas candidatas heuristicamente e se apoia no ambiente de execução do OpenMP para desambiguar ponteiros. TaskMiner anota programas complexos, e descobre oportunidades de paralelismo escondidas por muitos anos na sintaxe de benchmarks conhecidos, às vezes levando a ganhos de velocidade de até 400\% em uma máquina de 12 núcleos, sem nenhum custo extra de programação. |
Abstract: | This dissertation describes the design and implementation of a suit of static analyses and code generation techniques to annotate programs with OpenMP pragmas for task parallelism. These techniques approximate the ranges covered by memory regions, bound recursive tasks and estimate the profitability of tasks. These ideas have been implemented in a tool called TaskMiner, a source-to-source compiler that inserts OpenMP pragmas into C/C++ programs without any human intervention. By building onto the static program analysis literature, and relying on OpenMP's runtime ability to disambiguate pointers, TaskMiner is able to annotate large and convoluted programs, often replicating the performance gains of handmade annotation. Furthermore, the techniques employed in TaskMiner give us the means to discover opportunities of parallelism that remained buried in the syntax of well-known benchmarks for many years -- sometimes leading to up to four-fold speedups on a 12-core machine at zero programming cost. |
Subject: | Computação Paralelismo Processamento Paralelo Tarefas |
language: | Inglês |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLSC-BBKGHV |
Issue Date: | 16-Jul-2018 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
pedrohenriqueramoscosta.pdf | 1.94 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.