Near-Optimal Metastability-Containing Sorting Networks
Johannes Bund1, Christoph Lenzen2 and Moti Medina2
1Saarland University, Saarland Informatics Campus, Germany.
s9jobund@stud.uni-saarland.de
2Max Planck Institute for Informatics, Saarland Informatics Campus, Germany.
aclenzen@mpi-inf.mpg.de
bmmedina@mpi-inf.mpg.de
ABSTRACT
Metastability in digital circuits is a spurious mode of operation induced by violation of setup/hold times of stateful components. It cannot be avoided deterministically when transitioning from continuously-valued to (discrete) binary signals. However, in prior work (Lenzen & Medina ASYNC 2016) it has been shown that it is possible to fully and deterministically contain the effect of metastability in sorting networks. More specifically, the sorting operation incurs no loss of precision, i.e., any inaccuracy of the output originates from mapping the continuous input range to a finite domain.
The downside of this prior result is inefficiency: for B-bit inputs, the circuit for a single comparison contains Q(B2) gates and has depth Q(B). In this work, we present an improved solution with near-optimal Q(B logB) gates and asymptotically optimal Q(\logB) depth. On the practical side, our sorting networks improves over prior work for all input lengths B > 2, e.g., for 16-bit inputs we present an improvement of more than 70% in depth of the sorting network and more than 60% in cost of the sorting network.
