Data transmission method

p00001Data transmission method

p000025 The present invention relates to a method and apparatus of data transmission.

p00003Conventional computer networks typically support two modes of communication. A first mode of communication is one-to-one communication. In this case, a message is transported from a single source to a signal destination. A second mode of communication is broadcast communication. In this case the message is transported from a single source to all other elements connected to a network.

p00004In neural systems of interconnected neurons, neurons usually have very high connectivity to each other. It is often the case that a given neuron accepts data from others between 1,000 and 10,000 neurons, and takes data from a similar number of neurons. None of the two communication modes described above

p00005fifteen It is ideally suited to neural systems. If one-to-one communication is used, a large number of messages need to be sent. Specifically, if a neuron is going to transmit data to another 1,000 neurons, 1,000 messages would be required. If a broadcast communication is used, a message will be transmitted to all other neurons. This is again undesirable, since messages will be sent to more destinations than necessary, and valuable bandwidth will be wasted.

p00006Instead, a multicast communication mechanism would be preferable. In multicast communication, a message is transmitted from a single source to multiple receivers, but not all possible receivers. PCT Patent Application No. WO 03/036503 describes a routing system that uses a Layer 2 switch that interconnects several routers to intelligently redirect multicast packets through a

p0000725 Internet exchange that transports multicast content. European Patent Application Publication No. 0410568 describes a multidimensional, multi-nodal routing mechanism for retransmitting information from one node to another node using a header consisting of the bits of the route descriptor. Multicast communication is particularly attractive in neural systems, although current multicast communication techniques are not ideally suited for neural applications.

p00008It is an objective of the present invention to obviate or mitigate at least some of the problems outlined above.

p00009In accordance with the present invention, a method of data transmission between a plurality of interconnected elements is provided, the method comprising: receiving a message from a first element,

p0001035 said message comprising a routing key, processing said routing key to identify a plurality of said interconnected elements; and transmitting the data to said identified plurality of interconnected elements, wherein the processing of said routing key comprises attempting to locate a routing word by performing a search operation using said routing key and said search operation comprises comparing the routing key with the keys associated with the respective routing words, the routing key comprising a plurality of bits, using only some of the plurality of bits for at least some of the comparisons, determining the bits of the routing key to be used for a comparison that is determined for each key based on a respective mask associated with the key, said plurality of said interconnected elements using said routing word.

p00011Four. Five Thus, the invention provides a method of data transmission in which the elements to which data is transmitted are selected based on a routing key received within a message. For example, the routing key may take the form of an identifier of an element that transmits the message, and in such circumstances the identity of the element that transmits the message is therefore used to determine the elements to which the data is transmitted. .

p00012The data transmitted to the identified plurality of interconnected elements may comprise the message received. Indeed, the transmitted data may be identical for the received message. The received message may comprise a payload of data. However, it will be noted that in the neural embodiments of the invention,

p0001355 The received message usually contains only one routing key that is considered to be a neuronal "spike" and therefore no additional data is required.

p00014The identified plurality of interconnected elements can then be selected using the routing word. If the attempt is unsatisfactory, the default data can then be used to determine the elements to which the data is transmitted. Specifically, at least one interconnected element can be identified using the default data.

p00015The routing word can have one bit for each of the connected elements, and the status of a respective bit can determine whether the data is communicated to one of the interconnected elements. That is, where the method of data transmission is performed on an element connected to N additional elements, a routing word of N bits can be used, each bit representing one of the N elements. Search operation

p00016You can understand comparing the routing key with the keys associated with the respective routing words. The routing key may comprise a plurality of bits, and any subset of these bits can be used in at least some of the comparison operations. The bits to be used can be determined for each of the keys independently. That is, each of the keys can have a

p000175 associated mask that is used to ensure that only certain bits of the routing key are used in the search operation. The mask can be combined with the routing key using a bit-oriented logic Y operation.

p00018In preferred embodiments of the invention, the first element and the identified plurality of interconnected elements 10 are connected to a second element, and the method is performed on the second element.

p00019The above method can be implemented in hardware.

p00020The invention further provides a data carrier that carries a program code readable by

