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

The present invention generally relates to embedded devices and, more particularly, to a method and apparatus for executing neural network applications on a network of embedded devices.

An embedded device 100 is a portable device with an embedded electronic chip (which we call a central processing unit or CPU 120 ) and memory 130 which enable it to perform digital computations and communicate with other computers and embedded devices. Such devices are becoming endemic. Examples include digital cellular telephones, hand-held devices like the Palm Pilot, digital watch, calculator, pen, and even household appliances like television sets, radio sets, toasters, microwaves etc. Embedded devices can communicate with each other using telephone or cable wires, or cellular wireless communication.

The embedded chips in embedded devices have relatively small processing power, which is insufficient to solve complex tasks like recognizing speech phonemes or natural language understanding, etc. Currently, the processing of such complex tasks requires the use of non-embedded devices with sufficient computation resources (e.g. desktop computers, laptops etc.).

One approach to enabling complex computation through embedded devices is to use a client server interface in which client programs executing in embedded devices communicate (wirelessly) with a remote server on a workstation. FIG. 1 shows an embedded device 100 (cellular phone) communicating to a remote server 110 (a mainframe computer) using cellular wireless technology. Using the setup shown in FIG. 1, the cellular phone can execute complex applications. However, bandwidth limitations on typical current wireless communication channels severely limit the utility of this approach.

There are other disadvantages of much of this prior art. For example, often there is a lack of fault tolerance and a lack of speedy execution. The prior art often cannot recover from a cell phone going out of range and cannot take advantage of more cooperative cell phones coming into range. Also bandwidth limitations cause slow computation.

Another approach to enabling complex computation on embedded devices is to perform parallel distributed processing on distributed representations of task input. Neural networks are an eminently suitable mechanism for achieving this. This approach has the advantage of increased fault-tolerance and can make use of newly available embedded devices. Failure of some device does not fatally impair overall computation. Also, there is a much speedier execution of target application even on devices with low compute power and limited bandwidth.

FIG. 2 shows a feedforward neural network. A feedforward neural network 200 is a network of simple processing units, called “nodes” 210 , each of which computes an activation function 230 of all the inputs received by it and sends the result of the computation, called the “activation” 240 to some other nodes. Designated input nodes 250 do not perform any computation and simply send the inputs received by them (the inputs to the neural network 220 ) to their connecting nodes. The activation 240 at designated output nodes 260 is the “output” 270 of the neural network. Each connection between two nodes is directed. For example, n 5 is the starting node 211 and n 7 is the ending node 212 for the connection w 75 which is the “weight”, typically 280 , attached to it. This weight 280 is used in the computation of the activation function 230 (FIG. 3 below) at the ending node 212 of the connection. We refer to all the starting nodes of connections feeding into a node as the ‘incoming nodes’ (typically 213 ) for that node. Similarly, we refer to all the ending nodes of connections feeding out of a node as the ‘outgoing nodes’ (typically 214 ) for that node. To continue the example, all nodes feeding node n 5 , i.e. nodes n 1 and n 2 , are incoming nodes 213 for n 5 and all nodes receiving information from n 5 , e.g. nodes n 6 and n 7 are outgoing nodes 214 of node n 5 . The pattern of connectivity of the nodes, the weights associated with connections, and the specific function computation at each node determine the output 270 of the neural network.

Neural networks 200 are usually implemented as software simulations of the networks. Neural networks are widely applied to statistical pattern classification, regression and time series analysis tasks. In most applications, the inputs to the neural network represent mathematical representations of task related experience, which are used to learn the weights 280 of the connections, such that the correct output can be predicted with minimal error.

FIG. 2 shows a three layered feedforward neural network 200 , where n 1 , n 2 , n 3 , n 4 , n 5 , n 6 and n 7 are the nodes 210 and w 31 , w 32 , w 41 , w 42 , w 51 , w 52 , w 63 , w 64 , w 65 , w 73 , w 74 and w 75 are the weights 280 of the connections between the nodes. Nodes n 1 and n 2 are the designated input nodes 250 of the network. Nodes n 3 , n 4 , and n 5 receive inputs from nodes n 1 and n 2 . Nodes n 6 and n 7 are the designated output nodes 260 which receive inputs from nodes n 3 , n 4 , and n 5 . Nodes n 3 , n 4 , n 5 , n 6 and n 7 compute an activation function 230 which is a weighted sum of their inputs from other nodes as shown in FIG. 3 . The result of computations (activations 240 ) of nodes n 3 , n 4 , and n 5 are sent to nodes n 6 and n 7 . The activations 240 of nodes n 6 and n 7 represent the output 270 of the neural network. In this example, the inputs 220 to the network (i.e. inputs to nodes n 1 and n 2 ) might represent two parameters (e.g. pitch and fundamental frequency) from which the gender of a speaker needs to be determined. In such a scenario, the outputs of nodes n 6 and n 7 might represent the two genders male and female. The actual classification is achieved by comparing the numerical values of the activations of the nodes n 6 and n 7 and assigning the gender corresponding to the node with the greater numeric value. The weights 280 of the network are learned by presenting the network with several examples of (pitch, frequency, gender) triplets and “training” the network. There are a number of well known neural network training algorithms.

