硬件软件结合开发课程课件（英文版）ece587_11_06_12.pdf

11/06/20122012 Illinois Institute of Technology© ECE 587 – Hardware/Software Co-Design Lecture 22 Resource Optimization Professor Jia Wang Department of Electrical and Computer Engineering Illinois Institute of Technology November 6, 2012 ECE 587 – Hardware/Software Co-DesignFall 20121/21 Reading Assignment ?This lecture: 6.3, 6.4, 6.5 ?Next lecture: 6.6, 6.7, 6.8 ECE 587 – Hardware/Software Co-DesignFall 20122/21 Outline Estimation and Optimization Register Sharing Functional Unit Sharing ECE 587 – Hardware/Software Co-DesignFall 20123/21 The FSMD Model (Gajski et al.) ECE 587 – Hardware/Software Co-DesignFall 20124/21 Estimating Resource Usage (Gajski et al.) ?Resource usage can be estimated via usage tables ? Faster than performing the actual allocation/binding ? Can be used to obtain the initial allocation ?The least number of registers is directly seen from the table. ?It is not necessary to have one functional unit for each type of operation, e.g. use an adder/subtractor for both + and -. ECE 587 – Hardware/Software Co-DesignFall 20125/21 Estimating Interconnects (Gajski et al.) ?Use the connectivity table ?Need 14 input and 9 output connections ?Can be implemented as buses/mux’s ECE 587 – Hardware/Software Co-DesignFall 20126/21 Optimization Ideas ?Allow multiple variables to share the same register ? If their lifetimes do not overlap ? Use register fi le/scratch-pad memory to save connections from/to registers ? If they do not need to be used at the same time ?Share the same functional unit for multiple operations ? Across diff erent cycles ?Group connections into buses ECE 587 – Hardware/Software Co-DesignFall 20127/21 Outline Estimation and Optimization Register Sharing Functional Unit Sharing ECE 587 – Hardware/Software Co-DesignFall 20128/21 Register Sharing ?We assume any variable is only written once. ? Multiple writes to the same variable are resolved by renaming the variable for each write. ?Variable lifetime: set of states where the variable is alive ? Write state: the state after it is assigned a new value ? Read state: the states it is used on certain RHS’ ? All states between the write and the last read state ?Group variables with non-overlapping lifetimes and bind each group to a single register ? Try to have as few registers as possible ?There may exist many ways to group variables into the minimum number of groups. ? Break the tie by considering a second design metric ? e.g. the connectivity cost measured as number of selector inputs (mux’s to registers) ECE 587 – Hardware/Software Co-DesignFall 20129/21 Variable Binding and Connectivity Cost (Gajski et al.) ?The register can be shared at both input and output to reduce connectivity cost. ECE 587 – Hardware/Software Co-DesignFall 201210/21 Connectivity Cost Optimization via Compatibility Graph (Gajski et al.) ECE 587 – Hardware/Software Co-DesignFall 201211/21 Grouping Variables in Compatibility Graph (Gajski et al.) ?Prefer to merge nodes with high gain ECE 587 – Hardware/Software Co-DesignFall 201212/21 Final Variable Bindings (Gajski et al.) ?Prefer to merge nodes with high gains ECE 587 – Hardware/Software Co-DesignFall 201213/21 Datapath after Register Sharing (Gajski et al.) ?Assume a function unit is available for each type of operation ?Further savings on interconnects can be achieved via functional unit sharing. ECE 587 – Hardware/Software Co-DesignFall 201214/21 Outline Estimation and Optimization Register Sharing Functional Unit Sharing ECE 587 – Hardware/Software Co-DesignFall 201215/21 Functional Unit Sharing ?Minimize number of functional units in datapath ? Within any given state, a datapath will not perform every operation. ? Similar operations can be grouped into a single multifunction unit if they are active at diff erent states ?Increase unit utilizations ?Usually it’s not helpful to group dissimilar operations as they demand structurally diff erent designs. ECE 587 – Hardware/Software Co-DesignFall 201216/21 Functional Unit Sharing Gain (Gajski et al.) ?Note the extra selectors required for functional unit sharing ?The sharing would be advantageous if the cost of an adder/subtractor and two selectors is less than the cost of a separate adder and subtractor. ECE 587 – Hardware/Software Co-DesignFall 201217/21 Functional Unit Sharing via Compatibility Graph (Gajski et al.) ?Now the edge weights represent number of common sources and number of common destinations. ? Note that we count common registers instead of common variables. ECE 587 – Hardware/Software Co-DesignFall 201218/21 Functional Unit Merging (Gajski et al.) ?Prefer to merge nodes with similar structures and high gains ECE 587 – Hardware/Software Co-DesignFall 201219/21 Datapath after Register and Functional Unit Sharing (Gajski et al.) ?Only 7 selector inputs are needed. ECE 587 – Hardware/Software Co-DesignFall 201220/21 Summary ?Estimations can be made using the FSMD model ?Allocations and bindings are applied to the FSMD model state-by-state, and furth。