SPARK: A Parallelizing Approach to the High-Level Synthesis of Digital Circuits
Rapid advances in microelectronic integration and the advent of Systems-on-Chip have fueled the need for high-level synthesis, i.e., an automated approach to the synthesis of hardware from behavioral descriptions. SPARK: A Parallelizing Approach to the Hi
- PDF / 13,627,181 Bytes
- 241 Pages / 432 x 684 pts Page_size
- 92 Downloads / 175 Views
SPARK: A PARALLELIZING APPROACH TO THE HIGH-LEVEL SYNTHESIS OF DIGITAL CIRCUITS
SUMIT GUPTA Center for Embedded Computer Systems University of California San Diego and Irvine, USA
RAJESH K. GUPTA Department of Computer Science and Engineering University of California San Diego, USA
NIKIL D. DUTT Center for Embedded Computer Systems University of California Irvine, USA
ALEXANDRU NICOLAU Center for Embedded Computer Systems University of California Irvine, USA
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
CD-ROM available only in print edition eBook ISBN: 1-4020-7838-2 Print ISBN: 1-4020-7837-4
©2004 Springer Science + Business Media, Inc. Print ©2004 Kluwer Academic Publishers Boston All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://www.ebooks.kluweronline.com http://www.springeronline.com
This book is dedicated to our families.
Contents Preface Acknowledgments
xix xxiii
I Introduction to High-Level Synthesis
1
1 Introduction 1.1 System-Level Design of Hardware Systems 1.2 Why High-Level Synthesis and Why Now 1.3 Overview of High-Level Synthesis 1.4 Role of Parallelizing Compiler Transformations in HLS 1.5 Our Parallelizing High-Level Synthesis Methodology 1.6 Contributions of this Work 1.7 Book Organization
3 3 5 6 7 8 10 11
2 Survey of Previous Work 2.1 Early Work in High-Level Synthesis 2.2 HLS for Behaviors with Complex Control Flow 2.3 Intermediate Representations in High-Level Synthesis 2.4 Related Work in Compilers 2.5 Use of Loop Transformations in Compilers and High-Level Synthesis 2.6 What is Hindering Adoption of HLS Tools 2.7 Summary
15 15 17 18 19 20 21 22
3 Models and Representations 3.1 Modeling the Problem 3.2 Design Description Modeling 3.2.1 Modeling Data Dependencies 3.2.2 Better Design Visualization by Maintaining Variable Names 3.2.3 Modeling Control Flow 3.2.4 Mapping between Data Flow and Control Flow Graphs 3.2.5 HTGs: A Model for Designs with Complex Control Flow 3.2.6 Capturing the Complete Design Description
23 23 23 24 25 26 28 29 33
viii
CONTENTS 3.3
3.4
3.5 3.6
3.7
II
Modeling Hardware Resources, Timing and Data Types 3.3.1 Modeling the Data Type Information 3.3.2 Modeling the Hardware Resources 3.3.3 Modeling Clock Cycle Timing 3.3.4 Modeling Operation Chaining Formulation of the Scheduling Problem 3.4.1 Constraints due to Hardware Resource Allocation 3.4.2 Constraints due to Data Dependencies 3.4.3 Resource-Constrained Scheduling 3.4.4 Incorporating Operation Chaining in Scheduling Formulation Modeling Parallelizing Code Motions 3.5.1 Modeling Speculative Code Motions 3.5.2 Modeling Hierarchical Code Motions Scheduling Designs with Control Flow 3.6.1 Notion of Scheduling Steps within Basic Blocks 3.6.2 Formulation of Scheduling Problem with Conditional Constructs 3.
Data Loading...
