Task scheduling for exploiting parallelism and hierarchy in VLSI CAD algorithms

Author

Belkhale, Krishna P. ; Brouwer, Randall J. ; Banerjee, Prithviraj

Author_Institution

Illinois Univ., Urbana, IL, USA

Volume

12

Issue

5

fYear

1993

fDate

5/1/1993 12:00:00 AM

Firstpage

557

Lastpage

567

Abstract

Two approaches to handling the computational requirements of computer-aided design problems are considered. One approach is to take advantage of the hierarchical nature of circuit design and develop hierarchical CAD algorithms. Another involves the use of parallel processing and development of parallel CAD algorithms. How these two approaches can be combined to speed up various CAD applications is discussed. Toward this goal, two general problems in scheduling are solved: parallelizable independent task scheduling (PITS) and parallelizable dependent task scheduling (PDTS). The PITS scheduling theory is applied to a parallel hierarchical circuit extractor, and the PDTS scheduling theory is applied to a parallel hierarchical global router. Both implementations show speedups of about six on eight processors of a shared-memory multiprocessor

Keywords

VLSI; circuit CAD; circuit layout CAD; integrated circuit technology; parallel algorithms; scheduling; VLSI CAD algorithms; computer-aided design; parallel hierarchical circuit extractor; parallel hierarchical global router; parallel processing; shared-memory multiprocessor; task scheduling; Algorithm design and analysis; Circuit synthesis; Concurrent computing; Design automation; Helium; Parallel processing; Processor scheduling; Routing; Scheduling algorithm; Very large scale integration;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.277604

Filename

277604