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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/9980
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact