TWI408600B - Conpute unit with an internal bit fifo circuit - Google Patents

Abstract

A compute unit with an internal bit FIFO circuit includes at least one data register, a lookup table, a configuration register including FIFO base address, length and read/write mode fields for configuring a portion of the lookup table as a bit FIFO circuit and a read/write pointer register responsive to an instruction having a lookup table identification field, length of bits field and register extract/deposit field for selectively transferring in a single cycle between the FIFO circuit and the data register a bit field of specified length.

Description

Computing unit with internal bit first-in first-out circuit

The present invention relates to a computing unit having an internal bit FIFO circuit.

U.S. Patent Application Serial No. 11/258,801, entitled "Improved Pipeline Digital Signal Processor (IMPROVED PIPELINED DIGITAL SIGNAL PROCESS), filed on October 26, 2005 (AD-432J). ", the case is incorporated herein by reference.

A digital signal processor is a special purpose processor that is optimized for use in digital signal processing applications, such as digital filtering, speech analysis and synthesis, or video encoding and decoding to produce a compressed bit stream. Some communication or video applications may use Huffman coding, which uses a variable length coding scheme (unlike the coding scheme using a fixed number of bits per codeword). Huffman coding minimizes the total number of bits used for codewords that occur at the highest frequency. This encoding selects the number of bits based on a known probability, such that the data bit stream is decoded when the bits in the data stream arrive. This code achieves tighter data compression because the most frequently occurring characters are short, and the occasionally occurring characters are long, with the shortest character with the highest probability of occurrence being only one bit long. Most digital signal processors are designed to manipulate data with a fixed word size (eg, 8-bit, 16-bit or 32-bit words). When the processor needs to manipulate a non-standard word size, it is typically implemented using a bit-first-in, first-out circuit that can handle any specified length bit field. One disadvantage of such a device is that it is implemented outside the computing unit. In the storage, stalls may occur whenever access is required for reading or writing. This can only be aggravated by the fact that the Data Address Generator (DAG) completes access to the extended memory. Another problem with the FIFO FIFO is that it increases the distance the signal must travel and thus limits the speed of the operating cycle.

It is therefore an object of the present invention to provide an improved computing unit having an internal bit FIFO circuit.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit that utilizes the lookup table of the computing unit to implement the bit FIFO circuit.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit that can conditionally fill and spill from an external reservoir to an external reservoir.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit with a high water mark and a low water mark to define a continuous bit stream The window of the operand.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit that is filled and removed with a 32 bit memory alignment word.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit in which filling and removal occurs on the basis of upper and lower standards.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit capable of flowing a continuous bit between an external memory and any computing unit data register in a cycle. The form transfers a specified length bit field.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit that can utilize only a portion of a lookup table and possibly more than one bit FIFO circuit in one or more lookup tables in.

It is a further object of the present invention to provide such an improved computing unit having an internal bit FIFO circuit that can be left to right (Big Endian) or right to left (Little Endian). Deposit/extract data.

The present invention achieves the following results: a one-bit FIFO can be provided internally in a computing unit by configuring a lookup table in the computing unit to define a one-bit FIFO address, Length and read/write mode, and in response to an instruction having a lookup table identification field, a bit length field, and a scratchpad extraction/storage field, using a read/write index register for A specified length bit field is selectively transferred between the FIFO circuit and the data register in a single cycle.

However, in other embodiments, the invention is not required to achieve all of these objectives and the claims are not limited to structures or methods that achieve these ends.

The invention is characterized by a computing unit having an internal bit FIFO circuit, comprising: at least one data register; a lookup table; a configuration register comprising a first in first out substrate address, a length and a read /write mode field, Used to configure a part of the lookup table as a one-bit FIFO circuit; and a read/write index register in response to having a lookup table identification field, a bit length field, and a scratchpad extraction An instruction stored in the field for selectively forwarding a specified bit length field between the first in first out circuit and the data register in a single loop.

