Siddhartha Chatterjee

Irregular Computations in Fortran (2007)

. Modern dialects of Fortran enjoy wide use and good support on highperformance computers as performance-oriented programming languages. By providing the ability to express nested data parallelism,...

Expression And Implementation, Jan F. Prins, Siddhartha Chatterjee, Martin Simons

. Modern dialects of Fortran enjoy wide use and good support on highperformance computers as performance-oriented programming languages. By providing the ability to express nested data parallelism,...

"Low-End" DMA Coprocessor Speedups: Case Studies (2007)

Siddhartha Chatterjee, Allan L. Fisher

This paper examines the prospects for "low-end" coprocessors: custom devices, with one chip's worth of hardware, operating at system clock speeds and sharing a general purpose host...

y (2007)

Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi

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...

Daniela Genius (2007)

Philip J. Hanlon, Dean Chung, Siddhartha Chatterjee, Alvin R. Lebeck, Erin Parker

authors and should not be interpreted as representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. y

Cvl: ACVector Library Manual Version 2 (2007)

Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, Marco Zagha

Cvl is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....

Implementation of a Portable Nested Data-Parallel Language (2006)

Blelloch, Guy E., Chatterjee, Siddhartha, Hardwick, Jonathan C., Sipelstein, Jay, Zagha, Marco

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...

An automata-theoretic algorithm for counting solutions to Presburger formulas (2004)

Erin Parker, Siddhartha Chatterjee

Abstract. We present an algorithm for counting the number of integer solutions to selected free variables of a Presburger formula. We represent the Presburger formula as a deterministic finite...

A high-performance simd floating point unit for bluegene/l: Architecture, compilation, and algorithm design (2004)

Leonardo Bachega, Siddhartha Chatterjee, Kenneth A. Dockser, John A. Gunnels, Manish Gupta, Fred G. Gustavson, ...

We describe the design, implementation, and evaluation of a dual-issue SIMD-like extension of the PowerPC 440 floating-point unit (FPU) core. This extended FPU is targeted at both IBM’s massively...

Cache-efficient multigrid algorithms (2001)

Towards a Theory of Cache-Efficient Algorithms (2000)

Abstract. Multigrid is widely used as an efficient solver for sparse linear systems arising from the discretization of elliptic boundary value problems. Linear relaxation methods like Gauss-Seidel...

Sen, Sandeep, Chatterjee, Siddhartha, Dumir, Neeraj

We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our model, an...

Cache-Efficient Matrix Transposition (2000)

Siddhartha Chatterjee, Sandeep Sen

We investigate the memory system performance of several algorithms for transposing an # N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data cache,...

Cache-Efficient Matrix Transposition (2000)

Siddhartha Chatterjee, Sandeep Sen

We investigate the memory system performance of several algorithms for transposing an N \Theta N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data...

Towards a Theory of Cache-Efficient Algorithms (Extended Abstract) (2000)

Sandeep Sen, Siddhartha Chatterjee

) Sandeep Sen y Siddhartha Chatterjee z Submitted for publication Abstract We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with...

Recursive array layouts and fast parallel matrix multiplication (1999)

Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi

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....

Irregular Parallel Algorithms in Java (1999)

Brian Blount, Siddhartha Chatterjee, Michael Philippsen

The nested data-parallel programming model supports the design and implementation of irregular parallel algorithms. This paper describes work in progress to incorporate nested data parallelism into...

Recursive Array Layouts and Fast Matrix Multiplication (1999)

Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi

This paper investigates the use of recursive arraylayouts to improve performance and reduce variability.

Nonlinear Array Layouts for Hierarchical Memory Systems (1999)

Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi

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...

Recursive Array Layouts and Fast Parallel Matrix Multiplication (1999)

Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi

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....

Nonlinear Array Layouts for Hierarchical Memory Systems (1999)

Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi

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...

Recursive Array Layouts and Fast Parallel Matrix Multiplication (1999)

Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi

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....

Nonlinear Array Layouts for Hierarchical Memory Systems (1999)

Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi

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...

Towards a Theory of Cache-Efficient Algorithms (1999)

Sandeep Sen, Siddhartha Chatterjee

We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our model, an...

Recursive Array Layouts and Fast Matrix Multiplication (1999)

Siddhartha Chatterjee, Alvin R. Lebeck, Mithuna Thottethodi, Praveen K. Patnala

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...

Irregular parallel algorithms in JAVA (1999)

Nonlinear array layouts for hierarchical memory systems (1999)

Abstract. The nested data-parallel programming model supports the design and implementation of irregular parallel algorithms. This paper describes work in progress to incorporate nested data...

