Laxmikant V. Kale - US grants

This research seeks the efficient parallel execution of Logic Programs via the REDUCE OR process model. The model is aimed at exploiting large-scale parallel processors. By design, it is suitable for shared memory as well as message passing machines. It attempts to extract maximum parallelism from logic programs by dealing with AND and OR parallelism and handling their interaction effectively. An interpreter in C that runs on Intel Hypercube, Encore MultiMax, Sequent, ALLIANT and a simulation system has been developed. A binding scheme and runtime system were designed and implemented and key optimizations developed. The challenge is to control the overhead in the model so that it surpasses compiled sequential Prolog with a few processors, and to demonstrate that it is a useful way of programming large parallel machines. This will be achieved with an optimizing compiler, using static analysis, annotations, optimized algorithms and a streamlined runtime system. Identifying absence of "embedded" variables and determinacy in specific clauses will allow generation of code close to that produced by sequential compilers. Grain-size control will reduce the proportion of system overhead. Other issues involve generation of effective dependence graphs, and various control strategies.

This research investigates theoretical and practical issues in the design and evaluation of parallel algorithms, and involves cooperative work in theory and systems. The project ideally has four objectives. First, to develop a high level language for expressing parallel algorithms such that there is a natural correspondence between algorithmic concepts and programming language constructs and an algorithm can be expressed without forcing a serialization. Second, to study and develop techniques for mapping algorithms expressed in this high level notation to various architectures subject to simple user specified constraints. Third, to study instrumentation techniques for monitoring an algorithm's runtime behaviour on a given architecture. Fourth, to investigate issues related to giving high level visual feedback to the user on the performance of implementation of his or her algorithm on a specific architecture. These will set up an interactive loop between the user and the system that will enable rapid design and prototyping of parallel algorithms.

All common approaches to parallelizing compilers, high-level languages such as functional languages, and explicitly parallel languages - require a common base of support. This work will encapsulate this support in a language that abstracts over resource management decisions and machine details, and develops a runtime support system on different classes of MIMD machines for implementing this language. The language can then be used by implementors of other high level approaches to parallel programming as a universal and efficient back-end. It can also be used for efficient application programming. The language and the runtime system will support dynamic load balancing, and small to medium computational grainsize, to meet the above objectives. For expressiveness as well as efficiency, the language will support a rich set of primitives for expressing specific forms of information sharing. The runtime support system for the language has been implemented already on distributed memory machines such as iPSC/2, and shared memory machines such as Sequent Symmetry, and a preliminary compiler has been written. Performance results on these machines have been obtained on simple benchmarks and are very encouraging: they show that we can obtain excellent speedups with many processors, while costing only a few percent overhead over the best sequential C programs, on one processor.

9318159 Schulten Project Summary High performance computers, in particular massively parallel computers, and the emergent, high-capacity research network will be employed to advance modelling and structure determination calculations in molecular biology and pharmacology. To this end, seven investigators with expertise in computer science, applied mathematics, molecular biology, pharmacology, chemistry, and physics will combine their efforts towards four goals: (i) to develop prototype molecular dynamics algorithms for very large, very long, and very accurate applications as well as to enhance the efficiency of such algorithms; (ii) to transfer the above algorithms to a widely used molecular dynamics program for structural biology (X-PLOR) and to develop, within the framework of this program, efficient algorithms for computational crystallography and solution NMR spectroscopy; (iii) to use the computational test beds of NSF centers and to apply the programs developed to grand challenge problems in molecular biology and pharmacology, initially for structure determination and interactive molecular dynamics of membrane-protein-water systems, of membrane transport of drugs, of DNA-protein-water systems and, later, for large supramolecular systems like the coat of poliovirus or actin- myosin strands in muscle fiber; (iv) to develop a graphic user interface which allows convenient interactive molecular modelling between local graphics workstations and remote massively parallel computers at NSF centers, to pioneer the routine use of teleconference communication between the investigators through use of the National Research Network in its various stages of completion, and to institute a "teleacademy for computational biology" as a regular seminar on the video conference facilities of the NSF centers and other qualified sites.

