Performance of exhaustive search with parallel agents

Authors: TONI DRAGANOV STOJANOVSKI

Abstract: 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.

Keywords: Parallel algorithms, exhaustive search, multiagent systems

Full Text: PDF