Performance of exhaustive search with parallel agents

The advent of high-performance computing via many-core processors and distributed processing emphasizes the possibility for exhaustive search by multiple search agents. Despite the occurrence of elegant algorithms for solving complex problems, exhaustive search has retained its significance since many real-life problems exhibit no regular structure and exhaustive search is the only possible solution. Here we analyze the performance of exhaustive search when it is conducted by multiple search agents. Several strategies for joint search with parallel agents are evaluated. We discover that the performance of the search improves with the increase in the level of mutual help between agents. The same search performance can be achieved with homogeneous and heterogeneous search agents provided that the lengths of subregions allocated to individual search regions follow the differences in the speeds of heterogeneous search agents. We also demonstrate how to achieve the optimum search performance by means of increasing the dimensions of the search region.

Anahtar Kelimeler:

Parallel algorithms, exhaustive search, multiagent systems

Performance of exhaustive search with parallel agents

Keywords:

Parallel algorithms, exhaustive search, multiagent systems,

PDF

___

J. Sanders, E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU programming, Boston, MA, USA, Addison-Wesley, 2010.
A. Grama, V. Kumar, “State of the art in parallel search techniques for discrete optimization problems”, IEEE Transactions on Knowledge and Data Engineering, Vol. 11, pp. 28–35, 1999.
E. Korpela, D. Werthimer, D. Anderson, J. Cobb, M. Lebofsky, “SETI@home–massively distributed computing for SETI”, Computing in Science and Engineering, Vol. 3, pp. 78–83, 2011.
A. Siemion, J.V. Korff, P. McMahon, E. Korpela, D. Werthimer, D. Anderson, G. Bower, J. Cobb, G. Foster, M. Lebofsky, J. van Leeuwen, M. Wagner, “New SETI sky surveys for radio pulses”, Acta Astronautica: Special Issue
on Searching for Life Signatures, Vol. 67, pp. 1342–1349, 2010.
W. Stallings, Cryptography and Network Security: Principles and Practice, Upper Saddle River, NJ, USA, Prentice Hall, 2005.
P.C. Cocher, “Breaking DES”, CryptoBytes, Vol. 4, pp. 1–5, 1999.
K. Appel, W. Haken, “The solution of the four-color-map problem”, Scientific American, Vol. 237, pp. 108–121, 1977.
Mersenne Research, Inc.“Great Internet Mersenne Prime Search”, online, available at http://www.mersenne.org/. [10] J. Nievergelt, “Exhaustive search, combinatorial optimization and enumeration: exploring the potential of raw computing power”, in SOFSEM 2000 LNCS 1963, pp. 18–35, 2000.
J. Nievergelt, R. Gasser, F. Mser, C. Wirth, “All the needles in a haystack: can exhaustive search overcome combinatorial chaos?”, Lecture Notes in Computer Science, Vol. 1000, pp. 254–274, 1995.
V. Kumar, “Algorithms for constraint satisfaction problems: a survey”, AI Magazine, Vol. 13, pp. 32–44, 1992.
A. Masegosa, D. Pelta, I. del Amo, J. Verdegay, “On the performance of homogeneous and heterogeneous cooperative search strategies”, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2008), Vol. 236, pp. 287–300, 2009.
A. Masegosa, PhD, “Cooperative methods in optimisation: analysis and results”, University of Granada, Granada, Spain, 2010.
T. Stojanovski, L. Krstevski, “On the performance of exhaustive search with cooperating agents”, ETAI Conference, Ohrid, Macedonia, 2011.
R. Smith, R. Minton, Calculus: Multivariable, New York, NY, USA, McGraw-Hill Education, 2001.
N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller, “Equation of state calculations by fast computing machines”, Journal of Chemical Physics, Vol. 21, pp. 1087–1092, 1953.