Average Interconnection Length Estimation
- 77 Downloads
This chapter presents models and algorithms for accurately estimating the total interconnect length for both random and optimized placements. The algorithms developed in the next chapter for accurately estimating interconnect area require a good estimate of the final total interconnect length. The final total interconnect length is determined by the macro/custom cell placement algorithm which was presented in the previous chapter. This placement algorithm was based on the simulated annealing algorithm. A characteristic feature of simulated annealing is long computation times. Hence the possibility of executing the placement algorithm twice, once for ascertaining the final total interconnect length and the second for obtaining the final placement using the interconnect-area estimator, is unreasonable.
KeywordsSimulated Annealing Random Placement Distinct Object Rightmost Column Placement Algorithm
Unable to display preview. Download preview PDF.
- 1.S. Goto and E. Kuh, “An Approach to the Two-Dimensional Placement Problem in Circuit Layout,” (1978).Google Scholar
- 2.E. N. Gilbert, “Random Minimal Trees,” (1965).Google Scholar
- 1.W. E. Donath, “Statistical Properties of the Placement of a Graph.” (1968).Google Scholar
- 2.I. Sutherland and D. Oestreicher, “How Big Should a Printed Circuit Board Be?,” (1973).Google Scholar
- 3.W. E. Donath, “Placement and Average Interconnect Lengths of Computer Logic,” (1979).Google Scholar
- 4.B. Landman and R. Russo, “On a Pin Versus Block Relationship for Partitions of Logic Graphs,” (1971).Google Scholar