PARADIGM Publications

A concise listing of publications with full bibliography entries is available in PostScript form as well as ASCII in BibTeX form. A complete listing of all abstracts is also available.

Available publications are grouped by the following categories.

Automatic data partitioning
Compile-time estimation of communication costs
Compilation and communication generation
Data redistribution & storage representations
Synthesis of high-level communication
Support for irregular computations
Exploitation of task and data parallelism
Automatic support for multithreaded execution
Compiler assisted algorithm based fault tolerance
Compiler Support for Distributed Shared Memory

Project Overview

The PARADIGM Compiler for Distributed-Memory Multicomputers. [300K]
P. Banerjee, J. A. Chandy, M. Gupta, E. W. Hodges IV, J. G. Holm, A. Lain, D. J. Palermo, S. Ramaswamy, and E. Su.
in IEEE Computer, Vol. 28, No. 10, pages 37-47, October 1995.

The PARADIGM Compiler for Distributed-Memory Message Passing Multicomputers. [107K]
P. Banerjee, J. A. Chandy, M. Gupta, J. G. Holm, A. Lain, D. J. Palermo, S. Ramaswamy, and E. Su
in Proceedings of the First International Workshop on Parallel Processing, pages 322-330, Bangalore, India, December 1994.

P. Joisha and P. Banerjee, ``PARADIGM (version 2.0): A New HPF Compilation System,'' Proc. 1999 International Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, April 1999.

P. Joisha and P. Banerjee, ``An Experimental Evaluation of a New HPF Compiler Framework Based on a Commercial Symbolic Analysis Package,'' submitted to IEEE Transactions on Software Engineering.

Recent Papers on the PARADIGM Compiler

D. Palermo, E. W. Hodges and P. Banerjee, ``Dynamic Data Partitioning for Distributed Memory Multicomputers,'' Journal of Parallel and Distributed Computing (Special Issue on Compilation Techniques for Distributed Memory Systems) November 1, 1996, Vol. 38, no. 2, pp. 158-175.

S. Ramaswamy, B. Simons and P. Banerjee, ``Optimizations for Efficient Array Redistribution on Distributed Memory Multicomputers,'' Journal of Parallel and Distributed Computing (Special Issue on Compilation Techniques for Distributed Memory Systems) November 1, 1996, Vol. 38, no. 2, pp. 217-228.

S. Ramaswamy, S. Sapatnekar, and P. Banerjee, ``A Framework for Exploiting Data and Functional Parallelism on Distributed Memory Multicomputers,'' IEEE Trans. Parallel and Distributed Systems, Vol. 8, No. 11, pp. 1098-1116, November 1997.

M. Kandemir, A. Choudhary, N. Shenoy, P. Banerjee, J. Ramanujam, ``A Linear Algebra Framework for Automatic Determination of Optimal Data Layouts,'' IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 2, February 1999.

M. Kandemir, P. Banerjee, A. Choudhary, J. Ramanujam, and N. Shenoy, ``A Global Communication Optimization Technique Based on Data Flow Analysis and Linear Algebra,'' ACM Trans. on Programming Languages and Systems (TOPLAS), Sept. 1999.

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee, ``A Matrix-Based Approach to Global Locality Optimization,'' Journal of Parallel and Distributed Computing, Special Issue on Compilation and Architectural Support for Parallel Applications, Vol. 58, No. 2, Aug. 1999.

A. Lain and P. Banerjee, ``Compiler and Run-Time Support for Exploiting Regularity Within Irregular Applications,'' to appear in IEEE Transactions on Parallel and Distributed Systems (IEEE TPDS).

D. Palermo, E. W. Hodges, and P. Banerjee, ``Techniques for Selecting and Analyzing Data Distributions,'' Workshop on Challenges in Compiling for Scalable Parallel Systems, New Orleans, LA, Oct. 1996.

D. Chakrabarti, A. Lain, and P. Banerjee, ``Evaluation of Compiler and Runtime Library Approaches for Supporting Parallel Regular Applications,'' Proc. Int. Parallel Processing Symp. (IPPS-98), Apr. 1998, Orlando, FL.

M. Kandemir, P. Banerjee, A. Choudhary, J. Ramanujam, N. Shenoy, ``A Generalized Framework for Global Communication Optimization,'' Proc. Int. Parallel Processing Symp. (IPPS-98), Apr. 1998, Orlando, FL.

