[ Chapter start ] [ Previous page ] 16.8 ReferencesPage 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. “Mincut 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 performancedriven 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 ComputerAided Design for IntegratedCircuits and Systems, Vol. CAD3, 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 rdimensional 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 zeroslack 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 timingdriven 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. CAS26, 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 0471928380. 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 timingdriven placement and net and pathbased approaches. Describes some different methods to estimate interconnect delay during placement. ISBN 0897913957. [ reference location ]. Masleid, R. P. 1991. “Highdensity central I/O circuits for CMOS.” IEEE Journal of SolidState 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"; "Mazerunning and linesearch algorithms" an easilyreadable paper on detailed routing by Ohtsuki; and a mathematical paper, "Global routing," by Kuh and MarekSadowska. 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: BenjaminCummings. ISBN 0805304129. TK7874.P47. [ reference location ] SangiovanniVincentelli, A. 1986. “Automatic layout of integrated circuits.” In Nato Advanced Study on “Logic Synthesis and Silicon Compilers for VLSI Design”, G. De Micheli, A. SangiovanniVincentelli, and A. Paolo (Eds.). Norwell, MA: Kluwer. ISBN 9024726891, 9024735610. TK7874.N338. [ reference location ] Schweikert, D. G., 1976. “A 2dimensional placement algorithm for the layout of electrical circuits.” In Proceedings of the 9th Design Automation Conference. Description of halfperimeter 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; interconnectarea 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 placeandroute system from the Technical University of Munich. ISBN 0897913957. [ reference location ]. Wada, T., M. Eino, and K. Anami. 1990. “Simple noise model and lownoise dataoutput buffer for ultrahighspeed memories.” IEEE Journal of SolidState 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 weightbased approach is development of delay bounds on all nets. 21 references. [ reference location ]. [ Chapter start ] [ Previous page ] 




