Optimizing data analysis through directional dependencies of a graph including plurality of nodes and attributing threading models and setting status to each of the nodes

• US 8,166,479 B2
• Filed: 06/26/2008
• Issued: 04/24/2012
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: Softlife Projects Limited
• Original Assignee: Softlife Projects Limited
• Inventors: Roberts, David, Burpee, Tony
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Rashid, Wissam
• Application Number:
  US12/147,312
• Publication Number:
  US 20090007127A1
• Time in Patent Office: 1,398 Days
• Field of Search: 718/106
• US Class Current: 718/100
• CPC Class Codes: G01N 2021/6441 with two or more labels
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

There is provided an adaptive semi-synchronous parallel processing system and method, which may be adapted to various data analysis applications such as flow cytometry systems. By identifying the relationship and memory dependencies between tasks that are necessary to complete an analysis, it is possible to significantly reduce the analysis processing time by selectively executing tasks after careful assignment of tasks to one or more processor queues, where the queue assignment is based on an optimal execution strategy. Further strategies are disclosed to address optimal processing once a task undergoes computation by a computational element in a multiprocessor system. Also disclosed is a technique to perform fluorescence compensation to correct spectral overlap between different detectors in a flow cytometry system due to emission characteristics of various fluorescent dyes.

Claims

1. A method for processing data comprising:

defining a plurality of tasks requiring execution;

identifying one or more dependencies for each respective task of the plurality of tasks, the one or more dependencies comprising at least one of a resource dependency and a memory dependency;

determining dependencies between for each respective task of the plurality of tasks wherein the dependencies include directional dependencies;

creating a directed graph, wherein the directed graph includes;

a plurality of nodes, the nodes respectively corresponding to the plurality of tasks requiring execution; and

a plurality of directed edges that respectively correspond to the directional dependencies, each of said directed edges originating from a node of the plurality of nodes and terminating on another node of the plurality of nodes; and

analyzing the directed graph to assign execution of tasks to a plurality of processors to maximize computational efficiency;

performing the following steps until all data is processed;

setting status of all nodes of the plurality of nodes to processed or unprocessed status;

when a task corresponding to a node of the plurality of nodes has been completely computed, setting status of the node to processed status;

when data corresponding to a node of the plurality of nodes has been changed, setting status of the node to unprocessed status; and

executing tasks corresponding to all unprocessed nodes of the plurality of nodes in accordance with respectively assigned threading models.

2. The method as defined in claim 1, further comprising attributing a threading model to each node of the plurality of nodes.

3. The method as defined in claim 2 wherein attributing a threading model to each node of the plurality of graphing further comprises:

assigning a parallel threading model to each said node where said node corresponds to a task that is independent, may operate in parallel, and has a non-blocked status;

assigning a strip-mine threading model to each node in a collection of nodes that correspond to tasks that operate on common data; and

assigning a non-threading model is assigned to nodes corresponding to tasks that must be executed sequentially.

4. The method as defined in claim 3 wherein for each node assigned with a strip-mine threading model, iteratively computing each corresponding task for each data range associated with the task.

5. The method as defined in claim 3 wherein a strip-mine threading model comprises:

partitioning a data set into a plurality of subsets, the size of each subset of the plurality of subsets chosen to be containable within a cache memory of predetermined size associated with a processor of the plurality of processors;

allocating processing of a subset of the plurality of subsets to the processor;

loading the subset of the plurality of subsets into the cache memory associated with the processor;

executing a task utilizing the subset of the plurality of subsets; and

indicating, by the processor, that another subset of the plurality of subsets may be allocated.

6. The method as defined in claim 3 wherein multiple threading models may be assigned to any node of said plurality of nodes.

7. The method as defined in claim 1 wherein a branch prediction model is assigned to a node of the plurality of nodes, the branch prediction model determined by an entropy characterization of data operated on by a function corresponding to the node.

8. The method as defined in claim 1, further comprising assigning each node of the plurality of nodes to one or more processing queues and executing tasks corresponding to each node assigned to the one or more processing queues.

9. The method as defined in claim 8, wherein each node of the plurality of nodes is assigned to one or more processing queues based on the an identified memory dependency identified for that node.

10. The method as defined in claim 9, wherein the memory dependency includes a desired cache level allocation.

11. The method as defined in claim 8 wherein executing tasks assigned to the one or more processing queues further comprises:

for each node of the plurality of nodes, determining whether the status of each node is blocked or un-blocked; and

executing tasks corresponding to all non-blocked nodes of the plurality of nodes then executing tasks corresponding to all blocked nodes of the plurality of nodes.

12. The method as defined in claim 11 wherein executing tasks corresponding to all blocked nodes of the plurality of nodes further comprises repeating execution of tasks corresponding to all blocked nodes of the plurality of graphing nodes once data has become available.

13. A method for optimizing utilization of processor resources comprising:

determining a plurality of processing tasks required to perform a requested computation and obtaining from the plurality of processing tasks a set of task dependencies;

determining, from the plurality of processing tasks and task dependencies, a blocking state for each of the plurality of processing tasks and setting the blocking state to blocked or non-blocked;