In a preferred embodiment, the configuration register can further include a little endian/big endian mode field. Transmitting a one-bit field may include: in response to the information in the configuration register and the indicator register, and the instruction, extracting a one-bit field from the first-in first-out circuit and storing the bit field Bit in the calculation unit data register. Transferring a one-bit field may include: depositing a bit field from a data register into the bit first-in first-out circuit, and responding to the configuration register and the indicator register Information and the instructions. The extracting may include updating the read indicator in the read indicator register by the specified length in the modulo first in first out length. The depositing may include: updating the write indicator in the write index register by the specified length in the first in first out length of the module. The read/write index register may include a word address field and a bit position field for tracking the specified length. The read/write index register may further include a water mark register, the limit standard register is used to define: an upper limit standard, for which the transfer to the bit is advanced first. Out of the circuit, and must move the bit FIFO circuit to an external memory; and a lower limit standard, for which the priority is allowed to be forwarded to the bit FIFO circuit, and enabled by a contiguous bit The stream operator fills the bit FIFO from the external memory. Filling and stripping with external memory can occur in 32-bit words. The 32-bit words are Aligned memory. The lookup table can include a random access memory. The data register can be one of the calculation unit register files. The extracting may include updating the read indicator in the read indicator register and generating a lower limit standard signal if the bit remaining in the first in first out is below the lower limit criterion. The depositing may include: if the bit in the first in first out is higher than the upper limit criterion, updating the write indicator in the write indicator register and generating an upper limit standard signal. The lookup table can contain multiple bits first in, first out.

In addition to the preferred embodiments disclosed below, the invention is capable of other embodiments and of various embodiments. Therefore, it is to be understood that the application of the invention is not limited to the details of the details If an embodiment is described herein, the claim is not limited to the embodiment. In addition, its claim is not considered to be limiting unless there is clear and convincing evidence of a particular exclusion, limitation or waiver.

The digital signal processor 210 shown in FIG. 1 includes an address unit 212 having one or more digital address generators 214, 216; a control unit such as a program sequencer 218; and one or more The computing unit 220, each computing unit, includes a number of circuits, such as an arithmetic logic unit 222, a multiply/accumulator 224, and a shifter 226. There are typically two, four or more computing units in a digital signal processor. The digital signal processor is coupled to one or more memories, such as first level (L1) memory 230, via memory bus 228, including program memory 232 and data memory 234 or additional memory 236. Memory 230 may be a first order memory, which is typically very fast and relatively expensive. Memory 236 may be the third order (L3) Recalling the body, it is cheaper and slower. As the digital signal processor 210 operates at 1 GHz and higher, the operational cycle is so fast that the address unit and the computing unit require more than one cycle to complete their operation. In order to improve the overall processing power of the digital signal processor 210 and to enhance its performance, it is typically deep pipelined.

In pipelined operation, pipelined efficiency is preserved when the parallel build of chunks across all processors is between the results of previous instructions and subsequent instructions. However, if there is such a dependency, a pipeline stall may occur where the pipeline will stop and wait for the problematic instruction to complete before proceeding. For example, if a calculation result cannot be directly stored but must be used to generate an address (a correlation function can be found in the memory at the address), then the calculation unit result and data address generator There is a dependency between them that disrupts the smooth operation of the pipeline, an example will suffice.

Suppose the calculation unit calculates a result, which is an angle α, but it is a function of the angle sine α, which will be used in performing subsequent operations. The computing unit must then forward the result of the calculation to the address unit 212, and the data address generator 214 or 216 at the address unit 212 generates the correct address to extract the sine function of the angle from the memory 230 or 236 and bring it Go back and submit to the calculation unit. This delay or interruption in the pipeline wastes time. One of the digital signal processors 210 is characterized by an address unit 212 and only the address unit 212 can address the memories 230 and 236. Therefore, at any time, when the computing unit needs information from the L1 memory 230 or the L3 memory 236 to operate, the result of the calculation unit is later than when the data address generator 212 is loaded. The fact that it is effective causes pipeline operations to become delayed.

