Non-blocking, pipelined write allocates with allocate data merging in a multi-level cache system

This invention handles write request cache misses. The cache controller stores write data, sends a read request to external memory for a corresponding cache line, merges the write data with data returned from the external memory and stores merged data in the cache. The cache controller includes buffers with plural entries storing the write address, the write data, the position of the write data within a cache line and unique identification number. This stored data enables the cache controller to proceed to servicing other access requests while waiting for response from the external memory.

TECHNICAL FIELD OF THE INVENTION

The technical field of this invention is cache systems in digital data processors.

BACKGROUND OF THE INVENTION

In a multi-level cache system, write requests from a higher cache level that miss have to commit that data to the intended endpoint. These write are typically cached to improve performance. A write miss is treated like a read. Data is allocated in a cache including the write target address. When the allocated data returns it is stored in the cache. The required write then takes place in the cache. This cache line is then marked dirty.

Prior art solutions stalled the CPU and higher cache levels while this write allocate is processed. The entire cache controller stalled until the cache line had been allocated to the cache. This was highly inefficient. Because the CPU request was a write, this should have been processed without such stalls. The prior art did not pipeline write allocates. The cache controller could process only one allocate. The prior art cache controller had to wait until the allocated line was stored before writing data into the allocated cache line. In addition because this prior art committed the write data to the cache after the allocated line was written, all parity and error detection/correction information was lost. This removed soft error protection for this cache line.

SUMMARY OF THE INVENTION

This invention handles write request cache misses in a manner that does not block the cache from processing further access requests. On a write request generating a cache miss the cache controller stores write data, sends a read request to external memory for a corresponding cache line, merges the write data with data returned from the external memory and stores merged data in the cache.

The cache controller includes buffers with plural entries storing the write address, the write data, the position of the write data within a cache line and unique identification number. This stored data enables the cache controller to proceed to servicing other access requests while waiting for response from the external memory. The read response will typically be in data portions less than an entire cache line. On receipt of a data portion the cache controller determines if this portion encompasses the write data. If so, the write data is merged with this portion and stored in the proper location in the cache. If not, the portion is stored in the proper location in the cache. Upon receipt of all the return data from the external memory, the cache controller releases for reuse the corresponding buffer entries. Since the write data is merged with the newly allocated line in the buffer before being written to the cache, the amount of data being written to the cache is enough to generate parity/error correction syndrome information when the data is written. This enables soft error protection on this data

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

FIG. 1illustrates the organization of a typical digital signal processor system100to which this invention is applicable (prior art). Digital signal processor system100includes central processing unit core110. Central processing unit core110includes the data processing portion of digital signal processor system100. Central processing unit core110could be constructed as known in the art and would typically includes a register file, an integer arithmetic logic unit, an integer multiplier and program flow control units. An example of an appropriate central processing unit core is described below in conjunction withFIGS. 2 to 4.

Digital signal processor system100includes a number of cache memories.FIG. 1illustrates a pair of first level caches. Level one instruction cache (L1I)121stores instructions used by central processing unit core110. Central processing unit core110first attempts to access any instruction from level one instruction cache121. Level one data cache (L1D)123stores data used by central processing unit core110. Central processing unit core110first attempts to access any required data from level one data cache123. The two level one caches are backed by a level two unified cache (L2)130. In the event of a cache miss to level one instruction cache121or to level one data cache123, the requested instruction or data is sought from level two unified cache130. If the requested instruction or data is stored in level two unified cache130, then it is supplied to the requesting level one cache for supply to central processing unit core110. As is known in the art, the requested instruction or data may be simultaneously supplied to both the requesting cache and central processing unit core110to speed use.

Level two unified cache130is further coupled to higher level memory systems. Digital signal processor system100may be a part of a multiprocessor system. The other processors of the multiprocessor system are coupled to level two unified cache130via a transfer request bus141and a data transfer bus143. A direct memory access unit150provides the connection of digital signal processor system100to external memory161and external peripherals169.

FIG. 1illustrates several data/instruction movements within the digital signal processor system100. These include: (1) instructions move from L2 cache130to L1I cache121to fill in response to a L1I cache miss; (2) data moves from L2 cache130to L1D cache123to fill in response to a L1D cache miss; (3) data moves from L1D cache123to L2 cache130in response to a write miss in L1D cache123, in response to a L1D cache123victim eviction and in response to a snoop from L2 cache130; (4) data moves from external memory161to L2 cache130to fill in response to L2 cache miss or a direct memory access (DMA) data transfer into L2 cache130; (5) data moves from L2 cache130to external memory161in response to a L2 cache victim eviction or writeback and in response to a DMA transfer out of L2 cache130; (6) data moves from peripherals169to L2 cache130in response to a DMA transfer into L2 cache130; and (7) data moves from L2 cache130to peripherals169is response to a DMA transfer out of L2 cache130.

