METHOD AND SYSTEM FOR DISTRIBUTED COMPUTATION

• US 20110041136A1
• Filed: 08/14/2009
• Published: 02/17/2011
• Est. Priority Date: 08/14/2009
• Status: Active Grant

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Theurer, Charles Burton, Carbone, John William, Zhang, Li, Salvo, Joseph James, Messier, Daniel John
• Granted Patent: US 8,321,870 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• 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;

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 within a 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 configured to process one or more of the plurality of sub-tasks to generate the sub-solutions corresponding to the one or more of the plurality of sub-tasks.

3. The system of claim 2, 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.

4. The system of claim 2, wherein the processing subsystem is further configured to:

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

redistribute the one or more unprocessed sub-tasks to new nodes.

5. The system of claim 4, wherein the new nodes are configured to process the one or more unprocessed sub-tasks to determine sub-solutions corresponding to the one or more unprocessed sub-tasks.

6. The system of claim 5, 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.

7. 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.

8. The system of claim 1, wherein the distribution criteria comprises completion time of 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.

9. The system of claim 1, wherein the plurality of nodes are configured to communicate with one another via one or more communication modes, the communication modes comprising a 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.

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

11. The system of claim 1, wherein the processing subsystem is configured to divide the computational task into the plurality of sub-tasks based upon a nature of the computational task, size of the computational task, type of the computational task, expected number of available nodes, a number of nodes in the subset of available nodes, level of security required for the completion of the computational task, 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, current load on the subset of available nodes, domain of the plurality of sub-tasks, or combinations thereof.

12. The system of claim 1, wherein the computational task comprises facial recognition tasks, voice recognition tasks, traffic management tasks, routing tasks, video processing tasks, image processing tasks, vehicle management subsystem tasks, gaming and entertainment tasks, messaging tasks, signal processing tasks, tasks for analyzing large sets of data, and the like.

13. The system of claim 1, wherein the processing subsystem in the base node is configured to select the subset of available nodes from the plurality of nodes based upon signals broadcast to the plurality of nodes.

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

15. The system of claim 14, wherein the list comprises details of the plurality of sub-tasks mapped against their respective nodes of the subset of available nodes.

16. 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.

17. 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 or more nodes of the subset of available nodes.

18. 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.

19. 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;

select a subset of available telematics devices from the plurality of telematics devices based upon a present status, processing capability, distance, 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 the plurality of sub-tasks among the subset of available telematics devices 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, 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 telematics devices within a desired time period; and

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

20. A method for processing a computational task, comprising:

selecting a subset of available nodes from a plurality of nodes by determining a present status, processing capability, distance, network throughput, range, resources, features, and combinations thereof of the plurality of nodes;

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

distributing 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, current load on the subset of available nodes, domain of the plurality of sub-tasks, or combinations thereof;

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

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

21. The method of claim 20, further comprising processing one or more of the plurality of sub-tasks by the subset of available nodes to generate sub-solutions corresponding to the one or more of the plurality of sub-tasks.

22. The method of claim 21, 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.

23. The method of claim 20, wherein receiving the sub-solutions corresponding to the plurality of sub-tasks from the subset of available nodes further comprises:

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

redistributing the one or more unprocessed sub-tasks to new nodes.

24. The method of claim 20, wherein the computational task comprises facial recognition tasks, voice recognition tasks, traffic management tasks, routing tasks, video processing tasks, image processing tasks, vehicle management subsystem tasks, gaming and entertainment tasks, messaging tasks, signal processing tasks, tasks for analyzing large sets of data, or combinations thereof.

25. The method of claim 20, wherein dividing the computational task into the plurality of sub-tasks further comprises dividing the computational task into the plurality of sub-tasks based upon a nature of the computational task, size of the computational task, type of the computational task, expected number of available nodes, a number of nodes in the subset of available nodes, level of security required for the completion of the computational task, 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, current load on the subset of available nodes, domain of the plurality of sub-tasks, or combinations thereof.

26. The method of claim 20, wherein selecting the subset of available nodes further comprises broadcasting signals from the base node to the plurality of nodes to determine availability of the nodes.

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

28. The method of claim 27, wherein generating and maintaining the list comprises maintaining details of the plurality of sub-tasks mapped against their respective nodes of the subset of available nodes.

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

30. A method for processing a computational task, comprising:

selecting a subset of available nodes by determining a present status of a plurality of nodes;

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

distributing 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, current load on the subset of available nodes, domain of the plurality of sub-tasks, or combinations thereof;

receiving sub-solutions of one or more of the plurality of sub-tasks from 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;

redistributing the one or more unprocessed sub-tasks to new 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.