EIA-0081307
Torrellas, Josep
University of Illinois

ITR: Intelligent Memory Architectures and Algorithms to Crack the Protein Folding Problem

This project is a multidisciplinary effort to design fundamentally improved algorithms, hardware, and software to solve the protein folding problem. The project, which teams experts in hardware, software, and computational biology, promises advances in applications of protein folding such as drug design and understanding of diseases. In addition, the project will investigate new hardware and software based on advancing IC technology. The architecture under examination will use increased integration of processors and memory in a single chip, and software will take advantage of the proximity of memory and processing. This work is tightly coupled to the IBM Blue Gene effort, but will investigate complementary issues. In particular, simulation-based studies will investigate the use of next-generation intelligent architectures.

Roberto Car and Annabella Selloni of Princeton University are supported under the Information Technology Research Program (ITR) by the Division of Chemistry, the Division of Materials Research, and the Division of Advanced Computational Infrastructure and Research to make ab initio molecular dynamics simulations more effective and more accessible on high performance computing platforms. Co-PI's include Josep Torrellas and Laxmikant Kale of University of Illinois, Michael Klein of the University of Pennsylvania, Mark Tuckerman of New York University, Glenn Martyna of Indiana University, and Nicholas Nystrom of Carnegie Mellon University (via collaborative proposals CHE-0121357, CHE-0121302, CHE-0121375, CHE-0121367, and CHE-0121273, respectively). This team of computational chemists and computer scientists will develop new efficient and high accuracy methods, extensible open source software modules with desirable scaling properties, and novel hardware designs that will enable modeling of complex events and environments of interest to chemistry, materials science and engineering, geoscience, and biology.

Information technology (IT) has transformed computational science to the extent that realistic, atom-based simulations of key processes in chemistry, nanoscience and engineering, and biology can now be addressed using highly accurate simulations. This research can potentially impact the design of polymer-generating catalysts, nanoscale electronic devices, and artificial biomimetic catalysts.

EIA-0103645
Laxmikant V. Kale
University of Illinois

Performance Modeling and Programming Environments for PetaFlop Computers and the Blue Gene Machine

The objective of the proposal is to develop performance simulation capabilities to allow system level analysis and prediction of performance of the next generation complex PetaFlop machines that include multiple levels of memory hierarchy and interconnects. The performance simulator that will be developed will be used to test parallel data structures and algorithms implemented in programming environments used in these machines, as well as frameworks to enable the development of applications for these machine classes. A number of important applications will be used to test and validate the CS technology advances.

EIA- 0224453
Adve, Sarita V.
Hwu, Wen-mei;
Kale, Laxmicant V.;
Padua, David A.;
Patel, Sanjay J.
University of Illinois - Urbana/Champaign

CISE RR: Programming Environments and Applications for Clusters and Grids

This proposal, building a cluster platform connected by gigabit Ethernet, enables the "grid" to be used in the following four research projects:

Advanced Programming Environments for Cluster and Grids,
Parallel Applications for Clusters and Grids,
Dynamic Sequential Code Optimization, and

Architectures for Multimedia and Communications Applications.

The configuration permits experimentation on diverse subsystems with varying degrees of heterogeneity, up to three levels of parallelism, and a range of system sizes. The facility will be used in three ways: as an experimental test-bed for systems research on clusters and grids; as a prototype for the development of parallel and distributed applications for clusters and grids; and as a cost-effective production compute server for research in architecture, compilers, and machine learning. The shared facility addresses problems critical to computational infrastructure spanning architecture, compiler, and runtime research on systems ranging from single nodes to grids, covering various application domains.