FIG. 2is a block diagram illustrating details of a digital signal processor integrated circuit200suitable but not essential for use in this invention (prior art). The digital signal processor integrated circuit200includes central processing unit1, which is a 32-bit eight-way VLIW pipelined processor. Central processing unit1is coupled to level one instruction cache121included in digital signal processor integrated circuit200. Digital signal processor integrated circuit200also includes level one data cache123. Digital signal processor integrated circuit200also includes peripherals4to9. These peripherals preferably include an external memory interface (EMIF)4and a direct memory access (DMA) controller5. External memory interface (EMIF)4preferably supports access to supports synchronous and asynchronous SRAM and synchronous DRAM. Direct memory access (DMA) controller5preferably provides 2-channel auto-boot loading direct memory access. These peripherals include power-down logic6. Power-down logic6preferably can halt central processing unit activity, peripheral activity, and phase lock loop (PLL) clock synchronization activity to reduce power consumption. These peripherals also include host ports7, serial ports8and programmable timers9.

Central processing unit1has a 32-bit, byte addressable address space. Internal memory on the same integrated circuit is preferably organized in a data space including level one data cache123and a program space including level one instruction cache121. When off-chip memory is used, preferably these two spaces are unified into a single memory space via the external memory interface (EMIF)4.

Level one data cache123may be internally accessed by central processing unit1via two internal ports3aand3b. Each internal port3aand3bpreferably has 32 bits of data and a 32-bit byte address reach. Level one instruction cache121may be internally accessed by central processing unit1via a single port2a. Port2aof level one instruction cache121preferably has an instruction-fetch width of 256 bits and a 30-bit word (four bytes) address, equivalent to a 32-bit byte address.

Central processing unit1includes program fetch unit10, instruction dispatch unit11, instruction decode unit12and two data paths20and30. First data path20includes four functional units designated L1 unit22, S1 unit23, M1 unit24and D1 unit25and 16 32-bit A registers forming register file21. Second data path30likewise includes four functional units designated L2 unit32, S2 unit33, M2 unit34and D2 unit35and 16 32-bit B registers forming register file31. The functional units of each data path access the corresponding register file for their operands. There are two cross paths27and37permitting access to one register in the opposite register file each pipeline stage. Central processing unit1includes control registers13, control logic14, and test logic15, emulation logic16and interrupt logic17.

Program fetch unit10, instruction dispatch unit11and instruction decode unit12recall instructions from level one instruction cache121and deliver up to eight 32-bit instructions to the functional units every instruction cycle. Processing occurs simultaneously in each of the two data paths20and30. As previously described each data path has four corresponding functional units (L, S, M and D) and a corresponding register file containing 16 32-bit registers. Each functional unit is controlled by a 32-bit instruction. The data paths are further described below. A control register file13provides the means to configure and control various processor operations.

FIG. 3illustrates the pipeline stages300of digital signal processor core110(prior art). These pipeline stages are divided into three groups: fetch group310; decode group320; and execute group330. All instructions in the instruction set flow through the fetch, decode, and execute stages of the pipeline. Fetch group310has four phases for all instructions, and decode group320has two phases for all instructions. Execute group330requires a varying number of phases depending on the type of instruction.

The fetch phases of the fetch group310are: Program address generate phase311(PG); Program address send phase312(PS); Program access ready wait stage313(PW); and Program fetch packet receive stage314(PR). Digital signal processor core110uses a fetch packet (FP) of eight instructions. All eight of the instructions proceed through fetch group310together. During PG phase311, the program address is generated in program fetch unit10. During PS phase312, this program address is sent to memory. During PW phase313, the memory read occurs. Finally during PR phase314, the fetch packet is received at CPU1.

The decode phases of decode group320are: Instruction dispatch (DP)321; and Instruction decode (DC)322. During the DP phase321, the fetch packets are split into execute packets. Execute packets consist of one or more instructions which are coded to execute in parallel. During DP phase322, the instructions in an execute packet are assigned to the appropriate functional units. Also during DC phase322, the source registers, destination registers and associated paths are decoded for the execution of the instructions in the respective functional units.

