[ Chapter start ] [ Previous page ]

# 16.8 References

Page numbers in brackets after a reference indicate its location in the chapter body.

Benkoski, J., and A. J. Strojwas. 1991. “The role of timing verification in layout synthesis.” In Proceedings of the 28th ACM/IEEE Design Automation Conference, San Francisco, pp. 612–619. Tutorial paper with 60 references. This was an introduction to a session on Placement for Performance Optimization containing five other papers on this topic. [ reference location ]

Breuer, M. A. 1977. “Min-cut placement.” Journal of Design Automation and Fault Tolerant Computing, Vol. 1, no. 4, pp. 343–362. [ reference location ]

Chao, A. H., E. M. Nequist, and T. D. Vuong. 1990. “Direct solution of performance constraints during placement.” In Proceedings of the IEEE Custom Integrated Circuits Conference. Describes algorithms used in Cadence Gate Ensemble for performance-driven placement. Wiring estimate is based on single trunk Steiner tree with corrections for bounding rectangle aspect ratio and pin count. [ reference location ]

Cheng, C.-K., and E. S. Kuh. 1984. “Module placement based on resistive network optimization.” IEEE Transactions on Computer-Aided Design for Integrated-Circuits and Systems, Vol. CAD-3, pp. 218–225. [ reference location , reference location ]

Dunlop, A. E., and B. W. Kernighan. 1983. “A placement procedure for polycell VLSI circuits.” In Proceedings of the IEEE International Conference on Computer Aided Design, Santa Clara, CA, September 13–15. Describes the terminal propagation algorithm. [ reference location ]

Goto, S. and T. Matsuda. 1986. “Partitioning, assignment and placement.” In Layout Design and Verification, T. Ohtsuki (Ed.), Vol. 4, pp. 55–97. New York: Elsevier. ISBN 0444878947. TK 7874. L318. [ reference location ]

Hall, K. M. 1970. “An r-dimensional quadratic placement algorithm.” Management Science, Vol. 17, no. 3, pp. 219–229. [ reference location ]

Hanan, M. 1966. “On Steiner's problem with rectilinear distance.” Journal SIAM Applied Mathematics, Vol. 14, no. 2, pp. 255–265. [ reference location ]

Hanan, M., P. K. Wolff Sr., and B. J. Agule. 1973. “Some experimental results on placement techniques.” In Proceedings of the 13th Design Automation Conference. Reference to complete graph wire measure. [ reference location ]

Hartoog, M. R., 1986. “Analysis of placement procedures for VLSI standard cell layout.” In Proceedings of the 23rd Design Automation Conference. [ reference location ]

Hauge, P. S., et al. 1987. “Circuit placement for predictable performance.” In Proceedings of the IEEE International Conference on Computer Aided Design, pp. 88–91. Describes the zero-slack algorithm. See also: Nair, R., C. L. Berman, P. S. Hauge, and E. J. Yoffa, “Generation of performance constraints for layout,” IEEE Transactions on Computer Aided Design, Vol. 8, no. 8, pp. 860–874, August 1989; and Burstein, M. and M. N. Housewife, “Timing influenced layout design,” in Proceedings of the 22nd Design Automation Conference, 1985. Defines required, actual, and slack times. Describes application of timing-driven restrictions to placement using F–M algorithm and hierarchical global routing. [ reference location ]

Hu, T. C., and E. S. Kuh (Eds.). 1983. VLSI Circuit Layout: Theory and Design. New York: IEEE Press. Contains 26 papers divided into six parts; Part 1: Overview; Part II: General; Part III: Wireability, Partitioning and Placement; Part IV: Routing; Part V: Layout Systems; Part VI: Module Generation. ISBN 0879421932. TK7874. V5573. [ reference location ]

Hwang, F. K. 1976. “On Steiner minimal trees with rectilinear distance.” SIAM Journal of Applied Mathematics, Vol. 30, pp. 104–114. See also: Hwang, F. K., “An O(n log n) Algorithm for Suboptimal Rectilinear Steiner Trees,” IEEE Transactions on Circuits and Systems, Vol. CAS-26, no. 1, pp. 75–77, January 1979. Describes an algorithm to improve the rectilinear minimum spanning tree (RMST) approximation to the minimal rectilinear Steiner tree (minimal RST). The approximation is at most 1.5 times longer than the minimal RST, since the RMST is at worst 1.5 times the length of the minimal RST. [ reference location ]

Kirkpatrick, S., C. D. Gerlatt Jr., and M. P. Vecchi. 1983. “Optimization by simulated annealing,” Science, Vol. 220, no. 4598, pp. 671–680. [ reference location ]

