Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2008-07-08
2008-07-08
Kim, Hong (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S150000, C711S151000, C711S152000, C711S163000, C712S208000
Reexamination Certificate
active
11195093
ABSTRACT:
One embodiment of the present invention provides a system that avoids locks by transactionally executing critical sections. During operation, the system receives a program which includes one or more critical sections which are protected by locks. Next, the system modifies the program so that the critical sections which are protected by locks are executed transactionally without acquiring locks associated with the critical sections. More specifically, the program is modified so that: (1) during transactional execution of a critical section, the program first determines if a lock associated with the critical section is held by another process and if so aborts the transactional execution; (2) if the transactional execution of the critical section completes without encountering an interfering data access from another process, the program commits changes made during the transactional execution and optionally resumes normal non-transactional execution of the program past the critical section; and (3) if an interfering data access from another process is encountered during transactional execution of the critical section, the program discards changes made during the transactional execution, and attempts to re-execute the critical section zero or more times.
REFERENCES:
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5701432 (1997-12-01), Wong et al.
patent: 5742785 (1998-04-01), Stone et al.
patent: 5835764 (1998-11-01), Platt et al.
patent: 5940827 (1999-08-01), Hapner et al.
patent: 5974438 (1999-10-01), Neufeld
patent: 6021480 (2000-02-01), Pettey
patent: 6185577 (2001-02-01), Nainani et al.
patent: 6360220 (2002-03-01), Forin
patent: 6460124 (2002-10-01), Kagi et al.
patent: 6578033 (2003-06-01), Singhal et al.
patent: 6681311 (2004-01-01), Gaskins et al.
patent: 6918012 (2005-07-01), Venkitakrishnan et al.
patent: 6941449 (2005-09-01), Ross
patent: 2002/0087810 (2002-07-01), Boatright et al.
patent: 2002/0178349 (2002-11-01), Shibayama et al.
patent: 2003/0079094 (2003-04-01), Rajwar et al.
patent: 2004/0162948 (2004-08-01), Tremblay et al.
patent: 2004/0186970 (2004-09-01), Kekre et al.
patent: WO 01 93028 (2001-12-01), None
patent: WO 03/054693 (2003-07-01), None
“The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization”, by J. Gregory Steffan et al., 1998, IEEE, pp. 2-13.
Publication entitled “Speculation-Based Techniques for Transactional Lock-Free Execution of Lock-Based Programs”, by Ravi Rajwar, Online! 2002, XP002286237, Retrieved from the internet: URL:http://bbcr.uwaterloo.ca/{brecht/courses/856/readings-new/rajwar02speculationsbased.pdf.
Publication entitled “Checkpoint Processing and Recovery: Towards Scalable Large Instruction Window Processors”, by Haitham Akkary et al., Proceedings of th e 36thInternational Symporuim on Microarchitecture, 2003, IEEE.
Publication entitled “Multiple Reservations and the Oklahoma Update”, by Janice M. Stone et al., IEEE Parallel & Distributed Technology, Nov. 1993, pp. 58-71.
Publication entitled “Improving the Throughput of Synchronization by Insertion of Delays”, by Ravi Rajwar et al. Proceedings of the Sixth International Symposuim on High-Performance Computer Architecture, Jan. 8-12, 2000, pp. 168-179.
Publication entitled “Checkpoint Processing and Recovery: An Efficient, Scalable Alternative to Reorder Buffers” Haitham Akkary et al. IEEE Computer Society, Nov.-Dec. 2003, pp. 11-19.
Publication entitled “Multi-view Memory to Support OS Locking For Transaction Systems”, P. Bodorik et al., IEEE, 1997, pp. 309-318.
Publication entitled “Indexing for Multiversion Locking: Alternatives and Performance Evaluation”, Paul M. Bober et al, IEEE Transactions on Knowledge and Data Engineering, vol. 9, No. 1, Jan.-Feb. 1997, pp. 68-84.
Publication entitled: “Transactional Execution: Toward Reliable, High-Performance Multithreading” by Ravi Rajwar et al. IEEE Computer Society, Nov.-Dec. 2003, pp. 117-125.
Publication: “Speculative Lock Elision: Enabling Highly Concurrent Multithread Execution” by Ravi Rajwar and James R. Goodman, Computer Sciences Department, University of Wisconsin-Madison, Madison, WI 53706 USA, rajwar@cs.wisc.edu, XP-001075852, published in IEEE Journal Jan. 12, 2001, pp. 294-305.
“Structured Computer Organization” by Andrew S. Tanenbaum, Published 1999, pp. 5, 7-8.
“The Transaction Concept: Virtues and Limitations” by Jim Gray. Pro. Int'l Conf. Very Large Databases, Morgan Kaufman, 1981. pp. 144-154.
“Toward Efficient and Robust Software Speculative Parallelization on Multiprocessors” by Marcelo Cintra and Diego R. Lianos, PPoPP' 03 Jun. 11-13, 2003 ACM 1-58113-588-2/03/0006 pp. 13-24.
“Microsoft Computer Dictionary” Fifth Edition, pub 2002, p. 378.
Publication: “Specuculative Synchronization: Applying Thread-Level Speculation to Explicitly Parallel Applications” by Jose F. Martinez and Josep Torrellas, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA, http://iacoma.cs.uiuc.edu, XP-002285169, published in ASPLOS X, Oct. 2002, pp. 18-29.
Publication: “Transactional Memory: Architectural Support for Lock-Free Data Structures” by Maurice Herlihy, Digital Equip. Corp. Cambridge Research Laboratory, Cambridge, MA 02139, herlihy@crl.dcc.com and J. Eliot B. Moss, Dept. of Computer Science, University of Massachusetts, Amherst, MA 01003, moss@cs.umass.edu, XP-000380375, published in Computer Architecture News, May 21, 1993, pp. 289-300.
Publication: “Enhancing Software Reliability with Speculative Threads” by Jeffrey Oplinger and Monica S. Lam, Computer Systems, Laboratory, Stanford University, jeffop@stanford.edu, XP-002285168 published in SPLOS X, 10-2202, pp. 184-196.
“Lock-Based Programs and Transactional Lock-Free Execution”, by Ravi Rajwar et al., University of Wisconsin-Madison Technical Report #1440, Apr. 2002.
“Speculative Locks for Concurrent Execution of Critical Sections in Shared-Memory Multiprocessors”, by Jose F Martinez et al., Workshop on Memory Performance Issues, International Symposium on Computer Architecture, Jun. 2001.
“Transactional Memory: Architectural Support for Lock-Free Data Structures”, by Maurice Herlihy, 1993.
“Speculative Locks for Concurrent Execution of Critical Sections in Shared-Memory Multiprocessors”, by Jose F. Martinez et al., Technical Report UIUCDCS-R-2001-2202, Feb. 2001.
“Transactional Lock-Free Execution of Lock-Based Programs”, by Ravi Rajwar, Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 6-Oct. 9, 2002, San Jose, CA.
Chaudhry Shailender
Moir Mark S.
Tremblay Marc
Ayash Marwan
Kim Hong
Park, Vaughn & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Avoiding locks by transactionally executing critical sections does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Avoiding locks by transactionally executing critical sections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding locks by transactionally executing critical sections will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3949923