Extensible transactional memory testbed. (English) Zbl 1233.68164
Summary: Transactional memory (TM) is a promising abstraction as it hides all synchronization complexities from the programmers of concurrent applications. More particularly, the TM paradigm operated a complexity shift from the application programming to the TM programming. Therefore, expert programmers have now started to look for the ideal TM that will bring, once-for-all, performance to all concurrent applications. Researchers have recently identified numerous issues TMs may suffer from. Surprisingly, no TMs have ever been tested in these scenarios. In this paper, we present the first to date TM testbed. We propose a framework, TMunit, that provides a domain specific language to write rapidly TM workloads so that our test-suite is easily extensible. Our reproducible semantic tests indicate through reproducible counter-examples that existing TMs do not satisfy recent consistency criteria. Our performance tests identify workloads where well-known TMs perform differently. Finally, additional tests indicate some workloads preventing contention managers from progressing.
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Software:
ALPBench; Eraser; STAMP; Specomp; tm_db; Lee-TM; WormBench; STMBench7; ConTest; Minebench; TMunit; PARSEC; AVIO; veriSoft; SPLASH-2References:
| [1] | Abadi, M.; Birrell, A.; Harris, T.; Isard, M.: Semantics of transactional memory and automatic mutual exclusion, SIGPLAN not. 43, No. 1, 63-74 (2008) · Zbl 1295.68149 |
| [2] | Evaluation of the advanced synchronization facility (ASF), 2009 http://forums.amd.com/devblog/blogpost.cfm?threadid=118419&catid=317. |
| [3] | Ansari, M.; Kotselidis, C.; Jarvis, K.; Luján, M.; Kirkham, C.; Watson, I.: Lee-TM: a non-trivial benchmark for transactional memory, , 196-207 (2008) |
| [4] | Aslot, V.; Domeika, M. J.; Eigenmann, R.; Gaertner, G.; Jones, W. B.; Parady, B.: Specomp: a new benchmark suite for measuring parallel computer performance, , 1-10 (2001) · Zbl 0986.68740 |
| [5] | Ben-Asher, Y.; Farchi, E.; Eytani, Y.: Heuristics for finding concurrent bugs, , 288.1 (2003) |
| [6] | Bienia, C.; Kumar, S.; Singh, J. P.; Li, K.: The PARSEC benchmark suite: characterization and architectural implications, , 72-81 (2008) |
| [7] | Blundell, C.; Lewis, E.; Martin, M.: Deconstructing transactional semantics: the subtleties of atomicity, (2005) |
| [8] | Minh, C. Cao; Chung, J.; Kozyrakis, C.; Olukotun, K.: STAMP: Stanford transactional applications for multi-processing, , 35-46 (2008) |
| [9] | Chung, J.; Chafi, H.; Minh, C.; Mcdonald, A.; Carlstrom, B.; Olukotun, K. Kozyrakis C.: The common case transactional behavior of multithreaded programs, , 266-277 (2006) · Zbl 1119.68041 |
| [10] | Dalessandro, L.; Marathe, V. J.; Spear, M. F.; Scott, M. L.: Capabilities and limitations of library-based software transactional memory in C++, (2007) · Zbl 1283.68122 |
| [11] | Dice, D.; Shalev, O.; Shavit, N.: Transactional locking II, , 194-208 (2006) |
| [12] | Dragojevic, A.; Guerraoui, R.; Kapalka, M.: Stretching transactional memory, , 155-165 (2009) · Zbl 1315.68065 |
| [13] | Edelstein, O.; Farchi, E.; Goldin, E.; Nir, Y.; Ratsaby, G.; Ur, S.: Framework for testing multi-threaded Java programs, Concurrency comput. Pract. exp. 15, No. 3–5, 485-499 (2003) · Zbl 1009.68542 · doi:10.1002/cpe.654 |
| [14] | Felber, P.; Fetzer, C.; Riegel, T.: Dynamic performance tuning of word-based software transactional memory, , 237-246 (2008) |
| [15] | Felber, P.; Gramoli, V.; Guerraoui, R.: Elastic transactions, Lncs 5805, 93-107 (2009) · Zbl 1261.68024 |
| [16] | Godefroid, P.: Model checking for programming languages using verisoft, , 174-186 (1997) |
| [17] | Gramoli, V.; Harmanci, D.; Felber, P.: Toward a theory of input acceptance for transactional memories, Lncs 5401, 527-533 (2008) |
| [18] | Gray, J.; Reuter, A.: Transaction processing: concepts and techniques, (1992) · Zbl 0781.68006 |
| [19] | Guerraoui, R.; Henzinger, T. A.; Jobstmann, B.; Singh, V.: Model checking transactional memories, , 372-382 (2008) · Zbl 1160.68441 |
| [20] | Guerraoui, R.; Henzinger, T. A.; Singh, V.: Nondeterminism and completeness in transactional memories, , 21-35 (2008) · Zbl 1160.68441 |
| [21] | Guerraoui, R.; Henzinger, T. A.; Singh, V.: Software transactional memory on relaxed memory models, , 321-336 (2009) · Zbl 1242.68162 |
| [22] | Guerraoui, R.; Herlihy, M.; Pochon, B.: Polymorphic contention management, , 303-323 (2005) · Zbl 1314.68088 |
| [23] | Harmanci, D.; Felber, P.; Gramoli, V.; Fetzer, C.: Tmunit: testing software transactional memories, (2009) · Zbl 1233.68164 |
| [24] | Harris, T.; Fraser, K.: Language support for lightweight transactions, , 388-402 (2003) |
| [25] | Herlihy, M.; Lev, Y.: Tm_db: a generic debugging library for transactional programs, , 136-145 (2009) |
| [26] | Herlihy, M.; Wing, J. M.: Linearizability: a correctness condition for concurrent objects, ACM trans. Program. lang. Syst. 12, No. 3, 463-492 (1990) |
| [27] | Herlihy, M.; Luchangco, V.; Moir, M.; Iii, W. N. Scherer: Software transactional memory for dynamic-sized data structures, , 92-101 (2003) |
| [28] | Imbs, D.; De Mendvil, J. R. González; Raynal, M.: Virtual world consistency: a new condition for STM systems, , 280-281 (2009) |
| [29] | Jaleel, A.; Mattina, M.; Jacob, B.: Last level cache (LLC) performance of data mining workloads on a CMP – a case study of parallel bioinformatics workloads, , 88-98 (2006) |
| [30] | Guerraoui, R.; Kapałka, M.: On the correctness of transactional memory, , 175-184 (2008) |
| [31] | Guerraoui, R.; Kapałka, M.; Vitek, J.: Stmbench7: a benchmark for software transactional memory, SIGOPS oper. Syst. rev. 41, No. 3, 315-324 (2007) |
| [32] | Kestor, G.; Stipic, S.; Unsal, O. S.; Cristal, A.; Valero, M.: RMS-TM: a transactional memory benchmark for recognition, mining and synthesis applications, (2009) |
| [33] | Larus, J.; Rajwar, R.: Transactional memory, (2006) |
| [34] | Lev, Y.; Luchangco, V.; Marathe, V.; Moir, M.; Nussbaum, D.; Olszewski, M.: Anatomy of a scalable software transactional memory, (2009) |
| [35] | Long, B.; Hoffman, D.; Strooper, P.: Tool support for testing concurrent Java components, IEEE trans. Softw. eng. 29, No. 6, 555-566 (2003) |
| [36] | J. Lourenço, G. Cunha, Testing patterns for software transactional memory engines, in: ACM Workshop on Parallel and Distributed Systems: Testing and Debugging, 2007, pp. 36–42. |
| [37] | Lu, S.; Tucek, J.; Qin, F.; Zhou, Y.: AVIO: detecting atomicity violations via access interleaving invariants, , 37-48 (2006) |
| [38] | Lucia, B.; Devietti, J.; Strauss, K.; Ceze, L.: Atom-aid: detecting and surviving atomicity violations, , 277-288 (2008) |
| [39] | Sasanka, R. Man-Lap Li; Adve, S.; Chen, Y. -K.; Debes, E.: The alpbench benchmark suite for complex multimedia applications, , 34-45 (2005) |
| [40] | Manovit, C.; Hangal, S.; Chafi, H.; Mcdonald, A.; Kozyrakis, C.; Olukotun, K.: Testing implementations of transactional memory, , 134-143 (2006) |
| [41] | Menon, V.; Balensiefer, S.; Shpeisman, T.; Adl-Tabatabai, A. -R.; Hudson, R. L.; Saha, B.; Welc, A.: Practical weak-atomicity semantics for Java STM, , 314-325 (2008) |
| [42] | Musuvathi, M.; Qadeer, S.; Ball, T.; Basler, G.; Nainar, P. A.; Neamtiu, I.: Finding and reproducing heisenbugs in concurrent programs, , 267-280 (2008) |
| [43] | Narayanan, R.; Ozisikyilmaz, B.; Zambreno, J.; Memik, G.; Choudhary, A.: Minebench: a benchmark suite for data mining workloads, , 182-188 (2006) |
| [44] | O’leary, J.; Saha, B.; Tuttle, M. R.: Model checking transactional memory with spin, , 335-342 (2009) |
| [45] | Papadimitriou, C. H.: The serializability of concurrent database updates, J. ACM 26, No. 4, 631-653 (1979) · Zbl 0419.68036 · doi:10.1145/322154.322158 |
| [46] | Perfumo, C.; Sönmez, N.; Stipic, S.; Unsal, O.; Cristal, A.; Harris, T.; Valero, M.: The limits of software transactional memory (STM): dissecting haskell STM applications on a many-core environment, , 67-78 (2008) |
| [47] | Pugh, W.; Ayewah, N.: Unit testing concurrent software, , 513-516 (2007) |
| [48] | Riegel, T.; Felber, P.; Fetzer, C.: A lazy snapshot algorithm with eager validation, , 284-298 (2006) · Zbl 1155.68341 · doi:10.1007/11864219_20 |
| [49] | T. Riegel, C. Fetzer, H. Sturzrehm, P. Felber, From causal to z-linearizable transactional memory, Université de Neuchâtel, Switzerland, 2007. · Zbl 1283.68120 |
| [50] | Savage, S.; Burrows, M.; Nelson, G.; Sobalvarro, P.; Anderson, T.: Eraser: a dynamic data race detector for multithreaded programs, ACM trans. Comput. syst. 15, No. 4, 391-411 (1997) |
| [51] | W.N. Scherer III, M.L. Scott, Contention management in dynamic software transactional memory, in: Workshop on Concurrency and Synchronization in Java Programs, 2004. |
| [52] | Shpeisman, T.; Menon, V.; Adl-Tabatabai, A. -R.; Balensiefer, S.; Grossman, D.; Hudson, R. L.; Moore, K. F.; Saha, B.: Enforcing isolation and ordering in STM, SIGPLAN not. 42, No. 6, 78-88 (2007) |
| [53] | Spear, M.; Dalessandro, L.; Marathe, V.; Scott, M.: A comprehensive strategy for contention management in software transactional memory, , 141-150 (2009) |
| [54] | S.D. Stoller, Testing concurrent Java programs using randomized scheduling, in; Workshop on Runtime Verification, vol. 70(4), 2002, pp. 142–157. |
| [55] | Tai, K. -C.; Carver, R. H.; Obaid, E. E.: Debugging concurrent ada programs by deterministic execution, IEEE trans. Softw. eng. 17, No. 1, 45-63 (1991) |
| [56] | Woo, S. C.; Ohara, M.; Torrie, E.; Singh, J. P.; Gupta, A.: The splash-2 programs: characterization and methodological considerations, , 24-36 (1995) |
| [57] | Zyulkyarov, F.; Cvijic, S.; Unsal, O.; Cristal, A.; Ayguade, E.; Harris, T.; Valero, M.: Wormbench – a configurable workload for evaluating transactional memory systems, , 61-68 (2008) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
