OptiTrust: towards bug-free, optimized computer code

There are those who know how to optimize codes to make them faster, and those who know how to check them to detect and remove bugs. And then there is OptiTrust, an exploratory action supported by Inria and directed by Arthur Charguéraud, who aims to do both at once. This ambitious project first began to take shape three years ago during a joint project carried out by the Tonus and Camus teams at Inria Nancy Grand-Est as part of a PhD thesis by Yann Barsamian.The goal of that work was to optimise a code for the simulation of particle behaviour in plasmas (the same type of phenomena as that which happens in the sun). “For the simulation to be as accurate and realistic as possible, we strive to take into consideration a maximum number of particles," explains Arthur Charguéraud. “To ensure that the performance remains acceptable, we have to use all the possibilities offered by parallelism".

The particles are handled by several interconnected servers, each of which contains up to 64 cores which in turn incorporate parallel instructions (called "SIMD instructions" for Single Instruction Multiple Data), each capable of performing 16 arithmetic operations at once. “By taking advantage of the capabilities of each of these levels we can simulate the behaviour of 1,000 billion particles using with 200 servers, for example,” explains the researcher enthusiastically.

But the challenge is to develop a code that can get the maximum out of this power. “Yann Barsamian managed to write a code that performs very well, but to do so he had to test a large number of optimization options," continues Arthur Charguéraud. Manually writing hundreds of lines of code for each of these options is extremely time-consuming. Not to mention that each modification by hand increases the risk of introducing an error! In addition, if the servers used are changed, the optimizations that were previously the most efficient may no longer be as effective. Some optimizations might even have to be "undone". Hence the idea of a solution that can create efficient, portable and bug-free codes that perform well.

To reach this goal, Arthur Charguéraud had the idea of "making the computer do the work", by writing a code that would do the optimization work for him! This is how the OptiTrust exploratory action was born. “It's a risky gamble because the underlying approach, called "code transformation", is a divisive subject among researchers in computer science: some are not convinced that it is possible to obtain high-performance code in this way, while others use this approach but rely on programming languages that are very specific to a given field of application," explains the OptiTrust leader. "For our part, we have decided to use code transformations but with a widely used generalist language (C language), which allows us to optimise very diverse programmes”.

A code... and human intuition

Concretely, this means developing a tool that modifies the code instead of the human, while following human instructions. The programmer first writes the initial code, without worrying about how well it performs, specifying only that the aim for example is to simulate particle displacement in plasma. A second code is then designed, called a "script", which explains how the programmer wants to modify the initial code to make it more efficient. Each transformation is chosen from a catalogue of options. The sequence of these transformations produces the final optimized code. “This system solves all the problems encountered up to now: it allows dozens of optimization sequences to be tested very quickly", says Arthur Charguéraud. “In addition, if the script is moved to another machine, it can repeat the operation and find the best optimization again. Similarly, if the programmer modifies the initial code, the optimizations that will no longer apply can simply be deactivated while other transformations can continue to be applied. Finally, since the programmer doesn't modify the code by hand, writing it will be much quicker and there will be far fewer bugs".

Overcoming barriers to optimization and verification

All that is the theory.... But implementing it is much more complicated! Firstly, because the script must be told which line of code to intervene on... in a code which has already been modified by previous transformations. “To get around this difficulty, we have to find a way of navigating through the code, and to do so we rely on the notion of a "path", reveals Arthur Charguéraud. “The idea of a path is to identify which passing points in the code will be preserved by the first transformations and which will serve as landmarks to indicate which lines to apply subsequent transformations to".

The second major obstacle is ensuring that there are no bugs in the code making the transformations: this code is designed to modify another code, but in this type of tool, there is a high risk of bugs. “As a matter of fact, in compilers, which are also codes that transform other codes, bugs are found every day. And these compilers have been around for decades!” says the researcher. So what is the solution? Formal proof: tools that allow it to be mathematically proved that, whatever code is provided, the transformation will always produce an equivalent code, i.e. one that calculates the same thing—but faster.

Applications in various fields

On the basis of these ideas, Arthur Charguéraud applied for his exploratory action in March 2019... and in under two months he received the go-ahead from Inria, which granted him post-doc funding for more than two years as well as a budget for missions in France and abroad and equipment.

The project, which started in October 2019, has already made progress on path manipulation and is now tackling the catalogue of transformations. The aim is to get the tool to a point where it can be applied in a case study, i.e. a comparison between the code produced by the transformations and the one designed by the PhD student of the Camus team, Yann Barsamian. Hopefully, with a few dozen lines of starting code and a few dozen transformation instructions, it will be possible to generate a code that is at least as good as the thousands of handwritten lines of code. “In this particular case, I'm convinced that it's feasible”, says the researcher. “Once our tool has been developed, the next step will be to assess the approach using other numerical simulation codes on which the Tonus project team is working. If it works, we will have a clearer vision of whether the tool can be used to optimize programs from other areas where performance is also essential. Potentially, our tool could facilitate the work of industrial or academic partners and developers specialised in high-performance computing”.