Nonnumeric search results on the EM-4 distributed-memory multiprocessor

Andrew Sohn, Mitsuhisa Sato, Shuichi Sakai, Yuetsu Kodama, Yoshinori Yamaguchi

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

Numeric scientific problems have been the main focus of supercomputing as their numerous implementations on various multiprocessors indicate. Nonnumeric problems on the other hand have received very little attention for parallel implementation due to their irregular behaviors and a large amount of resource usage. This report presents our experiences implementing difficult nonnumeric problems on the EM-4 multiprocessor, believing that supercomputers should also be able to effectively execute nonnumeric problems if they are to be considered 'supercomputers.' We selected two typical search problems, the Eight-Puzzle and the Tower-of-Hanoi. Two parallel search techniques are used to implement the search problems, unidirectional and bidirectional heuristic search. A total of eight different programs has been implemented on the EM-4 multiprocessor with realistic problem sizes. Execution results demonstrate that the parallel bidirectional heuristic search can solve the tree depth 20 to 40 of the Eight-Puzzle in an optimal or near optimal number of iterations in less than two seconds, and is highly scalable as it gives over 40-fold speedup for both problems on 80 processors.

Original languageEnglish (US)
Pages (from-to)301-310
Number of pages10
JournalProceedings of the ACM/IEEE Supercomputing Conference
DOIs
StatePublished - 1994
EventProceedings of the 1994 Supercomputing Conference - Washington, DC, USA
Duration: Nov 14 1994Nov 18 1994

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Nonnumeric search results on the EM-4 distributed-memory multiprocessor'. Together they form a unique fingerprint.

Cite this