PARALLEL SORTING ALGORITHMS ON A HYPER-CHANNEL BROADCAST COMMUNICATION MODEL

This paper presents a new improved architecture, named a hyper-channel broadcast communication model, as a computational model. The hyper-ch annel broadcast communication model consists of processors shared by s ome channels, and there are no local links between processors. Based o n such an improved architecture, Ne first design two O(log N) cycles b asic operations for finding the maximum/minimum of N real numbers and the ranks of a linked list using N and N x N processors, respectively. Then based on these proposed operations, two O(log N) cycles sorting algorithms are derived by either using N x N processors for the concur rent-write case or using N x N x N processors for the conflict-free ca se, respectively.