Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2006-06-27
2011-11-22
Patel, Hetul (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711SE12032
Reexamination Certificate
active
08065499
ABSTRACT:
A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including different types of metadata enabling the processing threads to carry out simultaneous execution depending on a currently selected type of lock mode. A mode controller monitoring the processing threads initiates switching from one type of lock mode to another depending on current operating conditions such as an amount of contention amongst the multiple processing threads to modify the shared data. The mode controller can switch from one lock mode another regardless of whether any of the multiple processes are in the midst of executing a respective transaction. A most efficient lock mode can be selected to carry out the parallel transactions. In certain cases, switching of lock modes causes one or more of the processing threads to abort and retry a respective transaction according to the new mode.
REFERENCES:
patent: 5301290 (1994-04-01), Tetzlaff et al.
patent: 5596754 (1997-01-01), Lomet
patent: 5649200 (1997-07-01), Leblang et al.
patent: 5950199 (1999-09-01), Schmuck et al.
patent: 5956731 (1999-09-01), Bamford et al.
patent: 5987506 (1999-11-01), Carter et al.
patent: 6101590 (2000-08-01), Hansen
patent: 6148377 (2000-11-01), Carter et al.
patent: 6393437 (2002-05-01), Zinda et al.
patent: 6757893 (2004-06-01), Haikin
patent: 6810470 (2004-10-01), Wiseman et al.
patent: 6826570 (2004-11-01), Eshel et al.
patent: 7313794 (2007-12-01), Ansari
patent: 7395263 (2008-07-01), McKenney
patent: 7467378 (2008-12-01), Sobel
patent: 7536517 (2009-05-01), Harris
patent: 2004/0117531 (2004-06-01), McKenney
patent: 2005/0038961 (2005-02-01), Chen
patent: 2006/0106996 (2006-05-01), Ahmad et al.
patent: 2006/0161919 (2006-07-01), Onufryk et al.
patent: 2006/0236039 (2006-10-01), Golander
patent: 2007/0124546 (2007-05-01), Blanchard et al.
Herlihy, M., Moss, E., “Transactional Memory: Architectural Support for Lock-Free Data Structures”, Proceedings of the Twentieth Annual International Symposium on Computer Architecture, 1993, pp. 1-12.
Rajwar, R., Herlihy, M., Lai, K., “Virtualizing Transactional Memory”, ISCA '05: Proceedings of the 32nd Annual International Symposium on Computer Architecture, Washington, DC, IEEE Computer Society, 2005, pp. 494-505.
Ananian, C.S., Asanovic, K., Kuszmaul, B.C., Leiserson, C.E., Lie, S., “Unbounded Transactional Memory”, HPCA '05: Proceedings of the 11th International Symposium on High-Performance Computer Architecture, Washington, DC, IEEE Computer Society, 2005, pp. 316-327.
Hammond, L., Wong, V., Chen, M., Carlstrom, B.D., Davis, J.D., Hertzberg, B., Prabhu, M.K., Wijaya, H., Kozyrakis, C., Olukotun, K., “Transactional Memory Coherence and Consistency”, ISCA '04: Proceedings of the 31st Annual International Symposium on Computer Architecture, Washington, DC, IEEE Computer Society, 2004.
Ennals, R., “Software Transactional Memory Should Not Be Obstruction-Free”, www.cambridge,intel-research.net/rennals
otlockfree.pdf, 2005, pp. 1-10.
Fraser, K., Harris, T., “Concurrent Programming Without Locks”, www.cl.cam.ac.uk/Research/SRG
etos/papers/2004-cpwl-submission.pdf, 2004, pp. 1-48.
Herlihy, M., “SXM: C# Software Transactional Memory”, http://www.cs.brown.edu/˜mph/SXM/README.doc, 2005.
Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N., “Software Transactional Memory for Dynamic-Sized Data Structure”, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, 2003.
Marathe, V.J., Scherer III, W.N., Scott, M.L., “Design Tradeoffs in Modern Software Transactional Memory Systems”, LCR '04: Proceedings of the 7th Workshop on Workshop on Languages, Compilers, and Run-Time Support for Scalable Systems, New York, NY, ACM Press, 2004.
Marathe, V.J., Scherer III, W.N., Scott, M.L., “Adaptive Software Transactional Memory”, Proceedings of the 19th International Symposium on Distributed Computing, Cracow, Poland, 2005, pp. 354-368.
Moir, M., “Hybrid Transactional Memory”, Technical Report Archivist 2004-0661, Sun Microsystems Research, 2004, pp. 1-15.
Saha, B., Adl-Tabatabai, A.R., Hudson, R.L., Minh, C.C., Hertzberg, B., “McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime”, PPoPP '06, Mar. 29-31, 2006, New York, NY, pp. 187-192.
Shalev, O., Shavit, N., “Predictive Log-Synchronization”, EuroSys 2006, Apr. 18-21, 2006, Leuven, Belgium, pp. 305-315.
Shavit, N., Touitou, D., “Software transactional memory”, Distributed Computing 10(2), 1997, p. 99-116.
Welc, A., Jagannathan, S., Hosking, A.L., “Transactional Monitors for Concurrent Objects”, Proceedings of the European Conference on Object-Oriented Programming, vol. 3086 of Lecture Notes in Computer Science, Springer-Verlag, 2004, pp. 519-542.
Ananian, C.S., Rinard, M., “Efficient Object-Based Software Transactions”, Proceedings of Synchronization and Concurrency in Object-Oriented Languages (SCOOL), ACM, 2005.
Kumar, S., Chu, M., Hughes, C.J., Kundu, P., Nguyen, A., “Hybrid Transactional Memory”, PPoPP 2006, Mar. 29-31, 2006, New York, NY, pp. 209-220.
Harris, T., Fraser, K., “Language Support for Lightweight Transactions”, SIGPLAN Not. 38(11), 2003, pp. 388-402.
Dice, D., Shavit, N., “What Really Makes Transactions Faster?”, TRANSACT06 ACM Workshop, 2006.
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N., “Atomic Snapshots of Shared Memory”, J. ACM 40(4), 1993, pp. 873-890.
Agesen, O., Detlefs, D., Garthwaite, A., Knippel, R., Ramakrishna, Y.S., White, D., “An Efficient Meta-lock for Implementing Ubiquitous Synchronization”, ACM SIGPLAN Notices 34(10), 1999, pp. 207-222.
Dice, D., “Implementing Fast Java Monitors with Relaxed-Locks”, Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM '01), Monterey, California, Apr. 23-24, 2001, pp. 79-90.
Bloom, B.H., “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM, vol. 13, No. 7, Jul. 1970, pp. 422-426.
Boehm, H.J., “Space Efficient Conservative Garbage Collection”, SIGPLAN Conference on Programming Language Design and Implementation, 1993, pp. 197-206.
Michael, M.M., “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, IEEE Trans. on Parallel and Distributed Systems, vol. 15, No. 6, 2004, pp. 491-504.
Herlihy, M., Luchangco, V., Moir, M., “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures”, Proceedings of the 16th International Symposium on Distributed Computing, vol. 2508, Springer-Verlag Heidelberg, 2002, pp. 339-353.
Hart, T.E., McKenney, P.E., Brown, A.D., “Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation”, IEEE, 2006.
Fraser, K., “Practical lock-freedom”, Technical Report, No. 579, University of Cambridge, Computer Laboratory, Feb. 2004, pp. 1-116.
Hanke, S., “The Performance of Concurrent Red-Black Tree Algorithms”, Lecture Notes in Computer Science 1668, 1999, pp. 286-300.
Rajwar, R., Hill, M., “Transactional Memory Online”, http://www.cs.wisc.edu/trans-memory, 2006.
Purcell, C., Harris, T, “Brief Announcement: Implementing Multi-Word Atomic Snapshots on Current Hardware”, PODC'04, Jul. 25-28, 2004, St. Johns, Newfoundland, Canada.
Non-Final Office Action dated Jan. 22, 2009 for U.S. Appl. No. 11/475,814, 10 pgs.
Reply to Non-Final Office Action dated Jan. 22, 2009 for U.S. Appl. No. 11/475,814, filed Apr. 20, 2009, 11 pgs.
Non-Final Office Action dated Feb. 22, 2010 for U.S. Appl. No. 11/699,802, 10 pgs.
Reply to Non-Final Office Action dated Feb. 22, 2010 for U.S. Appl. No. 11/699,802, filed May 21, 2010, 13 pgs.
Non-Final Office Acti
Dice David
Shavit Nir N.
Brooks & Kushman P.C.
Dare Ryan
Oracle America Inc.
Patel Hetul
LandOfFree
Methods and apparatus to implement parallel transactions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus to implement parallel transactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus to implement parallel transactions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4311377