The limits of software transactional memory (STM): dissecting Haskell STM applications on a many-core environment

ABSTRACT

In this paper, we present a Haskell Transactional Memory benchmark to provide a comprehensive application suite for the use of Software Transactional Memory (STM) researchers. We develop a framework to profile the execution of the benchmark applications and to collect detailed runtime data on their transactional behavior, running them on a 128-core multiprocessor. Using a composite of the collected raw data, we propose new transactional performance metrics. We analyze key statistics related to scalability, atomic sections, transactional events, overall transactional overhead and the relative hardware performance, accordingly drawing conclusions on the results. Our findings advance our comprehension on the STM runtime and the characteristics of different applications under the transactional management of the pure, functional programming language, Haskell.

REFERENCES

• 1: Haskell official site: http://www.haskell.org.
• 2: Sgi numalink interconnect fabric: http://www.sgi.com/products/servers/altix/numalink.html.
• 3: K. Albayraktaroglu , A. Jaleel , Xue Wu , M. Franklin , B. Jacob , Chau-Wen Tseng , D. Yeung, BioBench: A Benchmark Suite of Bioinformatics Applications, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.2-9, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430554]
• 4: Jayaram Bobba , Kevin E. Moore , Haris Volos , Luke Yen , Mark D. Hill , Michael M. Swift , David A. Wood, Performance pathologies in hardware transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: S. Browne , J. Dongarra , N. Garner , G. Ho , P. Mucci, A Portable Programming Interface for Performance Evaluation on Modern Processors, International Journal of High Performance Computing Applications, v.14 n.3, p.189-204, August 2000 [doi>10.1177/109434200001400303]
• 6: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 7: J. Chung, H. Chafi, C. Cao Minh, A. McDonald, B. D. Carlstrom, C. Kozyrakis, and K. Olukotun. The common case transactional behavior of multithreaded programs. In 12th HPCA. Feb 2006.
• 8: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 9: H. Daume III. Yet another haskell tutorial. In www.cs.utah.edu/ hal/docs/daume02yaht.pdf. 2002-2006.
• 10: T. Fruhwirth. Parallelizing union-find in constraint handling rules using confluence. In 21st Conference on Logic Programming ICLP. Oct 2005.
• 11: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 12: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 13: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 14: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 15: Edmund S. L. Lam , Martin Sulzmann, A concurrent constraint handling rules implementation in Haskell with software transactional memory, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.19-24, January 16-16, 2007, Nice, France [doi>10.1145/1248648.1248653]
• 16: J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, 2006.
• 17: L. Man-Lap, R. Sasanka, S. V. Adve, Y.-K. Chen, and E. Debes. The alpbench benchmark suite for complex multimedia applications. In Procs. of IISWC-2005. Oct 2005.
• 18: Cameron McNairy , Rohit Bhatia, Montecito: A Dual-Core, Dual-Thread Itanium Processor, IEEE Micro, v.25 n.2, p.10-20, March 2005 [doi>10.1109/MM.2005.34]
• 19: R. Narayanan, B. Özisikyilmaz, J. Zambreno, G. Memik, and A. N. Choudhary. Minebench: A benchmark suite for data mining workloads. In IISWC, pages 182--188. IEEE, 2006.
• 20: Nicholas Nethercote , Alan Mycroft, The cache behaviour of large lazy functional programs on stock hardware, Proceedings of the 2002 workshop on Memory system performance, p.44-55, June 16-16, 2002, Berlin, Germany
• 21: W. Partain. The nofib benchmark suite of haskell programs. In Workshops in Computing, Springer Verlag. 1993.
• 22: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 23: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 24: T. Skare and C. Kozyrakis. Early release: Friend or foe? In Workshop on Transactional Memory Workloads. Jun 2006.
• 25: N. Sonmez, C. Perfumo, S. Stipic, A. Cristal, O. Unsal., and M. Valero. Unreadtvar: Extending haskell software transactional memory for performance. In TFP 2007. Apr 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Measurement

Keywords:
haskell, instrumentation, transactional memory