Implementation of Discrete Search Optimization Algorithms in Parallel and Their Performance Analysis

Muhammad Hanif Durad, Mohammad Zulqurnain, Anila Usman, Idrees Ahmad


The present paper discusses the implementation of the discrete search optimization techniques on a parallel platform (SGI-Altix 450 shared memory 64 processors system). We show that the combination of Asynchronous Parallel Iterative Deepening and Parallel Window Search technique tends to give more challenging speedups, memory consumption, and efficiency with less resource consumption as compared to the rest of the techniques. In general 5 techniques are compared with Parallel Asynchronous Window Search technique among which includes Depth First Search, Parallel Iterative Deepening, Parallel  A*, Parallel Window Search and  Parallel Asynchronous Iterative Deepening A*.

Full Text:



Cook, D. J., & Lyons, G. (1993). Massively parallel IDA* search. International Journal on Artificial Intelligence Tools, 2(02), 163-180.

Rao, V. N., Kumar, V., & Ramesh, K. (1987). A parallel implementation of iterative-deepening-A (pp. 178-182). Artificial Intelligence Laboratory, University of Texas at Austin.

Evett, M., Hendler, J., Mahanti, A., & Nau, D. (1995). PRA*: Massively parallel heuristic search. Journal of Parallel and Distributed Computing, 25(2), 133-143.

Mahanti, A., & Daniels, C. J. (1991). Simd parallel heuristic search.

Nerur, S., & Cook, D. J. (1994, May). A hybrid parallel-window/distributed tree algorithm for improving the performance of search-related tasks. In Proceedings of the 7th international conference on Industrial and engineering applications of artificial intelligence and expert systems (pp. 629-637).

Fenton, W., Rankumar, B., Salctore, V. A., Sinha, A. B., & Kale, L. V. (1991, August). Supporting machine independent parallel programming on diverse architectures. In proceedings of 1991 International Conference on Parallel Processing, pp. II-193-201, Boca Raton, Florida.

Reinefeld, A., & Schnecke, V. (1994, May). AIDA^*-Asynchronous Parallel IDA^. In Proceedings of the Biennial Conference-Canadian Society for Computational Studies of Intelligence (pp. 295-302). Canadian Information Processing Society.

Reinefeld, A., & Marsland, T. A. (1994). Enhanced iterative-deepening search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(7), 701-710.

Ibrahim, M. A., Xinda, L., & Rwakarambi, J. M. (2001, January). Parallel execution of an irregular algorithm depth first search (DFS) on heterogeneous clusters of workstation. In 2001 International Conferences on Info-Tech and Info-Net. Proceedings (Cat. No. 01EX479) (Vol. 3, pp. 328-332). IEEE.

Powley, C., & Korf, R. E. (1991). Single-agent parallel window search. IEEE Transactions on Pattern Analysis & Machine Intelligence, (5), 466-477.

Reinefeld, A., & Schnecke, V. (1994, May). Work-load balancing in highly parallel depth-first search. In Proceedings of IEEE Scalable High Performance Computing Conference (pp. 773-780). IEEE.

Grama, A., Kumar, V., Gupta, A., & Karypis, G. (2003). Introduction to parallel computing. Pearson Education.



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.