Efficient parallel algorithms for search problems: Applications in VLSI CAD

Sunil Arvindam; Vipin Kumar; V. Nageshwara Rao

Efficient parallel algorithms for search problems: Applications in VLSI CAD

Sunil Arvindam, Vipin Kumar, V. Nageshwara Rao

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proc 3 Symp Front Massively Parallel Comput Frontiers 90
Publisher	Publ by IEEE
Pages	166-169
Number of pages	4
ISBN (Print)	0818620536
State	Published - 1990
Event	Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 - College Park, MD, USA Duration: Oct 8 1990 → Oct 10 1990

Publication series

Name	Proc 3 Symp Front Massively Parallel Comput Frontiers 90

Other

Other	Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90
City	College Park, MD, USA
Period	10/8/90 → 10/10/90

Find It

Find It at U of M Libraries

Cite this

Arvindam, S, Kumar, V & Nageshwara Rao, V 1990, Efficient parallel algorithms for search problems: Applications in VLSI CAD. in Proc 3 Symp Front Massively Parallel Comput Frontiers 90. Proc 3 Symp Front Massively Parallel Comput Frontiers 90, Publ by IEEE, pp. 166-169, Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90, College Park, MD, USA, 10/8/90.

@inproceedings{35f9056be40c43739ad4361457ade17c,

title = "Efficient parallel algorithms for search problems: Applications in VLSI CAD",

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.",

author = "Sunil Arvindam and Vipin Kumar and {Nageshwara Rao}, V.",

year = "1990",

language = "English (US)",

isbn = "0818620536",

series = "Proc 3 Symp Front Massively Parallel Comput Frontiers 90",

publisher = "Publ by IEEE",

pages = "166--169",

booktitle = "Proc 3 Symp Front Massively Parallel Comput Frontiers 90",

note = "Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 ; Conference date: 08-10-1990 Through 10-10-1990",

}

TY - GEN

T1 - Efficient parallel algorithms for search problems

T2 - Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90

AU - Arvindam, Sunil

AU - Kumar, Vipin

AU - Nageshwara Rao, V.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025547741&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025547741&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0025547741

SN - 0818620536

T3 - Proc 3 Symp Front Massively Parallel Comput Frontiers 90

SP - 166

EP - 169

BT - Proc 3 Symp Front Massively Parallel Comput Frontiers 90

PB - Publ by IEEE

Y2 - 8 October 1990 through 10 October 1990

ER -

Efficient parallel algorithms for search problems: Applications in VLSI CAD

Abstract

Publication series

Other

Find It

Other files and links

Fingerprint

Cite this