Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2004-07-20
2011-12-06
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
Reexamination Certificate
active
08074030
ABSTRACT:
By exploiting an early release facility that may be provided by certain transactional memory designs, we facilitate transaction software constructs that operate on dynamically-sized data structures and/or other data structures for which traversal may be data dependent. Absent exploitation of such a facility, the act of traversing the data structure would typically introduce corresponding locations into the read set of a transaction, and a subsequent modification of any of the previously traversed locations would result in abortion of the traversing transaction. By exploiting an early release facility such as described herein, a transaction may release the locations that it has previously read in traversal and thereby eliminate such read locations as a source of conflict with other concurrently executing computations or transactions. In this way, concurrency may be enhanced while still employing a conceptually simple and convenient coordination facility.
REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5222217 (1993-06-01), Blount et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5241675 (1993-08-01), Sheth et al.
patent: 5319778 (1994-06-01), Catino
patent: 5369757 (1994-11-01), Spiro et al.
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5657474 (1997-08-01), Paul Dubois Taine et al.
patent: 5701432 (1997-12-01), Wong et al.
patent: 5742785 (1998-04-01), Stone et al.
patent: 5937199 (1999-08-01), Temple
patent: 5974438 (1999-10-01), Neufeld
patent: 6021480 (2000-02-01), Pettey
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6128713 (2000-10-01), Eisler et al.
patent: 6144965 (2000-11-01), Oliver
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6263360 (2001-07-01), Arnold et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6425048 (2002-07-01), Kaganoi
patent: 6460124 (2002-10-01), Kagi et al.
patent: 6493741 (2002-12-01), Emer et al.
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6675192 (2004-01-01), Emer et al.
patent: 6697927 (2004-02-01), Bonola
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 6862664 (2005-03-01), Tremblay et al.
patent: 6918012 (2005-07-01), Venkitakrishnan et al.
patent: 7076629 (2006-07-01), Bonola
patent: 7089374 (2006-08-01), Tremblay et al.
patent: 7206903 (2007-04-01), Moir et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2002/0069326 (2002-06-01), Richardson et al.
patent: 2002/0087810 (2002-07-01), Boatright et al.
patent: 2003/0066056 (2003-04-01), Petersen et al.
patent: 2003/0079094 (2003-04-01), Rajwar et al.
patent: 2003/0126186 (2003-07-01), Rodgers et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2003/0182465 (2003-09-01), Moir et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 2004/0162948 (2004-08-01), Tremblay et al.
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
patent: WO 01/53942 (2001-07-01), None
patent: WO 01/53943 (2001-07-01), None
patent: WO 01/80015 (2001-10-01), None
patent: WO 01/82057 (2001-11-01), None
patent: WO 03/060705 (2003-07-01), None
patent: WO 03/060715 (2003-07-01), None
Maurice Herlihy and J. Eliot B. Moss; “Transactional Memory: Architectural Support for Lock-Free Data Structures”; Computer Architecture, 1993. Proceedings of the 20th Annual International Symposium on IEEE; 1993; pp. 289-300.
Lance Hammond, Vicky Wong, Mike Chen, Brian D. Carlstrom, John D. Davis, Ben Hertzberg, Manohar K. Prabhu, Honggo Wijaya, Christos Kozyrakis, and Kunle Olukotun; “Transactional Memory Coherence and Consistency”; Computer Architecture, 2004. Proceedings. 31st Annual International Symposium on; Jun. 2004; ; pp. 102-113.
Maurice Herlihy, Mark Moir, Victor Luchangco, William N. Scherer III; “Software Transactional Memory for Dynamic-Sized Data Structures”; Sun Microsystems, Inc.; Jul. 13-16, 2003; pp. 4-5.
Nir Shavit, Dan Touitou; “Software transactional memory”; Annual ACM Symposium on Principles of Distributed Computing, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing; 1995; ACM Press; pp. 99-116.
Michael Barry Greenwald; “Non-Blocking Synchronization and System Design”; Aug. 1999, pp. 1 , 5 , 30 , 42 , 43 , 31.
Keir Fraser; “Technical Report”; Feb. 2004; University of Cambridge Computer Laboratory; No. 579; p. 34-50.
Tim Harris and Keir Fraser; “Language support for lightweight transactions”; Conference on Object Oriented Programming Systems Languages and Applications, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages; 2003; pp. 388-402; ACM Press.
Herlihy, M.P., et al., “Linearizability: A Correctness Condition for Con-Current Objects,”ACM Transactions on Programming Languages and Systems, 12(3):463-492, Jul. 1990.
Herlihy, M.P., “Wait-Free Synchronization,”ACM Transactions on Programming Languages and Systems, 11(1):124-149, Jan. 1991.
Massalin, H., et al., “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991, 21 pages.
Massalin, Henry, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 158 pages, 1992 [retrieved from the Internet on Jul. 13, 2007: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Bershad, B. N., “Practical Considerations for Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273. IEEE Computer Society Press. Washington, D.C., 1993.
Herlihy, M., “A Methodology for Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, Hagit, et al., “Are Wait-Free Algorithms Fast?”Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, A., “A performance evaluation of lock-free synchronization protocols,”Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, New York, NY, 1994.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., et al., “The Synergy Between Non-Blocking Synchronization and Operating System Structure,”Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Arora, N. S., et al., “Thread Scheduling for Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, ACM Press, New York, NY, 1998.
Attiya, Hagit, et al., “Atomic Snapshots in O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report ST
Herlihy Maurice
Moir Mark S.
Bataille Pierre-Michel
Birkhimer Christopher
Kowert Robert C.
Meyers, Hood, Kivlin, Kowert & Goetzel, P.C.
Oracle America Inc.
LandOfFree
Using transactional memory with early release to implement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using transactional memory with early release to implement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using transactional memory with early release to implement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4264989