logo - INRIA logo - CSU

Loop unRolling Stones : compiling in the polyhedral model.

Members | News | Context | Publications

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

  • Antoine Floc'h (PhD student CAIRN)
  • Antoine Morvan (PhD student CAIRN)
  • Naeem Abbas (PhD student CAIRN)
  • Tomofumi Yuki (PhD student CSU)
  • Vamshi Basupalli (Master student CSU)
  • Clément Guy (PhD student CAIRN-Triskell)

What happened in 2011?

  • Tomofumi will spend two month with the CAIRN group from late October 2011 to late December 2011. He will work with Antoine Morvan and Steven Derrien on cache prefetching techniques using polyhedral analysis.
  • Patrice Quinton spent 10 days in CSU in August 2011, he discussed the new memory allocation algorithm for the ALphaZ code generator for PGAS languages, developed by Tomofumi and provided helpful feedback. He and Rajopadhye started a review of architectures for exascale when energy constraints become dominant. In this context, locality of on-chip data transfers become critical. This may lead to revival of systolic techniques and Rajopadhye and Quinton are working to develop quantitative models for exascale architectures.
  • Naeem Abbas, Steven Derrien , Sanjay Rajoadhye and Patrice Quinotn submitted in august an extended version of their work on reductions in HMMER to IEEE Transaction on Parallel and Distributed Computing. The paper is currently under review.
  • The article of Antoine Floch, Tomofumi Yuki, Clément Guy, Steven Derrien, Benoit Combemale, Sanjay Rajopadhye and Robert France was accepted at the ACM/IEEE International Conference on Model Driven Engineering Languages and Systems to be held in Wellington in October 2011 (see below). This article involved member of two équipe associées LRS (EPI CAIRN) and MoCCA (EPI Triskell). It is the result of a very fruitful collaboration between the MDE and optimizing compilers communities.
  • Steven Derrien spent two months in CSU during June and July 2011. During this visit he was conducting the work of Youcef Barigou, a CAIRN internship who also visited CSU at that time. Among other task, the goal was to transform an implementation of a FDTD algorithm in order to run it efficiently on GPGPU using CUDA. He also discussed the research program of the EA for 2011-2012.
  • The article of Vamshi Basupalli, Tomofumi Yuki, Sanjay Rajopadhye, Antoine Morvan, Steven Derrien, Patrice Quinton and David Wonnacott was presented at the 7th International Workshop on OpenMP in Chicago in June 2011. This work has led to some interesting connection with the X10 language design group at IBM Watson, and we plan to extend the techniques use in this work so as to be able to deal with a more general class of programs in the context of the X10 language.

What happened in 2010?

  • Antoine Morvan spent two month in CSU, from September 2010 to end of October 2010. During his stay he worked on the validation of schedule for openMP programs and finalized 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 IRISA).
  • 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 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 exists a significant history of collboration between the EA partners : Sanjay Rajopadhye who is now Associate Professor at Colorado State University spent 9 years at IRISA as CNRS full researcher. He was first a member of the API group from 1994 to 1996 (led by Patrice Quinton), and then took the head of the COSI project from 1996 to 2001. He was alos the advisor of Steven Derrien during his 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 Software Developement) so as to help researchers prototyping new ideas and concepts 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 techniques, 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

  • Antoine Floch, Tomofumi Yuki, Clément Guy, Steven Derrien, Benoit Combemale, Sanjay Rajopadhye, Robert France, Model-Driven Engineering and Optimizing Compilers: A bridge too far?, to be presented as a full paper at the International Conference on Model Driven Engineering Languages and Systems, Wellington, New Zealand, October 2011
  • Vamshi Basupalli, Tomofumi Yuki, Sanjay Rajopadhye, Antoine Morvan, Steven Derrien, Patrice Quinton, David Wonnacott, ompVerify: Polyhedral analysis for the OpenMP Programmer, at the 7th International Workshop on OpenMP, Chicago, USA, June 2011 (doi).
  • Naeem Abbas, Steven Derrien, Patrice Quinton, Sanjay Rajopadhye, Accelerating HMMER on FPGA using Parallel Prefixes and Reductions, at the IEEE International Conference on Field Programmable Technology, Bejing, China, December 2010 (doi).