Energy and Memory Efficient Mapping of Bitonic Sorting on FPGA
Authors:
Open Access
- 22 February 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 240-249
Abstract
Parallel sorting networks are widely employed in hardware implementations for sorting due to their high data parallelism and low control overhead. In this paper, we propose an energy and memory efficient mapping methodology for implementing bitonic sorting network on FPGA. Using this methodology, the proposed sorting architecture can be built for a given data parallelism while supporting continuous data streams. We propose a streaming permutation network (SPN) by "folding" the classic Clos network. We prove that the SPN is programmable to realize all the interconnection patterns in the bitonic sorting network. A low cost design for sorting with minimal resource usage is obtained by reusing one SPN . We also demonstrate a high throughput design by trading off area for performance. With a data parallelism of p (2 ≤ p ≤ N/ log2 N), the high throughput design sorts an N-key sequence with latency O(N/p), throughput (# of keys sorted per cycle) O(p) and uses O(N) memory. This achieves optimal memory efficiency (defined as the ratio of throughput to the amount of on-chip memory used by the design) of O(p/N). Another noteworthy feature of the high throughput design is that only single-port memory rather than dual-port memory is required for processing continuous data streams. This results in 50% reduction in memory consumption. Post place-and-route results show that our architecture demonstrates 1.3x ∼1.6x improvment in energy efficiency and 1.5x ∼ 5.3x better memory efficiency compared with the state-of-the-art designs.Keywords
Funding Information
- National Science Foundation (CCF-1018801)
- Defense Advanced Research Projects Agency (PERFECT program)
This publication has 24 references indexed in Scilit:
- Hardware acceleration of database operations2014
- FlexGrip: A soft GPGPU for FPGAs2013
- Energy-efficient architecture for stride permutation on streaming data2013
- High throughput energy efficient parallel FFT architecture on FPGAs2013
- Energy efficient parameterized FFT architecture2013
- Combinatorial Matrix Classes2006
- Adaptive binary sorting schemes and associated interconnection networksIEEE Transactions on Parallel and Distributed Systems, 1994
- An 0(n log n) sorting network1983
- Sorting networks and their applications1968
- Permutation Groups, Complexes, and Rearrangeable Connecting NetworksBell System Technical Journal, 1964