Patent Publication Number: US-8526294-B2

Title: Data exchange device using orthogonal vectors

Description:
This application claims priority to French patent application 09/58498, which was filed Nov. 30, 2009 and is incorporated herein by reference. 
     TECHNICAL FIELD 
     The present invention relates to a device and a method of data exchange between units of an integrated circuit, as for example occurs in microprocessors or memories. 
     BACKGROUND 
     Generally, the data exchange between units of an integrated circuit occurs between a number of initiator units and a target unit. The initiator units transmit digital messages that they code for their transmission to the target unit. 
     Prior art is described in Xin Wang et al.: “Applying CDMA Technique to Network-on-Chip”, IEEE Transactions on very large scale integration (VLSI) systems, IEEE Service Center, Piscataway, N.J., USA, Vol. 15, #10, October 2007, pages 1091-1100. In this paper, the bits of the messages to be transmitted are coded by application of a set of orthogonal vectors derived from Walsh functions, then arithmetically added for transmission. The messages do not interfere and they are decoded at the target unit level. 
     SUMMARY OF THE INVENTION 
     An advantageous feature of embodiments of the present inventor is to decrease lag (number of clock cycles necessary for the initiator units to send a bit to a target unit). Some embodiments provide the advantageous features that they decrease the silicon surface area required by prior art circuits. 
     Thus, an embodiment of the present invention provides a method for transmitting messages from first units of an integrated circuit to at least one second unit of the integrated circuit, the first units transforming first digital messages into second digital messages, the second messages of the first units being added, then transmitted to said at least one second unit. The transformation of the first messages into second messages comprises the application of an orthogonal transformation by means of vectors obtained from rows or columns of an identity matrix. 
     According to an embodiment of the present invention, a bit of a first message of rank is transformed into an n-bit word of a second message of rank i by the steps of: 
     a) transforming said bit of the first message of rank i into an intermediary n-bit word by application of a vector obtained from a row or a column of an identity matrix of rank n; 
     b) obtaining the n-bit word of the second message of rank i by replacing the bit of rank i of said intermediary word with value “0”. 
     According to an embodiment of the present invention, rank n of the identity matrix is equal to the number of first messages. 
     According to an embodiment of the present invention, for a bit b i  of the first message of rank i, with i ranging from 1 to p, the second messages comprise n bits b ij , with j ranging from 1 to n and indicating the position of bit b ij  in the second message of rank i, each bit b ij  being provided at a time t j , and wherein, for each time t j , sum S j  of bits b ij  is calculated according to expression 
               S   j     =       ∑     i   =   1       i   =   p       ⁢   bij           