According to the present invention, in the digital signal processor 10a according to the present invention, each of the computing units 20a, 20b, 20c, 20d of FIG. 2 is provided with a local reconfigurable padding and removable random access memory array. For example, lookup table (LUT) 50a. Computing unit 28 may typically include: a multiplier 52; a number of selection circuits 54 and 56; a polynomial multiplier 58, such as for a Galois field operator; a barrel shifter 60; an arithmetic logic unit 62; an accumulator 64; and multiplexer 66 and so on. Furthermore, each computing unit includes a register file 68. The data register may be one of the calculation unit register files. Typically, when there is more than one computing unit (e.g., computing units 20a, 20b, 20c, and 20d in FIG. 3), the computing units may all share the same register file 68. Each computing unit also has its own local reconfigurable padding and stripping random access memory array (query tables 50a, 50b, 50c, and 50d). The local reconfigurable padding and removable random access memory array is small enough to fit in the conventional computing unit and can be accessed in a loop, while the local reconfigurable padding and pipetting The random access memory array is also large enough to support most applications within the computing unit without the need for external memory and causing pipeline stalls.

A computing unit with an internally configured bit-first-in first-out circuit (eg, using an internal computing unit lookup table) is suitable for both encoding operations and decoding operations. In the encoding operation, the computing unit 10 of FIG. 3A includes an arithmetic logic unit 12, one or more data registers 14 and a bit-first-in first-out 16 together with other components typically found in the computing unit. In operation, the original data or uncompressed bit stream 18 is provided on line 20 to arithmetic logic unit 12, which operates according to an algorithm (eg, H.264, Windows Media, MP3, or similar) compresses data. The compressed data is typically forwarded to the data register 14 in an operand block, such as a macroblock. Then, the data register 14 forwards the compressed data to the bit FIFO 16, and the bit FIFO 16 provides a continuous bit stream operation element (such as a video macro block) on the line 22 as the compressed bit stream. twenty four.

In addition to providing an internally configured bit FIFO 16 in computing unit 10, the present invention has the additional feature of providing an upper standard function in bit FIFO 16. During the encoding operation, if the number of bits in the bit FIFO 16 exceeds the upper limit criterion, this indicates that there is not enough space in the bit FIFO to store enough bits for encoding a complete operand ( For example, a complete macroblock), so some of the bits in the FIFO FIFO 16 must be moved to an external storage (typically an L3 level storage).

When computing unit 10 of FIG. 3B is operating in a decoding operation, a compressed bit stream 26 (such as from an L3 level storage device) is forwarded on line 28 to bit FIFO 16. These bits are passed through the data register 14 to the arithmetic logic unit 12, which decodes the data (typically in a video application) with the operands of the macroblock. Uncompressed or decoded material is then provided on line 30 as uncompressed material 32.

An additional feature of the present invention resides in the lower standard operation of the bit FIFO 16. The lower limit criterion established below the lower limit criterion cannot effectively decode the operand (eg, a macroblock) and must fill the bit first-in first-out limit from the external memory. When the number of bits in the FIFO FIFO 16 is higher than the lower limit criterion, then at least a minimum number of bits in the FIFO FIFO 16 are established to enable the macroblock or other defined operands to be solved. Code, and no delay occurred during processing.

The bit FIFO 16 of FIG. 4 is configured in lookup table 40, which may be a lookup table contained within computing unit 10, such as LUT0 50a, LUT1 50c, LUT2 50b, LUT3 50d of FIG. In addition to the arithmetic unit 12 and one or more data registers 14, the computing unit 10 also includes a one-bit FIFO configuration register 42, a read/write index register 44, and a limit standard register 46. The configuration register 42 actually configures the bit FIFO 16 in the lookup table 40. The configuration register 42 has a read/write field 48 indicating whether to read or write to the bit FIFO 16 and an endian field 50 indicating the operation bit first in first out 16 Whether the mode is to read the big end of the most significant bit from right to left, or the small end of the least significant bit from left to right. The configuration register 42 also has a field 52 for defining the length of the bit FIFO 16 in the lookup table 40, and a start address or base address 54 for defining the lookup table 40. The starting address of the bit FIFO FIFO 16. The indicator register 44 includes a write indicator 56 and a read indicator 58. The write indicator 56 of FIG. 5A includes a word address 60 and a bit position 62. The read indicator 58 also includes a one-word address field 64 and a bit position field 66. In each case, the word address indicates the address to be read and written in the first-in first-out 16 of the bit, and the bit position indicates the bit that has been designated by the read and write instructions of Figures 5B and 5C, respectively. The number of bits in the address. The read command 70 of FIG. 5B includes a one-bit FIFO identification field 72 that identifies a particular lookup table in which the FIFO FIFO has been configured; field 74, which indicates the bit to be read in field 74. The length of the element; field 76, indicating the number of bits to be stored in field 76. The write command 80 of Figure 5C also has a field 82 that identifies the bit to be written therein. The FIFO has a configured lookup table; a field 84, which specifies the length of the bit to be written in field 84; and a field 86 that identifies the bit to which the special transfer is extracted. Save.

