The objective of IMPACT (Illinois Microarchitecture Project utilizing Advanced Compiler Technology) is to provide critical research, architecture expertise, and compiler prototypes for the microprocessor industry. This objective is accomplished by analyzing and demonstrating the level of hardware and compiler support required by architectural enhancements in order to understand the cost and effectiveness of these enhancements. IMPACT's focus has historically been instruction-level parallelism (ILP). The current focus has switched to exposing, enhancing, and exploiting coarse-grain parallelism applicable to future microarchitectures.

W.-M. Hwu*, S. Lumetta, M. Frank, N. Navarro, S. Ryoo, S.-Z. Ueng, C. Rodrigues, S. Sadeghi, S. Stone, S. Tsao, John Stratton, Melvin Lathara

MARCO FCRP Gigascale Systems Research Center (GSRC)

The success of parallel application development for multi-core and many-core processors will hinge upon the existence of strong automatic parallelizers, as well as effective manual parallel programming tools. Both types of tools require deep analysis techniques that discover coarse-grain parallelism in large applications written in standard programming languages - a task many in industry consider impossible. Both will also require techniques for automating the tedious performance tuning process needed for parallel applications to achieve scalability and performance goals.

The parallelism analysis requires techniques for distilling a clear view of the information flow through memory objects in the presence of dynamic memory allocation, variable-sized data structures, small function bodies, and heavy pointer usage. These techniques are designed to leverage high-level programmer insights in the properties of the data structures and algorithms, a venue not capitalized by previous parallelism discovery tools. Results from our previous GSRC Soft Systems work confirm that simultaneous breakthroughs in multiple analysis fronts must occur in order to illuminate the program's inherent parallelism. Some of the parallel regions involve multiple procedures with thousands of C statements, a granularity much larger than what most people considered possible for automatic detection. We foresee great opportunities to bring this capability to fruition.

The proposed work will consist of three interrelated aspects. One is to solve the known, remaining hard problems in automatic parallelism discovery: value range propagation, flow sensitivity, leveraging algorithmic-level properties (with Keutzer), and variable relations in a scalable manner. These problems have all been found in real applications. We will focus on solid engineering solutions in the same manner as did scalable solutions to the pointer analysis problem. The second aspect is to apply the parallelism discovery system to manual parallelization tools. This will be performed by interfacing the parallelism discovery information to visualization tools for use by parallel application developers and hardware accelerator designers. The third aspect of the work is to develop automatic parallelization technology that leverages parallelism discovery work. This will enable the programming paradigm where programmers focus on developing parallel algorithms and express them in a sequential but parallelizable form. The work will focus on program transformations that involve large amounts of code and crossing procedure boundaries, a critical capability needed to parallelize programs at the coarse-grain level.

W.-M. Hwu*, S. Lumetta, M. Frank, N. Navarro, D. Burke, S. Ryoo, S.-Z. Ueng, C. Rodrigues, S. Sadeghi, S. Stone, S. Tsao

DARPA/MARCO FCRP Gigascale Systems Research Center (GSRC), Advanced Micro Devices, Xilinx, IBM

This project seeks to achieve orders of magnitude of improvement in power efficiency in future computing platforms by systematically synthesizing and utilizing hardware accelerators in the forms of ASIP, ASIC, and FPGA. This approach is motivated by the availability of immense numbers of transistors in future chips and the limitation of activating only a tiny fraction of them at any given time. New system architectures allow seamless integration of accelerators and processors with extremely high-bandwidth, short-latency communication. Advanced program analysis and transformation techniques convert traditional memory side-effect-based execution activities into explicit data flow, enabling extremely efficient direct hardware execution.

W.-M. Hwu*, S. Lumetta, M. Frank, N. Navarro, S. Ryoo, C. Rodrigues, S. Sadeghi

DARPA/MARCO FCRP Gigascale Systems Research Center (GSRC), National Science Foundation-Information Technology Research (NSF-ITR)

Future breakthroughs in computer architecture, software engineering, and trustworthy computing will rely on the compiler to perform program analyses that are considered infeasible today. Deep program analysis refers to compile-time techniques that can accurately derive important properties of the program execution. Examples of deep analysis include value ranges that can be assumed by variables, realizable data flow through memory objects, and memory locations that can be accessed by program components. New scalable approaches to deep program analysis arebeing developed to enable their application to large, complex software systems.

W.-M. Hwu*, S. Ryoo, S. Sadeghi

DARPA/MARCO FCRP Gigascale Systems Research Center (GSRC), National Science Foundation-Information Technology Research (NSF-ITR)

Pointer analysis is a critical foundation for virtually all advanced program analysis techniques. In a programming language like C that supports an explicit address operator, indirect calls, structures, heap allocation, and pointer casting, memory activity can easily be obscured. We believe that highly accurate results and the ability to scale to large programs do not have to be mutually exclusive goals. To this end, a pointer analysis framework has been developed that provides an efficient representation for achieving accurate results through novel mechanisms to deal with procedural side effects, global variables, heap locations, and fields. We are currently in the process of refining our pointer analysis framework and adapting it for various purposes, such as C-to-synthesis.

W.-M. Hwu*, S.-Z Ueng

DARPA/MARCO FCRP Gigascale Systems Research Center (GSRC)

The paradigm through which software developers use popular programming languages augmented with Application Programming Interface (API) functions has become the norm for software development. However, an increasing number of libraries are being provided without source-level information due to a vested interest in protecting intellectual property. This means that even if a compiler is capable of performing deep analysis, it may not be provided with the required level of information. Consequently, a system providing critical API function-level information without violating intellectual property and the principles of data hiding and software reusability has become highly desirable. Prototype Extensions for API functionS (PEAS) are meant to elevate the interface between hardware and software in computer architecture with API function-level information and enable compiler transformations in the absence of API function source information.

W.-M. Hwu*, R.E. Kidd, S. Ryoo, S.-Z. Ueng, C. Rodrigues, S. Sadeghi

Gelato Federation, Hewlett-Packard, National Science Foundation

This project will release the IMPACT research compiler as a general-purpose, open-source compiler for the IA64 Linux platform. The research compiler's features, such as predicated compilation, instruction-level parallelism optimizations, compiler-engineered speculation, and profile-based optimizations, as well as its extensible research framework, will be retained. In addition, an easy-to-use interface will be provided that will allow OpenIMPACT to be used as a high-performance alternative to traditional compilers. We are continuing to extend this framework with capabilities such as better interprocedural analysis and ongoing research, such as deep analysis. This project will be released under the University of Illinois (UIUC/NCSA) Open Source License.

W.-M. Hwu*, S.-Z. Ueng, M. Lathara, S. Tsao

Microsoft

The Phoenix compiler project is a new initiative by Microsoft. We hope to leverage Phoenix's capabilities to handle C++ and other programming languages and access large real-world Microsoft applications, while contributing IMPACT's deep analysis capabilities. To this end we are developing a bridge between the internal representations of Phoenix and the IMPACT compiler. An initial demonstration will show how IMPACT's deep analysis benefits visualization.