____________________________________________________________________ APPLICATION-DRIVEN ARCHITECTURE SYNTHESIS ____________________________________________________________________ EDITED BY Francky Catthoor IMEC Leuven, Belgium Lars Svensson IMEC Leuven, Belgium KLUWER ACADEMIC PUBLISHERS Boston/London/Dordrecht ____________________________________________________________________ CONTRIBUTORS Michael Birbas Ed Deprettere VLSI Design Lab. Delft University of Technology Dept. of Electrical Engineering Mekelweg 4 University of Patras 2600 GA Delft, The Netherlands Patras 26110, Greece Patrick Dewilde Jens P. Brage Delft University of Technology Dept. of Computer Science Mekelweg 4 Technical University of Denmark 2600 GA Delft, The Netherlands Building 344 DK2800 Lyngby, Denmark Frank Franssen VLSI Systems Design Methodology Dept. Francky Catthoor IMEC VLSI Systems Design Method. Dept. Kapeldreef 75 IMEC B3001 Leuven, Belgium Kapeldreef 75 B3001 Leuven, Belgium Werner Geurts VLSI Systems Design Methodology Dept. Bernard Courtois IMEC TIM3/INPG Kapeldreef 75 46 av. Felix Viallet B3001 Leuven, Belgium 38031 Grenoble C'edex, France Manfred Glesner Alain Darte Technische Hochschule Darmstadt Laboratoire de l'Informatique FG Mikroelektronische Systeme du Parall'elisme_TIM3 Karlstr. 15 'Ecole Normale Sup'erieure de Lyon D-6100 Darmstadt 46, All'ee d'Italie Germany 69364 Lyon C'edex 07, France Costas Goutis Hugo De Man VLSI Design Lab. VLSI Systems Design Method. Dept. Dept. of Electrical Engineering IMEC University of Patras Kapeldreef 75 Patras 26110, Greece B3001 Leuven, Belgium ii Peter Held Ole Olesen Delft University of Technology Dept. of Computer Science Mekelweg 4 Technical University of Denmark 2600 GA Delft, The Netherlands Building 344 DK2800 Lyngby, Denmark Geert Janssen Dept. of Electrical Engineering Vasilis Paliouras Eindhoven Univ. of Technology VLSI Design Lab. P.O. Box 513 Dept. of Electrical Engineering 5600 MB Eindhoven, The Netherlands University of Patras Patras 26110, Greece Ahmed Amine Jerraya TIM3/INPG Inhag Park 46 av. Felix Viallet TIM3/INPG 38031 Grenoble C'edex, France 46 av. Felix Viallet 38031 Grenoble C'edex, France Jochen Jess Dept. of Electrical Engineering Lars Philipson Eindhoven Univ. of Technology Dept. of Comp. Engineering P.O. Box 513 Lund University 5600 MB Eindhoven, The Netherlands P.O. Box 118 S-221 00 Lund, Sweden Efstathios Kyriakis-Bitzaros VLSI Design Lab. Peter P"ochm"uller Dept. of Electrical Engineering Technische Hochschule Darmstadt University of Patras FG Mikroelektronische Systeme Patras 26110, Greece Karlstr. 15 D-6100 Darmstadt Herv'e Le Verge Germany IRISA-CNRS-INRIA Campus de Beaulieu Patrice Quinton 35042 Rennes C'edex, France IRISA-CNRS-INRIA Campus de Beaulieu Jan Madsen 35042 Rennes C'edex, France Dept. of Computer Science Technical University of Denmark Kenny Ranerup Building 344 Dept. of Comp. Engineering DK2800 Lyngby, Denmark Lund University P.O. Box 118 Kevin O'Brien S-221 00 Lund, Sweden TIM3/INPG 46 av. Felix Viallet 38031 Grenoble C'edex, France iii Tanguy Risset Micha"el van Swaaij Laboratoire de l'Informatique VLSI Systems Design Methodology Dept. du Parall'elisme_TIM3 IMEC 'Ecole Normale Sup'erieure de Lyon Kapeldreef 75 46, All'ee d'Italie B3001 Leuven, Belgium 69364 Lyon C'edex 07, France Paul Wielage Yves Robert Delft University of Technology Laboratoire de l'Informatique Mekelweg 4 du Parall'elisme_TIM3 2600 GA Delft, The Netherlands 'Ecole Normale Sup'erieure de Lyon 46, All'ee d'Italie Norbert Wehn 69364 Lyon C'edex 07, France Technische Hochschule Darmstadt FG Mikroelektronische Systeme Jan Rosseel Karlstr. 15 VLSI Systems Design Method. Dept. D-6100 Darmstadt IMEC Germany Kapeldreef 75 B3001 Leuven, Belgium Klaus W"olcken Commission of the E.C. Dimitris Soudris Rue de la Loi 200 VLSI Design Lab. B1049 Brussels, Belgium Dept. of Electrical Engineering University of Patras Patras 26110, Greece Thanos Stouraitis VLSI Design Lab. Dept. of Electrical Engineering University of Patras Patras 26110, Greece Lars Svensson VLSI Systems Design Methodology Dept. IMEC Kapeldreef 75 B3001 Leuven, Belgium Jos van Eijndhoven Dept. of Electrical Engineering Eindhoven Univ. of Technology P.O. Box 513 5600 MB Eindhoven, The Netherlands ____________________________________________________________________ CONTENTS Preface ix 1 Application-driven synthesis methodologies for real-time processor architectures 1 1 Problem description 1 2 State-of-the-art and beyond 3 3 Contribution of this book 4 4 System specification model 7 5 Synthesis of array processors 9 6 Synthesis of multiplexed processors 12 7 Chapter overview 15 8 Conclusion 18 References 18 2 Behavioral specification for synthesis 23 1 Introduction 23 2 The ASCIS data flow graph 25 3 Input specification languages 37 4 Conclusion 43 References 44 3 Formal methods for solving the algebraic path problem 47 1 Introduction 47 2 The algebraic path problem 48 3 Pioneering systolic APP designs 50 4 Advanced systolic APP designs 52 5 Extending synthesis methods 55 v vi Application-driven architecture synthesis 6 Partitioning issues 62 7 Conclusion 66 References 66 4 HiFi: from parallel algorithm to fixed-size VLSI processor array 71 1 Introduction 71 2 Design philosophy 73 3 Algorithmic specification 74 4 Architecture model 76 5 Design trajectory 77 6 Fixed-size architecture design 88 7 Conclusion 92 References 92 5 On the design of two-level pipelined processor arrays 95 1 Introduction 95 2 Transformation of nested loops to UREs 98 3 Word-level array design 102 4 Bit-level array design 108 5 Conclusion 114 References 116 6 Regular array synthesis for image and video applications 119 1 Introduction 119 2 A design script 120 3 A real-life video application 121 4 Deriving the initial description 123 5 Re-indexing transformations 124 6 Localizing transformations 125 7 Space-time mapping 134 8 Conclusion 140 References 140 Contents vii 7 Memory and data-path mapping for image and video applications 143 1 Introduction 143 2 High-level memory management 146 3 High-level data-path mapping 156 4 Conclusion 162 References 162 8 Automatic synthesis for mechatronic applications 167 1 Introduction 167 2 System overview 168 3 Application domain and target architecture 172 4 Behavioral synthesis transformations 176 5 Structural synthesis 183 6 Results 187 7 Conclusion 189 References 189 9 Synthesis for control-flow-dominated machines 191 1 Introduction 191 2 Integration with existing design environments 193 3 An overview of AMICAL 197 4 Mixing manual and automatic design 202 5 A design example 204 6 Conclusion 209 References 209 10 Controller synthesis and verification 211 1 Introduction 211 2 Architecture selection 213 3 Architecture implementation 218 4 Formal verification of finite state machines 223 5 Verification of implementation 228 6 Conclusion 230 References 230 viii Application-driven architecture synthesis Index 233 ____________________________________________________________________ PREFACE The main intention of this book is to give an impression of the way current research in high-level and behavioral synthesis for real-time architectures is going. The focus lies especially on domains where application-specific VLSI solutions are attractive, such as significant parts of audio, telecom, instrumentation, speech, robotics, medical and automotive processing, image and video processing, TV, multimedia, radar, and sonar processing. The material in this book is based on work in the context of two research projects, Ascis (Architecture Synthesis for Complex Integrated Systems) and Nana (Novel parallel Algorithms for New real-time Architectures), both spon- sored by the Esprit program of Directorate XIII of the European Commission. The chapters are partly based on material presented at the final project work- shops, which took place at IMEC in Leuven, Belgium, on the 29th and 30th of April, 1992, marking the completion of three successful years of project coop- eration. Ascis and Nana were among the first of the Esprit Basic Research Actions. These are different from other Esprit projects in two ways: the foreseen indus- trial application of the results may be as far as five to seven years in the future, and some of the financial arrangements make it easier for universities to par- ticipate. For a project to gain Esprit sponsorship, it must have partners from at least two different European countries. Ascis and Nana both met this re- quirement with ease. The partners of the Nana project were: Delft University of Technology, the Netherlands; 'Ecole Normale Sup'erieure de Lyon (ENSL), France; Inter-university Micro-Electronic Center (IMEC), Leuven, Belgium; IRISA, Rennes, France; and Katholieke Universiteit Leuven, Belgium. The Ascis partners were: Eindhoven University of Technology, Eindhoven, The Netherlands; IMEC, Leuven, Belgium; INPG/TIM3, Grenoble, France; Tech- nical University of Darmstadt, Darmstadt, Germany; Technical University of Denmark, Lyngby, Denmark; Patras University, Patras, Greece; and Lund Uni- versity, Lund, Sweden. With seven partners in seven countries, Ascis in par- ticular was a good example of a pan-European research project. ix x Application-driven architecture synthesis The goal of the hardware synthesis work within these projects has been to contribute design methodologies and synthesis techniques which address the design trajectory from real behavior down to the RT-level structural specifica- tion of the system. In order to provide complete support for this synthesis trajectory, many design problems must be tackled. We do not claim to cover the complete path, but we do believe we have contributed to the solution of a number of the most crucial problems in the domains of specification and synthe- sis. We therefore expect this book to be of interest in academia; not for detai* *led descriptions of the research results_these have been published elsewhere_but for the overview of the field and a view on the many important but less widely known issues which must be addressed to arrive at industrially relevant results. The Ascis and Nana projects have also been application-driven from the start, and the book is intended to reflect this fact. The real-life applications that have driven the research are described, and the impact of their characteristics on the methodologies is assessed. We therefore believe that the book will be of interest to senior design engineers and CAD managers in industry, who wish either to anticipate the evolution of commercially available design tools over the next few years, or to make use of the concepts in their own research and development. The projects' emphasis on basic research notwithstanding, it must not be for- gotten that Esprit is a program which has the goal to support industry through research. It is therefore important to note that some of the Ascis and Nana results already have generated interest from European CAD and systems in- dustry. The continued research by the partners, some of it in the context of other Esprit projects, obviously also benefits from the results described in this book. In addition, a follow-up project for Nana (Nana-2) has been running for more than a year, and a proposal for an Ascis follow-up is being prepared. It has been a pleasure for us to work within the projects. The coordination of the work has meant many hours on the phone, in airplanes and airports, and behind computer keyboards. However, we consider ourselves amply rewarded: in addition to learning many new things about behavioral synthesis and related issues, we have also developed close connections with excellent people at each of the partner sites. Moreover, the pan-European aspect has allowed us to come in closer contact with research groups with a different background and "research culture," which has led to very enriching cross-fertilization. Preface xi We would like to use this opportunity to thank the many people who have helped make these projects successful, and to express our appreciation of their contributions: | The main authors of the chapters of this book, who were among the most active participants in the synthesis-related technical work within the projects. | The members of the Scientific Advisory Boards for the projects, whose di- rection and high-level steering has been an important contribution to their success and indirectly to the results in this book: Prof. Bernard Courtois, Prof. Hugo De Man, Prof. Patrick Dewilde, Prof. Jochen Jess, Prof. Man- fred Glesner, Prof. Costas Goutis, Prof. Ole Olesen, Prof. Lars Philipson, Prof. Patrice Quinton, Prof. Yves Robert, and Prof. Joos Vandewalle. | Our Project Officer at the European Commission, Dr. Klaus W"olcken, for his support and enthusiasm. | Our technical and administrative coordination staff at IMEC, for their support with the financial and practical details of project management that researchers are typically hopelessly inept at: Patrick Pype, Joost Deseure, and Annemie Stas. | Research associates in many countries, who contributed to the progress of these projects; in particular, we wish to mention Per Andersson, Florin Bal- asa, Abdelhamid Benaini, Henri-Pierre Charles, Gjalt De Jong, Ed Depret- tere, Michael Held, J"urgen Herpel, Thomas Hollstein, Holger J"urgs, Jian- Jin Li, Shen Li-Sheng, Fang Longsen, Christophe Mauras, Serge Miguet, Henrik Pallisgaard, Wim Philipsen, Yannick Saouter, St'ephane Ub'eda, Alle-Jan van der Veen, Sabine Van Huffel, Steven Van Leemput, Ingrid Verbauwhede, and Claus Vielhauer. | Last but not least: Jan Rosseel, whose LaTEX expertise proved invaluable in the production of this book. We finally hope that the reader will find the book useful and enjoyable, and that the results presented will contribute to the continued progress of the field of high-level and behavioral synthesis. Leuven, Belgium Francky Catthoor Santa Monica, California Lars Svensson -------------------------------------ORDER FORM------------------------------ Ref: ftpser Please send me: Application-Driven Architecture Synthesis, Edited by Catthoor/Svensson _____copy(ies) HB, ISBN 0-7923-9355-4, $ 92.00, Dfl 190.00 Payment enclosed to the amount of ___________________________ * Please invoice me * Please charge my credit card Name of Card Holder: ______________________________________ Card. no.: ________________________________________________ Expiry Date:______________________________________________ Am. Ex.* Visa* Diners Club* Mastercard* Delivery address: Name: ___________________________________________________________________ Address: ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ Date:________________ Signature:_______________________________ To be sent to: Outside North America In USA and Canada KLUWER ACADEMIC PUBLISHERS GROUP KLUWER ACADEMIC PUBLISHERS Order Dept. Order Dept P.O. Box 322 101 Philip Drive 3300 AH Dordrecht, The Netherlands Norwell, 02016 MA Tel: +31-78-524400 Tel: 617-871-6600 Fax +31-78-524474. Fax: 617-871-6528 email: vanderlinden@wkap.nl email: kluwer@world.std.com Orders from individuals accompanied by payment or authorization to charge a credit card account will ensure prompt delivery. Postage and handling charges will be absorbed by the Publisher on all such orders. Payment will be accepted in any convertible currency. Please check the rate of exchange at your bank. For sales within the Netherlands please add 6% VAT (BTW). Prices are subject to change without notice. * Delete those that do not apply.