instantiating a plurality of graphing nodes respectively representing the plurality of processing tasks wherein said plurality of nodes are initialized to a dirty state;

defining a set of directed edges between pairs of individual nodes from the plurality of graphing nodes;

counting references for each node of the plurality of graphing nodes;

adding blocking attributes to one or more nodes of the plurality of graphing nodes;

partitioning the plurality of graphing nodes into a blocked set and an non-blocked set;

within each of the blocked set partition and the non-blocked set partition, assigning a generation number to each node of the plurality of graphing nodes;

attributing a threading model to each node of the plurality of graphing nodes;

assigning each node of the plurality of graphing nodes to one or more processing queues;

executing tasks assigned to the one or more processing queues;

performing the following steps until all data is processed;

setting status of all nodes of the plurality of graphing nodes to clean or dirty status;

when a task corresponding to a node of the plurality of graphing nodes has been completely computed, setting status of the node to clean status;

when a data corresponding to a node of the plurality of graphing nodes has been changed, setting status of the node to dirty status; and

executing all dirty nodes of the plurality of graphing nodes in accordance with respectively assigned threading models.

14. The method as defined in claim 13 wherein defining a set of directed edges between pairs of individual nodes from the plurality of graphing nodes further comprises:

adding a node reference to a node from the pair of individual nodes when the node has at least one of the set of directed edges directed to it; and

not adding a node reference to a node from the pair of individual nodes when the node has at least one of the set of directed edges originating from the node.

15. The method as defined in claim 13 wherein counting references for each node of the plurality of graphing nodes further comprises removing a node of the plurality of graphing nodes if the node has zero counted references.

16. The method as defined in claim 13 wherein assigning a generation number to each node of the plurality of graphing nodes further comprises:

assigning a node a generation number of 1 if the node has no directed edges terminating at the node;

assigning a node a generation number of n if the node has a single directed edge terminating at the node that originated from a generation n−

1 node;

if the node has multiple directed edges terminating at the node, assigning the node a generation number equal to 1 plus the maximum number of the generation number of the nodes from which the multiple directed edges originate.

17. The method as defined in claim 13 wherein adding blocking attributes to one or more nodes of the plurality of graphing nodes further comprises:

for each node of the plurality of graphing nodes, adding a blocking attribute to the node if;

the node corresponds to a task with a blocked blocking state;

or

the node has a directed edge terminating at the node and the originating node of the directed edge has a blocked blocking state.

18. The method as defined in claim 13 wherein attributing a threading model to each node of the plurality of graphing nodes further comprises:

assigning a parallel threading model to each said node where said node corresponds to a task that is independent, may operate in parallel, and has a non-blocked status;

assigning a strip-mine threading model to each node in a collection of nodes that correspond to tasks that operate on common data; and

assigning a non-threading model is assigned to nodes corresponding to tasks that must be executed sequentially.

19. The method as defined in claim 18 wherein multiple threading models may be assigned to any node of said plurality of graphing nodes.

20. The method as defined in claim 18 wherein a branch prediction model is assigned to a node, the branch prediction model determined by an entropy characterization of data operated on by a function corresponding to the node.

21. The method as defined in claim 18 wherein for each node assigned with a strip-mine threading model, iteratively computing each corresponding task for each data range associated with the task.

22. The method as defined in claim 13 wherein executing tasks assigned to the one or more processing queues further comprises executing tasks corresponding to all non-blocked nodes of the plurality of graphing nodes then executing tasks corresponding to all blocked nodes of the plurality of graphing nodes.

23. The method as defined in claim 22 wherein executing tasks corresponding to all non-blocked nodes of the plurality of graphing nodes further comprises repeating execution of tasks corresponding to all non-blocked nodes of the plurality of graphing nodes.

24. The method as defined in claim 22 wherein executing tasks corresponding to all blocked nodes of the plurality of graphing nodes further comprises repeating execution of tasks corresponding to all blocked nodes of the plurality of graphing nodes once data has become available.

25. The method as defined in claim 13 wherein when a task corresponding to a node of the plurality of graphing nodes has been completely computed, setting status of the node to dirty status until all asynchronous data has been loaded.

26. The method as defined in claim 13 wherein executing all dirty nodes of the plurality of graphing nodes in accordance with respectively assigned threading models further comprises:

re-executing a task corresponding to a node of the plurality of graphing nodes, wherein the re-execution comprises;

locating one or more predecessor nodes of the node;

determining whether the one or more predecessor nodes are set to dirty status;

reexecuting each task corresponding to the one or more predecessor nodes that are set to dirty status; and

executing the task corresponding to the node of the plurality of graphing nodes.

27. The method as defined in claim 13 wherein assigning each node of the plurality of graphing nodes to one or more processing queues is accomplished by a scheduler.

28. The method as defined in claim 27 wherein assigning each node of the plurality of graphing nodes to one or more processing queues further comprises grouping tasks within queues by predecessor tasks.

29. The method as defined in claim 27 wherein assigning each node of the plurality of graphing nodes to one or more processing queues further comprises grouping tasks within queues by data sources.

30. The method as defined in claim 27 wherein assigning each node of the plurality of graphing nodes to one or more processing queues further comprises a weighted combination of:

grouping tasks within queues within queues by predecessor tasks; and

grouping tasks within queues within queues by data sources.

31. A system for optimizing data computed by multiple processors comprising:

a plurality of processors wherein;

the processors are respectively coupled to a plurality of cache memories; and

the processors are coupled to a common data bus;

a user interface comprising a user data entry interface and a display interface;

a memory for storing data and one or more instructions for execution by the plurality of processors to implement one or more functions of the data processing system to;

define a plurality of tasks requiring execution;

identify one or more dependencies for each respective task of the plurality of tasks, the one or more dependencies comprising at least one of a resource dependency and a memory dependency;

determine dependencies between for each respective task of the plurality of tasks wherein the dependencies include directional dependencies;

create a directed graph, wherein the directed graph includes;

a plurality of nodes, the nodes respectively corresponding to the plurality of tasks requiring execution; and

a plurality of directed edges that respectively correspond to the directional dependencies, each of said directed edges originating from a node of the plurality of nodes and terminating on another node of the plurality of nodes; and

analyze the directed graph to assign execution of tasks to a plurality of processors to maximize computational efficiency;

attribute a threading model to each node of the plurality of nodes;

assign a parallel threading model to each said node where said node corresponds to a task that is independent, may operate in parallel, and has a non-blocked status;

assign a strip-mine threading model to each node in a collection of nodes that correspond to tasks that operate on common data; and

assign a non-threading model is assigned to nodes corresponding to tasks that must be executed sequentially;

wherein a strip-mine threading model comprises;

partitioning a data set into a plurality of subsets, the size of each subset of the plurality of subsets chosen to be containable within a cache memory of predetermined size associated with a processor of the plurality of processors;

allocating processing of a subset of the plurality of subsets to the processor;

loading the subset of the plurality of subsets into the cache memory associated with the processor;

executing a task utilizing the subset of the plurality of subsets; and

indicating, by the processor, that another subset of the plurality of subsets may be allocated.

32. The system as defined in claim 31 wherein multiple threading models may be assigned to any node of said plurality of nodes.

33. The system as defined in claim 31 wherein the instructions to be executed by the plurality of processors further include instructions to assign a branch prediction model to a node of the plurality of nodes, the branch prediction model determined by an entropy characterization of data operated on by a function corresponding to the node.

34. The system as defined in claim 31 wherein the instructions to be executed by the plurality of processors further include instructions to assign each node of the plurality of nodes to one or more processing queues and execute tasks corresponding to each node assigned to the one or more processing queues.

35. The system as defined in claim 34, wherein each node of the plurality of nodes is assigned to one or more processing queues based on the an identified memory dependency identified for that node.

36. The system as defined in claim 35, wherein the memory dependency includes a desired cache level allocation.

37. The system as defined in claim 34 further comprising

for each node of the plurality of nodes, determining whether the status of each node is blocked or un-blocked;

and

executing tasks corresponding to all non-blocked nodes of the plurality of nodes then executing tasks corresponding to all blocked nodes of the plurality of nodes.

38. The system as defined in claim 37, further comprising repeating execution of tasks corresponding to all blocked nodes of the plurality of graphing nodes once data has become available.

39. The system as defined in claim 31, wherein the instructions to be executed by the plurality of processors further include instructions to perform the following steps until all data is processed:

setting status of all nodes of the plurality of nodes to processed or unprocessed status;

when a task corresponding to a node of the plurality of nodes has been completely computed, setting status of the node to processed status;

when data corresponding to a node of the plurality of nodes has been changed, setting status of the node to unprocessed status; and

executing tasks corresponding to all unprocessed nodes of the plurality of nodes in accordance with respectively assigned threading models.

40. A system for optimizing data computed by multiple processors comprising:

a plurality of processors wherein;

the processors are respectively coupled to a plurality of cache memories; and

the processors are coupled to a common data bus;

a user interface comprising a user data entry interface and a display interface;

a memory for storing data and one or more instructions for execution by the plurality of processors to implement one or more functions of the data processing system to;

define a plurality of tasks requiring execution;

identify one or more dependencies for each respective task of the plurality of tasks, the one or more dependencies comprising at least one of a resource dependency and a memory dependency;

determine dependencies between for each respective task of the plurality of tasks wherein the dependencies include directional dependencies;

create a directed graph, wherein the directed graph includes;

a plurality of nodes, the nodes respectively corresponding to the plurality of tasks requiring execution; and

a plurality of directed edges that respectively correspond to the directional dependencies, each of said directed edges originating from a node of the plurality of nodes and terminating on another node of the plurality of nodes; and

analyze the directed graph to assign execution of tasks to a plurality of processors to maximize computational efficiency;

perform the following steps until all data is processed;

setting status of all nodes of the plurality of nodes to processed or unprocessed status;

when a task corresponding to a node of the plurality of nodes has been completely computed, setting status of the node to processed status;

when data corresponding to a node of the plurality of nodes has been changed, setting status of the node to unprocessed status; and

executing tasks corresponding to all unprocessed nodes of the plurality of nodes in accordance with respectively assigned threading models.