Reducing unnecessary software transactional memory...

Details Reducing unnecessary software transactional memory... Reducing unnecessary software transactional memory...

2006-03-23

2010-12-28

Chavis, John (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

Reexamination Certificate

active

07861237

ABSTRACT:
A software transactional memory system is described which utilizes decomposed software transactional memory instructions as well as runtime optimizations to achieve efficient performance. The decomposed instructions allow a compiler with knowledge of the instruction semantics to perform optimizations which would be unavailable on traditional software transactional memory systems. Additionally, high-level software transactional memory optimizations are performed such as code movement around procedure calls, addition of operations to provide strong atomicity, removal of unnecessary read-to-update upgrades, and removal of operations for newly-allocated objects. During execution, multi-use header words for objects are extended to provide for per-object housekeeping, as well as fast snapshots which illustrate changes to objects. Additionally, entries to software transactional memory logs are filtered using an associative table during execution, preventing needless writes to the logs. Finally a garbage collector with knowledge of the software transactional memory system compacts software transactional memory logs during garbage collection.

REFERENCES:
patent: 5535352 (1996-07-01), Bridges et al.
patent: 5949088 (1999-09-01), Morgan
patent: 6151607 (2000-11-01), Lomet
patent: 6272607 (2001-08-01), Baentsch et al.
patent: 6289357 (2001-09-01), Parker
patent: 6341285 (2002-01-01), Blott et al.
patent: 6427154 (2002-07-01), Kolodner et al.
patent: 6457023 (2002-09-01), Pinter et al.
patent: 6505291 (2003-01-01), Sollars
patent: 6553392 (2003-04-01), Mosher et al.
patent: 6560773 (2003-05-01), Alexander et al.
patent: 6622300 (2003-09-01), Krishnaswamy et al.
patent: 6658652 (2003-12-01), Alexander et al.
patent: 6662362 (2003-12-01), Arora et al.
patent: 6694340 (2004-02-01), Lyle et al.
patent: 6839726 (2005-01-01), Kawamoto
patent: 6898602 (2005-05-01), Sayag
patent: 7010553 (2006-03-01), Chen et al.
patent: 7069279 (2006-06-01), Rau et al.
patent: 7103597 (2006-09-01), McGoveran
patent: 7117229 (2006-10-01), Marshall et al.
patent: 7240171 (2007-07-01), Barton et al.
patent: 7278137 (2007-10-01), Fuhler et al.
patent: 7325108 (2008-01-01), Tuel
patent: 7555619 (2009-06-01), Harris
patent: 7590806 (2009-09-01), Harris et al.
patent: 7607123 (2009-10-01), Chavan
patent: 2002/0107879 (2002-08-01), Arnold et al.
patent: 2002/0138507 (2002-09-01), Shuf et al.
patent: 2003/0069905 (2003-04-01), Dussud
patent: 2003/0084038 (2003-05-01), Balogh et al.
patent: 2003/0120873 (2003-06-01), Kanaley
patent: 2004/0107416 (2004-06-01), Buban et al.
patent: 2004/0122876 (2004-06-01), Hudson et al.
patent: 2004/0187123 (2004-09-01), Tremblay et al.
patent: 2005/0097078 (2005-05-01), Lohman et al.
patent: 2006/0004860 (2006-01-01), Liedes et al.
patent: 2006/0048119 (2006-03-01), Ren et al.
patent: 2006/0173885 (2006-08-01), Moir et al.
patent: 2006/0282476 (2006-12-01), Dolby et al.
patent: 2007/0028056 (2007-02-01), Harris
patent: 2007/0130238 (2007-06-01), Harris
patent: 2007/0136290 (2007-06-01), Shinnar et al.
patent: 2007/0143287 (2007-06-01), Adl-tabatabai et al.
patent: 2007/0157200 (2007-07-01), Hopkins
patent: 2007/0169030 (2007-07-01), Tarditi et al.
U.S. Appl. No. 11/192,784, filed Jul. 29, 2005, Harris.
Agesen et al., “An Efficient Meta-Lock for Implementing Ubiguitous Synchronization”, 30 pages, (Apr. 1999).
Bacon et al., “Thin locks: featherweight synchronization for Java”, pp. 258-268, (Jun. 1998).
Diniz & Rinard, “Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs”, 29 pages, (Aug. 1996).
Harris et al., “Composable Memory Transactions”, 13 pages, (Jun. 2005).
Harris & Fraser, “Language Support for Lightweight Transactions”, 15 pages, (Oct. 2003).
Hindman & Grossman, “Strong Atomicity for Java Without Virtual-Machine Support”, 18 pages, (printed Mar. 21, 2006).
Lev & Maessen, “Towards a Safer Interaction with Transactional Memory by Tracking Object Visibility”, 8 pages, (Oct. 2005).
Ringenburg & Grossman, “AtomCaml: First-Class Atomicity via Rollback”, 13 pages, (Sep. 2005).
Shinnar et al, Microsoft Research Technical Report “Integrating Support for Undo with Exception Handling”, 13 pages, (Dec. 2004).
Andrade et al., “Efficient Execution of Multi-Query Data Analysis Batches Using Compiler Optimization Strategies,” Lecture Notes in Computer Science, 15 pages (2004).
Finkelstein, “Common Expression Analysis in Database Application,” Proceedings of the 1982 ACM SIGMOND International Conference on Management of Data, pp. 235-245 (1982).
International Search Report and Written Opinion for PCT/US06/45526, dated Mar. 26, 2008, 12 pages.
Agrawal et al., “An Interprocedural Framework for Placement of Asynchronour I/O Operations,” UMDTechnical Report CS-TR-3563 (1998), http://www.lib.umd.edu/drum/bitstream/1903/778/2/CS-TR-3563.pdf, retreived on Feb. 24, 2010, pp. 1-25.
Agrawal et al., An Interprocedural Partial Redundancy Elilmination and its Application to Distributed Memory Compilation, Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, 1995, pp. 258-269.
Adl-Tabatabai et al., “Compiler and Runtime Support for Efficient Software Transactional Memory,” Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006, pp. 26-36.
First Office Action, corresponding Chile Patent Application No. 3405-2006, received Dec. 22, 2008, 5 pages.
Partial English translation of First Office Action, corresponding Chile Patent Application No. 3405-2006, received Dec. 22, 2008, 1 page.
Second Office Action, corresponding Chile Patent Application No. 3405-2006, received Nov. 19, 2009, 8 pages.
Partial English translation of Second Office Action, corresponding Chile Patent Application No. 3405-2006, received Nov. 19, 2009, 6 pages.
Harris et al., “Optimizing Memory Transactions,” PLDI '06, Ottawa, Ontario, Canada, Jun. 11-14, 2006, 12 pages.

Affiliated with

Also associated with

Rating

Reducing unnecessary software 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 Reducing unnecessary software transactional memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing unnecessary software transactional memory... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4158566