The execute phases of the execute group330are: Execute 1 (E1)331; Execute 2 (E2)332; Execute 3 (E3)333; Execute 4 (E4)334; and Execute 5 (E5)335. Different types of instructions require different numbers of these phases to complete. These phases of the pipeline play an important role in understanding the device state at CPU cycle boundaries.

During E1 phase331, the conditions for the instructions are evaluated and operands are read for all instruction types. For load and store instructions, address generation is performed and address modifications are written to a register file. For branch instructions, branch fetch packet in PG phase311is affected. For all single-cycle instructions, the results are written to a register file. All single-cycle instructions complete during the E1 phase331.

During the E2 phase332, for load instructions, the address is sent to memory. For store instructions, the address and data are sent to memory. Single-cycle instructions that saturate results set the SAT bit in the control status register (CSR) if saturation occurs. For single cycle 16 by 16 multiply instructions, the results are written to a register file. For M unit non-multiply instructions, the results are written to a register file. All ordinary multiply unit instructions complete during E2 phase322.

During E3 phase333, data memory accesses are performed. Any multiply instruction that saturates results sets the SAT bit in the control status register (CSR) if saturation occurs. Store instructions complete during the E3 phase333.

During E4 phase334, for load instructions, data is brought to the CPU boundary. For multiply extension instructions, the results are written to a register file. Multiply extension instructions complete during the E4 phase334.

During E5 phase335, load instructions write data into a register. Load instructions complete during the E5 phase335.

FIG. 4illustrates an example of the instruction coding of instructions used by digital signal processor core110(prior art). Each instruction consists of 32 bits and controls the operation of one of the eight functional units. The bit fields are defined as follows. The creg field (bits29to31) is the conditional register field. These bits identify whether the instruction is conditional and identify the predicate register. The z bit (bit28) indicates whether the predication is based upon zero or not zero in the predicate register. If z=1, the test is for equality with zero. If z=0, the test is for nonzero. The case of creg=0 and z=0 is treated as always true to allow unconditional instruction execution. The creg field is encoded in the instruction opcode as shown in Table 1.

TABLE 1ConditionalcregzRegister31302928Unconditional0000Reserved0001B0001zB1010zB2011zA1100zA2101zA0110zReserved111xNote that “z” in the z bit column refers to the zero/not zero comparison selection noted above and “x” is a don't care state. This coding can only specify a subset of the 32 registers in each register file as predicate registers. This selection was made to preserve bits in the instruction coding.

The dst field (bits23to27) specifies one of the 32 registers in the corresponding register file as the destination of the instruction results.

The scr2 field (bits18to22) specifies one of the 32 registers in the corresponding register file as the second source operand.

The scr1/cst field (bits13to17) has several meanings depending on the instruction opcode field (bits3to12). The first meaning specifies one of the 32 registers of the corresponding register file as the first operand. The second meaning is a 5-bit immediate constant. Depending on the instruction type, this is treated as an unsigned integer and zero extended to 32 bits or is treated as a signed integer and sign extended to 32 bits. Lastly, this field can specify one of the 32 registers in the opposite register file if the instruction invokes one of the register file cross paths27or37.

The opcode field (bits3to12) specifies the type of instruction and designates appropriate instruction options. A detailed explanation of this field is beyond the scope of this invention except for the instruction options detailed below.

The s bit (bit1) designates the data path20or30. If s=0, then data path20is selected. This limits the functional unit to L1 unit22, S1 unit23, M1 unit24and D1 unit25and the corresponding register file A21. Similarly, s=1 selects data path20limiting the functional unit to L2 unit32, S2 unit33, M2 unit34and D2 unit35and the corresponding register file B31.

The p bit (bit0) marks the execute packets. The p-bit determines whether the instruction executes in parallel with the following instruction. The p-bits are scanned from lower to higher address. If p=1 for the current instruction, then the next instruction executes in parallel with the current instruction. If p=0 for the current instruction, then the next instruction executes in the cycle after the current instruction. All instructions executing in parallel constitute an execute packet. An execute packet can contain up to eight instructions. Each instruction in an execute packet must use a different functional unit.