Siddhartha Chatterjee, Vibhor V. Jain, Alvin R. Lebeck, Shyam Mundhra, Mithuna Thottethodi

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...

CVL: A C Vector Library Manual. Version 2, (1998)

Blelloch, Guy E., Hardwick, Jonathan C., Sipelstein, Jay, Chatterjee, Siddhartha, Reid-Miller, Margaret

CVL is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....

Recursive Array Layouts and Fast Matrix Multiplication (1998)

Chatterjee, Siddhartha, Lebeck, Alvin R., Patnala, Praveen K., Thottehodi, Mithuna

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...

Exact Analysis of the Cache Behavior of Nested Loops (1998)

Chatterjee, Siddhartha, Parker, Erin, Hanlon, Philip J., Lebeck, Alvin R.

The authors develop from first principles an exact model of the behavior of loop nests executing in a memory hierarchy by using a nontraditional classification of misses that has the key property of...

The Combinatorics of Cache Misses During Matrix Multiplication (1998)

Hanlon, Philip J., Chung, Dean, Chatterjee, Siddhartha, Genius, Daniel, Lebeck, Alivn R., Parker, Erin

In this paper we construct an analytic model of cache misses during matrix multiplication. The analysis in this paper applies to square matrices of size 2m where the array layout function is given in...

Expressing irregular computations in modern Fortran dialects (1998)

An evaluation of Java for numerical computing (1998)

Abstract. Modern dialects of Fortran enjoy wide use and good support on highperformance computers as performance-oriented programming languages. By providing the ability to express nested data...

Expressing irregular computations in modern Fortran dialects (1998)

This paper describes the design and implementation of high performance numerical software in Java. Our primary goals are to characterize the performance of object-oriented numerical software written...

Tuning strassen’s matrix multiplication for memory efficiency (1998)

Abstract. Modern dialects of Fortran enjoy wide use and good support on highperformance computers as performance-oriented programming languages. By providing the ability to express nested data...

Mithuna Thottethodi, Siddhartha Chatterjee, Alvin R. Lebeck

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...

An evaluation of Java for numerical computing (1998)

Expressing Irregular Computations in Modern Fortran Dialects (1998)

Abstract. This paper describes the design and implementation of high performance numerical software in Java. Our primary goals are to characterize the performance of object-oriented numerical...

Tuning Strassen's Matrix Multiplication for Memory Efficiency (1998)

. Modern dialects of Fortran enjoy wide use and good support on highperformance computers as performance-oriented programming languages. By providing the ability to express nested data parallelism in...

Mithuna Thottethodi, Alvin R. Lebeck, Siddhartha Chatterjee

Strassen's algorithm for matrix multiplication gains its lower arithmetic complexityatthe expense of reduced locality of reference, which makes it challenging to implement the algorithm...

Tuning Strassen's Matrix Multiplication for Memory Efficiency (1998)

Mithuna Thottethodi, Siddhartha Chatterjee, Alvin R. Lebeck

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...

Architecture-efficient Strassen's Matrix Multiplication: A Case Study of Divide-and-Conquer Algorithms (1998)

Pauca Xiaobai, Siddhartha Chatterjee, V. Paúl Pauca, Xiaobai Sun, Siddhartha Chatterjee, Alvin Lebeck, ...

Many fast algorithms in arithmetic complexity have hierarchical or recursive structures that make efficient implementations on high performance computers with memory hierarchies non-trivial. In this...

An Evaluation of Java for Numerical Computing (1998)

Architecture-efficient Strassen's Matrix Multiplication: A Case Study of Divide-and-Conquer Algorithms (1997)

. This paper describes the design and implementation of high performance numerical software in Java. Our primary goals are to characterize the performance of object-oriented numerical software...

Paul Pauca, Xiaobai Sun, Siddhartha Chatterjee, Alvin Lebeck

Many fast algorithms in arithmetic complexity have hierarchical or recursive structures that make efficient implementations on high performance computers with memory hierarchies non-trivial. In this...

Direct all correspondence to: (1996)

Siddhartha Chatterjee, John R. Gilbert, Leonid Oliker, Robert Schreiber, Thomas J. Sheffler, Siddhartha Chatterjee, ...

*This work was performed while Chatterjee and Sheffier were postdoctoral scientists at RIACS, and Schreiber was a senior scientist at R1ACS. This work was supported by the NAS Systems Division via...

Piecewise execution of nested dataparallel programs (1996)

Daniel W. Palmer, Jan F. Prins, Siddhartha Chatterjee, Rickard E. Faith

Abstract. The technique of flattening nested data parallelism combines all the independent operations in nested apply-to-all constructs and generates large amounts of potential parallelism for both...

