A Nonoblivious Bus Access Scheme Yields an Optimal Partial Sorting Algorithm

✍ Scribed by Satoshi Fujita; Masafumi Yamashita

• Book ID: 102602697
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 286 KB
• Volume: 34
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0049

✦ Synopsis

This paper focuses on a linear array of n nodes with multiple shared buses as a practically feasible model for parallel processing. Let k be the number of shared buses. A nonoblivious scheme for mutually exclusive access to k shared buses is proposed. The effectiveness of the scheme is demonstrated by proposing an algorithm for solving a partial sort problem, which can be efficiently executed on the array according to the scheme. The partial sort problem with parameter m is the problem of sorting a subset S of a given set S, where S is the set of elements less than or equal to the mth smallest element in S. If m ‫؍‬ 1, then it is solved by an algorithm for finding the smallest element in S, and if m ‫؍‬ n, then it is solved by adapting normal sorting algorithm. The time complexity (9m/k) log 2 log 2 n ؉ 3.467 ͙n/k ؉ O(m/k ؉ (n/k) 1/4 ) of the proposed algorithm matches a lower bound ⍀ (͙n/k ؉ m/k) with respect to n and k, if m is small enough to satisfy m ‫؍‬ O(͙nk/log log n).