Search

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth (called a period in this context). In our previous paper Faster 3-Periodic Merging Network we reduced the time of merging on 3-periodic networks by a factor of 2, i.e. from 12 log ⁡ N to 6 log ⁡ N , compared to the first construction given by Kutyłowski, Loryś and Oesterdiekhoff. Note that merging on 2-periodic networks requires linear time. In this paper we extend our construction, and the analysis from that paper to any period p ≥ 3 . For p ≥ 3 our p -periodic network merges two sorted sequences of length N / 2 in at most 2 p p − 2 log ⁡ N + p p − 8 p − 2 rounds. The previous bound given by Kutyłowski et al. was 2.25 p p − 2.42 log ⁡ N for p ≥ 4 . That means, for example, that our 4-periodic merging networks work in time upper-bounded by 4 log ⁡ N and our 6-periodic ones in time upper-bounded by 3 log ⁡ N compared to the corresponding 5.67 log ⁡ N and 3.8 log ⁡ N previous bounds. Our construction is regular in the sense that it is parametrised with p and one can set p = 3 to get the family of 3-periodic merging networks, whereas the previous constructions given for p = 3 and p ≥ 4 differ in their structures. Moreover, our networks are also periodic sorters, and tests on random permutations suggest that the average sorting time might be close to log 2 ⁡ N . [ABSTRACT FROM AUTHOR]

We study the problem of constructing a sorting network that is tolerant to faults and whose running time (i.e., depth) is as small as possible. We consider the scenario of worst-case comparator faults and follow the model of passive comparator failure proposed by Yao and Yao [SIAM J. Comput., 14 (1985), pp. 120–128], in which a faulty comparator outputs its inputs directly without comparison. Our main result is the first construction of an N-input k-fault-tolerant sorting network with an asymptotically optimal depth θ(logN+k). That improves over the result of Leighton and Ma [Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, Velen, Germany, 1993, ACM, New York, pp. 30–41], whose network is of depth O(logN+k log [This symbol cannot be presented in ASCII format]). Actually, we present a fault-tolerant correction network that can be added after any N-input sorting network to correct its output in the presence of at most k faulty comparators. Since the depth of the network is O(logN + k) and the constants hidden behind the “O” notation are small, the construction can be of practical use. Developing the techniques necessary to show the main result, we construct a fault-tolerant network for the insertion problem. As a by-product, we get an N-input O(logN)-depth INSERT-network that is tolerant to random faults, thereby answering a question posed by Ma in his Ph.D. thesis [Fault-Tolerant Sorting Network, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1994]. The results are based on a new notion of constant delay comparator networks, that is, networks in which each register is used (compared) only in a period of time of a constant length. Copies of such networks can be pipelined with only a constant increase in the total depth per copy. [ABSTRACT FROM AUTHOR]