Scheduling threads for constructive cache sharing on CMPs

ABSTRACT

In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which concurrently scheduled threads share a largely overlapping working set. In this paper, we compare the performance of two state-of-the-art schedulers proposed for fine-grained multithreaded programs: Parallel Depth First (PDF), which is specifically designed for constructive cache sharing, and Work Stealing (WS), which is a more traditional design. Our experimental results indicate that PDF scheduling yields a 1.3--1.6X performance improvement relative to WS for several fine-grain parallel benchmarks on projected future CMP configurations; we also report several issues that may limit the advantage of PDF in certain applications. These results also indicate that PDF more effectively utilizes off-chip bandwidth, making it possible to trade-off on-chip cache for a larger number of cores. Moreover, we find that task granularity plays a key role in cache performance. Therefore, we present an automatic approach for selecting effective grain sizes, based on a new working set profiling algorithm that is an order of magnitude faster than previous approaches. This is the first paper demonstrating the effectiveness of PDF on real benchmarks, providing a direct comparison between PDF and WS, revealing the limiting factors for PDF in practice, and presenting an approach for overcoming these factors.

REFERENCES

• 1: U. A. Acar, G. E. Blelloch, and R. D. Blumofe. The data locality of work stealing. Theory of Computing Systems, 35(3), 2002.
• 2: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 3: James H. Anderson , John M. Calandrino, Parallel Real-Time Task Scheduling on Multicore Platforms, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.89-100, December 05-08, 2006 [doi>10.1109/RTSS.2006.32]
• 4: R. Balasubramonian, D. H. Albonesi, A. Buyuktosunoglu, and S. Dwarkadas. A dynamically tunable memory hierarchy. IEEE Trans. on Computers, 52(10), 2003.
• 5: Guy E. Blelloch , Phillip B. Gibbons, Effectively sharing a cache among threads, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007948]
• 6: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999 [doi>10.1145/301970.301974]
• 7: Guy E. Blelloch , Phillip B. Gibbons , Girija J. Narlikar , Yossi Matias, Space-efficient scheduling of parallelism with synchronization variables, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.12-23, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258494]
• 8: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• 9: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 10: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 11: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564 ]
• 12: J. M. Borkenhagen, R. J. Eickemeyer, R. N. Kalla, and S. R. Kunkel. A multithreaded PowerPC processor for commercial servers. IBM JRD, 44(6), 2000.
• 13: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 14: G. Chen, H. Chen, M. Haurylau, N. Nelson, D. Albonesi, P. M. Fauchet, and E. G. Friedman. Electrical and optical on-chip interconnects in scaled microprocessors. In International Symp. on Circuits and Systems, 2005.
• 15: Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Inspector joins, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: S. Chen, P. B. Gibbons, M. Kozuch, V. Liaskovitis, A. Ailamaki, G. E. Blelloch, B. Falsafi, L. Fix, N. Hardavellas, T. C. Mowry, and C. Wilkerson. Scheduling threads for constructive cache sharing on CMPs. Technical Report IRP-TR-07-01, Intel Research Pittsburgh, 2007.
• 17: Y.-Y. Chen, J.-K. Peir, and C.-T. King. Performance of shared caches on multithreaded architectures. J. of Information Science and Engineering, 14(2), 1998.
• 18: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Optimizing Replication, Communication, and Capacity Allocation in CMPs, Proceedings of the 32nd annual international symposium on Computer Architecture, p.357-368, June 04-08, 2005
• 19: Joachim Clabes , Joshua Friedrich , Mark Sweet , Jack DiLullo , Sam Chu , Donald Plass , James Dawson , Paul Muench , Larry Powell , Michael Floyd , Balaram Sinharoy , Mike Lee , Michael Goulet , James Wagoner , Nicole Schwartz , Steve Runyon , Gary Gorman , Phillip Restle , Ronald Kalla , Joseph McGill , Steve Dodson, Design and implementation of the POWER5™ microprocessor, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996749]
• 20: John D. Davis , James Laudon , Kunle Olukotun, Maximizing CMP Throughput with Mediocre Cores, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.51-62, September 17-21, 2005 [doi>10.1109/PACT.2005.42]
• 21: S. Eddy. HMMER: profile HMMs for protein sequence analysis. http://hmmer.wustl.edu/.
• 22: Alexandra Fedorova , Margo Seltzer , Christoper Small , Daniel Nussbaum, Performance of multithreaded chip multiprocessors and implications for operating system design, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.26-26, April 10-15, 2005, Anaheim, CA
• 23: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 24: Seongbeom Kim , Dhruba Chandra , Yan Solihin, Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, September 29-October 03, 2004 [doi>10.1109/PACT.2004.15]
• 25: Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
• 26: T. Moreshet, R. I. Bahar, and M. Herlihy. Energy-aware microprocessor synchronization: Transactional memory vs. locks. In WMPI, 2006.
• 27: G. J. Narlikar. A parallel, multithreaded decision tree builder. Technical Report CMU-CS-98-184, Carnegie Mellon University, 1998.
• 28: Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 1999 [doi>10.1145/314602.314607]
• 29: S. Parekh, S. Eggers, and H. Levy. Thread-sensitive scheduling for SMT processors. Technical report, U. Washington, 2000.
• 30: 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
• 31: R. Saavedra-Barrera , D. Culler , T. von Eicken, Analysis of multithreaded architectures for parallel computing, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.169-178, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97683]
• 32: Semiconductor Industry Association. The International Technology Roadmap for Semiconductors (ITRS) 2005 Edition, 2005.
• 33: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
• 34: P. Shivakumar and N. P. Jouppi. Cacti 3.0: An integrated cache timing, power and area model. Technical Report WRL 2001/2, Compaq Computer Corporation, 2001.
• 35: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 36: G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy [doi>10.1145/377792.377797]
• 37: G. Edward Suh , Srinivas Devadas , Larry Rudolph, A New Memory Monitoring Scheme for Memory-Aware Scheduling and Partitioning, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.117, February 02-06, 2002
• 38: G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004 [doi>10.1023/B:SUPE.0000014800.27383.8f]
• 39: Dominique Thiebaut , Harold S. Stone, Footprints in the cache, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.305-329, Nov. 1987 [doi>10.1145/29868.32979]
• 40: M. W. Weissmann. Libpmsort. http://freshmeat.net/projects/libpmsort.
• 41: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , T. N. Vijaykumar, Exploiting Choice in Resizable Cache Design to Optimize Deep-Submicron Processor Energy-Delay, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.151, February 02-06, 2002
• 42: Michael Zhang , Krste Asanovic, Victim Replication: Maximizing Capacity while Hiding Wire Delay in Tiled Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.336-345, June 04-08, 2005

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Measurement, Performance

Keywords:
chip multiprocessors, constructive cache sharing, parallel depth first, scheduling algorithms, thread granularity, work stealing, working set profiling