Impact of self-scheduling order on performance on multiprocessor systems

ABSTRACT

Processor self-scheduling is an efficient dynamic scheduling for multiprocessors. This paper discusses the impact of the self-scheduling order on the performance of multiply-nested parallel loops. It is shown that, due to data synchronization for cross-iteration data dependencies, the completion time of a multiply-nested loop is reduced when the nesting parallel loops with smaller delays are moved to the inside. The best performance is achieved when a shortest-delay scheduling order is used. The performance of the shortest-delay self-scheduling is compared to other self-scheduling orders and to compile-time static scheduling order proposed elsewhere. Program transformation needed to implement shortest-delay self-scheduling is also included.

REFERENCES

• 1: E.L. Lusk and R. A. Overbeek. "Implementation of Monitors with Macros: A Programming Aid for the HEP and other Parallel Processors", Argonne National Laboratory, ANL-83-97, Argonne, Illinois, December 1983.
• 2: Burton Smith, The architecture of HEP, on Parallel MIMD computation: HEP supercomputer and its applications, p.41-55, June 1985
• 3: P. Tang and P. Yew. "Processor Self-Scheduling for Multiple-Nested Parallel Loops," Proceedings of 1986 International Conference on Parallel Processing (August 19-22, 1986), pp. 528-535.
• 4: Z. Fang, P. Yew, P. Tang and C. Zhu. "Dynamic Processor Self-Scheduling for General Parallel Nested Loops," Proceedings of the 1987 International Conference on Parallel Processing (August, 1987), pp. 1-10.
• 5: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 6: r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
• 7: M.D. Guzzi. "Multitasking Runtime Systems for the Cedar Multiproce.,~or", Center for Supercomputing Research and Development, University of Illinois at Urb~ma-Champaign, Rpt No. 604, Urbana, Illinois, July, 1986.
• 8: Alliant Computer Systems Corp. FX/Series-- Architecture Manual., 1986.
• 9: F. Darema-Rogers, D. A. George, A. Norton and G. F. Pfister. "VM/EPEX- A VM/SP Based Environment for Parallel Execution", IBM Research RCl1381, Yorktown Heights, NY, 1985.
• 10: R.L. Graham. "Bounds of Certain Multiprocessing Timing Anomalies," SIAM Journal on Applied Mathematics (1969), Vol. 17, No. 2, pp. 416-429.
• 11: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 12: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 13: P. Tang, P. Yew and C. Zhu. "Algorithms for Generating Data-Level Synchronization Instructions", Center for Supercomputing Research and Development, University of Illinois at Urbana- Champaign, Rpt. No. 733, Urbana, January, 1988.
• 14: P. Tang, P. Yew, Z. Fang and C. Zhu. "Deadlock Prevention in Processor Self-Scheduling for Parallel Nested Loops," Proceedings of the 1987 International Conference o} Parallel Processing (August 1987), pp. 11-18.
• 15: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 16: Chuan-Qi Zhu , Pen-Chung Yew, A scheme to enforce data dependence on large multiprocessor systems, IEEE Transactions on Software Engineering, v.13 n.6, p.726-739, June 1987 [doi>10.1109/TSE.1987.233477]
• 17: P. Tang, Self-scheduling, data synchronization and program transformation for multiprocessor systems, University of Illinois, Department of Computer Science, Urbana, IL, 1990
• 18: R. Cytron. "Doacross: Beyond Vectorization for Multiprocessors," Proceedings of the 1986 International Conference for Parallel Processing (August, 1986), pp. 836-844.
• 19: M.J. Wolfe. "Optimizing Compiler for Supercomputers", Department of Computer Science, University of Illinois at Urbana-Champaign, Report No. UIUCDCS-R-82-1105, October, 1982.
• 20: John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
• 21: M. Wolfe. "Advanced Loop Interchanging," Proceedings o/the 1986 International Conference on Parallel ProcesMng (August 1986), pp. 536- 543.
• 22: R. Cytron. "Limited Processor Scheduling of Doacross Loops," Proceedings of the 1987 International Conference on Parallel Processing (August, 1987), pp. 226-234.
• 23: A. Shoshani and E. G. Coffman. "Detection and Prevention of Deadlocks," Proceedings of 4th Annual Princeton Conference an Information Sciences and Systems (Marchl 1970), pp. 355- 360.
• 24: Zhiyuan Li , Walid Abu-Sufah, A technique for reducing synchronization overhead in large scale multiprocessors, Proceedings of the 12th annual international symposium on Computer architecture, p.284-291, June 17-19, 1985, Boston, Massachusetts, United States
• 25: A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph and M. Snir. "The NYU Ultraeomputer Designing a MIJ/ID Shared Memory Parallel Computer," IEEE Trans. on Computer (Feb. 1983), Vol. C-32, No. 2, pp. 175-189.
• 26: D.J. Kuck et al. "Parallel Computing Today and Cedar Approach," Science (Feb. 1986), pp. 967- 974.
• 27: M. Wolfe. "Loop Skewing: the Wavefront Method Revisited", Kuck and Associates, inc., Savoy, Illinois, 1987.

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:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization; Deadlocks

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Performance