Geodesic
Modeling and search complexity in multiprocessor systems
Diskretnaya Matematika, Tome 11 (1999) no. 3, pp. 63-82.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_1999_11_3_a5,
     author = {\`E. \`E. Gasanov and E. R. Erokhina},
     title = {Modeling and search complexity in multiprocessor systems},
     journal = {Diskretnaya Matematika},
     pages = {63--82},
     publisher = {mathdoc},
     volume = {11},
     number = {3},
     year = {1999},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1999_11_3_a5/}
}
TY  - JOUR
AU  - È. È. Gasanov
AU  - E. R. Erokhina
TI  - Modeling and search complexity in multiprocessor systems
JO  - Diskretnaya Matematika
PY  - 1999
SP  - 63
EP  - 82
VL  - 11
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1999_11_3_a5/
LA  - ru
ID  - DM_1999_11_3_a5
ER  - 
%0 Journal Article
%A È. È. Gasanov
%A E. R. Erokhina
%T Modeling and search complexity in multiprocessor systems
%J Diskretnaya Matematika
%D 1999
%P 63-82
%V 11
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1999_11_3_a5/
%G ru
%F DM_1999_11_3_a5
È. È. Gasanov; E. R. Erokhina. Modeling and search complexity in multiprocessor systems. Diskretnaya Matematika, Tome 11 (1999) no. 3, pp. 63-82. http://geodesic.mathdoc.fr/item/DM_1999_11_3_a5/