Automatic determination of grain size for efficient parallel processing

ABSTRACT

The authors propose a method for automatic determination and scheduling of modules from a sequential program.

REFERENCES

• 1: Babb, R. Parallel processing with large-grain data flow techniques. IEEE Comput. (July 1984J, 55-61.
• 2: Ehrenfeucht, A., and Rosenberg, G. A decomposition theorem for -structures. Technica{ Report No. CU-CS-328-86. University of Colorado, Boulder, 1986.
• 3: Boontee Kruatrachue , Ted Lewis, Grain Size Determination for Parallel Processing, IEEE Software, v.5 n.1, p.23-32, January 1988 [doi>10.1109/52.1991]
• 4: Kuck, D. The structure of an advanced vectorizer for pipelined proc~:ssors. In Proceedings of COMPSAC {October 1980), pp. 709-715.
• 5: Leiserson, C., and Maggs, B. Communication-e~ficient parallel graph algorithms. International Parallel Processing Conference, IEEE, 1986.
• 6: C. L. McCreary, An algorithm for parsing a graph grammar, University of Colorado at Boulder, Boulder, CO, 1987
• 7: Saltz, J. Automated problem scheduling and reduction of synchronization delay effects. ICASE Report No. 87-22. NASA Institute for Computer Applications in Science and Engineering, July 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Design, Theory