• No results found

A versatile data path synthesis approach based on heuristic search

N/A
N/A
Protected

Academic year: 2023

Share "A versatile data path synthesis approach based on heuristic search"

Copied!
12
0
0

Loading.... (view fulltext now)

Full text

(1)

A VERSATILE DATA PATH SYNTHESIS APPROACH BASED ON HEURISTIC SEARCH

by

ALOK KUMAR

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

A Thesis Submitted in partial fulfillment of the requirements for the Degree of

Doctor of Philosophy

[NDIAN INSTITUTE OF TECHNOLOGY, DELHI NEW DELHI 110 016

JANUARY 1993

(2)

To my parents arul Tushar

(3)

Certificate

This is to certify that the thesis entitled "A Versatile Data Path Synthesis Approach based on Heuristic Search", being submitted by Alok Kumar to the Indian Institute of Technology, Delhi, for the award of Degree of Doctor of Philosophy, is a bonafide research work carried out by him under my supervision and guidance. The results obtained in this thesis have not been submitted to any other University or Institute for the award of any other degree or diploma.

Anshul Kumar Professor,

Deptt. of Computer Science and Engineering

Indian Institute of Techdology, New Delhi 110 016

(4)

Acknowledgements

I am greatly indebted to my supervisor Prof. Anshul Kumar for his invaluable technical guidance and moral support during the course of my research. Without his active involvement, it wouldn't have been possible for me to complete this arduous task. Working with him has been a great pleasure and learning experience for me.

I am also thankful to Dr. Balakrishnan for his technical guidance and encouragement. He has been a constant source of inspiration during my research.

I would also like to thank Dr. M. J. Zarabi, Executive Director( VLSI), Semiconductor Complex Ltd., for allowing me to continue my research work. Without his support and constant encouragement, it would have been difficult to complete this work.

I take this opportunity to thank Dr. Shashi Kumar and Dr. Sanjiv Kapoor for their valuable suggestions and comments. I also thank the Chairman and members of the Departmental Review Committee for their help.

I am greatly indebted to Mr. Naseer for providing all sorts of help during the final stages of this work.

I am also thankful to my colleagues at SCL for several technical discussions. I also thank other members of the design department for the administrative support.

My thanks are also due to several friends at IIT Delhi, specially Manoj, Ajay, Rajiv, Anand and other members of the CAD Lab who contributed one way or the other during the preparation of this thesis.

(5)

My parents have constantly encouraged and inspired me throughout my life. Without their blessings, I wouldn't have been successful in my endeavours. I take this opportunity to acknowledge their love, affection and support.

My parents-in-law have also helped a great deal during the course of this research. I express my gratitude for all the help and cooperation extended to me.

Finally, I sincerely accept the fact that this work wouldn't have been possible without the cooperation and innumerable sacrifices made by my wife, Noopur.

kgze.

( A 1_0 V. V.0 •4 -NR).

ii

(6)

Abstract

With the existing sub-micron process technologies, complex digital systems can be realized in a single VLSI chip. The importance of high level design automation tools is now well understood, as they can manage complex designs and reduce the design turnaround time significantly. High level synthesis (HLS) deals with automatic generation of register transfer level structure from behavioral description at algorithmic level.

Starting from the algorithmic level description of the digital system in a hardware description language, a number of sub-tasks are involved in HLS. These include HDL translation, operation scheduling, allocation/binding and control part synthesis. Scheduling, and allocation/binding sub- tasks together are commonly referred to as Data Path Synthesis (DPS). The complexity in HLS stems from the fact that various sub-tasks of high level synthesis are highly interdependent, and several of them have been shown to be NP-hard problems. Thus, only approximate solutions can be produced in polynomial time by exploring a limited portion of the design space.

The three major desirable features of a DPS appropch refer to its ability to integrate sub-tasks, its versatility and flexibility. Level of integration refers to the extent to which various synthesis sub- tasks are integrated. Versatility of a synthesis approach lies in its ability to handle a variety of design constraints, design styles and range of component types. Flexibility refers to its ability to trade-off between the solution quality and the computation complexity. Past approaches to DPS, however, have compromised on these to varying extent.

This thesis presents a novel approach to unify the various sub-tasks of data s nt esis in a common framework. The overall approach, called VITAL, is based on a search algorithm with its three forms - VITAL-NS (no search), VITAL-SS (selective search) and VITAL-EX (extended search). The search algorithms are based on computation of cost estimates which are lower bound on the achievable cost. We present several procedures for cost estimation for a variety of situations

iii

(7)

in DPS. These are described in terms of three generic heuristic functions - HF-ID (heuristic function based on Interval density), HF-SC (heuristic function for Set Covering problem) and HF- AS (heuristic function for Assignment problem).

The new approach is flexible as it can trade-off between the solution quality and computation time.

The choice between VITAL-EX, V1TAL-SS and VITAL-NS is one dimension of this flexibility. The other dimension is the choice in cost function.

The approach is versatile as it can deal with multi-cycle, multifunction, pipelined functional units in a functionally pipelined design. It supports mix of different speed FUs for an operation type, and chaining of operations. Support for conditional constructs and loops is provided. Both bus based and multiplexer based design styles can be handled. All this can be done in a time constrained or a cost constrained environment.

VITAL achieves a high level of integration between various synthesis subtasks. Scheduling and allocation are integrated by considering cost of FUs, registers, buses, multiplexers and interconnections during scheduling. Partial binding in terms of binding of operations to functional units during scheduling can also be carried out to improve the design quality.

The implementation results show the excellent performance of VITAL, thus giving an evidence of its practicality.

iv

(8)

Table of Contents

Acknowledgements Abstract

Table of Contents List of Figures

Chapter 1 Introduction

1.1 Digital Systems : Levels of description and synthesis 1

1.2 High level synthesis 2

1.3 High level synthesis sub-tasks 3

1.4 Survey of previous related work 6

1.4.1 Level of Integration 6

1.4.2 Versatility 9

1.4.2.1 Design constraints 9

1.4.2.2 Design styles and Functional unit types 10

1.4.3 Flexibility 11

1.4.3.1 Scheduling algorithms 12

1.4.3.2 Allocation and Binding algorithms 13

1 5 Limitations of past approaches 15

1.6 The New approach : Motivation and salient features 16

1.7 Thesis layout 17

(9)

Chapter 2 Overall Approach

2.1 Introduction 19

2.2 The VITAL Synthesiser : Inputs, Outputs, Objectives and Constraints 20

2.2.1 CDFG 20

2.2.2 Module library 23

2.2.3 Objective functions and constraints 24 23 Search based approach to Data Path Synthesis 25 2.3.1 Stage I : Scheduling, Allocation and Partial Binding 27 2.3.2 Stage II : Binding and Allocation Refinement 27

2.4 Search Algorithms 28

2.5 Time complexity of VITAL approaches to DPS 34 2.6 • Generalized Heuristic Functions for Lower Bound Computation 36 2.6.1 HF-ID : Heuristic Function based on Interval Density 36 2.6.2 HF-SC : Heuristic Function for Set Covering problem 38 2.6.3 HF-AS : Heuristic Function for Assignment problem 41

2.7 Proof of optimality of VITAL-EX 45

2.8 Conclusions 47

Chapter 3 Scheduling with Allocation and Partial Binding Using Simple Cost Function

3.1 Introduction 49

3.2 Computing Lower Bound on cost for simple case 50

3.3 Lower Bounds for Generalized FUs 60

3.3.1 Multi-cycle FUs 60

3.3.2 Multi-function FUs 62

3.3.3 Pipelined FUs 63

vi

(10)

3.4 Lower Bound computation for Operation Chaining 64 3.5 Lower Bound computation for Functional Pipelining

(One level pipelining) 70

3.6 Lower Bound computation for Functional Pipelining

(Two level pipelining) 73

3.7 Lower Bound computation for Conditional constructs 73

3.8 Lower Bound computation for Loops 80

3.9 Basic Time Constrained Scheduling Algorithm 81

3.9.1 The TCS Algorithm 82

3.9.2 Creating new configurations 83

3.9.3 Time complexity of TCS 85

3.10 Cost Constrained Scheduling 86

3.11 Scheduling with mix of different speed FUs 87

3.12 Conclusions 94

Chapter 4 Scheduling with Allocation and Partial Binding Using Extended Cost Function

4.1 Introduction 95

4.1.1 Multiplexer based Interconnection Structure (MIS) 97 4.1.2 Bus based Interconnection Structure (BIS) 97

4.2 Lower Bound computation for Registers 98

4.2.1 LB computation for registers for scheduled CDFG 101 4.2.2 LB computation for registers during scheduling 106

4.2.2.1 Computation of MLT 106

4.3 Lower Bound computation for Buses 113

4.3.1 Lower Bound computation for scheduled CDFG 116 4.3.2 Lower Bound computation during scheduling 116

vii

(11)

4.3.2.1 Computation of DDTs for single cycle operations 116 4.3.2.2 Computation of DDTs for multi-cycle/pipelined operations 118

4.4 Lower Bound computation for links 120

4.4.1 Lower Bound computation for MIS 121

4.4.1.1 A coarse lower bound 122

4.4.1.2 A refined lower bound 125

4.4.2 Lower Bound computation for BIS 132

4.5 Conclusions 133

Chapter 5 Binding and Allocation Refinement

5.1 Introduction 134

5.2 Subtasks during Stage-II 136

5.3 Algorithm for Lower Bound computation 138

5.3.1 Lower Bound computation for MIS 138

5.3.1.1 Lower Bound computation for M-OFB 138 5.3.1.2 Lower Bound computation for M-VRB 143

5.3.2 Lower Bound computation for BIS 148

5.4 Allocation and Binding Algorithm 151

5.5 Conclusions 155

Chapter 6 Experimental Results

6.1 Introduction 156

6.2 Results of VITAL-NS 158

6.2.1 Facet Example [TsSi 86] 158

6.2.2 Differential Equation Example from HAL [Pa 88a] 162

6.2.2.1 Non-pipelined FUs 162

viii

(12)

6.2.2.2 Pipelined multipliers 164 6.2.3 MAHA Code Sequence Example [PaPi 86] 166

6.2.3.1 Fastest Implementation 166

6.2.3.2 Cheapest implementation 167

6.2.4 Pipelined FIR filter from SEHWA [PaPa 88] 167 6.2.5 Fifth-order digital elliptic wave filter [KuWhKa 85] 172 6.2.5.1 With pipelined multipliers 172

6.2.5.2 With 2-cycle multipliers 178

6.2.6 Code sequence from Simulated Annealing [DeNe 89] • . 178

6.3 Results of VITAL-SS 180

6.3.1 Differential Equation Example 180

6.3.2 Simulated Annealing Code Sequence Example 181

6.3.3 MAHA Example 182

6.4 Simple Cost Function vs Extended Cost Function 183 64.1 Simulated Annealing Code Sequence Example 183

6.4.2 Differential Equation Example 183

6.4.3 Pipelined FIR Filter from SEHWA 184

Chapter 7 Conclusions

7.1 Summary of results and achievements 185

7.2 Directions of future work 186

References

ix

References

Related documents

This is to certify that the thesis entitled "Studies on essential oil based formulations for controlling mosquito larvae" being submitted by Mrs. Mohini Tiwary to the Indian

This is to certify that the thesis entitled "STUDIES ON HYDRAULICS, HEAT AND MASS TRANSFER IN A PACKED COLUMN", being submitted by KAUSHIK MAJUMDER to Indian Institute

This is to certify that the thesis entitled "Studies On Intramolecular Hydrogen Bonding in Small Peptides" being submitted by Abhishek Upadhyay to the Indian Institute

This is to certify that the thesis entitled "Studies on Processing of Metal Matrix composites" by Pawan Kumar Madan submitted to the Indian Institute of Technology,

This is to certify that this thesis entitled "STUDIES ON SURFACE PLASMON RESONANCE BASED FIBER OPTIC SENSORS" being submitted by Anuj Kumar Sharma to the Indian

This is to certify that the thesis entitled "STUDIES ON SURFACE PLASMON RESONANCE BASED FIBER OPTIC SENSORS WITH DIFFERENT PROBE DESIGNS" being submitted by Rajneesh

This is to certify that the thesis entitled, "STUDIES ON SYNTHESIS AND REACTIONS OF CALIX[nJARENES", being submitted by Mr. Lukesh Bajaj to the Department of

This is to certify that thesis entitled "A STUDY OF FUNCTIONAL ELECTRICAL COCHLEAR STIMULATION: AN EXTRACOCHLEAR APPROACH" being submitted by Mr. V.Sridhar to the