This project is advancing the state of art in both computational cosmology and parallel computing simultaneously and synergetically. Breakthroughs in cosmology, which improve our understanding of the formation of galaxies and planets, are enabled by advances in parallel computing being made in this project. Parallel machines with over hundred thousand powerful processors are now being built. NSF's widely accessible TeraScale facilities have already deployed a 3,000 processor machine in 2001. At the same time algorithmic advances have made it possible to solve problems at a much faster rate. Yet the complexity of algorithms combined with the difficulty of parallelizing them on such large machines remains a hindrance to advances in Science and Engineering. This project explores an object based methodology that is simplifying the process of developing highly efficient parallel applications. This approach allows users to write applications at the level of natural entities in the application domain, without explicit regard to which processors will house such entities and
carry out associated computations. To make this possible, the "runtime system" must be able to make fine-grained resource allocation decisions automatically. Advances in parallel computing are being sought to that end. Specifically, application developers may specify a program in terms of a collection of millions of objects that communicate with each other in several stylized patterns. In addition, parallel components can be plugged in and out of running computations, and exchange data with each other in a exible manner. Based on this infrastructure, this project is building a framework that makes it easy to build "particle-oriented" parallel programs. In addition to computational cosmology, which predomi-nately involves simulations that represent galaxies, dark matter, stars, planetary bodies and gas as particles, such programs are used in other fields as well. The framework contains highly efficient parallel algorithms that operate on collections of billions of particles, spread across machines with tens of thousands of processors. These advances are being used to carry out scientific studies in cosmology. Large, detailed simulations of structure formation powered by parallel computers are necessary to make quantitative predictions from cosmological theories. By calculating the non-linear gravitational and gas dynamics of the formation of galaxies and clusters of galaxies, we are creating galaxy catalogues, X-ray maps, and other observables that can be compared directly with new satellite and ground-based data, and thereby constrain the parameters of cosmological theories. These parameters include the amount and nature of the dark matter, the existence and equation of state of any dark energy, the total amount of baryons, and the nature of the initial uctuations in the Universe. Similar simulation studies are being used to study how planets form from a proto-solar disk in order to create an ab initio theory of planet formation. The software developed via this project is being made available to a wide community of researchers. Also, the research results of simulations can be downloaded or visualized via the web.

computer program /software; technology /technique development

Parallel machines of high capability are being designed and built to run Software for scientific and engineering modeling. This project is conducting research to create a simulation environment that allows applications to be developed, tested and tuned via simulation of the future machine, while allowing machine designers to tune their architectural choices to benefit a specific collection
of applications. It aims at simulating petascale machines with over a million processor cores. The project builds upon previous research on migratable objects, and a preliminary simulation system developed in earlier research. The software developed in this project is being distributed via the Internet, and consists of an emulator and a simulator. The emulator allows application developers to develop and test their application in a realistic petascale environment and generate traces for the simulator. The simulator uses the traces, along with a model of the architecture, to generate detailed performance data that can be used to tune the applications and to analyze the architectural choices under realistic application loads.

Software for Scientific and Engineering modeling can make a significant impact on society through better understanding of physical phenomenon and improved design of engineered artifacts. The results of this project, including the simulation software, will lead to effective use of the petascale computing facilities being developed and deployed nationally, for such software. It will reduce delays in software tuning. The project will also help train a new generation in techniques for effectively harnessing large parallel machines to society's goals.

Scientific applications can model interactions of medicines with proteins, predict the behavior of nano-materials, model the climate, and lead to better understanding of physical phenomenon. These applications demand ever greater computational resources, which can only be supplied by new parallel computers with ever increasing capability and complexity. Parallel computing can bring about new breakthroughs only if the complexity of efficient parallel programming can be overcome. Yet developing parallel applications remains significantly more difficult than serial development. Petascale machines with hundreds of thousands(and possibly millions) of processors add to the complexity, as do new sophisticated algorithms and multi-physics applications.


