Search 

Background to our research

Computer systems form an increasingly important part of the infrastructure of our society and are a crucial component of many industrial products. Software accounts for a dominant part of the development costs of computer systems in almost all industrial sectors. The steady exponential increase in processor efficiency following Moore's law, which has increased the speed of software almost automatically, has allowed large software systems to perform increasingly complex information processing functions. This trend has now reached its technological limits. We have reached the inevitable turning point, at which it is no longer possible to use the increasing supply of transistors on a chip to make individual processors much faster; from now on chips will contain several processors ("cores") that work in parallel to attain higher performance. Using multiple cores is also the only means to make chips consume less energy without decreasing efficiency. Current chips use a handful of cores, but this number is predicted to reach hundreds within a few years. The introduction of cost-effective multicores in almost all application domains means that almost all software development must design or redesign their programs to exploit parallelism to achieve efficiency and to reduce power consumption.

The multicore revolution will induce a paradigm shift in computer science, where several fields must refocus their research goals in order to supply techniques and tools to support development of software for multicore platforms. Parallel multi-computers, such as supercomputers and multi-computers (SMPs), have been around for two decades, and they have been a subject of research in algorithms, programming languages, etc. However, parallel programming has been restricted to performance-critical niche areas such as scientific computing. Moreover, programming for multicores will be different than programming for parallel multi-computers, since multicores have quite different trade-offs compared to past parallel computers: on-chip communication between cores, caches and memory elements will be very cheap, whereas the flow of data between the processor chip and the main memory will become the major bottleneck; programs can afford to perform additional parallel computation using an extra core at very little cost. The introduction of multicores in virtually all application areas will dramatically increase the demand for scientific and technological advances that support development of parallel software.

This vision incurs a grand challenge for computer science: constructing correct and efficient programs for parallel platforms is drastically more difficult than constructing sequential programs. Uncovering and exploiting the potential parallelism in an application problem is often difficult. Reasoning about all possible interactions in parallel executions, which may cause correctness and performance defects is notoriously complicated. As a result, parallel programming has so far been done only by experts and has been restricted to specific application areas (e.g., scientific computing) where programs have a regular structure. Fortunately, the last decades have witnessed dramatic advances in areas such as programming language technology, program analysis, verification, performance analysis, and embedded systems design, which can be leveraged to develop theories, methods, and tools for developing efficient and reliable software that exploits multicore platforms for increased performance and reduced energy consumption.

The UPMARC center will address the challenges in developing theories, methods, and tools that enable software development to reach the level foreseen by this vision. Key challenges are in the following areas.

• Algorithm construction: we shall develop principles for algorithm construction in key application areas; The new trade-offs for multicores in comparison with previous multi-computers will change many aspects of parallel programming.

• Resource Management: we will develop techniques for making the most efficient use of system resources, including processor cores, memory units, communication bandwidth, in order to meet requirements of performance and predictability. This is crucial especially for embedded programs, e.g., controlling industrial processes or products, which must compute results under timing constraints, often using tight energy and resource budgets. For single-processor systems, there are well-established techniques for this problem, but not so for parallel systems. We need new techniques in this area, considering the completely new architectures and cost trade-offs for multicores.

• Programming Language Technology: we will develop programming language constructions and paradigms, that allow the software developer to express the potential parallelism of an algorithm, at the same time as shielding her from the added complexity of concurrency. These constructs will be realized efficiently by transformations and run-time implementation for multicore platforms. Because of the transition to multicores, there will be both a drastically increased interest in adopting programming languages and constructs tailored for parallel execution, and a demand from chip manufacturers for hardware features that support parallel programming (transactional memory being one example).

• Verification: we will develop techniques for analyzing vital correctness properties. Testing and verification consumes enormous resources for establishing confidence in the correctness of software. Parallel programming makes this task significantly more challenging, due to the need for reasoning about the vast number of possible interactions between concurrently executing threads. Tools for verification of parallel software are still inadequately developed, but the last decades advances in program analysis and automated verification have created good prospects for ameliorating this situation.

More information is available in The UPMARC research programme.