Computer aided design of any style starts with coding the objects. The objects are blocks and nets. The code is, in fact, a permutation of object labels. A solemn fact is that the code is a linear array while the objects are floating on the multiple layer or 3D space so that potentially very restricted data can be on the code. Given this opportunity at ISPD 2013, I would like to disclose an unpublished story which stands solely on the concept of permutation. It was motivated by a question about a small gap found in classic channel routing. The interest is in how unrelated place and route matters be related with each other.

Routing for high-speed boards is still achieved manually today. There have recently been some related works to solve this problem; however, a more practical problem has not been addressed. Usually, the packages or components are designed with or without the requirement from board designers, and the boundary pins are usually fixed or advised to follow when the board design starts. In this paper, we describe this fixed ordering boundary pin routing problem, and propose a practical approach to solve it. Not only do we provide a way to address, we also further plan the wires in a better way to preserve the precious routing resources in the limited number of layers on the board, and to effectively deal with obstacles. Our approach has different features compared with the conventional shortest-path-based routing paradigm. In addition, we consider length-matching requirements and wire shape resemblance for high-speed signal routes on board. Our results show that we can utilize routing resources very carefully, and can account for the resemblance of nets in the presence of the obstacles. Our approach is workable for board buses as well.

Routing for high speed boards is still achieved manually nowadays. There have been some related works in escape routing to solve this problem recently, however a more practical problem is not addressed. Usually the packages/components are designed with or without the requirement from board designers, and the boundary pins are usually fixed or advised to follow when the board design starts. Previous works in escape routing are not likely to be used due to this nature, in this work, we describe this fixed ordering boundary pin escaping problem, and propose a practical approach to solve it. Not only can we have a way to address, we also further plan the wires in a better way to preserve the precious routing resources in the limited number of layers on the board, and to effectively deal with obstacles. Our approach has different feature compared with conventional shortest-path-based routing paradigm. In addition, we consider length-matching requirement and wire shape resemblance for high speed signal routes on board. Our results show that we can utilize routing resource very carefully, and can account for the resemblance of nets in the presence of the obstacles. Our approach is workable for board busses as well.

For multi-FPGA systems, the limitation of the number of FPGA I/O-pins is one of the most critical issues. Using time-multiplexed I/Os eases the limitation. While, a signal path through n time-multiplexed I/Os makes the system clock period n + 1 times longer at most. To capture this feature, we introduce a new cost total cut-hopcount. Under the total cut-hopcount, we propose a performance-driven bipartitioning method VIOP. VIOP combines three algorithms, such that i) min-cut partitioning, ii) coarse performance-driven partitioning, and iii) fine performance-driven partitioning. For min-cut and coarse performance-driven partitioning, we employ well-known bipartitioning algorithms CLIP-FM and DUBA, respectively. For fine performance-driven partitioning, we propose a partitioning algorithm CAVP. By VIOP, the average cost was improved by 11.5% compared with the state-of-the-art algorithms

The recent hierarchical design framework[8] for 3D floorplan-ning suggests a better performance than previous flat design framework. Under this framework, the layer assignment of the blocks is accomplished by some partitioning algorithms which are assumed to be critical[8]. In this paper, we provide an empirical study on the impact of such partitioning algorithms on the total wire length. By generating various partitions and running our floorplanner based on these partitions, we obtain the statistic of the resultant wire length. We observe that when the design instance has a large number of blocks which are uniformly sized, different partitions with the same cut size lead to roughly the same wire length. By another experiment, we find out that the cut size of the partition has the major influence on the wire length. Therefore, we argue that cut size is a metric good enough for the wire length optimization of 3D floorplanning and suggest that future research focus on other problems such as thermal effect, signal delay, etc.

After BSG and sequence-pair (SP) of the placement codes, a decade has passed with various proposals of new codes and ideas for applications, especially in VLSI physical design. Different in appearance, they are actually proposing generators of ABLR-relations, i.e. above, below, left-of, or right-of relations between two rectangles on a plane to be non-overlapping, together with methodologies how dimensions and peripheral constraints are integrated. This paper proposes another yet simplest generator numDAG which is simply a directed acyclic graph with vertices labelled with distinct numbers. Assuming each vertex representing a rectangle on a plane, an edge (i, j) is featured to imply the property "i is left-of j" or "i is above j" according to the edge being incremental or decremental, respectively, with respect to the numbers of end vertices. To demonstrate that the numDAG is the ABLR-relation generating system hierarchically above existing systems, we relate it with single-sequence, H-and V-constraint graph pair, SP, BSG, and O-tree. It is a future problem to find any practical merit by this idea but the contribution is believed in providing a base to the unified theory of constraint-driven placement. Several new ideas and problems are included

The shape-based routing needs a routing architecture with a geometrical computation framework on it. This paper introduces a novel routing architecture, Oct-Touched Tile (OTT), with a geometrical computation method along the horizontal- and vertical-constraints. The architecture is represented by the tiles spreading over the 2-D plane. Each tile is flexible to satisfy the constraints imposed for non-overlapping and sizing request. In this framework, any practically useful path finding and shape-based sizing technique are executed on the same architecture. Our system ex-perimentally demonstrates the performance comparable to a commercial tool.

