Andrew Lumsdaine - US grants

This project will explore theoretical and practical aspects of newly-developed waveform conjugate-direction methods for parallel solution of initial value problems (IVPs). Waveform relaxation (WR), a waveform-based iterative technique, is an increasingly popular parallel solution approach for IVPs. Conjugate-direction waveform methods have dramatically improved the convergence properties of WR for transient simulation of MOS devices. The project will establish the basis for broader application of these methods by developing refined convergence estimates and by building and testing a parallel implementation. New convergence results will be sought for conjugate-direction waveform methods applied to linear and nonlinear systems of ODEs and DAEs. The effects of discretization and multirate integration will also be studied. Pointwise and waveform-based IVP solvers will be implemented on ASIM, the Alewife simulator, and on the Alewife parallel computer. Their behavior for a variety of ODE and DAE problems on various hardware configuration will be compared. Waveform conjugate-direction methods appear to be an efficient and practical class of parallel techniques for a variety of applications. Together, the theoretical results and practical implementations will demonstrate their value and applicability.

The primary emphasis of this Career Development Plan is the coordinated development of research and education programs in high-performance computing for computational science and engineering. Research Plan: The main goals of high-performance computing are high-performance, scalability, and portability. To attain these objectives for modern scientific and engineering applications, new hardware paradigms, new software methodologies, and new numerical algorithms are needed. Moreover, the interdependencies between hardware, software, algorithm, and application have an essential bearing on performance, scalability, and portability and must also be well understood. This work is an inclusive effort to create a substantial, unified base of understanding about high-performance computing for scientific and engineering applications that can be broadly applied. The specific objectives of this work are to: (1) Develop and analyze high-performance, portable, computational kernels and numerical libraries that are capable of exploiting modern computing architectures and operating systems, such as symmetric multiprocessors, operating systems, and gigabit networks; (2) Develop and analyze prototype object-based and object-oriented scalable software libraries for high-performance computing and for computational scientific and engineering applications; (3) Develop and analyze new algorithms for maximizing the scalability of stationary and time-dependent problems; (4) Apply the new algorithms and software libraries to real, substantial, computational science and engineering applications. Education Plan: Because of the increasing importance of computational science and engineering, it is important that computer scientists (and indeed, scientists and engineers in general) understand the intricacies and inter-relationships inherent to high-performance computing. A graduate course in numerical computing has already been developed and incorporated into the graduate core curriculum in the Computer Science and Engineering program at the University of Notre Dame. Building on this course, new graduate-level courses in high-performance computing will continue to be introduced. At the undergraduate level, a senior elective in high-performance computing is being introduced, and there will be continued effort to support and direct undergraduate research.

9422380 Lumsdaine Distributed-memory computers have been available for about a decade. Still, hard questions remain concerning the scalability of implicit numerical methods, and new, alternative numerical methods, in order to gauge the value of further, large-scale investment in parallelization of key applications. Furthermore, algorithms, even if developed to be suitably scalable for certain applications, must be represented in software cost-effectively in order to make the massively parallel systems economical overall. Therefore, we seek to answer fundamental questions about algorithms and software technology related to implicit numerical integration methods, and more generally, about trade-offs between concurrency and convergence of iterative methods.

This project will advance the state of the art of high performance computing by the refinement and application of software component technologies. The project will use these technologies to build a high-performance library of generic components with the performance and flexibility required for complex scientific applications.

Three technical thrusts will support this approach. The researchers will develop and extend generic programming analysis and design methodologies to create component taxonomies for scientific computing, particularly for denoting higher-level domain abstractions and formally specifying their interfaces. Generative optimization will exploit these abstractions to automate performance tuning and optimization, thus avoiding the traditional loss of computational efficiency from high-level abstractions. Finally, library development will create highly parameterized components that offer maximum functionality and customizability for areas such as numerical linear algebra, multi-dimensional arrays, tensor operations, and stencil operations. Through the use of generative techniques, the library will be highly optimizable and will offer high performance at a reasonable development cost. Through the use of generic programming techniques, the library will incorporate parallel processing capabilities.

EIA-0131354
Andrew Lumsdaine
University of Notre Dame

Next Generation Software: Open Compilation for Self-Optimizing Generic Components

This proposal is to advance the state-of-the-art in high-performance software specifically related tot he design and compilation of high-performance scientific libraries. This work will address two of the most important issues-code complexity and performance optimization-by applying and extending two emerging programming paradigm: generic programming and concept-based optimization. The vehicle for this work will be development of an integrated framework consisting of open compilation and generic library technologies. By simultaneously developing the compilation technologies and the library technologies-and by providing mechanism to couple the two together-the whole will be greater than the sum of its parts

