Placement and Routing in VLSI design Problem Using Single Row Routing Technique

Abstract

Two major problems are involved in VLSI design, namely, the placement of components and routing between these components. Single row routing problem is a combinatorial optimization problem of significant importance for the design of complex VLSI multi layer printed circuit boards (PCB's). The design involves conductor routing that makes all the necessary wiring and interconnections between the PCB modules, such as pins, vias, and backplanes. In very large systems, the number of interconnections may exceed tens of thousands. Therefore, we have to optimize the wire routing and interconnections and thus determine the efficient designs. Kernighan-Lin algorithm, traveling salesman problem, simulated annealing algorithm and single row routing problem are used to find the best design. Included here are some simple examples to find the results. A simulation program using Microsoft Visual C++ is developed to simulate the single row routing problem using the simulated annealing algorithm. Keywords: Placement and Routing in VLSI; Single Row Routing; Kernighan-Lin Algorithm; Simulated Annealing