Arun Chauhan - US grants

A combination of factors has resulted in an industry-wide move to build multiple cores on a single chip to sustain the rate of growth in the computing power of processors. At the same time, high-level programming systems (e.g., scripting languages) have gained tremendous popularity motivated by dramatically higher programming productivity that such systems afford compared to traditional programming languages, such as C/C++ or Java. Unfortunately, these two trends combine to increase the gap between application software and the underlying hardware, which negatively impacts hardware utilization. An important reason is the critical nature of memory subsystems on the modern multi-core processors and a lack of any systematic methods to derive the memory behavior of programs written in high-level programming systems. This research aims at addressing the problem by developing a theoretical model to estimate the memory behavior of programs written in MATLAB and implementing the model in a prototype compiler.

A quantitative metric that past researchers have found useful in memory-related optimizations is reuse distance. Defined as the volume of data accessed between two successive references to a memory location, the goal is to transform programs to lower most of their reuse distances to below a threshold (usually, related to cache size).
By restricting the computation of reuse distances to locations accessible at the source-level it is possible to define source-level reuse distance. The metric, even though approximate, enables crucial analysis for high-level programming systems that often benefit remarkably from source-level transformations. This research develops efficient algorithms for source-level reuse distance analysis, validates it against the actual program behavior, and implements it in a MATLAB compiler to drive memory-related optimizations, especially those related to array accesses.

Parallel programs are typically written using a style in which independent processes are expressed sequentially and use locally-expressed message passing as a means of data exchange as well as a means of inter-process synchronization. From the network relationships that are implied by messaging among processes arise implicit data structures and implicit algorithms - that is, global parallel data structures and global parallel algorithms for which there is no explicit global representation. Limited only to a local approach for creating parallel programs, achieving correctness and performance of large-scale parallel algorithms is rapidly moving beyond our reasoning abilities. To address this shortcoming, this project develops a declarative language approach for describing new high-level communication operations, a means for composing these operations with computations, and a means for expressing transformations for optimizing the resulting compositions.

This project's implementation plan is based on aggressive evolution of the technology that is currently most effective in large-scale parallel computing - namely, explicitly managed shared data. In the distributed-memory case this is achieved with message passing, but the same discipline can be applied in the shared memory case as well. This project's approach may enable higher levels of expressiveness and abstraction for data management, communication, and coordination. Moreover, the separation of concerns that is naturally imposed between communication and computation greatly simplifies the mental model and implementation effort for programmers. In order not to sacrifice performance because of this division, this scheme's composition and transformation mechanisms will allow communication and computation to be (automatically) combined in an optimized fashion so that high performance and high scalability are achieved. To facilitate adoption by practicing programmers of the paradigms and tools that are developed, integration with education is essential. Accordingly, this project will directly train undergraduate, graduate, and post-doctoral researchers and will develop supporting curricula and materials to train both students and practicing programmers. Close collaboration with large-scale real-world scientific applications will further increase the practical relevance of this work.

The International Conference for Supercomputing (ICS) brings together experts from diverse fields, including parallel application writers, libraries and tools developers, compiler developers, computer architects, and programming languages experts. The conference solicits papers on all aspects of research, development, and application of large-scale, high-performance experimental and commercial systems. In 2011 the conference will be held May 31 - June 4, 2011 in Tucson, Arizona.
It is proposed to offer up to 10 NSF-sponsored student travel and junior faculty (without travel support) grants for a total budget of $10,000. Applications will be solicited via email mailing lists, personal contacts, and the conference web site. The selection process will consider the applicant?s level of participation in ICS, followed by how closely the student?s research interests match areas covered by ICS.