Parallel bidirectional A* search on a symmetry multiprocess

Andrew Sohn

Parallel bidirectional A* search on a symmetry multiprocess

Andrew Sohn

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

This report presents our experiences parallelizing and implementing search problems. We take the sequential A* search and parallelize it by combining with bidirectional search, called Parallel Bidirectional A* Search (PBiA*S). To identify the effectiveness of the PBiA*S, we implement two search problems, the Eight Puzzle and the Tower of Hanoi, on a Symmetry multiprocessor. Execution results demonstrate that the PBiA*S can be an effective parallel search method as it gives two to 12-fold speedup over the unidirectional A* search for the two search problems.

Original language	English (US)
Title of host publication	Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
Editors	Anon
Publisher	Publ by IEEE
Pages	19-22
Number of pages	4
ISBN (Print)	081864222X
State	Published - Dec 1 1993
Event	Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA Duration: Dec 1 1993 → Dec 4 1993

Other

Other	Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
City	Dallas, TX, USA
Period	12/1/93 → 12/4/93

All Science Journal Classification (ASJC) codes

Engineering(all)

Cite this

@inproceedings{89c32a58072248f7ae808b0c4bb865c6,

title = "Parallel bidirectional A* search on a symmetry multiprocess",

abstract = "This report presents our experiences parallelizing and implementing search problems. We take the sequential A* search and parallelize it by combining with bidirectional search, called Parallel Bidirectional A* Search (PBiA*S). To identify the effectiveness of the PBiA*S, we implement two search problems, the Eight Puzzle and the Tower of Hanoi, on a Symmetry multiprocessor. Execution results demonstrate that the PBiA*S can be an effective parallel search method as it gives two to 12-fold speedup over the unidirectional A* search for the two search problems.",

author = "Andrew Sohn",

year = "1993",

month = dec,

day = "1",

language = "English (US)",

isbn = "081864222X",

pages = "19--22",

editor = "Anon",

booktitle = "Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing",

publisher = "Publ by IEEE",

note = "Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing ; Conference date: 01-12-1993 Through 04-12-1993",

}

TY - GEN

T1 - Parallel bidirectional A* search on a symmetry multiprocess

AU - Sohn, Andrew

PY - 1993/12/1

Y1 - 1993/12/1

N2 - This report presents our experiences parallelizing and implementing search problems. We take the sequential A* search and parallelize it by combining with bidirectional search, called Parallel Bidirectional A* Search (PBiA*S). To identify the effectiveness of the PBiA*S, we implement two search problems, the Eight Puzzle and the Tower of Hanoi, on a Symmetry multiprocessor. Execution results demonstrate that the PBiA*S can be an effective parallel search method as it gives two to 12-fold speedup over the unidirectional A* search for the two search problems.

AB - This report presents our experiences parallelizing and implementing search problems. We take the sequential A* search and parallelize it by combining with bidirectional search, called Parallel Bidirectional A* Search (PBiA*S). To identify the effectiveness of the PBiA*S, we implement two search problems, the Eight Puzzle and the Tower of Hanoi, on a Symmetry multiprocessor. Execution results demonstrate that the PBiA*S can be an effective parallel search method as it gives two to 12-fold speedup over the unidirectional A* search for the two search problems.

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

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

M3 - Conference contribution

AN - SCOPUS:0027874123

SN - 081864222X

SP - 19

EP - 22

BT - Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

Y2 - 1 December 1993 through 4 December 1993

ER -

Parallel bidirectional A* search on a symmetry multiprocess

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this