Efficient parallel algorithms for search problems: applications in VLSI CAD

Author

Arvindam, Sunil ; Kumar, Vipin ; Rao, V. Nageshwara

Author_Institution

Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA

fYear

1990

fDate

8-10 Oct 1990

Firstpage

166

Lastpage

169

Abstract

Experimental results are presented to demonstrate that it is possible to speed up search-based algorithms by several orders of magnitude. Highly optimized sequential programs were first implemented in the C language for two applications: floor plan verification and tautology verification. Then parallel programs were developed for the Ncube by modifying the sequential programs to incorporate dynamic load balancing. The speedups obtained on 1024 processors ranged from 430 to 1099 for floor plan optimization, with larger problems showing higher speedups. For tautology verification the speedup on 1024 processors ranged from 564 to 1007, with larger problems again showing higher speedups

Keywords

VLSI; circuit layout CAD; parallel algorithms; parallel programming; search problems; C language; Ncube; VLSI CAD; dynamic load balancing; floor plan optimization; floor plan verification; parallel algorithms; parallel programs; search problems; search-based algorithms; tautology verification; Algorithm design and analysis; Application software; Artificial intelligence; Computer science; Design automation; Hypercubes; Parallel algorithms; Problem-solving; Search problems; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Frontiers of Massively Parallel Computation, 1990. Proceedings., 3rd Symposium on the

Conference_Location

College Park, MD

Print_ISBN

0-8186-2053-6

Type

conf

DOI

10.1109/FMPC.1990.89455

Filename

89455