MULTI-LEVEL PARALLEL FRAMEWORK

Authors

  • Mitica Craus
  • Laurentiu Rudeanu

DOI:

https://doi.org/10.47839/ijc.3.3.301

Keywords:

Parallel Algorithms, Framework, Message Passing Interface, Traveling Salesman Problem, Ant Colony

Abstract

This article deals with the pyramidal framework designed to be used in the parallelization of the ant-like algorithms. Such algorithms have several things in common: they run in cycles and the process can be divided among different "processing units". The parallel implementation of the Ant Colony Optimization algorithm for the Traveling Salesman Problem is an application of this system. The topology of the framework architecture is similar to a B-tree and contains three types of processing nodes: a single master (the root), several sub-masters corresponding to the internal nodes of the tree and several slaves as leaves. First the master reads the problem instance, wraps it up in a message that is sent to all the other processing nodes and initializes the central data structures. Then, the slaves take over the control by starting the algorithm while the master and the sub-masters are waiting for requests to update the data. The framework has an object-oriented design and was implemented in C++, using the MPI library.

References

M. Dorigo and G. D. Caro. Ant algorithms for discrete optimization, Artificial Life, no. 5 (1999), pp. 137-172.

P. Delisle, M. Krajecki, M. Gravel, and C. Gagne. Parallel implementation of an ant colony optimization metaheuristic with OpenMP, Proceedings of the 3rd European Workshop on OpenMP (EWOMP’01), Barcelona, Spain, 2001.

T. Stutzle. Parallelization strategies for ant colony optimization, Lecture Notes in Computer Science, vol. 1498 (1998), pp. 722-731.

E. Ghazali Talbi, O. Roux, C. Fonlupt, and D. Robillard. Parallel ant colonies for combinatorial optimization problems, Lecture Notes in Computer Science, vol. 1586 (1999), pp. 239-247.

B. Bullnheimer, G. Kostis, and C. Strauss. Parallelization strategies for the ant system, High Performance Algorithms and Software in Non-linear Optimization (R. D. L. et all., ed.), Applied Optimization, vol. 24 (1998), pp. 87-100.

D. A. L. Piriyakumar and P.Levi. A new approach to explointing parallelism in ant colony optimization'', 2001.

M. Craus and L.Rudeanu. Parallel Framework for Ant-like Algorithms, Proceedings of the 3rd International Symposium on Parallel and Distributed Computing (ISPDC 2004), Cork, Ireland, July 5th-7th 2004, pp. 36-41.

Downloads

Published

2014-08-01

How to Cite

Craus, M., & Rudeanu, L. (2014). MULTI-LEVEL PARALLEL FRAMEWORK. International Journal of Computing, 3(3), 20-28. https://doi.org/10.47839/ijc.3.3.301

Issue

2004, Volume 3, Issue 3

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    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.
•    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.