This project is developing a new approach to parallel programming which builds upon the automatic resource management and composibility of the Charm++ framework. This approach includes development of multiple, individually incomplete, programming models. Each model simplifies parallel programming while still covering significant categories of applications. This collection of interoperable models, supported by complete models including Adaptive MPI and Charm++, provides a powerful environment for developing future petascale applications. A compiler framework is being developed which provides a common representation and facilitates compatibility between models. In addition, the vision includes abstractions supported by libraries for commonly needed data types and functionalities. These abstractions will support and interoperate with domain specific frameworks. The results of this project will enable the large community of computational scientists and engineers to harness petascale machines with relative ease in order to generate breakthroughs in scientific discovery and engineering design.

Algorithms; Biology; Buckytubes; CRISP; Carbon Nanotubes; Chemistry; Code; Coding System; Computer Programs; Computer Retrieval of Information on Scientific Projects Database; Computer software; Computers; Funding; Grant; Institution; Investigators; Length; Method LOINC Axis 6; Methodology; NIH; Nanotubes, Carbon; National Institutes of Health; National Institutes of Health (U.S.); Peptides; Performance; Process; Research; Research Design; Research Personnel; Research Resources; Researchers; Resources; Science; Science of Chemistry; Software; Source; Study Type; System; System, LOINC Axis 4; Testing; Time; United States National Institutes of Health; base; computer program/software; interest; mimetics; nano materials; nano tubes, Carbon; nanomaterials; parallel architecture (computer); phase change; simulation; study design; tool

This proposal is for a provisional allocation of time on the Blue Waters computer system, due to become operational in 2011, and for travel funds to support technical coordination by various collaborators with the Blue Waters project team and vendor technical team.

The project involves molecular dynamics simulations of three cellular systems and processes: viral infection, morphogenesis of intra-cellular membranes, and the photosynthetic chromatophore. The actions of these biological processes unfold in time and it is difficult to follow such evolution with crystallography. Molecular dynamics simulations will provide insights into the evolution of these processes.

Planned work with the poliovirus involves the use of numerical simulation to study the changes at the atomic level that are responsible for the process by which a poliovirus enters a cell. It is thought that this will be representative of this process for a class of viruses, the non-enveloped RNA viruses, that include the agents of diseases such as hepatitis A, the common cold, and viral meningitis. The planned studies of how proteins shape intracellular membranes will provide insights into an important aspect of organelle and vesicle formation. The work on photosynthesis involves studies of the chromatophore in purple bacteria, a system involving over 200 proteins and a step along the route of being able to model an organelle. This will allow researchers to determine the statistically preferred routes for quinones as they couple distant proteins, and how the light-generated electrical potential spreads as it drives ATP synthesis and cellular transport.

The molecular simulation codes used in this work will be made widely available, providing tools for other researchers in the chemistry, biochemistry and materials research communities. There will be substantial involvement of post-doctoral researchers and graduate students in the projects for which the allocation is requested. The results of the work should be of use in medicine and bio-engineering.

The Cold Dark Matter (CDM) paradigm for the formation of structure in the universe has had many successes, from predicting the spectrum of fluctuations in the Cosmic Microwave Background to explaining the clustering of galaxies. But CDM theory is still at odds with the observed properties of galaxies on scales where the baryonic physics of gas cooling, star formation and feedback are important. Modeling these processes in the cosmological context is extremely difficult owing to the immense dynamic range and resolution needed, and requires the most advanced computational hardware available as well as new computing techniques and algorithms. The proposing team has developed smooth-particle hydrodynamics (SPH) codes addressing these processes at the galaxy scale, and plans to adapt their algorithms to new architectures in order extend them to cosmological volumes. In addition to moving their star formation and feedback algorithms from legacy message-passing interface (MPI) codes to a parallel language (CHARM++), they intend to implement faster algorithms that can achieve the needed dynamic range and take full advantage of the hundreds of thousands of processing cores on the Blue Waters system. The results will be processed by a parallel pipeline that creates simulated observations. The simulations will also be used in a program targeting science pre-majors from under-represented groups, introducing them to the use of computer simulations in astrophysics and encouraging them toward technically oriented majors.