Lengauer, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Chichester, England: Wiley. ISBN 0-471-92838-0. TK7874.L36. Contains chapters on circuit layout; optimization problems; graph algorithms; operations research and statistics; combinatorial layout problems; circuit partitioning; placement; assignment; floorplanning; global routing and area routing; detailed routing; and compaction. 484 references. [ reference location ]

Luk, W. K. 1991. “A fast physical constraint generator for timing driven layout.” In Proceedings of the 28th ACM/IEEE Design Automation Conference. Introduction to timing-driven placement and net- and path-based approaches. Describes some different methods to estimate interconnect delay during placement. ISBN 0-89791-395-7. [ reference location ].

Masleid, R. P. 1991. “High-density central I/O circuits for CMOS.” IEEE Journal of Solid-State Circuits, Vol. 26, no. 3, pp. 431–435. An I/O circuit design that reduces the percentage of chip area occupied by I/O circuits from roughly 22 percent to under 3 percent for a 256 I/O chip. Uses IBM C4 technology that allows package connections to be located over chip circuitry. 10 references. [ reference location ]

Ohtsuki, T. (Ed.). 1986. Layout Design and Verification. New York: Elsevier. Includes nine papers on CAD tools and algorithms: "Layout strategy, standardisation, and CAD tools," Ueda, Kasai and Sudo; "Layout compaction," Mylynski and Sung; "Layout verification," Yoshida; "Partitioning, assignment and placement," Goto and Matsuda; "Computational complexity of layout problems," Shing and Hu; "Computational and geometry algorithms," Asano, Sato and Ohtsuki; an excellent survey and tutorial paper by M. Burstein: "Channel routing"; "Maze-running and line-search algorithms" an easily-readable paper on detailed routing by Ohtsuki; and a mathematical paper, "Global routing," by Kuh and Marek-Sadowska. ISBN 0444878947. TK7874. L318. [ reference location ]

Preas, B. T., and P. G. Karger. 1988. “Placement, assignment and floorplanning.” In Physical Design Automation of VLSI Systems, B. T. Preas and M. J. Lorenzetti (Eds.), pp. 87–155. Menlo Park, CA: Benjamin-Cummings. ISBN 0-8053-0412-9. TK7874.P47. [ reference location ]

Sangiovanni-Vincentelli, A. 1986. “Automatic layout of integrated circuits.” In Nato Advanced Study on “Logic Synthesis and Silicon Compilers for VLSI Design”, G. De Micheli, A. Sangiovanni-Vincentelli, and A. Paolo (Eds.). Norwell, MA: Kluwer. ISBN 90-247-2689-1, 90-247-3561-0. TK7874.N338. [ reference location ]

Schweikert, D. G., 1976. “A 2-dimensional placement algorithm for the layout of electrical circuits.” In Proceedings of the 9th Design Automation Conference. Description of half-perimeter wire measure. [ reference location ]

Sechen, C. 1988. VLSI Placement and Global Routing Using Simulated Annealing. Norwell, MA: Kluwer. Contains chapters on the simulated annealing algorithm; placement and global routing; floorplanning; average interconnection length estimation; interconnect-area estimation; a channel definition algorithm; and a global router algorithm. ISBN 0898382815. TK7874. S38. [ reference location ]

Sigl, G., K. Doll, and F. M. Johannes. 1991. “Analytical placement: a linear or quadratic objective function?” In Proceedings of the 28th ACM/IEEE Design Automation Conference. Compares quadratic and linear cost function for placement algorithms. Explains the Gordian place-and-route system from the Technical University of Munich. ISBN 0-89791-395-7. [ reference location ].

Wada, T., M. Eino, and K. Anami. 1990. “Simple noise model and low-noise data-output buffer for ultrahigh-speed memories.” IEEE Journal of Solid-State Circuits, Vol. 25, no. 6, pp. 1586–1588. An analytic noise model for voltage bounce on internal VDD/VSS lines. [ reference location ]

Wong, D. F., H. W. Leong, and C. L. Liu. 1988. Simulated Annealing for VLSI Design. Norwell, MA: Kluwer. Introduction; Placement; Floorplan Design; Channel Routing; Permutation Channel Routing; PLA Folding; Gate Matrix Layout; Array Optimization. ISBN 0898382564. TK7874. W65. [ reference location ]

Youssef, H., R.-B. Lin, and E. Shragowitz. 1992. “Bounds on net delays for VLSI circuits.” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol. 39, no. 11, pp. 315–324. An alternative to the weight-based approach is development of delay bounds on all nets. 21 references. [ reference location ].

[ Chapter start ] [ Previous page ]