High Level Synthesis of Pipelined Datapaths

by Arató; , Pé; ter; Visegrá; dy, Tamá; s; Jankovits, Istvá; n

• ISBN13: 9780471495826
• ISBN10: 0471495824
• Edition: 1st
• Format: Hardcover
• Copyright: 2001-03-16
• Publisher: WILEY

Summary

The CAD tool PIPE has been developed in response to the increased speed requirement and complexity of ASIC executable tasks. High level synthesis offers more complex ASIC design solutions, now emerging in academic and industrial design environments. In this timely resource, the applicability of the PIPE tool is considered in the context of the field towards hardware / software co--design and system level synthesis. * Increasing interest in high-level logic synthesis as designs with 200 million transistors on a single chip become commonplace * Step-by-step tutorial in the CAD tool "PIPE", illustrating the applications potential, including the advantages, drawbacks and benchmark results * Supplementary CD-ROM including synthesis subroutines and benchmarks Professional hardware engineers and researchers who are familiar with high level synthesis or related topics would find this to be a valuable reference resource. Also, MSc and PhD students studying or researching high level synthesis or related topics could use the book as a tutorial text to accompany existing works on this rapidly evolving topic.

Author Biography

Péter Arató is the author of High Level Synthesis of Pipelined Datapaths, published by Wiley.

Table of Contents

Preface	ix
Introduction	1	(4)
The Elementary Operation Graph (EOG)	5	(2)
Reducing the restarting period	7	(16)
Inserting buffers	7	(5)
Applying multiple copies of operations	12	(3)
Combining the methods	15	(3)
Symbolic representation of recursive loops	18	(1)
Handling of conditional branches	19	(4)
Synchronization	23	(8)
Examples for applying the algorithms RESTART and SYNC	31	(8)
Scheduling as arrangement of synchronizing delay effects	39	(6)
Allocation	45	(12)
Covering non-concurrent operations	45	(7)
Topological cover of operations	52	(5)
Combinatorial and asynchronous operations	57	(6)
Multiple-process recursive loops	63	(14)
Pipelined utilization of recursive loops	64	(3)
Loop scheduling	67	(1)
Classification of recursive problems	68	(3)
Finite loop depth, variable number of iterations	68	(1)
Finite loop depth, constant number of iterations	69	(2)
Infinite loop depth	71	(1)
External synchronization	71	(6)
Control principles	77	(8)
Centralized control path	77	(4)
Distributed control path	81	(4)
Scheduling methods	85	(22)
Stages of scheduling and allocation	86	(2)
Initial allocation	88	(3)
Initial approximation of the optimal solution	91	(1)
Scheduling principles	92	(2)
Scheduling using Integer Linear Programming	94	(3)
List scheduling	97	(3)
General list scheduling	98	(1)
List scheduling under hardware constraint	98	(2)
Force-directed scheduling	100	(4)
Special problems of conditional execution	104	(3)
Examples for comparison of the scheduling algorithms	107	(28)
ILP solution inequalities	107	(6)
List scheduling solutions	113	(2)
List scheduling under hardware constraint	115	(1)
Force-directed solutions	115	(20)
Non-pipeline solution based on ti	116	(6)
Pipeline solution based on ti	122	(8)
Pipeline solution based on qi	130	(5)
The design tool PIPE	135	(4)
Usage	136	(1)
Input	137	(1)
Output	138	(1)
Effective graph generation	139	(10)
Binary structures	141	(1)
Linear structures	142	(1)
Transitions between binary and linear structures	143	(1)
Fixed-width binary structures	143	(2)
Capacity calculation for intermediate structures	145	(2)
Restrictions	147	(2)
System-level synthesis principles	149	(20)
Partitioning	151	(2)
Construction algorithms	151	(1)
Improvement algorithms	152	(1)
Clustering	153	(1)
Software allocation	154	(1)
Multiple-Context High-Level Synthesis	154	(3)
Transfer model of multiple-context environments	157	(6)
Multiple-context data-flow graphs	159	(4)
Multiple-context HLS design process	163	(6)
Solved problems	169	(68)
Problems	169	(11)
Solutions	180	(17)
Benchmark problems solved by tool PIPE	197	(40)
Further reading	237	(4)
Further reading in system-level synthesis	237	(2)
Further reading in methodology	239	(1)
Further reading in software performance optimization	239	(1)
Further reading in processor realizations	239	(2)
Glossary	241	(4)
References	245	(4)
Index	249