Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
High-performance implementation of regular and easily scalable sorting networks on an FPGA
Sklyarov V., Skliarova I. Microprocessors & Microsystems38 (5):470-484,2014.Type:Article
Date Reviewed: Nov 10 2014

Sorting networks are hardware sorter circuits consisting of comparators. Each comparator takes two input numbers and produces the maximum and minimum of those numbers at its outputs. Since the comparisons run in parallel, such networks are expected to produce faster results than software, and can be used as hardware accelerators for sorting.

Popular sorting networks follow a merge-sort-based scheme. The merge step, which combines partially sorted results, is usually done in one of two ways. The first method, even-odd merging, is based on merging even and odd indexed elements separately and combining the sorted subsequences. The second method, bitonic-merging, works by merging two sorted monotonic subsequences, one of which is ascending, and the other descending.

The authors report the results of using another implementation that is called even-odd transition network, which has a regular structure and allows the comparators to be reused. The new construction enables the mapping of larger-sized datasets on field-programmable gate arrays (FPGAs) compared to the earlier methods, though the throughput is compromised.

The first two sections provide a good introduction to the problem, and cover some of the relevant background. Both combinational and pipelined implementations are discussed. Classical merging methods, even-odd and bitonic, have their theoretical correctness proven in other works. Since the authors used a relatively newer even-odd transition network, they could perhaps have supplied a formal proof of the circuit here.

Section 3 presents the proposed method and shows how the same comparators can be reused through feedback registers. In the case of classical networks that are hardwired, data still needs to propagate through the remaining stages, even though sorting could have completed sooner. But the proposed method can detect such cases earlier, which has a theoretical advantage. Interestingly, when displaying experimental results in section 7, the authors did not provide any data with such an optimization to the sequential steps enabled.

Section 4 tabulates resource consumption and throughput estimates for the proposed network in comparison with earlier networks. In section 5, a variation that trades off some resources for throughput improvement is presented. Sections 6 through 8 cover practical applications, provide results, and demonstrate the merits of the scheme.

Overall, the paper is well organized and has a lot of details. Curious questions still remain for further research. Whether FPGAs are superior compared to graphics processing unit (GPU)-based even-odd transition networks is not clear yet. The proposed circuitry needs additional multiplexing, which can consume resources and introduce delays. Communication bottlenecks with the host system coupled with reduced throughput on the FPGA can introduce challenges to the proposal, when compared to purely software-based sorting.

Reviewer:  Paparao Kavalipati Review #: CR142914 (1502-0150)
Bookmark and Share
  Featured Reviewer  
 
Gate Arrays (B.7.1 ... )
 
 
Parallel Processing (I.3.1 ... )
 
 
Parallel Processors (C.1.2 ... )
 
 
Pipeline (B.2.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Gate Arrays": Date
Field programmable gate arrays (FPGAs)
Ukeiley R., Prentice-Hall, Inc., Upper Saddle River, NJ, 1993. Type: Book (9780133194685)
Sep 1 1994
Automated performance optimization of custom integrated circuits
Trimberger S., University Microfilms Int’l. (UMI), Ann Arbor, MI, 1986. Type: Book (9789780835717472)
Jan 1 1988
Properties of wired logic
Kambayashi Y. (ed), Muroga S. IEEE Transactions on Computers 35(6): 550-563, 1986. Type: Article
Jan 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy