Source: http://www.google.com/patents/US8099726?ie=ISO-8859-1&dq=6,034,652
Timestamp: 2014-07-14 17:36:06
Document Index: 717600301

Matched Legal Cases: ['Application No. 06838476', 'Application No. 3405', 'Application No. 2008', 'Application No. 3405', 'Application No. 3405', 'Application No. 3405']

Patent US8099726 - Implementing strong atomicity in software transactional memory - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA 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...http://www.google.com/patents/US8099726?utm_source=gb-gplus-sharePatent US8099726 - Implementing strong atomicity in software transactional memoryAdvanced Patent SearchPublication numberUS8099726 B2Publication typeGrantApplication numberUS 11/389,334Publication dateJan 17, 2012Filing dateMar 23, 2006Priority dateDec 7, 2005Also published asCN101542437A, CN101542437B, US7555619, US7590806, US7747565, US7810085, US7861237, US8266609, US20070130238, US20070136290, US20070136365, US20070143276, US20070143360, US20070143741, US20070169031Publication number11389334, 389334, US 8099726 B2, US 8099726B2, US-B2-8099726, US8099726 B2, US8099726B2InventorsTimothy Lawrence HarrisOriginal AssigneeMicrosoft CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (55), Non-Patent Citations (27), Referenced by (11), Classifications (36), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetImplementing strong atomicity in software transactional memoryUS 8099726 B2Abstract 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.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5535352Mar 24, 1994Jul 9, 1996Hewlett-Packard CompanyComputing systemUS5949088Oct 25, 1996Sep 7, 1999Micron Technology, Inc.Intermediate SRAM array product and method of conditioning memory elements thereofUS6151607Apr 28, 1999Nov 21, 2000Microsoft CorporationDatabase computer system with application recovery and dependency handling write cacheUS6272607Aug 24, 1999Aug 7, 2001International Business Machines CorporationMethod and apparatus for transactional writing of data into a persistent memoryUS6289357Apr 24, 1998Sep 11, 2001Platinum Technology Ip, Inc.Method of automatically synchronizing mirrored database objectsUS6341285Jun 28, 1999Jan 22, 2002Lucent Technologies Inc.Serial protocol for transaction execution in main-memory database systemsUS6427154Aug 2, 2000Jul 30, 2002International Business Machines CorporationMethod of delaying space allocation for parallel copying garbage collectionUS6457023Dec 28, 2000Sep 24, 2002International Business Machines CorporationEstimation of object lifetime using static analysisUS6505291Oct 26, 2000Jan 7, 2003Brecis CommunicationsProcessor having a datapath and control logic constituted with basis execution blocksUS6553392Oct 14, 1999Apr 22, 2003Hewlett-Packard Development Company, L.P.System and method for purging database update image files after completion of associated transactionsUS6560773Oct 7, 1999May 6, 2003International Business Machines CorporationMethod and system for memory leak detection in an object-oriented environment during real-time trace processingUS6622300Apr 21, 1999Sep 16, 2003Hewlett-Packard Development Company, L.P.Dynamic optimization of computer programs using code-rewriting kernal moduleUS6658652Jun 8, 2000Dec 2, 2003International Business Machines CorporationMethod and system for shadow heap memory leak detection and other heap analysis in an object-oriented environment during real-time trace processingUS6662362Jul 6, 2000Dec 9, 2003International Business Machines CorporationMethod and system for improving performance of applications that employ a cross-language interfaceUS6694340May 28, 1999Feb 17, 2004International Business Machines CorporationTechnique for determining the age of the oldest reading transaction with a database objectUS6839726Dec 12, 2002Jan 4, 2005Matsushita Electric Industrial Co., Ltd.Apparatus, method, and program for implementing garbage collection suitable for real-time processingUS6898602Dec 10, 2002May 24, 2005Sun Microsystems Inc.Measuring the exact memory requirement of an application through intensive use of garbage collectorUS7010553Mar 19, 2002Mar 7, 2006Network Appliance, Inc.System and method for redirecting access to a remote mirrored snapshotUS7069279Nov 4, 2002Jun 27, 2006Savaje Technologies, Inc.Timely finalization of system resourcesUS7103597Oct 3, 2002Sep 5, 2006Mcgoveran David OAdaptive transaction manager for complex transactions and business processUS7117229May 31, 2002Oct 3, 2006Computer Associates Think, Inc.Method and system for online reorganization of databasesUS7206903 *Jul 20, 2004Apr 17, 2007Sun Microsystems, Inc.Method and apparatus for releasing memory locations during transactional executionUS7240171Jan 23, 2004Jul 3, 2007International Business Machines CorporationMethod and system for ensuring consistency of a groupUS7278137Dec 26, 2002Oct 2, 2007Arc InternationalMethods and apparatus for compiling instructions for a data processorUS7325108Mar 15, 2005Jan 29, 2008International Business Machines CorporationMethod and system for page-out and page-in of stale objects in memoryUS7395382 *Aug 10, 2004Jul 1, 2008Sun Microsystems, Inc.Hybrid software/hardware transactional memoryUS7555619Mar 23, 2006Jun 30, 2009Microsoft CorporationEfficient per-object operations in software transactional memoryUS7590806Mar 23, 2006Sep 15, 2009Microsoft CorporationFiltering of transactional memory operations using associative tablesUS7607123Sep 21, 2004Oct 20, 2009Hewlett-Packard Development Company, L.P.Systems and methods for validating debug information for optimized codeUS7703098 *Jul 20, 2004Apr 20, 2010Sun Microsystems, Inc.Technique to allow a first transaction to wait on condition that affects its working setUS20020107879Dec 29, 2000Aug 8, 2002Arnold Jeremy AlanAccurately determining an object's lifetimeUS20020138507Mar 7, 2002Sep 26, 2002International Business Machines CorporationMethod for reducing write barrier overheadUS20030069905Nov 18, 2002Apr 10, 2003Microsoft CorporationMethod and system for concurrent garbage collectionUS20030084038Nov 1, 2002May 1, 2003Verisign, Inc.Transactional memory managerUS20030120873Nov 27, 2002Jun 26, 2003Kanaley Michael JohnMethod and apparatus to maintain consistency between an object store and a plurality of caches utilizing transactional updates to data cachesUS20040015642 *Jul 16, 2003Jan 22, 2004Sun Microsystems, Inc.Software transactional memory for dynamically sizable shared data structuresUS20040107416 *Dec 2, 2002Jun 3, 2004Microsoft CorporationPatching of in-use functions on a running computer systemUS20040122876Dec 20, 2002Jun 24, 2004Hudson Richard L.Execution of modified cheney scanning in a multithreaded processing environmentUS20040187123 *Jan 23, 2004Sep 23, 2004Marc TremblaySelectively unmarking load-marked cache lines during transactional program executionUS20050097078Oct 31, 2003May 5, 2005Lohman Guy M.System, method, and computer program product for progressive query processingUS20050166167Jan 21, 2005Jul 28, 2005Nec Laboratories America, Inc.System and method for modeling, abstraction, and analysis of softwareUS20060004860 *May 24, 2004Jan 5, 2006Antti-Pekka LiedesMethod for checkpointing a main-memory databaseUS20060048119Aug 26, 2004Mar 2, 2006International Business Machines CorporationMethod and system for auto parallelization of zero-trip loops through induction variable substitutionUS20060173885Apr 15, 2005Aug 3, 2006Sun Microsystems, Inc.Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanismsUS20060282476Jun 10, 2005Dec 14, 2006International Business Machines CorporationSystem and method using atomic sets of memory locationsUS20070011668Jun 27, 2005Jan 11, 2007Wholey J SManaging parameters for graph-based computationsUS20070028056Jul 29, 2005Feb 1, 2007Microsoft CorporationDirect-update software transactional memoryUS20070130238Mar 23, 2006Jun 7, 2007Microsoft CorporationGarbage collector support for transactional memoryUS20070136290Mar 23, 2006Jun 14, 2007Microsoft CorporationRemoval of unnecessary read-to-update upgrades in software transactional memoryUS20070136365Mar 23, 2006Jun 14, 2007Microsoft CorporationReducing unnecessary software transactional memory operations on newly-allocated dataUS20070143287Dec 15, 2005Jun 21, 2007Ali-Reza Adl-TabatabaiCoordinating access to memory locations for hardware transactional memory transactions and software transactional memory transactionsUS20070157200Dec 30, 2005Jul 5, 2007Hopkins William ESystem and method for generating a lock-free dual queueUS20070169030Mar 23, 2006Jul 19, 2007Microsoft CorporationCompiler support for optimizing decomposed software transactional memory operationsWO2004075046A2Feb 6, 2004Sep 2, 2004Sun Microsystems IncSelectively unmarking of load-marked cache lines during t speculative thread executionWO2004075051A1Jan 30, 2004Sep 2, 2004Sun Microsystems IncMethod and apparatus for avoiding locks by speculatively executing critical sections* Cited by examinerNon-Patent CitationsReference1Adl-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.2Agesen et al., "An Efficient Meta-Lock for Implementing Ubiguitous Synchronization", 30 pages, (Apr. 1999).3Agrawal 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.4Agrawal 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.5Ananian et al., "Efficient Object-Based Software Transactions," Proceedings of the 2005 ACM OOPSLA Workshop on Synchronization and Concurrency in Object-Oriented Langues, SCOOL '05, Oct. 16, 2005, pp. 65-74.6Andrade et al., "Efficient Execution of Multi-Query Data Analysis Batches Using Compiler Optimization Strategies," Lecture Notes in Computer Science, 15 pages (2004).7Bacon et al., "Thin locks: featherweight synchronization for Java", pp. 258-268, (Jun. 1998).8Diniz & Rinard, "Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs", 29 pages, (Aug. 1996).9European Search Report (Supplementary), EPC Patent Application No. 06838476.7, Mar. 11, 2011, 14 pages.10Finkelstein, "Common Expression Analysis in Database Application," Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, pp. 235-245 (1982).11First Office Action, corresponding Chile Patent Application No. 3405-2006, 5 pages.12 *Fraser, Keir. Practical lock-freedom. [online] (Feb. 2004). University of Cambridge, pp. 1-116. Retrieved From the Internet .13 *Fraser, Keir. Practical lock-freedom. [online] (Feb. 2004). University of Cambridge, pp. 1-116. Retrieved From the Internet <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.5042&rep=rep1&type=pdf>.14Hammond et al., "Programming with Transactional Coherence and Consistency," ASPLOS Proceedings, International Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 9, 2004, pp. 1-13.15Harris & Fraser, "Language Support for Lightweight Transactions", 15 pages, (Oct. 2003).16Harris et al., "Composable Memory Transactions", 13 pages, (Jun. 2005).17Harris et al., "Optimizing Memory Transactions," PLDI '06, Ottawa, Ontario, Canada, Jun. 11-14, 2006, 12 pages.18Hindman & Grossman, "Strong Atomicity for Java Without Virtual-Machine Support", 18 pages, (printed Mar. 21, 2006).19International Search Report and Written Opinion for PCT/US06/45526, dated Mar. 26, 2008, 12 pages.20Lev & Maessen, "Towards a Safer Interaction with Transactional Memory by Tracking Object Visibility", 8 pages, (Oct. 2005).21Notice of Rejection, Japan Patent Application No. 2008-544369, 17 pages, May 6, 2011 (English translation).22Partial English translation of First Office Action, corresponding Chile Patent Application No. 3405-2006, 1 page.23Partial English translation of Second Office Action, corresponding Chile Patent Application No. 3405-2006, 6 pages.24Ringenburg & Grossman, "AtomCaml: First-Class Atomicity via Rollback", 13 pages, (Sep. 2005).25Second Office Action, corresponding Chile Patent Application No. 3405-2006, 8 pages.26Shinnar et al, Microsoft Research Technical Report "Integrating Support for Undo with Exception Handling", 13 pages, (Dec. 2004).27U.S. Appl. No. 11/192,784, filed Jul. 29, 2005, Harris.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8239843 *Mar 11, 2008Aug 7, 2012Oracle America, Inc.Value predictable variable scoping for speculative automatic parallelization with transactional memoryUS8266609 *Mar 23, 2006Sep 11, 2012Microsoft CorporationEfficient placement of software transactional memory operations around procedure callsUS8359586 *Aug 20, 2007Jan 22, 2013The Mathworks, Inc.Code generationUS8533699 *Mar 31, 2011Sep 10, 2013Oracle International CorporationSystem and method for optimizing a code section by forcing a code section to be executed atomicallyUS8719807 *Dec 28, 2006May 6, 2014Intel CorporationHandling precompiled binaries in a hardware accelerated software transactional memory systemUS20070169031 *Mar 23, 2006Jul 19, 2007Microsoft CorporationEfficient placement of software transactional memory operations around procedure callsUS20080162886 *Dec 28, 2006Jul 3, 2008Bratin SahaHandling precompiled binaries in a hardware accelerated software transactional memory systemUS20090235237 *Mar 11, 2008Sep 17, 2009Sun Microsystems, Inc.Value predictable variable scoping for speculative automatic parallelization with transactional memoryUS20090328019 *Jun 27, 2008Dec 31, 2009Microsoft CorporationDetecting race conditions with a software transactional memory systemUS20120017203 *Jul 14, 2010Jan 19, 2012International Business Machines CorporationPath-Sensitive Analysis for Reducing Rollback OverheadsUS20120254846 *Mar 31, 2011Oct 4, 2012Moir Mark SSystem and Method for Optimizing a Code Section by Forcing a Code Section to be Executed Atomically* Cited by examinerClassifications U.S. Classification717/159, 717/153, 717/160, 717/151, 717/161, 717/154, 717/152, 717/158, 717/156, 717/157, 717/155International ClassificationG06F9/45Cooperative ClassificationG06F12/0802, G06F9/30181, G06F9/466, G06F9/45525, G06F8/4435, G06F9/3004, G06F8/443, G06F9/3802, G06F12/0253, G06F9/467, G06F9/30047, G06F8/4441European ClassificationG06F9/46T, G06F8/443, G06F12/08B, G06F12/02D2G, G06F9/46T2, G06F9/30A2, G06F9/30A2P, G06F9/30X, G06F9/38B, G06F8/4441, G06F8/4435, G06F9/455B4CLegal EventsDateCodeEventDescriptionMay 3, 2006ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HARRIS, TIMOTHY LAWRENCE;REEL/FRAME:017570/0653Effective date: 20060322RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google