Scalable algorithms for the mesh with buses: merging, sorting and selection

Abstract

Efficient scalable algorithms are developed for a mesh with fixed buses. The problems considered are merging, sorting and selection. The size of the input is fixed at n and the mesh size is varied from √n × √nto n ×n. The merging algorithm is optimal for all the mesh sizes, whereas the sorting and selection algorithms are within factors of (1/(1 − ϵ)) and log^4/3 nrespectively, of the optimal.

Keywords:

• Mesh connected computers
• merging
• sorting
• selection

C.R. Categories:

• F.2.3
• C 1.2

^* [email protected]

^* [email protected]

Notes

^* [email protected]