Multiword atomic read/write registers on multiprocessor systems

ABSTRACT

Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this article, we also experimentally evaluate the performance of our algorithm, together with lock-based approaches and a practical, previously previously known algorithm that is based that is based only on read and write primitives. The experimental evaluation is performed on three well-known parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases the READERSFIELD algorithm performs better, following its analytical evaluation.

REFERENCES

• 1: Adve, S. V. and Gharachorloo, K. 1996. Shared memory consistency models: A tutorial. IEEE Computer 29, 12, 66--76.
• 2: Barnes, G. 1993. Method for implementing lock-free shared data structures. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures. ACM Press, 261--270.
• 3: Bloom, B. 1988. Constructing two-writer atomic registers. IEEE Transactions on Computers 37, 12 (Dec.), 1506--1514.
• 4: Burns, J. E. and Peterson, G. L. 1987. Constructing multi-reader atomic values from non-atomic values. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, 222--231.
• 5: Chen, J. and Burns, A. 1997. A fully asynchronous reader/writer mechanism for multiprocessor real-time systems. Tech. Rep. YCS-288, Department of Computer Science, University of York. May.
• 6: CORPORATE SPARC International, I. 1994. The SPARC Architecture Manual: Version 9. Prentice-Hall, Inc.
• 7: Cortesi, D. 2004. Topics in IRIXA Programming. Silicon Graphics, Inc. (doc #:007-2478-009).
• 8: Culler, D., Singh, J. P., and Gupta, A. 1998. Parallel Computer Architecture: A Hardware/Software Approach (The Morgan Kaufmann Series in Computer Architecture and Design). Morgan Kaufmann.
• 9: Dubois, M., Scheurich, C., and Briggs, F. 1986. Memory access buffering in multiprocessors. In Proceedings of the 13th Annual International Symposium on Computer Architecture (ISCA'86). 434--442.
• 10: Goodman, J. R. 1989. Cache consistency and sequential consistency. Tech. Rep. 61, IEEE Scalable Coherent Interface (SCI) Working Group.
• 11: Haldar, S. and Vidyasankar, K. 1995. Constructing 1-writer multireader multivalued atomic variable from regular variables. J. ACM 42, 1 (Jan), 186--203.
• 12: Haldar, S. and Vidyasankar, K. 1996. Simple extensions of 1-writer atomic variable constructions to multiwriter ones. Acta Informatica 33, 2, 177--202.
• 13: Haldar, S. and Vitányi, P. 2002. Bounded concurrent timestamp systems using vector clocks. J. ACM 49, 1 (Jan), 101--126.
• 14: Herlihy, M. 1991. Wait-free synchronization. ACM Transaction on Programming and Systems 11, 1 (Jan), 124--149.
• 15: Herlihy, M. 1993. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems 15, 5 (Nov), 745--770.
• 16: Herlihy, M. P. and Wing, J. M. 1990. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12, 3 (July), 463--492.
• 17: Israeli, A. and Li, M. 1993. Bounded time-stamps. Distributed Computing 6, 4, 205--209.
• 18: Israeli, A. and Shaham, A. 1992. Optimal multi-writer multi-reader atomic register. In Proceedings of the 11th Annual Symposium on Principles of Distributed Computing. ACM Press, 71--82.
• 19: Kirousis, L. M., Kranakis, E., and Vitányi, P. M. B. 1987. Atomic multireader register. In Distributed Algorithms, 2nd International Workshop. LNCS, vol. 312. Springer, 1988, 278--296.
• 20: Kopetz, H. and Reisinge, J. 1993. The non-blocking write protocol NBW: A solution to a real-time synchronisation problem. In Proceedings of the Real-Time Systems Symposium. IEEE Computer Society Press, 131--137.
• 21: Lamport, L. 1977. Concurrent reading and writing. Communications of the ACM 20, 11 (Nov), 806--811.
• 22: Lamport, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Computers 28, 9, 690--691.
• 23: Lamport, L. 1986. On interprocess communication. Distributed Computing 1, 2, 77--101.
• 24: Larsson, A., Gidenstam, A., Ha, P. H., Papatriantafilou, M., and Tsigas, P. 2004. Multi-word atomic read/write registers on multiprocessor systems. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA'04) LNCS 3221. Springer-Verlag, 736--748.
• 25: Li, M., Tromp, J., and Vitányi, P. M. B. 1996. How to share concurrent wait-free variables. J. ACM 43, 4 (July), 723--746.
• 26: Li, M. and Vitányi, P. M. B. 1992. Optimality of wait-free atomic multiwriter variables. Information Processing Letters 43, 2 (Aug), 107--112.
• 27: Newman-Wolfe, R. 1987. A protocol for wait-free, atomic, multi-reader shared variables. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, 232--248.
• 28: Peterson, G. L. 1983. Concurrent reading while writing. ACM Transactions on Programming Languages and Systems 5, 1 (Jan), 46--55.
• 29: Peterson, G. L. and Burns, J. E. 1987. Concurrent reading while writing II: The multi-writer case. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE, 383--392.
• 30: Rajkumar, R. 1990. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing Systems (ICDCS '90). IEEE Computer Society Press, 116--123.
• 31: Sha, L., Rajkumar, R., and Lojoczky, J. 1990. Priority inheritence protocols: An approach to real-time syncronization. IEEE Transactions on Computers 39, 9 (Sept), 1175--1185.
• 32: Silberschatz, A., Galvin, P. B., and Gagne, G. 2001. Operating Systems Concepts. Addison-Wesley.
• 33: Silicon Graphics, I. 1993. IRIX 6.5: Man Pages. SGI Techpubs Library.
• 34: Simpson, H. R. 1990. Four-slot fully asynchronous communication mechanism. IEE Proc., Computers and Digital Techniques 137, 1 (Jan.), 17--30.
• 35: Singh, A. K., Anderson, J. H., and Gouda, M. G. 1994. The elusive atomic register. J. ACM 41, 2 (Mar.), 311--339.
• 36: Sundell, H. 2004. Efficient and practical non-blocking data structures. Ph.D. thesis, Chalmers University of Technology.
• 37: Sundell, H. and Tsigas, P. 2002. NOBLE: A non-blocking inter-process communication library. In Proceedings of the 6th Workshop on Languages, Compilers and Run-time Systems for Scalable Computers. LNCS. Springer Verlag.
• 38: Tanenbaum, A. S. 2001. Modern Operating Systems, 2nd ed. Prentice Hall.
• 39: Tsigas, P. and Zhang, Y. 2001. Evaluating the performance of non-blocking synchronisation on shared-memory multiprocessors. In Proceedings of the ACM SIGMETRICS 2001/Performance 2001. ACM Press, 320--321.
• 40: Tsigas, P. and Zhang, Y. 2002. Integrating non-blocking synchronisation in parallel applications: Performance advantages and methodologies. In Proceedings of the 3rd ACM Workshop on Software and Performance (WOSP'02). ACM Press, 55--67.
• 41: Vitányi, P. M. B. and Awerbuch, B. 1986. Atomic shared register access by asynchronous hardware. In 27th Annual Symposium on Foundations of Computer Science. IEEE, 233--243.
• 42: Weaver, D. L. and Germond, T., Eds. 2000. The SPARC Architecture Manual. Prentice Hall. Version 9.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

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

General Terms:
Algorithms, Performance, Theory

Keywords:
Atomic register, synchronization, wait-free