Efficient routing techniques for cooperating processors in dataflow computers

ABSTRACT

A key problem in designing a dataflow computer is to maintain a strong cooperation among the processors. This requires two types of communications among the processors which are commonly referred to as arbitration and distribution. The paper describes a family of switches, called CP networks which can be used as arbitrators and distributors in dataflow computers. The arbitration networks require &Ogr;(N log2 N) binary switches, and have &Ogr;(log22 N) delay, and distribution networks require &Ogr;(N log22 N) binary switches, and have &Ogr;(log22 N) delay.

REFERENCES

• Arvind85: Arvind , David E. Culler, Dataflow architectures, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
• Batcher68: Butcher, K. E. "Sorting Networks And Their Applications," Proceedings of the Spring Joint Computer Conference, 1968, pp. 307-314.
• Benes64: Benes, V. E. "Optimal Rearrangeable Multistage Connecting Networks," Bell System Technical JournM, July 1964, pp. 1641-1656.
• Clos53: Clos, C. "A Study Of Non-Blocking Switching Networks", BeN System Technical Journal, March 1953, pp.406-424.
• Dennis80: Dennis, J. B. "Data Flow Supercomputers," IEEE Computer, November 1980, pp. 48-56.
• Gurd85: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• OpTsao71: Opferman, D. C. and N. T. Tsao-Wu "On A Class Of Rearrangeable Switching Networks," BeN System Technical Journal, May-June 1971, pp.1579- 1600.
• Srini86: Vason P Srini, An architectural comparison of dataflow systems, Computer, v.19 n.3, p.68-88, March 1986 [doi>10.1109/MC.1986.1663181]
• Syre77: Syre, 3. C., D. Courte, and N. Hifdi "Pipelining, Parallelism and Asynchronism in the LAU System," Proceedings of the International Conference on ParMlel Processing, 1977, pp. 87-92.
• TakAm83: Naohisa Takahashi , Makoto Amamiya, A data flow processor array system: Design and analysis, Proceedings of the 10th annual international symposium on Computer architecture, p.243-250, June 13-17, 1983, Stockholm, Sweden
• Thompson78: Thompson, C. D. "Generalized Interconnection Networks For Parallel Processor Intercommunication," IEEE Transactions on Computers, vol. C-27, no. 12, December 1978, pp. 1119-1125.
• Waksman68: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design