Non-uniform dependences partitioned by recurrence chains

Yu, Yijun and D'Hollander, E. H. (2004). Non-uniform dependences partitioned by recurrence chains. In: 2004 International Conference on Parallel Processing (ICPP'04), 15-18 Aug 2004, Montreal, Canada.

Full text available as:

Preview

PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (226Kb)

DOI (Digital Object Identifier) Link:	http://dx.doi.org/doi:10.1109/ICPP.2004.1327909
Google Scholar:	Look up in Google Scholar

Abstract

Non-uniform distance loop dependences are a known obstacle to find parallel iterations. To find the outermost loop parallelism in these �irregular� loops, a novel method is presented based on recurrence chains. The scheme organizes non-uniformly dependent iterations into lexicographically ordered monotonic chains. While the initial and final iteration of monotonic chains form two parallel sets, the remaining iterations form an intermediate set that can be partitioned further. When there is only one pair of coupled array references, the non-uniform dependences are represented by a single recurrence equation. In that case, the chains in the intermediate set do not bifurcate and each can be executed as a WHILE loop. The independent iterations and the initial iterations of monotonic dependence chains constitute the outermost parallelism. The proposed approach compares favorably with other treatments of nonuniform dependences in the literature. When there are multiple recurrence equations, a dataflow parallel execution can be scheduled using the technique extensively to find maximum loop parallelism.

Item Type:	Conference Item
Copyright Holders:	2004 IEEE
Extra Information:	Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Keywords:	WHILE loop; data flow execution; loop parallelism; nonuniform distance loop dependence; parallel iteration; recurrence chain; recurrence equation
Academic Unit/Department:	Mathematics, Computing and Technology > Computing
Interdisciplinary Research Centre:	Centre for Research in Computing (CRC)
Item ID:	24313
Depositing User:	Yijun Yu
Date Deposited:	22 Feb 2011 11:42
Last Modified:	22 Feb 2011 18:42
URI:	http://oro.open.ac.uk/id/eprint/24313

Actions (login may be required)

	View Item
RDF+XMLBibTeXRDF+N-TriplesJSONDublin CoreAtomOAI-ORE Resource Map (Atom Format)Simple MetadataReferMETSOAI-ORE Resource Map (RDF Format)HTML CitationASCII CitationMultiline CSVRefMan RIS Format (UTF-8)OpenURL ContextObjectEndNoteMODSOpenURL ContextObject in SpanMPEG-21 DIDLEP3 XMLRefMan RIS FormatRDF+N3Eprints Application Profile	Public: Report issue / request change