It is an object of the present invention to provide a method and a system for combining the computational resources in embedded devices for executing neural network based applications.

It is yet another object of this invention to provide a method and a system for representing each embedded device as a node in a neural network that communicates with other nodes (embedded chips) for executing neural network based applications.

This invention is directed towards 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.

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIG. 1 is diagram showing a prior art client server mechanism for executing applications on a remote server through client embedded devices.

FIG. 2 is a diagram of a prior art neural network with two input nodes and two output nodes.

FIG. 3 is a diagram of a prior art single node (embedded device) of the neural network in FIG. 2, its inputs and outputs, and its activation function.

FIG. 4 is a diagram of neural network where embedded devices perform the functions of nodes of the network.

FIG. 5 is a flowchart showing the ‘Master Device Process’ used by a distinguished master device to facilitate the neural network computation.

FIG. 5 ( a ) is a flowchart showing the ‘Find Available Embedded Devices’ process executing on the Master Device.

FIG. 5 ( b ) is a flowchart showing the ‘Map Embedded Devices to Neural Network nodes’ process executing on the Master Device.

FIG. 5 ( c ) is a flowchart showing the ‘Start Neural Network on Embedded Devices’ process executing on the Master Device.

FIG. 5 ( d ) is a flowchart showing the ‘Collect Neural Network output’ process executing on the Master Device.

FIG. 6 is a flowchart showing the ‘Listen for Embedded Devices’ process executing on all the slave devices.

FIG. 6 ( a ) is a flowchart showing the ‘Respond Status’ process executing on all the slave devices.

FIG. 6 ( b ) is a flowchart showing the ‘Setup Neural Network Computation’ process executing on all the slave devices.

FIG. 6 ( c ) is a flowchart showing the ‘Execute Neural Network Computation’ process executing on all the slave devices.

FIG. 6 ( d ) is a flowchart showing the ‘Node Computation’ process executing on all the slave devices.

FIG. 4 shows a diagram of a feedforward neural network 200 where each node 210 of the network is an embedded device 100 . In particular, there is a distinguished Master Device 410 and several Slave Devices 420 (all the other embedded devices). The Master Device 410 is simply the device which needs to and decides to start a networked computation. The Master Device 410 initiates the computation performed by the network using the Master Device Process 500 shown in FIGS. 5, 5 ( a ), 5 ( b ), 5 ( c ) and 5 ( d ). In our system, all embedded devices 100 which are potential candidates for participation in the networked computation are Slave Devices 420 and execute the algorithm described in FIGS. 6, 6 ( a ), 6 ( b ), 6 ( c ), and 6 ( d ). Note that the same embedded device might operate both as a Master Device 410 and as a slave device 420 (e.g. the microwave appliance in FIG. 4 ).

FIG. 5 shows the Master Device Process 500 executing on the embedded device 100 acting as the Master Device 410 . The Master Device periodically (e.g. every few minutes or seconds in the preferred embodiment) executes the process ‘Find Available Embedded Devices’ 510 to find the embedded devices which are currently within communication range and are willing to participate in the neural network computation. After finding the available embedded devices, the master device 410 executes the ‘Map Embedded Devices to Neural Network Nodes’ 520 process which assigns the neural network nodes to the available embedded devices, and the ‘Start Neural Network on Embedded Devices’ 530 process to start the computation on all the embedded devices currently participating in the network. The Master Device 410 also starts a ‘Collect Neural Network output’ process 550 which gathers the output of the neural network 270 from the embedded devices which are executing the computation for the output nodes 260 of the neural network.

FIG. 5 ( a ) shows a flowchart for the ‘Find Available Embedded Devices’ process 510 which executes periodically on the Master Device 410 . The Master Device broadcasts 512 a prearranged signal to all devices 100 within communication range (e.g. broadcasting a signal at a specific frequency using cellular wireless technology). The Master Device waits for an ‘available’ response from embedded devices and compiles a list 514 of available embedded devices, a list of previously available embedded devices which are no longer within communication range, and a list of embedded devices which are newly ‘available’. Note that a lack of response from an embedded device classifies it as an ‘unavailable’ device which is out of communication range. Thus, a device which responds with a ‘busy’ response is classified in the ‘available’ list, but not in the newly available list, and a device which responds with an ‘available’ response is classified into both the newly available and the available lists.

