http://iet.metastore.ingenta.com
1887

Sorting without exchanges on a bit-serial systolic array

Sorting without exchanges on a bit-serial systolic array

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings G (Circuits, Devices and Systems) — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In the paper, 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 = log2n 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.

References

    1. 1)
      • J.V. McCanny , J.G. McWhirter . On the implementation of signal processing functions using one bit systolic arrays. Electron. Lett. , 6 , 241 - 243
    2. 2)
      • J.V. McCanny , J.G. McWhirter . A completely iterative pipelined multiplier array suitable for VLSI. IEE Proc. G, Electron. Circuits & Syst. , 40 - 47
    3. 3)
      • J.G. McWhirter , J.V. McCanny , K.W. Wood . Novel multi-bit convolver/correlator chip design based on systolic array principles. SPIE J. , 66 - 73
    4. 4)
      • H.T. Kung , S.W. Song , K. Preston , L. Uhr . (1982) A systolic 2D convolution chip, Multicomputer and image processing: algorithms and programs.
    5. 5)
      • M.J. Foster , H.T. Kung . The design of special purpose VLSI chips. IEEE comput. , 1 , 26 - 40
    6. 6)
      • Mead , Conway . (1979) , Introduction to VLSI design.
    7. 7)
      • Batcher, K.E.: `Sorting networks and their applications', AFIPS Conf. Proc., 1968, 32, p. 307–314, Spring Joint Computer Conferences.
    8. 8)
      • S. Zen-Cheung , C. Gen-huey , R.C.T. Lee . Systolic algorithms to examine all-pairs of elements. Commun. ACM , 2 , 161 - 167
    9. 9)
      • D.E. Knuth . (1972) , The art of computer programming.
    10. 10)
      • T. Nakatani , S.T. Huang , B.W. Arden , S.K. Tripathi . K-way bi-tonic sort. IEEE Trans. , 2 , 283 - 289
    11. 11)
      • H.S. Stone . Parallel processing with the perfect shuffle. IEEE Trans. , 2 , 153 - 161
    12. 12)
      • C.D. Thompson , H.T. Kung . Sorting on mesh connected parallel computers. Commun. ACM , 4 , 263 - 271
    13. 13)
      • D.J. Evans , G.M. Megson . Matrix inversion by systolic rank annihilation. Int. J. Comp. Math. , 319 - 357
    14. 14)
      • C. Choffrut , K. Culik . Folding the plane and the design of systolic arrays. Inf. Process. Lett. , 149 - 153
    15. 15)
      • Culik, K., Yu, S.: `Translation of systolic algorithms between systems of different topology', IEEE-ACM International Conference on Parallel Processing, 1985, p. 756–763.
    16. 16)
      • J. Ja Ja , R.M. Owens . VLSI sorting with reduced hardware. IEEE Trans. , 7 , 668 - 671
    17. 17)
      • H.F. Li , D.K. Probst , R.N. Prasad . Traversing the VLSI design hierarchy for a new fast systolic stack. IEE Proc. E, Comput. & Digital Tech. , 1 , 25 - 40
    18. 18)
      • Ipsen, I.C.F.: `Stable matrix computation in VLSI', 1984, PhD Thesis, Dept. of Computer Studies, An Arbor Michigan, USA.
    19. 19)
      • R. Lipton , D. Lopresti , W. Moore , A. McCabe , R. Urqhart . (1987) Comparing long strings on a short systolic array, Systolic arrays.
    20. 20)
      • C.D. Thompson . The VLSI complexity of sorting. IEEE Trans. , 1171 - 1184
    21. 21)
      • T. Leighton . Tight bounds on the complexity of parallel sorting. IEEE Trans. , 344 - 354
    22. 22)
      • J. Krammer , U. Schwiegelsholm , J. McCanny , J. McWhirter , E. Swartzlander . Architecture of a two-dimensional sorting algorithm, Systolic arrays.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-g-2.1990.0055
Loading

Related content

content/journals/10.1049/ip-g-2.1990.0055
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address