0202048
Wise, David S.
Indiana University - Bloomington

RI: A Research Infrastructure for Collaborative, High-Performance Grid Applications

This project, developing an experimental infrastructure for distributed high performance computing, supports ten research projects extending the location-transparency that the Grid provides for computation resources to the full spectrum of activities which end-users require. Services being explored include software development, parallel code middleware, distributed software components for scientific computing, security for parallel remote method invocation,
managing large-scale data streams, and collaboration methodologies. The research builds on and extends the institutions collaborations with several national Grid research teams. In contrast to existing national and university infrastructure available through production machines, this research requires an environment tolerant of experimental network protocols, temporary middleware, and other system-level changes. The infrastructure will contribute to the following research projects:
a. Opie: basic work on parallel matrix algorithms that achieve high efficiency across many architectural platforms
b. LAM: middleware MPI implementations supporting hierarchical and fault-tolerant parallel computing
c. dQUOB: application of SQL queries to live data streams
d. RMI Security: basic research into security mechanisms for remote method invocation, allowing security to be traded off with efficiency
e. HPJ: High Performance Java creating a language platform for portable high performance coding
f. Grid Broker: reliable, robust publish/subscribe service for introducing fault tolerance into the distributed Grid environment
g. Community Grids Collaboratory: advanced collaboration capabilities with applications to both distance education and distributed communities
h. Xports: design of methodologies for remote instrument access and data management of the resulting extremely large data sets
i. Software Components: distributed software component model designed for applications that use parallel computing "nodes" in wide-area Grid environments
j. Science Portals: set of tools that allow programmers to build Grid distributed applications accessed and controlled from desktop environments and web browsers
Major improvements to infrastructure supporting all these projects include a 16-node cycle server and a large-scale file server as well as network upgrades to and within the building.

We propose a novel marriage of new fundamentals of data structures and algorithms with the productive tools of generic programming. Together they promise tools that could make high performance computing available to any scientist. The data structure is the Morton-order representation of matrices (and arrays in general), which admits both row, column, and quadrant decompositions. Its benefits are grounded in architecture where it solves problems of locality at all levels of a memory hierarchy. The favored algorithms use divide- and-conquer recursion-a style associated with functional programming-because they address the problems of balanced scheduling and communication of distributed and multiprocessing. Generic programming contributes, also, to this higher-level algebraic view of program construction. The anticipated result is a style for parallel programming without requiring explicit choreography either of memory or of processors. That is, the programmer can specify computations, and eventually new algorithms, with a high-level language closer to mathematics. We propose to develop the tools and the techniques to carry these programs to an efficient parallel implementation.

Products will include a new programming style, new efficiencies for parallel and Grid computing, tools to carry old codes into this environment, tools to support the new generation of programs, support for teaching a new generation of programmers, and new algorithms that can only be inspired by this high-level perspective on programming.

based architecture to create layered approach to enabling scalable fault tolerance. The This project will focus on the middleware layer used to provide message passing capabilities for distributed memory applications. The system will use a component-design and implementation of the message passing system will provide sufficient flexibility to accommodate a wide variety of application state management and recovery mechanisms.

The proposed message passing system will have the following capabilities.
o Failure detection;
o Fault tolerance of the run-time system;
o Fault tolerance of the message passing layer (MPI);
o Meaningful semantics for the message passing layer in the presence of faults;
o Flexible application interface for fault notification; and
o Support for application state management and recovery.

This work will be realized as part of the component framework of LAM/MPI, an existing high-quality implementation of the Message Passing Interface standard.

This project will have broader impacts in several areas. Availability of a scalable and reliable middleware layer will enable new levels of application scalability. In addition, new capabilities for MPI jobs can be realized, including process migration, non-stop behavior, and gang scheduling. Since the proposed middleware will be realized in the context of MPI, applications written with MPI can immediately benefit from this work.
And, since the work will be integrated into a production-quality implementation of MPI, the results can actually be used by a widespread audience. The modular component-based design of our implementation will allow the middleware to be used by a wide variety of state management and application-specific fault tolerance schemes. Finally, important contributions from this work are in the form of interface designs-other implementations of MPI will also be able to adopt these approaches to provide reliability

Background

A typical compiler is designed to apply its optimizations to built-in types of the language it is compiling. Although built-in general-purpose optimizations might be generally beneficial, they cannot be directly applied to user-defined types because their correctness cannot be determined a priori. Extending a compiler to optimize some particular userdefined type would be useful for that particular type, but this approach becomes burdensome if the compiler must be extended on a type-by-type basis. A more powerful approach would be to enable compiler optimizations that are generic, i.e., that can be applied to any type (built-in or user-defined) that meets fundamental semantic requirements.

