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

Authors

  • Muhammad Hanif Durad Department of Computer and Information Sciences, Pakistan Institute of Engineering and Applied Sciences (PIEAS), Islamabad
  • Mohammad Zulqurnain Department of Computer and Information Sciences, Pakistan Institute of Engineering and Applied Sciences (PIEAS), Islamabad
  • Anila Usman Department of Computer and Information Sciences, Pakistan Institute of Engineering and Applied Sciences (PIEAS), Islamabad
  • Idrees Ahmad Department of Nuclear Engineering Pakistan Institute of Engineering and Applied Sciences (PIEAS), Islamabad

DOI:

https://doi.org/10.21015/vtm.v8i1.576

Abstract

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

References

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.

Downloads

Published

2020-11-18

How to Cite

Durad, M. H., Zulqurnain, M., Usman, A., & Ahmad, I. (2020). Implementation of Discrete Search Optimization Algorithms in Parallel and Their Performance Analysis. VFAST Transactions on Mathematics, 8(1), 45–53. https://doi.org/10.21015/vtm.v8i1.576

Issue

Vol. 8 No. 1 (2020): January-December

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC-By) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

                                      

This work is licensed under a Creative Commons Attribution  License CC BY