hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Architecture, cs.AR
Abstract:
Friedrichs et al. (TC 2018) showed that metastability can be contained when
sorting inputs arising from time-to-digital converters, i.e., measurement
values can be correctly sorted without resolving metastability using
synchronizers first. However, this work left open whether this can be done by
small circuits. We show that this is indeed possible, by providing a circuit
that sorts Gray code inputs (possibly containing a metastable bit) and has
asymptotically optimal depth and size. Our solution utilizes the parallel
prefix computation (PPC) framework (JACM 1980). We improve this construction by
bounding its fan-out by an arbitrary $f \geq 3$, without affecting depth and
increasing circuit size by a small constant factor only. Thus, we obtain the
first PPC circuits with asymptotically optimal size, constant fan-out, and
optimal depth. To show that applying the PPC framework to the sorting task is
feasible, we prove that the latter can, despite potential metastability, be
decomposed such that the core operation is associative. We obtain
asymptotically optimal metastability-containing sorting networks. We complement
these results with simulations, independently verifying the correctness as well
as small size and delay of our circuits.