D. R. Chakrabarti, N. Shenoy, A. Choudhary, and P. Banerjee, ``An Efficient Uniform Run-time Scheme for Mixed Regular-Irregular Applications,'' Proc. Int. Conf. Supercomputing (ICS-98), Melbourne, AUSTRALIA, July 1998.

M. Kandemir, A. Choudhary, N. Shenoy, J. Ramanujam, and P. Banerjee, ``A Hyperplane Based Approach for Optimizing Spatial Locality in Loop Nests,'' Proc. Int. Conf. Supercomputing (ICS-98), Melbourne, AUSTRALIA, July 1998.

M. Kandemir, J. Ramanujam, A. Choudhary, P. Banerjee, ``An iteration space transformation algorithm based on an explicit data layout representation for optimizing locality,'' Proc. Workshop on Languages and Compilers for Parallel Computing (LCPC-98), Chapel Hill, NC, Aug. 1998.

M. Kandemir, N. Shenoy, P. Banerjee, J. Ramanujam, and A. Choudhary, ``Minimizing Data and Synchronization Costs in One-Way Communication,'' Proc. Int. Conf. Parallel Processing (ICPP98), Minneapolis, MN, Aug. 1998.

M. Kandemir, A. Choudhary, J. Ramanujam, N. Shenoy, and P. Banerjee, ``Enhancing Spatial Locality Using Data Layout Optimizations,'' Proc. European Conference on Parallel Processing (Euro-Par'98), Southampton, ENGLAND, Sept. 1998.

M. Kandemir, A. Choudhary, J. Ramanujam, N. Shenoy, and P. Banerjee, ``A Matrix-Based Approach to the Global Locality Optimization Problem,'' Proc. Parallel Architectures and Compilation Techniques (PACT-98), Paris, FRANCE, Oct. 1998.

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee, "Improving Locality Using Loop and Data Transformations in an Integrated Framework" Proc. 31st International Symposium on Micro-Architecture (MICRO-31), Dallas, Texas, Dec. 1998.

D. Chakrabarti and P. Banerjee, ``A Novel Compilation Framework for Supporting Semi-Regular Distributions in Hybrid Applications,'' Proc. 1999 International Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, April 1999.

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee, ``A Graph Based Framework to Detect Optimal Memory Layouts for Improving Data Locality,'' Proc. 1999 International Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, April 1999.

P. Joisha and P. Banerjee, ``PARADIGM (version 2.0): A New HPF Compilation System,'' Proc. 1999 International Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, April 1999.

M. Kandemir, P. Banerjee, A. Choudhary, J. Ramanujam, and E. Ayguade, ``An ILP Approach for Optimizing Cache Locality,'' 1999 ACM International Conference on Supercomputing (ICS'99), Rhodes, Greece, June 1999.

D. Chakrabarti, N. Shenoy, A. Lain, A. Choudhary, P. Banerjee, ``An Efficient Uniform Compilation Scheme for Parallelizing Mized Regular-Irregular Applications,'' submitted to IEEE Transactions on Parallel and Distributed Systems.

M. Kandemir, N. Shenoy, P. Banerjee, J. Ramanujam, and A. Choudhary, ``Minimizing Data and Synchronization Costs in One-Way Communication,'' submitted to IEEE Trans. on Parallel and Dist. Systems, March 1998.

M. Kandemir, A. Choudhary, P. Banerjee, J. Ramanujam, and N. Shenoy, ``Minimizing Data and Synchronization Costs in One-Way Communication,,'' submitted to IEEE Transactions on Parallel and Distributed Systems, March 1998.

P. Joisha and P. Banerjee, ``An Experimental Evaluation of a New HPF Compiler Framework Based on a Commercial Symbolic Analysis Package,'' submitted to IEEE Transactions on Software Engineering.

M. Kandemir, J. Ramanujam, A. Choudhary, and P. Banerjee, ``An Iteration Space Transformation Technique for Optimizing Data Locality,'' submitted to IEEE Transactions on Computers, April 1999.

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee, ``Improving Locality Using Loop and Data Transformations in an Integrated Framework,'' submitted to ACM Transactions on Programming Languages and Systems, April 1999.

M. Kandemir, J. Ramanujam, A. Choudhary, and P. Banerjee, ``An Iteration Space Transformation Algorithm Based on Explicit Data Layout Representation for Optimizing Locality,'' in Languages and Compilers for Parallel Computers, Editors: S. Chatterjee et al., Lecture Notes in Computer Science, Springer-Verlag, 1999.

Automatic Data Partitioning

Compiler Techniques for Optimizing Communication and Data Distribution for Distributed-Memory Multicomputers. [560K]
D. J. Palermo.
PhD thesis, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, June 1996, CRHC-96-09/UILU-ENG-96-2215.

Automatic Selection of Dynamic Data Partitioning Schemes for Distributed-Memory Multicomputers. [199K]
D. J. Palermo and P. Banerjee.
in Proceedings of the 8th Workshop on Languages and Compilers for Parallel Computing, pages 392-406, Columbus, OH, August 1995.
(this paper is also available as Technical Report CRHC-95-09. [258K] )

PARADIGM: A Compiler for Automated Data Distribution on Multicomputers. [94K]
M. Gupta and P. Banerjee
in Proceedings of the 7th ACM International Conference on Supercomputing, Tokyo, Japan, July 1993.

Automatic Data Partitioning on Distributed Memory Multicomputers. [321K]
M. Gupta
PhD thesis, Department of Computer Science, University of Illinois, Urbana IL, September 1992, CRHC-92-19.

Demonstration of Automatic Data Partitioning Techniques for Parallelizing Compilers on Multicomputers. [111K]
M. Gupta and P. Banerjee
IEEE Transactions on Parallel and Distributed Systems, 3(2):179-193, March 1992.

Automatic Data Partitioning on Distributed Memory Multiprocessors. [68K]
M. Gupta and P. Banerjee
in Proceedings of the Sixth Distributed Memory Computing Conference, Portland, OR, April 1991.

Compile-time Estimation of Communication Costs

Compile-Time Estimation of Communication Costs of Programs. [154K]
M. Gupta and P. Banerjee
to appear in the Journal of Programming Languages, 1994.

Compile-Time Estimation of Communication Costs on Multicomputers. [65K]
M. Gupta and P. Banerjee
in Proceedings of 6th International Parallel Processing Symposium, pages 470-475, Beverly Hills, CA, March 1992.
(this paper is also available as Technical Report CRHC-91-16. [104K] )

Compilation and Communication Generation

Compiler Support for Privatization on Distributed-Memory Machines. [65K]
D. J. Palermo, E. Su, E. W. Hodges IV, and P. Banerjee.
in Proceedings of the 25th International Conference on Parallel Processing, Bloomingdale, IL, August 1996.

High Performance Fortran Support for the PARADIGM Compiler. [163K]
E. W. Hodges IV.
Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, October 1995, CRHC-95-23.

Advanced Compilation Techniques in the PARADIGM Compiler for Distributed-Memory Multicomputers. [119K]
E. Su, A. Lain, S. Ramaswamy, D. J. Palermo, E. W. Hodges IV, and P. Banerjee.
in Proceedings of the 9th ACM International Conference on Supercomputing, pages 424-433, Barcelona, Spain, July 1995.

Compiler Optimizations for Distributed Memory Multicomputers used in the PARADIGM Compiler. [208K]
D. J. Palermo, E. Su, J. A. Chandy, and P. Banerjee
in Proceedings of the 23rd International Conference on Parallel Processing, pages II:1-10, St. Charles, IL, August 1994.

Automating Parallelization of Regular Computations for Distributed Memory Multicomputers in the PARADIGM Compiler. [129K]
E. Su, D. J. Palermo, and P. Banerjee
in Proceedings of the 1993 International Conference on Parallel Processing, pages II:30-38, St. Charles, IL, August 1993.

Automating Parallelization of Regular Computations for Distributed-Memory Multicomputers.
E. Su
Master's thesis, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 1993.

Data Redistribution & Storage Representations

Interprocedural Array Redistribution Data-Flow Analysis. [75K]
D. J. Palermo, E. W. Hodges IV, and P. Banerjee.
in Proceedings of the 9th Workshop on Languages and Compilers for Parallel Computing, San Jose, CA, August 1996.
Springer-Verlag.

Automatic Generation of Efficient Array Redistribution Routines for Distributed Memory Multicomputers. [90K]
S. Ramaswamy and P. Banerjee.
in Proceedings of Frontiers '95: The Fifth Symposium on the Frontiers of Massively Parallel Computation, pages 342-349, McLean, VA, February 1995.
(this paper is also available as Technical Report CRHC-94-09. [126K] )

Processor Tagged Descriptors: A Data Structure for Compiling for Distributed-Memory Multicomputers. [89K]
E. Su, D. J. Palermo, and P. Banerjee
in Proceedings of the 1994 International Conference on Parallel Architectures and Compilation Techniques, pages 123-132, Montréal, Canada, August 1994.

Synthesis of High Level Communication

A Methodology for High-Level Synthesis of Communication on Multicomputers. [93K]
M. Gupta and P. Banerjee
in Proceedings of the Sixth ACM International Conference on Supercomputing, pages 357-367, Washington D.C., July 1992.

Support for Irregular Computations

Compiler and Run-Time Support for Irregular Computations. [395K]
A. Lain.
PhD thesis, Department of Computer Science, University of Illinois, Urbana, IL, October 1995, CRHC-92-22.

Exploiting Spatial Regularity in Irregular Iterative Applications. [104K]
A. Lain and P. Banerjee.
in Proceedings of the 9th International Parallel Processing Symposium, pages 820-827, Santa Barbara, CA, April 1995.

Techniques to Overlap Computation and Communication in Irregular Iterative Applications. [163K]
A. Lain and P. Banerjee
in Proceedings of the 8th ACM International Conference on Supercomputing, pages 236-245, Manchester, England, July 1994.

\item D. Chakrabarti, A. Lain, and P. Banerjee, ``Evaluation of Compiler and Runtime Library Approaches for Supporting Parallel Regular Applications,'' Proc. Int. Parallel Processing Symp. (IPPS-98), Apr. 1998, Orlando, FL. \item D. R. Chakrabarti, N. Shenoy, A. Choudhary, and P. Banerjee, ``An Efficient Uniform Run-time Scheme for Mixed Regular-Irregular Applications,'' Proc. Int. Conf. Supercomputing (ICS-98), Melbourne, AUSTRALIA, July 1998.

Task Parallelism

Compiling Matlab Programs to ScaLAPACK: Exploiting Task and Data Parallelism. [59K]
S. Ramaswamy, E. W. Hodges IV, and P. Banerjee.
in Proceedings of the International Parallel Processing Symposium, Honolulu, HI, April 1996.

Simultaneous Exploitation of Task and Data Parallelism in Regular Scientific Applications. [387KB]
S. Ramaswamy.
PhD thesis, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, January 1996.

Simultaneous Allocation and Scheduling Using Convex Programming Techniques. [96K]
S. Ramaswamy and P. Banerjee.
Parallel Processing Letters, December 1995, to appear.

A Convex Programming Approach for Exploiting Data and Functional Parallelism on Distributed Memory Multicomputers. [135K]
S. Ramaswamy, S. Sapatnekar, and P. Banerjee
in Proceedings of the 23rd International Conference on Parallel Processing, pages II:116-125, St. Charles, IL, August 1994.

A Framework for Exploiting Data and Functional Parallelism on Distributed Memory Multicomputers. [235K]
S. Ramaswamy, S. Sapatnekar, and P. Banerjee
Technical Report CRHC-94-10, Center for Reliable and High-Performance Computing, University of Illinois, Urbana, IL, June 1994.

Processor Allocation and Scheduling of Macro Dataflow Graphs on Distributed Memory Multicomputers. [69K]
S. Ramaswamy and P. Banerjee
in Proceedings of the 22nd International Conference on Parallel Processing, pages II:134-138, St. Charles, IL, August 1993.

A Scheduling Algorithm for Parallelizable Dependent Tasks. [46K]
K. P. Belkhale and P. Banerjee
in Proceedings of the International Parallel Processing Symposium, pages 500-506, Anaheim, CA, April 1991.

Approximate Algorithms for the Partitionable Independent Task Scheduling Problem. [40K]
K. P. Belkhale and P. Banerjee
in Proceedings of the 19th International Conference on Parallel Processing, pages 72-75, St. Charles, IL, August 1990.

Manual and Compiler Assisted Methods for Generating Fault-Tolerant Parallel Programs. [317K]
A. Roy-Chowdhury.
PhD thesis, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, December 1995, CRHC-95-27.

Compiler Assisted Generation of Error Detecting Parallel Programs. [175K]
A. Roy-Chowdhury and P. Banerjee.
Technical Report CRHC-95-20, Center for Reliable and High-Performance Computing, University of Illinois, Urbana, IL, August 1995.

Compiler Assisted Synthesis of Algorithm-Based Checking in Multiprocessors. [143K]
P. Banerjee, V. Balasubramanian, and A. Roy Chowdhury
in "Foundations of Dependable Computing: Vol III, System Implementation", Gary Koob editor, pages 159-211, Kluwer Academic Publishers, Boston, MA, 1994.