Claims(21)
What is claimed is:
1) A method of performing data processing in a distributed computing system the method including: instantiating plural flowlets associated
with a workflow, the workflow implementing a program for accomplishing
at least one data processing task, on multiple compute nodes of the
distributed computing system; and interconnecting, the flowlets
between one or more data sources and data sinks to form at least one
directed acyclic graph between the at one or more data sources and
data sinks.
http://charm.cs.illinois.edu/newPapers/06-18/paper.pdf
@inproceedings{orch06,
Author = "Chao Huang and Laxmikant V. Kale",
Title = "Charisma: Orchestrating Migratable Parallel Objects",
booktitle = "Proceedings of IEEE International Symposium on High Performance Distributed Computing (HPDC)",
year = 2007,
month = "July"
}
The background runtime system environment is a distributed computer system, and the benchmarks in this and many earlier papers clearly show execution on multiple compute nodes.
The 'Chares' of our work correspond to 'flowlets' in the claimed invention. Our much earlier 'chare arrays' (circa 2001) correspond to "plural flowlets associated with a workflow". The Charisma language described in this paper and subsequent publications prior to this filing provides the interconnection between data sources and sinks that forms a DAG among them.
If I wanted to really press the point, our much earlier work with Charm++ and Structured Dagger reads on this base claim as well, with the DAG being induced by the codified pattern of source objects directing messages to receiving objects.
2) The method of claim 1, Wherein the interconnecting includes using key/value pairs to route data among flowlets, wherein a key maps to a
particular compute node, and a value represents data.
The 'Group' and 'NodeGroup' constructs of basic Charm++ (1990's) describe this exactly - they are collections of objects where a key directly identifies particular compute processors and nodes. The location management scheme of our chare arrays may also read on this, in that an index in a collection maps to the compute node hosting the corresponding object. That location is used to pass values through remote method calls on those objects.
3) The method of claim 1, wherein the interconnecting includes routing output data from one or more flowlets to one or more inputs of one or
more other flowlets.
The reduction, multicast, scatter, gather, and permute operations of Charisma read on this exactly.
4) The method of claim 3, further comprising implementing flow control between at least one flowlet of the one or more flowlets and at least
one of the one or more other flowlets to whose inputs data is directly
or indirectly routed from the at least one flowlet of the one or more
flowlets.
5) The method of claim 4, wherein the flow control includes one or more techniques selected from the group consisting of throttling of a
rate of data processing by the at least one flowlet of the one or more
flowlets; determination of when to start or stop processing of data by
the at least one flowlet of the one or more flowlets; determination of
when to send data from the at least one flowlet of the one or more
flowlets to the one or more other flowlets; and window-based flow
control; signaling one or more upstream direct or indirect data
sources of a flowlet to start, stop, throttle up, or throttle down.
I've got nothing off the top of my head for flow control, but this can be revisited. I suspect that stream analytics implementations competing with ET International's might read on this, though.
6) The method of claim 1, further comprising storing a state of at least one flowlet to provide fault tolerance.
7) The method of claim 6, wherein storing a state comprises storing the state in a compute node other than a compute node on which a
corresponding flowlet is instantiated.
http://ppl.cs.illinois.edu/research/ft
Dozens of papers, dating as far back as 2004. One of the oldest, 04-06, reads on both of these claims.
8) The method of claim 7, further comprising instantiating the at least one flowlet on more than one compute node, wherein storing the
state in a compute node other than a compute node on which a
corresponding flowlet is instantiated includes storing the state in a
compute node on which the corresponding flowlet has a second
instantiation.
This is classical 'replica' based fault tolerance, which has been implemented by many systems. Our implementation starts almost contemporary with the earliest claimed priority (2012-10-29 "First commit to enable replica logic"). Given the much earlier work on both replica FT and our flowlet-like system, this was also an obvious combination in the KSR v. Teleflex sense.
9) The method of claim 1, further comprising: locking a local state store on a compute node such that it can only be accessed by a single
worker thread of the compute node on which the at least one flowlet is
run; and unlocking the local state store after the contents of the
local state store have been stored in a state store on a second
compute node.
I'll have to dig a little deeper to find something matching the "lock; copy elsewhere; unlock" pattern, but I think I can. I'd welcome others' input on this point.
10) The method of claim 1, wherein multiple flowlets are instantiated on a single compute node of the plurality of compute nodes, and
wherein the method further includes implementing at least one load
balancing technique among the flowlets instantiated on the single
compute node.
The first clause describes our very old well-published notions of processor virtualization and overdecomposition. Our early-2000's implementation of load balancing chares between processing elements would seem to apply for the processing elements and their chares within a single compute node.
11) The method of claim 1, further comprising implementing a preemption scheme among tasks of different priorities for at least one
worker thread of at least one of the compute nodes.
Our immediate entry methods read on this. They no longer appear in our documentation because they were deprecated as a bad idea several years ago.
12) A distributed computing system including: a plurality of compute nodes, wherein a compute node includes at least one processor and
memory; wherein a plurality of flowlets associated with a workflow,
the workflow implementing a program for accomplishing at least one
data processing task, are instantiated on at least a subset of the
compute nodes; and wherein the plurality of flowlets are
interconnected to form one or more directed acyclic graphs between one
or more data sources and one or more data sinks.
Once again, Charm++ code with chare arrays in general, and their induced DAGs, and Structured Dagger and Charisma more specifically.
13) The system of claim 12, further including one or more state stores on at least one of the plurality of compute nodes, wherein the at
least one state store is configured to store a state of a flowlet
during processing of data by the flowlet.
I'm not exactly sure how to read this claim. Is the "state store" describing 'workspace' or 'scratchpad' memory, or something else? Does our work with the Cell processor and the SPE-local memory
14) The system of claim 13, wherein at least one of the one or more state stores is configured to store a state of a flowlet running on a
different compute node from the compute node on which the at least one
of the one or more state stores is implemented.
This is further from what we've worked on, but seems like it might read directly on things like Apache Hadoop that ET International is explicitly competing with.
15) The system of claim 12, wherein key/value pairs are used to interconnect the flowlets, wherein a key maps to a particular compute
node, and a value represents data.
This is a combination of the execution model of Charm++-like systems and the logical design of MapReduce/Hadoop applications.
16) The system of claim 15, further including at least one key/value store configured to be shared among multiple compute nodes of the
plurality of compute nodes.
Hadoop hooked up to any NoSQL database, perhaps?
17) The system of claim 16, wherein the at least one key/value store is distributed among multiple compute nodes of the plurality of
compute nodes.
And that NoSQL database is distributed.
In fact, my predecessor's and my own published work on 'Multiphase Shared Arrays' could also read on claims 15 through 17.
18) The system of claim 12, wherein at least one of the compute nodes includes at least two priority-based task queues configured to store
tasks to be performed by at least one worker thread of the respective
compute node, wherein the at least one worker thread is configured to
preempt a lower-priority task with a higher-priority task and to
enqueue the lower-priority task on a lower-priority one of the
priority-based task queues.
Our implementation doesn't do this (see above; we've stepped away from preemption), but I bet someone else has made such a configuration.
19) A computer-readable medium containing executable instructions configured to cause one or more processors to implement the method of
claim 1.
20) The method of claim 1, further including downloading executable instructions configured to implement said instantiating and said
implementing.
21) The method of claim 1, further including providing for download executable instructions configured to implement said instantiating and
said implementing.
19-21 seem to be the standard 'do it on a computer' boilerplate.
prior-art-request
