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

## 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 |

Subjects: | University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use) |

Depositing User: | Miss Nina Watts |

Date Deposited: | 27 Jan 2009 11:29 |

Last Modified: | 19 Oct 2009 15:29 |

URI: | http://westminsterresearch.wmin.ac.uk/id/eprint/5707 |

### Actions (login required)

Edit Item (Repository staff only) |