Result: A novel approach for partitioning iteration spaces with variable densities

Title:
A novel approach for partitioning iteration spaces with variable densities
Authors:
KEJARIWAL, Arun, NICOLAU, Alexandra, BANERJEE, Utpal, POLYCHRONOPOULOS, Constantine D
Source:
PPoPP'05 (Proceedings of the 2005 ACM SIGPLAN symposium on principles and practice of parallel programming). :120-131
Publisher Information:
New York NY: ACM Press, 2005.
Publication Year:
2005
Physical Description:
print, 26 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie programmation, Programming theory, Boucle programme, Program loop, Bucle programa, Partitionnement, Partitioning, Subdivisión, Programmation parallèle, Parallel programming, Programación paralela, Technique programmation, Programmation technique, Técnica programación, Boucle imbriquée, Nested loop, Espace itération
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Center for Embedded Computer Systems University of California at Irvine, Irvine, CA, United States
Intel Corporation, Santa Clara, CA, United States
Center for Supercomputing Research and Development University of Illinois at Urbana-Champaign, Urbana, IL, United States
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18182676
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18182676
Database:
PASCAL Archive

Further Information

Efficient partitioning of parallel loops plays a critical role in high performance and efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with rectangular iteration spaces, the problem of partitioning non-rectangular iteration spaces - e.g., triangular, trapezoidal iteration spaces - with variable densities has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning N-dimensional non-rectangular iteration spaces with variable densities. We present a unimodular loop transformation and a geometric approach for partitioning an iteration space along an axis corresponding to the outermost loop across a given number of processors to achieve near-optimal performance, i.e., to achieve near-optimal load balance across different processors. We present a case study to illustrate the effectiveness of our approach.