Efficient cache allocation by optimizing size and order of allocate commands based on bytes required by CPU

This invention is a data processing system having a multi-level cache system. The multi-level cache system includes at least first level cache and a second level cache. Upon a cache miss in both the at least one first level cache and the second level cache the data processing system evicts and allocates a cache line within the second level cache. The data processing system determine from the miss address whether the request falls within a low half or a high half of the allocated cache line. The data processing system first requests data from external memory of the miss half cache line. Upon receipt data is supplied to the at least one first level cache and the CPU. The data processing system then requests data from external memory for the other half of the second level cache line.

TECHNICAL FIELD OF THE INVENTION

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

BACKGROUND OF THE INVENTION

Digital data processors to which this invention is applicable employ a two-level memory subsystem. There are level one memories which cache and a level two memory which includes directly addressable RAM, cache or both. The RAM of the level two memory can be cached in level one All cache allocates (level one data, level one instruction and level two) are processed by a level two controller to direct memory access (DMA) controller with interfaces with the peripheral which supplied the data. The level two cache line size is preferably 128 bytes. Because this data is to be brought from an external peripheral, this data transfer can take a long time. The number of cycles needed to fetch this data affects the total amount of time that the level two controller is busy. This affects the performance of the level two controller. The latency of this fetch and the order in which data returns directly affects the stalls visible to the CPU and the performance of the system.

SUMMARY OF THE INVENTION

The at least one first level cache can include an instruction cache and a data cache. In the preferred embodiment lines of the instruction cache are ½ N bits, lines of the data cache are N bit, lines of the second level cache are 2N bits and fetches from external memory are N bits.

For an instruction fetch, half of the first received data from external memory is stored in an allocated instruction cache line simultaneously with supply of the instruction to the central processing unit. For a load instruction, the first received data from external memory is stored in an allocated data cache line simultaneously with supply of the load data to the central processing unit. For a store instruction, the first received data from external memory is stored in an allocated data cache line and the write completes in the allocated cache line.

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 timers 9.

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.
Note 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 cores510. 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 the preferred cache line sizes for L1I cache121, L1D cache123and L2 cache130. In the preferred embodiment of this invention L2 cache line size is 128 bytes, the L1D cache line size is 64 bytes and L1I cache line size is 32 bytes.FIG. 7illustrates cache lines line 0711, line 1712, line 2713and line 3714of L1I cache121. Each cache line711,712,712and714includes 32 bytes. These four cache lines total 128 bytes.FIG. 7illustrates cache lines line 0721and line 1722of L1D cache123. Each cache line721and722includes 64 bytes. These two cache lines total 128 bytes.FIG. 7illustrates cache line731of L2 cache130. This cache line is 128 bytes.

Previous generations of TMS320C6000 family of digital signal processors the two-level memory hierarchy sent a single external request for the entire cache line. The requested data was returned in address order. CPU110may stall depending on where the requested data was in the cache line.

UMC630fetches the allocated cache line from an external source. In this invention UMC630optimizes this fetch by fetching the data that CPU110needs first. In case of an instruction fetch, the UMC630splits the cache line fetch request into two parts. The first part includes the 64 bytes that contain the bytes that CPU110needs. The second part includes the remaining bytes of the line of the L2 cache130. In case of loads or stores that cause write allocations, the first external request by UMC630is for the bytes that CPU110needs. This corresponds to the missed L1D cache line. The second external request is for the other half of the L2 cache line. The data that CPU110needs is thus returned to CPU110via the corresponding cache as soon as it arrives. Other data to fill the L2 cache line is accumulated. This unstalls CPU110. Thus while UMC630remains busy receiving the rest of the 12 cache line, CPU110does not stall.

FIGS. 8A and 8Btogether illustrate the process of a CPU110instruction fetch. Block801is the instruction fetch. PMC620determines whether this fetch is a hit in L1I121in test block802. If this instruction fetch is a hit (Yes in instruction block802), then PMC620supplies the fetched instruction(s) from L1I cache121to CPU110at block803. This ends the instruction fetch process at block804.

