You are to evaluate the Tilos gate sizing algorithm for optimizing the delay through a string of inverters.
We want to optimize the gate size of a string of inverters to minimize delay using the TILOS algorithm. Write a program called 'gateopt' which will be called in the following manner:
% gateopt data_file greedy|non_greedy
The 'greedy|non_greedy' keyword should choose between the two different optimization strategies discussed in class. If 'greedy' is specified, only the current gate is sized during optimization. If 'non_greedy' is specified, then both the current gate and supporting gate should be sized.
The contents of an input data file will look like:
initial_inverter_size START_LOADS load_stage_1 load_stage_2 load_stage_3 ... load_stage_i ... load_state_N END_LOADS
The 'load_stage_i' values are the capacitive loads at each point of the inverter chain, NOT counting the gate load of the inverter. The last load is on the output of the last inverter in the chain. Loads are in fF. A typical file might look like:
6 START_LOADS 30 60 10 END_LOADS
This defines an inverter string that has three inverters in it - the first inverter is size 6X driving a 30 fF + inverter ?X load, the second inverter is driving a 60 fF + inverter ?X load, the third and last inverter is driving a 10 fF load.
Your algorithm should assume an initial rising edge into the first inverter when calculating the delay. All inverters in the string (except the first) should be initially set to a 1X size. Your algorithm cannot adjust the size of the first inverter. The maximum size for any inverter is 9X (your program cannot use sizes past 9X).
To calculate the delay through the inverters, use the Rk, Ck, Cg delay model discussed in class. Values are:
Delay: For rising output (TPLH) Rk = 4.1, Ck = 23 For falling output waveforms (TPHL) Rk = 3.1, Ck = 18.9 Effective Gate Capacitance: Falling Input on Gate: Cg = 4.1 Rising Input on Gate: Cg = 2.5
Note that the 'effective' gate capacitance as used by this model is different depending upon whether or not the input waveform is rising or falling. To compute the effective gate capacitance for a Nx size inverter, the values would be:
Nx sized inverter: Falling Input on Gate: load = 4.1 * N fF Rising Input on Gate: load = 2.5 * N fF
Note that the total load which is driven by an inverter in the string will be the load specified in the data file PLUS the gate load of the next inverter in the string.
The delay for a Nx sized gate is calculated:
delay = Rk * Ck + Rk * Cload
where Cload is the output load of the inverter as discussed above. Note that you must use different values for Rk, Ck depending on whether you are calculating TPLH or TPHL. Note that Rk*Ck is the no load delay for the inverter.
Your program should print out the initial delay calculated through the inverter string. After optimization is finished, print out the final delay through the circuit as well as the final size of each inverter in the string.
Any programming language may be used to implement this progam.
Use the submission script "~reese/bin/submit_ee8273_sim2.sh" to submit your work.
Last modified: Thu Sep 10 09:33:28 CDT 1998