Changeset 30 for anr/section-3.1.tex

Timestamp:

Jan 12, 2010, 3:27:48 PM (15 years ago)

Author:

coach

Message:

M anr/section-2.tex
M anr/section-2.2.tex
M anr/section-3.1.tex

File:

• anr/section-3.1.tex (modified) (1 diff)

anr/section-3.1.tex

@@ -131 +131 @@
 % 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
-hardaware 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.
-}
+%\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
+has been studied since the advent of the first parallel architectures 
+in the 1970s. The basic approach consists in applying program transformations
+which exhibit or increase the potential parallelism, while guaranteeing
+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
+the legality of the transformation.
+
+This has lead to the invention of many loop transformations (loop fusion,
+loop splitting, loop skewing, loop interchange, loop unrolling, ...)
+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
+tool for many other optimization, like memory reduction and locality
+improvement. Another point is
+that the polyhedral domain \emph{stricto sensu} applies only to
+very regular programs. Its extension to more general programs is
+an active research subject.
 
 \subsubsection{Interfaces}