Staff View
Software support for parallel processing of irregular and dynamic computations

Descriptive

Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
Genre (authority = RULIB-FS)
Other
Genre (authority = marcgt)
technical report
Genre (authority = RULIB-FS)
Dissertation
PhysicalDescription
InternetMediaType
application/pdf
Extent
1 online resource (181 pages) : illustrations
Note (type = special display note)
Technical report LCSR-TR-271
Name (type = corporate); (authority = RutgersOrg-School)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
TypeOfResource
Text
TitleInfo
Title
Software support for parallel processing of irregular and dynamic computations
Abstract (type = abstract)
Many real world scientific computing problems are irregular and dynamic, which pose great challenge to the effort of parallelization. In this thesis, we study the efficient mapping of a subclass of these problems, namely the "Stepwise slowly changing" irregular computations, onto distributed memory multiprocessors using the task graph scheduling approach. There exists a large class of applications which belong to this category. Intuitively, the irregularity requires sophisticated mapping algorithms, and the "slowness" in the changes of the computational structures between steps allows the scheduling cost to be amortized, justifying the approach.

We study three representative and widely-used applications in this thesis:The N-body simulation in particle physics, the Vortex-Sheet Roll-Up and the Contour Dynamics Computation from Computational Fluid Dynamics. We start with an initial global compile-time scheduling using PYRROS, and as this schedule degenerates over the iterative process, we apply new rescheduling algorithms to improve performance. We develop rescheduling algorithms for two important dynamic patterns: task graph weight variation, and dynamic spawning of new subgraphs. These algorithms are implemented and tested on irregular applications such as the N-body and Vortex-Sheet. Our experiments show that global scheduling using sophisticated methods can be beneficial for these problems, and our fast rescheduling algorithms can correct run-time imbalance with very low cost.

In summary, we introduce two new rescheduling heuristics and discuss several central issues such as schedule reuse, performance/scheduling overhead trade-off and the guidelines for choosing an appropriate rescheduling method. We identify classes of problems where rescheduling algorithms are applicable, and finally present experimental evidence to justify our approach.

Throughout the thesis, performance results are obtained from particular problems but presented in the general framework of software supporting systems. In addition, we examine an automatic task graph generation tool that can handle restricted cases of sequential code, and carry out its integration with PYRROS system. The new system is capable of realizing automatic parallelization of simple programs, a step forward to the grand challenge of fully automatic parallelization of regular and irregular code.
Name (type = personal)
NamePart (type = family)
Jiao
NamePart (type = given)
Jia
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Gerasoulis
NamePart (type = given)
Apostolos
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (type = text); (authority = RULIB)
chair
OriginInfo
DateCreated (encoding = w3cdtf); (qualifier = exact); (keyDate = yes)
1996-10
RelatedItem (type = host)
TitleInfo
Title
Computer Science (New Brunswick)
Identifier (type = local)
rucore21032500001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/t3-g50h-4y77
Back to the top

Rights

RightsDeclaration (AUTHORITY = rightsstatements.org); (TYPE = IN COPYRIGHT); (ID = http://rightsstatements.org/vocab/InC/1.0/)
This Item is protected by copyright and/or related rights.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).
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.4
ApplicationName
GPL Ghostscript 9.07
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:54
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:54
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019