×

Universality of iterated networks. (English) Zbl 0806.94034

The authors consider the problem of constructing optimal universal multistage networks using an arbitrary interconnection permutation in place of the perfect-shuffle. For positive integers \(n\), \(k\) and any permutation on the symbols \(\{1,2, \dots,2n\}\), they consider the \(k\)- stage iterated network that has the same interconnection permutation at each stage and has \(n\) switches per column where in each column switch \(i\), \(1\leq i\leq n\) can either perform the transposition \((2i-1, 2i)\) on its inputs or pass them straight through. The universality of such networks is shown to be characterized by those whose 2-graphs are primitive and have the index of primitivity as a lower bound of the minimal number of stages needed to achieve universality. Computational results are given characterizing all nonisomorphic minimal networks with up to 12 inputs.

MSC:

94C15 Applications of graph theory to circuits and networks
68R10 Graph theory (including graph drawing) in computer science

Software:

Mathematica
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Anand, V. C. Dumir, and H. Gupta, A combinatorial distribution problem,Duke Math. J. 33, 757-769 (1966). · Zbl 0144.00401 · doi:10.1215/S0012-7094-66-03391-6
[2] W. Brown, ed.,Reviews in Graph Theory, Vols. 1 and 2, American Mathematical Society, Providence, RI, 1980. · Zbl 0538.05001
[3] R. G. Busacker and T. L. Saaty,Finite Graphs and Networks, McGraw-Hill, New York, 1965. · Zbl 0146.20104
[4] H. Cam and J. Fortes, Rearrangeability of shuffle-exchange networks,Proceedings of the Third Symposium on Frontiers of Massively Parallel Computation, 1990.
[5] R. F. Chamberlain and C. M. Fiduccia, Universality of iterated networks,Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, July 1992. · Zbl 0806.94034
[6] S. W. Golomb,Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1982.
[7] Hall,Combinatorial Theory, 2nd edn., Wiley, New York, 1986.
[8] Harary and Palmer,Graphical Enumeration, Academic Press, New York, 1973.
[9] D. H. Lawrie, Access and alignment of data in an array processor,IEEE Trans. Comput. 25, 1145-1155 (1976). · Zbl 0328.68034
[10] H. Mine,Nonnegative Matrices, Wiley, New York, 1987.
[11] D. S. Parker, Notes on shuffle/exchange type networks,IEEE Trans. Comput. 29, 213-222 (1980). · Zbl 0431.94050 · doi:10.1109/TC.1980.1675553
[12] M. C. Pease, The indirect binaryn-cube microprocessor array,IEEE Trans. Comput. 26(5), 458-473 (1977). · Zbl 0359.94057 · doi:10.1109/TC.1977.1674863
[13] G. PóPolya,Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds (translated by R. C. Read), Springer-Verlag, New York, 1987.
[14] C. S. Raghavendra and A. Varma, Rearrangeability of the 5-stage shuffle/exchange network forN = 8,Proceedings of the 1986 International Conference on Parallel Processing, pp. 119-122. · Zbl 0643.94040
[15] R. C. Read, The enumeration of locally restricted graphs, I and H,J. London Math. Soc. 34, 417-436 (1959);35, 344-351 (1960). · Zbl 0089.18301 · doi:10.1112/jlms/s1-34.4.417
[16] R. C. Read, The use ofS-functions in combinatorial analysis,Canad. J. Math. 20, 808-841 (1968). · Zbl 0165.32802 · doi:10.4153/CJM-1968-080-x
[17] J. H. Redfield, The theory of group-reduced distributions,Amer. J. Math. 49, 433-455 (1927). · JFM 53.0106.03 · doi:10.2307/2370675
[18] H. J. Siegel, The universality of various types of SIMD machine interconnection networks,Proceedings of the Fourth Annual Symposium on Computer Architecture, 1977. · Zbl 0359.94059
[19] S. Skiena,Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematics, Addison-Wesley, Reading, MA, 1990. · Zbl 0786.05004
[20] D. Steinberg, Invariant properties of the shuffle-exchange and a simplified cost-effective version of the omega network,IEEE Trans. Comput. 32(5), 444-450 (1983). · Zbl 0512.94018 · doi:10.1109/TC.1983.1676255
[21] H. S. Stone, Parallel processing with the perfect shuffle,IEEE Trans. Comput. 20, 153-161 (1971). · Zbl 0214.42703 · doi:10.1109/T-C.1971.223205
[22] A. A. Waksman, A permutation network,J. Assoc. Comput. Mach. 15, 159-163 (1968). · Zbl 0157.23702
[23] H. S. Wilf,Generatingfunctionology, Academic Press, San Diego, CA, 1990.
[24] S. Wolfram,Mathematica: A System for Doing Mathematics by Computer, Addison-Wesley, Reading, MA, 1988. · Zbl 0671.65002
[25] C. L. Wu and T. Y. Feng, The universality of the shuffle-exchange network,IEEE Trans. Comput. 30(5), 324-332 (1981). · Zbl 0463.94016 · doi:10.1109/TC.1981.1675790
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.