Abstract

A method for placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having an array of element placement positions thereon determines optimum placement in a three pass process. In the first pass, all of the elements are treated as if they are the same size, defined as a unit size, and are assigned to element positions on a unit size next level package, then their placement is optimized. These unit size elements are then replaced by macro size elements, which are approximately the actual size of the corresponding electronic elements. The macro size elements are then rearranged for optimal placement on a macro model image, taking their sizes and shapes into account. Finally, the macro size elements are replaced by actual size elements which are placed on an actual size next level package in element positions, and their placement is again optimized. By optimizing element placement in a three pass process, i.e., unit, macro and actual size, a more efficient placement process is obtained because the element placement program need not take all of the dimensional characteristics of the elements into account at once.

Other References

• "The Design of Printed Circuit Layouts by Computer": by Dunne, Proceedings of the Third Australian Computer Conference, 1967, pp. 419-423
• Nishioka et al., "An Approach of Gate Assignment and Module Placement for Printed Wiring Boards", Systems-Computers-Controls, vol. 11, No. 3, pp. 54-65, 1980
• Soukup, "Circuit Layout", Proc. of the IEEE, vol. 69, No. 10, pp. 1281-1304, Oct. 1981
• T. Raymond, "LSI/VLSI Design Automation," Computer, vol. 14, No. 7, pp. 89-101, (Jul. 1981)
• IBM Technical Disclosure Bulletin, vol. 17, No. 20, Mar. 1975, "Hierarchical Placement Method", W. E. Donath, pp. 3121-3125
• 1981 IEEE, 18th Design Automation Conference, Nashville, Tenn., 6/29, 30 & Jul. 1, 1981, "Automatic Component Placement in an Interactive Minicomputer Environment", Charles F. Shupe, Bell Laboratories, Paper 9.3, pp. 145-152
• 1981 IEEE, 18th Design Automation Conference, Nashville, TN, 6/29, 30 & Jul. 1, 1981, "Placement of Variable Size Circuits on LSI Masterslices", K. H. Khokhani, A. M. Patel, W. Ferguson, J. Sessa, D. Hatton, IBM Corp., Paper 20.3, pp. 426-434
• IEE 1981, European Conference on Electronic Design Automation, Brighton, Sussex, England, 1-4 Sept. 1981, "A System for Automatic Layout of Gat Array Chips", K. W. Laller, J. B. Hickson, Jr., R. K. Jackson, pp. 54-58
• No. 14, Design Automation Conference Proceedings, Jun. 20, 21, & 22, 1977, "The Chip Layout Problem: A Placement Procedure for LSI", K. H. Khokhani and A. M. Patel, pp. 291-297
• "A Class of Min-Cut Placement Algorithms", M. A. Breuer, Depts. of Electrical Engineering & Computer Science, University of Southern California, Los Angeles, Calif., pp. 284-290
• Design Automation of Digital Systems, Theory and Techniques, Prentice-Hall, Inc. Engelwood Cliffs, N.J., Chapter 5, Placement Techniques, Maurice Hanan & Jerome M. Kurtzberg, pp. 213-282