Tài liệu High-Level Synthesis pptx

High-Level Synthesis

Editors

High-Level Synthesis

From Algorithm to Digital Circuit

Philippe Coussy • Adam Morawiec

Adam Morawiec

European Electronic Chips & Systems

design Initiative (ECSI)

2 av. de Vignate

38610 Grieres

France

[email protected]

ISBN 978-1-4020-8587-1 e-ISBN 978-1-4020-8588-8

Library of Congress Control Number: 2008928131

c 2008 Springer Science + Business Media B.V.

No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by

any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written

permission from the Publisher, with the exception of any material supplied specifically for the purpose

of being entered and executed on a computer system, for exclusive use by the purchaser of the work.

Printed on acid-free paper.

987654321

springer.com

Philippe Coussy

Université Européenne

BP 92116

56321 Lorient Cedex

Centre de Recherche

[email protected]

France

Laboratoire Lab-STICC

de Bretagne - UBS

Cover illustration: Cover design by Martine Piazza, Adam Morawiec and Philippe Coussy

Foreword

High-level synthesis – also called behavioral and architectural-level synthesis –

is a key design technology to realize systems on chip/package of various kinds,

whether single or multi-processors, homogeneous or heterogeneous, for the embed￾ded systems market or not. Actually, as technology progresses and systems become

increasingly complex, the use of high-level abstractions and synthesis methods

becomes more and more a necessity. Indeed, the productivity of designers increases

with the abstraction level, as demonstrated by practices in both the software and

hardware domains. The use of high-level models allows designers with systems,

rather than circuit, background to be productive, thus matching the trend of industry

which is delivering an increasingly larger number of integrated systems as compared

to integrated circuits.

The potentials of high-level synthesis relate to leaving implementation details

to the design algorithms and tools, including the ability to determine the precise

timing of operations, data transfers, and storage. High-level optimization, coupled

with high-level synthesis, can provide designers with the optimal concurrency struc￾ture for a data flow and corresponding technological constraints, thus providing the

balancing act in the trade-off between latency and resource usage. For complex sys￾tems, the design space exploration, i.e., the systematic search for the Pareto-optimal

points, can only be done by automated high-level synthesis and optimization tools.

Nevertheless, high-level synthesis has been showing a long gestation period.

Despite early results in the 1980s, it is still not common practice in hardware design.

The slow acceptance-rate of this important technology has been attributed to a few

factors such as designers’ desire to micromanage integrated systems by controlling

their internal timing and the lack of a universal standard front-end language. The

former issue is typical of novel technologies: as systems grow in size it will be nec￾essary for designers to show a broader system vision and fewer concerns on internal

timing. In other words, this problem will naturally disappear.

The Babel of high-level modeling languages has been a significant obstacle

to the development of this technology. When high-level synthesis was introduced

in the 1980s, the designer community embraced Verilog and VHDL as specifica￾tion languages, due to their ability to perform efficient simulation. Nevertheless,

v

vi Foreword

such languages were conceived without an intrinsic hardware semantics, making

synthesis more cumbersome.

C-based hardware description languages (CHDLs) surfaced in the 1980s as

well, such as HardwareC and its hardware compiler Hercules. The limitations of

HardwareC and similar CHDLs are rooted in the modification of the C language

semantics to support hardware constructs, thus making each CHDL a different

dialect of C. The introduction of SystemC in the 1990s solved the problem by not

modifying the software programming language (in this case C++) and by introduc￾ing a class library with a well-defined hardware semantics. It is regrettable that the

initial enthusiasm was mitigated by the limited support of high-level synthesis for

SystemC.

The turn of the century was characterized by a renewed interest in CHDLs and

in high-level synthesis from CHDLs. New companies carried the torch of educat￾ing designers with new models and tools for design. Today, there are several offers

in high-level synthesis tools that provide effective solutions in silicon. Moreover,

some of the technical roadblocks to high-level synthesis have been overcome. Syn￾thesis of C-based models with pointers and memory allocators was demonstrated

