If you are experiencing problems downloading PDF or HTML fulltext, our helpdesk recommend clearing your browser cache and trying again. If you need help in clearing your cache, please click here . Still need help? Email help@ingentaconnect.com

A Nonoblivious Bus Access Scheme Yields an Optimal Partial Sorting Algorithm

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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 m th 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 (9 m / k ) log 2 log 2 n + 3.467 $$\sqrt{n/k}\$$ + O ( m / k + ( n / k ) 1/4 ) of the proposed algorithm matches a lower bound Omega ( $$\sqrt{n/k}\$$ + m / k ) with respect to n and k , if m is small enough to satisfy m = O ( $$\sqrt{nk}\$$ /log log n ).

Document Type: Research Article

Affiliations: Faculty of Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashi-Hiroshima, 739, Japan

Publication date: April 1, 1996

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more