1

ABIDI, M. A., ANO AGRAWAL, D. P. 1980 On conflint-free permutations in multistage interconnection networks. J. Dzgttal Syst 4, 2 (Summer), 115-134. Abstracted in Proc. 1979 Int. Conf Parallel Processing (Detroit, Mich., Aug. 21-24), IEEE Computer Society, Long Beach, Calif., p. 159.

2

BANDYOPADHYAY, S., BASU, S., AND CHOUDHURY, A. K. 1972. A cellular permuter array, iEEE Trans. Comput C-21, 10 (Oct.), 1116-1119.

3

BATCHER, K. E. 1968. Sorting networks and their applications. In Proc. AFIPS Spring Joint Computer Conference, vol. 32, Thompson, Washington, D. C., pp. 307-314.

4

BATCHER, K. E. 1976. The flip network in STARAN. In Proc. 1976 Int. Conf. Parallel Processing (Detroit, Mich., Aug. 24-27), IEEE Computer Society, Long Beach, Cahf., pp. 65-71 1976.

5

BENE~, V. E. 1962a. Heuristic remarks and mathematical problems regarding the theory of connecting systems. Bell Syst Tech J 41, 4 (July), 1201-1247.

6

BENE~, V. E. 1962b. Algebraic and topological properties of connecting networks. Bell Syst. Tech J 41, 4 (July), 1249-1273.

7

BENE~, V. E. 1962c. On rearrangeable three-stage connecting networks. Bell Syst Tech J 41, 5 (Sept.), 1481-1492

8

BENE.~, V. E. 1964a. Optimal rearrangeable multistage connecting networks. Bell Syst. Tech. J. 43, 4 (Part 2) (July), 1641-1656.

9

BENES, V. E. 1964b. Permutation groups, complexes, and rearrangeable connecting networks. Bell Syst Tech. J 43, 4 (Part 2) (July), 1619-1640.

10

BENE~, V. E. 1965. Mathematical Theory of Connectmg Networks and Telephone Traffx Academic Press, New York.

11

BENE~, V E. 1967. Square switch distribution network employing a minimal number of crosspoints. U.S. Patent No. 3358269 (Dec. 12, 1967).

12

CANTOR, D. G. 1971. On nonblocking switching networks. Networks 1, 4 (Winter), 367-377.

13

CHEN, P.-Y., LAWRm, D. H., YEW, P.-C., ANO PADUA, D. A. 1981. Interconnection networks using shuffles. Computer 14, 12 (Dec.), 55-64.

14

CHUNO, K.-M., AND WONG, C. K. 1979 Asymptotically optimal interconnectlon networks from twostate cells. IEEE Trans. Comput C-28, 7 (July), 5OO-5O5.

15

CLOS, C. 1953. A study of non-blocking switching networks. Bell Syst Tech. J. 32, 2 (Mar.), 406- 424

16

DIAS, D. M., AND JUMP, J. R. 1980. Analysis and simulation of buffered delta networks. IEEE Trans. Comput C-30, 4 (Apr.), 273-282. Also in Proc Workshop Interconnection Networks (West Lafayette, Ind., Apr. 21-22), IEEE Computer Society, Long Beach, Calif., pp. 84-92. 1980.

17

FENG, T.-Y 1974. Data manipulating functions m parallel processors and their implementations, IEEE Trans. Comput C-23, 3 (Mar.), 309-318.

18

FENG, T.-Y. 1981. A survey of lnterconnection networks. Computer 14, 12 (Dec.), 12-27.

19

Tse-yun Feng , Chuan-lin Wu , Dharma P. Agrawal, A microprocessor-controlled asynchronous circuit switching network, Proceedings of the 6th annual symposium on Computer architecture, p.202-215, April 23-25, 1979  [doi>10.1145/800090.802911]

20

FRANKLIN, M. A. 1980. VLSI performance comparison of Banyan and crossbar communications networks. IEEE Trans Cornput C-30, 4 (Apr.), 283-290. Also m Proc Workshop on Interconnectton Networks (West Lafayette, Ind., Apr. 21-22), iEEE Computer Society, Long Beach, Calif., 20- 28.

