Microsoft External Research backgrounder, July 2008
On July 28, 2008, Microsoft External Research announced the seven academic research projects that will share $1.5 million as part of the Safe and Scalable Multicore Computing request for proposal (RFP). The aim of this RFP is to stimulate and enable bold, substantial research in multicore software that rethinks the relationships among computer architecture, operating systems, runtimes, compilers and applications. The goal of the research is to propose new mechanisms and paradigms that will lead to safe and scalable concurrent systems and applications, focusing on mainstream client platforms.
Following are details of the winners and projects:
Sensible Transactional Memory via Dynamic Public or Private Memory, Dan Grossman, University of Washington, United States
Integrating transactions into the design and implementation of modern programming languages is surprisingly difficult. The broad goal of this research is to remove such difficulties via work in language semantics, compilers, runtime systems and performance evaluation. Researchers at the University of Washington will investigate programming-language techniques for eliminating semantic anomalies in weakly atomic transactional memory systems. While the basic notion of explicitly public or private memory is straightforward, the scientists involved in these projects identify five open research questions — subobject granularity, superobject granularity, parallelism within transactions, inference tools and ordering constraints — that will help make the idea a practical part of programming languages with transactional memory.
Supporting Scalable Multicore Systems Through Runtime Adaptation, Kim Hazelwood, University of Virginia, United States
The Paradox Compiler Project aims to develop the means to build scalable software that executes efficiently on multicore and manycore systems via a unique combination of static analyses and compiler-inserted hints and speculation, combined with dynamic, runtime adaptation. This research will focus on the Runtime Adaptation portion of the Paradox system. Future parallelization systems must be capable of dynamically adapting a compiled application to the underlying hardware and the execution environment because the specific hardware configuration (number of cores, number of function units per core, cache sizes) will not — and should not — be known by the compiler. Meanwhile, the system utilization changes at runtime, enabling the application to use more or fewer cores. Finally, the behavior of the application itself changes over time, which should result in regular re-evaluation of parallelism decisions. The focus of this team’s research is to develop a runtime system that requires a companion dynamic compilation layer to complement the static parallelization layer.
Language and Runtime Support for Safe and Scalable Programs, Antony Hosking, Jan Vitek, Suresh Jagannathan and Ananth Grama, Purdue University, United States
Expressing and managing concurrency at each layer of the software stack, with support across layers, as necessary, to reduce programmer effort in developing safe applications while ensuring scalable performance is a critical challenge. This team will develop novel constructs that fundamentally enhance the performance and programmability of applications using transaction-based approaches. The researchers will build tools grounded in the C# language, by extending technologies including Phoenix, Bartok and Singularity, building support for specification, analysis, compilation, execution and benchmarking of high-level transaction-based abstractions for concurrent programming.
Multicore-Optimal Divide-and-Conquer Programming, Paul Hudak, Yale University, United States
Divide and conquer is a natural, expressive and efficient model for specifying parallel algorithms. This team cast divide and conquer as an algebraic functional form, called DC, much like the more popular map, reduce and scan functional forms. As such, DC subsumes the more popular forms, and its modularity permits application to a variety of problems and architectural details. This team will tailor DC to multicore architectures and develop a notion of multicore-optimal divide-and-conquer programming. Expressing an algorithm in this framework not only will ensure maximal parallelism, but also will guarantee minimal communication costs, thus achieving a high degree of efficiency.
Geospatial-based Resource Modeling and Management in Multi- and Manycore Era, Tao Li, University of Florida, United States
To ensure that multicore performance will scale with the increasing number of cores, innovative processor architectures (e.g., distributed shared caches, on-chip networks) are increasingly being deployed in the hardware design. This team will explore novel techniques for geospatial-based on-chip resource utilization analysis, management and optimization focusing on accurate and scalable methods to model the geospatial resource utilization patterns across a large number of cores/components; architecture and operating system support for efficient mining of geospatial-based resource utilization at large scales; and studying the enabled geospatial-aware cooperative resource management for multi- and manycore processors.
Reliable and Efficient Concurrent Object-Oriented Programs (RECOOP), Bertrand Meyer, ETH Zurich, Switzerland
The goal of this project, starting with the simple concurrent object-oriented programming (SCOOP) model of concurrent computation, is to develop a practical formal semantics and proof mechanism, enabling programmers to reason abstractly about concurrent programs and allowing proofs of formal properties of these programs. Specifically, this team aims to enable precise reasoning on concurrent programs at a level of abstraction comparable with what is possible on sequential programs using modern languages and programming techniques. In addition, the project aims to enable formal reasoning and proofs.
Runtime Packaging of Fine-Grained Parallelism and Locality, David Penry, Brigham Young University, United States
Scalable multicore environments will require the exploitation of fine-grained parallelism to achieve superior performance. To overcome the overhead of task synchronization and variability in system architectures and runtime environments, packaging of parallelism and locality should be performed by the runtime environment. Current packaging algorithms suffer from a number of limitations. These researchers will develop new packaging algorithms that can take into account both parallelism and locality, are aware of critical sections, can be rerun as the runtime environment changes, can incorporate runtime feedback, and are highly scalable.
Parallel Computing Background
Parallel and multicore computing will radically transform computing as we know it, enabling a revolution in how people tap into the power of personal computing and its benefits. The entire computer industry is at a critical juncture. Computing has moved to multicore architectures, with increasing numbers of processors being integrated into single chips. Leveraging the computing power of those chips requires new platform architectures, operating system architectures, programming methods and tools, and application models. The changes affect the entire industry — including consumers, hardware manufacturers, the entire software development infrastructure, and application developers who rely on the software infrastructure to develop parallel computing applications.
Microsoft Corp. has been addressing the challenges of multicore processing and parallel computing, from both product and research perspectives, for the past several years. Microsoft External Research is working with industry and academic research communities, including the Barcelona Supercomputing Center, Universal Parallel Computing Research Center (UPCRC), Intel Corporation and research teams at the University of California, Berkeley, and University of Illinois at Urbana-Champaign, and now with the Safe and Scalable Multicore Computing RFP, to continue furthering developments in this important area.
The concept behind parallel computing is to divide a project into smaller bits of work that can be processed at the same time, or in parallel. Recent headlines have touted new duo-core and quad-core products that squeeze multiple processor cores onto a single chip. The idea is that more processor cores executing parts of the same program simultaneously can enable greater performance and achieve significant power savings.p>
To leverage the performance advantages from that parallelism on chips, we have to rethink how we develop software. The way we develop code that runs in parallel and uses those processors has implications for a whole new set of developments as well as for the existing software base.
Microsoft believes that a new class of more intelligent, aware, reliable, secure and useful applications will emerge through progress in parallel computing, delivering improvements in server, desktop and mobile computing experiences for businesses and consumers.