Streaming Sorting Networks

Abstract

Sorting is a fundamental problem in computer science and has been studied extensively. Thus, a large variety of sorting methods exist for both software and hardware implementations. For the latter, there is a trade-off between the throughput achieved and the cost (i.e., the logic and storage invested to sort n elements). Two popular solutions are bitonic sorting networks with O ( n log 2 n ) logic and storage, which sort n elements per cycle, and linear sorters with O ( n ) logic and storage, which sort n elements per n cycles. In this article, we present new hardware structures that we call streaming sorting networks , which we derive through a mathematical formalism that we introduce, and an accompanying domain-specific hardware generator that translates our formal mathematical description into synthesizable RTL Verilog. With the new networks, we achieve novel and improved cost-performance trade-offs. For example, assuming that n is a two-power and w is any divisor of n , one class of these networks can sort in n /; w cycles with O ( w log 2 n ) logic and O ( n log 2 n ) storage; the other class that we present sorts in n log 2 n /; w cycles with O ( w ) logic and O ( n ) storage. We carefully analyze the performance of these networks and their cost at three levels of abstraction: (1) asymptotically, (2) exactly in terms of the number of basic elements needed, and (3) in terms of the resources required by the actual circuit when mapped to a field-programmable gate array. The accompanying hardware generator allows us to explore the entire design space, identify the Pareto-optimal solutions, and show superior cost-performance trade-offs compared to prior work.