p00021fifteen Computer configured to cause a computer to perform the methods shown above. Also provided is a computer apparatus comprising a program memory that stores the instructions readable by the computer and a processor configured to read and execute the instructions stored in the program memory. Processor-readable instructions comprise instructions that control the processor to perform a method as shown above.

p00022twenty In accordance with a further aspect of the present invention, an apparatus for data transmission between a plurality of interconnected elements is provided. The apparatus comprises means for receiving a message from the first element, the message comprising a routing key, means for processing the routing key to identify a plurality of interconnected elements trying to locate a word of

p0002325 routing by performing a search operation using said routing key, said plurality of interconnected elements being identified using said routing word and means for transmitting data to the identified plurality of interconnected elements.

p00024The invention also provides an apparatus for the transmission of data between a plurality of elements.

p0002530 interconnected, the device comprising: a receiver interface configured to receive a message from a first element, said message comprising a routing key, a processor configured to identify a plurality of said interconnected elements using said routing key trying to locate a routing word by performing a search operation using said routing key, said plurality of said interconnected elements being identified using said routing word, and one

p0002635 transmitter interface configured to transmit data to said identified plurality of interconnected elements.

p00027Preferably, the apparatus comprises an associative memory in communication with a RAM. Data stored in associative memory can be used to identify the plurality of interconnected elements. Having used said associative memory in this mode, a word of

p0002840 Routing in RAM.

p00029A further aspect of the invention provides a network of interconnected elements, the networks being configured to transmit data to each other. Each element comprises a router, and the router is configured to: receive a message from a first element, the message comprising a routing key, process the

p00030Four. Five routing key to identify a plurality of interconnected elements attempting to locate a routing word by performing a search operation using said routing key, said plurality of interconnected elements being identified using said routing word, and transmitting the data to the identified plurality of interconnected elements .

p00031fifty The embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

p00032Figure 1 is a schematic illustration of a network of interconnected elements in which the present invention can be implemented;

p0003355 Figure 2 is a schematic illustration showing the operation of a router included in one of the elements of Figure 1;

p00034Figure 3 is a schematic illustration of a search table used by the router of Figure 2;

p0003560 Figure 4 is a schematic illustration of a routing key used in connection with the search table of Figure 3;

p00036Figure 5 is a schematic illustration showing the structure of the router of Figure 2 in greater detail; Figure 6 is a schematic illustration showing the structure of the router of Figure 5 in additional detail; and

p00037Figure 7 is a schematic illustration of a possible architecture for the elements of Figure 1.

p000385 Referring first to Figure 1, sixteen interconnected elements that are part of a larger network are illustrated. You can see that each of the elements is connected to its eight closest neighbors by direct communications links. Each of the elements in Figure 1 is configured to receive a message from any of its interconnected elements and to generate data to transmit to one or more of the elements to which it is connected.

p00039The transmission of data between interconnected elements is managed by routers included within each of the interconnected elements. Routers operate by processing a routing key received within a message, and determine from this routing key to which of the elements should be transmitted.

p00040fifteen data. For example, in preferred embodiments of the invention this routing key comprises an identifier of the element that transmits the message. This identifier is processed to identify the elements to which the data should be transmitted. This is schematically illustrated in Figure 2. In this it can be seen that a router 1 receives an identifier 2 from an originating element 3. Router 1 processes identifier 2 to identify three destination elements 4, 5, 6. Once the destination elements 4, 5, 6 have been identified, router 1 then transmits the data in the form of appropriate messages to the elements of destination 4, 5 6. Thus, the routing of the data by the router 1 is determined by the identifier 2 of the originating element 3 from which the router 1 receives a message.

p00041Router 1 performs routing operations using a routing table of the type shown

p0004225 schematically in Figure 3. The table comprises a plurality of search keys 7, against which the received identifier 2 is compared. If the received identifier matches one of the keys 7, the corresponding routing word 8 is retrieved and used to determine the appropriate elements to which the data should be transmitted. Each of the routing words 8 is a binary number that has a predetermined number of bits each bit representing a link to another element. That is, in the example of Figure 1, each of the routing words is an 8-bit number, the eight bits representing the eight communication links of each element. It will be appreciated however that in many embodiments of the invention, each of the elements will have more than eight communication links, and therefore each of the routing words will comprise more bits. If a particular bit of the routing word is set to '1' it indicates that the data on the communications link represented by that bit should be transmitted. Conversely, if a bit

p0004335 Particular of the routing word is set to '0', this indicates that the data should not be transmitted over the communications link represented by that bit.

p00044Routing as described above allows multicast communication effectively in which the element from which the message is received determines the elements to which the data is transmitted. However, when a very large network of interconnected elements is used, the routing table shown in Figure 3 will be very large. Thus, when each of the elements in Figure 1 is implemented as a single chip, it may be impossible or at least very expensive to set the routing table on the chip. Therefore various optimizations are possible. For example, it should be noted that the routing table included in a router in any network element needs to include only the entries for the keys that are associated with

p00045Four. Five Identifiers whose routes from their origin to all their destinations pass through that element, are generated in it or end in it.

p00046Additionally or as an alternative, each of the elements can implement a default routing in the event that the search table in Figure 3 fails to provide a match for a particular identifier. For example, when an identifier included within a message does not match any of the keys in the table in Figure 3, the data can simply be transmitted to a single element on the link diametrically opposite to that from which the message is received.

p00047Further; often you will need to handle groups of message identifiers in the same way. That is, the

p0004855 Messages received from a plurality of elements may all need to generate data transmissions to the same set of elements within the network. This can be achieved by effectively ignoring some bits of the message identifier when the search operation is performed. That is, some bits of the message identifier are treated as "does not matter" bits in the search operation. An embodiment using such bits "does not matter" is now described with reference to Figure 4.

p00049Referring to Figure 4, a sixteen bit routing key is illustrated. The sixteen bits form three logical components. A first component 9 comprises two bits indicating that the sixteen bits together represent routing data of a particular type. In one embodiment these bits have a value '00' when the routing table of Figure 3 is to be used to effect multicast communication, as described above. The values ​​'01', '10' and '11' are used respectively to indicate a one-to-one routing in which the remaining fourteen bits represent an address to which the data should be transmitted, a routing

p00050broadcast in which the remaining fourteen bits are not required, and some other routing algorithm implemented by the router.

p00051The second and third components 10, 11 of the routing key are used, when the first component

p000525 has the value '00' to perform the routing by performing a search operation using the search table of Figure 3. However, in the described embodiment of the invention, only the six bits constituting the second component 10 are used in the search operation, the remaining eight bits constituting the third component 11 that is ignored for routing purposes on the present router. That is, only the bits of the second component 10 determine the elements to which the data is transmitted using the bits of the third component 11 to determine an additional routing when appropriate to an additional element in the network. The bits of the third component 11 can be partially processed using a more detailed search table in the subsequent elements in the network, or they can be processed alternatively by software in such subsequent elements.

p00053fifteen It can be seen that optimizing the routing table in Figure 3 to take into account only the second component 10 (and not the third component 11) when performing routing operations, provides considerable benefits. In this relatively small example, a routing table that would otherwise need 16,384 entries (that is 214) instead requires 64 entries (this is 26).

p00054In the illustration of Figure 4, it can be seen that six adjacent bits form the second component 10, while 8 adjacent bits form the third component 11. There is no need for these second and third components to be formed from adjacent bits . For example, it could be decided that the 12 most significant bits of the second component 11 can also be ignored when search operations are performed. In that case, the 12 most significant bits will become part of the third component 11, and will not be

p0005525 would use during search operations. Similarly, it may be that a bit 13 needs to be considered in search operations, and therefore, bit 13 would become part of the second component 10. This is, in general terms, to reduce the size of the routing table, only some bits of the identifier are taken into account and the bits that are taken into account and those that are not taken into account can be located anywhere within the routing key.

p00056The router 1 comprising the search table of Figure 3 is now described in additional detail. It should be noted that in general terms, the router is an associative memory (content - address), with a programmable masking on the basis of each entry as well as correctly processing the second and third components 10, 11 of a routing key as has been previously described. This associative memory

p0005735 It connects to a conventional memory that maintains the routing words used to perform routing operations. Associative memory can be implemented using any conventional technique such as VLSI CAM cells or a fingerprint-directed RAM.

