In the design of printed circuit boards and integrated circuits, the problem of determining the appropriate wiring direction from pins is addressed by the more complex and difficult problem of "Place and Route Puzzle." We propose a method that can always find a solution. In this method, we convert the Place and Route Puzzle into a graph, divide it into 3-vertex-connected components, and then apply a known planar drawing method to each connected component to find a solution.

Recently, exploring repeated placements has been researched to apply on-chip processor array, which consists of the array of the same processors. This representation may also be used for the design of FPGA, scheduling of pipeline, and others. For this purpose, sequence-triple, representation for repeated placement, was proposed. However, it cannot represent a certain kind of placements but contains so many redundant codes. In this paper, we propose a novel representation method for repeated placement, which can represent any horizontal prior Horizontal-Vertical-Relation-Set. Also, we propose a decoding algorithm of the representation, which takes O(n3) time, where n is the number of rectangles in each cycle.

Recently, 3D-LSIs which consist of several silicon layers have been developed and have attracted attention. 3D-LSI has an advantage of the length of wires and the number of components per chip. However, a layout design of the 3D-LSIs will be much complex. In this paper, we propose a stacked-rectangular-dissection, which consists of several rectangular dissections, as a floorplan of 3D-LSI. And to search for a good floorplan of 3D-LSI with simulated annealing, a representation of a stacked-rectangular-dissection is presented.

The 3D packing problem consists of arranging nonoverlapping rectangular boxes (blocks) of given sizes in a rectangular box of minimum volume. As a representation of 3D packings, this paper proposes a novel encoding method called Double Tree and Sequence (DTS). The following are features of DTS: 1) It can represent any minimal packing. 2) It can be decoded into the corresponding 3D packing inO(n2) time, wherenis the number of rectangular boxes. 3) The size of the solution space (the number of codes) of DTS is significantly smaller than any conventional representation that can represent any packing. Experimental comparisons with conventional representations indicate the superiority of the proposed representation DTS.

3D packing problem is to arrange rectangular boxes (blocks) of given sizes in a rectangular box of the minimum volume without overlapping each other. As a representation for 3D packings, this paper proposes a novel encoding method, called DTS (double tree and sequence). The feature of the DTS is: (1) It can represent any minimal packings. (2) The size of the solution space (the number of codes) of DTS is much smaller than any conventional representation which can represent any packings. Experimental comparisons with conventional representations indicate the superiority of the proposed representation DTS

In recent high-performance analog integrated circuit design, it is often required to place some cells symmetrically to a horizontal or vertical axis. Balasa et al. proposed a method of obtaining the closest placement that satisfies the given symmetry constraints and the topology constraints imposed by a sequence-pair (seq-pair). However, this method has the following defects: 1) Balasa's necessary condition for existence of the cell placement that satisfies the given constraints is incorrect; 2) some cells overlap; 3) the closest placement of satisfying both the symmetry and topology constraints is not always obtained; and 4) there is no explanation of placing cells symmetrically to plural axes. In this paper, we clarify the necessary and sufficient conditions for the existence of the cell placement that satisfies the given symmetry constraints and the topology constraints imposed by a seq-pair, and we propose an efficient method of obtaining, by linear programming, the closest cell placement that satisfies the given constraints. Here, a simple constraint graph is obtained from a seq-pair in order to derive a set of linear constraint expressions. Then, to shorten the running time of linear programming, the number of linear expressions is reduced by substituting the expressions for dependent variables, and the solution is obtained. The effectiveness of the proposed method was shown by computational experiments

In our dynamically reconfigurable system model, computation resources are arranged in 2D-plane and each partial task is assigned to computation resources of rectangle-shape for a certain time period. The problem can be regarded as a rectangular box packing problem in 3D-space of 2D-plane and time axis. However, since partial tasks have order constraints, a packing should satisfy the given order constraints. We call this problem 3D-scheduling problem. Although there have been proposed various types of rectangular box packing representation, it is not examined until now which representation is fit to 3D-scheduling problem. In this paper, we investigate features of each 3D-packing representation, and show which representation is fit to 3D-scheduling problem theoretically and experimentally

Recently, it is often required in high performance analog IC design that some cells are placed symmetrically to horizontal or vertical axis. Balasa et al. proposed a method of obtaining the closest placement satisfying the given symmetry constraints and the topology constraints imposed by a sequence-pair, but this method has the following defects: (1) Some cells overlap each other. (2) The closest cell placement satisfying both the symmetry and topology constraints may not be obtained. (3) How to place cells symmetrically is mentioned only for one axis and there is no explanation for plural axes. In this paper, we propose an efficient method to obtain the closest cell placement satisfying the given symmetry constraints and the topology constraints imposed by a sequence-pair using linear programming. The proposed method obtains a simple constraint graph from a sequence-pair and derives a set of linear constraint expressions from the graph. The number of linear expressions decreases by substituting the expressions for dependent variables. Then the solutions are obtained by linear programming. The effectiveness of the proposed method was shown by computational experiments.

