DVPP: a VLSI dynamic-graph ensemble machine

ABSTRACT

In a previous paper, we proposed a special environment and techniques for the implementation of highly parallel processing. A new VLSI supercomputer architecture, DYPP (DYnamically Programmable multi-Processor), was introduced, with the unique property of being able to embed, and execute directly, program graphs both statically and dynamically. Either asynchronous (dataflow) or synchronous implementations of program graphs can be realized in DYPP. In the present paper, we provide further insight in its operation. In the proposed ensemble architecture, we separate processing and communication into two distinct, though overlapping and interacting layers. Separate, simpler (and thus more reliable), processors are assigned to the connectivity layer, which becomes active and self-adaptive, thus being able to detect and compensate for malfunctions in the underlying layer of main processing elements. There is no global control at either level. Rather in a first, static, version, the program graph (incorporating both connectivity information and operators, that is instructions), is “injected” in a preliminary, separate, phase via the connectivity-layer processors. In this phase, the connectivity graph is embedded between live (operational) main processing elements. In the second phase, processing takes place. A more advanced option makes the connectivity layer fully dynamic. In this case, the program graph is continuously injected (embedded) in a flow fashion to interact with the flow of data and intermediate results, which flow is said to become leviating. This can greatly reduce the need for local program memory and large numbers of PEs, and correspondingly the required VLSI area. As well, it can dispel the need for (large) resident, localized, static programs characteristically present in von Neumann architectures. Based on data levitation, the generalization of systolic arrays becomes feasible.

REFERENCES

