Combinable memory-block transactions

ABSTRACT

This paper formalizes and studies combinable memory-block transactions (MBTs). The idea is to encode short programs that operate on a single cache/memory block and then to specify such a program with a memory request. The code is then executed at the cache or memory controller, atomically with respect to other accesses to that block by this or other processors. The combinable form allows combining within the memory system or network. In addition to allowing for the standard set of read-modify-write operations (e.g., test-and-set, compare-and-swap, fetch-and-add), MBTs can be used to define other useful operations--such as a fetch-and-add that does not decrement below zero.

We show how MBTs can be used to design simple and efficient implementations of a variety of protocols and algorithms, including a priority write, a semaphore with a non-blocking P operation, a bounded queue, and a timestamp-based transactional memory system. In all cases the protocols gain some advantage by using MBTs that are different from the standard set of operations. To gain an understanding of the efficiency that can be gained by using combining, we define a notion of bounded contention and show that all our protocols have bounded contention under arbitrary loads.

REFERENCES

• 1: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 2: G. E. Blelloch, P. Cheng, and P. B. Gibbons. Scalable room synchronizations. Theory Comput. Syst., 36(5):397--430, 2003.
• 3: Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997 [doi>10.1145/268999.269000]
• 4: Zhen Fang , Lixin Zhang , John B. Carter , Ali Ibrahim , Michael A. Parker, Active memory operations, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275004]
• 5: Faith Ellen Fich , Danny Hendler , Nir Shavit, On the inherent weakness of conditional primitives, Distributed Computing, v.18 n.4, p.267-277, March 2006 [doi>10.1007/s00446-005-0136-5]
• 6: P. B. Gibbons , Y. Matias , V. Ramachandran, The queue-read queue-write asynchronous PRAM model, Theoretical Computer Science, v.196 n.1-2, p.3-29, April 6, 1998 [doi>10.1016/S0304-3975(97)00193-X]
• 7: A. Gottlieb , R. Grishman , C. P. Kruskal , K. P. McAuliffe , L. Rudolph , M. Snir, The NYU Ultracomputer Designing an MIMD Shared Memory Parallel Computer, IEEE Transactions on Computers, v.32 n.2, p.175-189, February 1983 [doi>10.1109/TC.1983.1676201]
• 8: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 9: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 10: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 11: IBM T.J. Watson Res. Ctr. System/370 principles of operations. Technical report, IBM, 1983.
• 12: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 13: Prasad Jayanti , King Tan , Sam Toueg, Time and Space Lower Bounds for Nonblocking Implementations, SIAM Journal on Computing, v.30 n.2, p.438-456, 2000 [doi>10.1137/S0097539797317299]
• 14: Anna R. Karlin , Eli Upfal, Parallel hashing: an efficient implementation of shared memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988 [doi>10.1145/48014.350550]
• 15: P. M. Kogge and H. S. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. on Computers, C--22(8):786--793, 1973.
• 16: Clyde P. Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.579-601, Oct. 1988 [doi>10.1145/48022.48024]
• 17: D. J. Kuck, E. S. Davidson, D. H. Lawrie, and A. H. Sameh. Parallel supercomputing today and the Cedar approach. Science, 231:967--974, 1986.
• 18: J. R. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2007.
• 19: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 20: D. Lenoski , J. Laudon , T. Joe , D. Nakahira , L. Stevens , A. Gupta , J. Hennessy, The DASH Prototype: Logic Overhead and Performance, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.41-61, January 1993 [doi>10.1109/71.205652]
• 21: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 22: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 23: G. F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. McAuliffe, E. A. Melton, V. A. Norton, and J. Weiss. The IBM Research parallel processor prototype(RP3): Introduction and architecture. In Proc. IEEE Int'l Conf. on Parallel Processing}, pages 764--771, 1985.
• 24: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• 25: R. M. Shapiro and R. E. Millstein. Rehability and fault recovery in distributed processing. In Oceans'77 Conf Record, vol II, 1977.
• 26: N. Shavit and D. Touitou. Software transactional memory. Distrib. Comput., 10(2):99--116, 1997.
• 27: Thinking Machines Corporation. Model CM-2 technical summary. Technical Report HA87-4, Thinking Machines Corporation, Cambridge, Massachusetts, 1987.
• 28: R. H. Thomas. A solution to the concurrency control problem for multiple copy databases. In Proc. IEEE COMP-CON Conf., 1978.
• 29: R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, 1986.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
combining, contention, linearizability, memory-block transactions, priority write, queue, read-modify-write, semaphore, shared memory, stack, transactional memory