In this paper, we propose selected (SSP), a sequence-pair (seq-pair) with the limited number of subsequences called adjacent crosses. Its features are: (1) The smallest packing based on a given SSP can be obtained in O(n) time, where n is the number of rectangles. (2) An arbitrary packing can be represented by SSP. (3) The total representation number of SSP of size n is not more than that of rectangular dissection of the same size with n-/spl lfloor//spl radic/(4n-1)/spl rfloor/ empty rooms (the necessary number of empty rooms to represent an arbitrary packing). To realize these features of SSP, we propose an algorithm to enumerate all adjacent crosses on a seq-pair in linear time of n + k (k is the number of adjacent crosses). Also we apply a conventional method to convert a seq-pair without adjacent crosses to an equivalent Q-sequence, representation of rectangular dissection, in O(n + k) time. A move operation to obtain an adjacent solution efficiently is proposed to perturb SSP for Simulated Annealing (SA). From experimental results, we confirmed the proposed method was carried out in linear time and was more efficient than the conventional method when SSP size got bigger.

VLSI floorplan is a rectangular dissection of a chip rectangle where dissection lines correspond to wiring channels and each module is assigned to a separate room. Floorplans are often represented by the slicing structures. Recently, sequence-pair (seq-pair) has been proposed as the description of the rectangle packing and later on a method to map a seq-pair to a floorplan has been proposed. However, such floorplans made of seq-pairs often include rooms with no module assigned, and so it is difficult to make good solution space by seq-pair. In this paper, we propose a novel solution space of floorplans for simulated annealing (SA) which consists of the all general floorplans with exact n rooms, where n is the number of given modules, using seq-pair. By using ingenious data structure, a feasible adjacent floorplan can be obtained in O(n/sup 2/) time and the reachability from any floorplan to any other in the proposed solution space is proved. The experimental results show the effectiveness of the solution space.

The sequence-pair was proposed in 1995 as a representation of the packing of rectangles of general structure. Since then, there have been efforts to expand its applicability over simple rectangles. This paper proposes a unified way to represent the packing of a set of rectilinear blocks, including arbitrary concave rectilinear blocks. Our idea is in the representation of a general block by a collection of rectangle blocks with additional constraints, Some sequence-pairs of rectangle blocks with such constraints may not be feasible, i.e., there is no corresponding parking. A necessary and sufficient condition of feasible sequence-pair is given by the properties of the horizontal and vertical constraint graphs. Furthermore, it is proved that any packing is represented by a feasible sequence-pair. The condition includes dimensions of blocks involved. If we limit the rectilinear blocks to L-shaped ones, a necessary and sufficient condition can be represented only in terms of the topology of the sequence-pair, without dimensions of blocks. A packing algorithm is designed as an SA search of the generated sequence-pairs. Experimental results show the effectiveness of the proposed method.

The sequence-pair was proposed in 1995 as a rep- resentation of the packing of rectangles of general structure. Since then, there have been efforts to expand its applicability over simple rectangles. This paper proposes a unified way to represent the packing of a set of rectilinear blocks, including arbitrary concave rectilinear blocks. Our idea is in the repre- sentation of a general block by a collection of rectangle blocks with additional constraints. Some sequence-pairs of rectangle blocks with such constraints may not be feasible, i.e., there is no corresponding packing. A necessary and sufficient condition of feasible sequence-pair is given by the properties of the horizontal and vertical constraint graphs. Furthermore, it is proved that any packing is represented by a feasible sequence-pair. The condition includes dimensions of blocks involved. If we limit the rectilinear blocks to L-shaped ones, a necessary and sufficient condition can be represented only in terms of the topology of the sequence-pair, without dimensions of blocks. A packing algorithm is designed as an SA search of the generated sequence-pairs. Experimental results show effectiveness of the proposed method. Index Terms—Compaction, layout, packing, placement, se- quence-pair.

In a typical very large scale integration/printed circuit board (VLSI/PCB) design, some modules are preplaced in advance, and the other modules are requested to be placed without overlap with each other and with these preplaced modules. The presence of such obstacles introduces inconsistency to a coding scheme, called sequence pair, which has been proposed for an obstacle free placement problem. We solve this difficulty by proposing a procedure called "adaptation" which transforms an inconsistent sequence pair to a consistent one with the utmost consideration for minimizing the modification. It is shown that a simulated annealing is well organized so that it tests only feasible placements by the adaptation procedure. As a design example, a Microelectronics Center of North Carolina (MCNC) benchmark data "ami49" is packed with treating ten modules among 49 modules as preplaced ones. Further, a PCB example which includes 32 free modules and four preplaced modules (connectors) is laid out successfully by our method with a conventional wiring estimation followed by a commercial router.

