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(n2n) to O(n2), respectively. Moreover, we show that both AT and AT2 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 theoret- ical analysis.
On the complexity of min-max sorting networks
RUSSO, Marco
2012-01-01
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(n2n) to O(n2), respectively. Moreover, we show that both AT and AT2 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 theoret- ical analysis.File | Dimensione | Formato | |
---|---|---|---|
2012_OnTheComplexityOfMinMaxNetworks.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
861.85 kB
Formato
Adobe PDF
|
861.85 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.