FIG. 5 ( b ) shows a flowchart of the ‘Map Embedded Devices to Neural Network Nodes’ process 520 executing periodically on the Master Device 410 . The Master Device computes n 1 , the number of neural network nodes which are currently unassigned to any embedded device (due to embedded devices becoming unavailable) and n 2 , the number of embedded devices that have newly become available. If n 1 <n 2 , the Master Device assigns the n 1 nodes to n 1 of the newly available Embedded Devices. If n 2 is 0 (i.e. if there are no newly available embedded devices), the Master Device assigns the n 1 nodes of the neural network to n 1 of the embedded devices which are already participating in the neural network computation and are still within communication range. If n 2 >0 and n 2 <n 1 , the Master Device assigns the n 1 nodes to the n 2 newly available embedded devices as equally as possible. This is accomplished by use of well known balancing algorithms.

FIG. 5 ( c ) shows a flowchart for the ‘Start Neural Network on Embedded Devices’ process 530 executing periodically on the Master Device 410 . By this time, all the nodes of the neural network have been assigned to different embedded devices. The Master Device now sends the weights 280 , local connectivity patterns (i.e. the devices executing the incoming nodes 213 and the outgoing nodes 214 for the current node), and the activation function 230 for each node 210 of the neural network to the Slave Device 420 responsible for it. The communication might be using remote wireless technology in the preferred implementation. The Master Device 410 also sends the inputs of the neural network 220 to the embedded devices 100 executing the computation of the input nodes of the neural network 250 .

FIG. 5 ( d ) shows a flowchart of the ‘Collect Neural Network Output’ process 550 executing on the Master Device 410 . This process waits for a ‘computation done’ event message from all the embedded devices executing the computation of the output nodes of the neural network. The Master Device 210 retrieves the output of the neural network 270 from these event messages and processes the output 270 as per the application.

FIG. 6 shows a flowchart describing the ‘Listen for Embedded Devices’ process 600 executing on all embedded devices 100 which wish to participate in networked computation (i.e. slave devices 420 ). The ‘Listen for Embedded Devices’ process 600 continuously loops waiting for events. If the slave device 420 receives an ‘available?’ query message, it executes a ‘respond status’ process 630 . If the slave device 420 receives a ‘set up Neural Network Computation’ message, it executes a ‘Set up Neural Network Computation’ process 640 .

FIG. 6 ( a ) shows a flowchart describing the ‘Respond Status’ process 630 executing on slave devices 420 . The slave device checks the status of its CPU 120 and memory 130 . If the slave device is either idle, or executing some computation, but not utilizing all of its CPU and memory, it sends an ‘available’ message to the Master Device 410 . If the slave device is utilizing all of its CPU and memory in some computation, it sends a ‘busy’ message to the Master Device 410 .

FIG. 6 ( b ) shows a flowchart describing the ‘Setup Neural Network Computation’ process 640 executing on slave devices 420 . The slave device 420 retrieves the following from the ‘setup neural network’ message: connectivity information for each node 210 that the slave device is responsible for (the identity of embedded devices executing the incoming nodes 213 and the outgoing nodes 214 for each node), the weights 280 for all the connections for each node that the slave device is responsible for, and the activation functions 230 for all the nodes that the slave device is responsible for. The slave device 420 then starts an ‘Execute Neural Network Computation’ process 642 that waits for all the activations 240 to arrive for each node 210 that the slave device is responsible for and then computes the activations for those nodes.

FIG. 6 ( c ) shows a flowchart describing the ‘Execute Neural Network Computation’ process 642 executing on each slave device 420 . The slave device 420 continuously loops waiting for activation messages from other slave devices executing the computation of the incoming nodes 213 of the current node. When an activation message arrives, the slave device 420 retrieves the activation 640 and the neural network node 210 for which the activation message arrived, and stores these in local memory 130 . The slave device 420 checks to see if the activations from all the starting nodes 281 connecting to the current node have arrived. If so, the slave device executes the ‘Node Computation’ process 647 for the current node 210 . If all the activations 240 have not arrived for the current node, the process continues looping waiting for more activation messages.

FIG. 6 ( d ) shows a flowchart describing the ‘Node Computation’ process 647 executing on slave devices 420 . The slave device computes the activation 240 of the current node, using the activation function 230 and the activations 240 of all the incoming nodes 213 to the current node. The slave device then sends activation messages to all the slave devices 420 that are executing the computation of the outgoing nodes 214 of the current node. If the current node is an output node 250 of the neural network, the slave device sends a ‘Computation Done’ message to the master device 410 .