Parallel algorithms on a mesh with multiple broadcasting

Parallel algorithms on a mesh-connected computer with multiple broadcasting mechanism are presented. The solution times of these algorithms are superior to those obtained on a mesh without broadcasting or a mesh with single global broadcasting. The results show that the time required to solve even simple problems can be reduced by careful analysis and design. It is assumed that a broadcast reaches all processors in a row or a column in constant time, t_b. In practice, broadcasting may take t _blog n time. In this case, the time complexity for the algorithms discussed becomes O(n^{1 2}log n). Another extension is to allow multiple access to a broadcast bus; for example, all processing elements (PEs) can broadcast a bit simultaneously. Such schemes are physically realizable. Thus the sum of a row of PEs can be found in O(m) steps, where m is the length of the words. Therefore the time required for sorting n elements and selecting the kth largest number on an n×n mesh with such schemes can be further reduced