NDLI: A general approach for partitioning N-dimensional parallel nested loops with conditionals

Please wait, while we are loading the content...

Tell me who I am: an interactive recommendation system

Towards automatic parallelization of tree reductions in dynamic programming

Smooth scheduling under variable rates or the analog-digital confinement game

Why Intel is designing multi-core processors

Efficient parallel algorithms for dead sensor diagnosis and multiple access channels

Modeling instruction placement on a spatial architecture

Tight bounds for the Min-Max boundary decomposition cost of weighted graphs

Compact routing with additive stretch using distance labelings

A distributed O(1)-approximation algorithm for the uniform facility location problem

The cache complexity of multithreaded cache oblivious algorithms

Distributed random digraph transformations for peer-to-peer networks

Chip-level integration: the new frontier for microprocessor architecture

Publish and perish: definition and analysis of an n-person publication impact game

A general approach for partitioning N-dimensional parallel nested loops with conditionals

On the price of heterogeneity in parallel systems

An empirical study to compare two parallel programming models

Conflict-free coloring for intervals: from offline to online

Translating between itanium and sparc memory consistency models

On space-stretch trade-offs: lower bounds

Semi-oblivious routing

Playing push vs pull: models and algorithms for disseminating dynamic data in networks

Fault-tolerant semifast implementations of atomic read/write registers

Towards a scalable and robust DHT

Energy implications of multiprocessor synchronization

The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions

Astronomical real-time streaming signal processing on a Blue Gene/L supercomputer

Reconfigurable resource scheduling

The FG programming environment: good and good for you

Packet-mode emulation of output-queued switches

Strip packing with precedence constraints and strip packing with release times

On space-stretch trade-offs: upper bounds

An implementation report for parallel triangular decompositions

A performance analysis of local synchronization

Fair online load balancing

Parallel depth first vs. work stealing schedulers on CMP architectures

Network design with weighted players

Exponential separation of quantum and classical online space complexity

Minimizing the stretch when scheduling flows of biological requests

Introducing the hydra parallel programming system

On the communication complexity of randomized broadcasting in random-like graphs

Power-aware scheduling for makespan and flow

Towards small world emergence

The cache-oblivious gaussian elimination paradigm: theoretical framework and experimental evaluation

Symmetric network computation

Deterministic load balancing and dictionaries in the parallel disk model

Minimizing peak energy on mesh-connected systems

An envolutionary path towards virtual shared memory with random access

Promoting cooperation in selfish grids

A general approach for partitioning N-dimensional parallel nested loops with conditionals

Content Provider	ACM Digital Library
Author	Banerjee, Utpal Kejariwal, Arun Girkar, Milind Polychronopoulos, Constantine D. Nicolau, Alexandru Saito, Hideki Tian, Xinmin
Abstract	Parallel loops account for the greatest amount of parallelism in scientific and numerical codes. For example, most of the DO loops in SPEC CFP2000 and SPEC OMPM2001 are of DOALL type and account for a large percentage of the total execution time. One of the ways to exploit parallelism is to partition the iteration space of a DOALL loop amongst different processors in a parallel processor system. Naturally, a good partitioning is of key importance to achieve high performance and for efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with both rectangular and non-rectangular iteration spaces, the problem of partitioning loops with conditionals has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning parallel nested loops, both perfect and non-perfect, with conditionals, where the expressions in a conditional are affine functions of the outer loop indices. We present a loop transformation based on elimination of redundant constraints bounding the iteration space of a nested loop. The transformation plays a critical role during the (static) partitioning process as it helps to capture the "exact" lower and upper bounds (can be either a constant or symbolic) of the loop indices. We generate a canonical form of the loop nest using the transformation and employ the geometric approach we proposed earlier (in [1, 2]) for partitioning the iteration space along an axis corresponding to the outermost loop. For cases in which such a transformation does not exist, we propose a general approach for loop canonicalization. We present several examples from the literature and numerical packages to illustrate the effectiveness of our approach.
Starting Page	49
Ending Page	58
Page Count	10
File Format	PDF
ISBN	1595934529
DOI	10.1145/1148109.1148117
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-30
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Conditionals Fourier-motzkin elimination Partitioning Affine Parallel loops
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Automatic code generation for executing tiled nested loops onto parallel architectures

Parallel fourier-motzkin elimination.

Parallel Fourier-Motzkin Elimination (1996)

Parameterized tiled loops for free

An approach to form affine time partitioning for statement instances of arbitrarily nested loops

Blocking and array contraction across arbitrarily nested loops using affine partitioning

A novel approach for partitioning iteration spaces with variable densities

Blocking and Array Contraction Across Arbitrarily Nested Loops Using Affine Partitioning

A note on preprocessing via fourier-motzkin elimination in two-stage stochastic programming (1996).

A general approach for partitioning N-dimensional parallel nested loops with conditionals

Similar Documents

Automatic code generation for executing tiled nested loops onto parallel architectures

Parallel fourier-motzkin elimination.

Parallel Fourier-Motzkin Elimination (1996)

Parameterized tiled loops for free

An approach to form affine time partitioning for statement instances of arbitrarily nested loops

Blocking and array contraction across arbitrarily nested loops using affine partitioning

A novel approach for partitioning iteration spaces with variable densities

Blocking and Array Contraction Across Arbitrarily Nested Loops Using Affine Partitioning

A note on preprocessing via fourier-motzkin elimination in two-stage stochastic programming (1996).

A general approach for partitioning N-dimensional parallel nested loops with conditionals