Runtime Performance of Parallel Array Assignment: An Empirical Study (1996)

Lei Wang James, James M. Stichnoth, Siddhartha Chatterjee

Generating code for the array assignment statement of High Performance Fortran(HPF) in the presence of block-cyclic distributions of data arrays is considered difficult, and several algorithms have...

COMP 122: Algorithms and Analysis Testing Graph Planarity (Part 1 of 2) (1996)

Runtime Performance of Parallel Array Assignment: An Empirical Study (1996)

Introduction In these two lectures, we will discuss the algorithm developed by Hopcroft and Tarjan [6] for efficiently testing whether a graph G = (V; E) is planar. This is an extremely elegant...

Lei Wang, James M. Stichnoth, Siddhartha Chatterjee

Generating code for the array assignment statement of High Performance Fortran(HPF) in the presence of block-cyclic distributions of data arrays is considered difficult, and several algorithms have...

Algorithms for Automatic Alignment of Arrays (1996)

Siddhartha Chatterjee, John R. Gilbert, Leonid Oliker, Robert Schreiber, Thomas J. Sheffler, Prof Siddhartha Chatterjee

Aggregate data objects (such as arrays) are distributed across the processor memories when compiling a data-parallel language for a distributed-memory machine. The mapping determines the amount of...

An object-oriented approach to nested data parallelism (1995)

Thomas J. Sheffler, Thomas J. Sheffler, Siddhartha Chatterjee, Siddhartha Chatterjee

This paper describes an implementation technique for integrating nested data parallelism into an object-oriented language. Data-parallel programming employs sets of data called "collections...

Aligning parallel arrays to reduce communication (1995)

Thomas J. Sheffler, Robert Schreiber, John R. Gilbert, Siddhartha Chatterjee, Thomas J. Sheffler, Robert Schreiber, ...

Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array...

An Object-Oriented Approach to Nested Data Parallelism (1995)

Thomas J. Sheffler, Siddhartha Chatterjee

This paper describes an implementation technique for integrating nested data parallelism into an object-oriented language. Data-parallel programming employs data aggregates called...

An Object-Oriented Approach to Nested Data Parallelism (1995)

Thomas J. Sheffler, Siddhartha Chatterjee

This paper describes an implementation technique for integrating nested data parallelism into an object-oriented language. Data-parallel programming employs sets of data called...

Efficient Distribution Analysis via Graph Contraction (1995)

Thomas J. Sheffler, Robert Schreiber, William Pugh, John R. Gilbert, Siddhartha Chatterjee

Alignment and distribution of data by an optimizing compiler is a dream of both manufacturers and users of parallel computers. The distribution problem has been formulated as an NP-complete graph...

Piecewise Execution of Nested Data-Parallel Programs (1995)

Daniel W. Palmer, Jan F. Prins, Siddhartha Chatterjee, Rickard E. Faith

The technique of flattening nested data parallelism combines all the independent operations in nested apply-to-all constructs and generates large amounts of potential parallelism for both regular and...

Generating Local Addresses and Communication Sets for Data-Parallel Programs (1995)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-Hua Teng, ...

Generating local addresses and communication sets is an important issue in distributedmemory implementations of data-parallel languages such as High Performance Fortran. We demonstrate a storage...

Locality, Communication, and Code Generation for Array-Parallel Languages (1995)

Aligning Parallel Arrays to Reduce Communication (1995)

We review our work on compiling array-parallel languages for distributed-memory parallel computers. We discuss compiler techniques for automatic determination of alignment and distribution...

Thomas J. Sheffler, Robert Schreiber, John R. Gilbert, Siddhartha Chatterjee

Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array...

Array distribution in data-parallel programs (1994)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Thomas J. Shefl:ler, Siddhartha Chatterjee, John R. Gilbert, ...

We consider dism_oution at compile time of the array data in a distributed-memory implementation of a data-parallel program written in a language like Fortran 90. We allow dynamic redistribution of...

Array distribution in data-parallel programs (1994)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Thomas J. Sheffler, Siddhartha Chatterjee, John R. Gilbert, ...

We consider distribution at compile time of the array data in a distributed-memory implementation of a data-parallel program written m a language like Fortran 90. We allow dynamic redistribution of...

Implementation of a Portable Nested Data-Parallel Language (1994)

Guy Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha

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...

Implementation of a Portable Nested Data-Parallel Language (1994)

Guy Blelloch Siddhartha, Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha

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...

Implementation of a Portable Nested Data-Parallel Language (1994)

G. Blelloch, S. Chatterjee, Siddhartha Chatterjee, J. Hardwick, J. Sipelstein, M. Zagha

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...

