- •Contents
- •1 Introduction
- •1.1 Objectives
- •1.2 Overview
- •2 Background
- •2.1 Digital Design for DSP Engineers
- •2.1.2 The Field-Programmable Gate Array
- •2.1.3 Arithmetic on FPGAs
- •2.2 DSP for Digital Designers
- •2.3 Computation Graphs
- •2.4 The Multiple Word-Length Paradigm
- •2.5 Summary
- •3 Peak Value Estimation
- •3.1 Analytic Peak Estimation
- •3.1.1 Linear Time-Invariant Systems
- •3.1.2 Data-range Propagation
- •3.2 Simulation-based Peak Estimation
- •3.3 Hybrid Techniques
- •3.4 Summary
- •4 Word-Length Optimization
- •4.1 Error Estimation
- •4.1.1 Word-Length Propagation and Conditioning
- •4.1.2 Linear Time-Invariant Systems
- •4.1.3 Extending to Nonlinear Systems
- •4.2 Area Models
- •4.3.1 Convexity and Monotonicity
- •4.4 Optimization Strategy 1: Heuristic Search
- •4.5 Optimization Strategy 2: Optimum Solutions
- •4.5.1 Word-Length Bounds
- •4.5.2 Adders
- •4.5.3 Forks
- •4.5.4 Gains and Delays
- •4.5.5 MILP Summary
- •4.6 Some Results
- •4.6.1 Linear Time-Invariant Systems
- •4.6.2 Nonlinear Systems
- •4.6.3 Limit-cycles in Multiple Word-Length Implementations
- •4.7 Summary
- •5 Saturation Arithmetic
- •5.1 Overview
- •5.2 Saturation Arithmetic Overheads
- •5.3 Preliminaries
- •5.4 Noise Model
- •5.4.1 Conditioning an Annotated Computation Graph
- •5.4.2 The Saturated Gaussian Distribution
- •5.4.3 Addition of Saturated Gaussians
- •5.4.4 Error Propagation
- •5.4.5 Reducing Bound Slackness
- •5.4.6 Error estimation results
- •5.5 Combined Optimization
- •5.6 Results and Discussion
- •5.6.1 Area Results
- •5.6.2 Clock frequency results
- •5.7 Summary
- •6 Scheduling and Resource Binding
- •6.1 Overview
- •6.2 Motivation and Problem Formulation
- •6.3 Optimum Solutions
- •6.3.1 Resources, Instances and Control Steps
- •6.3.2 ILP Formulation
- •6.4 A Heuristic Approach
- •6.4.1 Overview
- •6.4.2 Word-Length Compatibility Graph
- •6.4.3 Resource Bounds
- •6.4.4 Latency Bounds
- •6.4.5 Scheduling with Incomplete Word-Length Information
- •6.4.6 Combined Binding and Word-Length Selection
- •6.5 Some Results
- •6.6 Summary
- •7 Conclusion
- •7.1 Summary
- •7.2 Future Work
- •A.1 Sets and functions
- •A.2 Vectors and Matrices
- •A.3 Graphs
- •A.4 Miscellaneous
- •A.5 Pseudo-Code
- •References
- •Index
6.3 Optimum Solutions |
121 |
Consider performing ASAP and ALAP scheduling of the operations, using a latency = min for all operations. Let asap(v) denote the resulting ASAP control step for each operation v V . Similarly let alap(v, λ) denote the ALAP control step for each operation v V given a user-specified latency bound of λ and under the same operation latencies.
Each operation v V , executing on resource type r R(v), can only start its execution during one of the time steps in the set T (v, r) (6.13).
T (v, r) = {t N{0} : t ≥ asap(v) t ≤ alap(v, λ)−L(r)+ min(v)} (6.13)
It is useful to enumerate all possible start times T (v) for each operation v V , according to (6.14), and indeed the complete set of time-steps T (6.15).
T (v) = {t|r R(v) : t T (v, r)} |
(6.14) |
T = {t|v V : t T (v)} |
(6.15) |
6.3.2 ILP Formulation
Extending the notation used by Landwehr, et al. [LMD94], the ILP may be formulated as follows. Let bi,r define a Boolean variable with bi,r = 1 i instance number i of resource type r has at least one operation bound to it. This allows the objective function to be formulated in linear form (6.16).
|
|
I(r) |
|
|
|
|
|
Minimize |
cost(r) |
bi,r |
(6.16) |
r R |
|
i=1 |
|
In order to introduce the constraints, let xv,t,i,r be defined as in (6.17).
1, if operation v is scheduled at time-step t on the
xv,t,i,r = ith instance of resource type r (6.17)0, otherwise
The minimization is performed subject to three types of constraint. The first are the binding constraints, to ensure that each operation is executed on exactly one instance (6.18). The second are the resource constraints, to ensure that no resource instance is executing more than one operation at a time (6.19). The final set are the precedence constraints, to ensure that all operations obey the dependencies in the sequencing graph (6.20).
|
I(r) |
|
v V, |
|
|
xv,t,i,r = 1 |
(6.18) |
r R(v) i=1 t T (v,r)