Project News

Programming Large Scale Embedded Systems

The memory wall problem cannot be overcome by new operating systems or infrastructures alone, if the application is not properly prepared for it, i.e. if the data dependencies are not properly identified and treated in the program itself. Classical programming models are not aligned to this problem and hence make it difficult for compilers and the operating system to properly analyse the data dependency and to adjust accordingly.

Within the S(o)OS project, a new programming concept exploiting data flow information inherent to mathematical description has been proposed to address this problem.

Much like StarSs, the approach of this programming model consists in annotating the code with information regarding the respective data dependencies – however, in the form of mathematical representations of the functional block, rather than an in- and output interface. As we could show in S(o)OS, this allows for the following major advantages:

• correctness can be more easily verified by the developer

• the application does not have to be organised as a workflow, but can be programmed in any fashion

• the dependencies are specified in a more fine-granulated manner, allowing for overlaps in scheduling, pre-fetching etc.

• most importantly, the code behaviour, its segmentation and its degree of concurrency can be manipulated (to a degree)

It is easy to generate a dependency graph from a mathematical declaration, which in turn provides sufficient information for a scheduler to execute the respective functional blocks in an order that maximises resource utilisation. From the dependency graph also the best iteration function and potential segmentations can be identified that reduce the degree of dependency between parallel executed threads and adjust the relationship between work- and communication-load. In other words, we represent both the tasks, as well as its iteration function as mathematical formulas and transform the iteration function, so that the number of edges per executed slice is minimal (cf. figure).

In addition to this, the function itself can be transformed using classical mathematical theorems, allowing for alteration of the dependency graph itself.

Such transformations, however, have an effect on the declaration of the algorithmic body itself, in terms of dependencies (which data is consumed) and even in terms of algorithm itself. Not all transformations are thus equally sensible, as they may have an effect on the execution performance of the respective task. In the follow-up project POLCA, funded by the European Commission and to be started September 2013, we will elaborate these transformation-effects and develop an according tool-chain that will allow compilation unto different platforms.

Project partners include: University of Ulm; University of Twente; HLRS, University of Stuttgart; CETIC, Centre d’Excellence en Technologies de l’Information et de la Communication; IMDEA, Instituto Madrileno de Estudios Avanzados; Maxeler Technologies; Recore Systems

A first elaboration of the model and the transformation mechanisms will be presented at the ParCo 2013 conference in Munich on the 10^th to 13^th of September, so please join us for discussion there.