and patented by Stanford jointly with NEC, thus removing the last hard technical

difficulty to synthesize full C-based models.

At present, the potentials of high-level synthesis are still very good, even though

the designers’ community has not yet converged on a single modeling language

that would lower the entry barrier of tools into the marketplace. This book presents

an excellent collection of contributions addressing different aspects of high-level

synthesis from both industry and academia. This book 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.

EPF Lausanne, 2008 Giovanni De Micheli

Contents

1 User Needs ................................................. 1

Pascal Urard, Joonhwan Yi, Hyukmin Kwon, and Alexandre Gouraud

2 High-Level Synthesis: A Retrospective .......................... 13

Rajesh Gupta and Forrest Brewer

3 Catapult Synthesis: A Practical Introduction to Interactive C

Synthesis .................................................. 29

Thomas Bollaert

4 Algorithmic Synthesis Using PICO ............................. 53

Shail Aditya and Vinod Kathail

5 High-Level SystemC Synthesis with Forte’s Cynthesizer ........... 75

Michael Meredith

6 AutoPilot: A Platform-Based ESL Synthesis System .............. 99

Zhiru Zhang, Yiping Fan, Wei Jiang, Guoling Han, Changqi Yang,

and Jason Cong

7 “All-in-C” Behavioral Synthesis and Verification

with CyberWorkBench ....................................... 113

Kazutoshi Wakabayashi and Benjamin Carrion Schafer

8 Bluespec: A General-Purpose Approach to High-Level Synthesis

Based on Parallel Atomic Transactions ......................... 129

Rishiyur S. Nikhil

9 GAUT: A High-Level Synthesis Tool for DSP Applications ......... 147

Philippe Coussy, Cyrille Chavet, Pierre Bomel, Dominique Heller,

Eric Senn, and Eric Martin

10 User Guided High Level Synthesis ............................. 171

Ivan Aug´e and Fr´ed´eric P´etrot

vii

viii Contents

11 Synthesis of DSP Algorithms from Infinite Precision Specifications . . 197

Christos-Savvas Bouganis and George A. Constantinides

12 High-Level Synthesis of Loops Using the Polyhedral Model ........ 215

Steven Derrien, Sanjay Rajopadhye, Patrice Quinton, and Tanguy Risset

13 Operation Scheduling: Algorithms and Applications .............. 231

Gang Wang, Wenrui Gong, and Ryan Kastner

14 Exploiting Bit-Level Design Techniques in Behavioural Synthesis ... 257

Mar´ıa Carmen Molina, Rafael Ruiz-Sautua, Jos´e Manuel Mend´ıas,

and Rom´an Hermida

15 High-Level Synthesis Algorithms for Power and Temperature

Minimization ............................................... 285

Li Shang, Robert P. Dick, and Niraj K. Jha

Contributors

Shail Aditya

Synfora, Inc., 2465 Latham Street, Suite #300, Mountain View, CA 94040, USA,

[email protected]

Ivan Aug´e

UPMC-LIP6/SoC, Equipe ASIM/LIP6, Universit´ ´ e Pierre et Marie Curie, Paris,

France, [email protected]

Thomas Bollaert

Mentor Graphics, 13/15 rue Jeanne Braconnier, 92360 Meudon-la-Foret, France,

Thomas [email protected]

Pierre Bomel

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

Christos-Savvas Bouganis

Department of Electrical and Electronic Engineering, Imperial College London,

South Kensington Campus, London SW7 2AZ, UK,

[email protected]

Forrest Brewer

Electrical and Computer Engineering, University of California, Santa Barbara, CA

93106-9560, USA, [email protected]

Cyrille Chavet

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

ix

x Contributors

Jason Cong

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA

and

UCLA Computer Science Department, Los Angeles, CA 90095-1596, USA,

[email protected], [email protected]

George A. Constantinides

Department of Electrical and Electronic Engineering, Imperial

College London, South Kensington Campus, London SW7 2AZ, UK,

