Browsing by Author "Lu, Bing"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A Polynomial Time Approximation Scheme for the problem of Interconnecting Highways
    (2000-11-28) Cheng, Xiuzhen; Kim, Joon-Mo; Lu, Bing
    The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework in [2]. For every fixed c>1 and given any n line segments in the plane, a randomized version of the scheme finds a (1+1/c)-approximation to the optimal cost in O(n o(c)log n) time.
  • Thumbnail Image
    Item
    Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-like Models
    (2001-04-06) Shragowitz, Eugene; Youssef, Habib; Lu, Bing
    Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on non-critical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on noncritical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.
  • Thumbnail Image
    Item
    New Bound-Based Net Criticality Metrics for Timing-Driven Physical Design
    (2001-06-11) Shragowitz, Eugene; Chang, Hongliang; Liu, Jian; Youssef, Habib; Lu, Bing; Sutanthavibul, Supachai
    A target of this work is improving timing characteristics of layout and optimizing design flow by reducing the number of iterations required for a timing closure. This goal is achieved by introducing new criticality metrics that could be computed prior to placement and routing respectively and converted to weights of nets supplied to a placer and to a router. These new metrics are defined as a ratio of a net parameter to a net delay bound. The net delay bounds used in this paper are computed by the Iterative Minimax algorithm of Youssef et. al. (see references in the text). This algorithm has the lowest time complexity (linear) among all algorithms proposed for the computation of delay bounds and corresponds well with therequirements of layout tools. In this paper, a contribution is also made to the bound on the delays theory by proving that there is an infinite number of solutions for the zero-slack distribution problem. It is also explained why net bounds derived from a linear programming formulation could be difficult to implement on the placement step of layout. Part II: This report proposes new net criticality metrics and one pass design flow methodology for timing-driven physical design. The proposed net criticality metrics employ net parameters and bounds on net delays derived by the Minimax algorithm. The criticality metrics were mapped to weightsin the Cadence Silicon Ensemble DSM Automatic Layout System and produced in one-pass layouts with the clock cycle approximately 29% faster in average than without criticality evaluation. Criticality metrics are independent of layout tools producing actual placement and routing.Criticality calculation could be integrated with any layout system that allows weights for individual nets on the placement and routing steps. In the section on Criticality Metrics, it is proven that the net parameters strongly correlated to net delay could be used in formulas for criticality metrics. They provide the same relative ranking of nets with respect to the net criticality metrics as the projected net delays. On this ground, the new criticality metrics based on net parameters and delay bounds are introduced for placement and routing stages of layout respectively. These criticality metrics computed for each net in the design are sorted in the descending order to produce relative ranking of nets with respect to the net criticality. From the ordered list of criticality metrics weights are derived by layout systems. In the experimental part of this work, the proposed design flow and the criticality metrics were integrated with the Cadence SE (Silicon Ensemble) DSM Automatic Layout System (version 5.2.158). The SE system was allowed to place and route a set of designs in several modes with and without weights produced from the proposed new criticality metrics. With weights provided by the new criticality metrics, the SE system achieved reduction in the clock cycle by 27% in average for the set of tests in one iteration of layout. It also significantly outperformed attempts to reduce a clock rate by repeated iterations of layout and by using timing-driven version of the SE Layout System. A conclusion is that new metrics could be useful for all layout tools that allow weights to be assigned to nets.
  • Thumbnail Image
    Item
    Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem
    (2000-02-14) Lu, Bing; Ruan, Lu
    Given a set N of n terminals in the first quadrant of the Euclidean plane E2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently. In this paper, we present a polynomial time approximation scheme for this problem.