Parallelizing sequential frameworks using transactions

Details Parallelizing sequential frameworks using transactions Parallelizing sequential frameworks using transactions

2011-08-30

2011-08-30

To, Baoquoc (Department: 2162)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C707S713000

Reexamination Certificate

active

08010550

ABSTRACT:
Various technologies and techniques are disclosed for transforming a sequential loop into a parallel loop for use with a transactional memory system. A transactional memory system is provided. A first section of code containing an original sequential loop is transformed into a second section of code containing a parallel loop that uses transactions to preserve an original input to output mapping. For example, the original sequential loop can be transformed into a parallel loop by taking each iteration of the original sequential loop and generating a separate transaction that follows a pre-determined commit order process. At least some of the separate transactions are executed in different threads. When an unhandled exception is detected that occurs in a particular transaction while the parallel loop is executing, state modifications made by the particular transaction and predecessor transactions are committed, and state modifications made by successor transactions are discarded.

REFERENCES:
patent: 4884228 (1989-11-01), Stanley
patent: 5241675 (1993-08-01), Sheth et al.
patent: 5335343 (1994-08-01), Lampson et al.
patent: 5701480 (1997-12-01), Raz
patent: 6011921 (2000-01-01), Takahashi
patent: 6014741 (2000-01-01), Mahalingaiah
patent: 6016399 (2000-01-01), Chang
patent: 6088705 (2000-07-01), Lightstone
patent: 6507947 (2003-01-01), Schreiber et al.
patent: 6557048 (2003-04-01), Keller
patent: 6574725 (2003-06-01), Kranich
patent: 6615403 (2003-09-01), Muthukumar
patent: 6704861 (2004-03-01), McKeen
patent: 6754737 (2004-06-01), Heynemann et al.
patent: 6785779 (2004-08-01), Berg et al.
patent: 7089253 (2006-08-01), Hinshaw et al.
patent: 7146366 (2006-12-01), Hinshaw et al.
patent: 2002/0092002 (2002-07-01), Babaian
patent: 2003/0061255 (2003-03-01), Shah et al.
patent: 2003/0078910 (2003-04-01), Kanai
patent: 2003/0115276 (2003-06-01), Flaherty et al.
patent: 2003/0120669 (2003-06-01), Han
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0064439 (2004-04-01), Hinshaw et al.
patent: 2004/0148150 (2004-07-01), Ashar et al.
patent: 2004/0230960 (2004-11-01), Nair
patent: 2004/0236659 (2004-11-01), Cazalet et al.
patent: 2005/0193286 (2005-09-01), Thatte et al.
patent: 2005/0210185 (2005-09-01), Renick
patent: 2005/0283769 (2005-12-01), Eichenberger et al.
patent: 2006/0026130 (2006-02-01), Botzer
patent: 2006/0112248 (2006-05-01), Meiri et al.
patent: 2006/0190504 (2006-08-01), Pruet
patent: 2006/0218206 (2006-09-01), Bourbonnais et al.
patent: 2007/0011684 (2007-01-01), Du
patent: 2007/0113056 (2007-05-01), Dale
patent: 2007/0169059 (2007-07-01), Halambi
patent: 2007/0198518 (2007-08-01), Luchangco et al.
patent: 2008/0120298 (2008-05-01), Duffy
patent: 01197876 (2002-04-01), None
patent: A-H05-197604 (1993-06-01), None
patent: A-H10-049420 (1998-02-01), None
patent: A-2004-532480 (2004-10-01), None
patent: A-2006-501585 (2006-01-01), None
patent: 10-2005-0054380 (2005-06-01), None
patent: WO/96/23254 (1996-08-01), None
patent: WO01/13202 (2001-02-01), None
patent: WO 02/095632 (2002-11-01), None
patent: WO 2004/013725 (2004-02-01), None
patent: 2007016302 (2007-02-01), None
patent: WO 2007-016302 (2007-02-01), None
Costich, Oliver, “Transition Processing Using an Untrusted Scheduler in a Multilevel Database with Replicated Architecture”, North-Holland, 1992, 17 pages.
Dekeyser, et al., “Conflict Scheduling of Transactions on XML Documents”, Australian Computer Society Inc., 2004. vol. 27, 30 pages.
Yeo, et al., “Linear Orderability of Transactions in Mobile Environment with Hetergeneous Databases”, Peninsula School of Computing and Information Technology, Monash University, Australia, 1996, 9 pages.
International Search Report dated Oct. 28, 2008 for Application No. PCT/US2008/065362, 11 pages.
Chung, et al. “The Common Case Transactional Behavior of Multithreaded programs”, High-Performance Computer Architecture, 12th International Symposium, IEEE, Feb. 2006, 12 pages.
Wolfe, M. “High Performance Compilers for Parallel Computing”, Redwood City; Addison-Wesley, 1996, ISBN 0-8053-4. Chapters 5-7, 9, 11. 222 pages.
Frigo, et al. “The implementation of the Cilk-5 Multithread Language”, Retrieved at http://supertech.csail.mit.edu/papers/cilk5.pdf, in the proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and implementation, vol. 33, Issue 5, May 1998, pp. 1-12.
Welc, et al. “Safe Futures for Java”, Retrieved at http://www.cs.purdue.edu/homes/suresh/papers/oopsla05.pdf, Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, Oct. 16-20, 2005, pp. 439-453.
Hammond, et al., “Programming with Transactional Coherence and Consistency (TCC)”, ASPLOS 2004, Oct. 7-13, 2004, Boston, Massachusetts, USA. Retrieved at http://tcc.stanford.edu/publications/tcc—asplos2004.pdf, pp. 1-13.
International Search Report, Application No. PCT/US2008/066144, dated Nov. 27, 2008, 10 pages.
International Search Report, Application No. PCT/US2008/065363, mailed Oct. 29, 2008, 10 pages.
International Search Report, Application No. PCT/US2007/085035, mailed Mar. 21, 2008, 11 pages.
Shavit, Nir, “Software Transactional Memory”, In Proceedings of the 14th Symposium on Principles of Distributed Computing, Ottawa: ACM, 1995, 10 pages.
U.S. Appl. No. 11/601,541, Non-Final Office Action mailed Jun. 12, 2009, 6 pages.
U.S. Appl. No. 11/601,541, Amendment in response to Final Office Action, filed Jun. 2, 2009, 10 pages.
Japanese Patent Application No. 2009-537403, Notice of Rejection mailed Nov. 5, 2010, English Translation, 2 pages.
U.S. Appl. No. 11/601,541, Final Office Action mailed Apr. 7, 2009, 12 pages.
U.S. Appl. No. 11/601,541, Amendment in response to Non-Final Office Action, filed Dec. 12, 2008, 12 pages.
U.S. Appl. No. 11/601,541, Notice of Allowance, dated Dec. 31, 2009, 6 pages.
U.S. Appl. No. 11/601,541, Amendment in response to Non-Final Office Action, filed Sep. 3, 2009, 8 pages.
Voluntary Claim amendments filed in Chinese Patent Application No. 20080018391.2, filed Jul. 1, 2010, 6 pages.
Chilean Patent Application No. CL200801531, Office Action dated Apr. 22, 2010, 5 pages.
Chilean Patent Application No. CL200801531, Response to Office Action, filed Jun. 8, 2010, 37 pages.
U.S. Appl. No. 11/601,541, Non-Final Office Action mailed Sep. 22, 2008, 8 pages.
U.S. Appl. No. 11/820,556, Notice of Allowance, dated Aug. 20, 2010, 13 pages.
U.S. Appl. No. 11/820,556, Amendment in Response to Non-Final Office Action, filed May 5, 2010, 12 pages.
U.S. Appl. No. 11/820,556, Non-Final Office Action mailed Feb. 5, 2010, 7 pages.
Japanese Patent Application No. 2009-537403, Notice of Rejection, dated Nov. 5, 2010, 2 pages.
EP Patent Application No. EP07845108.5, extended European Search Report, dated Sep. 16, 2010, 7 pages.
Chinese Patent Application No. 200780042809.9, Voluntary Claim amendments filed Jan. 4, 2010, 9 pages.
Chinese Patent Application No. 200780042809.9, Response to Office Action, dated Dec. 9, 2010, 36 pages.
Voluntary Claim amendments filed in Chinese Patent Application No. 20080018922.8, filed Jun. 30, 2010, 7 pages.
Chinese Patent Application No. 200780042809.9, Office Action dated Aug. 20, 2010, 12 pages.
Lance Hammond, et al., “Transactional Coherence and Consistency: Simplifying Parallel Hardware and Software”, 2004, IEEE Computer Socket, pp. 92-103.
Stanley Lippmann, et al., “C++ Primer”, Apr. 2, 1998, Addison-Wesley Professional, 3rd Edition, section 5.5, 5.7 and 5.8. 12 pages.
U.S. Appl. No. 11/810,111, Non-Final Office Action mailed Dec. 27, 2010, 28 pages.
Japanese Patent Application No. 2009-537403, Response to Notice of Rejection, filed Feb. 3, 2011, 8 pages.
EP Patent Application No. EP08770359, extended European Search Report, dated Dec. 29, 2010, 6 pages.
EP Patent Application No. EP07845108.5, Response to Extended European Search Report, dated Mar. 23, 2011, 15 pages.
U.S. Appl. No. 11/820,556, Response to Non-Final O

Affiliated with

Also associated with

Rating

Parallelizing sequential frameworks using 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 Parallelizing sequential frameworks using transactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallelizing sequential frameworks using transactions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2748908