Index: /anr/anr.bib =================================================================== --- /anr/anr.bib (revision 173) +++ /anr/anr.bib (revision 174) @@ -620,2 +620,18 @@ year = {2001}, } +@INPROCEEDINGS{FP:96 + ,AUTHOR = "Paul Feautrier" + ,TITLE = "Automatic Parallelization in the Polytope Model" + ,BOOKTITLE = "The Data-Parallel Programming Model" + ,YEAR = 1996 + ,EDITOR = "Guy-Ren\'e Perrin and Alain Darte" + ,PAGES = "79--103" + ,VOLUME = "LNCS 1132" + ,PUBLISHER = "Springer" +} + +@book{DRV:2000, + author={Alain Darte and Yves Robert and Fr\'ed\'eric Vivien}, + title={Scheduling and automatic Parallelization}, + publisher={Birkh\"auser}, year=2000 +} Index: /anr/section-3.1.tex =================================================================== --- /anr/section-3.1.tex (revision 173) +++ /anr/section-3.1.tex (revision 174) @@ -166,45 +166,4 @@ \subsubsection{Automatic Parallelization} -% FIXME:LIP FIXME:PF FIXME:CA -% Paul je ne suis pas sur que ce soit vraiment un etat de l'art -% Christophe, ce que tu m'avais envoye se trouve dans obsolete/body.tex -%\mustbecompleted{ -%Hardware is inherently parallel. On the other hand, high level languages, -%like C or Fortran, are abstractions of the processors of the 1970s, and -%hence are sequential. One of the aims of an HLS tool is therefore to -%extract hidden parallelism from the source program, and to infer enough -%hardware operators for its efficient exploitation. -%\\ -%Present day HLS tools search for parallelism in linear pieces of code -%acting only on scalars -- the so-called basic blocs. On the other hand, -%it is well known that most programs, especially in the fields of signal -%processing and image processing, spend most of their time executing loops -%acting on arrays. Efficient use of the large amount of hardware available -%in the next generation of FPGA chips necessitates parallelism far beyond -%what can be extracted from basic blocs only. - -%The Compsys team of LIP has built an automatic parallelizer, Syntol, which -%handle restricted C programs -- the well known polyhedral model --, -%computes dependences and build a symbolic schedule. The schedule is -%a specification for a parallel program. The parallelism itself can be -%expressed in several ways: as a system of threads, or as data-parallel -%operations, or as a pipeline. In the context of the COACH project, one -%of the task will be to decide which form of parallelism is best suited -%to hardware, and how to convey the results of Syntol to the actual -%synthesis tools. One of the advantages of this approach is that the -%resulting degree of parallelism can be easilly controlled, e.g. by -%adjusting the number of threads, as a mean of exploring the -%area / performance tradeoff of the resulting design. - -%Another point is that potentially parallel programs necessarily involve -%arrays: two operations which write to the same location must be executed -%in sequence. In synthesis, arrays translate to memory. However, in FPGAs, -%the amount of on-chip memory is limited, and access to an external memory -%has a high time penalty. Hence the importance of reducing the size of -%temporary arrays to the minimum necessary to support the requested degree -%of parallelism. Compsys has developped a stand-alone tool, Bee, based -%on research by A. Darte, F. Baray and C. Alias, which can be extended -%into a memory optimizer for COACH. -%} The problem of compiling sequential programs for parallel computers @@ -214,5 +173,5 @@ the preservation of the program semantics. Most of these transformations just reorder the operations of the program; some of them modify its -data structures. Dpendences (exact or conservative) are checked to guarantee +data structures. Dependences (exact or conservative) are checked to guarantee the legality of the transformation. @@ -221,8 +180,15 @@ which interact in a complicated way. More recently, it has been noticed that all of these are just changes of basis in the iteration domain of -the program. This has lead to the invention of the polyhedral model, in -which the combination of two transformation is simply a matrix product. - -As a side effect, it has been observed that the polytope model is a useful +the program. This has lead to the introduction of the polyhedral model, +\cite{FP:96,DRV:2000} in which the combination of two transformation is +simply a matrix product. + +Since hardware is inherently parallel, finding parallelism in sequential +programs in an important prerequisite for HLS. The large FPGA chips of +today can accomodate much more parallelism than is available in basic blocks. +The polyhedral model is the ideal tool for finding more parallelism in +loops. + +As a side effect, it has been observed that the polyhedral model is a useful tool for many other optimization, like memory reduction and locality improvement. Another point is Index: /anr/section-7.tex =================================================================== --- /anr/section-7.tex (revision 173) +++ /anr/section-7.tex (revision 174) @@ -46,5 +46,5 @@ professor at ENS Lyon (Paul Feautrier) and a research associate (CR2) at INRIA Rh\^one-Alpes (Christophe Alias). The non-permanent - personal required is a PhD student that will work on network process + personel required is a PhD student that will work on network process generation from polyhedral loops, then on extensions to non-polyhedral loops. We are looking for a student with both @@ -53,5 +53,5 @@ a working implementation. \parlf - The table below summarizes the \hommemois in man-months by + The table below summarizes the \hommemois by deliverables and tasks for both permanent and non-permanent personnels. The non-permanent personnels costs represent 23\% of