Runtime optimization of distributed execution graph

Data processing: software development – installation – and managem – Software program development tool – Translation of code

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C717S156000, C718S100000, C712S007000

Reexamination Certificate

active

07844959

ABSTRACT:
A general purpose high-performance distributed execution engine for coarse-grained data-parallel applications is proposed that allows developers to easily create large-scale distributed applications without requiring them to master concurrency techniques beyond being able to draw a graph of the data-dependencies of their algorithms. Based on the graph, a job manager intelligently distributes the work load so that the resources of the execution engine are used efficiently. During runtime, the job manager (or other entity) can automatically modify the graph to improve efficiency. The modifications are based on runtime information, topology of the distributed execution engine, and/or the distributed application represented by the graph.

REFERENCES:
patent: 5201046 (1993-04-01), Goldberg
patent: 5410696 (1995-04-01), Seki
patent: 5414849 (1995-05-01), Yamamoto
patent: 5680530 (1997-10-01), Selfridge
patent: 5999729 (1999-12-01), Tabloski, Jr.
patent: 6104962 (2000-08-01), Sastry
patent: 6154736 (2000-11-01), Chickering et al.
patent: 6237021 (2001-05-01), Drummond
patent: 6253372 (2001-06-01), Komatsu
patent: 6282708 (2001-08-01), Augusteijn
patent: 6330583 (2001-12-01), Reiffin
patent: 6378066 (2002-04-01), Lewis
patent: 6393458 (2002-05-01), Gigliotti
patent: 6430590 (2002-08-01), Fischer
patent: 6442663 (2002-08-01), Sun et al.
patent: 6505345 (2003-01-01), Chen
patent: 6662354 (2003-12-01), Krablin
patent: 6665863 (2003-12-01), Lord
patent: 7028167 (2006-04-01), Soltis, Jr.
patent: 7047232 (2006-05-01), Serrano
patent: 7292585 (2007-11-01), Slaughter et al.
patent: 7509632 (2009-03-01), Boger
patent: 7644142 (2010-01-01), Chen et al.
patent: 2002/0162089 (2002-10-01), Lewis
patent: 2003/0088755 (2003-05-01), Gudmunson
patent: 2003/0135621 (2003-07-01), Romagnoli
patent: 2003/0177240 (2003-09-01), Gulko
patent: 2003/0195938 (2003-10-01), Howard
patent: 2004/0054992 (2004-03-01), Nair
patent: 2004/0078780 (2004-04-01), Dutt et al.
patent: 2004/0216096 (2004-10-01), Messer
patent: 2004/0244006 (2004-12-01), Kaufman
patent: 2005/0034112 (2005-02-01), Stanfill
patent: 2005/0039159 (2005-02-01), Pan
patent: 2005/0188180 (2005-08-01), Illmann
patent: 2005/0198469 (2005-09-01), Mitchell
patent: 2005/0273773 (2005-12-01), Gold
patent: 2005/0278152 (2005-12-01), Blaszczak
patent: 2006/0026571 (2006-02-01), Cabillic
patent: 2006/0143611 (2006-06-01), Sadiq
patent: 2008/0079724 (2008-04-01), Isard
patent: 2008/0082644 (2008-04-01), Isard
patent: WO9930230 (1999-06-01), None
patent: WO0211344 (2002-02-01), None
Fan Chan et al., “Visual Programming support for graph-oriented parallel/distributed processing”, Published online Jul. 29, 2005 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/spe.676; Software-Practice and Experience; Softw. Pract. Exper. 2005; 35:1409-1439.
Baraglia, et al., “Resource Management Systems: Scheduling of Resource-Intensive Multi-Component Applications,” http://www.grid.it/Groups/1068825896233/1106577425414/DeliverableRisorse.pdf, Jan. 23, 2004.
Bal, et al., “ORCA: A Language for Parallel Programming of Distributed Systems,” http://ieeexplore.ieee.org/iel1/32/3545/00126768.pdf?tp=&arnumber=126768&isnumber=3545, Mar. 1992.
Blochinger, et al., “Visualizing Structural Properties of Irregular Parallel Computations,” http://delivery.acm.org/10.1145/1060000/1056036/p125-blochinger.pdf?key1=1056036&key2=2417831511&coll=Portal&dl=GUIDE&CFID=74220359&CFTOKEN=92790055, 2005.
Dean, et al., “MapReduce: Simplified Data Processing on Large Clusters,” http://labs.google.com/papers/mapreduce-osdi04.pdf, 2004, pp. 1-13.
Park, et al., “Design and implementation of the parallel multimedia file system based on message distribution,” http://portal.acm.org/citation.cfm?doid=354384.376325, 2000, pp. 422-425.
Bove, et al., “Cheops: A Reconfigurable Data-Flow System for Video Processing,” http://web.media.mit.edu/˜wad/cheops—CSVT/cheops.html, 1995, 21 pgs.
Gerlach, et al., “DPS—Dynamic Parallel Schedules,” http://dps.epfl.ch/dpsdps.pdf, 2003, 10 pgs.
Fritzson, “A Task Merging Technique for Parallelization of Modelica Models,” http://www.modelica.org/events/Conference2005/online—proceedings/Session1/Session1c4.pdf, Mar. 7-8, 2005, pp. 123-128.
Upgrade: A Framework for Building Graph-Based Interactive Tools http://ai1.inf.uni-bayreuth.de/apache/publications/westfechtel/2002/GRABATS%202002.pdf.
Harrold, et al., “Aristotle: A System for Research on and Development of Program Analysis Based Tools,” http://www.cc.gatech.edu/aristotle/Publications/Papers/aristotle.ps, Mar. 1997, 13 pgs.
Akinde, et al., “Constructing GPSJ View Graphs,” http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-19/paper8.pdf, 1999, 12 pgs.
Liechti, et al., “Structured graph format: XML metadata for describing Web site structure,” http://xml.coverpages.org//sgfWWW7.html, 13 pgs, Computer Networks and ISDN Systems, 1998.
Babaoglu, Ozalp et al. Mapping Parallel Computations onto Distributed Systems in paralex. Department of Mathematics, University of Bologna [online], May 1991 [retrieved on Feb. 25, 2010]. Retrieved from the Internet: <URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber+00257368>.
Babaoglu, “Paralex: An Environment for Parallel Programming in Distributed Systems,” Department of Mathematics, University of Bologna, Italy, Jul. 2004.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Runtime optimization of distributed execution graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Runtime optimization of distributed execution graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Runtime optimization of distributed execution graph will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4226463

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.