Accelerating computing: the challenge of vectorisation

At a time when more and more fields of activity are generating ever-greater volumes of data, having access to software capable of processing this data effectively and more energy-efficiently has become a crucial issue. Processors play a key role as the computing units at the heart of all our computers and smartphones. One way to boost their power is to increase their operating frequency. The processor will then carry out more operations in a given time. 

However, in 2005, manufacturers ran into a “frequency wall”. One of their responses was to install several processors operating in parallel. “But one of the major industrial challenges is to keep increasing the computing density of processors through vectorisation,” explains Charles Paperman, a member of the Inria Links project team (University of Lille Inria centre), associate professor at the University of Lille and leader of the Shannon meets Cray (SxC) project. Vectorisation is precisely the aim of this project funded by the French National Research Agency (ANR), in which several Inria teams are participating.

Vectorisation, an outstanding mathematical technique

To understand what we are talking about, imagine a processor that has to perform five additions of two numbers. One option is to add the five additions one after the other, requiring five processor cycles (specialists call them “instructions”).

Another possibility is to group the numbers to be added into two columns (vectors in mathematical language) and then add these columns together in a single instruction. This is the principle of vectorisation, which increases the calculation density and requires fewer instructions for the processor. “In ideal cases, accelerations by a factor of eight are obtained,” explains Gabriel Radanne, a researcher and member of the Cash project team (Inria Lyon centre) who is involved in the SxC project.

A method inherited from Cray supercomputers

This is not a new technique, having been introduced into computers for the first time via Cray supercomputers (named after the engineer Seymour Cray) in the 1970s. “These computers were essentially designed for scientific computing and they triumphed in terms of FLOPS (floating point operations per second), in other words, their computing speed,” stresses Charles Paperman. 

Over the last ten years, these vector architectures have become increasingly popular. They are now included in the processors we all use, particularly for video decoding. However, some fields remain untouched by vectorisation.

In order to benefit from this acceleration, the processor must have a unit dedicated to vector calculation (such as the commonly used x86 architectures). Alongside this vector unit, a set of instructions is required to provide guidelines to the processor in a language it understands (“low-level” assembly language). 

Finally, the algorithm to be accelerated, which is written in a “high-level” language that is easier for programmers to handle, must be transformed so as to make proper use of vector instructions.

But when you move away from this structure, this technique works less well, if at all.

Possible applications in bioinformatics and data processing

The SxC project tackles this very problem:

One of the aims of the project is therefore to create a programming language that will guarantee the production of vectorised code. There is no shortage of possible applications... Bioinformatics for DNA sequence analysis and data processing are the first possibilities to be considered. Other fields potentially concerned include cybersecurity and artificial intelligence.

Extensive collaborative work involving different fields

To this end, researchers from Inria, the University of Lille, ENS Lyon, Grenoble INP - UGA and the University of Bordeaux will be working hand in hand. Some are specialists in theoretical computer science while others are experts in in programming languages, hardware synthesis and the applications in question. 

“These are very distinct IT communities, which are rarely used to working together. That is one of the standout features of this project,” points out Gabriel Radanne, an expert in programming languages, while Charles Paperman is proficient in circuit complexity theory.  

Underpinned by Shannon

The tools used to overcome the obstacles to vectorisation will indeed be based on circuit complexity theory, developed by Claude Shannon in the 1940s. Prior to the SxC project, Charles Paperman helped to “manually” create a vector-based algorithm for a query engine to explore JSON documents, a format widely used on the Web. By harnessing the theoretical tools of circuit complexity theory, this algorithm can improve information extraction efficiency by one or two orders of magnitude.

On this basis, the project now aims to develop an “intermediate representation” with the task of carrying out the necessary algorithm transformations, while answering formal questions. “Over and above the applications, a number of fundamental open questions underlie this project. Are there any programmes that cannot be vectorised? What class of problems can be vectorised?” says Charles Paperman. A programming language will also be designed to enable users to address this intermediate representation in the Rust ecosystem (a widely used programming language). 

Open-source software developments

All of these developments will also need to adapt to the different sets of vectorised instructions, which act as the “conductors” of microprocessors. In particular, one part of the project is devoted to the RISC-V instruction set. Unlike instruction sets developed by manufacturers such as Intel, this one is free to use. Developing and testing vectorised instructions for RISC-V is therefore a key digital sovereignty issue at national and European levels. In addition, all software development for the project will be carried out in open-source format. 

Although “Shannon Meets Cray” was launched last March, the project will really come into its own when several doctoral students are recruited in September. “Everyone's raring to go!” confides Charles Paperman. This project is scheduled to last for a total of five years. Watch this space...