[email protected]

Philippe Coussy

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

Steven Derrien

Irisa, universit’e de Rennes 1, Campus de beaulieu, 35042 Rennes Cedex, France,

[email protected]

Robert P. Dick

Department of Electrical Engineering and Computer Science, Northwestern

University, Evanston, IL, USA, [email protected]

Yiping Fan

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA, [email protected]

Wenrui Gong

Department of Electrical and Computer Engineering, University of California,

Santa Barbara, CA 93106, USA, [email protected]

Alexandre Gouraud

France Telecom R&D, 38-40 rue du General Leclerc, 92794 Issy Moulineaux

Cedex 9, France, [email protected]

Rajesh Gupta

Computer Science and Engineering, University of California, San Diego, 9500

Gilman Drive, La Jolla, CA 92093-0404, USA, [email protected]

Guoling Han

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA, [email protected]

Dominique Heller

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

Contributors xi

Rom´an Hermida

Facultad de Inform´atica, Universidad Complutense de Madrid, c/Prof. Jos´e Garc´ıa

Santesmases s/n, 28040 Madrid, Spain, [email protected]

Niraj K. Jha

Department of Electrical and Engineering, Princeton University, Princeton, NJ

08544, USA, [email protected]

Wei Jiang

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA, [email protected]

Ryan Kastner

Department of Electrical and Computer Engineering, University of California,

Santa Barbara, CA 93106, USA, [email protected]

Vinod Kathail

Synfora, Inc., 2465 Latham Street, Suite # 300, Mountain View, CA 94040, USA,

[email protected]

Hyukmin Kwon

Samsung Electronics Co., Suwon, Kyunggi Province, South Korea,

[email protected]

Eric Martin

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

Jos´e Manuel Mend´ıas

Facultad de Inform´atica, Universidad Complutense de Madrid, c/Prof. Jos´e Garc´ıa

Santesmases s/n, 28040 Madrid, Spain, [email protected]

Michael Meredith

VP Technical Marketing, Forte Design Systems, San Jose, CA 95112, USA,

[email protected]

Mar´ıa Carmen Molina

Facultad de Inform´atica, Universidad Complutense de Madrid, c/Prof. Jos´e Garc´ıa

Santesmases s/n, 28040 Madrid, Spain, [email protected]

Rishiyur S. Nikhil

Bluespec, Inc., 14 Spring Street, Waltham, MA 02451, USA, [email protected]

Fr´ed´eric P´etrot

INPG-TIMA/SLS, 46 Avenue F´elix Viallet, 38031 Grenoble Cedex, France,

[email protected]

Patrice Quinton

ENS de Cachan, antenne de Bretagne, Campus de Ker Lann, 35 170 Bruz Cedex,

France, [email protected]

xii Contributors

Sanjay Rajopadhye

Department of Computer Science, Colorado State University, 601 S. Howes St.

USC Bldg., Fort Collins, CO 80523-1873, USA, [email protected]

Tanguy Risset

CITI – INSA Lyon, 20 avenue Albert Einstein, 69621, Villeurbanne, France,

[email protected]

Rafael Ruiz-Sautua

Facultad de Inform´atica, Universidad Complutense de Madrid, c/Prof. Jos´e Garc´ıa

Santesmases s/n, 28040 Madrid, Spain, [email protected]

Benjamin Carrion Schafer

EDA R&D Center, Central Research Laboratories, NEC Corp., Kawasaki, Japan,

[email protected]

Eric Senn

European University of Brittany – UBS, Lab-STICC, BP 92116, 56321 Lorient

Cedex, France, [email protected]

Li Shang

Department of Electrical and Computer Engineering, Queen’s University, Kingston,

ON, Canada K7L 3N6, [email protected]

Pascal Urard

STMicroelectronics, Crolles, France, [email protected]

Kazutoshi Wakabayashi

EDA R&D Center, Central Research Laboratories, NEC Corp., Kawasaki, Japan,

[email protected]

Gang Wang