p00058The structure of the router is now described with reference to Figures 5 and 6. Referring to Figure 5, as described above, it can be seen that router 3 comprises an associative memory 14 and search RAM 15. In general terms a Routing key of the type described above is presented to associative memory as indicated by an arrow 16. The associative memory then performs a search operation comparing each of the keys of the associative memory with the routing key presented. The success or failure generated by this operation is taken by the associative memory as indicated by the

p00059Four. Five arrow 17. If a success is generated, an appropriate routing word is obtained from the search RAM 15 and is output as indicated by an arrow 18.

p00060The structure of router 1 and its operation is now described in additional detail with reference to Figure 6, which illustrates two entries of associative memory 14 and two corresponding entries of the search RAM

p00061fifteen. A first entry of the associative memory comprises a mask 19, a mask control 20, a key 21 and a comparator 22. A routing key (for example, the identifier of a source element as discussed above) is provided as it is indicated by arrow 18 that is passed to mask control 20, together with mask 19. The mask control 20 is a collection of Y-gates that perform a bit-oriented Y operation between the routing key provided and the mask 19.

p0006255 The mask 19 is configured so that it correctly handles the "does not matter" bits of the routing key. For example, if the routing key has the form shown in Figure 4, where the fourteen least significant bits form an operative part of the routing key, then the fourteen bits of the mask of the form 11111100000000 are provided. It can be seen that performing the bit-oriented logical operation Y between this mask and the routing key of Figure 4 will preserve the status of the six most significant bits of the routing key of the operative part, while setting the eight bits less significant to "0". Ensuring that the key 21 also has its eight least significant bits at '0' this effectively implements the desired "no matter" policy.

p0006365 The result of the bit-oriented operation Y performed by the mask control 20 is taken to comparator 22 together with the key 21 associated with that associative memory input. If the comparison is satisfactory, the routing data 23 stored in the search RAM 15 and associated with the described input of the associative memory are read and extracted as indicated by arrow 18.

p00064The above description of Figure 6 has referred to a single entry of associative memory 14 and an entry

p000655 associated with the search RAM 15. An additional input of the associative memory 14 comprising a mask 19a, a mask control 20a, a key 21 and a comparator 22a are also shown in Figure 6. However, it will be appreciated that the associative memory will in practice contain a large number of additional entries that have the same structure. It can be seen from Figure 6 that if any of the comparators 22, 22a generates a success, its output is passed to an OR gate 24, which generates the success / failure data as indicated by arrow 17. That is, if there is a satisfactory comparison, the respective comparator passes a '1' to the OR gate 24, and therefore the output 17 to '1' will indicate a success. If none of the comparator outputs output a '1', the output of the OR 24 gate will be '0'. The success / failure output indicated by arrow 17 can be used to activate the default routing behavior in the event of failure, as described above.

p00066fifteen The above description of Figures 5 and 6 has referred to the location of the appropriate data for a particular routing key. It will be appreciated that before such processing can be performed, the associative memory must be properly configured as well as store the appropriate data. Such a process is now described, first of all with reference to Figure 5. In general, the control signals indicated by arrows 25a, 25b indicate whether a key or mask will be written in the associative memory and the appropriate data are presented below as indicated by arrow 26. The data presented is written to a address of associative memory 14 determined by the address data indicated by arrow 27. The address data indicated by arrow 27 further identifies an entry of the search RAM 18, meaning that an appropriate control signal indicated by an arrow 28 can be provided to allow the data (in the form of a routing word) indicated by arrow 29 are written in search RAM 15.

p0006725 The writing arrangement of Figure 5 is shown in additional detail in Figure 6. In this it can be seen that the address indicated by arrow 27 is passed to a decoder of the writing address 30 which selects an appropriate memory entry associative 14. Each of the elements of associative memory 14 receives control signals indicated by 25a, 25b, 25c, 25d to indicate whether the key data or mask data will be written. The data to be written is then provided to an appropriate element of associative memory that is provided as indicated by arrow 26, and is stored in any element of associative memory that is currently enabled for writing.

p00068It can also be seen from Figure 6 that the decoder of the write address 30 selects a

p0006935 element of the search RAM 18 to which the routing data provided will be written as indicated by arrows 29.

