Repository logo
 

Automatic parallelization of "inherently" sequential nested loop programs

Simple item page
dc.contributor.authorZou, Yun, author
dc.contributor.authorRajopadhye, Sanjay, advisor
dc.contributor.authorStrout, Michelle, committee member
dc.contributor.authorBohm, A. P. Willem, committee member
dc.contributor.authorBreidt, F. Jay, committee member
dc.date.accessioned2007-01-03T08:22:40Z
dc.date.available2007-01-03T08:22:40Z
dc.date.issued2011
dc.description.abstractMost automatic parallelizers are based on detection of independent operations, and most of them cannot do anything if there is a true dependence between operations. However, there exists a class of programs for which this can be surmounted based on the nature of the operations. The standard and obvious cases are reductions and scans, which normally occur within loops. Existing work that deals with complicated reductions and scans normally focuses on the formalism, not the implementation. To help eliminate the gap between the formalism and implementation, we present a method for automatically parallelizing such "inherently" sequential programs. Our method is based on exact dependence analysis in the polyhedral model, and we formulate the problem as a detection that the loop body performs a computation that is equivalent to a matrix multiplication over a semiring. It handles both a single loop as well as arbitrarily nested loops. We also deal with mutually dependent variables in the loop. Our scan detection is implemented in a polyhedral program transformation and code generation system (AlphaZ) and used to generate OpenMP code. We also present optimization strategies to help improve the performance of the generated code. Experiments on examples demonstrate the scalability of programs parallelized by our implementation.
dc.format.mediumborn digital
dc.format.mediummasters theses
dc.identifierZou_colostate_0053N_10821.pdf
dc.identifierETDF2011400339COMS
dc.identifier.urihttp://hdl.handle.net/10217/70841
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.subjectscan and reduction
dc.subjectrecurrence equations
dc.subjectsemiring
dc.subjectautomatic parallelization
dc.subjectpolyhedral model
dc.titleAutomatic parallelization of "inherently" sequential nested loop programs
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineComputer Science
thesis.degree.grantorColorado State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science (M.S.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Zou_colostate_0053N_10821.pdf
Size:
458.3 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

2000-2019
Theses and Dissertations