Technology Innovation Architect, Intuit, Inc., 7535 Torrey Santa Fe Road,

San Diego, CA 92129, USA, Gang [email protected]

Changqi Yang

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA, [email protected]

Joonhwan Yi

Samsung Electronics Co., Suwon, Kyunggi Province, South Korea,

[email protected], [email protected]

Zhiru Zhang

AutoESL Design Technolgoies, Inc., 12100 Wilshire Blvd, Los Angeles, CA

90025, USA, [email protected]

List of Web sites

Chapter 2

related to system level design, synthesis and verification. Our recent projects include

the SPARK parallelizing synthesis framework, SATYA verification framework. Ear￾lier work from the laboratory formed the technical basis for the SystemC initiative.

http://mesl.ucsd.edu/

Chapter 3

Catapult Synthesis product information page

The home page for Catapult Synthesis on www.mentor.com, with links to product

datasheets, free software evaluation, technical publications, success stories, testimo￾nials and related ESL product information.

http://www.mentor.com/products/esl/high level synthesis/

Algorithmic C datatypes download page

The Algorithmic C arbitrary-length bit-accurate integer and fixed-point data types

allow designers to easily model bit-accurate behavior in their designs. The data types

were designed to approach the speed of plain C integers. It is no longer necessary to

compromise on bit-accuracy for the sake of speed or to explicitly code fixed-point

behavior using integers in combination with shifts and bit masking.

http://www.mentor.com/products/esl/high level synthesis/ac datatypes

Chapter 4

Synfora, Inc. is the premier provider of PICO family of algorithmic synthesis tools

to design complex application engines for SoCs and FPGAs. Synfora’s technology

helps to reduce design costs, dramatically speed IP development and verification,

xiii

Microelectronic Embedded Systrems Laboratory at UCSD hosts a number of projects

xiv List of Web sites

and reduce time-to-market. For the latest information on Synfora and PICO prod￾ucts, please visit http://www.synfora.com

Chapter 5

More information on Cynthesizer from Forte Design Systems can be found at

http://www.ForteDS.com

Chapter 6

More information on AutoPilotTM from AutoESL Design Technologies can be

found at http://www.autoesl.com and http://cadlab.cs.ucla.edu/soc/

Chapter 7

Home Page for CyberWorkBench from NEC

http://www.cyberworkbench.com

Chapter 8

More information on Bluespec can be found at http://www.bluespec.com

Documentation, training materials, discussion forums, inquiries about Bluespec

SystemVerilog. http://csg.csail.mit.edu/oshd/

Open source hardware designs done by MIT and Nokia in Bluespec SystemVer￾ilog for H.264 decoder (baseline profile), OFDM transmitter and receiver, 802.11a

transmitter, and more.

Chapter 9

GAUT is an open source project at UEB-Lab-STICC. The software for this project

is freely available for download. It is provided with a graphical user interface, a

quick start guide, a user manual and several design examples. GAUT is currently

supported on Linux and Windows. GAUT has already been downloaded more than

200 times by people from industry and academia in 36 different countries. For more

information, please visit:

http://web.univ-ubs.fr/gaut/

List of Web sites xv

Chapter 10

More information can be found on UGH from at UPMC-LIP6/SoC and INPG￾TIMA/SLS at http://www-asim.lip6.fr/recherche/disydent/

This web site contains introduction text, source code and tutorials (through CVS) of

the opensource Dysident framework that includes the UGH HLS tool.

Chapter 11

More information on Chapter 11 can be found at

http://cas.ee.ic.ac.uk/

Chapter 12

More information on MMAlpha can be found at

http://www.irisa.fr/cosi/ALPHA/

Chapter 13

More information Chapter 13 can be found on at

http://www.cse.ucsd.edu/∼ kastner/research/aco/

Chapter 14

More information on Chapter 14 can be found at

http://atc.dacya.ucm.es/

Chapter 15

More information on Chapter 15 can be found at

http://www.princeton.edu/∼jha