Software and Programmer Efficiency Research Group

Fully-funded PhD Positions available on the ParaBoost project in Lugano, Switzerland. More information.

Until recently our information society has been blessed with exponentially increasing computer system performance. With computer architects being forced to provide future performance improvements in the form of additional parallel cores, software developers have to parallelize their applications in order to see any future performance improvement. Unfortunately, parallelizing software is difficult. In this project we will thus investigate an approach to benefit from the increasing core count that does not require the explicit parallelization of applications. We base the project on the existing idea of competitive parallel execution (CPE). CPE lets multiple algorithms compete, each on its own core, on solving the same problem. The algorithm that finds the solution first wins the competition. The competition thus takes only as long as the fastest concurrently executing algorithm.

In the ParaBoost project, we will combine this idea of concurrently competing algorithm variants with the software engineering benefits afforded by modern programming languages. We will create a managed runtime environment called a multi-variant virtual machine (MVVM), to enable existing Java software to benefit from multi-variant execution. By lifting multi-variant execution into the language runtime, we will gain fine-grained control over the execution of the variants. This control will allow us to go beyond existing CPE approaches: The MVVM will be able to competitively execute software that uses more than one thread, it will improve performance by dynamically allocating more time to more promising variants, and it will learn and use models predicting the performance of variants based on features of their input.

To create the MVVM we will address a set of challenging research questions:

• How can we efficiently isolate competing variants inside a single virtual machine?
• How can we terminate the variants that lost the competition?
• How can we synchronize and contain the externally visible effects of variants?
• What are the classes of algorithms and software applications that most benefit from an MVVM?
• Can we automatically identify parts of applications that could benefit from competitive execution?
• How much can we gain by favoring variants that make more progress?
• How should we dynamically allocate time to variants?
• How can we build a model that predicts variant performance based on inputs?

We will build the MVVM on top of the Jikes RVM, a Java virtual machine specifically designed for virtual machine research. By building the MVVM we will be able to explore novel ideas that improve the state of the art in multi-variant execution. With our project, we will contribute to enabling the large body of existing sequential software to continue to benefit from future performance improvements.