Abstract | ||
---|---|---|
This paper extends previous work on sorting networks (SNs) based on min/max circuits. In particular, we have identified the complexity of both min/max-based sorting and merging networks showing that, depending on design choice, the time complexity of this kind of SN ranges from O(1) to O(log (n)) and spatial complexity from O(n2^n) to O(n^2), respectively. Moreover, we show that both AT and AT^2 metrics of the proposed SN are better than those of Batcher's SNs also for SNs with several hundreds of inputs. In addition to these results we show how to design a fast digital, serial, pipelined sorting network using FPGA technology. As expected, FPGA synthesis results confirm our theoretical analysis. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.ins.2011.12.008 | Inf. Sci. |
Keywords | Field | DocType |
sn range,max circuit,spatial complexity,fpga technology,proposed sn,design choice,previous work,theoretical analysis,time complexity,fpga synthesis result,sorting networks,fpga | Sorting network,Computer science,Field-programmable gate array,Algorithm,Sorting,Artificial intelligence,Spatial complexity,Time complexity,Merge (version control),Electronic circuit,Machine learning | Journal |
Volume | ISSN | Citations |
190, | 0020-0255 | 1 |
PageRank | References | Authors |
0.36 | 18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Giuseppe Campobello | 1 | 54 | 11.19 |
Giuseppe Patanè | 2 | 163 | 17.87 |
M. Russo | 3 | 425 | 37.60 |