Returning to FIG. 4, the limit standard register 46 includes an upper limit standard field 90 and a lower limit standard field 92. The upper standard field is related to the encoding operation when a store or write bit is occurring. The lower standard field is related to the decoding operation when the extraction or reading bit is occurring. The index register 44 is responsive to a read command or a write command for selective transfer from the bit FIFO circuit to the data register in a single loop or the data register is selectively transferred to the Bit FIFO circuit. The transfer of the specified bit field may mean extracting a meta field from the FIFO circuit and storing the bit field in the calculation unit data register, or storing a bit from the data register. The field is in the bit first-in first-out circuit. The extraction action or the deposit operation includes updating the read index in the read index register or the write index in the write index register by a specified length in the first in first out length of the mode, so as to appropriately track the bit first in first out 16 The state is a circular memory. That is, for example, assume that the bit FIFO 16 is a 512-bit memory. When the bit overflows 512, the bit FIFO 16 loops back to zero and begins again, as indicated by arrow 94. The word address and bit position in the indicator register of Figure 5A continuously track the data in the bit FIFO 16.

During the decoding operation, the limit standard register 46 utilizes the upper limit standard field 90 to signal that the FIFO is almost full and must be removed or unloaded from the bit FIFO 16 to the off-chip memory 100. (such as L3 level) to make space available, otherwise data overflow will occur. Lower limit in decoding operation The standard field is signaled. There is not enough data in the FIFO to process the next macroblock and must be populated from the off-chip bitstream memory 100 for FIFO, otherwise insufficient data will occur. The lower bound criterion is set to the minimum number of bits to ensure that there are enough bits to allow a complete operand (e.g., video macroblock) to be processed without delaying due to lack of sufficient data.

A graphical representation of the lower limit criteria 102 and the upper limit criteria 104 is shown in FIG. 6, where the lookup table 40 is populated from top to bottom. The location of the base address 106 and the location of the read index 108 and the location of the write index 110 are also displayed, respectively. Also shown in Figure 6 is the big endian path 112, MSB first, left to right; and the little endian path 114, LSB first, right to left. Filling and pipetting to external memory 100 preferably occurs in standard words (such as 32-bit words, and typically aligned memory), ie, in bytes (8 bits), short words (16 bits) ), word (32 bits) or double word (64 bits) to manipulate padding and padding. The lookup table 40 can be implemented using conventional random access memory devices.

The operation of the upper limit standard and the lower limit standard can be better understood with reference to Figs. 7A and 7B. In Figure 7A, there is a large number of bits 120 in the bit FIFO 16 where the write index 110 is very close to the upper limit criterion 104, at which point FIFO must be removed to avoid data overflow. In FIG. 7B, there are only a few bits 122 in the bit FIFO 16, and the read indicator 108 has barely reached the lower limit criterion, which confirms that there are enough bits 122 in the bit FIFO 16 and must be filled. FIFO for complete processing of operands (such as data video macro blocks) without delay or insufficient data.

Filled separately from the off-chip L3 level memory 100 in FIGS. 8 and 9, respectively. The operation and removal of the operation of the L3 level memory 100 outside the wafer. In the filling operation of FIG. 8, the bit FIFO 16 is filled from the off-chip L3 level memory 100 via the data register 14, and the data register 14 accepts four 8-bit bytes or a 32-bit unit. The word is forwarded to the bit FIFO 16 at the write index 110 in the available space indicated at 122. The transfer operation from the bit FIFO 16 to the external chip memory 100 occurs in Figure 9, when the data above the read index 108 is transferred to the data register 14 for transfer to the off-chip memory. 100 hours. Although the invention has been described above with reference to a single bit in a single lookup table in a single computing unit, the computing unit may have more than one configured bit FIFO; in fact, a single query in FIG. There may be more than one bit FIFO 16a, 16b in Table 40.