If this instruction fetch is a miss in L1I cache121(No in test block802), then PMC620evicts and allocates an L1I cache line in block805. In the preferred embodiment L1I cache121is direct mapped. This means that data from external memory161can reside in only one cache line in L1I cache121. This line corresponds to the address generating the cache miss. Thus PMC620evicts and allocates this line in L1I cache121. The preferred embodiment does not support writes into L1I cache121. Thus this evicted and allocated cache line cannot be dirty and no data needs to be written back.

In test block806UMC630determines whether the instruction fetch is a hit in L2 cache130. If this instruction fetch is a hit in L2 cache130(Yes in test block806), then UMC630supplies the requested cache line to L1I cache121in block807. PMC620stores this just supplied data into the allocated line (block808) and supplies the fetched instruction(s) to CPU110(block803). It is known in the art that storing this received data in the cache and supplying data to CPU110can occur in parallel. This ends the instruction fetch process at block804.

If this instruction fetch is a miss in L2 cache130(No in test block806), then UMC630evicts and allocates an L2 cache line in block809. In the preferred embodiment L2 cache130is four way set associative. Thus any address from an external source may alias into one of four cache lines or ways. UMC630determines which of these cache ways to evict. In accordance with the preferred embodiment of this invention, the evicted way is the least recently used way. Data can be written to within L2 cache130and thus can be dirty. Also as part of block809, UMC630determines whether the way to be evicted is dirty. If it is dirty, then UMC630writes back the changed data before it is deleted.

In test block810UMC630determines whether the requested instruction(s) of the original instruction fetch aliased to the low half of the allocated L2 cache line. If the requested instruction(s) is in the low half of the L2 cache line (Yes in test block810), then UMC630fetches the low half L2 cache line from external memory161in block811. UMC630stores the received low half line in L2 cache130in block812.

Operations now split into two paths. On a first path, UMC630supplies the requested cache line to L1I cache121in block807. PMC620stores this just supplied data into the allocated line (block808) and supplies the fetched instruction(s) to CPU110(block803). It is known in the art that storing this received data in the level one cache and supplying data to CPU110can occur in parallel. Further the storing the returned data in the low half L2 cache line (block812) could also occur in parallel with storing this received data in the level one cache and supplying data to CPU110. This ends the instruction fetch process at block804. On the second path,630fetches the high half L2 cache line from external memory161in block813. UMC630stores the received high half line in L2 cache130in block814. This ends the instruction fetch process at block815.

If the requested instruction(s) is in the high half of the L2 cache line (No in test block810), then UMC630fetches the high half L2 cache line from external memory161in block816. UMC630stores the received high half line in L2 cache130in block817.

Operations now split into two paths. On a first path, UMC630supplies the requested cache line to L1I cache121in block807. PMC620stores this just supplied data into the allocated line (block808) and supplies the fetched instruction(s) to CPU110(block803). It is known in the art that storing this received data in the cache and supplying data to CPU110can occur in parallel. Further the storing the returned data in the high half L2 cache line (block817) could also occur in parallel with storing this received data in the level one cache and supplying data to CPU110. This ends the instruction fetch process in block804. On the second path,630fetches the low half L2 cache line from external memory161in block818. UMC630stores the received low half line in L2 cache130in block819. This ends the instruction fetch process in block820.

FIGS. 9A and 9Btogether illustrate the process of a CPU110load or store with allocate. A write allocate on a load instruction that misses in L1D cache123is described below. However, it is not necessary to provide such a write allocate. A store operation generating a miss generates a write through operation if write allocation is not supported. This invention still includes substantial utility in the absence of write allocation. Block901is the load or store instruction with write allocation. DMC610determines whether this load or store is a hit in L1D123in test block902. If this load or store is a hit (Yes in instruction block902), then DMC610supplies the requested load data from L1D cache123to CPU110(block903). This ends the data fetch process in block904.

