Interconnect coding method and apparatus

A computer program that is embodied on a storage medium for execution on a processor is provided. With this computer program, A current cost is calculated for each transition on a bus having a predetermined width for a functional circuit so as to form a transition cost matrix. Then, a predetermined number of the lowest cost transitions for from the transition cost matrix is determined so as to generate a probability transition matrix. The product of the probability transition matrix and the transition cost matrix can be iteratively determined, while also updating the probability transition matrix until the probability transition matrix converges.

TECHNICAL FIELD

The invention relates generally to encoding and, more particularly, to encoding data to reduce the cost for transitions on a bus.

BACKGROUND

Turning toFIG. 1, an example of a conventional communication system100can be seen. As shown, this system generally comprises functional circuits102-1and102-2that communicate with one another over a communication channel (which generally includes codes104-1and104-2, transceivers106-1and106-2, and bus108). When transmitting data across a bus108, transitions between cycles can be costly in terms of power consumption, so the codecs104-1and104-2are employed to reduce current consumption associated with these transitions. For example, if it assumed that the bus108is 4 bits wide, an transition from “0000” to “1111” is much more costly than a transition from “0000” to “0001.” Thus, to avoid the costly transitions, codecs104-1and104-2employ what is known as “invert codes,” which introduces an extra bit to the bus108to indicate an inverse. For example, as shown inFIG. 1, bus108is 4 bits wide with an extra invert bit (effectively making the bus1085 bits wide). In this example, when there is a transition from “0000” to “1111,” the invert bit is toggled to “1” so that the bus transmits “10000.” By using the invert bit, it allows the number of transitions to be limited to 3 (instead of 4) with a 4-bit bus.

While this “invert code” system (i.e., system100) can reduce the peak current by up to 50% and reduce energy consumption by up to 30%, there are some drawbacks. Namely, these systems are also less than optimal in savings related to peak current and energy consumption. Thus, there is a need for an improved system.

SUMMARY

An embodiment of the present invention, accordingly, provides an apparatus. The apparatus comprises a functional circuit; and a codec that is coupled to the functional circuit, wherein the codec includes: a buffer that is configured to receive transmission data from the functional circuit and to provide reception data to the functional circuit; a lookup table (LUT) having a probability transition matrix for encoding and decoding, wherein the probability transition matrix is a transition pattern encoded matrix based on a transition cost matrix corresponding to an average current cost for the functional circuit that is substantially minimized over a plurality of transitions; and a controller that is coupled to the buffer, that is to configured to encode the transmission data using the LUT to generate encoded transmission data, and that is configured to decode encoded reception data using the LUT.

In accordance with an embodiment of the present invention, the buffer further comprises a first buffer, and wherein the codec further comprises a second buffer that is coupled to the controller, that is configured to receive the encoded reception data, and that is configured to transmit encoded transmission data.

In accordance with an embodiment of the present invention, the apparatus further comprises transceiver that is coupled to the second buffer.

In accordance with an embodiment of the present invention, the apparatus further comprises a bus that is coupled to the transceiver.

In accordance with an embodiment of the present invention, the probability transition matrix, when calculated, is iteratively updated in response to the product of the probability transition matrix and the transition cost matrix until the probability transition matrix converges.

In accordance with an embodiment of the present invention, a computer program that is embodied on a storage medium for execution on a processor is provided. The computer program comprises the steps of: calculating a current cost for each transition on a bus having a predetermined width for a functional circuit so as to form a transition cost matrix; determining a predetermined number of the lowest cost transitions for from the transition cost matrix so as to generate a probability transition matrix; iteratively determining the product of the probability transition matrix and the transition cost matrix and updating the probability transition matrix until the probability transition matrix converges.

In accordance with an embodiment of the present invention, the predetermined number is 2m, wherein m is an information width.

In accordance with an embodiment of the present invention, the step of determining the predetermined number of the lowest cost transitions further comprises forming the probability transition matrix is formed by assigning input probabilities in as ascending order of cost to descending order of probability.

In accordance with an embodiment of the present invention, the step of iteratively determining the product further comprises determining the Hadamard product of the probability transition matrix and the transition cost matrix for each iteration.

