Modeling and search complexity in multiprocessor systems

There exist at least two methods to program searching in multiprocessor systems. The former (separative) method assumes separation of data and subsequent independent treatment by each processor of its own part of data. The latter (cooperative) method assumes sharing data and processor power. In this research, we give a mathematical model of parallel searching algorithms; in the framework of this model we study parallel solution of search problems with a search relation which is a linear quasi-order relation. We suggest a method to separate data in an optimal way and demonstrate that the separative approach, generally speaking, does not provide us with the optimal solution: we give an example of a search problem with a linear quasi-order relation for which the cooperative approach yields a better result.
This research was supported by the Russian Foundation for Basic Research, grants 95–01–00597 and 98–01–00130.