Loop unRolling Stones : compiling in the polyhedral model.

LRS is a joint team between the Mélange Group from Colorado State University and the CAIRN team at IRISA, that started in January 2010.

Members

Steven Derrien (Assistant Professor at University of Rennes 1)
Sanjay Rajopadhye (Associate Professor at CSU)
Patrice Quinton (Professor at ENS Cachan)

Antoine Floc'h (PhD student CAIRN)
Antoine Morvan (PhD student CAIRN)
Naeem Abbas (PhD student CAIRN)
Tomofumi Yuki (PhD student CSU)

News

Antoine Morvan is currently in CSU for a two month stay, we will stay till late october. During his stay he will work on the validation of schedule for openMP programs and finalize the bridge between Gecos and Alphaz.

In addition to the EA weekly videoconferencing meetings, we have also set up a joint reading group session gathering students and faculties from both side of the EA every wednesday (morning for CSU, evening for INRIA).

The article of Naeem Abbas, Steven Derrien, Sanjay Rajopahdye and Patrice Quinton was accepted at the IEEE International Conference of Field Programmable Technologies to be held in Bejing in december 2010 (see below).

Steven Derrien and Patrice Quinton spent two weeks at CSU in July where they worked on efficient scheduling of reductions operations on hardware, and discussed joint research direction for the forthcoming years.

Antoine Floc'h spent one month in CSU in June, where he worked on code generation and more particulalry on how a MDE implemenation of the D-Tiling program transformation iniatilly proposed by DaeGon Kim and Sanjay Rajopadhye.

Tomofumi Yuki visited the CAIRN group from February 2010 to late May 2010. During his stay, he mainly worked on establishing possible links between MDE/EMF and the Alphaz infrastructure.

Context

Thanks to the outbreak of multi-core architectures, there is nowaday a renewed interest on optimizing and parallelizing compilers based on the so-called polyhedral model. Indeed, several industrial strengh compilers (llvm, gcc) now integrate polyhedral frameworks. However, there are still many open problems to be solved before this technology becomes mainstream.

Among these challenges, efficient compilation and parallelization for non conventional architectures (Graphical Processing Unit, FPGA based hardware accelerator, embedded heterogeous muti-core architectures) are crucial problems in both the High Performance Computing (HPC) and Electronic System Level (ESL) scientific communities.

To tackles these challenges, the LRS INRIA Equipe Associée propose to bring together researchers from CSU and INRIA who share a common background (the polyhedral model), have well recognized complementary skills (paralelization on GPUs for CSU and Hardware synthesis for INRIA-CAIRN), but most importantly have a very rich and strong history of collaboration.

Indeed, there exist a significant hitsry of collboration between the EA partners : Sanjay Rajopadhye who is now Associate Professor à Colorado State University spent 9 years at IRISA as CNRS full researcher. He was first a member of the API group from 1994 à 1996 (led par Patrice Quinton), and then took the head of the COSI project from 1996 à 2001. He was alos the advisor Steven Derrien PhD thesis. We hope that the EA will help rebuild the strong connections that have existed between the EA partners.

Research program

The goal of the team is twofold :

Propose new methodologies and algorithms to tackle some of the open problems in automatic parallelization and high level hardware synthesis from nested loop specifications. In particular, we would like to address the problem of parallelization of complex bioinformatics algorithms based of sophistcated dynamic programming algorithms, for which we would like to propose efficient parallelization schemes for both FPGAs (Field Programmable Gate Arrays) and GPUs (Graphical Processing Units).

Provide a common open software infrastructure based on (modern/cutting edge) software engineering techniques (Model Driven Sofwtare Developement) so as to help researchers prototying new ideas and concept in the domain of optimizing compilers. Our goal being to be able to make our in-house software completely interoperable.

As far as the second point is concerned, the CAIRN group at IRISA already have a strong commitment in using Model Driven Software Design technique, and has set up a very fruitfull collaboration with the Triskell EPI in Rennes. This is not yet the case of the Mélange group, however we expect to leverage on another equipe associée (the MoCAa EA) which also involves groups from CSU (Software Insurance Lab) and IRISA (Triskell group) to strenghen the connections on the CSU side.

Software

Publications

Naeem Abbas, Steven Derrien, Patrice Quinton, Sanjay Rajopadhye, Accelerating HMMER on FPGA using Parallel Prefixes and Reductions, to be presented as a full paper at the IEEE International Conference on Field Programmable Technology, Bejing december 2010.