A new method of packing the rectangles is proposed with applications to integrated circuit (IC) layout design. A special work-sheet, called the bounded-sliceline grid, is introduced. It consists of special segments that dissect the plane into rooms to which binary relations "right-of" and "above" are associated such that any two rooms are uniquely in either relation. A packing is obtained through an assignment of the modules into the rooms followed by a compaction procedure. Changing the assignments by swapping the contents of two rooms, a simulated annealing strategy is implemented to search for a good packing. Empirical results show that hundreds of rectangles are packed with a quite good quality in area efficiency. A wide adaptability is demonstrated specific to IC layout design. Ideas to handle a multilayer, nonrectangular chips with L-shaped modules are suggested.

A fundamental issue in floorplanning is in how to represent candidate solutions. A representation called sequence-pair was recently proposed. Seq-pair is so general as to represent an area minimum placement, and also efficient because it does not represent any overlapping placement. However, seq-pair is not expressive enough since channels are not represented. The paper gives a mapping from seq-pair to rectangular dissection, which represents channels by line segments. Consequently, candidate arrangements of modules and channels are successfully represented with the generality and the efficiency inherited from the seq-pair.

Article VLSI/PCB placement with obstacles based on sequence-pair Share on Authors: H. Murata Japan Advanced Institute of Science and Technology, Japan Japan Advanced Institute of Science and Technology, JapanView Profile , K. Fujiyoshi Tokyo University of Agriculture and Technology, Japan Tokyo University of Agriculture and Technology, JapanView Profile , M. Kaneko Japan Advanced Institute of Science and Technology, Japan Japan Advanced Institute of Science and Technology, JapanView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 26–31https://doi.org/10.1145/267665.267675Online:01 April 1997Publication History 38citation300DownloadsMetricsTotal Citations38Total Downloads300Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The design of optimum connection blocks of field programmable gate arrays (FPGA's) in number and in distribution of switches is formulated as a bipartite graph design problem and solved. A bipartite with vertex sets R and L (|R|/spl les/|L|) is called totally perfect if there is a perfect matching from L/sub s/ to R for any L/sub s//spl sub/L with |L/sub s/|/spl les/|R|. The difference of maximum and minimum degrees of the vertices in L or R is called the skew of the respective vertex set. The problem is to construct a minimum totally perfect bipartite graph with the minimum skew. The result shows that a method, biscattering, can construct such a matrix in O(|R|/spl times/|L|) time where the lower bound is attained for both skews. This construction also solves the problem of designing optimum direct-concentrators.

A new method of packing rectangles (modules) is presented with applications to IC layout design. It is based on the bounded-sliceline grid (BSG) structure. The BSG dissects the plane into rooms associated with binary relations "right-to"and "above" such that any two rooms are uniquely in either relation. A packing is obtained through an assignment of modules on the BSG. Followed by physical realization BSG-PACK. A simulated annealing searches for a goon packing of all packings by changing the assignments. Experiments showed that hundreds of rectangles are easily packed in a small rectangle area (chip) with quite good quality in area efficiency. A wide adaptability is demonstrated specific to IC layout design. Remarkable examples are: the chip is not necessarily rectangle, L-shaped modules and modules which are allowed to partially overlap each other can be handled.

The earliest and the most critical stage in VLSI layout design is the placement. The background is the rectangle packing problem: given a set of rectangular modules of arbitrary sizes, place them without overlap on a plane within a rectangle of minimum area. Since the variety of the packing is uncountably infinite, the key issue for successful optimization is the introduction of a finite solution space which includes an optimal solution. This paper proposes such a solution space where each packing is represented by a pair of module name sequences, called a sequence-pair. Searching this space by simulated annealing, hundreds of modules have been packed efficiently as demonstrated. For applications to VLSI layout, we attack the biggest MCNC benchmark ami49 with a conventional wiring area estimation method, and obtain a highly promising placement.

The first and the most critical stage in VLSI layout design is the placement, the background of which is the rectangle packing problem: Given many rectangular modules of arbitrary site, place them without overlapping on a layer in the smallest bounding rectangle. Since the variety of the packing is infinite (two-dimensionally continuous) many, the key issue for successful optimization is in the introduction of a P-admissible solution space, which is a finite set of solutions at least one of which is optimal. This paper proposes such a solution space where each packing is represented by a pair of module name sequences. Searching this space by simulated annealing, hundreds of modules could be successfully packed as demonstrated. Combining a conventional wiring method, the biggest MCNC benchmark ami49 is challenged.

The optimal design problem of the connection-blocks of FPGA with respect to the number of switches and their distribution is solved. This also concerns with the optimal construction of direct concentrators.>