An Optimal Sorting Algorithm on a Linear Array with Reconfigurable Pipelined Bus System

摘要

Optical interconnections attract many researchers' attention because of their potential for gigahertz transfer rates and concurrent access to the bus in a pipelined fashion. The power of such interconnection networks gives us the opportunity to reconsider traditional algorithms. Prom this point of view, we studied an optimal sorting algorithm - Cole's optimal CREW PRAM sorting[1], and implement the idea in an innovative way on an optical interconnection model, the LARPBS model[3]. We show how to implement this algorithm using only several basic operations designed for LARPBS, and give a solution on processor assignment and processor reusing. We discovered several new properties of this sorting algorithm and present them as lemmas in the paper. Reconfigurability of the LARPBS model is used in different ways to accomplish special communication and computation goals efficiently. Our sorting algorithm on the LARPBS model achieves an optimal time complexity of O(log n) using O(n) processors. This algorithm is optimal, considering the number of comparisons required is O(n log n) which is the same as the sequential complexity of the problem.