FIG. 5is a block diagram illustrating a computing system including a local memory arbiter according to an embodiment of the invention.FIG. 5illustrates system on a chip (SoC)500. SoC500includes one or more DSP cores510, SRAM/Caches520and shared memory530. SoC500is preferably formed on a common semiconductor substrate. These elements can also be implemented in separate substrates, circuit boards and packages. For example shared memory530could be implemented in a separate semiconductor substrate.FIG. 5illustrates four DSP cores510, but SoC500may include fewer or more DSP cores510.

Each DSP core510preferably includes a level one data cache such as L1 SRAM/cache512. In the preferred embodiment each L1 SRAM/cache512may be configured with selected amounts of memory directly accessible by the corresponding DSP core510(SRAM) and data cache. Each DSP core510has a corresponding level two combined cache L2 SRAM/cache520. As with L1 SRAM/cache512, each L2 SRAM/cache520is preferably configurable with selected amounts of directly accessible memory (SRAM) and data cache. Each L2 SRAM/cache520includes a prefetch unit522. Each prefetch unit522prefetchs data for the corresponding L2 SRAM/cache520based upon anticipating the needs of the corresponding DSP core510. Each DSP core510is further coupled to shared memory530. Shared memory530is usually slower and typically less expensive memory than L2 SRAM/cache520or L1 SRAM/cache510. Shared memory530typically stores program and data information shared between the DSP cores510.

In various embodiments, each DSP core510includes a corresponding local memory arbiter524for reordering memory commands in accordance with a set of reordering rules. Each local memory arbiter524arbitrates and schedules memory requests from differing streams at a local level before sending the memory requests to central memory arbiter534. A local memory arbiter524may arbitrate between more than one DSP core510. Central memory arbiter534controls memory accesses for shared memory530that are generated by differing DSP cores510that do not share a common local memory arbiter524.

FIG. 6is a further view of the digital signal processor system100of this invention. CPU110is bidirectionally connected to L1I cache121and L1D cache123. L1I cache121and L1D cache123are shown together because they are at the same level in the memory hierarchy. These level one caches are bidirectionally connected to L2130. L2 cache130is in turn bidirectionally connected to external memory161and peripherals169. External memory161and peripherals169are shown together because they are at the same level in the memory hierarchy. Data transfers into and out of L1D cache123is controlled by data memory controller (DMC)610. Data transfers into and out of L1I cache121is controlled by program memory controller (PMC)620. Data transfers into and out of L2130including both cache and directly addressable memory (SRAM) are controlled by unified memory controller (UMC)630. This application is primarily concerned with level 2 cache and UMC630.

FIG. 7illustrates buffers used in the write allocation of this invention.FIG. 7illustrates three buffer types. The left of the drawing corresponds to an internal bus to L1I cache121and L1D cache123and the right of the drawing corresponds to an external bus to external memory161.

External command buffer710is first type of buffer. External command buffer710includes plural entries711,712to719. External command buffer710holds commands from UMC630to read data in or write data out to an external endpoint. Each CPU transaction uses one entry irrespective of the size of the read/writes or whether it is an allocate or not.

FIG. 8illustrates the contents of an exemplary external command buffer entry711. External command buffer entry711holds information on the endpoint address in field811, the cache line size in field812, a unique transaction identification number in field813and other control data used by the memory interface in field814.

External write allocate buffer720is the second type buffer. External write allocate buffer720includes plural entries721,722to729. External write allocate buffer720holds the write allocate data. Write allocates operate as fire and forget. Thus write allocates are issued by UMC630, but the controller does not stall waiting for the write allocate to finish. Data from this buffer is merged with the data returned from the endpoint.

FIG. 9illustrates the contents of an exemplary external write allocate buffer entry721. External write allocate buffer entry721stores the write data that triggered the write allocate in field921. This write data is used when the allocate completes. External write allocate buffer721stores a unique transaction identification number in field922. This unique transaction identification number corresponds to the unique transaction identification number in external command buffer711for the same transaction.

Response buffer730is the third type buffer. Read response buffer730includes entries731,732to739. Read response buffer730holds information corresponding to read data returned from the endpoint. External read response buffer730does not hold the actual data, but information such as CPU address, allocate way, byte position for write allocate and the number of data phases needed by the level PMC610or DMC620.

FIG. 10illustrates the contents of an exemplary response buffer entry731. Response buffer entry731stores instructions on how to process the allocate data when it returns. This includes the cache address in field1031, the number of data bytes expected in field1032, the position of the write allocate data in field1033, a unique transaction identification number in field1034and other control information in field1035. The unique transaction identification number in field1034corresponds to the unique transaction identification number in external command buffer711for the same transaction.

