An Architecture for Bitonic Sorting with Optimal VLSI Performnance

Abstract

We propose a class of designs of a new interconnection network, the pleated cube-connected cycles (PCCC), which can impleement stable bitonic sorting of n records of size q in area A = O(q <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /T <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), where T, the computation time, is in the range [Ω(q log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n), O(q √n/(q+ log n))]. Thus, this network is an AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2,/R</sup> -optimal bitonic sorter in the synchronous VLSI model of computation under the word-local restriction.