The quarter-state-sequence floorplan representation
Sakanushi, K. Kajitani, Y. Mehta, D.P.
Dept. of Inf. Syst. Eng., Osaka Univ., Japan;
This paper appears in: Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on [see also Circuits and Systems I: Regular Papers, IEEE Transactions on]
Publication Date: Mar 2003
Search Michi Abe
This discovery dates back to a 1930 paper by Michio Abe that is concerned with ...
Volume: 50, Issue: 3
On page(s): 376- 386
ISSN: 1057-7122
INSPEC Accession Number: 7573372
Digital Object Identifier: 10.1109/TCSI.2003.809442
Posted online: 2003-07-09 09:37:19.0
Abstract
A floorplan of a bounding box is its dissection into rectangles (rooms) by horizontal and vertical segments. This paper proposes a string data structure called the Quarter-state sequence (or Q sequence) to represent the floorplan. The Q sequence is a concatenation of the states of rooms along the Abe order and is related to the VH graph, which is the union of the vertical-constraint and horizontal-constraint graphs. It is proved that any floorplan of n rooms is uniquely encoded by a Q sequence and any Q sequence is uniquely decoded to a floorplan, both in O(n) time. An exact formula for counting distinct floorplans is given and compared with existing bounds. A linear time transformation of one Q sequence to another is defined. An n-room packing algorithm based on simulated annealing was implemented and found to compare favorably with existing packing algorithms.
An enhanced Q-sequence augmented with empty-room-insertion andparenthesis trees
Changwen Zhuang Sakanushi, K. Liyan Jin Kajitani, Y.
Inf. & Media Sci., Univ. of Kitakyusyu, Fukuoka;
This paper appears in: Design, Automation and Test in Europe Conference and Exhibition, 2002. Proceedings
Publication Date: 2002
On page(s): 61-68
Meeting Date: 03/04/2002 - 03/08/2002
Location: Paris, France
ISBN: 0-7695-1471-5
References Cited: 15
INSPEC Accession Number: 7341937
Digital Object Identifier: 10.1109/DATE.2002.998250
Posted online: 2002-08-07 00:49:38.0
Abstract
After the discussion on the difference between floorplanning and packing in VLSI placement design, this paper adapts the floorplanner that is based on the Q-sequence to a packing algorithm. For the purpose, some empty room insertion is required to guarantee not to miss the optimum packing. To increase the performance in packing, a new move that perturbs the floorplan is introduced in terms of the parenthesis-tree pair. A simulated annealing based packing search algorithm was implemented. Experimental results showed the effect of empty room insertion
The prime-graph and Q-sequence for coding the floorplan
Kajitani, Y. Sakanushi, K.
Univ. of Kitakyusyu, Fukuoka;
This paper appears in: Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on
Publication Date: 2002
Volume: 3, On page(s): 771-774
Meeting Date: 05/26/2002 - 05/29/2002
Location: Phoenix-Scottsdale, AZ, USA
ISBN: 0-7803-7448-7
References Cited: 11
INSPEC Accession Number: 7439538
Posted online: 2002-08-07 00:44:38.0
Abstract
Characterization of the floorplan has been a classical subject in combinatorics and is now a hot topic in VLSI layout design, both towards an efficient generation of floorplans. But so far no promising way has been obtained. This paper presents an answer providing an elegant representation by the name of prime-graph, and mentions an equivalent string code the Q-sequence, which was previously presented. This code has many advantages in handling the floorplans, some of which are briefly mentioned. A review is included on characterization of floorplans since it may be interesting to know how our result revived a historical contribution by Abe (see Journal of Japan Mathematical Physics, vol. 4, no. 4, p. 359-366, 1930)
A compact code for representing floorplans
Hua-An Zhao Chen Liu Kajitani, Y. Sakanushi, K.
Kyushu Kyoritsu Univ., Japan;
This paper appears in: Circuits and Systems, 2004. MWSCAS '04. The 2004 47th Midwest Symposium on
Publication Date: 25-28 July 2004
Volume: 1, On page(s): I- 433-6 vol.1
ISSN:
ISBN: 0-7803-8346-X
INSPEC Accession Number: 8380860
Digital Object Identifier: 10.1109/MWSCAS.2004.1354020
Posted online: 2004-11-15 09:48:15.0
Abstract
A new compact code called EQ-sequence for representing a floorplan is presented. A floorplan decides the placement of modules in VLSI design. The EQ-sequence is developed from Q-sequence and it can preserve the adjacent relationships of rooms on a floorplan, but the Q-sequence cannot. The algorithms for encoding, moving and decoding of EQ-sequences are introduced, respectively. By the EQ-sequence, we can check whether two modules abut or not on a floorplan. It has been proved that any floorplan of n rooms is uniquely encoded by an EQ-sequence and any EQ-sequence is uniquely decoded to a floorplan, both are in O(n) time.
An extended representation of Q-sequence for optimizing channel-adjacency and routing-cost
Full text pdf formatPdf (163 KB)
Source with EDA Technofair Design Automation Conference Asia and South Pacific archive
Proceedings of the 2003 conference on Asia South Pacific design automation table of contents
Kitakyushu, Japan
SESSION: Modeling for floorplan table of contents
Pages: 338 - 341
Year of Publication: 2003
ISBN:0-7803-7660-9
Authors
Changwen Zhuang SII EDA Technologies Inc., Kitakyushu, Fukuoka
Keishi Sakanushi Osaka University, Osaka
Liyan Jin Tokyo Inst. of Technol., Tokyo
Yoji Kajitani Univ. of Kitakyushu, Kitakyushu, Fukuoka
Sponsors
SIGDA: ACM Special Interest Group on Design Automation
IPSJ : Information Processing Society of Japan
IEICE : Institute of Electronics, Information and Communication Engineers
: IEEE Circuits and Systems Society
Publisher
ACM Press New York, NY, USA
Additional Information:
abstract references collaborative colleagues
Tools and Actions: Find similar Articles Review this Article
Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/1119772.1119837
What is a DOI?
ABSTRACT
This paper proposes a topological representation for general floorplan, called the H-sequence, which can check channel-adjacency and boundary-adjacency in a constant time. Moreover, we define Routing-cost for the placement to measure its routing difficulty. Experimental results indicate that H-sequence based placement algorithm can optimize routing-cost effectively in a short time.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
1 H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. on CAD, Vol. 15, No. 12, pp. 1518--1524, 1996.
2 S. Nakatake, H. Murata, K. Fujiyoshi, and Y. Kajitani, "Module packing based on the BSG-Structure and IC layout applications," IEEE Trans. on CAD, Vol. 17, No. 6, pp. 519--530, 1998.
3 Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States
4 C. Zhuang , Y. Kajitani , K. Sakanushi , L. Jin, An Enhanced Q-Sequence Augmented with Empty-Room-Insertion and Parenthesis Trees, Proceedings of the conference on Design, automation and test in Europe, p.61, March 04-08, 2002
5 Krzysztof Kozminski , Edwin Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits., Proceedings of the 21st conference on Design automation, p.655-656, June 25-27, 1984, Albuquerque, New Mexico, United States
6 Y-T. Lai and M. Leinwand, "A theory of rectangular dual graphs," Algorithmica, Vol. 5, pp. 467--483, 1990.
7 F. Y. Young, D. F. Wong, and H. Young, "Slicing floorplans with boundary constraints," IEEE Trans. on CAD, Vol. 18, No. 9, pp. 1385--1389, Sep., 1999.
8 M. Abe, "Covering the square by squares without overlapping," Journal of Japan Mathematical Physics, Vol.4, No.4, pp. 359--366, 1930 (in Japanese).
9 K. Sakanushi and Y. Kajitani, "The Quarter-State Sequence (Q-Sequence) to represent the floorplan and applications to layout optimization," Proc. of Asia Pacific Conf. on Circuits and Systems 2000, pp. 829--832, Dec., 2000.
10 T. Simizu, "Plane dividing T-configurations with consequent numbering and T-symbolism for orthogonal case," Society for Science on Form, Forma, Vol. 5, No. 2, pp. 173--178, 1990.
Collaborative Colleagues:
Liyan Jin:
Yoji Kajitani
Keishi Sakanushi
Changwen Zhuang
Yoji Kajitani:
Liyan Jin
Keishi Sakanushi
Changwen Zhuang
Keishi Sakanushi:
Liyan Jin
Yoji Kajitani
Changwen Zhuang
Changwen Zhuang:
Liyan Jin
Yoji Kajitani
Keishi Sakanushi
Theory of T-junction floorplans in terms of single-sequence
Xuliang Zhang Kajitani, Y.
SII EDA Technol. Inc., Fukuoka, Japan;
This paper appears in: Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on
Publication Date: 23-26 May 2004
Volume: 5, On page(s): V-341- V-344 Vol.5
ISSN:
ISBN: 0-7803-8251-X
INSPEC Accession Number: 8189782
Posted online: 2004-09-03 10:47:21.0
Abstract
In a placement, two rectangles on a plane are non-overlapping if and only if the relationship between them is one of ABLR (above, below, left-of, right-of)-relations. From the standpoint that a system of ABLR-relations is specified by the designer to confine the placement, the first concern is its consistency, i.e. if there is a corresponding placement. The second is an efficient way to construct a corresponding placement. The third is a handy coding of the ABLR-system all the way. In this paper, the first concern is solved by an existence condition of the primal-and dual-orders of rectangles. The second is answered by a linear time construction algorithm of a T-junction floorplan. This is new in its speed and generality with respect to the number of rooms. The third is by a new coding single-sequence SS. Its unique suitability to handle the T-junction floorplan is remarkable. Using the merit that SS can control the distribution of empty rooms, a novel application is suggested to space-planning, a recent trend in VLSI physical design to budget the space for congestion relief and interference separation (though the detail is not contained here for the space).
EQ-sequence and its applications in VLSI layout.
Wang, Wei-Gang; Liu, Chen; Zhao, Hua-An; Zhang, Liang-Zhen
Dianzi Yu Xinxi Xuebao (Journal of Electronics and Information Technology). Vol. 27, Suppl , pp. 237-241. Dec. 2005
Floorplan is the most important step in the VLSI design and encoding for a floorplan is the key in whole process. A floorplan is composed by rectangles which are dissections of the chip by horizontal and vertical line segments. EQ-sequence is a good method used for floorplan encoding with Abe order denoting modules relation, it is the extension of Q-sequence. In this paper, we show the practical application of the EQ-sequence in VLSI floorplan, and it resolves the problem of judging if modules abut on each other and abut to walls.
--------------------------------------------
Statistical Properties of Extremely Squeezed Configurations: A Feature in Common between Squared Squares and Neighboring Cities
Kazuya Hayata*
Department of Socio-Informatics, Sapporo Gakuin University, Ebetsu 069-8555
(Received April 18, 2003)
Properties of several extremely squeezed configurations (ESCs) are described through rank-ordering statistics of the area data of their elements. The validity of a regression calculus is confirmed with a residual analysis followed by Durbin–Watson testing. As specific ESC systems two perfect squared squares and selected Japanese prefectures containing many cities are considered. The results are explained by a competitive effect, which could arise among elements being closely packed in a constrained domain.
KEYWORDS: critical phenomena, squared squares, competing cities, rank-ordering statistics