Intellectual Merit

-Formal concept definitions. The PIs propose to integrate concept-based optimization with their research on formalization of concepts for generic programming.
-Language support for concepts. Concept-based optimization will leverage and inform our on-going research on direct language support for concepts and generic programming.
-Compiler support for concepts. The PI's initial efforts incorporating concepts into the GNU C++ compiler will be extended to support concept-based optimizations.
- Concept-based optimizations. The PI's will leverage generic programming mechanisms to define optimizations using concepts so that such optimizations apply to user-defined types, simply by stating that the types model (i.e., meetthe requirements of) particular concepts.
-Deployment and library evolution. Selected generic libraries, including the Standard Template Library, the
Boost Graph Library, and the Vector, Signal, and Image Processing Library will be upgraded to take advantage of language extensions for generic programming and to take advantage of concept-based optimization.
-Evaluation suite. The PIs will collect optimizations for a suite of high-level benchmarks that can be used to evaluate concept-based optimizations. An important benchmark in this regard will be to demonstrate that generic optimizations offer the same performance benefits when applied to built-in types as do traditional type-specific optimizations.

Broader Impact
The proposed research will have:
- Direct impact on the future development of mainstream programming languages that support generic programming (e.g., C++, C#, and Java), and on their standard libraries.
-Support for generic programming in these languages that will provide valuable high-level information about user-defined types,making high-level and concept-based optimization more widely applicable.

This project will directly train graduate students and post-doctoral researchers in the emerging field of generic programming. Results from our research will be integrated into graduate programming coursesand into textbooks.

Software developers rely on high-quality software libraries to mitigate the cost of building complex applications. However, many software libraries provide complex interfaces to make the library adaptable to application-specific needs. This complexity raises the cost of adoption and reduces the benefits of software reuse. Researchers discovered that libraries can be made more versatile and easier to use if the underlying programming language provides library authors with constructs for reasoning, during the compilation of the application, about program metadata and for customizing the library implementation based on this information. Current programming languages provide these features in an immature form and the state of the art in programming language theory does not yet reach this combination of features. The investigators are advancing the theory to bring type safety and modularity to this context and they are working closely with the C++ Standards Committee to transfer their results to industrial practice.

The combination of language features needed to reason about metadata and customize libraries is called reflective metaprogramming. Previous research in this area provides type safety and modularity for metaprogramming but not reflective metaprogramming. The investigators are researching type safety for reflective metaprogramming through a careful integration of 1) a meta-language that provides computation over values and types and that provides reflection over all the program's metadata, 2) a facility for classifying types, and 3) a type system that provides hooks into the meta-language using dependent types. By developing a more reliable and expressive metaprogramming system, this research improves programmer productivity for both the developers and users of software libraries because many more bugs will be caught early in the development cycle by the modular type system.

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.

A central task in understanding how neurons collectively process information is to map how neurons influence each other in local cortical networks. As defined here, local cortical networks will consist of tens to hundreds of neurons. Influence will be defined as how well knowledge of activity in one neuron will allow the activity in another neuron to be predicted. Three methods for measuring influence between neurons will be explored. To assess these methods, they will be used on data from simple, and then realistic, models of cortical networks where the underlying connectivity structure is known. After refinement, the methods will be applied to recordings from hundreds of cortical neurons in small slice cultures of brain tissue. Over 100 cortical neurons at a time will be recorded through the use of an advanced, 512 electrode array. In addition, measures of influence will be applied to data taken from 16 wire electrodes placed in behaving rats. These in vivo recordings will serve as a first step toward linking influence maps in cortical networks to behavior. This research is expected to provide new knowledge that could aid the design of brain-like computing devices. In addition, it could ultimately be used as a tool to identify differences in influence patterns between healthy and pathological brains.

The three methods for measuring influence will include directed information, transfer entropy, and Granger causality. Special care will be taken to identify situations where these measurements may produce false positive connections. These include cases where two neurons are driven by a common source at different delays, and cases where one neuron influences another neuron indirectly through an intercalated neuron. Such false positive connections will be identified and corrected, to the extent possible, by comparing raw pairwise measures of influence with conditional measures of influence. Simulations will also provide an estimate of how often neurons outside the recorded population can contribute to false positive connections. These estimates will be used to place confidence limits on the influence maps extracted from actual data. In neurons where influences converge, synergistic interactions between influences will be measured. The map of influence will serve to identify locations within the network where synergistic transformations of information, or computations, occur.