If this load or store instruction is a miss in L1D cache123(No in test block902), then DMC610evicts and allocates an L1D cache line in block905. DMC610determines which cache way to which the requested data aliases to evict. In the preferred embodiment L1D cache123is two way set associative. This means that data from external memory161can reside in two cache lines in L1D cache123. In accordance with the preferred embodiment of this invention, the evicted way is the least recently used way. Thus DMC610evicts and allocates this line in L1D cache123. Data can be written to within L1D cache123and thus can be dirty. Also as part of block905, DMC610determines whether the way to be evicted is dirty. If it is dirty, then DMC610writes back the changed data before it is deleted.

In test block906UMC630determines whether the load or store is a hit in L2 cache130. If this load instruction is a hit in L2 cache130(Yes in test block905), then UMC630supplies the requested cache line to L1D cache123in block907. DMC610stores this just supplied data into the allocated line (block908). If the instruction was a store (write) operation, the write completes within the L1D cache line. If the instruction was a load (read), DMC610supplies the requested load data to CPU110(block903). It is known in the art that storing this received data in the cache and supplying data to CPU110can occur in parallel. This ends the data fetch process in block904.

If this load or store instruction is a miss in L2 cache130(No in test block906), then UMC630evicts and allocates an L2 cache line in block909. In the preferred embodiment L2 cache130is four way set associative. Thus any address from an external source may alias into one of four cache lines or ways. UMC630determines which cache way to which the requested data aliases to evict. In accordance with the preferred embodiment of this invention, the evicted way is the least recently used way. Data can be written to within L2 cache130and thus can be dirty. Also as part of block909, UMC630determines whether the way to be evicted is dirty. If it is dirty, then UMC630writes back the changed data before it is deleted.

In test block910UMC630determines whether the requested data of the original load or store instruction aliased to the low half of the allocated L2 cache line. If the requested data is in the low half of the L2 cache line (Yes in test block910), then UMC630fetches the low half L2 cache line from external memory161in block911. UMC630stores the received low half line in L2 cache130in block912.

Operations now split into two paths. On a first path, UMC630supplies the requested cache line to L1D cache123in block907. DMC610stores this just supplied data into the allocated line (block908). If the instruction was a store (write) operation, the write completes within the L1D cache line. If the instruction was a load (read), DMC610supplies the requested load data to CPU110(block903). It is known in the art that storing this received data in the cache and supplying data to CPU110can occur in parallel. Further the storing the returned data in the low half L2 cache line (block912) could also occur in parallel with storing this received data in the level one cache and supplying data to CPU110. This ends the data fetch process in block904. On the second path,630fetches the high half L2 cache line from external memory161in block913. UMC630stores the received high half line in L2 cache130in block914. This ends the load or store instruction process in block915.

If the requested instruction(s) is in the high half of the L2 cache line (No in test block910), then UMC630fetches the high half L2 cache line from external memory161in block916. UMC630stores the received high half line in L2 cache130in block917.

Operations now split into two paths. On a first path, UMC630supplies the requested cache line to L1D cache123in block907. DMC610stores this just supplied data into the allocated line (block908). If the instruction was a store (write) operation, the write completes within the L1D cache line. If the instruction was a load (read), DMC610supplies the requested load data to CPU110(block903). It is known in the art that storing this received data in the cache and supplying data to CPU110can occur in parallel. Further the storing the returned data in the high half L2 cache line (block917) could also occur in parallel with storing this received data in the level one cache and supplying data to CPU110. This ends the load or store instruction process in block904. On the second path,630fetches the low half L2 cache line from external memory161in block918. UMC630stores the received low half line in L2 cache130in block919. This ends the load or store instruction process in block920.

This improves allocate performance by a huge factor depending on the bytes that CPU requires. When the bytes that CPU110requires is in position 32 to 63 or 98 to 127, this causes an improvement of 200%

The stalls visible to CPU110are most critical to the performance of the application. This scheme minimizes such stalls by fetching the data that CPU110needs first. Because the CPU unstalls as soon as it receives the data it needs. This improves fetch performance. The improvement can be as large as 200% for instruct fetches where the L1I cache line is the last half of the L2 cache line.