In VLSI system, a certain set of nets is required to propagate their signals within a tolerable skew of delays. Though the delay of the signal on a wire is determined by a complex environment, it is hard to satisfy this requirement unless all the concerned nets are routed within a certain skew of length. This paper approaches this problem by the concept of l-equidistance routing which aims to route the concerned nets by prescribed length l. After a basic technique to route a 1-sink net with prescribed length, an algorithm is presented for the channel routing where sink terminals are on the upper line and source terminals on the bottom lines. The key idea is in the symmetric slant grid interconnect scheme by which the problem is reduced to the ordinary grid routing problem. An algorithm that attains minimum total wire length is presented. Then a solution is given for the case when terminals are on the perimeters on a rectangle. These algorithms are explained on the Euclidean space. But it is shown that a straightforward transformation of the routes to those on the orthogonal grid is possible keeping the property of equidistance. Proposed algorithms were implemented and applied to random data to demonstrate their ability.

A challenge to an automated layout of analog IC starts with the insight into a high quality placement crafted by experts. It has been observed that such a placement comprises clusters corresponding to groups of matched devices and devices are placed faithfully to the drawn schema while the placement is still compacted. This paper proposes a novel device-level placement based on Sequence-Pair which includes an effective representation of clusters extracted from the schema. A key idea is to capture a topological structure of clusters in order to place clusters at as faithful positions to those in the schema. We represent this structure in terms of ABLR-relations which can be translated into Sequence-Pair. In experiments, we tested our algorithm for industrial instances and compared the results with those by manual. We showed that our results were better than manual results by, on average, 12.8% and 18.1% with respect to area and net-length.

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.

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.

Sequence-pair-based floorplanning has revealed the limit of its usefulness in very large scale integration layout design, the key issue being that it is nonhierarchical and indifferent to the preceding step of partitioning. This paper restructures the sequence pair enhanced to a pair of logic expressions to accept the constraint induced by the previous step - the balanced bipartition. Since the bipartition is hierarchical in nature, the transferred constraint is called the hierarchical superconstraint. Since floorplanning based on this data structure automatically works cooperatively with the partitioning, it is called the consistent floorplanning, which has potential to store all the feasible floorplans under the constraint induced by any balanced binary search. As a typical example, we focus on clock-tree synthesis by H-tree. Experiments are given to show better achievements in length and wire density for module-based circuits and clock trees.

Sequence-Pair based floorplanning has been revealed its limit of usefulness in VLSI physical design. Among reasons, the key issue is in its being non-hierarchical and indifferent to the preceding step of partitioning. This paper restructure the algorithm by the idea that the partition algorithm produces the constraint that is imposed on the sequence-pair data. The partition algorithm is the one based on the balanced-bipartition that works hierarchically. Thus a new floorplan algorithm that is consistent with the hierarchical partition algorithm is constructed. This is enhanced to include other algorithms that are based on the binary search. Here, a clock-tree synthesis by H-tree is shown to be consistent. Experiments are given to show better achievements in length and wire-density.

Abstract | Given a route which connects terminal-s on a one-layer routing area(Steiner tree), \n ip is a procedure that makes a current route change its con-guration within its peripheral domain. A \nip reforms a route by replacing one of its edges with a minimal detour. A route can \nip one nearby obstacle. If the obstacle is another route, a more organized operation, called the dual \nip, is applied to a pair of routes. The idea is enhanced to the 2-layer hv-routing. The per-formance of \nip and dual \nip was experimented in simulated annealing which reforms a route or a set of routes with respect to the evaluation function of mul-tiple objectives. Some unique and satisable results were observed. I.

A semi-synchronous circuit is a circuit in which every register is ticked by a clock periodically, but not necessarily simultaneously. A feature of semi-synchronous circuits is that the minimum delay between registers may be critical with respect to the clock period of the circuit. In this paper, we discuss a delay insertion method which makes such a semi-synchronous circuit faster. The maximum delay-to-register ratio of the cycles on the circuit gives a lower bound of the clock period. We show that this bound is achieved in the semi-synchronous framework by the proposed gate-level delay insertion method on the assumption that the delay of each element on the circuit is unique.

A new approach for the minimum area floorplanning is proposed where the shape of every module can vary under the constraint of area and floorplan topology. Simulating the air-pressure mechanics, the algorithms iterate to improve the layout to decide the shapes and positions of modules. It is proved that the layout approaches the optimal layout each step by the measure of energy which is defined by the current layout. Experimental results showed very fast convergence. An extension to a more practical case with the aspect-ratio constraint is discussed.

