Feedback-directed thread scheduling with memory considerations

ABSTRACT

This paper describes a novel approach to generate an optimized schedule to run threads on distributed shared memory (DSM) systems. The approach relies upon a binary instrumentation tool to automatically acquire the memory sharingrelationship between user-level threads by analyzing their memory trace. We introduce the concept of Affinity Graph to model the relationship. Expensive I/O for large trace files is completely eliminated by using an online graph creation scheme. We apply the technique of hierarchical graph partitioning and thread reordering to the affinity graph to determine an optimal thread schedule. We have performed experiments on an SGI Altix system. The experimental results show that our approach is able to reduce the totalexecution time by 10% to 38% for a variety of applications through the maximization of the data reuse within a single processor, minimization of the data sharing between processors, and a good load balance.

REFERENCES

• 1: T. Davis. University of Florida sparse matrix collection. In http://www.cise.ufl.edu/research/sparse, 1997.
• 2: Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004 [doi>10.1016/j.jpdc.2003.09.005]
• 3: Chen Ding , Maksim Orlovich, The Potential of Computation Regrouping for Improving Locality, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.13, November 06-12, 2004 [doi>10.1109/SC.2004.58]
• 4: B. Hendrickson and R. Leland. The Chaco user's guide: Version 2.0. In Sandia Tech Report SAND94-2692, 1994.
• 5: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 6: Shin-Jae Lee , Minsoo Jeon , Dongseung Kim , Andrew Sohn, Partitioned parallel radix sort, Journal of Parallel and Distributed Computing, v.62 n.4, p.656-668, April 2002 [doi>10.1006/jpdc.2001.1808]
• 7: Honghui Lu , Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, Message passing versus distributed shared memory on networks of workstations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224285]
• 8: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 9: Jaydeep Marathe , Frank Mueller, Hardware profile-guided automatic page placement for ccNUMA systems, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122987]
• 10: E. P. Markatos , T. J. LeBlanc, Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.379-400, April 1994 [doi>10.1109/71.273046]
• 11: James Philbin , Jan Edler , Otto J. Anshus , Craig C. Douglas , Kai Li, Thread scheduling for cache locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.60-71, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: J. C. Pichel, D. B. Heras, J. C. Cabaleiro, and F. F. Rivera. Improving the locality of the sparse matrix-vector production shared memory multiprocessors. In PDP, pages 66--71. IEEE Computer Society, 2004.
• 13: Juan C. Pichel , Dora B. Heras , Jose C. Cabaleiro , Francisco F. Rivera, A New Technique to Reduce False Sharing in Parallel Irregular Codes Based on Distance Functions, Proceedings of the 8th International Symposium on Parallel Architectures,Algorithms and Networks, p.306-311, December 07-09, 2005 [doi>10.1109/ISPAN.2005.10]
• 14: Venkata K. Pingali , Sally A. McKee , Wilson C. Hsieh , John B. Carter, Restructuring computations for temporal data cache locality, International Journal of Parallel Programming, v.31 n.4, p.305-338, August 2003 [doi>10.1023/A:1024556711058]
• 15: Hongzhang Shan , Jaswinder Pal Singh, Parallel sorting on cache-coherent DSM multiprocessors, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331572]
• 16: B. Sinharoy , R. N. Kalla , J. M. Tendler , R. J. Eickemeyer , J. B. Joyner, POWER5 System microarchitecture, IBM Journal of Research and Development, v.49 n.4/5, p.505-521, July 2005
• 17: F. Song, S. Moore, and J. Dongarra. Modeling of L2 cache behavior for thread-parallel scientific programs on Chip Multi-Processors. In UT Computer Science Technical Report UT-CS-06-583, 2006.
• 18: SGI. Linux resource administration guide. In SGI Techpubs Library 007-4413-011, 2006.
• 19: Yong Yan , Xiaodong Zhang , Zhao Zhang, Cacheminer: A Runtime Approach to Exploit Cache Locality on SMP, IEEE Transactions on Parallel and Distributed Systems, v.11 n.4, p.357-374, April 2000 [doi>10.1109/71.850833]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Experimentation, Performance

Keywords:
affinity graph, distributed shared memory, scientific applications, shared-memory programming