Floorplan Representation in VLSI:Rectilinear Shape Handling and Conclusions

By -

Rectilinear Shape Handling

Shape handling makes feasible the treating of blocks with arbitrary shapes. It makes sense especially in deep sub-micron technology, where, with the number of routing layers increasing, wires are placed in layers other than the device layer, and the placement becomes more like a packing problem: a set of macro blocks are packed together without overlaps, with some objective functions minimized.

The basic idea to handle the arbitrary-shaped blocks is to partition them into rectangles, and then the representations and the optimizing strategies described above can be used. Fig. 53.34(a) and (b) demonstrate two schemes of partitioning, the horizontal one and the vertical one. However, if the generated rectangle blocks were treated as individual ones, it would be quite impossible to recover the original blocks. The generated rectangle blocks may be shifted (Fig. 53.34(c)) or separated (Fig. 53.34(d)). So extra constraints have to be imposed on the generated rectangle blocks in order to keep the original blocks’ shapes.

image

One proposed method of adding extra constraints is illustrated with Fig. 53.35(b) for horizontal and (c) for vertical. The vertexes in the constraint graph correspond to the generated rectangle blocks, while the direct edges denote the relative positions of the blocks. For example, an edge from ‘a’ to ‘b’ with a weight of 1 means that block ‘b’ lies to the right of ‘a’, the distance between their left boundaries is 1, which is exactly the width of ‘a’.

Because the relative-position constraints are always represented with the format such as “larger than or equal to” during optimization, inversely directed edges, such as the edge from ‘b’ to ‘a’ with a negative weight, helps to determine the position relationships solely.

Conclusions

Floorplan representation is an important issue for floorplan optimization. We classify the representations into graph based and placement based methods based on the different strategies used in deriving the representations. The graph-based methods are based on the constraint graphs, which include the constraint graphs, the corner stitching, the twin binary tree and the O-tree. The placement-based methods are based on the local topology relations in deriving the floorplans, which include the sequence pair, the bounded sliceline grid, the corner block list and the slicing tree.

The floorplans can also be classified into different categories: general, mosaic and slicing floorplans. Slicing floorplan is a subset of mosaic floorplan, which is again a subset of the general floorplan. We have different representations for different types of floorplans. The constraint graphs, the corner stitching, the sequence pair, the bounded sliceline grid and the O-trees are for general floorplans. The twin binary tree and the corner block list are for mosaic floorplans. The slicing tree is for slicing floorplans. Different representations have different solution spaces and time complexities to derive a floorplan.

Comments

Post a Comment

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

By -
Introduction Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for un d e rstanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code. As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furt
Read more

Collision Detection:Penetration Depth Computation

By -
Image
Penetration Depth Computation In this section, we give a brief overview of penetration depth (PD) computation algorithms between convex polytopes and general polyhedral models. The PD of two inter-penetrating objects A and B is defined as the minimum translation distance that one object undergoes to make the interiors of A and B disjoint. It can be also defined in terms of the TCSO. When two objects are overlapping, the origin of the Minkowski sum of A and − B is contained inside the TCSO. The penetration depth corresponds to the minimum distance from the origin to the surface of TCSO [18]. PD computation is often used in motion planning [37], contact resolution for dynamic simulation [38, 39] and force computation in haptic rendering [40]. For example, computation of dynamic response in penalty-based methods often needs to perform PD queries for imposing the non-penetration constraint for rigid body simulation. In addition, many applications, such as motion planning and dynamic simula
Read more

Concurrent Data Structures:Linked Lists

By -
Linked Lists Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a se t ; if a data value is associated with each key, we have a dic tionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees. Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is ha nd-over-hand locking (sometimes called l o c k coupling ) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventin
Read more