Computer simulation plays a central role in helping us understand, predict, and engineer the physical and chemical properties of technological materials systems such as semiconductor devices, photovoltaic systems, chemical reactions and catalytic behavior. Despite significant progress in performing realistic simulations in full microscopic detail, some problems are currently out of reach: two examples are the modeling of electronic devices with multiple functional parts based on new materials such as novel low power computer switches that would revolutionize the Information Technology industry, and the photovoltaic activity of complex interfaces between polymers and inorganic nanostructures that would enhance US energy self-reliance. The research program of this collaborative software institute aims to create an open and effective scientific software package that can make efficient use of cutting-edge high performance computers (HPC) to solve challenging problems involving the physics and chemistry of materials. By having such software available, this software initiative will have multiple broad impacts. First, the community of materials scientists will be able to study next-generation problems in materials physics and chemistry, and computer science advances that enable the software will be demonstrated and made accessible for both communities which will help cross-fertilize further such collaborative efforts. Second, the capability of simulating and engineering more complex materials systems and technological devices could play a role in helping the US continue is competitive edge in science, technology, and education. Third, through training of young scientists, direct outreach to the broader scientific community through workshops and conferences, and educational programs ranging from secondary to graduate levels, the power, importance, and capabilities of computational modeling, materials science, and computer science methodologies that enable the science will be communicated to a broad audience. Finally, by enabling the refinement of existing materials systems as well as discovery of new materials systems, the resulting scientific advances can help broadly impact society via technological improvements: in terms of the two examples provided above, (a) the successful design of new electronic device paradigms helps significantly advance the digital revolution by permitting the introduction of smaller, more efficient, and more capable electronic circuits and information processing systems, and (b) successful creation of inexpensive, easy-to-fabricate, and durable photovoltaic materials and devices can lead to cleaner forms of energy production while reducing reliance on fossil fuels.

The technical goal is to greatly enhance the open software tool OPENATOM to advance discovery in nanoscience and technology. OPENATOM will be delivered as a open, robust and validated software package capable of utilizing HPC architectures efficiently to describe the electronic structure of complex materials systems from first principles. In terms of describing electronic ground-states, OPENATOM will be enhanced by features such as improved configurational sampling methods, hybrid density functionals, and incorporation of fast super-soft pseudopotential techniques. In addition, the team will incorporate the many-body GW-BSE approach for electronic excitations that permits accurate computation of electronic energy levels, optical absorption and emission, and luminescence. Ultimately, such an extensible software framework will permit accurate electronic structure computations to employ effectively future HPC platforms with 10,000,000 cores.

Many scientific and visualization methods involve organizing the data they are processing into a hierarchy (also known as a "tree"). These applications and methods include: astronomical simulations of particles moving under the influence of gravity, analysis of spatial data (that is, data that describes objects with respect to their relative position in space), photorealistic rendering of virtual environments,reconstruction of surfaces from laser scans, collision detection when simulating the movement of physical objects, and many others. Tree data structures, and the algorithms used to work on these structures, are heavily used in these applications because they help to make these applications run much faster on supercomputers. However, implementing tree-based algorithms can require a significant effort, particularly on modern highly parallel computers. This project will create ParaTreet, a software toolkit for parallel trees, that will enable rapid development of such applications. Details of the parallel aspects will be hidden from the programmer, who will be able to quickly evaluate the relative merits of different trees and algorithms even when applied to large datasets and very computation-intensive applications. The combination of such an abstract and extensible framework with a portable adaptive runtime system will allow scientists to effectively use parallel hardware ranging from small clusters to petascale-class machines, for a wide variety of tree-based applications. This project will demonstrate the feasibility of such an approach as well as generate evidence of community adoption of this technology. If successful, this project will enable NSF-supported researchers to solve science problems faster as well as to tackle more complex problems, thus serving NSF's science mission.