21

GECSEI, J. 1977. Interconnection networks from three-state cells. IEEE Trans. Comput C-26, 8 (Aug.), 705-711.

22

GECSEI, J., AND BRASSARD, J -P. 1981. The topology of cellular partitioning networks. IEEE Trans Comput C-30, 2 (Feb.).

23

L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973

24

HWANG, F. K. 1972. Rearrangeabfiity of multi-connection three-stage Clos networks. Networks 2, 4 (Winter), 301-306.

25

HWANG, F. K. 1976. Balanced networks. In Proc. 1976 lnt Con{ Communicatwn Conference Record (Phdadelphia, June 14-16), IEEE, New York, pp. (7-13)-(7-16)

26

JOEL, A. E., JR. 1968. On permutation switching networks Bell Syst Tech. J 47, 5 (May-June), 813-822

27

JOEL, A E., JR. 1979. Circuit switching: Unique architecture and applications. Computer 12, 6 (June), 10-22. Also in Tutortal D~str~buted Processor Communxat~on Archttecture, K. J. Thurber, Ed. IEEE Comput. Soc., Long Beach, Cahf., pp. 325-337.

28

KAUTZ, W. H., LEVITT, K N., ANO WAKSMAN, A. 1968. Cellular interconnection arrays. IEEE Trans Comput C- 17, 5 (May), 443-451

29

David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978

30

LANG, T. 1976. Interconnections between processors and memory modules using the shuffle-exchange network. IEEE Trans. Comput C-25, 5 (May), 496-503.

31

LANG, T., AND STONE, H. S. 1976. A shuffle-exchange network with simplified control. {EEE Trans Comput C-25, 1 (Jan.), 55-65.

32

LAWRIE, D. H. 1975. Access and alignment of data in an array processor IEEE Trans Comput C- 24, 12 (Dec.), 1145-1155

33

LENFANT, J. 1978. Parallel permutations of data: A Bene~ network control algorithm for frequently used permutations. IEEE Trans Comput C-27, 7 (July), 637-647.

34

LEV, G F., PIPPENGER, N, AND VALIANT, L. G. 1981. A fast parallel algorithm for routing m permutation networks. IEEE Trans Comput C- 30, 2 (Feb), 93-100.

35

LIPOVOSK!, G J. 1970. The architecture of a large associative processor In Proc AFIPS 1970 Spring Joint Computer Conference (May), vol 36, AFIPS Press, Arlington, Va., pp. 385-396.

36

LIPOVSKI, G. J. 1979. The architecture of the banyan switch for TRAC. Prelim. Tech. Rep TRAC-7, Depts Computer Science and Electrical Engineering, Univ. of Texas (Jan. 15).

37

LIPOVSKI, G J, AND TRIPATHI, A. 1977. A reconfigurable vanstructure array processor. In Proc 1977 Int Conf Parallel Processing (Detroit, Mich., Aug. 23-26), IEEE Computer Society, Long Beach, Cahf., pp. 165-174

38

MALEK, M., AND MYRE, W. W. 1980. Figures of merit for interconnect~on networks. In Proc Workshop Interconnect~on Networks (West Lafayette, Ind., Apr. 21-22), iEEE Computer Society, Long Beach, Calif., pp. 74-83.

39

MALEK, M., AND MYRE, W W. 1981. A description method of lnterconnection networks IEEE Cornput Soc Dlstrlb Process Q 1, 1 (Feb.), 1-6.

40

MARCUS, M J. 1970a. Space-time equivalents in connecting networks In Proc 1970 Int Conf Communxatton Conference Record, pp (35-25)- (35-31).

41

MARCUS, M. J. 1970b. Designs for time slot interchangers. In Proc 1970 Nat. Electronics Conf (Chicago, I11., Dec. 7-9), vol. 26, pp. 812-817.

42

MARCUS, M. J. 1977. The theory of connecting networks and their complexity: A review. Proc. IEEE 65, 9 (Sept.), 1263-1271.

43

MASSON, G. M. 1973. Upper bounds on fanout m connection networks. IEEE Trans C~rcuit Theory CT-20, 3 (May), 222-229.

44

MASSON, G. M 1976. On rearrangeable and nonblocking switching networks. In Proc. 1976 Int Conf Communication Con{erence Record (Philadelphia, Pa, June 14-16), IEEE, New York, pp. (7-1)-(7- 7). Also in Tutorial: Distributed Processor Communicatwn Architecture, K. J. Thurber, Ed. IEEE Computer Society, Long Beach, Calif., pp. 355-361.

45

MASSON, G M. 1977. Binomial switching networks for concentration and distribution. IEEE Trans Commun COM-25, 9 (Sept.), 873-883.

46

MASSON, G. M., AND JORDAN, B W. 1971. Reahzation of a class of multiple connection assignments with asymmetrical three-stage connection networks. In Proc 5th Annu Princeton Conf Information and Systems Science (Princeton, N. J., Mar. 25- 26), Princeton Univ., N. J., pp. 316-320.

47

MASSON, G M., AND JORDAN, B. W. 1972. General- ~zed mulU-stage connection networks. Networks 2, 3 (Fall), 191-209.

48

MASSON, G. M., GINGHER, G. C., AND NAKAMURA, S. 1979. A sampler of circuit switching networks. Computer 12, 6 (June), 32-48. Also in Tutortal' D~strtbuted Processor Commun~catzon Architecture, K. J. Thurber, Ed. IEEE Computer Society, Long Beach, Cahf, 1979, pp. 362-378.

49

OrMAN, J. P. 1967. A universal automaton, In Transacttons of the Moscow Mathemattcs Society. American Mathematical Society, Providence, R. I., pp 200-215.

50

OPFERMAN, D C., AND TSAO-WU, N T. 1971. On a class of rearrangeable switching networks; Part I: Control algorithms; Part II: Enumeration studies and fault diagnosis. Bell Syst. Tech J. 50, 5 (May-June), 1579-1618.

51

OSATAKE, T, OGAWA, T., AND HAYASHIDA, T. 1973. Optimum structure of one-sided rearrangement switching networks Electron. Commun Jpn 56, 1 (Jan.), 28-33.

52

PARKER, D. S., JR 1980a. New points of view on three-stage rearrangeable switching networks. In Proc Workshop Interconnection Networks (West Lafayette, Ind, Apr. 21-22), IEEE Computer Socmty, Long Beach, Calif., pp. 56-63.

53

PARKER, D S., JR. 1980b Notes on shuffle/exchange-type switching networks IEEE Trans Comput. C-29, 3 (Mar.), 213-222.

54

Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979  [doi>10.1145/800090.802906]

55

PATEL, J. H. 1981. Performance of processor-memory interconnections for multiprocessors. IEEE Trans. Comput. C-30, 10 (Oct.), 771-780.

56

PAULL, M. C. 1962. Reswitching of connection networks. Bell $yst. Tech J. 41, 3 (May), 833-855.

57

Marshall C. Pease, An Adaptation of the Fast Fourier Transform for Parallel Processing, Journal of the ACM (JACM), v.15 n.2, p.252-264, April 1968  [doi>10.1145/321450.321457]

58

PEASE, M. C., III 1977. The indirect binary n-cube microprocessor array IEEE Trans. Comput C- 26, 5 (May), 458-473.

59

PIPPENGER, N. 1974. On the complexity of strictly nonblocking connection networks. IEEE Trans. Commun COM-22, 11 (Nov.), 1890-1892.

60

PIPPENGER, N. 1976. The complexity of seldomblocking networks. In Proc. 1976 Int Conf Communication Conference Record (Phfiadelphla, June 14-16), IEEE, New York, pp. (7-8)-(7-12).

61

PIPPENGER, N. 1977. Superconconcentrators. SIAM J Comput 6, 2 (June), 298-304.

62

PIPPENGER, N. 1978. Generalized connectors. SlAM J Comput. 7, 4 (Nov.), 510-514.

63

PRADHAN, D. K., AND KODANDAPANI, K. L. 1979. A framework for the study of permutations and apphcations to memory processor interconnection networks. In Proc. 1979 lnt Conf Parallel Processing (Detroit, Mich., Aug. 24-27), IEEE Computer Society, Long Beach, Calif., pp. 148- 158.

64

PRADHAN, D. K., AND KODANOAPANI, K L. 1980. A uniform representation of single- and multistage lnterconnection networks used m SIMD machines IEEE Trans Comput C-29, 9 (Sept.), 777-79O.

65

RAMANUJAM, H R. 1973 Decomposition ofpermutation networks IEEE Trans Comput C-22, 7 (July), 639-643.

66

SIEGEL, H. J. 1976. Single instruction stream--Multiple data stream machine interconnection network design In Proc. 1976 Int Conf Parallel Processing (Detroit, Mich., Aug. 24-27), pp. 273- 282.

67

SIEGEL, H. J. 1977a. Analys, s techniques for SIMD machine mterconnection networks and the effects of processgr address masks IEEE Trans Comput. C-26, 2 (Feb.), 153-161.

68

Howard Jay Siegel, The universality of various types of SIMD machine interconnection networks, Proceedings of the 4th annual symposium on Computer architecture, p.70-79, March 23-25, 1977

69

SIEGEL, H. J 1978. Partitionable SIMD computer system lnterconnectlon network unaversality. In Proc. 16th Annu Allerton Conf. Communicatton, Control, and Computtng (Oct.), Univ. of Illinois, Urbana-Champaign, Ill., pp 586-595.

70

SIEGEL, H. J 1979a. Interconnect~on networks for SIMD machines. Computer 12, 6 (June), 57-65. Also m Tutortal D~str~buted Processor Communication Architecture, K. J. Thurber, Ed. IEEE Computer Society, Long Beach, Cahf., pp. 379- 387.

71

SIEGEL, H. J. 1979b. Partitioning permutation networks: The underlying theory. In Proc 1979 Int. Conf Parallel Processing (Detroit, Mich., Aug. 21-24), IEEE Computer Society, Long Beach, Calif., pp. 175-184.

72

SIEGEL, H. J. 1979c. A model of SIMD machines and a comparison of various interconnection networks. IEEE Trans Comput C-28, 12 (Dec.), 907-917.

73

SIEGEL, H. J. 1980. The theory underlying the partitioning of permutation networks. IEEE Trans Comput. C-29, 9 (Sept.), 791-801.

74

SIEGEL, H J., AND MCMILLEN, R. J. 1981a. The multistage cube: A versatile interconnection network. Computer 14, 12 (Dec.), 65-76.

75

SIEGEL, H. J., AND MCMILLEN, R. J. 1981b. Using the augmented data manipulator network in PASM. Computer 14, 2 (Feb.), 25-33.

76

SIEGEL, H. J., MCMILLEN, R. J., AND MUELLER, P. T., JR. 1979. A survey of interconnection methods for reconfigurable parallel processing systems. In Proc. AFIPS 1979 Nat. Computer Conf (June 4-9), vol. 48, AFIPS Press, Arhngton, Va., pp. 529-542.

77

SMITH, S. D., AND SIEGEL, H. J. 1978. Rec~rculating, pipelined, and multistage SIMD interconnection networks. In Proc. 1978 Int Conf Parallel Processing (Detroit, Mich., Aug. 22-25), IEEE Computer Society, Long Beach, Cahf., pp. 206-214.

78

S. Diane Smith , H. J. Siegel, An emulator network for SIMD machine interconnection networks, Proceedings of the 6th annual symposium on Computer architecture, p.232-241, April 23-25, 1979  [doi>10.1145/800090.802913]

79

STONE, H S. 1971. Parallel processing with the perfect shuffle. IEEE Trans Comput C-20, 2 (Feb.), 153-161. Also in TutorLal: Dtstr~buted Processor Cornmunicatlon Architecture, K. J. Thurber, Ed IEEE Computer Society, Long Beach, Calif., pp. 388-396.

80

THOMPSON, C. D. 1978 Generalized connect~on networks for parallel processor intercommunication. IEEE Trans Comput C-27 (Dec.), 1119-1125.

81

THOMPSON, G. B. 1976. A conceptual model for crossbar switching networks In Proc 1976 Int. Conf Communtcatton Conference Record (Philadelphm, June 14-16), IEEE New York, pp. (7- 23)-(7-25)

82

THURBER, K. J. 1974. Interconnection networks--A survey and assessment. In Proc 1974 Nat Computer Conf (Chicago, May 6-10), AFIPS Press, Arhngton, Va., pp 909-919.

83

THURBER, K. J. 1978. Carcuit switching technology: A state-of-the-art survey. COMPCON 78 Fall (Washington, D. C, Sept. 5-8), IEEE Computer Society, Long Beach, Calif., pp. 116-124. Also in Tutorial Distributed Processor Commun~catwn Architecture, K. J. Thurber, Ed. IEEE Computer Society, 1979, pp. 338-346.

84

Kenneth J. Thurber, Distributed Processor Communication Architecture, IEEE Computer Society Press, Los Alamitos, CA, 1979

85

Anand R. Tripathi , G. Jack Lipovski, Packet switching in banyan networks, Proceedings of the 6th annual symposium on Computer architecture, p.160-167, April 23-25, 1979  [doi>10.1145/800090.802905]

86

TSAO-Wu, N. T. AND OPFERMAN, D. C. 1969. On permutation algorithms for rearrangeable switchlng networks. In Proc 1969 int Conf Communcatwn Conference Record, pp. (10-29)-(10-34).

87

Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States  [doi>10.1145/800116.803752]

88

Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968  [doi>10.1145/321439.321449]

89

Wu, C.-L., ASO FENO, T.-Y. 1979. Fault diagnosis for a class of multistage interconnection networks. In Proc. 1979. Int. Conf. Parallel Processtng (Detroit, Mich., Aug. 21-24), IEEE Computer Society, Long Beach, Calif., pp. 269-278.

90

Wu, C.-L., A~O FENG, T.-Y. 1980a. The reverseexchange lnterconnection network. IEEE Trans Comput C-29, 9 (Sept.), 801-811. Also essentially in Proc. 1979 Int Conf. Parallel Processing (Detroit, Mich., Aug. 21-24), IEEE Computer Society, Long Beach, Calif., pp. 160-174

91

Wu, C.-L., ANO FE~G, T.-Y. 1980b. On a class of multistage interconnection networks. IEEE Trans Comput. C-29, 8 (Aug.), 694-702.

Erol Gelenbe, Performance analysis of the connection machine, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.183-191, May 1990

Sape J. Mullender , Paul M. B. Vitányi, Distributed match-making for processes in computer networks (preliminary version), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.261-271, August 1985, Minaki, Ontario, Canada

J. T. Deutsch , A. R. Newton, A multiprocessor implementation of relaxation-based electrical circuit simulation, Papers on Twenty-five years of electronic design automation, p.481-488, June 1988

J. T. Deutsch , A. R. Newton, A multiprocessor implementation of relaxation-based electrical circuit simulation, Proceedings of the 21st conference on Design automation, p.350-357, June 25-27, 1984, Albuquerque, New Mexico, United States

Randall D. Rettberg , William R. Crowther , Philip P. Carvey , Raymond S. Tomlinson, The Monarch Parallel Processor Hardware Design, Computer, v.23 n.4, p.18-28, 30, April 1990

Barry Wilkinson, On Crossbar Switch and Multiple Bus Interconnection Networks with Overlapping Connectivity, IEEE Transactions on Computers, v.41 n.6, p.738-746, June 1992

Sape J Mullender , Paul M B Vitanyi, Distributed match-making for processes in computer networks, ACM SIGOPS Operating Systems Review, v.20 n.2, p.54-64, April 1986

George Broomell: colleagues

J. Robert Heath: colleagues