• 1: W.B. Ackerman, "A Structure Processing Facility for Data Flow Computers", Proc.
• 2: W.B. Ackerman, "Data Flow Languages," Proc. 1979 Nat. Computer Conf. AFTPS Press, Arlington, Va., pp.1087-1095, 1979.
• 3: Arvind, K.P. Gostelow, and W. Plouffe, "The (Preliminary) Id Report," Tech. Rap l14a, Dept. of Information and Computer Science, Univ. Calif. Ixvine, Calif., Ma~ 1978.
• 4: Arvind and R.E. Thomas, "I-Struetureg, An Efficient Data Type for Functiona Languages," Laboratory for Computer Science, MIT, TM-178, 1980.
• 5: K.E. Batcher, "Design of a Massively Parallel Processor," IF_.EE Trans, Compat., vol. C-29, no. 9, pp.836-$40, 1980.
• 6: F. Barman, "Edge Grammars and Parallel Computation," 1983 Allerton Conference on Circuits, Communications & Computers, Urbana, ill. pp.214-223, 1983.
• 7: F. Betman, M. Goodrich, Ch. Koelb~l, W.J. Robison III and K. Showell, "Prep-P: A Mapping Processor for CHIP Computers," Proc. lnt'i Conf. on Parallel Processing, pp.731-733. 1985.
• 8: S.N. Bhatt and C.E. Lciserson, "t/ow to Assemble Tree Machines," MIT, Laboratory for Computer Science, Technical Memo TM-255, 1984.
• 9: Sally Anne Browning, The tree machine: a highly concurrent computing environment, 1980
• 10: L. J. Caluwaerts , J. Debacker , J. A. Peperstraete, Implementing streams on a data flow computer system with paged memory, Proceedings of the 10th annual international symposium on Computer architecture, p.76-83, June 13-17, 1983, Stockholm, Sweden
• 11: A.L. Davis and R.N. Keller, "Data Flow Program Graphs." {EEE Computer, roll5. no.2, pp.26-41, Feb. 1982.
• 12: J. B. Dennis, First version of a data flow procedure language, Programming Symposium, Proceedings Colloque sur la Programmation, p.362-376, April 09-11, 1974
• 13: J.B. Dennis, "The Varieties of Data Flow Computers," Proc. 1st lnt'l Conf. Distribated Computing Systems, pp.430-439, Oct. 1979.
• 14: J.B. Dennis and K.K.-S. Wcmg, "An Abstract Implementation for Concurrent Computation with Streams," Proc. Inl'l Conf. on Parallel Processing. pp.35-45, 1979.
• 15: J.B. Dennis "Data Flow Supercornputers," IEEE Computer, vol. 13. no. 11, pp.48-56, November 1980.
• 16: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 17: D.D. Gajski, D.A. Padua, DJ. Kuek and R.H. Kuhn, "A Second Opinion on Data Flow Machines and Languages," IEEE Computer, vol. 15, no. 2, pp.58-69, Feb. 1982.
• 18: J.-L. Gaudiot and M.D. Ercegovac, "A Scheme for Handling Arrays in Data-Flow Systems," Pro(:. lnt'l Conf. on Distributed Systems, pp.724-729, 1982.
• 19: J. L. Gaudiot, Methods for handling structures in data-flow systems, Proceedings of the 12th annual international symposium on Computer architecture, p.352-358, June 17-19, 1985, Boston, Massachusetts, United States
• 20: J.-L. Gaudiot, R.W. Vedder, O.K. Tucker, D. Finn and M.L. Campbell, "A Distributed VLS{ Architecture for Efficient Signal and Data Processing," IEEE Trans. Comput., vol. C-34, pp.1072-1077, December 1985.
• 21: 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]
• 22: Marius V. A. Hăncu , Kenneth C. Smith, DYPP—A VLSI supercomputer architecture supporting two-level fault tolerance, program graph injection and data levitation concepts, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.115-120, February 1986, Cincinnati, Ohio, United States [doi>10.1145/324634.325215]
• 23: Kye Sherrick Hedlund, Wafer scale integration of configurable, highly parallel processors, 1982
• 24: K.S. Hedlund and L Snyder, "Wafer-Scale Integration of Configurable, Highly Parallel Processors," Pro(:. Int. Conf. Parallel Process., IEI~E, pp.262-264, 1982.
• 25: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 26: R.M. Karp and R.E. Miller, "Properties of a Model for Parallel Computations," SIAM 3". of Applied Math., vol.14, no.6, pp.1390-1411, Nov. 1966.
• 27: S.P. Kartashev and S.I. Kartashev, "Architectures for Supersystems of tim 80's," Proc. 1980 AFIPS Nationat Computing Conference, pp.165-I80, 1980.
• 28: R.H. Kuhn and D,A, Padua, CEds.), Tutorial on Parallel Processing, IEEE Computer Society Press, New York, 1981.
• 29: H.T. Kung and C.E. Leiserson, "Systolic Arrays (for VLSI)," Sparse Matrix Proceedings 1978, Duff, I.S. and Stewart, G.H., (Eds.), SIAM, pp.256-282, 1979. (An earlier version appears in Chapter 8 of Mead and Conway {35}).
• 30: S.-Y. Kung and R.V. Gal-Ezer, "Synchronous vs. Asynchronous Computation in VLSI Array Processors," Proc. SPIE Conf., Arlington, VA, May 1982.
• 31: S.-Y. Kung, K.S. Arun, R.L Gal-Ezcr and D,V. Bhaskar Rao, "Wavcfront Array Processor: Language, Architecture and Applications," IEF_~ Trans. Corr~ut.vol. C-31, no.l I , pp.1054-1066, Nov. 1982.
• 32: S.-Y. Kung, "On Supereomputing with Systolie/Wavefront Array Processors," Proc. lEE.E, vol.72, no.7, pp.867-884, July 1984.
• 33: F.T. Leighton and C.E. Leiserson, "Wafer-Scale Integration of Systolic Arrays," Proc. 23rd Annual Syrup. on Foundations of Computer Science, pp.297-311, 1982.
• 34: F.B. Manning, "An Approach to Highly Integrated, Computer-Maintained Cellular Arrays," IEEE Trans. Computers, vol. C-26, no.6, pp.536-552, June 1977.
• 35: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 36: D. Misunas, "A Computer Architecture for Data-Flow Computation," Laboratory for Computer Science, MIT, TM- 100, March 1978.
• 37: D.I, Moldovan, "On the Design of Algorithms for VLSI Systolic Arrays," Proc. IEEE, vol.71, no. I, pp.l I3-120, Jan. 1983.
• 38: R.L. Petrlt2, "Current Stares of Large Scale Technology," IEEE J. Solid-State Circuits, SC-2, pp.130-147, Dec. 1967.
• 39: Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
• 40: J. E. Rodrigues , Jorge E Rodriguez Bezos, A GRAPH MODEL FOR PARALLEL COMPUTATIONS, Massachusetts Institute of Technology, Cambridge, MA, 1969
• 41: Arnold L. Rosenberg, Three-Dimensional VLSI: a case study, Journal of the ACM (JACM), v.30 n.3, p.397-416, July 1983 [doi>10.1145/2402.322384]
• 42: C.L. S~itz, "Ensemble Architectures for VLSI - A Survey and Taxonomy," in Proc. Conf. Advanced Res. VLSI, Massachussets Inst. Technol., Cambridge. Inn. 1982. Dadham, MA: Artech., pp.13 0-135, 1982.
• 43: C.L. Seitz. "Concurrent VLSI Architectures," I~ Trans. Compat., vol.C-33, no. 12, pp. 1247-1265, 1984.
• 44: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 45: L Snyder, "Introduction to the Poker Parallel Programming Environment," Proc. lnt'l Conf. Parallel Processing, pp.289-292, 1983.
• 46: L Snyder, "Supercomputers and VLSI: The Effect of Large-Scale Integration on Computer Architecture," /n Yovits, M.Y. (Ed.), Advances in Computers, voi.23, Academic Press, pp. 1-33. 1984.
• 47: Vason P. Srini, An architecture for extended abstract data flow, Proceedings of the 8th annual symposium on Computer Architecture, p.303-325, May 12-14, 1981, Minneapolis, Minnesota, United States
• 48: Vason P. Srini, A fault-tolerant dataflow system, Computer, v.18 n.3, p.54-68, March 1985 [doi>10.1109/MC.1985.1662830]
• 49: Peter Joseph Varman, Wafer-scale integration of linear processor arrays, 1983
• 50: LW. Young and H.K. Kent, "Abstract Formulation of Data Processing Problems." Internal Report, Product Specification Dept., The National Cash Register Company, Ha w'thome. CA, 1958.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.3 Control Structure Reliability, Testing, and Fault-Tolerance**
          Subjects: Test generation**
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Design, Reliability