Although specific features of the invention are shown in some drawings and not shown in other drawings, this is merely a convenience, as each feature may be combined in accordance with any or all of the other features of the invention. The words "including", "comprising", "having", and "having" are used to be broadly understood and are not limited to any implementation. Moreover, any embodiment disclosed in this application is not to be construed as the only possible embodiment.

In addition, any amendments to this patent during the prosecution of a patent application are not a waiver of any claim made in the application as filed: those skilled in the art cannot reasonably expect to draft a claim, which may Literally, all possible equivalents are covered, many of which will be unpredictable at the time of the correction and beyond the reasonable explanation (if any) that will be abandoned, the rationale correction may take no more than one pair of equivalents The tangential relationship, and/or for many other reasons, the Applicant cannot expect to describe some insubstantial substitution of any of the appended claims.

Other embodiments will be apparent to those skilled in the art and in the claims below.

10‧‧‧Computation unit

10a‧‧‧Digital Signal Processor

12‧‧‧Arithmetic Logic Unit

14‧‧‧data register

16‧‧‧ 10,000 FIFO

16a‧‧‧元元先先出

16b‧‧‧ 10,000 FIFO

18‧‧‧Uncompressed bit stream (original data)

20‧‧‧ lines

20a‧‧‧Computation unit

20b‧‧‧Computation unit

20c‧‧‧Computation unit

20d‧‧‧Computation unit

22‧‧‧ lines

24‧‧‧Compressed bit stream

26‧‧‧Compressed bitstream from L3

28‧‧‧ lines

30‧‧‧ lines

32‧‧‧Uncompressed data

40‧‧‧Enquiry Form

42‧‧‧Configuration register

44‧‧‧Read/write indicator register

46‧‧‧Restricted standard register

48‧‧‧Read/write field

50a‧‧‧Enquiry Form

50b‧‧‧Enquiry Form

50c‧‧‧Enquiry Form

50d‧‧‧Enquiry Form

50‧‧‧End field

52‧‧‧Multiplier

52‧‧‧ fields

54‧‧‧Selection circuit

54‧‧‧Starting address or base address

56‧‧‧Selection circuit

56‧‧‧ Write indicators

58‧‧‧ Polynomial Multiplier

58‧‧‧ Reading indicators

60‧‧‧ barrel shifter

62‧‧‧Arithmetic Logic Unit

64‧‧‧ accumulator

66‧‧‧Multiplexer

68‧‧‧Scratch file

70‧‧‧Reading instructions

72‧‧‧ bit FIFO first-in-first-out identification field

74‧‧‧ field

76‧‧‧ field

80‧‧‧write instructions

82‧‧‧ field

84‧‧‧ field

86‧‧‧ field

90‧‧‧ upper limit standard field

92‧‧‧lower standard field

94‧‧‧Starting to represent the arrow

94‧‧‧Starting to represent the arrow

100‧‧‧chip memory

102‧‧‧lower standard

104‧‧‧ upper limit standard

106‧‧‧Base address

108‧‧‧ reading indicators

110‧‧‧ write indicators

112‧‧‧ Big End: MSB first, left to right

114‧‧‧Little End: LSB first, right to left

120‧‧‧ bits

122‧‧‧ bits

210‧‧‧Digital Signal Processor

212‧‧‧ address unit

214‧‧‧Digital Address Generator

216‧‧‧Digital Address Generator

218‧‧‧Program Sequencer

220‧‧‧Computation unit

222‧‧‧Arithmetic Logic Unit

224‧‧‧Multiplier/Accumulator

226‧‧‧ shifter

228‧‧‧Memory bus

230‧‧‧First Order (L1) Memory

232‧‧‧Program memory

234‧‧‧Data Memory

236‧‧‧Additional memory

