Method and apparatus for executing neural network applications on a network of embedded devices

• US 6,418,423 B1
• Filed: 01/29/1999
• Issued: 07/09/2002
• Est. Priority Date: 01/29/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kanevsky, Dimitri, Kambhatla, Nandakishore, Zadrozny, Wlodek Wlodzimierz
• Primary Examiner(s): Dam, Tuan Q.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/239,939
• Time in Patent Office: 1,257 Days
• Field of Search: 706/15, 706/45, 702/34, 709/200
• US Class Current: 706/15
• CPC Class Codes: G06N 3/10 Interfaces, programming languages or software development kits, e.g. for simulating neural networks

Abstract

Disclosed is a system and a method for combining the computational resources of numerous embedded devices to enable any of them to perform complex tasks like speech recognition or natural language understanding. A distinguished master device communicates with a network of embedded devices, and organizes them as the nodes of a neural network. To each node (embedded device) in the neural network, the master device sends the activation function for that node and the connectivity pattern for that node. The master device sends the inputs for the network to the distinguished input nodes of the network. During computation, each node computes the activation function of all of its inputs and sends its activation to all the nodes to which it needs to send output to. The outputs of the neural network are sent to the master device. Thus, the network of embedded devices can perform any computation (like speech recognition, natural language understanding, etc.) which can be mapped onto a neural network model.

Claims

1. An master embedded device having one or more memories and one or more computing sections, further comprising:

a communication section that communicates signals to and from one or more slave embedded devices;

an availability process that periodically identifies one or more of the slave embedded devices as available embedded devices being slave embedded devices that are able to communicate with the master embedded device and to perform a neural network computation;

a mapping process that periodically maps one or more nodes of a neural network on to each of the available embedded devices;

a starting process that periodically sends a message to all of the mapped available devices to start their respective neural network computation; and

a collection process that collects an output of the neural network.

2. A master embedded device, as in claim 1, where the communication section comprises any one or more of the following:

a wireless connection, a cellular telephony connection, an infrared connection, a coaxial cable connection, a fiber optic connection, a microwave connection, and a satellite communication connection.

3. A master embedded device, as in claim 1, where the device is embedded within any one or more of the following:

a digital cellular telephone, a hand-held device, a digital watch, a personal digital assistant, a calculator, a pen, a household appliance, a television set, a radio, a computer, a cable television box, a toaster, and a microwave oven.

4. A master embedded device, as in claim 1, where:

A. the availability process comprises the steps of;

developing a list of unresponsive available embedded devices, a list of currently available embedded devices, and a list of newly available embedded devices; and

B. the mapping process comprises the steps of;

determining a number of the nodes that are mapped to the unresponsive available embedded devices, being unassigned nodes;

comparing the number of unassigned nodes to the number of newly available devices;

assigning each unassigned node to a newly available device if the number of unassigned nodes is less than or equal to the number of newly available devices; and

assigning one or more unassigned nodes to each of the newly available embedded devices and to zero or more of the currently available embedded devices if the number of unassigned nodes is greater than the number of newly available devices.

5. A master embedded device, as in claim 1, where the starting process comprises the following steps:

for each slave embedded device corresponding to one of the nodes, sending a weight for each connection to the node, an incoming identity of the slave embedded devices performing the network calculation of one or more respective incoming nodes, an outgoing identity of the slave embedded devices performing the network calculation of one or more respective outgoing nodes, and an activation function for the node; and

sending the inputs to the neural network to the slave embedded devices corresponding to one or more input nodes.

6. A master embedded device, as in claim 1, where collection process comprises the following steps:

waiting for a “

computation done”

message from all of the slave embedded devices, being output devices, that correspond to one or more output nodes of the neural network; and

retrieving the output from all of the output devices.

7. A slave embedded device having one or more memories and one or more computing sections, further comprising:

a communication section that communicates signals to and from one or more master embedded devices and one or more other slave devices;

a looping process that waits for event messages communicated from one or more of the master embedded devices;

a response status process executed after receiving a “

available”

event message; and

a neural network set up process executed after receiving a “

setup”

event message.

8. A slave embedded device, as in claim 7, where the communication section comprises any one or more of the following:

a wireless connection, a cellular telephony connection, an infrared connection, a coaxial cable connection, a fiber optic connection, a microwave connection, and a satellite communication connection.

9. A slave embedded device, as in claim 7, where the device is embedded within any one or more of the following:

a digital cellular telephone, a hand-held device, a digital watch, a personal digital assistant, a calculator, a pen, a household appliance, a television set, a radio, a computer, a cable television box, a toaster, and a microwave oven.

