Files in this item



application/pdf9136553.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Parallel algorithms for placement and routing in VLSI design
Author(s):Brouwer, Randall Jay
Doctoral Committee Chair(s):Banerjee, Prithviraj
Department / Program:Electrical and Computer Engineering
Discipline:Electrical and Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
Abstract:The computational requirements for high quality synthesis, analysis, and verification of VLSI designs have rapidly increased with the fast growing complexity of these designs. Past research has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. In this thesis, we propose two new parallel algorithms for two VLSl synthesis tasks, standard cell placement and global routing.
The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained.
The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, we present results which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs, and we present measurements on the parallel speedups available.
Issue Date:1991
Rights Information:Copyright 1991 Brouwer, Randall Jay
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9136553
OCLC Identifier:(UMI)AAI9136553

This item appears in the following Collection(s)

Item Statistics