Networks for sorting multitonic sequences

Lee and Batcher have designed networks that efficiently merge k separately provided sorted sequences of known lengths totalling n. We show that the design is still possible, and in fact easier to describe, if we do not make use of the lengths, or even the directions of monotonicity, of the individual sequences—the sequences can be provided in a single undelimited concatenation of length n. The depth of the simplest resulting network to sort sequences that are “k-tonic” and of length n is , generalizing Batcher's 1968 results for the extreme values of k (k=2 corresponding to merging, and k=n/2 corresponding to general sorting).The exposition is self-contained and can serve even as an introduction to sorting networks and Batcher's results.     

Sorting nine inputs requires twenty-five comparisons

This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.     

Introspective Sorting and Selection Algorithms

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N²). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ(N log N) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.     

Periodic Merging Networks

We consider the problem of merging two sorted sequences on constant degree networks performing compare—exchange operations only. The classical solution to this problem is given by the networks based on Batcher's Odd—Even Merge and Bitonic Merge running in log(2n ) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present a new family of merging networks working in a completely different way than the previously known algorithms. They have a novel property of being periodic: this means that for some (small) constant k , each processing unit of the network performs the same operations at steps t and t+k (as long as t+k does not exceed the runtime). The only operations executed are compare—exchange operations, just like in the case of Batcher's networks. The architecture of the networks is very simple and easy to lay out. We show that even for period 3 there is a network in our family merging two n -element sorted sequences in time O(log n ). Since each network of period 2 requires steps to merge such sequences, 3 is the smallest period for which we may achieve a fast runtime. In order to improve constants standing in front of log n we increment the period and tune the construction using additional techniques. We achieve the runtime 9 . . . log_3 n 5.7 . . . log n for a network of period 4, and 2.25 . . . ((k+3)/(k-1+log 3))log n 2.25 . . . log n for a network of period k+3 , for . Due to the periodic design, our networks have small area complexity. For instance, if each processing unit requires O(1) area and a comparator uses a single wire of width O(1) connecting the processing elements, then our networks require area. This compares well with Batcher's networks that require area . Received February 1997, and in revised form September 1997, and in final form February 1998.     

Sorting and Counting Networks of Arbitrary Width and Small Depth

We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let w be the product w = p ₀ ⋅ p ₁ ⋅s p _n-1 , whose factors are not necessarily prime. We present a novel network construction of width w and depth O(n ² ) = O(log ² w) , using comparators (or balancers) of width less than or equal to max(p _i ) . This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width w , one for each distinct factorization of w . A factorization in which max(p _i ) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(p _i ) is small and n is large makes the opposite tradeoff. Received June 18, 2001. Online publication October 30, 2001.     

Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach.23, 566–571) is solved: lim_n→∞M(m, n)/n=log m/2+m/2^{log m}.     

Uniform minimal full-access networks

Minimal Full-Access (MFA) networks are the class of all interconnection networks for N = 2ⁿ inputs and outputs that require a minimum number of switching elements and provide full access capability. In this paper, MFA networks with 2 × 2 switching elements that use the same interconnection pattern between the stages are studied; such networks are called uniform MFA (UMFA) networks. Most of the known networks, including the Omega, the binary n-cube, and the regular (2, 2)-banyan, belong to this class. A graph-theoretic approach is used to study the class of UMFA networks, and a procedure is described to derive topologically nonequivalent networks from the Omega network. It is shown that the number of UMFA networks grow exponentially with N, and a lower bound of about 2^N/32 is obtained for N ⩾ 32. We also outline an extension of our methods to derive similar bounds for networks using k × k switches, for k ⩾ 3.     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

Simplified odd-even sort using multiple shift-register loops

By using anN-loop shift-register structure called a uniform ladder,N records can be sorted by a simplified adaptation of the odd-even transposition-sort algorithm to finish in (N + 1)/2 loop times (periods) using (N – 1) comparators. The sorting can be overlapped with input/output; the percentage of unoverlapped sorting times is less than 20% of the total time with a single ladder, less than 6% using two ladders, and is zero with a sufficient number of ladders.Presented at the Second International Magnetic Bubble Conference, Eindhoven, The Netherlands, August 1976.     

