System Synthesis with VHDL System Synthesis with VHDL Edited by Petru EIes Timisoara Technical University Krzysztof Kuchcinski Linkoping University and Zebo Peng Linkoping University Springer-Science+Business Media, B.V. A c.l.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-1-4419-5024-6 ISBN 978-1-4757-2789-0 (eBook) DOI 10.1007/978-1-4757-2789-0 Printed on acid-free paper All Rights Reserved © 1998 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998. Softcover reprint ofthe hardcover 1st edition 1998 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. CONTENTS Preface xi PART I PRELIMINARIES 1 Introduction ................................................ 3 1.1 Design Specification and VHDL ........................... 3 1.1.1 Hardware Description Languages ..................... 5 1.1.2 VHDL .......................................... 6 1.1.3 Design Representations ............................. 7 1.2 Synthesis .............................................. 7 1.2.1 System Synthesis ................................. 8 1.2.2 Optimization .................................... 11 1.2.3 Related Issues ................................... 12 1.3 Transformational Approach .............................. 13 1.4 Current Trends ........................................ 14 1.5 Outline of the Book .................................... 17 2 VHDL ................................................... 21 2.1 The Basic Constructs ................................... 22 2.1.1 Entity Dec1aration ................................ 23 2.1.2 Architectures .................................... 24 2.1.3 Packages ....................................... 28 2.2 Data Types, Objects, and Expressions ...................... 30 2.2.1 Data types ...................................... 30 2.2.2 Objects ........................................ 32 2.2.3 Expressions ..................................... 33 2.3 Processes and Sequential Statements ....................... 35 VI CONTENTS 2.3.1 Process Statement ................................ 35 2.3.2 Variable Assignment Statement ..................... 36 2.3.3 If Statement .................................... 36 2.3.4 Case Statement .................................. 37 2.3.5 Loop Statement .................................. 38 2.3.6 Next and Exit Statements .......................... 39 2.3.7 Assertion and Report Statements .................... 39 2.4 The Simulation Mechanism .............................. 40 2.4.1 The Simulation Cyc1e ............................. 42 2.4.2 Delta Delay and Delta Cyc1e ....................... 43 2.4.3 Postponed Processes .............................. 45 2.4.4 Signal Assignment Statement ....................... 45 2.4.5 Wait Statement .................................. 49 2.4.6 Resolved Signals and Resolution Functions ............ 51 2.5 Subprograms ......................................... 53 2.5.1 Functions ...................................... 54 2.5.2 Procedures ..................................... 55 2.5.3 Overloading .................................... 55 2.6 Concurrent Statements .................................. 55 2.6.1 Concurrent Signal Assignment Statement ............. 56 2.6.2 Concurrent Procedure Call Statement ................ 58 2.6.3 Concurrent Assertion Statement ..................... 59 2.7 VHDL for System Synthesis ............................. 60 3 High-Level Synthesis ....................................... 63 3.1 Introduction .......................................... 63 3.1.1 The High-Level Synthesis Tasks .................... 65 3.l.2 Basic Synthesis Techniques ........................ 66 3.2 Scheduling ........................................... 68 3.2.1 List Scheduling .................................. 72 3.2.2 Force-Directed Scheduling ......................... 73 3.2.3 Transforrnation-Based Scheduling ................... 77 3.2.4 Advanced Scheduling Topics ....................... 78 3.3 Data Path Allocation and Binding ......................... 80 3.3.1 Integer Linear Programming ....................... 82 3.3.2 Clique Partitioning and Graph Colouring .............. 83 3.3.3 Left-Edge Algorithm ............................. 85 3.4 Controller Synthesis .................................... 87 3.4.1 Controller-Style Selection ......................... 89 3.4.2 Controller Generation ............................. 93 3.4.3 Controller Implementation ......................... 94 CONTENTS VII 4 System-Level Synthesis ..................................... 99 4.1 The System-Level Synthesis Tasks ....................... 101 4.2 Allocation of System Components ........................ 103 4.3 System Partitioning ................................... 104 4.3.1 Granularity .................................... 104 4.3.2 Abstract Representation .......................... 105 4.3.3 Objective ...................................... 106 4.3.4 Aigorithm ..................................... 109 4.4 Partitioning Aigorithms ................................ 110 4.4.1 Hierarchical Clustering ........................... 111 4.4.2 Kemighan-Lin (KL) Aigorithm .................... 114 4.4.3 Other Iterative Partitioning Approaches .............. 119 4.5 Communication Synthesis .............................. 119 4.5.1 Channel Binding ................................ 120 4.5.2 Communication Refinement ....................... 121 4.5.3 Interface Generation ............................. 123 4.6 Hardware/Software Co-Design .......................... 124 4.7 Synthesis Approaches at the System Level ................. 125 4.7.1 Integer Programming Based Approaches ............. 126 4.7.2 Distributed Real-Time Systems .................... 127 4.7.3 SpecSyn, a System Design Environment ............. 129 4.7.4 The Vu1can Co-Synthesis System ................... 130 4.7.5 The Cosyma Co-Synthesis System .................. 131 4.7.6 The COSMOS Co-Design Environment .............. 132 4.7.7 The Chinook Co-synthesis System .................. 133 5 Optimization Heuristics .................................... 137 5.1 Introduction ......................................... 137 5.1.1 CombinatoriaIOptimization ....................... 137 5.1.2 Branch-and-Bound Technique ..................... 138 5.2 Heuristics ........................................... 141 5.2.1 Classification .................................. 141 5.2.2 Evaluation of Heuristics .......................... 143 5.2.3 Neighborhood Search ............................ 144 5.3 Simulated Annealing .................................. 146 5.3.1 Introduction and the Algorithm .................... 146 5.3.2 Generic Decisions ............................... 148 5.3.3 Problem-Specific Decisions ....................... 150 5.3.4 Discussion ..................................... 152 5.4 Tabu Search ......................................... 152 Vlll CONTENTS 5.4.1 The Basic Scheme .............................. 153 5.4.2 Tabus and Tabu Tenure .......................... 154 5.4.3 Aspiration Criteria .............................. 155 5.4.4 Diversification and Intensification .................. 156 5.4.5 Neighborhood Selection Techniques ................ 157 5.4.6 Stopping Conditions ............................. 157 5.4.7 Discussion ..................................... 157 5.5 Genetic Algorithms ................................... 158 5.5.1 Natural Selection and the Basic Algorithm ........... 158 5.5.2 Encoding ...................................... 159 5.5.3 Fitness Function and Selection ..................... 161 5.5.4 Genetic Operators ............................... 161 5.5.5 Selection of Control Parameters .................... 162 5.5.6 Discussion ..................................... 163 PART 11 TRANSFORMAT IONAL APPROACH 165 6 Transformational Design Basics ............................. 167 6.1 Design Representation ................................. 167 6.1.1 Partial Ordering ................................ 170 6.1.2 Basic Definitions ............................... 171 6.1.3 Semantics Definition ............................ 177 6.1.4 Timing ....................................... 181 6.2 Mapping VHDL Specifications to ETPN .................. 182 6.2.1 Compiling VHDL to ETPN ....................... 182 6.2.2 ETPN Representation of Behavioral VHDL .......... 185 6.2.3 Representation of VHDL Control Structures .......... 186 6.3 Hardware Implementation of ETPN ...................... 190 6.3.1 Data Path Implementation ........................ 190 6.3.2 Petri net Implementation ......................... 191 6.4 Basic Transformations ................................. 194 6.4.1 Compiler Oriented Transformations ................. 195 6.4.2 Operation Scheduling Oriented Transformations ....... 202 6.4.3 Data Path Oriented Transformations ................ 209 6.4.4 Control Oriented Transformations .................. 210 6.5 Pipeline Transformations ............................... 212 6.5.1 Analysis and synthesis methods .................... 214 6.5.2 Pipeline transformations in ETPN .................. 218 6.6 Selection of Transformations ............................ 224 6.6.1 Problem-Specific Selection Scheme ................. 225 6.6.2 General Heuristics .............................. 230 CONTENTS ix 7 Synthesis of Advanced Features .............................. 233 7.1 Synthesis of Subprograms .............................. 233 7.1.1 Implementation Alternatives ....................... 235 7.1.2 Representation and Transformation ................. 237 7.1.3 Processes, Signals and Subprogram Synthesis ......... 240 7.2 Synthesis Strategies for Interacting VHDL Processes ......... 243 7.2.1 SimulationiSynthesis Correspondence ............... 244 7.2.2 Implementation Alternatives ....................... 246 7.3 Synthesis with Signal Levellnteraction .................... 248 7.3.1 Representation of Signals and Wait Statements ........ 248 7.3.2 Synthesis of Several Control Units .................. 250 7.3.3 Synthesis of a Single Control Unit .................. 251 7.4 Synthesis with System Levellnteraction ................... 253 7.4.1 The Designer's View ............................ 255 7.4.2 The Simulation Model ........................... 257 7.4.3 A Synthesis Strategy ............................. 258 7.4.4 Discussion ..................................... 260 7.5 Specification and Synthesis with Timing Requirements ....... 261 7.5.1 Specification of Timing Constraints in VHDL ......... 263 7.5.2 Synthesis Considering Timing Constraints ............ 272 8 Hardware/Software Partitioning .............................. 275 8.1 The Partitioning Strategy ............................... 276 8.2 Extraction of Basic Regions ............................. 278 8.3 The Process Graph .................................... 280 8.4 Process Graph Partitioning .............................. 283 8.4.1 The Cost Function and the Constraints ............... 283 8.4.2 Iterative Improvement Heuristics ................... 285 8.5 Partitioning Examples ................................. 295 PART III ADVANCED ISSUES 301 9 Test Synthesis ............................................ 303 9.1 Digital System Testing ................................. 306 9.1.1 Test Pattern Generation .......................... 306 9.1.2 Design for Testability ............................ 308 9.2 High-Level Test Synthesis .............................. 311 9.2.1 Testability Analysis ............................. 312 9.2.2 Testability Improvement Transformations ............ 321 x CONTENTS 10 Low-Power Synthesis ...................................... 329 10.1 Sources of Power Consumption and Its Reduction ........... 330 10.2 Power Estimation ..................................... 332 10.3 High-Level Power Optimization ......................... 335 10.3.1 Estimation ..................................... 336 10.3.2 Optimization ................................... 338 10.3.3 High-level Synthesis Transformations for Low Power .. 338 10.3.4 Summary of Low Power Transformations ............ 344 10.4 Low-power Synthesis Systems and Algorithms ............. 347 10.4.1 HYPER-LP .................................... 347 10.4.2 Profile-Driven Synthesis System (PDSS) ............ 348 10.4.3 Power-Profiler ................................. 349 10.4.4 Module and Register Allocation and Binding ......... 349 Bibliography 351 INDEX 365 Preface We have witnessed during the last two decades a tremendous growth in the area of design automation for digital circuits and embedded systems. The driving force of this growth is the underlying development in microelectronics technology, wh ich has delivered an exponential increase in computational power and storage capacity. It has been shown that the number of transistors on a single chip has increased ten times every six years and the speed of micropro cessors has increased ten times every eight years. And it is expected that this exponential growth will continue in the near future. Design automation techniques have provided an enabling technology for designing complex integrated circuits and systems. Design methodologies and tools that operate at the physical and logical level are widely available today and extensively used in the industry. More and more recent research activities have therefore been devoted to the design tasks at the behavioral and architec tural level. Many high-level synthesis techniques and systems have been developed in recent years. Embedded systems are usually composed of several interacting components such as custom or application specific processors, ASICs, memory blocks, and the associated communication infrastructure. The development of tools to support the design of such systems requires a further step from high-level synthesis towards a higher abstraction level. The lack of design tools accepting a system-level specification of a complete system, which may include both hardware and software components, is one of the major bottlenecks in the design of embedded systems. Thus, more and more research efforts have been spent on issues related to system-level synthesis.