In accordance with an embodiment of the present invention, the step of calculating the current cost for each transition further comprises calculating an average so as to determine an average current.

In accordance with an embodiment of the present invention, the step of calculating the current cost for each transition further comprises calculating a maximum so as to determine a peak current.

DETAILED DESCRIPTION

Turning toFIG. 2, an example of a communication system200in accordance with an embodiment of the present invention can be seen. The communication system200is similar to system except that codec104-1and104-2and bus108have been replaced with codecs202-1and202-2and bus204. Instead of using an invert code (as codecs104-1and104-2employ), codecs202-1and202-2use probability transition matrices that are transition pattern encoded matrixes based on a transition cost matrix corresponding to a cost function (i.e., an average current cost) for the respective functional circuit102-1or102-2that is substantially minimized over a several transitions. In other words, codecs202-1and202-2uses encoding and decoding tables or matrices that reduce peak currents and energy consumption over large numbers of cycles (where transitions occur between cycles).

To do this, the codecs202-1and202-2(which can be seen in greater detail inFIG. 2and which are referred to hereinafter as202) employ a logic operations on incoming data (i.e., transmission data from functional circuit102or encoded receive data from transceiver106). Buffers302and306are used as temporary storage for data that allow data to be encoded or decoded by controller304, which uses lookup table (LUT)208. Generally, for encoding, the encoded transmission data e[i] (which is represented by the model shown inFIG. 4) can be:
e[i]=F(t[i],e[i−1])  (1)
where F is the encode function and t[i] is the transmission data. As shown, this encoding function uses the data t[i] (which has an information width of m) and the previous or delayed encoded transmission data e[i−1] (which has as a width n that is equal to that of bus204and is greater than the information width m). For decoding, the reception data r[i] (which can be represented by the model shown inFIG. 5) can be:
r[i]=G(e[i],e[i−1])  (2)
where G is the decode function and is generally the inverse of encode function F.

Looking to the encode function F, in particular, it can be represented by a transition pattern matrix (or, simply, transition matrix)T, which can be written as:

