IWannaBit!

ABSTRACT

Just One Lousy Bit! I want to know if any memory operation misses or any line in my L1 cache gets evicted. Why? Because with this one Bit I can write any number of lock-free algorithms easily. This Bit gives me an N-word atomic read set, and with a typical Store Conditional instruction a 1-word atomic write set. The algorithm writing community has begged for D-CAS or Hardware Transactional Memory for years, but proposals far outstrip implementations: neither are available on any commodity system. With this Bit I hope to lower the hardware costs as low as possible while still being useful.

REFERENCES

• 1: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 2: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 3: 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
• 4: 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]
• 5: Simon Doherty , David L. Detlefs , Lindsay Groves , Christine H. Flood , Victor Luchangco , Paul A. Martin , Mark Moir , Nir Shavit , Guy L. Steele, Jr., DCAS is not a silver bullet for nonblocking algorithm design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007945]
• 6: 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
• 7: 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
• 8: Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, 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.1123003]
• 9: Moore, K., Bobba, J., Moravan, M., Hill, M., Wood, D. 2006. LogTM: Log-based Transactional Memory. In Proc. of the 12^th Annual Intl. Symp. on High Performance Computer Architecture.
• 10: Owens, J., Luebke, D., Govindaraju, N., Harris, M. Krüger, J., Lefohn, A., Purcell, T. A Survey of General-Purpose Computation on Graphics Hardware. Computer Graphics Forum, V 26 N 1, Mar 2007, pg 80--113.
• 11: Chris Purcell , Tim Harris, Brief announcement: implementing multi-word atomic snapshots on current hardware, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011829]
• 12: 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
• 13: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 14: 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]
• 15: 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]
• 16: Standard Performance Evaluation Corporation. SPECjbb2005 (Java Business Benchmark) Documentation, release 1.07, 2005.
• 17: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 18: John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224988]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Languages, Performance

Keywords:
hardware transactional memory, lock-free algorithms, locking, non-blocking algorithms, software transactional memory