Multi-execution: multicore caching for data-similar executions

ABSTRACT

While microprocessor designers turn to multicore architectures to sustain performance expectations, the dramatic increase in parallelism of such architectures will put substantial demands on off-chip bandwidth and make the memory wall more significant than ever. This paper demonstrates that one profitable application of multicore processors is the execution of many similar instantiations of the same program. We identify that this model of execution is used in several practical scenarios and term it as "multi-execution." Often, each such instance utilizes very similar data. In conventional cache hierarchies, each instance would cache its own data independently. We propose the Mergeable cache architecture that detects data similarities and merges cache blocks, resulting in substantial savings in cache storage requirements. This leads to reductions in off-chip memory accesses and overall power usage, and increases in application performance. We present cycle-accurate simulation results of 8 benchmarks (6 from SPEC2000) to demonstrate that our technique provides a scalable solution and leads to significant speedups due to reductions in main memory accesses. For 8 cores running 8 similar executions of the same application and sharing an exclusive 4-MB, 8-way L2 cache, the Mergeable cache shows a speedup in execution by 2.5x on average (ranging from 0.93x to 6.92x), while posing an overhead of only 4.28% on cache area and 5.21% on power when it is used.

REFERENCES

• 1: Tilera TILE Multicore Processors: http://www.tilera.com/products/processors.php.
• 2: Ambric Am2000 Family Massively Parallel Processor Array: http://www.ambric.com/products/index.php.
• 3: Nvidia GT200 Series: http://www.nvidia.com/object/geforce gtx 280.html.
• 4: PolyScalar: http://users.csc.calpoly.edu/franklin/PolyScalar/Home.htm.
• 5: SPEC CPU2000: http://www.spec.org/cpu/.
• 6: icsiboost: http://code.google.com/p/icsiboost/.
• 7: Alaa R. Alameldeen , David A. Wood, Adaptive Cache Compression for High-Performance Processors, Proceedings of the 31st annual international symposium on Computer architecture, p.212, June 19-23, 2004, München, Germany
• 8: A. Asuncion and D. Newman. UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, 2007. http://www.ics.uci.edu/mlearn/MLRepository.html.
• 9: S. Bederman. Cache Management System Using Virtual and Real Tags in The Cache Directory. IBM Technical Disclosure, 21(11), April 1979.
• 10: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 11: Matthew Bridges , Neil Vachharajani , Yun Zhang , Thomas Jablin , David August, Revisiting the Sequential Programming Model for Multi-Core, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.69-84, December 01-05, 2007 [doi>10.1109/MICRO.2007.35]
• 12: C.-C. Chang and C.-J. Lin. LIBSVM: a Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm.
• 13: Jichuan Chang , Gurindar S. Sohi, Cooperative Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 14: Michael Chu , Rajiv Ravindran , Scott Mahlke, Data Access Partitioning for Fine-grain Parallelism on Multicore Architectures, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.369-380, December 01-05, 2007 [doi>10.1109/MICRO.2007.11]
• 15: Douglas C. Burger and Todd M. Austin. The SimpleScalar Tool Set, Version 2.0. Technical Report CS-TR-1997-1342, University of Wisconsin, Madison, June 1997.
• 16: K. C. Elliott. Varieties of Exploratory Experimentation in Nanotoxicology. History and Philosophy of the Life Sciences, 29(3), 2007.
• 17: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2002 [doi>10.1109/L-CA.2002.8]
• 18: T. Kurihara, E. Kamada, K. Shimada, and T. Shimizu. A RISC Processor for SR8000: Accelerating Large Scale Scientific Computing with SMP. In IEEE Symposium on High Performance Chips(HOT CHIPS), 1999.
• 19: Fernando Lozano , Pedro Rangel, Algorithms for parallel boosting, Proceedings of the Fourth International Conference on Machine Learning and Applications, p.368-373, December 15-17, 2005 [doi>10.1109/ICMLA.2005.8]
• 20: Marios Kleanthous , Yiannakis Sazeides, CATCH: a mechanism for dynamically detecting Cache-Content-Duplication and its application to instruction caches, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403720]
• 21: M. Nedjalkov , H. Kosina , S. Selberherrr, Monte Carlo algorithms for stationary device simulations, Mathematics and Computers in Simulation, v.62 n.3-6, p.453-461, 3 March 2003 [doi>10.1016/S0378-4754(02)00246-X]
• 22: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 23: Jih-Kwon Peir , Windsor W. Hsu , Alan Jay Smith, Functional Implementation Techniques for CPU Cache Memories, IEEE Transactions on Computers, v.48 n.2, p.100-110, February 1999 [doi>10.1109/12.752651]
• 24: Joydeep Ray , James C. Hoe , Babak Falsafi, Dual use of superscalar datapath for transient-fault detection and recovery, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 25: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 26: Eric Rotenberg, AR-SMT: A Microarchitectural Approach to Fault Tolerance in Microprocessors, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.84, June 15-18, 1999
• 27: S. Wilton and N. Jouppi. CACTI: An Enhanced Cache Access and Cycle Time Model. IEEE Journal of Solid-State Circuits, 31(5):677--688, May 1996.
• 28: K. Solanki, N. Jacobsen, S. Chandrasekaran, U. Madhow, and B. S. Manjunath. High-Volume Data Hiding in Images: Introducing Perceptual Criteria into Quantization Based Embedding. In Proceedings of the IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), volume 4, pages 3485--3488, May 2002.
• 29: P. Sollich and A. Krogh. Learning With Ensembles: How Overfitting Can Be Useful. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8, pages 190--196. The MIT Press, 1996.
• 30: D. J. Sorin, M. M. K. Martin, M. D. Hill, and D. A. Wood. Fast Checkpoint/Recovery to Support Kilo-Instruction Speculation and Hardware Fault Tolerance. (TR-1420), October 2000.
• 31: J. Gregory Steffan , Christopher Colohan , Antonia Zhai , Todd C. Mowry, The STAMPede approach to thread-level speculation, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.253-300, August 2005 [doi>10.1145/1082469.1082471]
• 32: Carl A. Waldspurger, Memory resource management in VMware ESX server, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844146]
• 33: David Wang , Brinda Ganesh , Nuengwong Tuaycharoen , Kathleen Baynes , Aamer Jaleel , Bruce Jacob, DRAMsim: a memory system simulator, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105748]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Management, Measurement, Performance

Keywords:
cmp, data similar execution, multicore cache design