A distributed design rule checker for VLSI layouts

Abstract

VLSI technology is continually fueling the need for more efficient computer aided design tools. Parallel or distributed processing is a possible solution to this problem. Advances in computer networking have made distributed processing over a local area network very attractive and cost-effective. This research investigates the application of such a large-grained parallel processing method to the task of checking geometric constraints or design rules that are imposed on the layout of VLSI circuits to ensure a correct implementation of the design despite imperfections in the fabrication process. The thesis begins with a study of design rule checking algorithms including algorithms for parallel processing as applied to design rule checking. Then, the algorithms for a technology independent design rule verification tool are developed. For distributed processing, two separate approaches are examined. One approach, called the data partitioning method, divides a fully instantiated or non-hierarchical layout into several sections and then processes each section on a different computer. The second approach looks for smaller tasks within the design rule checking process that can be executed in parallel and is called the task partitioning method. A dynamic task-scheduling algorithm is used to assign the tasks to the available processors. Implementations of both of these parallel processing schemes on a local area network of workstations are described. Experiments are performed to assess the performance of the programs and the results of testing a few layouts are presented.