Abstract:
A method and apparatus for direct mapping in a compute unit having an internal random access memory the primary operational sequences of an algorithm to related function including storing in an internal random access memory at least one predetermined direct mapped function value for each primary operational sequence of an algorithm; holding in an input data register the address in the random access memory of at least one mapped function value for a selected primary operational sequence of the algorithm and holding in an output register the at least one mapped function value for the selected primary operational sequence of the algorithm read out of the random access memory.

Description:
RELATED APPLICATIONS 
       [0001]    This application claims benefit of and priority to (AD-473) U.S. patent application Ser. No. 11/527,001 filed Sep. 26, 2006, entitled ITERATIVE PROCESS WITH ROTATED ARCHITECTURE FOR REDUCED PIPELINE DEPENDENCY, by Wilson et al. and (AD-432J) U.S. patent application Ser. No. 11/258,801, filed, Oct. 26, 2005, entitled PIPELINED DIGITAL SIGNAL PROCESSOR, by Wilson et al. which are incorporated herein in their entirety by this reference. 
     
    
     FIELD OF THE INVENTION 
       [0002]    This invention relates to a method of mapping the primary operational sequence or sequences of an algorithm to an internal look-up table in a compute unit. 
       BACKGROUND OF THE INVENTION 
       [0003]    In a pipelined machine if an instruction is dependent on the result of another one, a pipeline stall will happen where the pipeline will stop, waiting for the offending instruction to finish before resuming work. This is especially a problem in iterative arithmetic coding processes such as JPEG2000, JPEG, On2, and in H.264 Context-based Adaptive Binary Arithmetic Coding (CABAC). For example H.264 CABAC is based on the principle of recursive interval subdivision. [For a full description of the H264 CABAC standards and details see ITU-T Series H: Audiovisual and Multimedia Systems Infrastructure of audiovisual—coding of moving video] Given a probability estimation p( 0 ) and p( 1 )=1-p( 0 ) of a binary decision (0,1), an initially given interval or range will be subdivided into two sub-intervals having a range*p( 0 ) and range-range*p( 0 ), respectively. Depending on the decision, the corresponding sub-interval will be chosen as the new code interval, and a binary code string pointing to that interval will present the sequence of binary decisions. It is useful to distinguish between the most probable symbol (MPS) and the least probable symbol (LPS), so that binary decisions are identified as either MPS or LPS, rather then 0 or 1. According to H.264 CABAC process the range and state are used to access a two dimensional look-up table to determine the rLPS (range of least probable symbol). Current range is derived from the rLPS and the previous range. If the code offset (Value) is less than the current range, the Most probable path is taken where the most probable symbol (MPS) is designated as the next output bit, and the state transition is preformed based on the most probable symbol (MPS) look-up table. If Value is greater than current range, the Least probable path is taken where the MPS bit is inverted, the current Value is determined from the previous Value and the range then rLPS is assigned to range. Following this, if the state equals zero, the MPS is inverted. The next state transition is derived from the LPS state table based on the current state, followed by the renormalization process where the range is then renormalized to the [511,256] interval. This is done by left-shifting range the required amount of bits. Value must be left shifted the same amount of bits. Value bits that are shifted out constitute the output of the arithmetic coder. The problem with the normalization procedure is that some times a carry bit is produced during the Value updating. This carry bit can propagate to parts of the code that have been already issued. Thus, the outstanding bits mechanism is implemented so that output bit is suspended until it is clear that future carry bits will not propagate to already-emitted parts of the code. Basically, any bit with a value ‘0’ will stop the carry propagation. The aforesaid routines and algorithms, as well as many others require a great deal of computation and are vulnerable to pipeline stall. Yet in this and many other algorithms, there are preferred paths or most probable solutions or primary operational sequences of operation which require numerous cycles of operation to accomplish yet whose output is fairly predictable. 
       BRIEF SUMMARY OF THE INVENTION 
       [0004]    It is therefore an object of this invention to provide an improved method and apparatus for mapping the primary operational sequence(s) of an algorithm to an internal compute unit Random Access Memory look-up table. 
         [0005]    It is a further object of this invention to provide such an improved method and apparatus for mapping the primary operational sequence(s) of an algorithm to an internal compute unit Random Access Memory look-up table which has improved efficiency and performance especially in pipelined machines. 
         [0006]    It is a further object of this invention to provide such an improved method and apparatus for mapping the primary operational sequence(s) of an algorithm to an internal compute unit Random Access Memory look-up table which requires less power. 
         [0007]    It is a further object of this invention to provide such an improved method and apparatus for mapping the primary operational sequence(s) of an algorithm to an internal compute unit look-up table which allows reuse of the look-up table for different algorithms. 
         [0008]    It is a further object of this invention to provide such an improved method and apparatus for mapping the primary operational sequence(s) of an algorithm to an internal compute unit Random Access Memory look-up table which increases system flexibility and enables “soft” solutions, i.e., without dedicated hardware. 
         [0009]    The invention results from the realization that an improved, faster, more efficient method and apparatus for performing an algorithm can be achieved, with a compute unit having an internal random access memory, by providing in the random access memory a look-up table for storing at least one predetermined direct mapped function value for each primary operational sequence of an algorithm (e.g. H.264 CABAC encoder normalization), addressing from an input data register at least one mapped function value for the selected primary operational sequence of the algorithm and holding the at least one mapped functional value read out of the random access memory look-up table. 
         [0010]    The subject invention, however, in other embodiments, need not achieve all these objectives and the claims hereof should not be limited to structures or methods capable of achieving these objectives. 
         [0011]    This invention features in a compute unit having an internal random access memory, for providing within the compute unit direct mapping of the primary operational sequences of an algorithm to related function including storing in an internal random access memory at least one predetermined mapped function value for each primary operational sequence of an algorithm and holding in an input data register the address in the random access memory of at least one mapped function value for a selected primary operational sequence of the algorithm. An output register holds the at least one mapped function value for the selected primary operational sequence of the algorithm read out of the random access memory. 
         [0012]    The invention also features a compute unit having an internal random access memory for mapping the primary operational sequences of an algorithm. There is an internal random access memory for storing at least one predetermined direct mapped function value for each primary operational sequence of an algorithm. There is an input data register for holding the address in the random access memory of at least one mapped function value for a selected primary operational sequence of the algorithm and an output register for holding the at least one mapped function value for the selected primary operational sequence of the algorithm read out of the random access memory. 
         [0013]    In a preferred embodiment the algorithm may include an H.264 CABAC encode normalization process. The input data register may be one of the compute unit register file. The output register may be one of the compute unit register file. The input data register may have a range number of normalization bits field, number of outstanding bits field, and value MSB bit field. The output register may have a value MSP bit field, new outstanding bit field, number of bits to write to FIFO field and value of bits to write to FIFO field. The output data register may include a plurality of fields. The random access memory may include a value MSB function, number of outstanding bits, number of bits to write to FIFO, and the bit stream sequence. The succession of addresses in the input data register may not be dependent on each other. The random access memory may include a look-up table. The algorithm may include H.264 CABAC decode process. The random access memory look up table may include an rLPS, MPS State and a valid flag mapping functions. The input data register may include a state, range and value fields. The output register may include an rLPs, MPS-State and a valid field. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0014]    Other objects, features and advantages will occur to those skilled in the art from the following description of a preferred embodiment and the accompanying drawings, in which: 
           [0015]      FIG. 1  is a schematic block diagram of a compute unit configured to implement the method and apparatus of this invention; 
           [0016]      FIG. 2  is a schematic block diagram of a compute unit configured to perform variable length decoding according to the method and apparatus of this invention; 
           [0017]      FIG. 3  is a schematic block diagram of a compute unit configured to perform H.264 CABAC encoder normalization according to the method and apparatus of this invention; 
           [0018]      FIG. 4  is a schematic block diagram of an encoder portion of the H.264 CABAC algorithm; 
           [0019]      FIG. 5  is a flow chart of the normalization process of  FIG. 4 ; 
           [0020]      FIG. 6  is an illustration of the operation of the input data register, look-up table and output register implementing the H.264 CABAC encoder normalization process by mapping the primary operational sequences of that algorithm according to the method and apparatus of this invention; 
           [0021]      FIG. 7  is a flow chart of the H.264 CABAC encoder normalization process carried out by mapping the primary operational sequences of the algorithm according to the method and apparatus of this invention; 
           [0022]      FIG. 8  is a view similar to  FIG. 6  for CABAC decode; 
           [0023]      FIGS. 9 and 10  are graphical representations of the probability of occurrence of the number of outstanding bits and number of normalization bits, respectively, in an H.264 CABAC encode normalization process; and 
           [0024]      FIG. 11  is a schematic block diagram of a compute with internal random access memory look-up table configured to implement the method and apparatus of this invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]    Aside from the preferred embodiment or embodiments disclosed below, this invention is capable of other embodiments and of being practiced or being carried out in various ways. Thus, it is to be understood that the invention is not limited in its application to the details of construction and the arrangements of components set forth in the following description or illustrated in the drawings. If only one embodiment is described herein, the claims hereof are not to be limited to that embodiment. Moreover, the claims hereof are not to be read restrictively unless there is clear and convincing evidence manifesting a certain exclusion, restriction, or disclaimer. 
         [0026]    There is shown in  FIG. 1 . a portion of the compute unit  10  including an internal random access memory  12  which includes a look-up table  14  of mapped function values for each primary operational sequence of an algorithm. There is an input data register  16  which includes a number of fields  18  which provide an address on line  20  to preselected map functions in look-up table  14  of random access memory  12 . The one or more map functions are read out on line  22  to output register  24  which itself contains a number of fields  26 . 
         [0027]    The invention may be used in a Variable Length Decoding (VLD) application,  FIG. 2 , where the field providing the address  18   a  comprises  n  bits from the bit stream which are delivered over line  20   a  to the variable length decoding map functions in look-up table  14   a  of random access memory  12   a.  These functions stored in look-up table  14   a  are the most frequently occurring operations in the variable length decoding algorithm. The output on line  22   a  read out from the look-up table  14   a.  may be one of the following options if in the  n input bits  a symbol was present, the output register will take the form of  24   a,  where the MSB is set to ‘1’ to mark a symbol present, a shift field that defines how much to advance the bit stream pointer and the actual symbol field. Otherwise, if the VLD symbol is longer then  n , the output register will take the form of  25   a,  where the MSB is ‘0’ to mark a fraction of a symbol and the other field is a pointer to the beginning of the next parsing table address 
         [0028]    In another embodiment,  FIG. 3 , the primary operational sequence or the most frequently occurring operations is directed to an H.264 CABAC encoded normalization process. In that case, input register  16   b  includes three fields, the 2 LSB of normalization value field (the amount of left shifting required to put range in the [511,256] interval)  18 - 1 , the 2 LSB of ebits bits field (the number of suspended (outstanding) bits)  18 - 2 , and a 3 value most significant bit field  18 - 3 . In this embodiment the compute unit random access memory  12   b  holds in its look-up  14   b  the traditional CABAC encode mapping functions and the output register  24   b  includes four fields,  26 - 1  which contains the MSB of value,  26 - 2  which contains the new or updated number of outstanding ebits,  26 - 3  which contains the number of bits to write to the bit stream FIFO, and  264  which contains the values of the bit stream to be written to the FIFO. 
         [0029]    In a typical H.264 CABAC encoder there is context modeling and updating  30 ,  FIG. 4 , followed by the arithmetic decoder  32  after which the range is left-shifted or renormalized to the [511,256] interval. Value  34  must be left shifted the same amount of bits. Value bits that are shifted out constitute the output of the arithmetic coder, which then provide the bit stream to the bit packer  36 . Some times a carry bit is produced during the Value updating. This carry bit can propagate to parts of the code that have been already issued. Thus, the normalization process has a mechanism that can suspend an output bit or bits (outstanding bits) form being written to the bit stream FIFO until it is clear that future carry bits will not propagate to already-emitted parts of the code. Further explanation of the CABAC protocols in operation is contained in (AD-473) U.S. patent application Ser. No. 11/527,001 filed Sep. 26, 2006, entitled ITERATIVE PROCESS WITH ROTATED ARCHITECTURE FOR REDUCED PIPELINE DEPENDENCY, by Wilson et al. herein incorporated in its entirety by this reference. 
         [0030]    The normalization process is shown in greater detail in  FIG. 5 , where first the inquiry is made as to whether the range is less than 256,  40 . If the answer is no, the routine is done  42 . However, if the answer is yes, the range is less than 256 and the next inquiry is whether the value is less than 256,  43 . If it is, then a zero followed by outstanding bits of ones are written out to the bit stream FIFO, and outstanding bits counter is reset to zero  44 ; if it is not, further inquiry is made as to whether it is greater than 512,  46 . If it is greater than 512, then 512 is subtracted from the value  48  and a one followed by outstanding bits of zeros are written out to the bit stream FIFO, and outstanding counter is reset to zero  50 . If the value is not greater than 512, that is, it is between 256 and 512 then the value is reduced by 256 and the outstanding counter is incremented by one,  52  which suspends this output bits (outstanding) form being written to the bit stream FIFO until it is clear that future carry bits will not propagate to already-emitted parts of the code. All in keeping with the h.264 CABAC encode protocols. Finally the value and range are shifted left once  54  effecting a multiply by two operation. 
         [0031]    In accordance with this invention,  FIG. 6 , the data register inputs: normalization two LSB  18 - 1 , outstanding two LSB ebits  18 - 2 , and three MSB of value  18 - 3  are combined together to delivered on line  20   b  as an address to random access memory  12   b  to access the values in look-up table  14   b  corresponding to that address which map that input directly to the output. The addressed field value MSB  26 ′- 1 , number of ebits  26 ′- 2 , number of bits to write to FIFO  26 ′- 3  and the value or bit stream to write to FIFO  26 ′- 4  are read out where they appear in data register in fields  26 - 1 ,  26 - 2 ,  26 - 3 ,  26 - 4 . By using this direct mapping method the final result is obtained much more quickly and efficiently as can be seen by comparing the flow chart in  FIG. 5  with that in  FIG. 7 . 
         [0032]    In this normalization process  34   a,    FIG. 7 , accomplished by mapping the primary operational sequences or most probable solutions or preferred paths, the flow chart of  FIG. 5  can be shortcut so that it takes the form of normalization process  34   a,    FIG. 7 . There an inquiry is made as to whether the two LSB of the normalization value is greater than 2 and the number of outstanding bits (ebits) is greater than 2. If the answer is yes, the bit by bit normalization process  34   FIG. 5  is preformed  62  and the routine is done  64 . If they are not greater than two then the CABAC normalization look-up table method  63  is used and the particular combination of normalization ebits and value MSBs are used to access the information in the LUT. This again renders the write bit stream FIFO the length of the code to be written and the code value  64  then the value is updated according to the value MSB field retuned from the LUT  66  after which the operation is complete in far fewer steps then previously as indicated in  FIG. 5 . 
         [0033]    In another embodiment, CABAC decode can be implemented,  FIG. 8 , using random access memory  12   b  with the CABAC decode look-up table which now contains the CABAC look-up table  70 . Now the fields in input data register  16   b  are state  72 , range  74  and value  76  that combine to form an address which on line  20   b  accesses the proper map direct to the solution representing the direct solution containing the rLPS fields  78 , the (Most Probable Symbol) MPS-State field  80 , and the valid flag  82  which are deposited in the proper fields  84 ,  86  and  88 , respectively of output register  24   b.    
         [0034]    A determination is made of what particular values to store in the look-up table of the random access memory. The greater the number of values stored in the look-up table in the random access memory, the faster the system can operate and the less vulnerable it is to pipeline stall. However, the more values stored in the random access memory the larger it has to be and the more expensive and more usurptive of space on the chip it becomes. The optimum preferred path or most probable solutions or primary operational sequences that are to be shortcutted through the direct mapping technique is determined by considering the probability of occurrence of the number of outstanding bits,  FIG. 9 , and the number of normalization bits,  FIG. 10 . 
         [0035]    In  FIG. 9  it can be seen that the number of outstanding bits or ebits, that is the number of undetermined bits per one determined bit is highest at two and fairly high at three and four by just dealing with the first two conditions, one and two in  FIG. 9 . The size and cost of the internal random access memory contained on the compute unit and the increased speed and decreased vulnerability to pipeline stall can be balanced. The number of normalization bits or number of shifts to normalize,  FIG. 10 , can be seen as highest at one and decreasing to zero at eight, a consequence of the fact that there are only eight bits to consider. Thus, again by concentrating the primary operational sequence based on the first two in  FIG. 10  results in the best balance between size and cost of compute unit internal random access memory and pipeline stall vulnerability. Further discussion of the probability considerations is contained in (AD-432J) U.S. patent application Ser. No. 11/258,801, filed, Oct. 26, 2005, entitled PIPELINED DIGITAL SIGNAL PROCESSOR, by Wilson et al. which is incorporated herein in its entirety by this reference. 
         [0036]    Each compute unit  10   c,    FIG. 11  is provided with a local internal random access memory  100  containing a lookup table (LUT)  102 . Compute unit  10   c  typically may include multiplier  104 , a number of select circuits  106  and  108 , a polynomial multiplier  110 , such as for Galois field operations, barrel shifter  112 , arithmetic logic unit  114 , accumulator  116 , and mux  118  among other things. Also, each compute unit includes a register file  120 . Typically when there is more than one compute unit, they may all share the same register file  120 . Each compute unit also has its own local internal random access memory containing a LUT. These local internal random access memory arrays are small enough to fit in conventional compute units and to be accessible in one cycle, yet they are large enough to support most applications internally of the compute unit without having to go to external memory and bringing about pipeline stall. 
         [0037]    Although specific features of the invention are shown in some drawings and not in others, this is for convenience only as each feature may be combined with any or all of the other features in accordance with the invention. The words “including”, “comprising”, “having”, and “with” as used herein are to be interpreted broadly and comprehensively and are not limited to any physical interconnection. Moreover, any embodiments disclosed in the subject application are not to be taken as the only possible embodiments. 
         [0038]    In addition, any amendment presented during the prosecution of the patent application for this patent is not a disclaimer of any claim element presented in the application as filed: those skilled in the art cannot reasonably be expected to draft a claim that would literally encompass all possible equivalents, many equivalents will be unforeseeable at the time of the amendment and are beyond a fair interpretation of what is to be surrendered (if anything), the rationale underlying the amendment may bear no more than a tangential relation to many equivalents, and/or there are many other reasons the applicant can not be expected to describe certain insubstantial substitutes for any claim element amended. 
         [0039]    Other embodiments will occur to those skilled in the art and are within the following claims.