This project builds upon an existing collaboration on Computational Astronomy and the resultant software base in the ChaNGa (Charm N-body GrAvity solver) code. ChaNGa is a software package that performs collisionless N-body simulations, and can perform cosmological simulations with periodic boundary conditions in co-moving coordinates or simulations of isolated stellar systems. This project will extend ChaNGa with a parallel tree toolkit called ParaTreet and associated applications, that will allow scientists to effectively utilize small clusters as well as very large supercomputers for parallel tree-based calculations. The key data structure in ParaTreet is an asynchronous software-based tree data cache, which maintains a writeback local copy of remote tree data. We plan to support a variety of spatial decomposition methods and the associated trees, including Oct-trees, KD-trees, inside-outside trees, ball trees, R-trees, and their combinations. Different trees are useful in different application circumstances, and the software will allow their relative merits to be evaluated with relative ease. The framework will support a variety of parallel work decomposition methods, including those based on space filling curves, and support dynamic rearrangement of parallel work at runtime. The algorithms supported will range from Barnes-Hut with various multipole expansions, data clustering, collision detection, surface reconstruction, ray intersection, etc. The software includes a collection of dynamic load balancing strategies in the Charm++ framework that can be tuned for specific problem structures. It also includes support for clusters of accelerators, such as GPGPUs. This project will demonstrate the feasibility of such an approach as well as generate evidence of community adoption of this technology.

Spatial astronomical data is often extremely large and it is highly non-uniformly distributed. Algorithms that deal with such data have to be parallelized over large distributed memory supercomputers to deal with its size. The non-uniformity in the spatial distribution can be extreme, with some regions of space having million times more particles than other similar size regions. This creates significant challenges for scalable and efficient performance, as well as for the productive programming of such algorithms. Yet, the field of computational astronomy increasingly needs such scalable algorithms in the coming era. The raw computing capability unleashed by modern PetaFLOP/s and ExaFLOP/s computers, respectively, executing up to quadrillions and quintillions of calculations per second, is making it potentially feasible to get answers via simulations to some fundamental questions in the field, including those of galaxy formation and the properties of dark matter and dark energy. As the Large Synoptic Survey Telescope maps out the entire visible sky every few nights, it is expected to generate more than 10 terabytes per day, and this data needs to be analyzed in a timely fashion to fulfill its scientific goals of discovering hazardous asteroids, new minor planets, and exploding stars. This project provides new techniques and tools for researchers to use for high-performance simulations of non-uniform data. This enables previously untenable computer simulations to be done by astrophysicists, unlocking new insights and answering questions about the nature of the cosmos. The results are also used as case studies and educational material in classes taught by the investigators. Additionally, the project aim to involve women and undergraduate students in performing this research, continuing their experience of having done so in the past. This project thus aligns with the NSF's mission: to promote the progress of science and to advance the national health, prosperity and welfare.

This project aims at developing novel parallel algorithms, data structures, and application demonstrations for computational problems involving data organized into hierarchical trees. A canonical example of such a domain is astronomical data, where particles representing clustered mass (stars or galaxies) are spread over the space of a simulation box or survey field in a highly non-uniform manner. Organizing them into trees, with multiple alternative tree organizations possible, including k-d trees, octrees, space-filling-curve based trees, etc., allows the efficient computation of various quantities such as gravitational forces, densities (and therefore hydrodynamics), two-point or three-point correlations, etc. The optimum choice of tree structure and algorithm depends both on the problem and the parameters of the parallel machine. The research methods used will include complexity analysis and, more significantly, empirical comparisons over a range of possible application scenarios including particle distributions and classes of traversals and algorithms. This will include formulation of algorithms and their implementations on parallel machines. The main outcomes of this project will be research papers describing effective algorithms and comparison and evaluation of particle decomposition techniques and tree types. This project is funded by the Office of Advanced Cyberinfrastructure in the Directorate for Computer and Information Science and Engineering and the Division of Astronomical Sciences in the Directorate for Mathematical & Physical Sciences.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.