| topknet.ipynb | (11 kb) | Python / Jupyter Notebook |
Like sorting networks, selection networks are special comparator networks. A comparator network consists of wires or lanes carrying values and comparators or conditional swap devices connecting pairs of wires. A comparator swaps values between wires if they are not in a desired order. Comparators connecting disjoint pairs of wires may be executed in parallel, due to which they can be arranged in layers (of comparators executable in parallel). The size of a selection network is its number of comparators, and its depth is its number of layers.
Selection networks are algorithms for selecting, for example, the top-k or bottom-k elements from their input. They have a fixed execution structure, that is, their execution structure is independent of the input data. This property makes them suitable for hardware implementations.
The Python code provided here as a Jupyter Notebook implements so-called splitter selection networks for selecting the top-k values, which are especially useful if k is small compared to the size of the input. Such selection networks were used in:
Splitter selection networks are strongly inspired by pairwise sorting networks as introduced by Ian Parberry: