VLSI layout

Floorplanning with I/O assignment via feasibility-seeking and superiorization methods

  • ShanYu
  • Yair Censor
  • Guojie Luo
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, VLSI layout Tags , , , , , ,

    The feasibility-seeking approach offers a systematic framework for managing and resolving intricate constraints in continuous problems, making it a promising avenue to explore in the context of floorplanning problems with increasingly heterogeneous constraints. The classic legality constraints can be expressed as the union of convex sets. However, conventional projection-based algorithms for feasibility-seeking do not guarantee … Read more

    Per-RMAP: Feasibility-Seeking and Superiorization Methods for Floorplanning with I/O Assignment

  • ShanYu
  • Yair Censor
  • Ming Jiang
  • Guojie Luo
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, VLSI layout Tags , , , ,

    The feasibility-seeking approach provides a systematic scheme to manage and solve complex constraints for continuous problems, and we explore it for the floorplanning problems with increasingly heterogeneous constraints. The classic legality constraints can be formulated as the union of convex sets. However, the convergence of conventional projection-based algorithms is not guaranteed when the constraints sets … Read more

    Minimum cost Layout Decomposition and Legalization for Triple Patterning Lithography

  • Xingquan Li
  • Wenxing Zhu
  • Ziran Zhu
    • Categories VLSI layout

    With the need of 16/11nm cells, triple patterning lithography (TPL) has been concerned in lithography industry. Based on a new conflict projection technique to identify conflicts, we formulate in this paper the TPL layout decomposition problem as a minimum cost coloring problem. The problem is solved in two steps. First, it is relaxed to a … Read more

    A Semidefinite Optimization Approach to the Parallel Row Ordering Problem

  • Philipp Hungerländer
    • Categories Facility Planning and Design, Linear, Cone and Semidefinite Programming, VLSI layout

    The $k$-Parallel Row Ordering Problem (kPROP) is an extension of the Single-Row Facility Layout Problem (SRFLP) that considers arrangements of the departments along more than one row. We propose an exact algorithm for the kPROP that extends the semidefinite programming approach for the SRFLP by modelling inter-row distances as products of ordering variables. For k=2 … Read more

    The Checkpoint Ordering Problem

  • Philipp Hungerländer
    • Categories Facility Planning and Design, Linear, Cone and Semidefinite Programming, VLSI layout

    We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to … Read more

    Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout

  • Philipp Hungerländer
    • Categories Facility Planning and Design, Linear, Cone and Semidefinite Programming, VLSI layout Tags , , , , , ,

    In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also … Read more

    A Computational Study and Survey of Methods for the Single-Row Facility Layout Problem

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , ,

    The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange … Read more

    Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

  • Antoine Deza
  • Tamás Terlaky
  • Anthony Vannelli
  • Chris Dickson
  • Hu Zhang
    • Categories Integer Programming, VLSI layout Tags , ,

    Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

    Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

  • Miguel F. Anjos
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

    A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

  • Miguel F. Anjos
  • Andrew Kennings
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear … Read more