Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2006-06-27
2010-02-23
Kim, Matt (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
Reexamination Certificate
active
07669015
ABSTRACT:
The present disclosure describes a unique way for each of multiple processes to operate in parallel using (e.g., reading, modifying, and writing to) the same shared data without causing corruption to the shared data. For example, each of multiple processes utilizes current and past data values associated with a global counter or clock for purposes of determining whether any shared variables used to produce a respective transaction outcome were modified (by another process) when executing a respective transaction. If a respective process detects that shared data used by respective process was modified during a transaction, the process can abort and retry the transaction rather than cause data corruption by storing locally maintained results associated with the transaction to a globally shared data space.
REFERENCES:
patent: 5301290 (1994-04-01), Tetzlaff et al.
patent: 5596754 (1997-01-01), Lomet
patent: 5956731 (1999-09-01), Bamford et al.
patent: 5987506 (1999-11-01), Carter et al.
patent: 6148377 (2000-11-01), Carter et al.
patent: 6826570 (2004-11-01), Eshel et al.
patent: 7395263 (2008-07-01), McKenney
patent: 2004/0117531 (2004-06-01), McKenney
patent: 2005/0038961 (2005-02-01), Chen
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.
Office Action issued in U.S. Appl. No. 11/475,262, dated Dec. 9, 2008.
Response to Office Action filed in U.S. Appl. No. 11/475,262, dated Apr. 7, 2009.
Office Action issued in U.S. Appl. No. 11/475,262, dated Jul. 8, 2009.
Chris Purcell et al., Brief Announcement; Implementing Multi-Word Atomic Snapshots on Current Hardware, Jul. 25-28, 2004, p. 1, PODC '04.
Dice David
Shalev Ori
Shavit Nir N.
Brooks & Kushman P.C.
Dare Ryan
Kim Matt
Sun Microsystems Inc.
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-4224082