Title
Gate Matrix Layout Revisited: Algorithmic Performance And Probabilistic Analysis
Abbreviated Journal Title
Lect. Notes Comput. Sci.
Keywords
Computer Science; Theory & Methods
Abstract
We consider the gate matrix layout problem for VLSI design, and improve the time and space complexities of an existing dynamic programming algorithm for its exact solution. Experimental study indicates the requirement of enormous computation time for exact solutions of even small size matrices. We derive an expression for the expected number of tracks required to layout in gate matrix style based on a probabilistic model. A local search approximation algorithm is studied experimentally and found to perform reasonably well on average.
Journal Title
Lecture Notes in Computer Science
Volume
405
Publication Date
1-1-1989
Document Type
Article
Language
English
First Page
280
Last Page
290
WOS Identifier
ISSN
0302-9743
Recommended Citation
Das, Sajal K.; Deo, Narsingh; and Prasad, Sushil, "Gate Matrix Layout Revisited: Algorithmic Performance And Probabilistic Analysis" (1989). Faculty Bibliography 1980s. 765.
https://stars.library.ucf.edu/facultybib1980/765
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu