ALBERT

Description: Given a set of terminals on the plane N={s,ν1,…,νn}, with a source terminal s, a Rectilinear Distance-Preserving Tree (RDPT) T(V, E) is defined as a tree rooted at s, connecting all terminals in N. An RDPT has the property that the length of every source to sink path is equal to the rectilinear distance between that source and sink. A Min- Cost Rectilinear Distance-Preserving Tree (MRDPT) minimizes the total wire length while maintaining minimal source to sink linear delay, making it suitable for high performance interconnect applications.This paper studies problems in the construction of RDPTs, including the following contributions. A new exact algorithm for a restricted version of the problem in one quadrant with O(n2) time complexity is proposed. A novel heuristic algorithm, which uses optimally solvable sub-problems, is proposed for the problem in a single quadrant. The average and worst-case time complexity for the proposed heuristic algorithm are O(n3/2) and O(n3), respectively. A 2-approximation of the quadrant merging problem is proposed. The proposed algorithm has time complexity O(α2T(n)+α3) for any constant α 〉 1, where T(n) is the time complexity of the solution of the RDPT problem on one quadrant. This result improves over the best previous quadrant merging solution which has O(n2T(n)+n3) time complexity.We test our algorithms on randomly uniform point sets and compare our heuristic RDPT construction against a Minimum Cost Rectilinear Steiner (MRST) tree approximation algorithm. Our results show that RDPTs are competitive with Steiner trees in total wire-length when the number of terminals is less than 32. This result makes RDPTs suitable for VLSI routing applications. We also compare our algorithm to the Rao-Shor RDPT approximation algorithm obtaining improvements of up to 10% in total wirelength. These comparisons show that the algorithms proposed herein produce promising results.

Description: Sleep mode operation and exploiting it to minimize the average power consumption are of great importance in modern VLSI circuits. In general, sleep mode refers to the mode in which part(s) of the system are idle. In this paper, we study the problem of partitioning a circuit according to the activity patterns of its elements such that circuit elements with similar activity patterns are packed into the same partition. Then a partition can be placed in sleep mode during the time intervals all elements contained in that partition are idle. We formulate the partitioning problem to exploit sleep mode operation and show that the problem is NP-complete. We present polynomial time algorithms for practical classes of the problem. Applications of the problem to memory and module partitioning and clock gating are discussed. The experimental data confirm that a careful partitioning allows upto 40% more sleep time which could be exploited to minimize the average power consumption.

Description: Traditional placement problems are studied under a fully specified cell library and a complete netlist. However, in the first, e.g., 2 years of a 2 – 3 year microprocessor design cycle, the detailed netlist is unavailable. For area and performance estimation, layout must nevertheless be done with incomplete information. Another source of incompleteness comes from logic synthesis changes; some instances and their parameters will change as the project evolves. In the re-configurable computing area, sometimes we need to perform quick placement before all information is available. The problem of placement with incomplete data (PID) can be abstracted as having to place a circuit when pc% of the cells and pn% of the nets are missing. The key challenge in PID is how to add missing cells and nets.In this paper, two “patching-methods” for adding missing nets and cells are proposed. The methods are called abstraction and fusion.Experimental results are very interesting. First, they show that PID is a difficult problem and an arbitrary (and perhaps intuitively sound) method may not produce highquality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not. Specifically, when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8% while fusion has a 67.8% error in predicting the wirelength in the same circuit.