and is provided to the second unit.
 
     According to an embodiment of the present invention, sums S j  are decoded in the second unit to recover bits b i  of the first messages, the decoding of sums S j  comprising the steps of: 
     a) if the first p sums S j , with j ranging from 1 to n, corresponding to first messages transmitted at the same time are all equal to “0”, defining that bits b i  of the first messages are all equal to “0”; 
     b) if the first p sums S j  are all equal and are different from zero, defining that bits b i  of the first messages are all equal to “1”; and 
     c) if the first p sums S j  do not all have the same value, defining that bit b i  of the message of rank i is equal to “0” if sum S i  is equal to the greater value of two values likely to be taken by the first p sums S j  and defining that bit b i  is equal to “1” if sum S i  is equal to the minimum value of two values likely to be taken by the first p sums S j . 
     According to an embodiment of the present invention, the transformation of the first messages into second messages comprises the implementation of an XOR operation between the bits of the first messages and the row or columns elements of the identity matrix. 
     According to an embodiment of the present invention, several vectors are assigned to a first unit and/or the assignment of one or several vectors to a first unit is modified along time. 
     According to an embodiment of the present invention, the first messages comprise several bits processed in parallel. 
     In another aspect, the present invention also provides for an integrated circuit comprising first units and at least one second unit connected to an interconnection unit. The first units are capable of providing second digital messages by a coding comprising the application of an orthogonal transformation to first messages, the orthogonal transformation being performed by means of vectors obtained from rows or columns of an identity matrix, the interconnection unit comprising at least one adder capable of adding the second messages of the first units and of transmitting second added messages to said at least one second unit. 
     According to an embodiment of the present invention, the circuit comprises means for transforming a bit of a first message of rank i into an n-bit word of a second message of rank i, 
     a) said bit of the first message of rank i being transformed into an intermediary n-bit word by application of a vector obtained from a row or a column of an identity matrix of rank n; 
     b) the bit of rank i of said intermediary word being replaced with value “0” to obtain the n-bit word of the second message of rank i. 
     According to an embodiment of the present invention, dimension n of the identity matrix is greater than or equal to number p of the first messages. 
     According to an embodiment of the present invention, the second unit comprises a decoder, the decoder comprising: 
     a) means capable of determining whether the first p sums S j , with j ranging from 1 to n, provided by the interconnection unit and corresponding to first messages transmitted at the same time, are all equal to zero; 
     b) means capable of determining whether the first p sums S j  are all equal and are different from zero; 
     c) means capable of defining that bits b i  of the first messages are all equal to “0” if the first p sums S j  are all equal to “0”; 
     d) means capable of defining that bits b i  of the first messages are all equal to “1” if the first p sums S j  are all equal and are different from zero; and, if the first p sums S j  are not all of same value, 
     e) means capable of defining that bit b i  of the message of rank i is equal to “0” if sum S i  is equal to the maximum value of two values likely to be taken by the first p sums S j , and that bit b i  of the message of rank i is equal to “1” if sum S i  is equal to the minimum value of two values likely to be taken by the first p sums S j . 
     According to an embodiment of the present invention, the means enabling to transform the first messages into second messages implement an XOR or  XOR  operation between the bits of the first messages and the row or column elements of an identity matrix. 
     According to an embodiment of the present invention, the circuit comprises a controller capable of modifying the assignment of the vectors to the first units along time and/or of assigning several vectors to a first unit. 
     According to an embodiment of the present invention, the first messages comprise several bits and the circuit comprises circuits capable of processing the bits of the first messages in parallel. 
     The foregoing objects, features, and advantages of embodiments of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a circuit for transmitting messages according to the present invention; and 
         FIG. 2  illustrates the operation of a decoder according to the present invention. 
     
    
    
     DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS 
     The present inventor has determined that the lag due to the use of orthogonal vectors originating from Walsh functions (which correspond to Hadamard matrixes) was due to two factors. 
     On the one hand, when these matrixes or functions are of order n, only n−1 vectors can be used since, due to the necessary digitization of the matrix, the first row is not linearly independent from the others and must be discarded. This results in a bandwidth loss, this loss being for example equal to 3% for n=32, or to 25% when n=4. 
     On the other hand, the dimension of the above matrixes can only be equal to an integral power of two. This results in an additional bandwidth loss which depends on the number of initiator units and may be very large. For example, if there are 16 initiator units, a matrix of order  32  must be used (due to the loss of a row, a matrix of order  16  only enables one to code  15  initiator units) and the bandwidth loss then is 50%, which is substantial. 
     In addition to minimizing, if possible at the same time, the two above-mentioned factors, embodiments of the present invention provide for a binary matrix having, on the one hand, all its lines linearly independent two by two and, on the other hand, a dimension that can better adapt to any number of initiator units. The identity matrix of order n which provides numerous advantageous features. 
       FIG. 1  shows a circuit  1  according to an embodiment of the present invention. Circuit  1  comprises a series of p initiator units, which, for simplification, will be called initiators hereafter, Init 1 , Init 2 , . . . . Init p . Each initiator Init i  is connected to a coder Cod i , with i ranging from 1 to p. Each coder Cod i  is assigned a vector derived from a row or a column of an identity matrix of order n greater than or equal to p. Each coder Cod i  is connected to an interconnection unit  10 , which is also connected to a target unit  20 . A controller  100  is connected to initiators Init i  and to target unit  20 , especially to synchronize the system and to manage data exchanges. 
     Target unit  20  comprises a decoder DEC. Target unit  20  may correspond to one or several target circuits using the same decoder. Of course, interconnection unit  10  may also be connected to several target circuits, each having a decoder. 
     Interconnection unit  10  comprises half adders ADD 2 , . . . ADD p . Adder ADD 2  has an input connected to coder Cod 1  and an input connected to coder Cod 2 . The output of adder ADD 2  is connected to an input of adder ADD 3 , not shown, having its other input connected to the coder of rank  3 . Generally, except for the first one, adder ADD i  of rank i has its inputs connected to the coder of rank i and to the adder of rank i−1. The output of adder ADD i  is connected to an input of the adder of rank i+1, except for the last one, of rank p, having its output connected to target unit  20 . 
     A first operating mode of the circuit of  FIG. 1  will now be detailed, assuming that the messages provided by the initiators only have one bit and that the dimension of the identity matrix is equal to number p of the initiators. 
     Initiator Init 1  thus provides a bit b 1  to coder Cod 1  and initiator Init i , of rank i, with i ranging from 1 to p, provides a bit b i  to coder Cod i . 
     Coder Cod 1  transforms bit b 1  into a word m 1  of p bits b 11 , b 12 , . . . b 1p  by means of a vector derived from a row or a column of the identity matrix of order p. The same occurs for any coder Cod i  which, from a bit b i , provides a word m i  of p bits b ij , with j ranging from 1 to p. For example, coder Cod i  performs an XOR logic operation between bit b i  and each of the elements of the row of rank i of the matrix. 
     Each of bits b ij  is provided to the output of coder Cod i  at each clock cycle, that is, bits b i1  are output from their respective coder at time t 1 , bits b ij  being provided at time t j . 
     In interconnection unit  10 , bits b ij  are arithmetically added at each clock cycle, that is, at time t j , the interconnection unit calculates sum S j  of all bits b ij  provided by coders Cod i . Sum S j  is provided to the decoder of target unit  20 . Of course, sum S j  is calculated by means of adders ADD 2 , ADD p , but it should be understood that any other architecture enabling calculation of sum S j  is within the contemplated scope of the present invention. 
     The decoder of unit  20  thus receives, from time t 1  to time t p , a set of p sums S j . Sums S j  are decoded to recover the transmitted messages, which is possible with no ambiguity since the vectors used in the coding are orthogonal. Once decoded, the transmitted messages are conveyed towards the corresponding target unit(s). 
     Among the advantages of the method according to described embodiments of the present invention described hereabove, it should be noted that the use of the identity matrix enables significant improvement to the system bandwidth. 
     By comparison, the binary matrixes based on Walsh functions are only pseudo-orthogonal and, hence, one of their rows cannot be used to code a message. On the contrary, the identity matrix directly is an orthogonal binary matrix, and all the vectors originating from its rows or columns may be used to code messages. The resulting bandwidth gain for example is 2% for a matrix of order  64 . 
     On the other hand, the dimension of a matrix based on Walsh functions can only be equal to a power of 2. Thus, dimension  32  comes after dimension  16  and so, in the prior art, 32 clock pulses are necessary in all cases to transmit a number of messages ranging between 16 and 31. By contrast, the identity matrix may have any dimension, including an odd dimension, which can exactly adapt to the number of initiators. The bandwidth gain is here very large, since it may reach 50%. 
     Of course, the above-described operating mode may have several alterations without departing from the scope of the present invention. 
     For example, it should be understood that an initiator may be adapted to deliver several messages simultaneously, several rows of the identity matrix being assigned to the initiator. 
     The dimension of the identity matrix is not necessarily equal to the number of initiators or to the number of messages that can be transmitted at the same time. Generally, it is sufficient for the identity matrix to have a dimension greater than or equal to the maximum number of messages likely to be transmitted at the same time. 
     Also, when the messages provided by the initiators comprise several bits, the bits may be processed in parallel as described hereabove. 
     Further, the elements of the orthogonal vectors derived from the rows or columns of the identity matrix do not necessarily correspond to the elements of the identity matrix. For example, the elements of the used vectors may correspond to the inverses of the elements of the identity matrix, to a linear combination of rows (or columns) of the identity matrix, or to any other transformation which does not alter the orthogonality. 
     Also, an operator other than XOR may be used to obtain word m i  from bit b i . For example, the  XOR  function may be used, provided to accordingly modify the decoding algorithm. 
     A second embodiment of the circuit of  FIG. 1  will now be described, wherein, as compared with the first mode, the words provided by the coders do not correspond to the direct application of a vector derived from the identity matrix. 
     First, as in the first mode, each coder Cod i , with i ranging from 1 to p, applies a row or a column of the identity matrix of rank p to bit b i  of the message of rank i to transform it into a p-bit word m i . Word m i  is formed of bits b ij , with j ranging from 1 to p. Preferably, to obtain word m i , coder Cod i  performs an XOR logic operation between bit b i  and each of the elements of a row of the identity matrix of dimension p. The used row or column of the identity matrix may be but is not necessarily of rank i. 
     The present inventor has then noted that if the bit of rank i of word m i  is replaced with value “0”, the possible values likely to be taken by the various sums S j , with j ranging from 1 to p, are limited. Indeed, in this case, either all sums S j  are equal, and they can then only have value “0” or value “p−1”, or they are not all equal, and they can then only have one of two consecutive analog values N or N−1. 
     Thus, in the second embodiment of the circuit of  FIG. 1 , the p-bit word m i  obtained by application of a row or column of the identity matrix to bit b i  is an intermediary word which is modified into a p-bit word M i . The modification comprises replacing the bit of rank i of word m i  with value “0”, word M i  further corresponding to word m i . 
     Words M i  are provided to interconnection unit  10 , where they are added to form sums S j  transmitted to the decoder of target unit  20 . 
     Due to the forcing to “0” of the bits of rank i, the decoder is simplified, as will be seen hereafter in relation with  FIG. 2 . 
       FIG. 2  illustrates a decoding algorithm that can be used by the decoder of target unit  20 . As seen previously, along times t 1  to t p , the decoder receives a set p of sums S 1 , S 2  . . . S p . 
     At step  200 , the decoder examines whether all sums S j , with j ranging from 1 to p, are identical. 
     If so, the decoder examines at step  210  whether sums S j  are all zero. 
     If sums S j  are all zero, this means that all the transmitted bits correspond to value “0”, which is indicated in  FIG. 2  at step  220 . 
     If all sums S j  are equal but are different from zero, this indicates that all the transmitted bits correspond to value “1” (step  230 ). As can be seen, although, in this case, the value of each of sums S j  is known to be equal to p−1, the decoder need not determine this value to decode the transmitted messages. As a result, the decoder is simplified. 
     If at step  200 , the answer is no, the method proceeds to step  250 . 
     At step  250 , the decoder determines in any fashion whether a sum of rank i, S i , is equal to N or to N−1. If sum S i  is equal to N, bit b i  has value “0”. If sum S i  is equal to N−1, bit b i  has value “1”. Here again, the value of N, which ranges between 1 and p−1, matters little and the decoder need not know it or determine it to define bits b i . 
     Thus, in  FIG. 2 , based on any sum S i , the decoder determines at step  250  whether there exists a sum S k , with k ranging from 1 to p, which is greater than sum S i . If such is the case, sum S i  corresponds to value N−1 and bit b i  is equal to “1” (step  260 ); otherwise, bit b i  is equal to “0” (step  270 ). The transmitted messages are thus decoded after examination of all sums, without requiring the determination of the values of the sums. 
     Accordingly, the second operating mode of the circuit of  FIG. 1  enables greatly simplifying the decoder, which may be formed by simple comparators, which results in a significant gain in silicon surface area efficiency. 
     Further, less data are required by the decoder, since they come down to four states for sums S j . As a result, the bus which connects interconnection unit  10  to target unit  20  may have a decreased number of rows, which further decreases the used silicon surface area. 
     Of course, as in the case of the first embodiment, the second operating mode may be modified without departing from the scope of the present invention. 
     Thus, an initiator may provide several simultaneous messages. In this case, several rows or columns of the identity matrix are assigned to this initiator and the coder associated with this initiator is capable of delivering the coded words corresponding to these messages. 
     Additionally, when the messages provided by the initiators comprise several bits, the bits may be processed in parallel, each bit being processed as described hereabove. 
     Also, the dimension of the identity matrix may be greater than the number of transmitted messages. For example, assume that the identity matrix is of dimension n and the number of messages is equal to a number p smaller than n. As previously described, bit b i  of the message of rank i is coded by application of a row or of a column, for example, the row of rank i, of the matrix, after which the bit of rank i of the obtained word is forced to “0” before transmission to interconnection unit  10 . In this case, at the decoding, only the first p sums S j  are to be considered, the sums of rank p+1 to n being useless to recover the value of the transmitted bits. 
     However, preferably, the rank of the matrix is adapted to the number of transmitted messages, to decrease the system lag. This may be provided for at the level of controller  100  which, in its management of the system, can adapt the matrix dimension to the number of transmitted messages. 
     It should be noted that the method according to the present invention is very flexible and is able to adapt to various situations. 
     For example, if an initiator wants to send several messages simultaneously, the controller can assign as many vectors thereto as there are messages to be sent. These vectors may be borrowed from other initiators which do not hold the priority. They can also be created by increasing the size of the matrix. 
     Also, the controller can modify the assignment of the vector(s) assigned to an initiator over time. 
     Generally, it should be noted that, in the described embodiments of the present invention, interconnection unit  10  comprises no conditional logic elements, which simplifies the device. Further, any electronic device comprising a circuit according to the present invention or implementing a method according to the present invention of course is within the scope of the present invention. 
     Specific embodiments of the present invention have been described hereabove, as well as different variations. It should be noted that those skilled in the art may combine various elements of these various embodiments and/or variations without showing any inventive step. 
     Of course, the present invention is likely to have various alterations, modifications, and improvements which will readily occur to those skilled in the art. Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the present invention. Accordingly, the foregoing description is by way of example only and is not intended to be limiting. The present invention is limited only as defined in the following claims and the equivalents thereto.