tailieunhanh - High Level Synthesis: from Algorithm to Digital Circuit- P24

High Level Synthesis: from Algorithm to Digital Circuit- P24: This book presents an excellent collection of contributions addressing different aspects of high-level synthesis from both industry and academia. "High-Level Synthesis: from Algorithm to Digital Circuit" should be on each designer's and CAD developer's shelf, as well as on those of project managers who will soon embrace high level design and synthesis for all aspects of digital system design. | 12 High-Level Synthesis of Loops Using the Polyhedral Model 219 In Sect. we shall survey the front-end transformations whereas back-end will be presented in Sect. . The MMAlpha Front-End From Initial Specifications to a Virtual Architecture The front-end of MMAlpha contains several tools to perform code analysis and transformations. Code analysis and verification The initial specification of the program called here a loop nest is translated into an internal representation in form of recurrence equations. Thanks to the polyhedral model some properties of the loop nest can be checked by analysis one can check for example that all elements of an array represented by an Alpha variable are defined and used in a system by means of calculations on domains. More complex properties of code can also be checked using verification techniques 8 . Scheduling This is the central step of MMAlpha. It consists in analyzing the dependences between the variables and deriving for each variable say V i j a timing-function tv i j which gives the time instant at which this variable can be computed. Timing-functions are usually affine of the form tv i j av i v j TV with coefficients depending on variable V. Finding out a schedule is performed by solving an integer linear problem using parameterized integer programming and is described in 17 . More complex schedules can be found multi-dimensional timing functions for example allow some forms of loop tiling to be represented but code generation is still not available for such functions. Localization It is an optional transformation also sometimes referred to as uniformization or pipelining that helps removing long interconnections 28 . It is inherited from the theory of systolic arrays where data which are reused in a calculation should be read only once from memory thus saving input-outputs. MMAlpha performs automatically many such localization transformations described in the literature. Space-time mapping Once a schedule is