An efficient top-down search algorithm for learning Boolean networks of gene expression

Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and for a limited function class. In general, the conventional algorithm has the high time complexity of O(2^{2k mn k+1}) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized network search algorithm with average time complexity O ^{(mn k+1}/ (log m)^(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we provide tests for yeast expression data. Editor: David Page     

The design of complete encryption networks using cryptographically equivalent permutations

A design procedure for complete substitution-permutation encryption networks is presented. The cryptographically important property of completeness is achieved after three iterations, the minimum possible number for all networks of size N = i · n² (i = 1,2,…,n), where n is the size of the substitution function used. The permutation stage is constructed by choosing a single member of a class of cryptographically equivalent permutations for all the network rounds, hence having the advantage of simplifying the network implementation. An algorithm for generating members of the class of cryptographically equivalent permutations is given.     

Optimal conclusive sets for comparator networks

A set of input vectors S$S$ is conclusive for a certain functionality if, for every comparator network, correct functionality for all input vectors is implied by correct functionality for all vectors in S$S$. We consider four functionalities of comparator networks: sorting, merging, sorting of bitonic vectors, and halving. For each of these functionalities, we present two conclusive sets of minimal cardinality. The members of the first set are restricted to be binary, while the members of the second set are unrestricted. For all the above functionalities, except halving, the unrestricted conclusive set is much smaller than the binary one.     

A three-stage construction for multiconnection networks

Summary A multiconnection network of size N is a switching network with N inputs and N outputs which realizes multiconnections, i.e., connections between the N inputs and N outputs in such a way that every output is connected to exactly one input, but an input can be connected to an arbitrary number of outputs. That network is complete if it can realize all N ^N multiconnections. This structure generalizes the permutation network. We consider here the design of multiconnection networks by a three-stage Clos network using complete substitution networks as its building cells and we show that the resulting multiconnection network is complete if and only if the cells in the middle stage have size 2. Moreover, we describe the control algorithm for such a network. This leads to the design of cellular multiconnection networks of arbitrary size with a relatively simple control algorithm.     

Multistability of HNNs with almost periodic stimuli and continuously distributed delays

In this article, we investigate multistability of Hopfield neural networks (HNNs) with almost periodic stimuli and continuously distributed delays. By employing the theory of exponential dichotomy and Schauder's fixed point theorem, sufficient conditions are gained for the existence of 2 ^N almost periodic solutions which lie in invariant regions. Meanwhile, we derive some new criteria for the networks to converge toward these 2 ^N almost periodic solutions and the domain of attraction is also given. The obtained results are new, general and improve corresponding results existing in previous literature.     

Evolutionary Design of Arbitrarily Large Sorting Networks Using Development

An evolutionary algorithm is combined with an application-specific developmental scheme in order to evolve efficient arbitrarily large sorting networks. First, a small sorting network (that we call the embryo) has to be prepared to solve the trivial instance of a problem. Then the evolved program (the constructor) is applied on the embryo to create a larger sorting network (solving a larger instance of the problem). Then the same constructor is used to create a new instance of the sorting network from the created larger sorting network and so on. The proposed approach allowed us to rediscover the conventional principle of insertion which is traditionally used for constructing large sorting networks. Furthermore, the principle was improved by means of the evolutionary technique. The evolved sorting networks exhibit a lower implementation cost and delay.     

Generalized Recursive Sorting Networks

A class of recursive sorting networks based on mod(s) m-merging, a generalization of Batcher′s odd-even merging, is studied in this paper. Iterative decomposition of a sorter into smaller comparator modules, an equivalent problem but in a different setting, is also resolved based on the scheme proposed here. We first show that it is impossible to generalize the principle of odd-even merging in a three-stage network. Then the condition on generalized mod(s) m-merging with four stages is proven. This scheme degenerates to the three-stage odd-even merging network when m = 2 and s = 2. An algorithm for computing the optimal configuration is also given. Applications of this sorting network include parallel relational database computers and modular construction of sorting networks for large packet switches.     

Computing Mimicking Networks

A mimicking network for a k -terminal network, N , is one whose realizable external flows are the same as those of N . Let S(k) denote the minimum size of a mimicking network for a k -terminal network. In this paper we give new constructions of mimicking networks and prove the following results (the values in brackets are the previously best known results): S(4)=5 [2 ¹⁶ ] , S(5)=6 [2 ³² ] . For bounded treewidth networks we show S(k)= O(k) [2^ 2 ^k ] , and for outerplanar networks we show S(k) 10k-6 [k ² 2 ^k+2 ] . Received April 1, 1997; revised December 10, 1997.     

A parallel routing algorithm on circulant networks employing the Hamiltonian circuit latin square

Double-loop [J. Bermond, F. Comellas, D. Hsu, Distributed Loop Computer Networks: A Survey, J. Parallel and Distributed Computing, Academic Press, 24 (1995) 2-10] and 2-circulant networks (2-CN) [J. Park, Cycle Embedding of Faulty Recursive Circulants, J. of Korea Info. Sci. Soc. 31 (2) (2004) 86-94] are widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on circulant networks, that is a key to the performance of this network. We would like to transmit 2k packets from a source node to a destination node simultaneously along paths on G(n; ±s₁, ±s₂, … , ±s_k), where the ith packet traverses along the ith path (1 ? i ? 2k). In order for all packets to arrive at the destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian circuit latin square (HCLS), a special class of (n × n) matrices, we present O(n²) parallel routing algorithm on circulant networks.     

Parallel Algorithms for Partitioning Sorted Sets and Related Problems

We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k ≤ h ≤ n/k , partition S into g = O(n/(hk)) subsets D ₁ , D ₂ , . . . , D _g of size Θ(hk) each, such that, for any two indices i and j with 1 ≤ i < j ≤ g , no element in D _i is bigger than any element in D _j . Note that with various combinations of the values of parameters h and k , several fundamental problems, such as merging, sorting, and finding an approximate median, can be formulated as or be reduced to this partition problem. The partition problem also finds many applications in solving problems of parallel computing and computational geometry. In this paper we present efficient parallel algorithms for solving the partition problem and a number of its applications. Our parallel partition algorithm runs in O( log n) time using processors in the EREW PRAM model. The complexity bounds of our parallel partition algorithm on the respective special cases match those of the optimal EREW PRAM algorithms for merging, sorting, and finding an approximate median. Using our parallel partition algorithm, we are also able to obtain better complexity bounds (even possibly on a weaker parallel model) than the previously best known parallel algorithms for several important problems, including parallel multiselection, parallel multiranking, and parallel sorting of k sorted subsets. Received May 5, 1996; revised July 30, 1998.     

Wavelength Assignment for Realizing Parallel FFT on Regular Optical Networks

Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2ⁿ nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2^{n − 1}, 2^{n − 1}, 2^{max (k,n − k) − 1} and 2^{max (k,n − k) − 1} respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2^{n − 3},2), 2^{n − 2}, max (3× 2^{max (k,n − k) − 3},2) and 2^{max (k,n − k) − 2}. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity.