Take the 2-minute tour ×
Ask Patents is a question and answer site for people interested in improving and participating in the patent system. It's 100% free, no registration required.

http://www.google.com/patents/US20140108489

I work on a system that closely resembles the invention described in the above application. It in fact shares a common intellectual lineage, dating back over 25 years. The principals of the assignee, ET International, and at least some of the inventors are definitely aware of our work, since we interact with them regularly at academic conferences.

I'm going to try to lay out an answer describing the correspondence between the claims presented and prior art produced by my lab and others before the date of priority. I'll appreciate any help I can get in presenting that properly, and adding references I'm unaware of. Thus, I'll leave the answer as Community Wiki, to share credit for help knocking this dangerous application down.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Although I am a co-inventor on a particular multiprocessor cache coherency patent I do not understand this subject matter at all. I would like to point something out that may just reflect unfamiliarly with the term "reads on" or might be more fundamental. You have "reads on" going in the wrong direction. A proposed claim is not novel if it reads on some existing reference. That is, the previous thing needs to have everything in it that the claim requires in order for the claim to read on the prior art reference or system. Then we would say the previous work anticipates the claimed invention. –  George White Aug 17 at 5:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.