The most powerful computing systems in the world have historically been dedicated to solving scientific problems. Until recently, the computations performed by these systems have typically been simulations of various physical phenomena. However, a new paradigm for scientific discovery has been steadily rising in importance, namely, data-intensive science, which focuses sophisticated analysis techniques on the enormous (and ever increasing) amounts of data being produced in scientific, commercial, and social endeavors. Important research based on data-intensive science include areas as diverse as knowledge discovery, bioinformatics, proteomics and genomics, data mining and search, electronic design automation, computer vision, and Internet routing. Unfortunately, the computational approaches needed for data-intensive science differ markedly from those that have been so effective for simulation-based supercomputing. To enable and facilitate efficient execution of data-intensive scientific problems, this project will develop a comprehensive hardware and software supercomputing system for data-intensive science.

Graph algorithms and data structures are fundamental to data-intensive computations and, consequently, this project is focused on providing fundamental, new understandings of the basics of large-scale graph processing and how to build scalable systems to efficiently solve large-scale graph problems. In particular, this work will characterize processing overheads and the limits of graph processing scalability, develop performance models that properly capture graph algorithms, define the (co-design) process for developing graph-specific hardware, and experimentally verify our approach with a prototype execution environment. Key capabilities of our system include: a novel fine-grained parallel programming model, a scalable library of graph algorithms and data structures, a graph-optimized core architecture, and a scalable graph execution platform. The project will also address the programming challenges involved in constructing scalable and reliable software for data-intensive problems.

The field of supercomputing is experiencing a rapid change in system structure, programming models, and software environments in response to advances in application requirements and in underlying enabling technologies. Traditional parallel programming approaches have relied on static resource allocation and task scheduling through programming interfaces such as MPI and OpenMP. These methods are reaching their efficiency and scalability limits on the new emerging classes of systems, spurring the creation of innovative dynamic strategies and software tools, including advanced runtime system software and programming interfaces that use them. To accelerate adoption of these next-generation methods, a unique environment is being created and operated that provides a comprehensive ensemble of state-of-the-art runtime system software and programming interfaces. Taken from previous research and development projects, some at the host institution, Indiana University, and others from premiere research organizations across the nation, these execution systems are integrated in a single supported Reconfigurable Execution Framework Testbed (REFT) and made available to parallel application algorithm developers as well as researchers in advanced tools for parallel computing. The basic REFT hardware capabilities include a medium- scale heterogeneous Linux cluster with multi-core sockets, high-bandwidth interconnect, and mass storage; field-programmable gate arrays; and instrumentation for power measurement. ParalleX-based HPX-3, ETI SWARM, Berkeley GasNet, Rice University?s Habanero, Illinois? Charm++, Cray Chapel, IBM X-10, and UPC among other programming and execution models comprise the major components of this unique facility.

Supercomputing is making a sharp corner turn in form, function, and methodologies. Unfortunately, few in the field are skilled in the use of the emerging execution and programming models that are becoming increasingly critical to effectively utilizing supercomputers to deliver quality science for extreme-scale applications?either those at the highest end of the performance spectrum (Petaflops currently and Exaflops at the end of the decade) or strong-scaled fixed-size problems. REFT serves the NSF computational science community by dramatically lowering the barrier to training, experimentation, and adoption of new dynamic execution methods and systems. It provides full documentation, on-line tutorials, in-house classes, and workshops for skill development and community building for the broad US HPC community to accelerate application, evaluation, and exploitation. As a repository for competing and complementary software environments it provides a single site for conducting comparative studies by end-users to establish best practices. As an NSF resource, it serves to expedite and further goals of computational science by enabling effective application of the next generation Petaflops-class computer systems of millions of cores and eventual Exascale systems with billion-way concurrency.

Advances in science and engineering are increasingly dependent on effective use of high performance computers for simulation of physical phenomena and analysis of experimentation data. Yet experts in the US in the development and application of supercomputing are relatively few; even as national demand and international competition increasingly stress the nation's capabilities in this area. Critical to satisfying the countryss needs in the field of high performance computing is the ready access to quality education to train future computational scientists, computer scientists, and design engineers as well as systems' administrators in the application, development, and management of the most powerful computers in the world. The field of HPC as a whole comprises many areas of specialization. But they all share the same common interrelated foundations. This project is developing a new college level course in High Performance Computing to serve as an entry-level introduction for all who wish to enter the field. The new syllabus presents the concepts, knowledge, and skills required by everyone who will be engaged in activities associated with high performance computing. In a closely synergistic manner, the separate topics related to parallel programming interfaces, supercomputer architecture, applications and parallel algorithms, and software environments and tools are combined in a mutually supportive presentation across about two-dozen lectures. Students become familiar with the material through hands-on programming examples and independent exercises for experience with methods and tools, as well as to be exposed to the sensitivity of system operational behavior to a range of alternative approaches and use-cases. Cultural aspects of the field are also shared including the extensive domain specific terminology, the rich history, and key leadership institutions and people. Students who have completed this intense first-year graduate (and advanced senior-level) college course will be capable of proceeding on to advanced areas of specialization, accepting entry-level positions in industry and national laboratories for which computation is of critical importance in fulfilling their mission, or in preparation to guide such courses in the future at home educational institutions.

