Beyond 0-1: The 1-N Principle and Fast Validation of N-Sorter Sorting Networks
The well-known 0–1 principle for traditional data-oblivious sorting networks states that a network with L inputs can be fully validated with an input vector set consisting of all <inline-formula> <tex-math notation="LaTeX">$2^{L}$ </tex-math></inline-formula...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10177149/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The well-known 0–1 principle for traditional data-oblivious sorting networks states that a network with L inputs can be fully validated with an input vector set consisting of all <inline-formula> <tex-math notation="LaTeX">$2^{L}$ </tex-math></inline-formula> unique vectors containing only the values 0 and 1 in each vector’s L inputs. Researchers providing proofs of this principle tend to ignore the fact, which is emphasized here, that 0–1 vectors provide all distinct orderings of the two inputs to the 2-sorters which perform all of the sorting operations in the networks. The authors have recently described single-stage N-sorters, with <inline-formula> <tex-math notation="LaTeX">$N{>}2$ </tex-math></inline-formula>, and multiway merge sorting networks which use these N-sorters. The new N-sorters and their networks are also data-oblivious. It is easily shown that 0–1 vectors are not sufficient to fully verify even a single-stage 3-sorter, the smallest such N-sorter, as the 0–1 vectors are unable to produce all distinct orderings of the 3 inputs. In order to verify these N-sorters, the authors propose the 1-N principle, which states that testing an N-sorter with all distinct orderings of N input values is necessary and sufficient to prove the N-sorter’s correctness. An algorithm is defined which generates a vector set consisting of all distinct orderings of N inputs, which is then used to fully verify the associated single-stage N-sorter. In order to validate the authors’ L-input sorting networks which use these N-sorters, methods have been created which produce validation vector sets that are dramatically reduced in size versus the unsorted vector sets they are derived from. For example, the ratios of the number of L! permutation vectors to the equivalent reduced vectors are <inline-formula> <tex-math notation="LaTeX">${>}$ </tex-math></inline-formula>1,000,000 for <inline-formula> <tex-math notation="LaTeX">$\text{L}{=}12$ </tex-math></inline-formula>, and are much higher as L increases. |
|---|---|
| ISSN: | 2169-3536 |