BVE: a wafer-scale engine for differential equation computation

ABSTRACT

With the advent of specialized VLSI and WSI hardware components the finite difference algorithms for solving differential equations become more attractive. This paper presents a novel computer architecture dedicated to compute boundary value problems. Improvement in speed and reliability can be obtained by means of WSI technology; however, a fault/defect tolerant scheme must be designed. Here we present a time redundancy approach which uses all the available computational resources; this is there is no spare or idle processors. This special purpose WSI parallel architecture runs as a loosely coupled MIMD (multi-instruction multi-data streams) machine and may execute more than 100 million instructions per second. The main features of this boundary value engine (BVE) are: 1) local communication -connections are limited to nearest neighbor; 2) cell regularity -all processors, memories and buses are identical; and 3) fault-tolerance -faulty modules are discarded by means of a novel time redundancy approach. As the feature size continues to shrink, the architecture can easily be extended to accommodate more computational cells.

REFERENCES

• 1: Arvind , Robert A. Iannucci, A critique of multiprocessing von Neumann style, Proceedings of the 10th annual international symposium on Computer architecture, p.426-436, June 13-17, 1983, Stockholm, Sweden
• 2: R. Aubusson and I cart, "Wafer-Scale lntegration-A Fault Tolerant Procedure," IEEE J. Solid-State Circuits, vol. SC-13, no. 3, pp. 339--344, June 1978.
• 3: G. H. Chapman, J. I. Raffel, J. M. Canter, F. M. Rhodes, "Advances in Laser Link Technology for Wafer-Scale Circuits," presented at the Int. Workshop on Wafer Scale Integration, Brunel University, England, September 1987.
• 4: J. G. Delgado-Frias and I. Contreras, "WASP: A WSI Bit-Serial Processor," presented at the IEEE CompEuro '87, Hamburg, W. Germany, May 1987.
• 5: J. G. Delgado-Frias, W. R. Moore and J. A. Trotter, "High Harvest Approaches for 2-D Arrays," presented at the International Conference on Designing for Yield, Univ. of Oxford, England, July 1987.
• 6: J. C. Harden , II,N. R. Strader, Architectural Yield Optimization for WSI, IEEE Transactions on Computers, v.37 n.1, p.88-110, January 1988 [doi>10.1109/12.75138]
• 7: Isaac Fried, Numerical Solution of Differential Equations, Academic Press, Inc., Orlando, FL, 1979
• 8: F. B. Manning, "An Approach to Highly Integrated, Computer-Maintained Cellular Arrays," IEEE Transactions on Computers, vol. C-26, no. 6, pp. 536-552, June 1977.
• 9: T. E. Mangir, "Sources of Failures and Yield Improvements for VLSI and Restructurable Interconnects for RVLSI and WSI: Part II -Restructurable Interconnects for RVLSI and WSI," Proceedings o/the IEEE, vol. 72, no. 12, pp. 1687-1694, December 1984.
• 10: G. i. Marhuk and V. V. Shaidurov, Difference Methods and their Exploitations, New York, NY: Springer- Verlag, 1983.
• 11: J. F. McDonald, E. It. Rogers, K. Rose, and A. J. Steckl, ~The Trials of Wafer-Scale Integration,~ IEEE Spectrum, vol. 21, no. 10, pp. 32-39, October 1984.
• 12: D.L. Peltzer, =Wafer-Scale Integration: The Limits of VLSI?," VLSI Design, vol. 4, no. 5, pp. 43-47, September 1983.
• 13: R. L. Petritz, "Current Status of Large Scale Integration Technology," IEEE J. Solid-State Circuits, vol. SC-2, no.6, pp. 130-147, December 1967.
• 14: J. i. Raffel, A. H. Anderson, G. H. Chapman, K. H. Konkle, B. Mathur, A. M. Soares, and P. W. Wyatt, ~A Wafer-Scale Digital Integrator Using Restructurable VLSI," IEEE J. Solid-State Circuits, vol. SC-20, no. 1, pp. 399-406, February 1985.
• 15: M. G. Sami and R. Stefanelli, "Fault-Tolerance of VLSI Processing Arrays: The Time Redundancy Approach," in Proe. of the 1985 Real-Time System Symposium, Austin Texas, pp. 200-207.December 1984
• 16: C. H. Stapper, F. M. Armstrong, and K. Sail, "Integrated Circuit Yield Statistics," Proceedings of the IEEE, vol. 71, no. 4, pp. 453-470, April 1983.
• 17: David M. Young , David R. Kincaid, A tutorial on finite-dfference methods and ordering of mesh points, Proceedings of 1986 ACM Fall joint computer conference, p.556-559, November 1986, Dallas, Texas, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Finite difference methods
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems

General Terms:
Algorithms, Design