Software transactional memory for multicore embedded systems

ABSTRACT

Embedded systems, like general-purpose systems, can benefit from parallel execution on a symmetric multicore platform. Unfortunately, concurrency issues present in general-purpose programming also apply to embedded systems, protection from which is currently only offered with performance-limiting coarse-grained locking or error-prone and difficult-to-implement fine-grained locking. Transactional memory offers relief from these mechanisms, but has primarily been investigated on general-purpose systems. In this paper, we present Embedded Software Transactional Memory (ESTM) as a novel solution to the concurrency problem in parallel embedded applications. We investigate common software transactional memory design decisions and discuss the best decisions for an embedded platform. We offer a full implementation of an embedded STM and test it against both coarse-grained and fine-grained locking mechanisms. We find that we can meet or beat the performance of fine-grained locking over a range of application characteristics, including size of shared data, time spent in the critical section, and contention between threads. Our ESTM implementation benefits from the effective use of L1 memory, a feature which is built into our STM model but which cannot be directly utilized by traditional locking mechanisms.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 2: Analog Devices, Inc. ADSP-BF53x/BF56x Blackfin Processor Programming Reference, revision 1.2 ed. One Technology Way, Norwood, Mass, 02062, February 2007.
• 3: Analog Devices, Inc. ADSP-BF561 Blackfin Processor Hardware Reference, revision 1.1 ed. One Technology Way, Norwood, Mass, 02062, February 2007.
• 4: Analog Devices, Inc. Visual DSP 5.0 Kernel (VDK) User's Guide, revision 3.0 ed. One Technology Way, Norwood, Mass, 02062, August 2007.
• 5: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 6: James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224985]
• 7: James H. Anderson , Srikanth Ramamurthy , Rohit Jain, Implementing wait-free objects on priority-based systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.229-238, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259443]
• 8: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 9: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 10: Colin Blundell , Joe Devietti , E. Christopher Lewis , Milo M. K. Martin, Making the fast case common and the uncommon case simple in unbounded transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 11: Crowl, L., Lev, Y., Luchangco, V., Moir, M., and Nussbaum, D. Integrating transactional memory into C. In TRANSACT'07: ACM SIGPLAN Workshop on Transactional Computing (2007), ACM.
• 12: 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
• 13: Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In DISC'06: Proceedings of the 20th International Symposium on Distributed Computing (September 2006), ACM, pp. 194--208.
• 14: Dave Dice , Nir Shavit, Understanding Tradeoffs in Software Transactional Memory, Proceedings of the International Symposium on Code Generation and Optimization, p.21-33, March 11-14, 2007 [doi>10.1109/CGO.2007.38]
• 15: Bernhard Egger , Chihun Kim , Choonki Jang , Yoonsung Nam , Jaejin Lee , Sang Lyul Min, A dynamic code placement technique for scratchpad memory using postpass optimization, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176788]
• 16: Ennals, R. Software transactional memory should not be obstruction-free. Tech. Rep. IRC-TR-06-052, Intel Research Cambridge, January 2006.
• 17: Cesare Ferri , Tali Moreshet , R. Iris Bahar , Luca Benini , Maurice Herlihy, A hardware/software framework for supporting transactional memory in a MPSoC environment, ACM SIGARCH Computer Architecture News, v.35 n.1, March 2007 [doi>10.1145/1241601.1241611]
• 18: Poletti Francesco , Paul Marchal , David Atienza , Luca Benini , Francky Catthoor , Jose M. Mendias, An integrated hardware/software approach for run-time scratchpad management, Proceedings of the 41st annual Design Automation Conference, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996634]
• 19: Keir Fraser , Tim Harris, Concurrent programming without locks, ACM Transactions on Computer Systems (TOCS), v.25 n.2, p.5-es, May 2007 [doi>10.1145/1233307.1233309]
• 20: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 21: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 22: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 23: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 24: Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 25: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 26: 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
• 27: T. S. Rajesh Kumar , R. Govindarajan , C. P. Ravi Kumar, Optimal Code and Data Layout in Embedded Systems, Proceedings of the 16th International Conference on VLSI Design, p.573, January 04-08, 2003
• 28: Marathe, V. J., III, W. N. S., and Scott, M. L. Adaptive software transactional memory. In DISC 19: In Proceedings of the 19th International Symposium on Distributed Computing (2005).
• 29: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 30: Marathe, V. J., Spear, M. F., Heriot, C., Acharya, A., Eisenstat, D., III, M. N. S., and Scott, M. L. Lowering the overhead of nonblocking software transactional memory. In TRANSACT'06: ACM SIGPLAN Workshop on Transactional Computing (June 2006), ACM.
• 31: Mark Moir, Transparent Support for Wait-Free Transactions, Proceedings of the 11th International Workshop on Distributed Algorithms, p.305-319, September 24-26, 1997
• 32: Matteo Monchiero , Gianluca Palermo , Cristina Silvano , Oreste Villa, Power/performance hardware optimization for synchronization intensive applications in MPSoCs, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 33: Moore, K., Bobba, J., Moravan, M., Hill, M., and Wood, D. Log': Log-based transactional memory. In High-Performance Computer Architecture, 2006. The Twelfth International Symposium on (Feb. 2006).
• 34: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 35: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, 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.1123001]
• 36: Bratin Saha , Ali-Reza Adl-Tabatabai , Quinn Jacobson, Architectural Support for Software Transactional Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.185-196, December 09-13, 2006 [doi>10.1109/MICRO.2006.9]
• 37: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Experimentation, Performance

Keywords:
embedded systems, locking, multicore, software transactional memory (stm), synchronization, transactions