A main task in designing IC/PCB is to pack rectilinear modules under various constraints and objectives. If modules are all rectangles without any positional constraint, recently proposed BSG and Sequence-pair based packing algorithms have been proved to work fast enough for practical use. Focusing BSC, to support an effective use, this paper develops techniques to handle rectilinear modules and modules with positional constraints. First a solution is proposed for pre-placed modules. It is to give a linear order to the floating modules following which they are embedded in packing. In the course, the pre-placed modules are considered as the constraints such that no floating modules are forbidden to be placed. The packing of modules including rectilinear ones is solved by applying the above techniques after rectilinear modules are sliced into a set of rectangles. Experimental results on industrial PCB-data showed that the proposed algorithm outputs high quality packings.

Article The channeled-BSG: a universal floorplan for simultaneous place/route with IC applications Share on Authors: Shigetoshi Nakatake Department of Electrical and Electronic Engineering, Tokyo Institute of Technology Department of Electrical and Electronic Engineering, Tokyo Institute of TechnologyView Profile , Keishi Sakanushi Department of Electrical and Electronic Engineering, Tokyo Institute of Technology Department of Electrical and Electronic Engineering, Tokyo Institute of TechnologyView Profile , Yoji Kajitani Department of Electrical and Electronic Engineering, Tokyo Institute of Technology Department of Electrical and Electronic Engineering, Tokyo Institute of TechnologyView Profile , Masahiro Kawakita Semiconductor Systems Engineering Center, Toshiba Corporation Semiconductor Systems Engineering Center, Toshiba CorporationView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 418–425https://doi.org/10.1145/288548.289064Online:01 November 1998Publication History 9citation195DownloadsMetricsTotal Citations9Total Downloads195Last 12 Months1Last 6 weeks0 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

A floorplannar that can handle convex-rectilinear blocks is developed by enhancing the BSG-based packing algorithm.The ideas are in the intr~ duction of (1) multi-rectangle representation of a block as a superpose of element-rectangles, (2) parametric-BSG as a generalization of the BSG, (3) mult i-BSG which is an arrangement of plural BSG's on a multi-layer, and (4) layer sharing condition of element-rectangles so that non-overlapping is di~ cussed on each layer.A solution space of packings is defined as the set of packings generated by changing parametric-BSG and room assignments.It is guaranteed to contain an optimal packing if the BSG is not smaller than a certain size.A floorplan based on a simulated annealing w= implemented.In experiments, it output highly compressed packings.

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d ≤ 2. The improvement over other analyzed algorithms is a factor of about e ≈ 2.718. © 1998 John Wiley & Sons, Inc. Networks 31: 283–292, 1998

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.

It is known that the clock-period in a sequential circuit can be shorter than the maximum signal delay between registers if the clock arrival time to each register is controlled. We propose an algorithm to find the minimum clock-period of a circuit whose signal propagation delays are given. Experimental results on LGSynth93 benchmarks show that this technique achieves as much as about 16% reduction of clock-period compared with the conventional maximum signal delay based methods. An application of this technique to improve the reliability of circuits is considered.

It is known that the clock period can be shorter than the maximum of the signal delays between registers if the clock arrival time to each register is properly scheduled. The algorithm to design an optimal clock schedule is given. In this paper, we propose a clock-tree routing algorithm that realizes a given clock schedule using the Elmore delay model. Following the deferred-merge-embedding (DME) framework, the algorithm generates a topology of the clock tree and determines the locations and sizes of intermediate buffers simultaneously. The experimental results show that this method constructs clock trees with moderate wire length compared with that of zero-skew clock trees.

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.>

Abstract This paper solves the minimum augmentation problem for a given tree and positive integer k, that is, to make a tree k‐edge‐connected by adding the minimum number of edges. It is shown that the minimum number of edges is the least integer not less than a half of the deficiency of the tree which is defined as the sum of k‐(degree) over all the vertices whose degrees are less than k. The proof is constructive and gives a polynomial‐time algorithm for constructing such an augmentation.

Abstract For a directed graph G , let d + (ν) and d (ν) be the outdegree and indegree of vertex ν, respectively. Given a positive integer k , the outdeficiency and indeficiency are defined by δ (ν) = max ( k − d + (ν), 0) and δ (ν) = max( k − d − (ν), 0), respectively. It is evident that in augmenting G to a k ‐edge‐connected directed graph, at least δ k ( G ) = max(Σδ (ν), Σδ (ν)) edges are necessary. This paper proves the theorem that if G is a directed tree (directed graph whose underlying graph is a tree) this number of edges is enough. The proof is made by presenting a construction procedure of polynomial‐order complexity.

For a given placement of blocks and global routing of nets, a new formulation and its solution of the problem of determining the order of channels for the complete channel routing are presented. If the order of channels satisfying the condition exists, it is called the safe order since following it, each channel can be routed the wiring requirement without any prediction of necessary width. Thus the compaction of the routing area can be made utmost each time. The idea is based on the general feature of channel routers not on any particular one. Related subjects such as the simultaneously routable channels, generalization of the safe order, switch box routing, and the placement with nonrectangular blocks are discussed.