umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parallelizing the Critical Path
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

For many parallel matrix computations the execution time is determinedby the length of the critical path. The baseline approach used to reduce the execution time is to adjust the task granularity. If the tasks are made smaller, the length of the critical path will decrease and by extension reduce the execution time for the computation. However, reducing the size of the tasks lowers the efficiency and adds parallel overhead. Another way to lessen the impact of the critical path is to parallelize the critical tasks. In theory, this would speed up the execution of the critical path while avoiding the problems associated with a finer granularity for the non-critical tasks. The aim of this paper is to investigate if an extended approach that incorporates a parallelization of the critical path, in addition to adjusting the granularity, can significantly outperform the baseline approach of simply adjusting the granularity. A comparative study is presented that measures the extended approach’s performance against the baseline approach, using triangular linear solve as the reference computation. The results show that the extended approach can outperform the baseline approach, most notably when there is an abundance of available cores. Redistribution of data and a change in the parallel task model are identified as possible areas of improvement.

Place, publisher, year, edition, pages
2016. , 59 p.
Series
UMNAD, 1073
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:umu:diva-128410OAI: oai:DiVA.org:umu-128410DiVA: diva2:1051981
Educational program
Master of Science Programme in Computing Science and Engineering
Supervisors
Examiners
Available from: 2016-12-06 Created: 2016-12-05 Last updated: 2016-12-06Bibliographically approved

Open Access in DiVA

fulltext(802 kB)61 downloads
File information
File name FULLTEXT01.pdfFile size 802 kBChecksum SHA-512
125f5f24681bf995e774fe0e9d8f15cd6702803c36fa8d9184c92910ab2757065c1e43e030bff11360726992665928bfe0c5c522d19924499953f25e7298cfc2
Type fulltextMimetype application/pdf

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 61 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 201 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf