Browse Prior Art Database

A CLASS OF CELLULAR ARCHITECTURES TO SUPPORT PHYSICAL DESIGN AUTOMATION

IP.com Disclosure Number: IPCOM000128449D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

R.A. Rutenbar: AUTHOR [+5]

Abstract

Special-purpose hardware has been proposed as a solution to several increasingly complex problems in design automation. This paper examines a class of cellular architectures -- called raster pipeline subarrays -- applicable to physical design automation problems represented on a cellular grid. Machines with this architecture were first employed for cellular image processing, and many similarities exist between problems in grid-based DA and problems in cellular image processing and pattern recognition. A review of machines designed for cellular image processing shows how DA machines proposed/constructed for grid-based problems fit naturally into a taxonomy of image processors; a review of some of the mathematical tools developed to formalize pattern recognition problems shows how they can be usefully applied to DA problems. Implementations of design rule checking and routing algorithms are described in detail for an existing raster pipeline subarray machine called a cytocomputer. Experimental results using this hardware are encouraging, and extensions to large, practical problems are studied. Based upon these studies we define the architecture and necessary performance characteristics of a raster pipeline subarray machine optimized specifically for grid-based DA applications. The merits of such an architecture are evaluated in the context of practical special-purpose hardware.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 28

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A CLASS OF CELLULAR ARCHITECTURES TO SUPPORT PHYSICAL DESIGN AUTOMATION

R. A. Rutenbar, T.N. Mudge and D.E. Atkins

CRL-TR-10-83

FEBRUARY l983

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 Room 1079, East Engineering Building
Ann Arbor, Michigan 43109
USA
Tel: (313) 763-8000

A Class of Cellular Architectures to Support Physical Design Automation by
R. A. Rutenbar, T. N. Mudge and D. E. Atkins

Computing Research Laboratory
Department of Electrical and Computer Engineering University of Michigan
Ann Arbor, MI

Abstract

Special-purpose hardware has been proposed as a solution to several increasingly complex problems in design automation. This paper examines a class of cellular architectures -- called raster pipeline subarrays -- applicable to physical design automation problems represented on a cellular grid. Machines with this architecture were first employed for cellular image processing, and many similarities exist between problems in grid-based DA and problems in cellular image processing and pattern recognition. A review of machines designed for cellular image processing shows how DA machines proposed/constructed for grid-based problems fit naturally into a taxonomy of image processors; a review of some of the mathematical tools developed to formalize pattern recognition problems shows how they can be usefully applied to DA problems. Implementations of design rule checking and routing algorithms are described in detail for an existing raster pipeline subarray machine called a cytocomputer. Experimental results using this hardware are encouraging, and extensions to large, practical problems are studied. Based upon these studies we define the architecture and necessary performance characteristics of a raster pipeline subarray machine optimized specifically for grid-based DA applications. The merits of such an architecture are evaluated in the context of practical special-purpose hardware.

Key words -- design automation, special-purpose hardware, design rule checking, routing, image-processing.

1. Introduction

1 This work was supported in part by NSF Grant No. MCS-8009315 and MCS-8007298. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

University of Michigan Computing Research Laboratory Page 1 Feb 01, 1983

Page 2 of 28

A CLASS OF CELLULAR ARCHITECTURES TO SUPPORT PHYSICAL DESIGN AUTOMATION

2 The successful implementation of increasingly complex integrated systems has been made possible only because of the existence of increasingly sophisticated CAD tools. Traditional CAD research -- for example, the mathematical analysis of design automation (DA) algorithms and data-structures, the application of software structuring techniques to chip layout, and the use of data bases to manage the design process -- has resulted in the product...