Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2008-07-01
2008-07-01
Sough, Hyung S. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S150000, C711S163000
Reexamination Certificate
active
07395382
ABSTRACT:
A transactional memory implementation has been developed that is capable of coordinating concurrent hardware transactional memory (HTM) and software transactional memory (STM) transactions over a unified transactional memory space. Some implementations employ hardware transactional memory, if available or suitable, to improve performance. Some exploitations include a hardware transactional memory in which, or for which, hardware-mediated transactions are augmented to include within their transactional scope (or mechanism) one or more additional transactional locations that facilitate coordination with concurrently executing software-mediated transactions (if any).
REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Oliver
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6460124 (2002-10-01), Kagi et al.
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2003/0079094 (2003-04-01), Rajwar 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/0068597 (2004-04-01), Kulick et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 2004/0237073 (2004-11-01), Wu 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
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, 2001: 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 STAN-CS-TR-99-1624, Palo Alto, CA, Aug. 1999, 241 pages.
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,”SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 137 146, ACM Press, New York, NY, ISBN: 1-58113-185-2, 2000.
Detlefs, David L., et al., “Even Better DCAS-Based Concurrent Deques,”Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, Germany, ISBN: 3-540-41143-7, 2000.
Herlihy, Maurice, et al., “Software Transactional Memory for Dynamic-Sized Data Structures,” Sun Microsystems, Inc. PODC '03, Jul. 13-16, 2003, Boston Massachusetts, pp. 92-101.
Dice, Dave and Garthwaite, Alex, “Mostly Lock-Free Malloc,” in ACM SIGPLAN International Symposium on Memory Management, ACM Press, 2002, pp. 163-174.
Doherty, et al., “Bringing Practical Lock-Free Synchronization to 64-Bit Applications,” POCD '04, Jul. 25-28, 2004, St. John's. Newfoundland, Canada, 9 pages.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD Thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alco, CA, Aug. 1999, 241 pages.
Harris, T. and Fraser, K., “Language Support for Lightweight Transactions” in Proceedings of the 16thAnnual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (2003), 15 pages.
Harris, Timothy L., et al., “A Practical Multi-Word Compare-and-Swap Operation,” in Proceedings of the 16thInternational Symposium on Distributed Computing, 2002, 15 pages.
Hendler, et al., “A Scalable Lock-free Stack Algorithm,” SPAA '04, Jun. 27-30, Barcelona, Spain, pp. 206-215.
Herlihy, M. and Moss, J., “Transactional Memory: Architectural Support for Lock-Free Data Structures,” in Proceedings of the 20thInternational Symposium in Computer Architecture, (1993) pp. 289-300.
Herlihy, M., et al., “Obstruction-Free Snychronization: Double-Ended Queues as an Example,” in Proceedings of the 23rdInternational Conference on Distributed Computing Systems, 2003, 8 pages.
Lev, Yossi and Moir, Mark, “Fast read sharing mechanism for software transactional memory,” 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004) poster presentation, Jul. 2004, 6 pages.
Michael, M. and Scott, M., “Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors,” Journal of Parallel and Distributed Computing, 51(1):1-26, 1998.
Moir, et al., “A Scalable and Lock-Free FIFO Queue Algorithm,” Aug. 9, 2004, 10 pages.
Moir, M., “Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions,” in Proceedings of the 19thannual ACM Symposium on the Principles of Di
Doan Duc T.
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sough Hyung S.
Sun Microsystems Inc.
LandOfFree
Hybrid software/hardware transactional memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid software/hardware transactional memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid software/hardware transactional memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2755058