Programming Models, Compilers, and Algorithms for Irregular Data-Parallel Computations (1994)

Modeling Data-Parallel Programs with the Alignment-Distribution Graph (1994)

Advances in parallel computing have made it clear that the ability to express computations in a machine-independent manner and the ability to handle dynamic and irregular computations are two...

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Thomas J. Sheffler

We present an intermediate representation of a program called the Alignment-Distribution Graph that exposes the communication requirements of the program. The representation exploits ideas developed...

Array Distribution in Data-Parallel Programs (1994)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Thomas J. Sheffler

We consider distribution at compile time of the array data in a distributed-memory implementation of a dataparallel program written in a language like Fortran 90. We allow dynamic redistribution of...

Implementation of a Portable Nested Data-Parallel Language (1994)

Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha

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...

Compiling Nested Data-Parallel Programs for Shared-Memory Multiprocessors (1993)

Siddhartha Chatterjee Carnegie, Siddhartha Chatterjee

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...

Cmu-Cs-93-114 (1993)

School Of Computer, Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, ...

Cvl is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....

Cvl: A C Vector Library - Manual Version 2 (1993)

Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, Marco Zagha

CVL is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....

Mobile and Replicated Alignment of Arrays in Data-Parallel Programs (1993)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber

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...

Implementation of a Portable Nested Data-Parallel Language (1993)

Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha, Siddhartha Chatterjee

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...

Genetic Algorithms (1993)

Siddhartha Chatterjee, Siddhartha Chatterjee

Multigrid is widely used as an efficient solver for sparse linear systems arising from the discretization of elliptic boundary value problems. Linear relaxation methods such as Gauss–Seidel and...

The Alignment-Distribution Graph (1993)

Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber

Implementing a data-parallel language such as Fortran 90 on a distributed-memory parallel computer requires distributing aggregate data objects (such as arrays) among the memory modules attached to...

The alignment-distribution graph (1993)

Alignment-distribution Graph, Uncl As, Siddhartha Chatterjee, Siddhartha Chatterjee, Siddhartha Chatterjee, John R. Gilbert, ...

Implementing a data-parallel language such as Formm 90 on a distn_outed-memory parallel computer requires distn"outing aggregate data objects (such as arrays) among the memory modules...

Optimal Evaluation of Array Expressions on Massively Parallel Machines (1992)

Siddhartha Chatterjee Research, Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-hua Teng

this article was presented at the Second Workshop on Languages, Compilers, and Runtime Environments for Distributed Memory Multiprocessors, Boulder, Colorado, September 30#October 2, 1992.

Solving Linear Recurrences with Loop Raking (1992)

Guy E. Blelloch, Siddhartha Chatterjee, Marco Zagha

We present a variation of the partitionmethod for solving m th -order linear recurrences that is well-suited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor...

Solving Linear Recurrences with Loop Raking (1992)

Guy Blelloch, Marco Zagha, Siddhartha Chatterjee, Siddhartha Chatterjee

We present a variation of the partition method for solving linear recurrences that is wellsuited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor capabilities,...

Solving Linear Recurrences with Loop Raking (1992)

Guy Blelloch School, Guy E. Blelloch, Marco Zagha, Siddhartha Chatterjee, Prof Guy, E. Blelloch

We present a variation of the partition method for solving linear recurrences that is wellsuited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor capabilities,...

Compiling data-parallel programs for efficient execution on shared-memory multiprocessors /--Siddhartha Chatterjee. (1991)

Chatterjee, Siddhartha.

"October 1991."

Size and Access Inference for Data-Parallel Programs (1991)

Siddhartha Chatterjee, Guy E. Blelloch, Allan L. Fisher

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...

Scan Primitives for Vector Computers (1990)

Siddhartha Chatterjee, Guy E. Blelloch, Marco Zagha

This paper describes an optimized implementation of a set of scan (also called allprefix -sums) primitives on a single processor of a CRAY Y-MP, and demonstrates that their use leads to greatly...

VCODE: A Data-Parallel Intermediate Language (1990)

Guy Blelloch, Siddhartha Chatterjee

This paper describes VCODE, a data-parallel intermediate language. VCODE is designed to allow easy porting of data-parallel languages, such as C*, PARALATION LISP, and Fortran 8x, to a wide class of...

Reference Manual (Version 1.1) (1990)

Guy Blelloch, Siddhartha Chatterjee, Fritz Knabe, Jay Sipelstein, Marco Zagha

This report introduces VCODE, an intermediate language for data-parallel computations. VCODE is designed to allow easy porting of data-parallel languages, such as C*, PARALATION LISP, and Fortran 8x,...

Size and Access Inference for Data-Parallel Programs (1990)