Alexander Veidenbaum - US grants

This project includes two research efforts related to the Cedar project: enlargement of the Cedar shared memory and architectural studies for new large-scale multiprocessors. The memory enlargement allows realistic benchmarks to be run on the machine, which facilitates the architectural studies. The studies to be carried out include investigations of memory hierarchy organization in multiprocessors, cache design, virtual memory, and new techniques for processor synchronization and instruction execution. These topics are being investigated analytically, by simulation, and experimentally on the enlarged Cedar.

This is a workshop to bring together researchers and designers from academia and industry to discuss possible directions in the development of high-performance, parallel, distributed, and multimedia processors and systems. The topics center around systems on a chip and their utilization in building larger systems. The participants include designers of processors, compilers and operating systems, together with application experts. The wide representation will allow rich interaction concerning ideas and emphasis in the field.

Rapid advances in networking and Internet technologies has fueled the emergence of the "software as a service" model for enterprise computing that enables organizations to outsource many Information Technology (IT) services. This model allows organizations to concentrate on their core business instead of sustaining large investments in IT. IT outsourcing results in savings from the economies of scale due to leveraging of hardware, software, personnel, as well as maintenance and upgrade costs. Outsourcing is a common practice in Enterprise Resource Planning (ERP) and Customer Relationship Management (CRM) domains and it is gaining popularity in basic services such as email, storage and disaster protection.

This research will explore the data privacy challenges that arise in outsourcing data management services. Data management systems are among the most common, expensive, and complex software systems used by almost all types of organizations. In the envisioned "database as a service" (DAS) model, the client's data resides on the premises of the service provider and is accessed using SQL queries. Since clients' data as a very valuable asset, the service provider must implement sufficient security measures to guarantee data privacy. The research will explore the resulting challenges: (1) Privacy protection from malicious outsiders: protecting service providers from theft of customer data (e.g., hackers breaking into a provider's site and scanning all disks). (2) Privacy protection from database service providers: assuring that clients' encrypted data cannot be decrypted at the service provider. Thus, techniques to evaluate queries over encrypted data at the service provider need to be developed. (3) Ensuring Integrity of the Results: developing scalable techniques to ensure that the service provider returns exactly the right answer set to the client's query.

Embedded platforms are increasingly used to connect to the Web and are executing mobile code. These platforms are a resource-constrained environment in which interpreted execution of mobile codes is the norm because dynamic compilation is not feasible. At the same time, the performance of the executed code is of critical importance and is often a limiting factor in both the capabilities of the system and user perception.

The goals of the research proposed here are 1) to significantly improve interpreter performance for mobile code on embedded platforms without increasing resource requirements and 2) to design a resource constrained dynamic compilation system to be used with an interpreter for adaptive optimization to further improve the performance.

The goals will be achieved by using extensive compile-time analysis and by passing the results of the analysis to the interpreter running on a client system via code annotations. Annotations will identify super-operators, groups of instructions that can be executed as a unit and optimized together. This will allow a more efficient interpretation by minimizing communication overhead and dispatch costs. Annotations will also permit adaptive dynamic optimization requiring fewer resources and little or no overhead.

Project Abstract

Multi-core (parallel) processors are becoming ubiquitous. The use of such systems is key to science, engineering, finance, and other major areas of the economy. However, increased applications performance on such systems can only be achieved with advances in mapping such applications to multi-core machines. This task is made more difficult by the presence of complex memory organizations which is perhaps the key bottleneck to efficient execution, and which was not previously addressed effectively. This research involves making the mapping of the program to the machine aware of the complexities of the memory-hierarchy in all phases of the compilation process. This will ensure a good fit between the application code and the actual machine and thereby guarantee much more effective utilization of the hardware (and thus efficient/fast execution) than was previously possible.

