Siddhartha Chatterjee

VLDB 2026 Research / reviewers in the wild / expert

dblp:c/SiddharthaChatterjee · DBLP profile ↗

← Back

32ranked-venue papers

16as first author

0since 2021 · last 2009

0000-0003-3100-7793ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Systems, architecture and hardware · 19 · 9 first-authorSoftware engineering, systems software and programming languages · 7 · 5 first-authorGraphics, computer vision, multimedia, augmented reality and games · 2 · 2 first-authorTheory of computation · 2Applied, interdisciplinary, general and emerging computing · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Computer architecture, parallel and distributed computing, and storage systems 18 papers		High-performance computing · 34% Parallel and multicore computing · 25% Memory systems · 23%
Software engineering, system software, and programming languages 10 papers		Compilers and program optimization · 94% Programming languages and type systems · 6%
Theoretical computer science 5 papers		Algorithms and data structures · 96% Computational complexity · 4%

Topics — the 30 heaviest of 49, each with the papers that count most for it

Topic	Weight	Papers	Last	Evidence papers
Parallel and multicore computing parallel programming models	0.1	5	2006	Shared memory programming for large scale machines · PLDI 2006 Optimal Evaluation of Array Expressions on Massively Parallel Machines · ACM Trans. Program. Lang. Syst. 1995 Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993
High-performance computing › supercomputing bluegene/l	0.1	2	2004	Unlocking the Performance of the BlueGene/L Supercomputer · SC 2004 An overview of the BlueGene/L Supercomputer · SC 2002
Compilers and program optimization optimizing compiler	0.1	2	2006	Shared memory programming for large scale machines · PLDI 2006 Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993
Memory systems cache	0.1	3	2002	Towards a theory of cache-efficient algorithms · J. ACM 2002 Tuning Strassen's Matrix Multiplication for Memory Efficiency · SC 1998 Recursive Array Layouts and Fast Matrix Multiplication · IEEE Trans. Parallel Distributed Syst. 2002
Memory systems › cache cache behavior	0.1	2	2002	Recursive Array Layouts and Fast Matrix Multiplication · IEEE Trans. Parallel Distributed Syst. 2002 Exact Analysis of the Cache Behavior of Nested Loops · PLDI 2001
Algorithms and data structures › memory hierarchy cache-efficient algorithms	0.1	2	2002	Towards a theory of cache-efficient algorithms · J. ACM 2002 Towards a theory of cache-efficient algorithms · SODA 2000
Parallel and multicore computing › parallel programming models › distributed memory programming models partitioned global address space	0.1	1	2006	Shared memory programming for large scale machines · PLDI 2006
High-performance computing › numerical linear algebra matrix multiplication	0.1	2	2002	Recursive Array Layouts and Fast Matrix Multiplication · IEEE Trans. Parallel Distributed Syst. 2002 Tuning Strassen's Matrix Multiplication for Memory Efficiency · SC 1998
Integrated circuit design › digital circuit design › arithmetic circuit design floating-point unit	0.0	1	2004	Unlocking the Performance of the BlueGene/L Supercomputer · SC 2004
High-performance computing supercomputer architecture	0.0	1	2004	Unlocking the Performance of the BlueGene/L Supercomputer · SC 2004
Compilers and program optimization parallelizing compiler	0.0	4	1996	Runtime Performance of Parallel Array Assignment: An Empirical Study · SC 1996 Optimal Evaluation of Array Expressions on Massively Parallel Machines · ACM Trans. Program. Lang. Syst. 1995 Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993
Compilers and program optimization › parallel language compilation data-parallel compilation	0.0	4	1993	Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993 Mobile and replicated alignment of arrays in data-parallel programs · SC 1993 Automatic Array Alignment in Data-Parallel Programs · POPL 1993
High-performance computing performance optimization	0.0	1	2002	Recursive Array Layouts and Fast Matrix Multiplication · IEEE Trans. Parallel Distributed Syst. 2002
High-performance computing supercomputing	0.0	1	2002	An overview of the BlueGene/L Supercomputer · SC 2002
Integrated circuit design system-on-chip	0.0	1	2002	An overview of the BlueGene/L Supercomputer · SC 2002
Algorithms and data structures › memory hierarchy › external memory algorithms i/o complexity	0.0	1	2002	Towards a theory of cache-efficient algorithms · J. ACM 2002
Parallel and multicore computing data-parallel programming	0.0	3	1995	Optimal Evaluation of Array Expressions on Massively Parallel Machines · ACM Trans. Program. Lang. Syst. 1995 Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993 Size and Access Inference for Data-Parallel Programs · PLDI 1991
Performance modeling and evaluation › simulation cache simulation	0.0	1	2001	Exact Analysis of the Cache Behavior of Nested Loops · PLDI 2001
Performance modeling and evaluation static performance analysis	0.0	1	2001	Exact Analysis of the Cache Behavior of Nested Loops · PLDI 2001
Memory systems › memory hierarchy cache and TLB effects	0.0	1	2000	Cache-Efficient Matrix Transposition · HPCA 2000
Memory systems › cache cache-aware algorithm design	0.0	1	2000	Towards a theory of cache-efficient algorithms · SODA 2000
Memory systems › memory hierarchy cache hierarchy	0.0	1	2000	Towards a theory of cache-efficient algorithms · SODA 2000
Memory systems › cache cache performance	0.0	1	2000	Cache-Efficient Matrix Transposition · HPCA 2000
Performance modeling and evaluation › performance model construction memory system performance modeling	0.0	1	2000	Cache-Efficient Matrix Transposition · HPCA 2000
Algorithms and data structures › memory hierarchy › external memory algorithms cache-oblivious algorithms	0.0	1	2000	Towards a theory of cache-efficient algorithms · SODA 2000
High-performance computing distributed memory systems	0.0	3	2006	Shared memory programming for large scale machines · PLDI 2006 Optimal Evaluation of Array Expressions on Massively Parallel Machines · ACM Trans. Program. Lang. Syst. 1995 Mobile and replicated alignment of arrays in data-parallel programs · SC 1993
Parallel and multicore computing › data parallelism nested data parallelism	0.0	2	1993	Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors · ACM Trans. Program. Lang. Syst. 1993 Implementation of a Portable Nested Data-Parallel Language · PPoPP 1993
High-performance computing numerical linear algebra	0.0	1	1998	Tuning Strassen's Matrix Multiplication for Memory Efficiency · SC 1998
Parallel and multicore computing › data distribution block-cyclic distribution	0.0	1	1996	Runtime Performance of Parallel Array Assignment: An Empirical Study · SC 1996
Parallel and multicore computing data distribution	0.0	1	1996	Runtime Performance of Parallel Array Assignment: An Empirical Study · SC 1996