T__=[ti,j]i,j=12n⁢⁢where(3)ti,j={10(4)
with the valid transitions being represented as “1” and invalid as “0.” Each row of this transition matrixThas 2mnon-zero elements, and, if the input has a distribution, the transition matrixTcan be represented as a probability transition matrixP, where each entry corresponds to a probability value within the distribution and where all rows will sum to 1. For a uniform distribution, probability transition matrixPis:

P__=12m⁢T__(5)
As an example, if a (2,1) TPC code (where the information width m is 2 and the bus width n is 3) is employed, there are eight code words w1to w8(as shown in the transition diagram ofFIG. 3) that result in the following probability transition matrixP:

P__=14⁡[1100100111010001101100101101000111001001110011001010001111010001](6)
In order to take advantage of the probability transition matrixP, there are several features to compensate for with the bus204, namely, peak current and energy consumption. This problem can be though of as an optimization process for probability transition matrixP, where the theoretically optimized matrixPOPT is:

Turning first to energy consumption (or average current) optimization, α is set equal to 0 so that equation (7) becomes:

P__OPT=arg⁢⁢m⁢inP∈{TPC}⁢Iavg,bus.(8)
Assuming a stationary ergodic input process, the TPC can be assumed to be a first order homogenous Markov process, which allows the average current Iavg,busto be:

Iavg,bus=limN→∞⁢1N⁢∑i=1N⁢CIavg⁡(e⁡[i-1],e⁡[i])_,(9)
where CIavg(e[i−1],e[i]) is that average current cost of a transition from e[i−1] to e[i]. With an initial probability of p(0),CIavg(e[i−1],e[i])can be expressed as:

CIavg⁡(e⁡[i-1],e⁡[i])_=p⁡(0)⁢Pi-1⁡(P__·CIavg__)⁢1_,(10)
where1is an all−1 column vector,CIavgis average current cost matrix, and • denotes the Hadamard product. Convergence of the average current Iavg,busin equation (9) implies that equation (10) converges, and, it can be observed that:

limN→∞⁢Pi=X__=XP__=PX__(11)
Thus,Xconsists of the left and right eigenvectors of probability transition matrixPwhich correspond to an eigenvalue of 1. Since the row sum for probability transition matrixPis 1, then the right eigenvector that corresponds to eigenvalue 1 is column vector1. This means thatXis the outer product of the left and right eigenvectors, yielding:

To be able to optimize the tree (shown inFIG. 7) should be “pruned.” This “pruning” is performed iteratively using a transition cost matrixCtranuntil the probability transition matrixPconverges. A diagrammatic example of “pruning” can be seen inFIG. 8, and a flow chart depicting a method for performing this “pruning” can be seen inFIG. 9. Initially, the running cost vectorCrun(which is a column vector whose k-th component indicates the accumulated cost of the k-th state) is initialized with a column vector0in step402, and the row and column indices are initialized in step403. Once initialized, the transition cost matrixCtranis calculated by calculating the transitions costs in step406or each column (as set forth in steps405and410) and within each row (as set forth in steps404and416) and updating the transition cost matrixCtranin step408. Preferably, the transition cost matrixCtranis updated in step408by averaging the calculated cost with a cost from the column of the running cost vectorCrun. While the transition cost matrixCtranis calculated, the lowest predetermined number (which is generally related to the information width m and which is generally 2m) of lowest cost transitions in transition cost matrixCtranare identified in step412. This is usual performed at after calculations for each row of transition cost matrixCtranso as to allow the corresponding row in probability transition matrixPto be populated in step414. Once completed for each row, the running cost vectorCrunis updated in step418, and, in step419, a determination is made (based on a previous iteration) as to whether the probability transition matrixPhas converged. If not, the process begins again in step403, and, if probability transition matrixPhas converged, the average current Iavg,busis determined in step420. Typically, the average current Iavg,busis determined by use of equation (11) with the probability transition matrixPand the transition cost matrixCtran.

With the average current Iavg,bushaving been generally resolved, the focus can be turned to determining peak current optimization. For peak current, α is set equal to 1 so that equation (7) becomes:

⁢P__OPT=arg⁢⁢m⁢inP∈{TPC}⁢Ipeak,bus.
For computation of the peak current Ipeak,bus, the algorithm is similar to that used for the average current Iavg,bus(which is described above), except that computation of the cost (i.e., step406) is slightly difference. As shown in the example tree diagram ofFIG. 10, peak current is generally a maximum, which is usually equivalent to the maximization operation. As no averaging is employed (i.e., step408), the cost propagation is also generally a maximum, rather than the average of the surviving branches.

Due to the similarities in the algorithms, calculation for the average current Iavg,busand the peak current Ipeak,buscan be performed at the same time. To perform joint optimization among the average current Iavg,busand the peak current Ipeak,bus(for any value of α), the tree optimization algorithm can be further modified to propagate a cost vector v=(Cavg;Cpeak). Each element of the cost vector v is computed using the same methods described above. However, the cost that is calculated to perform branch pruning is defined by the cost function f as follows:
f(Cavg;Cpeak)=αCpeak+(1−α)Cavg.  (15)
The cost function f need not be limited to the weight sum expression in equation (15), and can be any generic function. Preferably, (as described above in step412), the pruning would be also performed by identifying the 2mlowest transitions. Further generalization of joint optimization is also possible by increasing the dimensions of v and implementing a suitable cost function f. For example, delay could be incorporated by using cost vector v and cost function f. Additionally, these calculations (due to complexity) cannot be calculated “by hand” but instead are computed by a processor or computer using software (which is embodied on a storage medium). This processor and memory can either be separate from or included within controller304.

The performance of this methodology compared to an uncoded bus and bus invert coded bus is given inFIGS. 11 and 12. It can be seen that a is a suitable variable for balancing the optimization between the average current Iavg,busand the peak current Ipeak,bus. This coding scheme provides up to 70% reduction in peak current and 15% savings in energy compared to an uncoded bus, and 30% reduction in peak current and 7% savings in energy compared to a bus invert coded bus. Also, the shift of balance between peak current optimization or energy optimization can be seen depending on the value of α, where α=1 is peak current only optimization and α=0 is energy only optimization.