Modern processors (multi-cores) employ increasingly complex memory hierarchies. Management of such hierarchies is becoming critical to the overall success of the compilation process since effective utilization of the memory hierarchy dominates overall performance. This research develops a new cache-hierarchy-aware compilation and runtime system (i.e., including compilation, scheduling, and static/dynamic processor mapping of parallel programs). These tasks have one thing in common: they all need accurate estimates of data element (iteration, task) computation and memory access times which are currently beyond the (cache-oblivious) state-of-the-art. This research thus develops new techniques for iteration space partitioning, scheduling, and synchronization which capture the variability due to cache, memory, and conditional statement behavior and their interaction. This research will have a broad impact on the computer industry as it will allow the ubiquitous multi-core systems of the future to be efficiently exploited by parallel programs.

The performance growth in uniprocessor (single core) performance resulting from improvements in semiconductor technology has recently slowed down significantly. Sequential applications or sequential portions of parallel applications require further advances to improve their performance. Today's processors complete instructions in their program order, which is a major performance bottleneck because any long-latency instruction, such as access to memory, delays completion of all subsequent instructions. This project aims to achieve higher single core performance by defining a new, compiler assisted mechanism for out of order instruction completion. It investigates how the use of compile-time program knowledge can be passed to the hardware and be used to simplify the architectural checks required for such out of order completion. The architecture of a standard processor is fully preserved and legacy software can execute without modification.
The out-of-order instruction commit mechanism will use a novel compiler/architecture interface. The compiler provides information about instruction ``blocks'' and the processor uses the block information to decide which instructions can be committed out of order and when. Some blocks are guaranteed to be data independent blocks which allows instructions from different such blocks be committed simultaneously and out of order. Other blocks have data or control dependencies and require in-order execution and in-order commit. Micro-architectural support for the new commit mode is driven by the block information, which significantly simplifies the hardware. Exception handling is also simplified with compiler assistance. The new commit mechanism will effectively increase the size of the instruction window allowing more cache misses to be overlapped for both L1 and L2 caches. The project will also investigate additional compiler and architecture optimizations to further improve performance.

Most modern microprocessors support some form of vector operations that allow the same operation to be applied to small vectors of arguments simultaneously. Studies have shown that use of these instructions can improve the performance of many scientific codes by a factor of 2 or more. Unfortunately, the state of the art in autovectorization falls far short of this goal, only achieving improvements of 20-30% on the same codes.

While studies have shown that current autovectorizing compilers do not identify all of the opportunities for vectorization, little is known about why they fail to do so. The PIs plan to evaluate tradeoffs between different compiler optimizations and vectorization in an effort to understand how optimization choices affect opportunities for autovectorization. They will use an extensive set of benchmarks to evaluate these tradeoffs. This research will make it possible to develop better autovectorizing compilers by avoiding optimization choices that interfere with autovectorization. The performance benefits of such compilers will improve the performance of applications ranging from multimedia software to scientific computing.

Title: XPS:FULL:FP:Collaborative Research:Advancing autovectorization

The goal of this project is to advance the state of the art in autovectorization. This is a technique applied by compilers to automatically transform computer programs so that they can take advantage of the vector devices found in most processors. Today, most compilers have autovectorization capabilities, but their effectiveness is limited. The intellectual merit of this project lies in its potential to advance an important and beautiful core area of computer science, compiler technology, by creating new techniques and extending our understanding of programming patterns, program analysis, and transformation techniques. Beyond computer science, the project's broader significance and importance is that its results aim at increasing the fraction of code segments that, without human intervention, make use of vector devices. The effect of this increase is the acceleration of computer programs and the reduction of the energy that they consume. Faster programs are of great importance in all application areas, but are particularly important in science and engineering where computing speed is an enabler of discoveries and better designs.

The research strategy is to develop and evaluate a prototype autovectorizer based on the exploration of the space of equivalent versions of a program guided by an intelligent search engine. The space of equivalent versions is obtained with a source-to-source restructurer. A repository of codelets is planned in order to train the search engine so that it becomes capable of guiding the selection in the space of possibilities in order to identify a highly efficient version of the code.