Browse Prior Art Database

A Systolic Design Rule Checker

IP.com Disclosure Number: IPCOM000128570D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

Rajiv Kane: AUTHOR [+4]

Abstract

Rapid advances in technology are making it possible to fabricate circuits of an ever increasing complexity. This increase in circuit complexity poses a severe challenge to the algorithms presently in use in design automation tools. One of the ways to meet the challenge is to develop new computer architechures capable of running these design automation algorithms efficiently. Another approach is to develop yet faster algorithms. Several new architectures and corresponding algorithms have recently been proposed for design automation. Blank et al [BLAN81] describe a bit map processor architecture suitable for boalean operations, wire routing using Lee's algorithm, and for some design rule check (DRC) functions such as shrink and expand. Mudge et al [NlUDG$2] describe Cytocomputer architecture adapted for DRC and Lee type wire routing. Yet another DRC architecture is described in [SEIL82]. Some other references far special purpose architectures and associ-ated algorithms for wire routing are [DAMNI82] and [NAIR82]. A parallel process-ing approach for logic module placement has been developed by Ueda et al [UEDA83]. Simulation has also been the focus of several new architectural stu-dies. The most popular such development is the Yorktown Simulation Engine ([PFIS82], [DENN82], and [KRON82]). Another logic simulation machine is described by Abrarnovici et a1 [ABRA82]. In this paper, we shall be concerned with the design of a systolic system for design rule checks, Our design differs from all earlier work on special purpose architectures for design automation in that ours is the first systolic design. Of course, systolic designs have been stu died for quite some time. A valuable reference is [KUNG82]. Our systolic system for DRC's differs from earlier work on hardware assisted DRG's in that it is edge based rather than bit map based. Consequently, it has the potential of being much faster than earlier designs. . Specifically, our systolic design rule checker (SDRC) checks for spacing and width errors. The design may be extended to include other design rule checks. Our design points out the potential for systolic systems in design automation applications.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Systolic Design Rule Checker

Rajiv Kane Sartaj Sahni

Computer Science Department

Institute of Technology

136 Lind Hall

University of Minnesota

Minneapolis, Minnesota 55455 "

Technical Report 83-13

July 1983 s~ 00 ,fit

1. Introduction

Rapid advances in technology are making it possible to fabricate circuits of an ever increasing complexity. This increase in circuit complexity poses a severe challenge to the algorithms presently in use in design automation tools. One of the ways to meet the challenge is to develop new computer architechures capable of running these design automation algorithms efficiently. Another approach is to develop yet faster algorithms. Several new architectures and corresponding algorithms have recently been proposed for design automation. Blank et al [BLAN81] describe a bit map processor architecture suitable for boalean operations, wire routing using Lee's algorithm, and for some design rule check (DRC) functions such as shrink and expand. Mudge et al [NlUDG$2] describe Cytocomputer architecture adapted for DRC and Lee type wire routing. Yet another DRC architecture is described in [SEIL82]. Some other references far special purpose architectures and associ-ated algorithms for wire routing are [DAMNI82] and [NAIR82]. A parallel process-ing approach for logic module placement has been developed by Ueda et al [UEDA83]. Simulation has also been the focus of several new architectural stu-dies. The most popular such development is the Yorktown Simulation Engine ([PFIS82], [DENN82], and [KRON82]). Another logic simulation machine is described by Abrarnovici et a1 [ABRA82]. In this paper, we shall be concerned with the design of a systolic system for design rule checks, Our design differs from all earlier work on special purpose architectures for design automation in that ours is the first systolic design. Of course, systolic designs have been stu died for quite some time. A valuable reference is [KUNG82]. Our systolic system for DRC's differs from earlier work on hardware assisted DRG's in that it is edge based rather than bit map based. Consequently, it has the potential of being much faster than earlier designs. . Specifically, our systolic design rule checker (SDRC) checks for spacing and width errors. The design may be extended to include other design rule checks. Our design points out the potential for systolic systems in design automation applications.

2. Polygons and Errors

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 13

A Systolic Design Rule Checker

In arriving at our SDRC, we made several assumptions on the nature of the polygon to be handled and also on the type of errors to be checked for. First, we assume that polygons are composed of horizontal and vertical edges only. Hence, only right angled bends are permitted. Polygons may contain holes. These holes are also restricted to be polygons with right angled bends. Figure 1 sho...