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