hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
Abstract:
When setup/hold times of bistable elements are violated, they may become
metastable, i.e., enter a transient state that is neither digital 0 nor 1. In
general, metastability cannot be avoided, a problem that manifests whenever
taking discrete measurements of analog values. Metastability of the output then
reflects uncertainty as to whether a measurement should be rounded up or down
to the next possible measurement outcome.
Surprisingly, Lenzen and Medina (ASYNC 2016) showed that metastability can be
contained, i.e., measurement values can be correctly sorted without resolving
metastability first. However, both their work and the state of the art by Bund
et al. (DATE 2017) leave open whether such a solution can be as small and fast
as standard sorting networks. 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. Concretely, for
10-channel sorting networks and 16-bit wide inputs, we improve by 48.46% in
delay and by 71.58% in area over Bund et al. Our simulations indicate that
straightforward transistor-level optimization is likely to result in
performance on par with standard (non-containing) solutions.
