Efficient parallel algorithms for search problems: Applications in VLSI CAD

Sunil Arvindam, Vipin Kumar, V. Nageshwara Rao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProc 3 Symp Front Massively Parallel Comput Frontiers 90
PublisherPubl by IEEE
Pages166-169
Number of pages4
ISBN (Print)0818620536
StatePublished - Dec 1 1990
EventProceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 - College Park, MD, USA
Duration: Oct 8 1990Oct 10 1990

Publication series

NameProc 3 Symp Front Massively Parallel Comput Frontiers 90

Other

OtherProceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90
CityCollege Park, MD, USA
Period10/8/9010/10/90

Fingerprint Dive into the research topics of 'Efficient parallel algorithms for search problems: Applications in VLSI CAD'. Together they form a unique fingerprint.

Cite this