WestminsterResearch

Sorting without exchanges on a bit-serial systolic array

Megson, Graham M. (1990) Sorting without exchanges on a bit-serial systolic array. Circuits, Devices and Systems, IEE Proceedings G, 137 (5). pp. 345-352. ISSN 0956-3768

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumbe...

Abstract

The author considers, a number of bit-serial systolic designs for ordering a list of n elements without 'on-the-fly' exchanges are considered. The algorithms require 4n+p+k bit steps where p=log2 n and k is the number of bits required to encode all the possible elements. The arrays require O(n(p+k)) bit cells with a complexity roughly the same as that of a full adder and between max (p,k) and p+k input/output pins. The input to the array is the list to be sorted and an auxiliary vector whose elements have bit length p. The output is the list itself and the auxiliary vector, which is updated to produce pointers to the correct position of each element in the ordered list.

Item Type:Article
Uncontrolled Keywords:VLSI, cellular arrays, digital arithmetic, logic arrays parallel processing, sorting, subroutines, algorithms auxiliary vector, bit length, bit-serial systolic array full adder, nonexchange sorting, on-the fly exchanges ordered list, pointers
Research Community:University of Westminster > Electronics and Computer Science, School of
ID Code:5707
Deposited On:27 Jan 2009 11:29
Last Modified:19 Oct 2009 16:29

Repository Staff Only: item control page