Modular design of high-throughput, low-latency sorting units

Amin Farmahini-Farahani, Henry J. Duwe, Michael J. Schulte, Katherine Compton

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

High-throughput and low-latency sorting is a key requirement in many applications that deal with large amounts of data. This paper presents efficient techniques for designing high-throughput, low-latency sorting units. Our sorting architectures utilize modular design techniques that hierarchically construct large sorting units from smaller building blocks. The sorting units are optimized for situations in which only the (M) largest numbers from (N) inputs are needed, because this situation commonly occurs in many applications for scientific computing, data mining, network processing, digital signal processing, and high-energy physics. We utilize our proposed techniques to design parameterized, pipelined, and modular sorting units. A detailed analysis of these sorting units indicates that as the number of inputs increases their resource requirements scale linearly, their latencies scale logarithmically, and their frequencies remain almost constant. When synthesized to a 65-nm TSMC technology, a pipelined 256-to-4 sorting unit with 19 stages can perform more than 2.7 billion sorts per second with a latency of about 7 ns per sort. We also propose iterative sorting techniques, in which a small sorting unit is used several times to find the largest values.

Original languageEnglish (US)
Article number6205742
Pages (from-to)1389-1402
Number of pages14
JournalIEEE Transactions on Computers
Volume62
Issue number7
DOIs
StatePublished - 2013
Externally publishedYes

Keywords

  • design optimization
  • iterative sorting
  • parallel sorting algorithms
  • partial sorting
  • VLSI designs

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Modular design of high-throughput, low-latency sorting units'. Together they form a unique fingerprint.

Cite this