p00070In Figure 6, the router is shown to have a unique decoder of the write address for both associative memory 14 and search RAM 15. This is not necessarily the case. For example, since in the case of a hit, exactly one of the comparators will generate a bit for the routing key presented, the collective output of the comparators will be a code 1 of N (that is, exactly it will be set to '1' one bit with the N - 1 bits set to '0'). This N code 1 can then be used to direct the search RAM 15 in an efficient manner.

p00071Four. Five Referring again to Figure 6, it should be noted that the provision of a mask for each of the associative memory entries allows different "no matter" policies to be implemented for the different associative memory entries. In alternative embodiments of the invention, a single "no matter" policy can be applied to all entries in associative memory. In such embodiments a single mask is stored and passed to the mask controls of all inputs.

p00072The above description refers to a router that routes data between elements in a network of interconnected elements. However, the invention is also applicable to routing within the elements. For example, referring now to Figure 7, a structure suitable for one of the elements shown in Figure 1 is shown. It can be seen that in addition to the router 1, the illustrated element comprises a monitor processor 31 that is responsible for the overall management of the element. Additionally, an interface of the receiver 32 is provided for each of the communications links along which the messages are received (that is, eight interfaces of the receiver will be provided on each of the network elements of Figure 1). The interfaces of the receiver 32 pass the data to an arbitrator 33 who is responsible for presenting the messages received from the interfaces of the receiver 32 to the router 1. The order in which the messages are passed to the router is determined by the arbitrator 33, but Since messages are routed independently, the order in which messages are passed is of little significance. Router 1 then performs routing in the manner described above., Routing the data to any of the fascicle processors 34 within the element or to the interfaces of the transmitter 35. It should be noted that each of the fascicle processors 34 is configured to implement a plurality of neurons (known as a beam) that are part of a neural network. However, processors 34 may take another suitable form, and do not need to implement a plurality of neurons. A transmitter interface 35 is provided for each of the links in

p00073communications on which data can be transmitted (that is, eight transmitter interfaces will be provided on each of the network elements of Figure 1). In this way, it can be seen that router 1 routes the data both to the processors within the illustrated element and also to other elements within the network. Fascicle processors 34 can generate messages that are handled by router 1 in the same way as

p000745 the messages of the interconnected elements are received.

p00075The routing and communication methods according to the present invention have particular applicability in neuronal systems in which neurons communicate with each other. Such systems require efficient multicast communication of the type provided by the present invention. Such systems can be implemented using elements that have the form shown in Figure 7, where each of the fascicle processors 34 included within each of the elements implements a plurality of neurons as described above. It will be appreciated that in such circumstance each of the neurons may have a respective identifier. These neuron identifiers can then be used as routing keys. Indeed, it will be appreciated that routing keys can take any convenient form. That is, the keys

p00076fifteen Routing can take the form of neuron identifiers, processors or elements. In fact, in alternative embodiments of the invention, other routing keys are used.

p00077It will be appreciated that the routing tables used in the embodiments of the present invention should be defined. Routing tables can be configured using external software. For example, in neural implementations of the invention, the lists of neural networks that describe the interconnections of neurons are provided, and the neurons are then mapped onto processors to determine the entries in the routing table. This is a process similar to the FPGA configuration. Resource restrictions such as routing table size and bandwidth limitations must be taken into account during the mapping process. When an appropriate routing table is generated, it can be written below.

p0007825 using a method as described with reference to Figure 6.

p00079For static applications, the routing table is fixed. However, it is possible to allow local processors to modify routing tables while the system is running. This allows development processes to be modeled, for example in neuron-based systems. Changes to tables

p0008030 Routing during the operation of the system must, of course, be carried out with care to ensure that the desired routings are always obtained.

p00081Preferred embodiments of the present invention have been described above. It will be appreciated however that various modifications can be made to such embodiments without departing from the scope of the invention, as

p0008235 defined by the appended claims. For example, the invention has been described so that an identifier of an element from which a message emanates is used to determine routing. This is not necessarily the case. The element from which the message emanates can provide any suitable data within the message to be used as the routing key in the search operation.

p0008340 Additionally, the illustration in Figure 1 shows a two-dimensional arrangement of elements in which each of the elements is connected to eight of its closest neighbors. It will be appreciated, however, that many other configurations are possible. For example, three-dimensional arrangements can be used, and indeed, in a network in which each element has eight connections, a four-dimensional hypercube interconnect fabric can be used.