1 is a simplified block diagram of a prior art digital signal processor (DSP) having an external memory and a memory bus; FIG. 2 is a calculation having multiple local reconfigurable lookup tables in accordance with the present invention. Figure 3A and 3B are simplified schematic block diagrams of an encoding and decoding system in accordance with the present invention; and Figure 4 is an internal bit advanced in the lookup table in the computing unit in accordance with the present invention. First-out schematic diagram; Figures 5A, 5B, and 5C show the field configuration of the index register, read command, and write command, respectively; Figure 6 is a diagram similar to Figure 4, illustrating the big-end and small-end options according to the present invention. The use of the lower limit standard feature and the upper limit standard feature; Figures 7A and 7B show the effects of the use and upper and lower limits, respectively.

Figures 8 and 9 respectively show the filling and removing operations between the implementation of the bit FIFO look-up table and the external storage; and Figure 10 illustrates the implementation of more than one bit FIFO in a lookup table.

10a‧‧‧Digital Signal Processor

20a‧‧‧Computation unit

20b‧‧‧Computation unit

20c‧‧‧Computation unit

20d‧‧‧Computation unit

50a‧‧‧Enquiry Form

50b‧‧‧Enquiry Form

50c‧‧‧Enquiry Form

50d‧‧‧Enquiry Form

52‧‧‧Multiplier

54‧‧‧Selection circuit

56‧‧‧Selection circuit

58‧‧‧ Polynomial Multiplier

60‧‧‧ barrel shifter

62‧‧‧Arithmetic Logic Unit

64‧‧‧ accumulator

66‧‧‧Multiplexer

68‧‧‧Scratch file

Claims (15)

A digital signal processor comprising a bit address unit, a control unit and a calculation unit, the calculation unit comprising: at least one data register; an arithmetic logic unit; a local random access memory array; a memory, comprising a first-in first-out base address field, a length field, and a read/write mode field, configured to configure a portion of the memory array as a one-bit FIFO circuit to provide or Storing a continuous bit stream operation element; and a read/write index register responsive to an instruction having a recognition field, a bit length field, and a scratchpad extraction/storage field, A bit field having one of the lengths specified in the bit length field is selectively transferred between the bit FIFO circuit and the data register in a single clock cycle. The computing unit of claim 1, wherein the configuration register further comprises a little endian/big endian mode field. According to the calculation unit of claim 1, wherein the forwarding one-bit field includes: in response to the information in the configuration register and the indicator register, and the instruction, extracting a first-in first-out circuit from the bit The bit field and store the bit field in the calculation unit data register. According to the computing unit of claim 1, wherein the forwarding of the one-bit field includes: storing a bit field from a data register into the bit first-in first-out circuit, and responding to the temporary storage in the configuration And the information in the indicator register And the order. According to the calculation unit of claim 3, the extracting comprises: updating the read indicator in the read indicator register by the specified length in the modulo first in first out length. According to the calculation unit of claim 3, wherein the storing comprises: updating the write indicator in the write index register by the specified length in the first-in first-out length of the module. The computing unit of claim 1, wherein the read/write index register includes a word address field and a bit position field for tracking the specified length. According to the calculation unit of claim 1, further comprising a limit standard register, wherein the limit standard register is used to define an upper limit standard, and for the upper limit standard, the bit first-in first-out circuit must be removed to an external The storage; and the lower limit criterion, for which the continuous bit stream operation element must be used to fill the bit first-in first-out from the external storage. According to the calculation unit of claim 1, wherein the filling and removal with an external memory occurs in a 32-bit word. The computing unit of claim 9, wherein the 32-bit words are aligned memory. The computing unit of claim 1, wherein the lookup table comprises a random access memory. The computing unit of claim 1, wherein the data register is one of the computing unit register files. According to the calculation unit of claim 8, wherein the extraction comprises: if left If the bit in the first in first out is lower than the lower limit criterion, the read indicator in the read indicator register is updated and a lower limit standard signal is generated. According to the calculation unit of claim 8, wherein the depositing includes: if the bit in the first in first out is higher than the upper limit criterion, updating the write indicator in the write index register and generating an upper limit standard signal. The computing unit of claim 1, wherein the lookup table can include a plurality of bits, first in first out.