Title :
Space-planning: placement of modules with controlled empty area by single-sequence
Author :
Zhang, Xuliang ; Kajitani, Yoji
Author_Institution :
Syst. Dev. Dept., SII EDA Technol. Inc., Kitakyushu, Japan
Abstract :
The single-sequence (simply SS ) is a permutation of integers 1,2,3,..., n each represents an object placed on a plane without mutual overlapping. An SS represents a system of ABLR-relations (above, below, left-of, right-of) between every pair of integers by SS-to-ABLR rule: if (x, y) is in SS in this order and xy, then x is left-of or below y, respectively. If objects are rooms of a T-junction floorplan of n rooms and integers denote their Abe-orders, the ABLR-relations between rooms are coded to an SS by just reading the rooms in a dual way. We enhance the definition and the fact to the case when the floorplan consists of m(≥n) rooms and the ABLR-relations are defined on the focused n of these rooms. Coding, i.e. getting the minimum SS from a given floorplan and decoding, i.e. getting the minimum floorplan from a given SS such that focused n rooms satisfy the ABLR-relations defined through the SS-to-ABLR rule are fixed by linear time algorithms. The first application is in a core technique space-planning in physical design of large systems. It is to suggest global routes to insert empty-rooms to relieve spot congestion, critical-path, crosstalk, unroutable nets, etc. without changing the ABLR-relations among the focused rooms.
Keywords :
circuit layout CAD; circuit optimisation; integrated circuit layout; ABLR-relation; SS-to-ABLR rule; T-junction floorplan; controlled empty area; linear time algorithm; single-sequence; space-planning; spot congestion; Crosstalk; Decoding; Electronic design automation and methodology; Routing; Timing; Wire;
Conference_Titel :
Design Automation Conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific
Print_ISBN :
0-7803-8175-0
DOI :
10.1109/ASPDAC.2004.1337534