In this invention a write access from the higher level cache that misses is write allocated. Write allocation recalls data corresponding to the write access for storage within the cache. Such a write allocate is a multi-step process. In the prior art a write allocate would take many cycles creating long stalls to the CPU. This invention prevents those stalls and increases the performance of write allocates.

FIG. 11is a flow chart illustrating the process of the write allocate of this invention. The process begins with a write request in block1101. This write request comes from DMC610based upon a cache miss within L1D cache123. The preferred embodiment of this invention does not support writes into L1I cache121.

Test block1102determines whether the address of this write request causes a hit within L2 cache130. If this write request generates a hit (Yes in test block1102), then this write is performed into the L2 cache123entry (block1103). This completes the write process (block1104).

If this write request does not generate a hit (No in test block1102), then block1105generates a write allocate. This requires data to be recalled from the base memory, such as external memory161, and the write performed in the cache. Block1106loads the command buffer, the write allocate data buffer and the response buffer with data corresponding to the write request. UMC630generates a unique transaction identification number to mark the corresponding entries in these buffers. The write request then creates a read allocate (block1107). UMC630transmits a read request to the endpoint such as external memory161to recall the entire cache line for storing in L2 cache130. Such a read allocate is single cycle process. All the information needed for this read allocate is stored in buffers. UMC630treats this as a fire and forget request similar to a write to the endpoint, except UMC630processes it as an allocate. UMC630having loaded the buffers with the required data is released to service other requests. Thus UMC630creates an allocate having no impact different than sending a write to the endpoint. As noted below completion of the write allocate is controlled by an autonomous state machine operating on data and parameters stored in the buffers. Thus neither CPU110nor other cache levels stall during this time. This state machine executes the following steps.

This UMC630state machine waits for return data from the external memory161as evidenced by the dashed line between blocks1107and1108. In block1108data returns from external memory161. The data size of this return data depends upon the bus connection between L2 cache130and external memory161. In particular it is generally expected that several portions of return data will be required to fill a L2 cache line. Block1108operates upon each return of a portion of this data.

When allocate data starts arriving, the state machine uses the unique transaction identification to identify the corresponding entries in the buffers. Test block1109determines if the just received return data encompasses the write data. Field1033of response buffer entry731identifies the location of the write data within the requested cache line. If the just received data encompasses the write data (Yes in test block1109), then the write data stored in the write allocate data buffer entry721field921is merged into the return data (block1110). Following this merge or if the just received data does not encompass the write data (No in test block1109), then the return data or merged return data and write data is stored in the cache (block1111). Note the response buffer entry731includes cache address data (field1031) to enable computation of the physical address of the cache.

Test block1112determines if the just received return data is the last return data. The expected data bytes field1030of response buffer entry731enables this determination. If the just received return data is the last return data (Yes at test block1112), then the write allocate process ends at block1113. The corresponding buffer entries in external command buffer710, external write allocate data buffer and response buffer703are released for reuse. If the just received return data is not the last return data (No at test block1112), then flow returns to block1108to wait for the next return data.

This invention advantageously uses write allocate data merging. In the prior art when the allocate data is committed to the cache, the cache controller would wait for it to complete and then commit the write allocate data as an additional write access to the cache. In this invention, the write data is merged at the correct byte position and written while the allocate data is being committed to the cache. This avoids an extra write at the end of the allocate. The absence of this final write operation of the prior art reduces power consumption in writing to the cache.

This invention avoids protection errors. The manner of storing the return data and the write data in the cache enables calculation of parity and/or error detection/correction bits during the write to the cache. This preserves soft error protection in the cache.

Prior art solutions stalled the CPU and higher cache levels while the write allocate processed. The entire cache controller stalled until the entire cache line had been allocated to the cache. This was highly inefficient. Because the CPU request was a write, this should have been processed without such stalls. The prior art did not pipeline write allocates. The cache controller could process only one allocate due to a lack of buffers. The prior art did not merge write allocate data. Thus the cache controller had to wait until the entire allocated line was stored and the write data was written into the allocated cache line.

The multiple buffers of this invention make it possible for the cache controller to save the command to the buffers and unstall the cache pipeline. Allocations are pipelined. The write allocate data is saved in buffers. This makes it possible for the cache controller to process multiple write allocates. Write allocate data merging avoids the extra write. These changes make it possible for the cache controller to treat the write as a single-cycle transaction and retain all the performance improvements that come with caching the write while avoiding any impact of this caching.