Jean-Paul Brassard
ABSTRACT
This paper presents a new method of obtaining couplings in networks.
We begin by introducing a new class of networks which are structural extensions of triangular permuting networks. More, by using augmented cells, we increase the functionnal capability of such networks.
Then we present an algorithm to solve the problem of constructing a complete coupling in such networks. This algorithm lends itself to a hardware implementation with partially distributed control.
- 1.A. Waksman, "A Permutation Network", JACM, Vol. 15, No. 1, pp. 159-163, Jan. 1968. Google Scholar
Digital Library
- 2.J. Lenfant, "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations", IEEE Trans. Comput., Vol. C-27, No. 7, pp. 637-647, July 1978.Google Scholar
- 3.D.C. Opferman and N.T. Tsao-Wu, "On a Class of Rearrangeable Switching Networks, Part I: Control Algorithms, Part II: Enumeration studies and Fault Diagnosis", Bell System Tech. J., Vol. 50, No. 5, pp. 1579-1618, May-June 1971.Google ScholarCross Ref
- 4.K. Batcher, "Sorting Networks and Their Applications", SJCC Conf. Proc., pp. 307-314, 1968.Google Scholar
- 5.G.M. Masson, G.C. Gingher, S. Nakamura, "A Sampler of Circuit Switching Networks", Computer, Vol. 12, No. 6, pp. 32-48, June 1979.Google ScholarDigital Library
- 6.J. Gecsei, "Interconnection Networks from Three-State Cells", IEEE Trans. Comput., Vol. C-26, pp. 705-711, Aug. 1977.Google Scholar
- 7.L.R. Goke and G.J. Lipovski, "Banyan Networks for Partitioning Multiprocessor Systems", Proc. 1st. Annual Computer Architecture Conf., (Gainesville, F1.), pp. 21-28, Dec. 1973. Google ScholarDigital Library
- 8.T. Osatake, T. Ogawa, T. Hayashida, "Optimum Structure of One-Sided Rearrangeable Switching Networks", Electronics and Communications in Japan, Vol. 56-A, No. 1, pp. 28-33, 1973.Google Scholar
- 9.W.H. Kautz, K.N. Levitt, A. Waksman, "Cellular Interconnection Arrays", IEEE Trans Comput., Vol. C-17, pp. 443-451, May 1968.Google Scholar
- 10.J.P. Brassard, "Réseaux d'interconnexions triangulaires en milieu asynchrone", International Symposium on Mini and Micro Computers, IEEE Catalog No. 77CH1347-4C, Proc. of MIMI 77 (Montreal), pp. 245-250, Nov. 1977.Google Scholar
- 11.J. Gecsei and J.P. Brassard, "The Topology of Cellular Partitioning Networks", to be published (submitted to IEEE T.C. in Aug. 1979).Google Scholar
- 12.J.P. Brassard, "Couplage sur les réseaux d'interconnexions planaires", PHD thesis, Département IRO, Université de Montréal, to be submitted in 1980.Google Scholar
Index Terms
- Path building in cellular partitioning networks
Recommendations
The topology of cellular partitioning networks
We investigate generalizations of triangular permuting networks in two directions: the connecting power of cells and the network topology. The main result indicates that permuting, coupling, and partitioning capabilities can be obtained by using 2-, 3-, ...
Partitioning and Permuting Properties of CC-Banyan Networks
A multicomputer network, called rectangular CC-banyan, is presented and formally defined. A graph-theoretic approach is used to study this network's permuting and partitioning properties. It is shown that a CC-banyan has a modular structure and hence ...
The Theory Underlying the Partitioning of Permutation Networks
The age of the microcomputer has made feasible large-scale multiprocessor systems. In order to use this parallel processing power in the form of a flexible multiple-SIMD (MSIMD) system, the interconnection network must be partitionable and dynamically ...
Comments