Hardware assists for high performance computing using a mathematics of arrays

ABSTRACT

Work in progress at the University of Missouri-Rolla on hardware assists for high performance computing is presented. This research consists of a novel field programmable gate array (FPGA) based reconfigurable coprocessor board (the Chameleon Coprocessor) being used to evaluate hardware architectures for speedup of array computation algorithms. These algorithms are developed using a Mathematics of Arrays (MOA). They provide a means to generate addresses for data transfers that require less data movement than more traditional algorithms. In this manner, the address generation algorithms are acting as an intelligent data prefetching mechanism or special purpose cache controller. Software implementations have been used to provide speedups on the order of 100% over classical methods to the solution of heat transfer equations on a uniprocessor. We extend these methods to application designs for the Chameleon Coprocessor.

REFERENCES

• 1: Kevin Dowd, High performance computing, O'Reilly & Associates, Inc., Sebastopol, CA, 1993
• 2: Mullin, Lenore, "A Mathematics of Arrays", Ph.D. dissertation, Syracuse University, December 1988.
• 3: Philip S. Abrams, What's wrong with APL?, Proceedings of seventh international conference on APL, p.1-8, June 11-13, 1975, Pisa, Italy [doi>10.1145/800117.803777]
• 4: Mullin, L., "The Psi Correspondence Theorem: Array Mapping Using the Psi Calculus", Department of Computer Science, University of Missouri- Rolla.
• 5: Mullin, L., Thibault, S., "A Reduction semantics for array expressions: the PSI compiler", TR CSC-94-05, March 9, 1994, Department of Computer Science, University of Missouri- Rolla.
• 6: Coffin, Larry, "Designing a New Programming Methodology for Optimizing Array Accesses in Complex Scientific Problems", OURE Paper, University of Missouri - Rolla, 1994.
• 7: Xilinx, Inc, 2100 Logic Drive, San Jose, CA 95124 . The Programmable Logic Databook, April 1994.
• 8: Wo, D., Forward, K., "Compiling to the gate Level for a Reconfigureable Co-Processor", Proceedings of FPGAs for custom computing machines (1994), pp 147-154.
• 9: Abbott, A., Athanas, P., Chen, L., Elliott, R., "Finding Lines and Building Pyramids with Splash 2", Proceedings of FPGAs for custom computing machines (1994), pp 155-161.
• 10: Gent, G., Smith, S., Haviland, R., "An FPGA-based Custom Coprocessor for Automatic Image Segmentation Applications", Proceedings of FPGAs for custom computing machines (1994), pp 172-179.
• 11: Quenot, G., Kraljic, I., Serot, J., Zavidovique B., "A Reconfigureable Compute Engine for Real-Time Vision Automata Prototyiping", Proceedings of FPGAs for custom computing machines (1994), pp 91 - 100.
• 12: Arnold, J., Duncan, Buell, A. , Hoang, D., "The Splash 2 Processor and Applications", Proceedings ICCD '93.
• 13: Ferguson, W., "Selecting Math Coprocessors", IEEE Spectrum, July 1991, pp 38-41.
• 14: Bergmann, N., Mudge, J., "Comparing the Performance of FPGA-Based Custom Computers with General -Purpose Computers for DSP Applications", Proceedings of FPGAs for custom computing machines (1994), pp 164-171.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms, Design, Performance