Method and system for distributed computation having sub-task processing and sub-solution redistribution

• US 8,321,870 B2
• Filed: 08/14/2009
• Issued: 11/27/2012
• Est. Priority Date: 08/14/2009
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Messier, Daniel John, Salvo, Joseph James, Carbone, John William, Theurer, Charles Burton, Zhang, Li
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Zhao, Bing
• Application Number:
  US12/541,285
• Publication Number:
  US 20110041136A1
• Time in Patent Office: 1,201 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5017 Task decomposition
• 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: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A system for processing a computational task is presented. The system includes a plurality of nodes operationally coupled to one another via one or more networks. The plurality of nodes includes a base node including a processing subsystem configured to receive the computational task, select a subset of available nodes from the plurality of nodes based upon a present status, processing capability, distance, network throughput, range, resources, features, or combinations thereof of the plurality of nodes, divide the computational task into a plurality of sub-tasks, distribute the plurality of sub-tasks among the subset of available nodes based upon a number of nodes in the subset of available nodes, completion time period allowed for the plurality of sub-tasks, a distribution criteria, level of security required for the completion of the plurality of sub-tasks, resources available with the subset of available nodes, processing capability of the subset of available nodes, range of the subset of available nodes, features in the subset of available nodes, reliability of the subset of available nodes, trust in the subset of available nodes, the current load on the subset of available nodes, domain of the plurality of sub-tasks, or combinations thereof, receive sub-solutions corresponding to the plurality of sub-tasks from the subset of available nodes in a desired time period, and reassemble the sub-solutions to determine a solution corresponding to the computational task.

Claims

1. A system for processing a computational task, comprising:

a plurality of nodes operationally coupled to one another via one or more networks, the plurality of nodes, comprising;

a base node comprising a processing subsystem configured to;

receive the computational task;

determine nodes that are available from the plurality of nodes based on receipt of response to a query signal broadcasted to the plurality of nodes via at least one of one or more communication modes available in the one or more networks;

select a subset of available nodes from nodes available in the plurality of nodes based on information present in the response to the query signal, wherein the information comprises a present status, processing capability, distance from the base node, network throughput, range, resources, features, or combinations thereof;

divide the computational task into a plurality of sub-tasks;

distribute one or more of the plurality of sub-tasks for processing among the subset of available nodes using one of the one or more communication modes based on cost of using each of the one or more communication modes, and at least one of a number of nodes in the subset of available nodes, completion time period allowed for each of the plurality of sub-tasks, a distribution criteria, level of security required for the completion of the plurality of sub-tasks by the computational task, resources available with each of the subset of available nodes, processing capability of each of the subset of available nodes, reliability of the subset of available nodes, trust of the base node in the subset of available nodes, the current load on the subset of available nodes, or combinations thereof;

receive sub-solutions corresponding to the plurality of sub-tasks generated at the subset of available nodes within a desired time period;

verify receipt of the received sub-solutions within the desired time period to determine existence of one or more unprocessed sub-tasks from the plurality of sub-tasks;

redistribute the one or more unprocessed sub-tasks, to generate sub-solutions, to new nodes from the nodes that are available in the plurality of nodes;

receive sub-solutions corresponding to the one or more unprocessed sub-tasks within the desired time period; and

reassemble the sub-solutions to determine a solution corresponding to the computational task.

2. The system of claim 1, wherein the subset of available nodes is further configured to communicate the sub-solutions corresponding to the one or more of the plurality of sub-tasks to the base node.

3. The system of claim 1, wherein the new nodes are further configured to communicate the sub-solutions corresponding to the one or more unprocessed sub-tasks to the base node.

4. The system of claim 1, wherein the one or more networks comprises a satellite network, a cellular network, a local area network, a wide area network, a private network, a wired network, a wireless network, or combinations thereof.

5. The system of claim 1, wherein the distribution criteria comprises completion time required for the computational task, criticality of the computational task, the importance rating of the computational task, expected number of resources required for processing of the computational task, or combinations thereof.

6. The system of claim 1, wherein the communication modes comprise Bluetooth, a Global System for Mobile Communications method (GSM), a General Packet Radio Service method (GPRS), a Worldwide Interoperability for Microwave Access method (Wi-Max), Wi-Fi, 802.15.4 (Zigbee or similar), or combinations thereof.

7. The system of claim 1, wherein the plurality of nodes comprises peer devices, non-peer devices, or both.

8. The system of claim 1, wherein the processing subsystem is further configured to generate and maintain a list of the subset of available nodes.

9. The system of claim 8, wherein the list comprises details pertaining to mapping of the plurality of sub-tasks against their respective nodes from the subset of available nodes.

10. The system of claim 1, wherein the processing subsystem is configured to distribute a sub-task of the plurality of sub-tasks to multiple nodes of the subset of available nodes.

11. The system of claim 1, wherein the processing subsystem is further configured to distribute multiple sub-tasks of the plurality of sub-tasks to one node of the subset of available nodes.

12. The system of claim 1, wherein the plurality of nodes and the subset of available nodes comprise telematics devices, non-telematics devices, peer devices, non-peer devices, or combinations thereof.

13. A system for processing a computational task, comprising:

a plurality of telematics devices operationally coupled to one another via one or more networks, the plurality of telematics devices, comprising;