Methods — techniques the papers use, named apart from their topics

asynchronous message · 0.1affinity test elimination · 0.1associativity analysis · 0.1performance analysis · 0.0benchmarking · 0.0winograd algorithm · 0.0system architecture design · 0.0strassen algorithm · 0.0recursive algorithm · 0.0performance scaling studies · 0.0memory hierarchy model · 0.0presburger arithmetic · 0.0cache simulation · 0.0memory model analysis · 0.0external-memory analysis · 0.0experimental validation · 0.0cache complexity analysis · 0.0dynamic programming · 0.0

Year	Publication	Venue	Position
2009	Compiler and runtime techniques for software transactional memory optimization abstract Abstract Software transactional memory (STM) systems are an attractive environment to evaluate optimistic concurrency. We describe our experience of supporting and optimizing an STM system at both the managed runtime and compiler levels. We describe the design policies of our STM system and the statistics collected by the runtime to identify performance bottlenecks and guide tuning decisions. We present an initial work on supporting automatic instrumentation of the STM primitives for C/C++ and Java programs in the IBM XL compiler and J9 Java virtual machine. We evaluate and discuss the performance of several transactional programs running on our system. Copyright © 2008 John Wiley & Sons, Ltd. Peng Wu 0001, Maged M. Michael, Christoph von Praun, Takuya Nakaike, Rajesh Bordawekar, Harold W. Cain, Calin Cascaval, Siddhartha Chatterjee, Stefanie Chiras, Mark F. Mergen, Michael F. Spear, Huayong Wang	Concurr. Comput. Pract. Exp.	8
2006	Shared memory programming for large scale machines abstract This paper describes the design and implementation of a scalable run-time system and an optimizing compiler for Unified Parallel C (UPC). An experimental evaluation on BlueGene/L®, a distributed-memory machine, demonstrates that the combination of the compiler with the runtime system produces programs with performance comparable to that of efficient MPI programs and good performance scalability up to hundreds of thousands of processors.Our runtime system design solves the problem of maintaining shared object consistency efficiently in a distributed memory machine. Our compiler infrastructure simplifies the code generated for parallel loops in UPC through the elimination of affinity tests, eliminates several levels of indirection for accesses to segments of shared arrays that the compiler can prove to be local, and implements remote update operations through a lower-cost asynchronous message. The performance evaluation uses three well-known benchmarks --- HPC RandomAccess, HPC STREAM and NAS CG --- to obtain scaling and absolute performance numbers for these benchmarks on up to 131072 processors, the full BlueGene/L machine. These results were used to win the HPC Challenge Competition at SC05 in Seattle WA, demonstrating that PGAS languages support both productivity and performance. Christopher Barton, Calin Cascaval, Gheorghe Almási 0001, Yili Zheng, Montse Farreras, Siddhartha Chatterjee, José Nelson Amaral	PLDI	6
2004	An Automata-Theoretic Algorithm for Counting Solutions to Presburger Formulas Erin Parker, Siddhartha Chatterjee	CC	2
2004	Unlocking the Performance of the BlueGene/L Supercomputer abstract The BlueGene/L supercomputer is expected to deliver new levels of application performance by providing a combination of good single-node computational performance and high scalability. To achieve good single-node performance, the BlueGene/L design includes a special dual floating-point unit on each processor and the ability to use two processors per node. BlueGene/L also includes both a torus and a tree network to achieve high scalability. We demonstrate how benchmarks and applications can take advantage of these architectural features to get the most out of BlueGene/L. Gheorghe Almási 0001, Siddhartha Chatterjee, Alan Gara, John A. Gunnels, Manish Gupta 0002, Amy Henning, José E. Moreira, Robert Walkup	SC	2
2003	Enabling Dual-Core Mode in BlueGene/L: Challenges and Solutions abstract BlueGene/L is a massively parallel computer system with 65536 dual-processor compute nodes. The peak performance of BlueGene/L is in excess of 360 TFLOP/s if both processor cores in a node are used for computation. The main challenge of deploying this dual-core mode of operation is that the L1 caches in each core are not hardware coherent. This forces a software-based approach to cache coherence and guides our design of a programming model for dual-core mode. We describe the design, implementation, and performance evaluation of system software for enabling the use of dual-core mode on BlueGene/L. Our preliminary performance results show that our approach to dual-core mode is effective for key numerical kernels. George S. Almási, Leonardo R. Bachega, Siddhartha Chatterjee, Manish Gupta 0002, Derek Lieber, Xavier Martorell, José E. Moreira	SBAC-PAD	3
2003	High-performance Java codes for computational fluid dynamics abstract Abstract The computational science community is reluctant to write large‐scale computationally‐intensive applications in Java due to concerns over Java's poor performance, despite the claimed software engineering advantages of its object‐oriented features. Naive Java implementations of numerical algorithms can perform poorly compared to corresponding Fortran or C implementations. To achieve high performance, Java applications must be designed with good performance as a primary goal. This paper presents the object‐oriented design and implementation of two real‐world applications from the field of computational fluid dynamics (CFD): a finite‐volume fluid flow solver (LAURA, from NASA Langley Research Center) and an unstructured mesh adaptation algorithm (2D_TAG, from NASA Ames Research Center). This work builds on our previous experience with the design of high‐performance numerical libraries in Java. We examine the performance of the applications using the currently available Java infrastructure and show that the Java version of the flow solver LAURA performs almost within a factor of 2 of the original procedural version. Our Java version of the mesh adaptation algorithm 2D_TAG performs within a factor of 1.5 of its original procedural version on certain platforms. Our results demonstrate that object‐oriented software design principles are not necessarily inimical to high performance. Copyright © 2003 John Wiley & Sons, Ltd. Christopher Riley, Siddhartha Chatterjee, Rupak Biswas	Concurr. Comput. Pract. Exp.	2
2002	Blue Gene/L, a System-On-A-Chip abstract Summary form only given. Large powerful networks coupled to state-of-the-art processors have traditionally dominated supercomputing. As technology advances, this approach is likely to be challenged by a more cost-effective System-On-A-Chip approach, with higher levels of system integration. The scalability of applications to architectures with tens to hundreds of thousands of processors is critical to the success of this approach. Significant progress has been made in mapping numerous compute-intensive applications, many of them grand challenges, to parallel architectures. Applications hoping to efficiently execute on future supercomputers of any architecture must be coded in a manner consistent with an enormous degree of parallelism. The BG/L program is developing a peak nominal 180 TFLOPS (360 TFLOPS for some applications) supercomputer to serve a broad range of science applications. BG/L generalizes QCDOC, the first System-On-A-Chip supercomputer that is expected in 2003. BG/L consists of 65,536 nodes, and contains five integrated networks: a 3D torus, a combining tree, a Gb Ethernet network, barrier/global interrupt network and JTAG. George S. Almási, Daniel K. Beece, Ralph Bellofatto, Gyan Bhanot, Randy Bickford, Matthias A. Blumrich, Arthur A. Bright, José R. Brunheroto, Calin Cascaval, José G. Castaños, Luis Ceze, Paul Coteus, Siddhartha Chatterjee, Dong Chen 0005, George L.-T. Chiu, Thomas M. Cipolla, Paul Crumley, Alina Deutsch, Marc Boris Dombrowa, Wilm E. Donath, Maria Eleftheriou, Blake G. Fitch, Joseph Gagliano, Alan Gara, Robert S. Germain, Mark Giampapa, Manish Gupta 0002, Fred G. Gustavson, Shawn Hall, Ruud A. Haring, David F. Heidel, Philip Heidelberger, Lorraine M. Herger, Dirk Hoenicke, T. Jamal-Eddine, Gerard V. Kopcsay, Alphonso P. Lanzetta, Derek Lieber, M. Lu, Mark P. Mendell, Lawrence S. Mok, José E. Moreira, Ben J. Nathanson, Matthew Newton, Martin Ohmacht, Rick A. Rand, Richard D. Regan, Ramendra K. Sahoo, Alda Sanomiya, Eugen Schenfeld, Sarabjeet Singh, Peilin Song, Burkhard D. Steinmacher-Burow, Karin Strauss, Richard A. Swetz, Todd Takken, R. Brett Tremaine, Mickey Tsao, Pavlos Vranas, T. J. Christopher Ward, Michael E. Wazlowski, J. Brown, Thomas A. Liebsch, A. Schram, G. Ulsh	CLUSTER	13
2002	Cache-efficient wavelet lifting in JPEG 2000 abstract The discrete wavelet transform (DWT), the technology at the heart of the JPEG 2000 image compression system, operates on user-definable tiles of the image, as opposed to fixed-size blocks of the image as does the discrete cosine transform (DCT) used in JPEG. This difference reduces artificial blocking effects but can severely stress the memory system. We examine the interaction of the DWT and the memory hierarchy, modify the structure of the DWT computation and the layout of the image data to improve cache and translation lookaside buffer (TLB) locality, and demonstrate significant performance improvements of the DWT over a baseline implementation. Our optimized DWT implementation exhibits speedups of up to 4/spl times/ over the DWT in a JPEG 2000 reference implementation. Siddhartha Chatterjee	ICME (1)	1
2002	An overview of the BlueGene/L Supercomputer abstract This paper gives an overview of the BlueGene/L Supercomputer. This is a jointly funded research partnership between IBM and the Lawrence Livermore National Laboratory as part of the United States Department of Energy ASCI Advanced Architecture Research Program. Application performance and scaling studies have recently been initiated with partners at a number of academic and government institutions,including the San Diego Supercomputer Center and the California Institute of Technology. This massively parallel system of 65,536 nodes is based on a new architecture that exploits system-on-a-chip technology to deliver target peak processing power of 360 teraFLOPS (trillion floating-point operations per second). The machine is scheduled to be operational in the 2004-2005 time frame, at price/performance and power consumption/performance targets unobtainable with conventional architectures. Narasimha R. Adiga, Gheorghe Almási 0001, George S. Almási, Yariv Aridor, Rajkishore Barik, Daniel K. Beece, Ralph Bellofatto, Gyan Bhanot, Randy Bickford, Matthias A. Blumrich, Arthur A. Bright, José R. Brunheroto, Calin Cascaval, José G. Castaños, Waiman Chan, Luis Ceze, Paul Coteus, Siddhartha Chatterjee, Dong Chen 0005, George L.-T. Chiu, Thomas M. Cipolla, Paul Crumley, K. M. Desai, Alina Deutsch, Tamar Domany, Marc Boris Dombrowa, Wilm E. Donath, Maria Eleftheriou, C. Christopher Erway, J. Esch, Blake G. Fitch, Joseph Gagliano, Alan Gara, Rahul Garg 0001, Robert S. Germain, Mark Giampapa, Balaji Gopalsamy, John A. Gunnels, Manish Gupta 0002, Fred G. Gustavson, Shawn Hall, Ruud A. Haring, David F. Heidel, Philip Heidelberger, Lorraine M. Herger, Dirk Hoenicke, R. D. Jackson, T. Jamal-Eddine, Gerard V. Kopcsay, Elie Krevat, Manish P. Kurhekar, Alphonso P. Lanzetta, Derek Lieber, L. K. Liu, M. Lu, Mark P. Mendell, A. Misra, Yosef Moatti, Lawrence S. Mok, José E. Moreira, Ben J. Nathanson, Matthew Newton, Martin Ohmacht, Adam J. Oliner, Vinayaka Pandit, R. B. Pudota, Rick A. Rand, Richard D. Regan, Bradley Rubin, Albert E. Ruehli, Silvius Vasile Rus, Ramendra K. Sahoo, Alda Sanomiya, Eugen Schenfeld, M. Sharma, Edi Shmueli, Sarabjeet Singh, Peilin Song, Vijay Srinivasan, Burkhard D. Steinmacher-Burow, Karin Strauss, Christopher W. Surovic, Richard A. Swetz, Todd Takken, R. Brett Tremaine, Mickey Tsao, Arun R. Umamaheshwaran, P. Verma, Pavlos Vranas, T. J. Christopher Ward, Michael E. Wazlowski, W. Barrett, C. Engel, B. Drehmel, B. Hilgart, D. Hill, F. Kasemkhani, David J. Krolak, Chun-Tao Li 0001, Thomas A. Liebsch, James A. Marcella, A. Muff, A. Okomo, M. Rouse, A. Schram, M. Tubbs, G. Ulsh, Charles D. Wait, J. Wittrup, Myung Bae, Kenneth A. Dockser, Lynn Kissel, Mark K. Seager, Jeffrey S. Vetter, K. Yates	SC	18
2002	Towards a theory of cache-efficient algorithms abstract We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations. As a corollary, we obtain cache-efficient algorithms in the single-level cache model for fundamental problems like sorting, FFT, and an important subclass of permutations. We also analyze the average-case cache behavior of mergesort, show that ignoring associativity concerns could lead to inferior performance, and present supporting experimental evidence.We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting. Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and for dealing with the hitherto unresolved problem of limited associativity. Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir	J. ACM	2
2002	Recursive Array Layouts and Fast Matrix Multiplication abstract The performance of both serial and parallel implementations of matrix multiplication is highly sensitive to memory system behavior. False sharing and cache conflicts cause traditional column-major or row-major array layouts to incur high variability in memory system performance as matrix size varies. This paper investigates the use of recursive array layouts to improve performance and reduce variability. Previous work on recursive matrix multiplication is extended to examine several recursive array layouts and three recursive algorithms: standard matrix multiplication and the more complex algorithms of Strassen (1969) and Winograd. While recursive layouts significantly outperform traditional layouts (reducing execution times by a factor of 1.2-2.5) for the standard algorithm, they offer little improvement for Strassen's and Winograd's algorithms. For a purely sequential implementation, it is possible to reorder computation to conserve memory space and improve performance between 10 percent and 20 percent. Carrying the recursive layout down to the level of individual matrix elements is shown to be counterproductive; a combination of recursive layouts down to canonically ordered matrix tiles instead yields higher performance. Five recursive layouts with successively increasing complexity of address computation are evaluated and it is shown that addressing overheads can be kept in control even for the most computationally demanding of these layouts. Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi	IEEE Trans. Parallel Distributed Syst.	1
2001	Exact Analysis of the Cache Behavior of Nested Loops abstract We develop from first principles an exact model of the behavior of loop nests executing in a memory hicrarchy, by using a nontraditional classification of misses that has the key property of composability. We use Presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. We use existing tools to simplify these formulas and to count cache misses. The model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. The complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. Validation against cache simulation confirms the exactness of our formulation. Our method can serve as the basis for a static performance predictor to guide program and data transformations to improve performance. Siddhartha Chatterjee, Erin Parker, Philip J. Hanlon, Alvin R. Lebeck	PLDI	1
2001	The Combinatorics of Cache Misses during Matrix Multiplication Philip J. Hanlon, Dean Chung, Siddhartha Chatterjee, Daniela Genius, Alvin R. Lebeck, Erin Parker	J. Comput. Syst. Sci.	3
2000	Cache-Efficient Matrix Transposition abstract We investigate the memory system performance of several algorithms for transposing an N/spl times/N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data cache, the translation lookaside buffer, register tiling, and the array layout function to the overall running time of the algorithms. We use various memory models to capture and analyze the effect of various facets of cache memory architecture that guide the choice of a particular algorithm, and attempt to experimentally validate the predictions of the model. Our major conclusions are as follows: limited associativity in the mapping from main memory addresses to cache sets can significantly degrade running time; the limited number of TLB entries can easily lead to thrashing; the fanciest optimal algorithms are not competitive on real machines even at fairly large problem sizes unless cache miss penalties are quite high: low-level performance tuning "hacks", such as register tiling and array alignment, can significantly distort the effects of improved algorithms; and hierarchical non-linear layouts are inherently superior to the standard canonical layouts (such as row- or column-major) for this problem. Siddhartha Chatterjee, Sandeep Sen	HPCA	1
2000	Towards a theory of cache-efficient algorithms Sandeep Sen, Siddhartha Chatterjee	SODA	2
1999	Nonlinear array layouts for hierarchical memory systems abstract Programming languages that provide multidimensional arrays and a flat linear model of memory must implement a mapping between these two domains to order array elements in memory.This layout function is fixed at language definition time and constitutes an invisible, non-programmable array attribute.In reality, modem memory systems are architecturally hierarchical rather than flat, with substantial differences in performance among different levels of the hierarchy.This mismatch between the model and the true architecture of memory systems can result in low locality of reference and poor performance.Some of this loss in performance can be recovered by re-ordering computations using transformations such as loop tiling.We explore nonlinear array layout functions as an additional means of improving locality of reference.For a benchmark suite composed of dense matrix kernels, we show by timing and simulation that two specific layouts (4D and Morton) have low implementation costs (2-5% of total running time) and high performance benefits (reducing execution time by factors of 1.1-2.5);that they have smooth performance curves, both across a wide range of problem sizes and over representative cache architectures; and that recursion-based control structures may be needed to tilly exploit their potential. Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi	International Conference on Supercomputing	1
1999	Recursive Array Layouts and Fast Parallel Matrix Multiplication abstract Matrix multiplication is an important kernel in linear algebra algorithms, and the performance of both serial and parallel implementations is highly dependent on the memory system behavior. Unfortunately, due to false sharing and cache conflicts, traditional column-major or row-major array layouts incur high variability in memory system performance as matrix size varies. This paper investigates the use of recursive array layouts for improving the performance of parallel recursive matrix multiplication algorithms. We extend previous work by Frens and Wise on recursive matrix multiplication to examine several recursive array layouts and three recursive algorithms: standard matrix multiplication, and the more complex algorithms of Strassen and Winograd. We show that while recursive array layouts significantly outperform traditional layouts (reducing execution times by a factor of 1.2--2.5) for the standard algorithm, they offer little improvement for Strassen's and Winograd's algorithms; ... Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi	SPAA	1
1998	Tuning Strassen's Matrix Multiplication for Memory Efficiency abstract Strassen's algorithm for matrix multiplication gains its lower arithmetic complexity at the expense of reduced locality of reference, which makes it challenging to implement the algorithm efficiently on a modern machine with a hierarchical memory system. We report on an implementation of this algorithm that uses several unconventional techniques to make the algorithm memory-friendly. First, the algorithm internally uses a non- standard array layout known as Morton order that is based on a quad-tree decomposition of the matrix. Second, we dynamically select the recursion truncation point to minimize padding without affecting the performance of the algorithm, which we can do by virtue of the cache behavior of the Morton ordering. Each technique is critical for performance, and their combination as done in our code multiplies their effectiveness. Performance comparisons of our implementation with that of competing implementations show that our implementation often outperforms the alternative techniques (up to 25%). However, we also observe wide variability across platforms and across matrix sizes, indicating that at this time, no single implementation is a clear choice for all platforms or matrix sizes. We also note that the time required to convert matrices to/from Morton order is a noticeable amount of execution time (5% to 15%). Eliminating this overhead further reduces our execution time. Mithuna Thottethodi, Siddhartha Chatterjee, Alvin R. Lebeck	SC	2
1996	Runtime Performance of Parallel Array Assignment: An Empirical Study abstract Compiling the array assignment statement of High Performance Fortran in the presence of block-cyclic distributions of data arrays is considered difficult, and several algorithms have been published to solve this problem. We present a comprehensive study of the performance of these algorithms. We classify these algorithms into several families and identify several issues of interest in the compilation process, and present experimental performance data for the various algorithms. We demonstrate that block-cyclic distributions can be compiled almost as efficiently as block and cyclic distributions. James M. Stichnoth, Siddhartha Chatterjee	SC	3
1996	Algorithms for Automatic Alignment of Arrays Siddhartha Chatterjee, John R. Gilbert, Leonid Oliker, Robert Schreiber, Thomas J. Sheffler	J. Parallel Distributed Comput.	1
1995	Solving Linear Recurrences with Loop Raking Guy E. Blelloch, Siddhartha Chatterjee, Marco Zagha	J. Parallel Distributed Comput.	2
1995	Generating Local Address and Communication Sets for Data-Parallel Programs Siddhartha Chatterjee, John R. Gilbert, Fred J. E. Long, Robert Schreiber, Shang-Hua Teng	J. Parallel Distributed Comput.	1
1995	Optimal Evaluation of Array Expressions on Massively Parallel Machines abstract We investigate the problem of evaluating Fortran 90-style array expressions on massively parallel distributed-memory machines. On such a machine, an elementwise operation can be performed in constant time for arrays whose corresponding elements are in the same processor. If the arrays are not aligned in this manner, the cost of aligning them is part of the cost of evaluating the expression tree. The choice of where to perform the operation then affects this cost. We describe the communication cost of the parallel machine theoretically as a metric space; we model the alignment problem as that of finding a minimum-cost embedding of the expression tree into this space. We present algorithms based on dynamic programming that solve the embedding problem optimally for several communication cost metrics: multidimensional grids and rings, hypercubes, fat-trees, and the discrete metric. We also extend our approach to handle operations that change the shape of the arrays. Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-Hua Teng	ACM Trans. Program. Lang. Syst.	1
1994	Implementation of a Portable Nested Data-Parallel Language Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha, Siddhartha Chatterjee	J. Parallel Distributed Comput.	5
1993	Automatic Array Alignment in Data-Parallel Programs abstract Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distributed-memory parallel machine by requiring nonlocal data accesses. Determining array alignments that reduce communication is therefore a key issue in compiling such languages. Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-Hua Teng	POPL	1
1993	Implementation of a Portable Nested Data-Parallel Language abstract This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as well as nested data-parallel function calls. These features allow the concise description of parallel algorithms on irregular data, such as sparse matrices and graphs. In addition, they maintain the advantages of data-parallel languages: a simple programming model and portability. The current NESL implementation is based on an intermediate language called VCODE and a library of vector routines called CVL. It runs on the Connection Machine CM-2, the Cray Y-MP C90, and serial machines. We compare initial benchmark results of NESL with those of machine-specific code on these machines for three algorithms: least-squares line-fitting, median finding, and a sparse-matrix vector product. These results show that NESL's performance is competitive with that of machine-specific codes for regular dense data, and is often superior for irregular data. Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha	PPoPP	2
1993	Generating Local Address and Communication Sets for Data-Parallel Programs abstract Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution, and a computation involving the regular section A(l:h:s), the local memory access sequence for any processor is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time. Siddhartha Chatterjee, John R. Gilbert, Fred J. E. Long, Robert Schreiber, Shang-Hua Teng	PPoPP	1
1993	Mobile and replicated alignment of arrays in data-parallel programs abstract When a data-parallel language like FORTRAN 90 is compiled for a distributed-memory machine, aggregate data objects (such as arrays) are distributed across the processor memories. The mapping determines the amount of residual communication needed to bring operands of parallel operations into alignment with each other. A common approach is to break the mapping into two stages: first, an alignment that maps all the objects to an abstract template, and then a distribution that maps the template to the processors. We solve two facets of the problem of finding alignments that reduce residual communication: we determine alignments that vary in loops, and objects that should have replicated alignments. We show that loop-dependent mobile alignment is sometimes necessary for optimum performance, and we provide algorithms with which a compiler can determine good mobile alignments for objects within do loops. We also identify situations in which replicated alignment is either required by the program itself (via spread operations) or can be used to improve performance. We propose an algorithm based on network flow that determines which objects to replicate so as to minimize the total amount of broadcast communication in replication. This work on mobile and replicated alignment extends our earlier work on determining static alignment. Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber	SC	1
1993	Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors abstract While data parallelism is well-suited from algorithmic, architectural, and linguistic considerations to serve as a basis for portable parallel programming, its characteristic fine-grained parallelism makes the efficient implementation of data-parallel languages on MIMD machines a challenging task. The design, implementation, and evaluation of an optimizing compiler are presented for an applicative nested data-parallel language called VCODE targeted at the Encore Multimax, a shared-memory multiprocessor. The source language supports nested aggregate data types; aggregate operations including elementwise forms, scans, reductions, and permutations; and conditionals and recursion for control flow. A small set of graph-theoretic compile-time optimizations reduce the overheads on MIMDmachines in several ways: by increasing the grain size of the output program, by reducing synchronization and storage requirements, and by improving locality of reference. The two key ideas behind these... Siddhartha Chatterjee	ACM Trans. Program. Lang. Syst.	1
1991	Size and Access Inference for Data-Parallel Programs abstract Abstract: "Data-parallel programming languages have many desirable features, such as single-thread semantics and the ability to express fine-grained parallelism. However, it is challenging to implement such languages efficiently on conventional MIMD multiprocessors, because these machines incur a high overhead for small grain sizes. This paper presents compile-time analysis techniques for data-parallel program graphs that reduce these overheads in two ways: by stepping up the grain size, and by relaxing the synchronous nature of the computation without altering the program semantics.The algorithms partition the program graph into clusters of nodes such that all nodes in a cluster have the same loop structure, and futher refine these clusters into epochs based on generation and consumption patterns of data vectors. This converts the fine-grain parallelism in the original program to medium-grain loop parallelism, which is better suited to MIMD machines. A compiler has been implemented based on these ideas. We present performance results for data-parallel kernels analyzed by the compiler and converted to single-program multiple-data (SPMD) code running on an Encore Multimax." Siddhartha Chatterjee, Guy E. Blelloch, Allan L. Fisher	PLDI	1
1990	Scan primitives for vector computers abstract The authors describe an optimized implementation of a set of scan (also called all-prefix-sums) primitives on a single processor of a CRAY Y-MP, and demonstrate that their use leads to greatly improved performance for several applications that cannot be vectorized with existing computer technology. The algorithm used to implement the scans is based on an algorithm for parallel computers. A set of segmented versions of these scans is only marginally more expensive than the unsegmented versions. The authors describe a radix sorting routine based on the scans that is 13 times faster than a Fortran version and within 20% of a highly optimized library sort routine, three operations on trees that are between 10 to 20 times faster than the corresponding C versions, and a connectionist learning algorithm that is 10 times faster than the corresponding C version for sparse and irregular networks.> Siddhartha Chatterjee, Guy E. Blelloch, Marco Zagha	SC	1
1989	Connected speech recognition on a multiple processor pipeline abstract The authors report on efforts to put a connected speech recognition application on the MARS hardware accelerator. The beam-search algorithm chosen for this purpose was decomposed on a functional basis, not on a data-partitioning basis as in other attempts. This allows for easy synchronization and static load balancing. Further flexibility is provided by retaining the hierarchical structure of the speech graph. The implementation is being tested on a 1000-word vocabulary and preprocessed input data.> Siddhartha Chatterjee, Prathima Agrawal	ICASSP	1