10. A slave embedded device, as in claim 7, where the response status process comprises the steps of:

checking the status of the computing sections and the memory;

sending an “

available”

message to the master embedded device if the memory and computing section have adequate free resources; and

sending a “

busy”

message to the master embedded device if the memory and computing section have no adequate free resources.

11. A slave embedded device, as in claim 7, where the neural network set up process comprises the steps of:

A. extracting from the “

setup”

event message one or more nodes to which the slave embedded device is mapped;

for each of the mapped nodes, extracting from the “

setup”

event message the following;

a weight for each connection to the nodes to which the respective mapped node is connected, an incoming identity of the slave embedded devices performing the network calculation of one or more respective incoming nodes, an outgoing identity of the slave embedded devices performing the network calculation of one or more respective outgoing nodes, and an activation function for the mapped node; and

B. executing a neural network process comprising the following steps;

waiting for activation messages from incoming nodes;

after receiving an activation message, retrieving an activation and a destination node identity for which the activation message is intended; and

checking that all the activations have arrived for each destination node; and

executing a node computation process for each destination node for which all activations have arrived.

12. A slave embedded device, as in claim 11, where the node computation process comprises the steps of:

computing an activation using the activation function and all the activations received from incoming nodes, sending an activation message containing the computed activation to all the slave embedded devices corresponding to the output nodes of the node; and

sending a “

computation done”

message to the master embedded device if the node is an output node of the neural network.

13. A neural network comprising:

A. one or more slaves embedded device having one or more memories and one or more computing sections, further comprising;

a slave communication section that communicates signals to one or more other slave devices and one or more master devices;

a looping process that waits for event messages;

a response status process executed after receiving a “

available”

event message; and

a neural network set up process executed after receiving a “

setup”

event message;

B. one or more master embedded devices having one or more memories and one or more computing sections, further comprising;

a master communication section that communicates signals to and from one or more of the slave embedded devices;

an availability process that periodically identifies one or more of the slave embedded devices as available embedded devices being slave embedded devices that are able to communicate with the master embedded device and to perform a neural network computation;

a mapping process that periodically maps one or more node of a neural network on to each of the available embedded devices;

a starting process that periodically sends a message to all of the mapped available devices to start their respective neural network computation; and

a collection process that collects an output of the neural network.

14. A neural network, as in claim 13, used for any one or more of the following:

recognizing phonemes of human speech, recognizing handwritten letters of an alphabet, recognizing identity of human faces, and processing natural language text.

15. A master embedded device neural network process comprising the steps of:

periodically identifying one or more of the slave embedded devices as available embedded devices being slave embedded devices that are able to communicate with the master embedded device and to perform a neural network computation;

periodically mapping one or more node of a neural network on to each of the available embedded devices;

periodically sending a message to all of the mapped available devices to start their respective neural network computation; and

collecting an output of the neural network.

16. A master embedded device neural network system comprising:

means for periodically identifying one or more of the slave embedded devices as available embedded devices being slave embedded devices that are able to communicate with the master embedded device and to perform a neural network computation;

means for periodically mapping one or more node of a neural network on to each of the available embedded devices;

means for periodically sending a message to all of the mapped available devices to start their respective neural network computation; and

means for collecting an output of the neural network.

17. A computer program product for a master embedded device which performs the steps of:

periodically identifying one or more of the slave embedded devices as available embedded devices being slave embedded devices that are able to communicate with the master embedded device and to perform a neural network computation;

periodically mapping one or more node of a neural network on to each of the available embedded devices;

periodically sending a message to all of the mapped available devices to start their respective neural network computation; and

collecting an output of the neural network.

18. A slave embedded device process comprising the steps of:

communicating signals to and from one or more master embedded devices and one or more other slave devices;

looping that waits for event messages communicated from one or more of the master embedded devices;

responding status after receiving a “

available”

event message; and

setting up a neural network after receiving a “

setup”

event message.

19. A slave embedded device having one or more memories and one or more computing sections, further comprising:

means for communicating signals to and from one or more master embedded devices and one or more other slave devices;

means for looping that waits for event messages communicated from one or more of the master embedded devices;

means for responding status after receiving a “

available”

event message; and

means for setting up a neural network after receiving a “

setup”

event message.

20. A computer program product for a slave embedded device which performs the steps of:

communicating signals to and from one or more master embedded devices and one or more other slave devices;

looping that waits for event messages communicated from one or more of the master embedded devices;

responding status after receiving a “

available”

event message; and

setting up a neural network after receiving a “

setup”

event message.