This course will achieve the widest possible dissemination and impact by being recorded in high definition digital video and made available on-line and on-demand to all who wish to view the lectures. Organized as short segments of between 5 and 11 minutes each, the material is easily viewed and reviewed for best educational experience. Detailed slides to which the lectures are directed are edited into the video stream and made available separately for study. This use of MOOC-like technology will extend the reach of this discipline to many geographic regions and socio-economic groups that do not have ready access to world-class experts and educators in the field of high performance computing but who would greatly value to extend their educational opportunities in these directions. This course material will provide the foundation for a future Indiana University course giving transferable credit for having taken this course.

Graphs and graph algorithms are fundamental to computer science. Although historically they have not played a major role in traditional scientific computing, their importance is rapidly increasing with the emergence of informatics and data-centric applications. Although many graph analysis tasks are performed sequentially today, problem sizes continue to grow, necessitating the increasing use of parallel computing. Parallel graph algorithms are already being written, but with great effort and limited code reuse. A major issue in current ways of implementing parallel graph algorithms is the lack of performance portability: not only is it often required to reimplement algorithms on different platforms for the best performance, it is frequently also necessary to completely redesign them.

To avoid this rewriting and thus increase scientists' productivity, this project will study domain-specific programming languages allowing graph algorithms to be expressed portably, while using compilation techniques that allow the high-level expressions to achieve performance competitive with hand-written, low-level code for these algorithms. Domain-specific languages have already shown benefit in multiple application areas. This project will extend their benefits further in the graph domain, including to more platforms and data representations than in the past. In particular, the project goals include finding abstractions common to the expressions of graph applications on different platforms, as well as between different applications. To demonstrate the effectiveness of these abstractions, the project includes the creation of prototype implementations of graph algorithms for a variety of high-performance computing platforms and the evaluation of the high-level versions of algorithms against comparable low-level versions.

Modeling and simulating physical phenomena with computers is now an important tool for development and discovery in almost all fields of science and engineering. Joining theory and experimentation, computation is now recognized as the "third pillar" of scientific research. More recently, data analytics (the science of examining raw data with the purpose of drawing conclusions about that information) has emerged as an important computational tool for scientific discovery - a tool that is likely to be as important as, if not more important than, modeling and simulation. Within the broad domain of data analytics, the use of graphs is a powerful conceptual tool that describes relationships between discrete objects. Because of the growing importance of data analytics, many research groups have turned their attention to developing new approaches for solving large-scale graph problems. While the research results in this area have been valuable, the software products that have been produced tend to be limited in scope and/or not of sufficient quality to be reused. This project will address this problem by creation of GraphPack, a comprehensive unified graph library with a coherent user interface and support for multiple state-of-the-art compute platforms. This work will have broad impacts in scientific and engineering application areas, larger social and economic areas depending on graph analytics, and in education. GraphPack will improve the ease of use and broaden the applicability of graph algorithms. Application areas include such diverse areas as knowledge discovery, genomics, proteomics, electronic design automation, forest management, Internet routing, power grid management, and many more.

GraphPack will be a reliable and comprehensive toolkit applicable across a wide variety of problems and architectures that will unleash the capabilities of the community by making the current state of the art readily available. GraphPack will develop a consistent and comprehensive set of abstractions necessary to express a wide variety of (generic) graph algorithms and data structures in the context of unimodal as well as hybrid parallelism. These abstractions will be incorporated as abstract concepts, and selected concrete efficient implementations will be provided. While genericity is an important goal, GraphPack will also provide a simplified user interface for graph algorithms for the situations where simplicity is more important than fully tuned performance. GraphPack will also provide a GraphBLAS interface based on the recent efforts to provide a standardized set of graph operations based on the concepts of linear algebra. By providing multiple interfaces with efficient parallel implementations, GraphPack will enable a wide variety of applications to take advantage of high-performance graph algorithms.