a base node comprising a processing subsystem configured to;

receive the computational task;

determine telematics devices that are available from the plurality of telematics devices based on a response to query signals broadcasted to the plurality of telematics devices via at least one of one or more communication modes available in the one or more networks;

select a subset of available telematics devices from telematics devices available in the plurality of telematics devices based on information present in the response to the query signal, wherein the information comprises a present status, processing capability, distance from the base node, network throughput, range, resources, features, or combinations thereof of the plurality of telematics devices;

divide the computational task into a plurality of sub-tasks;

distribute one or more of the plurality of sub-tasks for processing among the subset of available telematics devices using one of the one or more communication modes based on cost of using each of the one or more communication modes, and at least one of a number of telematics devices in the subset of available telematics devices, completion time period allowed for each of the plurality of sub-tasks, a distribution criteria, level of security required for the completion of the plurality of sub-tasks by the computational task, resources available with each of the subset of available telematics devices, processing capability of the subset of available telematics devices, communication range of the subset of available telematics devices, reliability of the subset of available telematics devices, trust of the base node in the subset of available telematics devices, current load on the subset of available telematics devices, or combinations thereof;

receive sub-solutions corresponding to the plurality of sub-tasks generated at the subset of available telematics devices within a desired time period;

verify receipt of the sub-solutions within the desired time period to determine existence of one or more unprocessed sub-tasks from the plurality of sub-tasks;

redistribute the one or more unprocessed sub-tasks, to generate sub-solutions, to new nodes from nodes that are available in the plurality of nodes;

receive sub-solutions corresponding to the one or more unprocessed sub-tasks within the desired time period; and

reassemble the sub-solutions to determine a solution corresponding to the computational task.

14. A method for processing a computational task received at a base node, comprising:

broadcasting query signals to a plurality of nodes via one or more communication modes to determine nodes that are available;

selecting a subset of available nodes from the nodes available in the plurality of nodes by determining, from information in a response to the query signal, a present status, processing capability, distance from the base node, network throughput, range, resources, and combinations thereof of the plurality of nodes;

dividing the computational task into a plurality of sub-tasks;

distributing one or more of the plurality of sub-tasks for processing among the subset of available nodes using one of the one more communication modes based on cost of using each of the one or more communication modes, and at least one of a number of nodes in the subset of available nodes, completion time period allowed for each of the plurality of sub-tasks, a distribution criteria, level of security required for the completion of the plurality of sub-tasks by the computational task, resources available with each of the subset of available nodes, processing capability of each of the subset of available nodes, reliability of the subset of available nodes, trust of the base node in the subset of available nodes, current load on the subset of available nodes, or combinations thereof;

receiving sub-solutions corresponding to the plurality of sub-tasks generated at the subset of available nodes within a desired time period;

verifying receipt of the sub-solutions within the desired time period to determine existence of one or more unprocessed sub-tasks from the plurality of sub-tasks;

redistributing the one or more unprocessed sub-tasks, to generate sub-solutions, to new nodes from nodes that are available in the plurality of nodes;

receiving sub-solutions corresponding to the one or more unprocessed sub-tasks within the desired time period; and

reassembling the sub-solutions to determine a solution corresponding to the computational task.

15. The method of claim 14, further comprising communicating the sub-solutions corresponding to the one or more of the plurality of sub-tasks by the one or more of the subset of available nodes to the base node.

16. The method of claim 14, further comprising generating and maintaining a list of the subset of available nodes.

17. The method of claim 16, wherein generating and maintaining the list comprises maintaining details pertaining to mapping of the plurality of sub-tasks against their respective nodes from the subset of available nodes.

18. The method of claim 14, wherein the plurality of nodes comprises telematics devices, non-telematics devices, peer devices, non-peer devices, or combinations thereof.

19. A method for processing a computational task received at a base node from a plurality of nodes, comprising:

determining nodes that are available from the plurality of nodes based on a response to a query signal broadcasted by the base node to the plurality of nodes via one or more communication modes;

selecting a subset of available nodes from nodes that are available in the plurality of nodes, based on information from the response to the query signal;

dividing the computational task into a plurality of sub-tasks;

distributing one or more of the plurality of sub-tasks for processing among the subset of available nodes using one of the one or more communication modes one of the based on cost of using each of the one or more communication modes, and at least one of a number of nodes in the subset of available nodes, completion time period allowed for each of the plurality of sub-tasks, a distribution criteria, level of security required for the completion of the plurality of sub-tasks by the computational task, resources available with each of the subset of available nodes, processing capability of each of the subset of available nodes, reliability of the subset of available nodes, trust of the base node in the subset of available nodes, current load on the subset of available nodes, or combinations thereof;

receiving sub-solutions of one or more of the plurality of sub-tasks generated at one or more of the subset of available nodes within a desired time period;

verifying receipt of sub-solutions within the desired time period to determine existence of one or more unprocessed sub-tasks from the plurality of sub-tasks;

redistributing the one or more unprocessed sub-tasks, to generate sub-solutions, to new nodes from nodes that are available in the plurality of nodes;

receiving sub-solutions corresponding to the one or more unprocessed sub-tasks within the desired time period; and

reassembling the sub-solutions to determine a solution corresponding to the computational task.