TW201301032A - High-performance cache system and method - Google Patents

Abstract

A digital system is provided for high-performance cache systems. The digital system includes a processor core and a cache control unit. The processor core is capable of being coupled to a first memory containing executable instructions and a second memory with a faster speed than the first memory. Further, the processor core is configured to execute one or more instructions of the executable instructions from the second memory. The cache control unit is configured to be couple to the first memory, the second memory, and the processor core to fill at least the one or more instructions from the first memory to the second memory before the processor core executes the one or more instructions. Further, the cache control unit is also configured to examine instructions being filled from the first memory to the second memory to extract instruction information containing at least branch information, to create a plurality of tracks based on the extracted instruction information; and to fill the at least one or more instructions based on one or more tracks from the plurality of instruction tracks.

Description

High performance cache method and device

The invention relates to an integrated circuit and a computer field

Generally speaking, the role of the cache is to copy a part of the contents of the memory, so that the content can be quickly accessed by the processor core in a short time to ensure the continuous operation of the pipeline.

The current cache addressing is based on the following method: First, the label in the tag memory is read by the index segment in the address. At the same time, the index in the address is shared with the displacement segment in the block to read the contents of the cache. In addition, the tag read in the tag memory is matched with the tag segment in the address. If the tag read from the tag memory is the same as the tag segment in the address, then the content read from the cache is valid, called a cache hit. Otherwise, if the tag read from the tag memory is different from the tag segment in the address, the cache is missing, and the content read from the cache is invalid. For the cascading cache, the above operations are performed in parallel for each way group to detect which way group cache hits. The read content corresponding to the hit path group is valid content. If all the way groups are missing, all readings are invalid. After the cache is missing, the cache control logic populates the contents of the low-level storage medium into the cache.

Cache misses can be divided into three categories: mandatory missing, missing conflicts, and missing capacity. In the existing cache structure, in addition to prefetching a small portion of content successfully, forced deletion is inevitable. However, existing prefetch operations can be costly. In addition, although the multiplexed associative cache can reduce the lack of collisions, it is subject to power consumption and speed limitations (eg, because the multiplexed associative cache structure requires that all channels and addresses addressed by the same index be read and compared simultaneously. ), the number of road groups is difficult to exceed a certain number. In addition, in order to match the speed of the cache with the running speed of the processor core, it is difficult to increase the capacity of the cache. So there are multi-level cache settings, low-level cache is larger than high-level cache but slow.

Therefore, modern cache systems are typically composed of multi-level caches connected by multiplexes. New cache structures, such as victim cache, trace cache, and prefetch (putting the next cache block in the cache buffer or using prefetch instructions when taking a cache block) are used to compensate for some of the existing defects. . However, with the ever-increasing processor/memory speed gap, the current architecture, and in particular the potential for multiple cache misses, is still the most serious bottleneck that constrains the performance of modern processors.

The method and system apparatus proposed by the present invention can directly address one or more of the above or other difficulties.

The present invention provides a digital system that includes a processor core and a cache control unit. The processor core is coupled to a first memory including executable instructions and a second memory faster than the first memory, and the processor is configured to execute one or more pieces stored in the second memory Executable instructions. The cache control unit is connected to the first memory, the second memory, and the processor core, and is configured to fill the one or more instructions to the processor core before executing the at least one or more instructions in the first memory Two memory. In addition, the cache control unit can further be configured to review an instruction being filled from the first memory to the second memory, thereby extracting instruction information including at least branch (transfer) information, and according to the extracted instruction. The information creates a plurality of tracks and fills at least one or more instructions according to one or more tracks in the plurality of instruction tracks.

The present invention also provides a method for assisting operation of a processor core that connects a first memory containing executable instructions and a second memory that is faster than the first memory. The method includes reviewing an instruction being filled from a first memory to a second memory, thereby extracting instruction information including at least branch information, establishing a plurality of tracks according to the extracted instruction information, and according to the plurality of instructions One or more tracks in the track fill at least one or more instructions from the first memory to the second memory before being executed by the processor core, such that the processor core can acquire the at least one piece independent of the first memory Or multiple instructions.

The present invention also proposes a method for a cache control device to control processor core cache operations. The processor core is coupled to a first memory including executable instructions and a second memory faster than the first memory; and the processor core is configured to execute one or more second memories Executable instructions. The method includes reviewing an instruction being filled from the first memory to the second memory, and extracting instruction information from the reviewed instruction. The method further includes determining, before the processor core executes the branch point (transition point), the branch point according to the extracted instruction information, and filling the instruction segment of the branch target instruction corresponding to the branch point from the first memory to the first The second memory causes the second memory to contain any instructions caused by the processor core to execute the branch point.

The present invention also provides a method for controlling a plurality of cache memories including a first memory connected to a processor core and a second memory connected to the first memory by a cache control unit. The method includes reviewing instructions that are populated into a plurality of memories, and extracting instruction information from the reviewed instructions. The method further includes creating a track point in the track table according to the extracted instruction information, and representing the entry of the branch target track point by one of the low level cache memory block number and the high level cache memory block number. Wherein, when the branch target track point is represented by the low-level cache memory block number, an instruction segment corresponding to the branch target track point is filled into the first memory; when the high-level cache memory block number is used to represent the branch target track point The instruction segment corresponding to the branch target track is filled into the second memory instead of the first memory.

The present invention also proposes a processor core control cache running cache control device. The processor core is coupled to a first memory including executable instructions and a second memory faster than the first memory, and the processor is configured to execute executable instructions in the second memory One or more. The apparatus includes a first fill generation unit, a tracker and a dispenser. The first padding generating unit is configured to review an instruction filled from the first memory into the second memory, and extract instruction information from the reviewed instruction. The tracker is configured to control the leading indicator according to the extracted instruction information, thereby determining the branch point before the processor core executes to the branch point. In addition, the allocator is configured to fill the instruction segment corresponding to the target instruction of the branch point from the first memory to the second memory, so that the second memory includes any instruction caused by the processor core to execute the branch point.

Other aspects of the present invention can be understood and appreciated by those skilled in the art in light of the description of the invention.

Although the invention may be modified in various forms of modifications and substitutions, some specific embodiments of the invention are set forth in the specification and detailed. It should be understood that the inventor's point of departure is not to limit the invention to the particular embodiments set forth, but the inventor's point of departure is to protect all improvements, equivalent transformations and modifications based on the spirit or scope defined by the claims. .

1 is an embodiment of a computing environment in accordance with the present invention. As shown in FIG. 1, computing environment 1000 includes a processor core 125, a high level memory 124, a fill/generator 123, a low level memory 122, and a tracking engine 320. It should be understood that the components or devices shown in the figures are only for purposes of illustration and not limitation, and some of the components or devices may be omitted, and other components or devices may be added. Further, the present embodiment describes only the apparatus for reading an instruction, and the apparatus for reading data and storing data is similar.

The high level memory 124 and the low level memory 122 may be constructed of any suitable storage device, such as static memory (SRAM), dynamic memory (DRAM), and flash memory. In this embodiment, the level of memory indicates how close it is to the processor core. The closer the memory level is to the processor core, the higher the level of memory. In addition, usually a higher level of memory is faster in speed and smaller in area. The high-level memory 124 can be used as a cache of the system or a level 1 cache when other buffers exist, or can be divided into a plurality of memory segments called blocks (eg, memory blocks) for storing the processor core 125. Access to information (ie: instructions and information).

Processor core 125 can be any suitable processor that can be pipelined and cooperate with the cache system. Processor core 125 may use separate instruction caches and data caches, and may include some instructions for cache operations. When processor core 125 executes an instruction, processor core 125 first needs to read the instructions and/or data from the memory. The tracking engine 320 and the padding/generator 123 are used to populate the high-level memory 124 with instructions to be executed by the processor core 125, enabling the processor core 125 to be missing from the high-level memory 124 with a very low cache. Rate to read the required instructions. In the present embodiment, the term "filling" means moving data/instructions from a lower level memory to a higher level memory, and the term "access memory" means that the processor core 125 is closest to the memory ( That is, high-level memory 124 or level 1 cache) for reading or writing.

The tracking engine 320 and other components such as the fill/builder 123 can be implemented in the same integrated circuit as part of the processor die, or can be a stand-alone wafer, or run as a program in a processor die, or by software and hard. Body composition.

In the present embodiment, the tracking engine 320 generates the appropriate address for acquiring the desired instruction or the instruction block containing the required instruction based on the information sent by the pad/generator 123 and the processor core 125. The tracking engine 320 can also provide the fill/generator 123 with an appropriate address so that the fill/builder 123 can use the address to retrieve the corresponding instruction or the instruction block containing the corresponding instruction from the lower memory 122, and The instructions or blocks of instructions are stored in memory 124. In addition, the tracking engine 320 can also generate block numbers for the high level instruction memory 124. The block number and the intra-block offset generated by the processor core 125 can form an instruction addressing address together, and the corresponding instruction is sent from the high-level instruction memory 124 to the processor core without a cache miss. 125.

Specifically, the pad/generator 123 includes a generator 130 and a padding engine 132. The fill engine 132 can fetch instructions or instruction blocks based on the appropriate address. The generator 130 can review each instruction fetched from the low-level memory 122 and extract certain information such as an instruction type, an instruction address, and a branch target information of the branch instruction. The instructions and the extracted information including the target information of the points are sent to the tracking engine 320. In this embodiment a branch instruction or a branch point refers to any suitable form of instructions that causes processor core 125 to change the execution stream (e.g., execute an instruction out of order). The tracking engine 320 can determine address information, such as instruction type, branch source address, and branch target address information, according to the instruction and the branch target information. For example, the instruction types may include conditional branch instructions, unconditional branch instructions, and other instructions. In particular, an unconditional branch instruction can be considered to be a special case of a conditional branch instruction, ie, the condition is always true. Therefore, the instruction type can be divided into branch instructions and other instructions. The branch source address can refer to the address of the branch instruction itself, and the branch target address can refer to the address to which the branch will be transferred when the branch succeeds. In addition, you can include other information.

In addition, the tracking engine 320 can establish an address tree or a track table based on the address information provided by the determined information for populating the high level memory 124. Figure 2A illustrates an embodiment of implementing an address tree in accordance with the method of the present invention.

As shown in FIG. 2A, the address tree 300 can include tree nodes 310 and 312, trunks 301, 302, 304, 305, and 307, and tree branches 303 and 306. A trunk corresponds to a fixed or variable length sequence of instructions. A tree node can be a branch instruction that may be transferred after the instruction. If the branch transfer succeeds, a tree branch connecting the tree node and the branch target address is established. For example, 301, 302, 304, 305, and 307 are common instruction segments corresponding to the trunk; 310 and 312 are branch instructions corresponding to the tree nodes; 311 and 313 are branch targets, and tree branches 303 and 306 can be established thereby. In addition, other possible structures can also be used.

Any portion of address tree 300 or address tree 300 may be used as a track or track of a sequence of instructions executed by processor core 125 during program execution. The first instruction of the sequence of instructions may be considered a track head (HOL) or track header, and the instruction segments including the first instruction are filled into high level memory 124 for use by processor core 125. . During execution, the current instruction can be the first instruction in the sequence of instructions being executed, so that the HOL moves along the trajectory. In addition, one or more predictive track headers (PHOLs) may be generated for indicating a sequence of instructions that processor core 125 may use. For example, in a tree node (ie, a branch instruction), there may be two PHOLs depending on whether a branch occurs. During execution, the PHOL can be moved according to the branch point in the trajectory, and the PHOL is usually ahead of the HOL.

The address tree 300 can provide different depths depending on the number of layers of the branch nodes. For example, a layer address tree can support only one layer of branches (eg, the next branch), and a two-layer address tree can support two layers of branches (eg, the first layer when the first layer branch does not occur) The branch after the branch, or the branch of the first layer when the first layer branch occurs corresponds to the branch on the branch target track; in addition, a multi-layer address tree can support the multi-layer branch.

Figure 2B is an embodiment of the operation of the address tree in accordance with the present invention. As shown in FIG. 2B, the straight line represents the program, the curve represents the transfer path, the thick point represents the branch instruction, and the broken line represents the division of the corresponding program by the fixed length or the approximate length instruction segment (eg, the instruction segment).

Initially, processor core 125 executes block 30 until conditional branch instruction 31. If the branch transition condition of the branch instruction 31 is not true, the processor core 125 executes the program segment 33 until the unconditional branch instruction 36, and then moves to the program segment 37 along the transfer path 34 path unconditional branch. On the other hand, if the branch transition condition is satisfied when the conditional branch instruction 31 is executed, the processor core 125 executes the program segment 35 to which the transfer path 32 is transferred, and then continues to execute the program segment 37.

After execution of block 37, processor core 125 executes block 38 until conditional branch instruction 39 for the loop. If the loop condition of the conditional branch instruction 39 is true, the block 38 is executed again along the transition path 40. The 38 segments are repeatedly executed until the loop condition is not established, after which the processor core 125 executes the block 41.

The plurality of program segments may be represented by instruction segments 11, 12, 13, 14, 15, 16, and 17, and each of the instruction segments may include the same number of instructions or a different number of instructions in the variable length instruction set. For example, instruction segment 11 may include all of the instructions in program segment 30 and a portion of instructions in program segment 33; instruction segment 12 may include another portion of instructions in program segment 33; instruction segment 13 may include a portion of program segment 35 The instruction segment 14 may include another portion of the instructions in the program segment 35 and a portion of the instructions in the program segment 37; the instruction portion 15 may include another portion of the instructions in the corresponding program segment 37; the instruction portion 16 may include a portion of the program segment 38. The instruction segment 17 can include another portion of the instructions in the program block 38 and a portion of the instructions in the program segment 41. The size of each instruction segment can be determined based on the application target or hardware resources.

For convenience of description, it is assumed in the present embodiment that the filling of the instruction segments may not use the alternate filling method, and the next to-be-filled instruction segment is filled into the high-level instruction memory 124 after the completion of the filling of one instruction segment. Further, assume that the depth of the address tree 300 is one layer. That is, only one layer of the branch is used to fill the instruction segment into the high level memory 124. Other configuration methods can also be used similarly. At the beginning of processor core 125 operation, pad/generator 123 begins to fill instruction segment 11 into high level memory 124 and scans each instruction that is filled into high level memory 124. In some cases, two or more instructions can be scanned at a time, executing one instruction, and the scanned instructions are ahead of the instructions that are executed. For example, two instructions can be reviewed in one clock cycle while processor core 125 executes one instruction; or in the case of a multi-transmit processor, eight instructions are reviewed in one clock cycle while processor core 125 executes four instructions instruction. Other configuration methods can also be used to scan before execution.

Further, after the pad/generator 123 scans the conditional branch instruction 31, the pad/generator 123 can determine that the conditional branch instruction 31 is a branch instruction and can extract the target address of the branch instruction 31 located in the program segment 35. Thus, the tracking engine 320 controls the padding/generator 123 to fill the instruction segment corresponding to the target address, that is, the instruction segment 13, into the high level memory 124. Thus, the instruction segment 13 is filled into the high level memory 124 before the conditional branch instruction 31 is executed. In addition, the instruction segment 11 in which the branch instruction 31 corresponds to the next instruction sequentially executed has been filled into the high level memory 124, so no additional padding operation is required.

Further, when the branch instruction 31 is executed, it is assumed that the branch transition condition is not established, and the instruction segment 11 is continuously executed. When the last instruction in the instruction segment 11 is executed, the latter instruction segment 12 has been filled into the high level instruction memory 124 so that the last instruction in the instruction segment 11 can be executed without a cache miss. Execute the latter instruction.

When the instruction segment 12 is filled, the instruction being filled is scanned. The pad/generator 123 can find that the last instruction of the instruction segment 12 is a branch instruction (ie, an unconditional branch instruction 36). Thus, the instruction segment (ie, instruction segment 14) corresponding to the target address of the branch instruction 36 is filled into the high level instruction memory 124.

Similarly, it is already known that the next instruction corresponding to the last instruction is in instruction segment 14 before the last instruction in instruction segment 13 is executed. Since the instruction segment 14 has been filled, no additional padding is required. Similarly, instruction segments 15, 16 and 17 are populated into high level instruction memory 124 before processor core 125 executes any of instruction segments 15, 16, and 17.

In addition, when scanning to the branch instruction 39 for the loop in the instruction segment 17, the target instruction segment (ie, the instruction segment 16) and the instruction segment corresponding to the sequential execution of the next instruction address have been filled into the high-level memory. 124, so no additional padding is required. When the branch transition condition of instruction 39 is no longer true, the loop ends and the subsequent instructions in instruction segment 17 continue to be executed.

In summary, the tracking engine 320 and other components can control the above operations in accordance with the concept of the address tree to substantially reduce the cache miss rate. The tracking engine 320 and other components (eg, pad/generator 123) may also refer to a multi-component-oriented interface similar to the cache controller, thereby substantially reducing the cache miss rate. 3A is an embodiment 2000 of the cache system of the present invention.

As shown in FIG. 3A, the tracking engine 320 includes a track table 126 and a tracker 170. The track table can contain tracks of instructions that processor core 125 needs to execute, and tracker 170 can provide multiple addresses based on track table 126. In this embodiment, a track represents a sequence of instructions to be executed (e.g., an instruction segment). This representation can also include any suitable data type, such as an address, block number, or other digit. In addition, a new track is created when a track contains a branch point with a branch target that may change the program stream or is in another different instruction segment, such as an instruction in the next instruction segment, An exception handler, as well as different program threads. The sequence of instructions may contain the same number of instructions, or may include a different number of instructions when applied, for example, to a variable length instruction set.

The track table 126 can include a plurality of tracks, each track in the track table 126 corresponding to a row in the track table 126, and having a line number or block number corresponding to the memory block. A track may include a plurality of track points, each track point corresponding to a single address. Moreover, as if one track corresponds to a single row in the track table 126, one track point corresponds to a separate entry (eg, a storage unit) of the corresponding row in the track table 126. Thus, the total number of track points in the track can be equal to the total number of entries in a row in track table 126. In addition, other configuration methods can be used.

A track point (ie, a single item in a table entry) can contain information about a branch instruction whose branch target can be in another track. In this way, the content of the track point may include information of the instruction corresponding to the track point and information of the branch target address, the information of the branch target address may include the track number of the target track, and the positioning item is used in the target track. The offset of the position in the middle. By examining the content of the track point, the target track can be determined based on the track number, and a specific entry in the target track is determined based on the offset. In this way, the track table becomes a table in which the branch track entry address corresponds to the branch source address and the entry content of the entry corresponds to the branch target address.

For example, in FIG. 3A, processor core 125 reads and executes an instruction address using (M+Z) bits, where M and Z are integers. The M bit portion of the address can be used to indicate the upper address, and the Z bit portion can be just offset. The track table 126 can contain 2 ^M lines, i.e., 2 ^M tracks, and the M-bit high order address can be used to address the tracks in the track table 126. Each row can contain 2 ^Z track entries, ie 2 ^Z track points, and the offset (Z bits) can be used to address a particular track point (table entry) in the corresponding row.

When a new track is created, the new track can be placed in a valid row in the track table. If the new track contains a branch track point (corresponding to a branch source instruction), then a branch track point is established within an entry in the line. The location of the row and entry of the branch point in the track table 126 can be determined based on the branch source address. For example, the row may be determined according to the upper address of the branch source address, and the entry is determined according to the offset of the branch source address.

Moreover, each entry or track point in the row can include a content format that includes a type region 57, an XADDR region 58, and a YADDR region 59. It can also contain other areas. Type area 57 may represent the type of instruction corresponding to the track point. As mentioned previously, the instruction types may include conditional branch instructions, unconditional branch instructions, and other instructions. The XADDR region 58 may contain an M-bit address, also referred to as a first-dimensional address or simply a first address. The YADDR region 59 may contain a Z-bit address, also referred to as a second-dimensional address or simply a second address.

In addition, the content of the new track point can correspond to the branch target instruction. In other words, the contents of the branch track point store the branch target address information. For example, the row number or block number in the track table 126 corresponding to a particular row of a branch target instruction is stored as the first address 58 into the content of the branch track point. Further, the offset of the branch target is stored as the second address 59 into the content of the branch track point. The offset can be calculated based on the branch source instruction address and the branch transfer displacement (distance). Thus, when addressing the branch target, the first address XADDR 58 stored in the branch track point (ie, the branch source instruction) is used as the row address, and the second address YADDR stored in the branch track point is stored. 59 is used as the column address.

Instruction memory 46 may be part of high level memory 124 for instruction access and may be constructed of any suitable high performance memory. Instruction memory 46 may contain 2 ^M memory blocks, each memory block containing 2 ^Z bytes or words.

The tracker 170 can be comprised of a variety of components or devices, such as registers, selectors, stacks, and/or other storage modules for determining the next track to be executed by the processor core 125. The tracker 170 can determine the next track based on information such as the current track in the track table 126, track point information, and whether branching has occurred due to execution of the processor core 125.

For example, during operation, the instruction address of the (M+Z) bit is passed on the bus 55. The M bit address is sent to the track table 126 as the first address or XADDR (or X address) through the bus 56, and Z is the address as the second address or YADDR (or Y address) through the bus bar 53. It is sent to the track table 126. According to the first address and the second address, an entry in the track table can be found and its content is output to the bus bar 51. If the entry corresponds to a branch instruction (a branch track point or a branch source instruction), the contents of the entry are used as the target address of the branch through the bus bar 51.

If the branch transfer condition of the branch instruction does not hold, the branch transfer does not occur, and the branch transfer from the processor core 125 does not occur. The signal control selector 49 selects the YADDR on the bus 53 to increase by one. 1) The value on the bus 54 is obtained as a new second address after a byte or word, and the new address is output on the bus 52. Register 50 keeps the first address unchanged and is incremented by one (1) by the increment one logic 48 until it points to the next branch instruction on the current track. Thereafter, the first address and the second address are held in the register 50 and supplied to the bus bar 55.

On the other hand, if the branch transfer condition of the branch instruction is established, the branch transfer occurs, and the branch transfer prosperous signal control selector 49 issued by the processor core 125 selects the track corresponding to the branch point on the bus bar 51. The new target address stored in the contents of the entry is sent to the bus 52 as an output. The register 50 holds the changed first address and provides a new address of (M+Z) bits to the bus 55. The signal from processor core 125 for controlling selector 49 is also referred to as a "taken" signal for indicating whether a branch has occurred.

Thus, while the processor core 125 provides only the offset, the tracking engine 320 provides a block address on the bus 56, thereby enabling the addressing of the instruction memory 46. The processor core 125 feeds back the branch instruction execution (i.e., "occurrence" signal) to the tracker 170 so that the tracker 170 can determine how to operate.

The instruction segment corresponding to the track has been filled into the instruction memory 46 before the new track is executed. Such a process is iteratively executed so that all instructions can be executed by processor core 125 without a cache miss. In addition, a two-level indicator (PHOL) can also be used to review the two subsequent points-to-point after the first branch point, and the tracker 170 and/or the filler/generator 123 can take the two The instruction segments corresponding to the two tracks of the branch point are filled into the instruction memory 46, thereby further hiding the delay of filling the buffer.

FIG. 3B is another embodiment 3000 of the cache system of the present invention. This embodiment omits components similar to the embodiment of Fig. 3A. As shown in FIG. 3B, the XADDR address or block address on the bus 56 for addressing the track table 126 and the instruction memory 46 can have a number of different sources. That is to say, the tracker 170 can select a track from a plurality of address sources. For example, the selector 49 of FIG. 3A is replaced with a multiplexer 65 so that selection can be made from four different sources: the target address of the current branch instruction on the bus bar 51 (track table content), The first address on the bus 54 is unchanged and the second address is incremented by one (1), a normal address, an address from the stack 61 on the bus 64, and the bus 62. Corresponds to the track position of the exception handler entry.

The multiplexer 65 selects a track (current track or new track) based on the current command and the operating state. For example, if the track point corresponding to the second address is not a branch instruction, then the first address remains unchanged, and the increment one logic 48 keeps incrementing the second address by one (1) until the next branch instruction. If the track point corresponding to the second address is a branch instruction or a branch instruction is reached, and the branch condition is not satisfied, then the first address remains unchanged and the second address is incremented until the next branch instruction. On the other hand, if the branch condition is satisfied, or the branch is unconditional, then the target address is used as the new first address to reach a new track. Finally, if the last instruction is reached, it will also enter a new track corresponding to the next instruction segment.

Some special programs, such as exception handlers, can also be populated into the high level memory 124 and create corresponding tracks. The track point addresses corresponding to these special program entries can be stored in special registers (eg EXCP). When a time occurs (e.g., an exception occurs), the track point address corresponding to a special program (e.g., an exception handler) is selected by the selector 65 via the bus 62 to enter the special program.

Additionally, stack 61 can include a plurality of separate stacks. Each individual stack can provide stack operations, such as pushing instructions onto the stack, and popping the instructions to save thread content or save the "cable" state. When a program calls a path, the address and/or other information of the track point corresponding to the returned address can be pushed onto the stack, and when returned from a call path, the saved track point address and/or other information The stack can be popped and the track is forced to change according to the track point (select 64 by selector 65). In some cases, processor core 125 may execute a "jump and link" type of instruction (ie, branch transfer or call to return address when the path is completed). Similarly, a stack can be used to hold the return address of this type of instruction. In addition, processor core 125 can execute a plurality of nested "call" or "jump and link" type instructions. The separate stack can include multiple layers to hold multiple return addresses at different stack levels. In addition, the plurality of stacks can support multi-threaded programs. Track table 126 can include a plurality of stacks corresponding to different threads, and thread identifier 63 can be used to identify the current program thread. In addition, thread identifier 63 points to the current stack that supports the current thread. Other sources or permutations may also be used in this embodiment.

Thus, multithreaded programs can be supported by using a plurality of stacks, each of which can be used by a thread or program alone, depending on the identity of the thread identifier 63.

4 is another embodiment 4000 of the cache system of the present invention. Embodiment 4000 is similar to embodiment 2000 in Figure 3A. However, the instruction memory 78 is used instead of the instruction memory 46 in this embodiment. As shown in FIG. 4, the instruction memory 78 can contain 2 ^N memory blocks, where N is an integer and N□M. That is, the instruction memory 78 can contain fewer memory blocks than the instruction memory 46. The first address on bus bar 56 is therefore also only used to address track table 126.

In addition, one mapping unit 79 may map the first address to a block number or block address 80 of N bits long. In this way, the address addressed to the high-level memory can be mapped to reduce the size of the high-level memory. Since the processor core 125 is almost impossible to use all the instruction addresses in the entire address space, such a mapping-based method may not provide a memory block corresponding to all the address spaces, thereby reducing the instruction memory 78. size.

Figure 5 is another embodiment 5000 of the cache system of the present invention. Embodiment 5000 is similar to embodiment 4000 of FIG. However, track table 126 may contain only 2 ^N rows. That is to say, the first address on the bus bar 56 is mapped by the mapping unit 82 and the track table 126 and the instruction memory 78 are simultaneously addressed to reduce the size requirement.

Moreover, where the total number of rows in track table 126 and instruction memory 78 is less than the total addressable space of processor core 125, the rows in track table 126 may still use M bits as the first address and use Z bits as the first The two addresses thereby reducing the memory capacity of the track table 126 and the instruction memory 78 at the same time.

6 is another embodiment 6000 of the cache system of the present invention. Embodiment 6000 is similar to embodiment 5000 of FIG. However, as shown in FIG. 6, a mapping unit 83 is placed outside the track table 126 and the instruction memory 78 such that the first address 84 of the M bit is mapped to N before being used by the track table 126 and the instruction memory 78. The first address of the bit is 85. Thus, the addresses addressed to track table 126, instruction memory 78, and tracker 170 are mapped to reduce capacity.

Thus, the rows in the track table 126 can use the first address of the N bits and the second address of the Z bit. The total number of rows in the track table 126 and the instruction memory 78 can be less than the total address addressable by the processor core 125. Space, thereby reducing the memory capacity of track table 126 and instruction memory 78 at the same time. In addition, a shorter first address can improve the performance of the entire system.

Although the above mapping method can reduce the capacity of the cache and track table, each instruction segment can still correspond to one track. Additional structures can also be used to prevent duplicate builds of built tracks without discarding built track information. FIG. 7A is another embodiment 8000 of the cache system of the present invention implemented using one or more of the above mapping methods.

As shown in FIG. 7A, the cache system 8000 includes low level memory 122, high level instruction memory 124, and processor core 125. In addition, cache system 8000 also includes a fill/builder 123, a dispatcher 1200, a track table 126, and a tracker 170. Dispenser 1200, track table 126, and tracker 170 form the body portion of tracking engine 320 (not shown). Also, as previously described, the tracking engine 320, pad/generator 123, and other related logic can be used as a cache control unit. It should be understood that the various components listed herein are merely for convenience of description and may include other components, or some components may be combined or omitted. The plurality of components may be distributed among a plurality of systems, may be physically present or virtual, or may be implemented by hardware (such as integrated circuits), implemented by software, or by a combination of hardware and software.

In addition, the pad/generator 123 can include a fill engine 132, a generator 130, and an address translation unit 131, and the tracker 170 can include a multiplexer 137, registers 138, add-on logic 136, and stack 135. Other components may also be included, or some components may be combined or omitted. For ease of description, high level memory 124 may be considered a level one (L1) cache, and low level memory 122 may be considered a level two (L2) cache or main memory, depending on the particular application and configuration. As described earlier, the generator 130 extracts the branch instruction (source) address (the track table address corresponding to the branch instruction), the branch type, and the branch target address (the track table content corresponding to the branch track point) to establish the track. Table 126.

The distributor 1200 can be used to store track information or to store track information after allocation to reduce the capacity size requirements of the track table 126 and the high level memory 124. For example, the distributor 1200 can include an active table 121. An active table can store information about an established track and establish a mapping between an address (or a portion of the address) and a block number represented by a valid line occupied by the track in the track table 126. For example, when a track is created, the address information of the track is stored in the active list. Other forms of placement are also possible.

As shown in FIG. 7A, the active table 121 can be used to store block addresses of the instruction segments in the high level memory 124, and each block address corresponds to a block number (BNX). The block number corresponding to a specific address can be obtained by performing content matching on the address and the entry in the active table 121. The location of the matching successful content may be encoded to obtain a block number, which may be used to index one row in the track table and one block in the high level memory 124. If the match is unsuccessful, it means that the track corresponding to the address has not been established yet. The instruction segment corresponding to the address is filled into the high level memory 124, and a new track is built in the track table 126 in the row indexed by the address index 129 through the bus bar 153, and the active table 121 is in the bit. The entry index 129 indexed by the bus bar 153 is updated (written) to the corresponding block address. Figure 8 is an embodiment of the active watch of the present invention.

As shown in FIG. 8, the active list 121 can include an address/data bidirectional addressing unit 100. In one direction, the data/address bidirectional addressing unit 100 can output a BNX number based on an input block address. The data/address bidirectional addressing unit 100 generates a corresponding BNX by matching the input block (high order) address and the data/address bidirectional address unit 100. In the other direction, the data/address bidirectional addressing unit 100 can output a corresponding block address based on an input BNX number. The input BNX number may be indexed to an entry storing the block address. In addition, the data/address bidirectional addressing unit 100 can include a plurality of entries 101, each entry 101 including a register, a comparator, a flag bit 111 (ie, a V bit), and a flag bit 112 (ie, A bit) and a flag bit 113 (ie, U bit). The result of the comparator can be sent to encoder 102 for generating a matching entry number.

Control logic 107 can be used to control the read/write state. The V (valid) bit of each entry 101 can be initialized to "0", and the A (active) bit of each entry 101 can be written to an active signal on signal line 119. A write indicator 105 can be directed to an entry in the data/address bidirectional addressing unit 100, and the indicator is generated by a loop auto increment unit 110 (129 in Figure 7A). The maximum value that the loop self-incrementing unit 110 can generate is equal to the total number of the entries 101. When the maximum value is reached, the next value generated by the increase of the loop self-incrementing unit 110 is restarted from "0", and continues to increase until it reaches the maximum value again.

During the running process, when the write indicator 105 points to a current entry 101, the V bit and the A bit of the current entry 101 are checked. If both the V bit and the A bit are "0", then the current entry is free and can be written. When the write operation is completed, the loop auto increment unit 110 may increment the index by one (1) to point to the next entry. However, if one of the V bits and the A bit is not "0", then the current entry cannot be used for a new write, and the loop auto increment unit 110 can increment the indicator by one (1) to point to the next table. Item, and check if the next entry is available for new writes.

In the matching process, the input block address data 104 is compared with the contents of the registers of each entry 101. The contents of the register contain only the upper bits of the address (corresponding to the memory block in the high level memory 124). If the match is successful, the encoder 102 encodes the match result as an entry number and sends the entry number to the match address output 109. If the match is unsuccessful, the input block address is written into the register 101 in the entry pointed to by the indicator 105, and the V bit in the entry is set to "1", and the entry number is It is output 109 from the matching address. The output entry number is then used to represent BNX (because it indexes a memory block, hence the block number). The lower bits of the input address (i.e., the offset in one memory block) are then used to represent BNY. The BNX and BNY are used together to represent the BN, which is then stored in a track entry and used to index the track table 126, the high level memory 124, and the active table 121. Although "BN" as used herein generally refers to a "block number" including BNX and BNY, it can be understood by those skilled in the art that in some special cases, it can only refer to the upper part of the address. That is equivalent to BNX. Further, the loop self-increment unit 110 may increment the index BNY by one (1) to point to the next entry.

For a read operation, the read address 106 is used to select an entry in the plurality of entries 101, and the contents of the registers in the selected entry are read and sent to the data output 108, and the selected The V bit of the entry 101 is set to "1".

A U bit in an entry 101 can be used to indicate a storage state. When the write indicator 105 points to an entry 101, the U bit in the pointed entry is set to "0". When an entry 101 is read, the U bit in the read entry is set to "1". In addition, when the loop self-increment unit 110 generates a write index 105 to point to a new entry, the U bit in the new entry is checked. If the U bit is "0", then the new entry can be used for replacement, and in order to complete a possible data write operation, the write indicator 105 stays at the new entry. However, if the U bit is "1", then the indicator 105 is further pointed to the next entry.

Optionally, a window indicator 116 can be used to set the U bit in the entry to which it points to "0", and the window (clear) indicator 116 is located at the position of the N entries preceding the write indicator 105 (N is An integer). The value of the window indicator 116 can be obtained by increasing the value of the write index 105 by the adder 115. The N entries between the write indicator 105 and the window indicator 116 can be considered as a window. Thus, the clear indicator can set the U bit in an entry to "0". Thereafter, any read operation on the entry will cause the U bit to be set to "1". When the write indicator 105 points to the entry, the U bit is checked. If the U bit is "0", it means that the entry has not been used since the entry is cleared by the clear indicator 116, so the write indicator 105 stays in the entry and is used for the next write. On the other hand, if the U bit is "1", indicating that the entry has been used recently, the write indicator moves to the next entry. The frequency at which the entry in the entry 101 is replaced can be changed by changing the size of the window (i.e., changing the value of N). This method can be used as a usage-based replacement strategy to replace entries in the active table 121.

Alternatively, the U bit may be more than one bit, such that there are multiple U bits. The multi-bit U bit can be cleared by the write indicator 105 or the window (clear) indicator 116, and each read operation can increase the value of the corresponding multi-bit U bit by "1". During the write operation, the U bit in the current entry is a pre-set value. If the value of the U bit is less than the predetermined value, the current entry can be replaced. If the value of the U bit is greater than the predetermined value, the indicator 105 moves to the next entry.

Returning to Fig. 7A, when the processor core 125 is turned on, a reset signal (not shown) sets the effective position of all entries in the active list 121 to "0". When the reset signal is released, a reset vector (the instruction address of the reset start point) is placed on the bus 141 to be sent to the active table 121 for matching. Since no match is found in the contents of the entry in the active table 121, the active table 121 writes the upper portion of the address (ie, the reset vector) to the entry in the active table 121 pointed to by the WXADDR 153 generated by the indicator 129. The valid bit of the entry is set to "1" and the reset vector is sent to the fill engine 132 via the bus 144.

The fill engine 132 fetches the instructions from the low level memory 122 through the bus bar 154 according to the instruction address corresponding to the reset vector. The fetched instructions are populated into a memory block of the high level memory 124 indexed by the WXADDR 153 generated by the indicator 129. At the same time, when the instruction is fetched from the low level memory 122 through the bus bar 140, the generator 130 can scan and review the instructions. In addition, the trajectory information corresponding to the instruction is written into the corresponding entry or track point in the track table 126 that is pointed by the WXADDR 153.

When the filling operation is completed, the indicator 129 moves to the next available entry in the active list 121. Alternatively, the address translation unit 131 may perform translation conversion on the virtual address and the real address. The address translation unit 131 can also be placed outside of the lower level memory 122, thereby reducing the delay in acquiring the high level memory 124 from the lower level memory 122.

The generator 130 scans each instruction in the instruction block populated into the high level memory 124. When the generator 130 finds a branch instruction, the target address of the branch instruction is calculated. The target address may be added by the instruction segment start address of the branch instruction plus the offset of the branch instruction, and the distance that the branch is transferred to the target instruction. The lower bit portion of the target address is the offset of the branch target instruction in its row (which will be denoted later by BNY). The calculated upper portion of the target address is used to match the content in the active table 121. If the match is unsuccessful, then the active table 121 sends this value through the bus 144 to the fill engine 132 to effect the fill operation.

On the other hand, if the match is successful, it indicates that the instruction segment containing the branch target has been stored in the high level memory 124, and the matching line number (BNX) and the branch target instruction are in the line (BNX). The shift amount (BNY) (i.e., the merge is referred to as BN) is sent to the bus 149 for writing a track entry. The entry is indexed by WXADDR 153 (row address) and the value of the offset from the generator 130 (column address) on the bus 143 indicating that the branch instruction is in the instruction segment in which it is located. Thus, when all the instructions in the instruction segment are scanned and processed, the entries corresponding to the same instruction segment in the active table 121, the track table 126, and the high level memory 124 are indexed by the same WXADDR.

More specifically, the high level memory 124 contains the entire instruction segment to be used by the processor core 125, the active table 121 contains the block (high order) address to be matched with the subsequent instruction segments, and the track table 126 contains the All branch track points in the instruction segment include their position in the instruction segment and the BN value of their target address. A BN value includes a row address BNX and a column address BNY.

Figure 9 shows an embodiment of a method of establishing a new track using track table 126 in accordance with the teachings of the present invention. As shown in FIG. 9, an established track 66 (represented by BNX0) may contain three branch instructions or branch points 67, 68, and 69. When reviewing the branch point 67, a new track 70 (the next available line indicated by BNX1) is established for storing the target command of the branch point 67, and the number of the track or the line number in the track table 126 (ie, BNX1) is recorded in the branch point 67 as the first address. Similarly, when reviewing the branch point 68, another new track 71 (with BNX2) representation is established in the track table 126, and the track number is recorded in the branch point 68; when reviewing the branch point 69, in the track table Another new track 72 (with BNX3) representation in 126 is established and the track number is recorded in branch point 69.

In this way, new tracks corresponding to all branch points in a single track can be established. Furthermore, the track table 126 can be large enough to accommodate all block numbers, and the number of new tracks can be obtained by adding one (1) to the largest track number in the used track. Optionally, depending on the specific track granularity, the number of instructions corresponding to one track may be multiple (higher granularity may allow a single track or row to represent the instruction segment containing a larger number of instructions with a smaller number of entries) ).

Returning to Figure 7A, continuing the previous operation, the tracker 170 can output a BN 151 for addressing the track table 126 and the high level memory 124. That is, the tracker 170 can provide coordinate operations to the track table 126, the high level memory 124, and the processor core 125. FIG. 7B shows an embodiment of a component of the cache system 8000 that implements the operations.

As shown in FIG. 7B, the tracker 170 includes a stack 135, an auto-incrementer 136, a multiplexer 137, a register 138, and an exception handler address register 139. Tracker 170 controls a read indicator of track table 126 during operation. That is, the tracker 170 outputs an address (i.e., BN 151) for addressing the track table 126 and the high level memory 124. BN 151 includes BNX 152 and BNY 156. BNX 152 can be used to address one row or track in track table 126 and address a memory block in high level memory 124, at which point BNY 156 can be used in track table 126 by BNX An entry in the track or row pointed to by 152 is addressed.

The tracker 170 can select the output BN 151 from a different source through the multiplexer 137. For example, the multiplexer 137 can have four BN input sources: one BN stored in the stack 135 sent through the bus 164, the current BNX 151 and the booster 136 sent through the bus 165. A new BN formed by the current BNY 156 self-incremented BNY, a BN derived from the track table 126 sent through the bus 150, and a BN derived from the exception handler address register 139. There are also other sources available. As described earlier, the BN stored in the stack 135 may be the BN value corresponding to the program address at the time of the function call or return, and the BN stored in the exception handler address register 139 may be the address of the exception handler. BN value. All BN values output by the multiplexer 137 include BNX and BNY.

In addition, multiplexer 137 is controlled by signal 381 from processor core 125 to select a particular BN to output 418. For example, when an exception occurs in the processor core 125, the multiplexer 137 is controlled by the signal 381 to select the BN sent from the exception handler address register 139 as the output 418; when the processor core 125 returns a function call, The multiplexer 137 signal 381 controls the BN sent from the stack 135 as the output 418; when the processor core 125 performs the branch transfer (the signal 381 becomes a branch transfer signal), the multiplexer 137 signal 381 controls the selection of the track. Table 126 sends BN as output 418; and when processor core 125 does not perform branch transfer or performs other normal operations, multiplexer 137 is controlled by signal 381 to select BN 165, ie BNX 152 remains unchanged, BNY is self-contained The booster 136 is incremented by BN as output 418.

The bus or output 418 (i.e., the next BN) from the multiplexer 137 can be stored in the register 138 under control of the signal 417 from the processor core 125 and used to update the BN 151 of the tracker output. . When the register 138 is controlled by the signal 417 to keep the current BN 151 unchanged, the register 138 does not output the output 418. On the other hand, when the register 138 is controlled by the signal 417 to update the current BN 151, the output 418 is sent to the bus bar 151 to become the current BN 151, thereby updating the BNX 152 and the BNY 156.

The BN 151 provided by the tracker 170 includes BNX 152 and BNY 156. BNX 152 is used to address the instruction segment, and processor core 125 uses the offset of the PC to fetch the instructions that need to be executed. Moreover, BNX 152 and BNY 156 are sent to track table 126 such that track table 126 can deliver the next BN to bus bar 150.

As shown in FIG. 7B, to describe the correlation between the track table 126 and the tracker 170, it is assumed that the track table 126 includes tracks (ie, rows) 410, 411, and 412. Each track can contain 16 entries or track points from 0 to 15. Further, the track point 413 (the eighth item in the track 410) may be a branch point where the branch target is the track point 414 (the second item in the track 411), and the track point 415 (the 14th item in the track 411) may Is another branch point whose branch target is track point 416 (the fifth item in track 412).

It is assumed that the instruction segment corresponding to the track 410 has been filled in the high level memory 124, and the processor core 125 executes the instruction from the start position of the track 410. That is to say, the program counter (PC) of the processor core 125 starts from the instruction address corresponding to the 0th entry in the track 410.

At the same time, it is assumed that the tracker 170 also sends a read indicator 151 containing the 0th item of the track 410 in the track table 126 of BNX and BNY. Other entries in track 410 can also be used. The type information, address information, and the like of the instruction can be determined by checking the contents of the entry.

As described earlier, when running from the 0th item of the track 410, since the 0th item of the track 410 is not a branch point, the tracker 170 keeps the BNX 152 unchanged and increases BNY by the booster 136, thereby The next BN of the next entry in the track 410 in the corresponding track table 126 is obtained. The tracker 170 continuously increments BNY to move to the next entry in track 410 until a branch point is reached, such as track point 413 (item 8 in track 410). In this process, since the BNX has not changed, the instruction segment address does not change, and the processor core 125 can continuously acquire instructions from the high-level memory 124 using the offset of the PC.

When the tracker 170 reaches the track point 413 (the eighth item in the track 410), since the track point 413 is a branch point, both the source address and the target address are analyzed. If the instruction segment of the next instruction containing the branch point source address and/or the instruction segment containing the target address has not been filled into the high level memory 124, then the processor core 125 may be The executed instruction segment is filled into the high level memory 124.

In some cases, since the entry in the active table 121 is established when the track table row is established, when the tracker 170 reaches the track point 413, the instruction segment containing the next instruction of the source address and the inclusion is included. The instruction segment of the target address may have been populated into the high level memory 124. Thus, since the next instruction is the ninth item in the track 410, and the instruction segment corresponding to the track 410 has been filled into the high level memory 124, the next instruction of the track point 413 does not need to be filled. Further, since the track point 414 has been established in the track table 126 and the active table 121, the instruction segment corresponding to the track target (the second item of the track 411) corresponding to the track 411 has been filled into the high level memory 124.

Since processor core 125 executes instructions at a slower rate than tracker 170 moves along track points corresponding to the instructions, tracker 170 can wait for processor core 125 or synchronize with processor core 125 at the branch point. In addition, the track table 126 can have the branch target as the next BN on the bus 150 (the second item of the track 411), that is, BNX is 411 and BNY is 2, and the signal 381 can execute the branch of the track point 413 at the processor core 125. Provides an indication of whether a branch occurred during the instruction.

As shown in this embodiment, when a branch occurs, the tracker 170 sends the track table through the bus bar 150 to obtain the next BN as the BN 151, that is, the BNX points to the track 411 and the BNY points to the second item of the track 411. BNX is also used to address the corresponding instruction segments in high level memory 124 such that processor core 125 can begin execution of instructions corresponding to the second entry of track 411. However, if the branch does not occur, the branch point is simply treated as a non-branch point, and the tracker 170 moves forward.

Similarly, starting from the second term of the track 411, the tracker 170 finds the branch track point 415 (the 14th item of the track 411) where the next branch target is the track point 416 (the fifth item of the track 412). The track point 413 is operated in a similar manner as previously described. If a branch for branch track point 415 (item 14 of track 411) occurs, processor core 125 begins execution at track point 416. On the other hand, if the branch for the branch track point 415 does not occur, the tracker 170 moves to the 15th item of the track 411, that is, the last item of the track 411.

When the entry is not a branch point, but the last instruction of the track is running, starting from the track point corresponding to the next instruction located in the next track, the tracker 170 keeps the BNX 152 unchanged and continues to BNY 156. Increase by one (1) to generate a new BNY until a new BNY points to the first branch point in the new track.

Thus, the track table 126 can be created before the processor core 125 actually executes the instructions so that the instructions can be populated into the high level memory 124 to avoid or reduce latency due to cache misses. Other mechanisms, such as increasing the speed of the track table, increasing the granularity of BNY, reducing the number of entries in the track table by using multiple entries in the track table, etc., can be applied separately or in combination in the above implementation. In the example.

It is also possible to further improve the cache miss rate by employing a multi-layer branching method in the track table 126. For example, when an entry is read from a table row in the track table 126, a branch track point is found and the instruction segment containing the branch target instruction corresponding to the branch track point is filled into the high level memory 124. At the same time, a new track (level 1) is created in the track table 126. In addition, the new track is also detected, the first branch track point in the new track is found, and the instruction segment containing the branch target instruction corresponding to the branch track point in the new track is filled into the high level memory 124. Thus, another new track (secondary) is created in the track table 126. Thus, two levels of branch points are used to fill the high level memory 124, and for the processor core 125, the fill operation is further hidden. It is also possible to establish a secondary track for all possible execution results of the primary track. In this way, the two-level track is not only established according to the first branch point in the new track according to the branch target corresponding to the current branch point, but also established according to the first branch point of the new track corresponding to the next instruction after the current branch point.

In addition, one or more layers of variable layer tracks can be created based on the distance from the current program counter (PC). The distance may be represented by the number of instructions leading the instruction executed by the current processor core 125. That is, regardless of how many layers of tracks are established to ensure that the filled instructions are ahead of the instruction being executed by a predetermined value, the tracks can be built to fill at least the number corresponding to the distance determined by the distance. The instruction segment of all instructions. The distance can also be represented by a distance from the current branch point. That is, regardless of how many layers of tracks are established to ensure that the filled instructions are ahead of the instruction being executed by a pre-set value and mask the fill delay, the tracks can be built to fill at least from the branch point. An instruction segment of an instruction corresponding to the distance. Other parameters can also be used.

Moreover, in some examples, a plurality of memory blocks (eg, instruction segments and data segments) can be simultaneously populated into the high level memory 124. When the plurality of instruction segments or data segments are filled, each segment can be divided into a plurality of small segments, and a priority order can be set for each small segment. In this way, it is not necessary to fill the entire individual segment at one time. The priority order of each small segment may be prioritized based on the processor core 125, and the small segments of the different segments may be padded using an alternate mechanism according to the priority order of each small segment.

For example, if an instruction segment is 256 words (1024 bytes) long, the instruction segment can be split into four small segments, each of which contains 64 words (256 bytes). Thus, for an instruction segment starting at address 0x1FC00000, the four small segments start from 0x1FC00000, 0x1FC00100, 0x1FC00200, and 0x1FC00300, respectively. If the instruction required by processor core 125 is located in the second small segment 0x1FC00100, the priority of this small segment 0x1FC00100 can be set high. Thus, the filling order when filling the instruction segments can be 0x1FC00100, 0x1FC00200, 0x1FC00300, and 0x1FC00000. In addition, if the instruction segment starting from 0x1FC00000 is filled in, and another or the second instruction segment starting from 0x90000000 is also required to be filled, the second instruction segment can also be divided into four small segments, respectively Start with 0x90000000, 0x90000100, 0x90000200, and 0x90000300. If the instruction required by the processor core 125 is in the fourth small segment (0x90000300), then the fourth small segment can be set to a high priority order, and the entire padding order can be 0x1FC00100 in an alternating manner. 0x90000300, 0x1FC00200, 0x90000000, 0x1FC00300, 0x90000100, 0x1FC00000, and 0x90000200. In addition, more segments and small segments can be used to fill the high level memory 124, and other configurations can be used. Although the above embodiment describes the instruction segment padding, a similar method can be used for data segment padding. In addition, the instruction segment and the data segment can also be alternately filled with segments.

Figure 10A is another embodiment 9000 of the cache system of the present invention. Cache system 9000 is similar to cache system 8000 in Figure 7A. However, as shown in FIG. 10A, the cache system 9000 includes a switch 133, and the allocator 1200 in the cache system 9000 includes a reservation table 120 in addition to an active table 121.

The reserved table is similar to the active table, and stores the track information of all branch instructions in the program together with the active table, thereby reducing the capacity of the active table 121 and the primary cache. More specifically, when a track corresponding to a branch point has been established, the branch target of the branch point can be stored in the reservation table. The branch target track may be established based on information stored in the reserved table when the execution flow is close to the branch point.

In some examples, the active table stores the created tracks (eg, corresponding to the instruction segments that have been populated into the high level memory 124), while the reserved table stores the tracks that will be created (eg, the corresponding has not been filled to a high level) The instruction segment in the memory 124). Thus, when a track is created, a track point can correspond to an entry in the active table (eg, a BN) or an entry in the reserved table (a TBN). "TBN" as used herein refers to "temporary block number" or "temporary BN" and represents a number in a number space different from the number space in which the BN is located, thus preserving the number space used by the table and actively The number space used by the table is relative. In this way, one TBN and one BN can be distinguished. For example, one TBN and one BN can be distinguished by the highest bit of the number. When a track point (such as a branch point) contains content that is BN, the instruction segment containing the branch target instruction has been filled into the high level memory 124. On the other hand, when the content of the track point is TBN, the instruction segment containing the branch target instruction has not been filled into the high level memory 124. Thus, when a track contains multiple branch points, since some branch points may never be accessed, using TBN instead of BN can reduce the amount of memory padding and save one level of cache space.

In this way, a reserved table can be used to improve system performance and reduce storage capacity requirements. FIG. 12 is an embodiment of establishing a new track using the track table 126, the reservation table 120, and the active table 121.

As shown in FIG. 12, the established track 66 (BNX0) may include three branch points 67, 68, and 69. For ease of description, the BNX number is used to mark tracks or lines in the track table 126. When the branch point 67 is examined, the address of the target instruction of the branch point 67 is stored in the entry 73 of the reservation table 120 (labeled as TBNX0), and the number of the entry 73 (ie, TBNX0) is stored as the first address. In branch point 67. When the branch point 68 and the branch point 69 are examined, the addresses of the target instructions of the branch point 68 and the branch point 69 are also stored in the reservation table 120 (labeled as TBNX1 and TBNX2). Similarly, the numbers of the two entries are stored as the first address in branch points 68 and 69, respectively.

Further, when the processor core 125 is about to execute the branch instruction 67, the target address in the entry 73 of the reservation table 120 is transferred to the entry 74 of the active table 121. In some embodiments, the total number of entries in the active table 121 is equal to the total number of rows in the track table 126, such that the entries of the active table 121 can have a one-to-one correspondence with the rows of the track table 126. Thus, based on the correspondence 75, a branch target new track 70 including the branch point 67 can be established in the track table 126 according to the corresponding entry (BNX1) in the active table 121. The TBNX0 number in branch point 67 is also replaced with BNX1 so that the next time this instruction is to be executed, the BNX1 can directly index to the target track and the corresponding memory block without going to the reserved list.

Therefore, the corresponding new track is only established when the branch instruction is about to be executed. Thus, before the branch point 67 is executed, the target addresses of the branch points 68 and 69 are stored in the reservation table 120, and new tracks corresponding to the branch points 68 and 69 are not established.

Returning to Fig. 10A, when the processor core (125) is turned on, the reset signal (not shown) puts the valid position '0' of each entry in the active list 121. When the processor core reset signal is released, the reset vector (the instruction address value of the reset start point) is placed on the bus 141. Because no match is found in both the reservation table 120 and the active table 121, the reservation table 120 places the address value on the bus 144 and sends it to the fill engine 132 for obtaining instructions from the lower memory 122 via the bus 154. Segment (eg: reset vector).

The indicator 129 points to the current entry in the active list 121 through the bus 153, and the indicator 129 points to an instruction in the high-level memory 124 or stores the memory block of the acquired instruction segment.

The generator 130 extracts the track information related to the instruction in the instruction segment and writes the corresponding entry in the track table 126 pointed by the indicator 129 through the address bus 153. When the padding operation is completed, the valid bit of the current entry of the active table 121 is set to '1'. Thereafter, the indicator 129 moves to the next valid entry of the active list 121.

The generator 130 scans each instruction in the instruction block that is filled into the high level memory 124. When the generator 130 finds a branch instruction, the target address of the branch instruction is calculated. The target address may be represented as a start address (source instruction segment address) of the instruction segment containing the branch instruction plus a shift of the transfer from the start point, plus a branch distance from the source instruction to the target instruction (usually the branch offset). The calculated upper bits of the target address are used to match the contents of the reservation table 120 and the active table 121.

If the matching between the reservation table 120 and the active table 121 is unsuccessful, the upper address is written into the entry indicated by the indicator 127 in the reservation table 120, and the value of the indicator 127 and the lower address of the target address are The target offset address (both together form a TBN) is placed in the track table 126 in an entry indicated by the bus 153 (branch source row address) and by the bus bar 143 (branch source offset address). Bus 143 may provide a column address corresponding to the offset of the branch instruction in its associated instruction segment.

If there is a match in the reservation table 120, the value of the index 127 pointing to the match is written into the track table 126 as the TBN together with the target offset by the bus bar 153 (row address) and the bus bar 143 (offset) Quantity) The determined item. If there is a match in the active list 121, the matched active entry and the offset are written as a BN to the table indicated by the bus bar 153 (row address) and the bus bar 143 (offset) in the track table 126. item. The instruction corresponding to the target address appearing in the form of TBN has not been filled into the high-level memory 124, and the instruction corresponding to the target address appearing in the form of BN has been filled into the high-level memory.

The above process is repeated until the entire instruction segment is acquired and populated into the high level memory 124. Thus, passive table 120, active table 121, and track table 126 contain information about the instruction segments, and high level memory 124 contains the entire instruction segment for execution by processor core 125. The active table 121 contains the start (segment) address values of the instruction segments for subsequent instruction segments to match, and the track table 126 contains all of the branch points and corresponding target TBN or BN values in the instruction segment.

When the tracker 170 outputs a BN 151 for indicating an entry in the track table 126, the contents of the entry are read through the read port 161. If the content display is not a branch point, then the subsequent operations are the same as the corresponding operations in the embodiment of Fig. 7A. However, if the content is displayed as a branch point, the branch target address (BN or TBN) is read out to the switch 133.

Since the branch target address can correspond to one entry in the reservation table 120 (ie, one TBN) or one entry in the corresponding active table 121 (ie, one BN), the switch 133 can be used to reserve the table 120 and the active table 121. The entries in the table are exchanged. The switch 133 sends the TBN through the bus bar 180 to the reservation table 120 to initiate an operation of filling the memory block from the lower level memory to the high level memory 124, and outputs a BN after the exchange is completed. This pre-filling ensures that the processor can find them in the high-level memory 124 when it needs to execute instructions.

As shown in FIG. 13, the switch 133 includes a TBNX table 190 and a BNX table 191. The entries in the TBNX table 190 correspond to the entries in the active table 121 and can be used to map entries transferred from the active table 121 to the reserved table 120. The content of each entry in the TBNX table 190 may include the entry number of the corresponding entry in the reservation table 120 and a flag bit G bit.

The entries in the BNX table 191 correspond to the entries in the reservation table 120 and can be used to map entries from the reservation table 120 into the active table 121. The content of each entry in the BNX table 191 may include the entry number (ie, BN) of the corresponding entry in the active table 121 and a valid bit.

In addition, the track information outputted from the track table 126 to the bus bar 150 may also include a G bit 192 corresponding to the G bit in the TBNX table 190 for indicating that the BNX value is currently present in the active list. The BNX value can be directly output; otherwise, mapping is required.

When an entry in the active table 121 is transferred to the reservation table 120, the corresponding entry in the TBNX table 190 is used to record the entry number (BN) 172. Similarly, when one of the entries in the reservation table 120 is transferred to the active table 121, the corresponding entry in the BNX table 191 is used to record the entry number of the entry and the valid location is valid.

When the track point information on the bus bar 150 contains the entry number of the reservation table 120, the entry number TBNX is used as an index to read the BNX value and the valid bit from the BNX table 191. If the BNX value is valid (i.e., the valid bit is set to be valid), the BNX value is output as BNX in the next BN 166 and sent to the tracker. On the other hand, if the BNX value is invalid, the TBNX is used as an index to read content from the reservation table 120 through the bus bar 180, and initiates filling of the TBNX from the low-level memory 122 to the high-level memory 124. The operation of the corresponding memory block.

When the track point information on the bus bar 150 includes the entry number (ie, BN) of the active table 121, if the G bit in the track point information on the bus bar 150 and the G of the corresponding entry in the TBNX table 190 When the bits are equal, the BNX value is output as BNX in the next BN 166. On the other hand, if the G bit in the track point information on the bus bar 150 is not equal to the G bit in the corresponding entry in the TBNX table 190, the entry number in the reserved table 120 is read from the TBNX table 190 and is The BNX value and the valid bit are read out from the corresponding row in the BNX table 191 as an index. If the BNX value is valid, the BNX value is output as BNX in the next BN 166. On the other hand, if the BNX value is invalid, the content of the entry in the reservation table 120 is used as an index to read the content from the reservation table 120 through the bus bar 180.

Thus, as long as there are valid entries in the TBNX table 190 and the BNX table 191, a replacement module 193 maintains a scan of the track table 126 and reads track point information from the bus 159. If the track point information of a track point includes an entry number of the active table 121, and the entry number corresponds to a valid entry in the TBNX table 190, the entry number of the reserved table 120 is output through the bus bar 158, and The track point information is changed to the item number in the reservation table 120. Similarly, if the track point information of a track point includes an entry number of the reserved table 120, and the entry number corresponds to a valid entry in the BNX table 191, the entry number of the active table 121 is output through the bus bar 158. And changing the track point information to the item number in the active table 121.

The exchange between the entries in the TBNX table 190 and the entries in the BNX table 191 can be achieved by scanning the entire track table. Such exchanges can be made at various times. For example, if the active table capacity is full, it means that the high-level memory 124 is full. Some of the memory blocks in the high level memory 124 can be replaced, as are the active tables. The replaced entries in the active table can be moved to the reservation table, and the BNX guidelines in the track table need to be exchanged for new TBNX guidelines. After the exchange process is completed, the previous entries in the TBNX table 190 and the BNX table 191 can be set to be invalid.

Returning to Fig. 10A, when the branch point contents are sent to the switch 133, and the switch 133 completes the corresponding operation of the track table read port 161, it means that the high-level memory 124 already has an instruction segment containing the branch target instruction. Then, the result BN is directly output to the tracker 170. Subsequent operations are similar to those in Figure 7A. FIG. 10B shows a portion of the cache system 9000 showing an embodiment of operating the track table 126, the high level memory 124, and the processor core 125 using the passive table 120 and the active table 121.

As shown in FIG. 10B, similar to FIG. 7B, the tracker 170 includes an auto-incrementer 136, a multiplexer 137, and a register 138. Other components are omitted for convenience of description. During operation, tracker 170 outputs an address (i.e., BN 151) for addressing track table 126 and high level memory 124. BN 151 includes BNX 152 and BNY 156. BNX 152 can be used to address one row or track in track table 126 and address a memory block in high level memory 124, at which point BNY 156 can be used in track table 126 by BNX An entry in the track or row pointed to by 152 is addressed.

In addition, multiplexer 137 is controlled by signal 381 from processor core 125 to select the next BN 166 from switch 133 or the BN from auto-incrementer 136 as output 418. Output 418 (i.e., next BN) from multiplexer 137 may be stored in register 138 under the control of signal 417 from processor core 125. Register 138 does not update output 418 when register 138 is controlled by signal 417 to keep current BN 151 unchanged. On the other hand, when the register 138 is controlled by the signal 417 to update the current BN 151, the output 418 is sent to the bus bar 151 to become the current BN 151, thereby updating the BNX 152 and the BNY 156.

To describe the relationship between the track table 126 and the tracker 170, similar to FIG. 7B, it is assumed that the track table 126 includes tracks (ie, rows) 410, 411, and 412. Each track can contain 16 entries or track points from 0 to 15. Further, the track point 413 (the eighth item in the track 410) may be a branch point where the branch target is the track point 414 (the second item in the track 411), and the track point 415 (the 14th item in the track 411) may Is another branch point whose branch target is track point 416 (the fifth item in track 412).

It is assumed that the instruction segment corresponding to the track 410 has been filled in the high level memory 124, and the processor core 125 executes the instruction from the start position of the track 410. That is to say, the program counter (PC) of the processor core 125 starts from the instruction address corresponding to the 0th entry in the track 410.

At the same time, it is assumed that the tracker 170 also sends a read indicator 151 containing the 0th item of the track 410 in the track table 126 of BNX and BNY. Other entries in track 410 can also be used. The type information, address information, and the like of the instruction can be determined by checking the contents of the entry.

As described earlier, when running from the 0th item of the track 410, since the 0th item of the track 410 is not a branch point, the tracker 170 keeps the BNX 152 unchanged and increases BNY by the booster 136, thereby The next BN of the next entry in the track 410 in the corresponding track table 126 is obtained. The tracker 170 continuously increments BNY to move to the next entry in track 410 until a branch point is reached, such as track point 413 (item 8 in track 410). In this process, there is no change in the instruction segment address since BNX has not changed. The processor core 125 can continuously fetch instructions from the high level memory 124 using the offset of the PC.

When the tracker 170 reaches the track point 413 (the eighth item in the track 410), since the track point 413 is a branch point, the source address and the content of the entry, that is, the target address are analyzed. The switch 133 can check the target address in the form of BN or TBN. If the target address is a BN, the instruction segment corresponding to the target address has been filled into the high level memory 124 and is ready to be read by the processor core 125. On the other hand, if the target address is a TBN, the instruction segment corresponding to the target address has not been filled into the high level memory 124. Thus, if the instruction segment corresponding to the TBN is not in the high level memory 124, the instruction segment is filled into the high level memory 124. And as previously described, switch 133 converts TBNX to BNX and sets the value of BNY to the value of TBNY. Thus, the switch 133 can provide a BN that is sent out as the next BN 166. The switch 133 can provide a BN as the next BN 166 regardless of whether the entry is BN or TBN.

Moreover, if the instruction segment containing the next instruction of the source address has not been filled into the high level memory 124, then the instruction segment is also populated into the high level memory 124 for possible execution by the processor core 125. However, for track point 413, since the next instruction is the ninth entry of track 410 and the instruction segment of corresponding track 410 has been filled into high level memory 124, the next instruction of track point 413 does not need to be filled. Thus, only when the instruction segment corresponding to the track 411 including the branch target (the second entry of the track 411) has not been filled, is it filled into the high-level memory 124.

Since the tracker 170 moves at the command track point faster than the processor core 125 executes the instructions, both instruction segments that the processor core 125 can execute can execute any of the two instruction segments at the processor core 125. The instructions are previously filled into the high level memory 124. This will not cause a cache miss. BNY 156 may be considered part of the lead indicator (BNX is unchanged in the same track) to populate high level memory 124 with instructions that processor core 125 may execute before processor core 125 executes the instructions.

Thus, since the TBNX in the reservation table 120 does not automatically fill the high-level memory 124, a large number of entries in the track or track table 126 can be generated in a short time. The instructions may be populated into the high level memory 124 when the execution stream approaches the instruction (eg, a branch target instruction).

Moreover, when track point 413 is reached and the associated instruction segment has been filled into high level memory 124, track table 126 or switch 133 can provide branch target BNX of 411 and BNY of 2 as the next BN 166 (track 411 The second entry), and the tracker 170 can wait for a signal 381 sent by the processor core 125 when the branch instruction of the track point 413 is executed, indicating whether a branch transfer has occurred.

If branching occurs as in this embodiment, track table 126 or switch 133 uses next BN 166 as BN 151 for tracker 170, where BNX points to track 411 and BNY points to the second entry of track 411. At the same time, BNX is also used as an address corresponding to the instruction segment in the high level memory 124, so that the processor core 125 can execute the instruction from the second entry of the track 411. However, if branch branching does not occur, the tracker 170 or leading indicator moves forward as if the branch point was simply treated as a non-branch point.

Similarly, starting from the second entry of the track 411, the tracker 170 finds the branch track point 415 of the next branch target as the track point 416 (the fifth entry of the track 412) (the 14th table of the track 411) item). Then, if the instruction segment of the corresponding track 412 has not been filled into the high level memory 124, the instruction segment is filled into the high level memory 124, and as described above, the leading indicator waits for the track point 415 branch instruction to execute.

Furthermore, the above discussion is based on a layer of orbital operations. That is to say, the leading indicator listens to the first branch point, that is, the corresponding two branches of the first branch point result in corresponding filling operations. The track table 126 can also support two layers of track operations or multiple layers of track operations. For example, in a two-layer track operation, the lead indicator can stop at the first branch point after the first branch point. Thus, the instructions corresponding to the four possible outcomes of the two branch points are filled into the high level memory 124. Similarly, more instructions can be filled with multiple layers of track operations.

It will be appreciated that while the reservation table 120, the active table 121, and the switch 133 are used to achieve a more flexible and efficient operation of filling the high level memory 124, as previously described, a table or other structure may be used. achieve.

Furthermore, returning to FIG. 10A, in operation, more tracks can be added to the track table 126 and corresponding instructions are populated into the high level memory 124. However, the capacity of track table 126 and/or high level memory 124 is limited. An alternate mechanism is needed to replace the tracks in the track table 126 and/or the instruction segments in the high level memory 124. For example, an alternative mechanism based on active table 121, reserved table 120, and track table 126 can be used. In particular, an entry in the active list 121 that can be replaced can be determined.

It is assumed that the content TBNX value '118' sent by the track table 126 through the bus bar 180 is used to fill an instruction segment into the high level memory 124, and the instruction segment address 0x1FC0 corresponding to the TBNX value '118' is stored in the reserved table 120. The entry pointed to by the bus bar 153 in the active table 121 stores a BNX value of '006', and the corresponding command segment address is 0x4000. Thus, the address 0x1FC0 in the read reservation table 120 is sent to the bus 144 for replacing the address 0x4000 in the active table 121, and the address 0x1FC0 is sent to the fill engine 132 for filling the instruction segment from the address 0x1FC0 to The high level memory 124 replaces the instruction segment starting from address 0x4000. Further, the entry containing the BNX value '006' corresponding to the address 0x4000 is moved to the entry in the reservation table 120 pointed to by the indicator 127.

An alternative strategy can also be used to determine which entry or storage unit in the track table 126 should be replaced. For example, a least recently used policy or a least frequently used policy can be employed. When using the least recently used policy, each track or track point contains one usage bit (U bit); when using the least frequent usage policy, each track or track point contains a counter that records the number of uses.

In some cases, more than one layer of cache structure can be used. Distributor 1200 or active table 121 can be used to support more than one layer of cache structure. Figure 11 shows an embodiment of an allocator or reservation table for a multi-layer cache structure.

In this embodiment, a three-layer storage hierarchy is taken as an example, which is three levels, two levels, and one level. For the sake of explanation, it is assumed that these three layers of memory are used as instruction memory (data memory is similar). The capacity of the secondary memory is twice the capacity of the primary memory (ie, one secondary memory block can contain two primary memory blocks), and the tertiary memory capacity is twice the secondary memory capacity (ie, A three-level memory block can contain two secondary memory blocks or four primary memory blocks). The primary memory is directly connected to the processor core 125 as a high level memory. For the case of more storage tiers, the method of the invention can also be applied.

In addition, for convenience of description, the third-level memory contains all the contents of the secondary memory and the primary memory, but the secondary memory does not necessarily contain the content in the primary memory. Although not shown in the figure, a track table can be used to build the tracks of the instructions in the three-layer memory, and each track point (such as a branch point) can be represented by one of the two formats shown in FIG. One format consists of two parts, the high-order to low-order bits being the block address portion of the first-level memory index address, and the offset portion within the track or within the memory block. The other format consists of three parts, the block address part of the three-level memory index address, the index and the offset part.

As shown in FIG. 11, the distributor 1200 or the reservation table 120 may include a content addressed memory (CAM) 87 and a random access memory (RAM) 98. The CAM 87 contains a list item, and each entry in the CAM corresponds to a three-level memory block number BNX3. Thus, each entry can contain an address corresponding to a particular BNX3 level three memory block.

In addition, the RAM 98 may include six columns, wherein two columns 88 are used to store two secondary memory block numbers BNX2 and valid bits corresponding to a particular three-level memory block, and the other four columns 89 are used to correspond to four of the three-level memory blocks. One level track number BNX1 and valid bits. The multiplexer 93 can select a particular one-level memory block number or track number corresponding to the three-level memory block based on the index bit 97. Similarly, multiplexer 92 may select a particular secondary memory block number or track number corresponding to the tertiary memory block based on index bit 97, and more specifically upper bit LSB1 90 in index bit 97.

This table can be accessed in two ways. One is to search for CAM 87 using a storage address (eg, a three-level memory block address). If there is an address match, the matching entry in the CAM is selected and the contents of the corresponding RAM 98 are read. The other is to address directly in CAM 87 and RAM 98 with the first address BNX3 94 of the three-level memory block number TBN, reading the contents of the selected row in CAM 87 and/or RAM 98.

As described in the previous examples, the filled instructions are scanned and detected when the instruction segments are filled from the main memory or any external memory into all of the three levels of memory. When a branch instruction is detected, the branch target address of the branch instruction is used to compare with the level three memory block address stored in CAM 87.

If no match is found, this means that the instruction segment corresponding to the branch target address is not yet included in the third level memory. At this time, according to a certain criterion, such as a replacement strategy, a third-level memory block in the three-level memory is selected, and the instruction segment in which the branch target is located is filled into the memory block. At the same time, the memory block address information in the selected three-level memory is filled as the track point content into the corresponding entry of the branch point in the first-level track table. The block number of the selected three-level memory block is used as the first address BNX3 94, the index portion in the storage address is used as the index number 97, and the offset portion in the storage address is used as the offset. Quantity (BNY) 96. In addition, the index number 97 may include 2 bits, wherein the upper bit LSB1 90 is used to distinguish two memory blocks in the secondary memory, and the upper LSB1 and the low bit LSB0 97 are used together to distinguish four of the first-level memories. Memory block.

On the other hand, if a match is found, it indicates that at least the required block of instructions is stored in the level three memory. At this time, the matched BNX3 is filled in the track entry together with the index number and the offset as the track point content.

During the running process, when the leading indicator reaches the track entry, the branch target address displayed by the track entry or the track point is the TBN of the third-level memory. The first address (94) in the TBN can be addressed to CAM 87 and/or RAM 98.

In particular, the RAM 98 can be addressed and read out using the first address 94 of the primary track (BNX3) and the corresponding two secondary track numbers and significant bits and four primary track numbers and significant bits can be read. The multiplexer 93 selects a valid primary track number from the four primary block numbers based on the index bit 97 (i.e., LSB1, LSB0) and the valid bit V. In addition, multiplexer 92 selects a valid secondary track number from the two secondary block numbers based on index high 90 (i.e., LSB1) and valid bit V.

If a valid first-level track number is selected, it indicates that the instruction segment corresponding to the target address has been filled into the primary memory, and the valid primary track number is directly sent to the bus 99 to replace the branch instruction. First address. At the same time, the corresponding index is discarded, and the intra-block offset (BNY) is unchanged. This way TBN becomes BN. In addition, since a three-level memory block contains four first-level memory blocks, a single-level memory block number cannot be determined by BNX3 94 alone. BNX3, together with index 97, determines a particular level 1 memory block number. In the four primary memory blocks, zero, one, two, three or four primary memory blocks corresponding to the three-level memory blocks may be included. Similarly, in two secondary memory blocks, zero, one, or two primary memory blocks in the corresponding three-level memory block may be included.

On the other hand, if no valid primary track number is selected, it indicates that the instruction segment corresponding to the target address has not been filled into the primary memory. If a valid secondary block number is selected, it means that the instruction segment corresponding to the target address has been filled into the secondary memory, and the valid secondary block number can be sent to the bus 91. At this time, the instruction segment corresponding to the secondary memory block number can be filled into the primary memory from the secondary memory, and the block number and the valid bit of the corresponding primary memory block in the RAM 98 are updated to correspond to the filled Instruction segment. For example, the primary block number (BNX1) in the entry pointed to by the BNX3 and the index in the RAM 98 and its valid bit may be updated, and the track entry content format is updated to the BN number using the primary track. The BN number includes a first address (ie: BNX1) and a second address (ie, offset or BNY).

If no valid secondary track number is selected, meaning that the instruction segment corresponding to the target address has not been filled into the secondary memory, the instruction segment corresponding to the tertiary track number is filled from the tertiary memory to Secondary memory and primary memory. Corresponding portions of RAM 98 are also updated to correspond to the filled instruction segments in the primary and secondary memory. For example, the primary block number (BNX1) in the entry pointed to by the BNX3 and the index in the RAM 98 and its valid bit may be updated, and the track entry content format is updated to the BN number using the primary track. If the secondary memory block is also populated, the secondary block number (BNX2) in the entry in the RAM 98 and pointed to by the index and its valid bit can also be updated.

When the instruction segment is filled, the instruction segment can be filled from the third-level memory to the secondary memory and then from the secondary memory to the primary memory. Alternatively, in the case where there is an independent path between the third-level memory and the first-level memory, the instruction segment can be read from the third-level memory while the instruction segment is filled from the third-level memory to the secondary memory. The body is filled to the primary memory. In addition, if the track point in the primary memory contains only the primary track information, it can also be operated in a similar manner as before.

Figure 14A is another embodiment 10000 of the cache system of the present invention. Cache system 10000 is similar to cache system 9000 in Figure 10A. However, cache system 10000 includes certain features for supporting multi-threaded programs.

Different tracks in track table 126 may correspond to one thread or multiple threads. Since the thread state needs to be saved and restored when the online content is switched, a plurality of stacks 135 are used for respectively storing the information of the thread stack. A thread identification (PID) 188 stores the current thread identification or thread number. When the tracker 170 uses the stack 135, the PID 188 provides an indicator to the stack for proper stack operation.

Additionally, a second fill/builder 187 can be provided outside of the low level memory 122. The generator 186 in the fill/builder 187 is similar to the generator 130 in the fill generator 123, but has a higher bandwidth than the generator 130. That is, generator 186 can scan and review more instructions at a time. Further, the operation of the padding/generator 187 for the reservation table 120 is also similar to the operation of the pad generator 123 for the active table 121. Thus, the fill engine 185 fills the instruction segments corresponding to the addresses in the reserved table 120 from the lower level memory (not shown) into the lower level memory 122. Thus, the instruction segments corresponding to the addresses in the reservation table 120 are stored in the low level memory 122, thereby reducing or eliminating the time waiting for the processor core 125 to fetch.

In addition, different tracks can correspond to the same instruction segment (the same instruction segment can be stored in different level 1 cache memory blocks due to different virtual address addresses). The pad/generator 187 may also include a translation translation buffer (TLB) 131 located outside of the padding engine 185 such that instructions in both the low level memory 122 and the high level memory 124 are in physical address mode, while the processor core 125 Instructions can be fetched directly from the high level memory 124 without virtual to physical address translation.

Figure 14B shows an integral part of the cache system 10000. As shown in FIG. 14B, each entry in the active list 121 may correspond to a memory block or instruction segment in the high level memory 124 and correspond to a track in the track table 126. In this way, the high level memory 124 can be managed by the active table 121. On the other hand, the low-level memory 122 can also be used as a cache, and the low-level memory 122 can be managed by the reservation table 120. Thus, each entry in the reservation table 120 can correspond to a memory block or instruction segment in the low level memory 122. Further, for convenience of description, it is assumed that the high-level memory 124 and the low-level memory 122 are not included in each other. In other words, the content or memory block corresponding to any one of the storage addresses does not exist in both the high level memory 124 and the low level memory 122.

When the instructions are populated into the high level memory 124, the generator scans and reviews the instructions and may create a track containing the branch points in the track table 126. The branch target address is matched with the entry in the active table 121. If the matching is successful, indicating that a corresponding memory block has been filled into the high level memory 124, the matching block number in the high level memory 124 in the track table 126 is recorded as the branch target address in the BN format. However, if the match is unsuccessful, indicating that the corresponding memory block has not been filled into the high level memory 124, then the branch target address is matched in the reservation table 120 to begin the padding process. Optionally, the branch target address may be successfully matched in the entries of the reserved table 120 and the active table 121 at the same time.

If the matching in the reservation table 120 is successful, indicating that the corresponding instruction segment has been filled into the low-level memory 122, the block number in the lower-level memory 122 in which the matching is successful in the TBN format is recorded as the branch target address in the track table 126. . If no match is successful in both the reservation table 120 and the active table 121, the fill engine 185 fills the corresponding instruction segment from the external memory (not shown) through the bus bar 423 into the low-level memory 122. The virtual to physical address translator 131 can convert and translate virtual addresses and physical addresses. Thus, the memory block filled in the low-level memory 122 contains the corresponding instruction segment, and the padded memory block number in the low-level memory 122 is recorded as the branch target address in the track table 126 in the TBN format.

During operation, when the leader indicator 156 reaches a branch track point in the track table 126 that includes the branch target address of the TBN format, as described earlier, a BN is generated in the active table 121, and the corresponding instruction segment is The low level memory 122 is filled into the high level memory 124. Further, the TBN in the track table 126 is replaced with the BN, and the TBNX corresponding to the TBN stored in the reservation table 120 is cleared.

Thus, when an instruction segment corresponding to an entry in the reservation table 120 is filled into the high level memory 124, the associated TBN is replaced with BN. Similarly, when an instruction segment corresponding to an entry in the active table 121 is replaced or backfilled to the lower level memory 122, the associated BN is replaced with a TBN. By exchanging the entries in the reservation table 120 and the active table 121, an efficient multi-level cache operation can be realized.

Although different embodiments are respectively shown in different figures, these embodiments may be implemented independently or in some combination. Thus, the various components of these embodiments may be used alone or in combination without departing from the principles of the invention. For the convenience of description, some specific examples are given below.

For example, generator 130 can be used to extract branch source addresses to index the writes to track table 126. A source address (such as the address of an instruction) can be analyzed in two formats. In one format, a higher address portion, an index portion, and an offset portion are used to represent the address in the case of a multi-layer cache hierarchy or a storage hierarchy, and in another format, a high or block bit is used. The address portion and an offset portion represent the address. In some cases, the branch source address may be represented by a high order address portion, an index portion, and an offset portion. In addition, BNY can be used directly as the offset portion, and the upper address and index are sent to the distributor 1200 for conversion to a block number. Generator 130 can also be used to extract instruction types (eg, unconditional branches, conditional branches, non-branches (including loads, store instructions, etc.)).

Furthermore, generator 130 can be used to calculate a branch target address by adding a branch source address to a branch offset, wherein the branch source address can be a block address of an instruction segment containing the branch source instruction The offset of the branch source instruction in the instruction segment is added, and the branch offset can be an amount of a jump. The upper address and index of the branch target address are sent to the bus bar 141 to match the contents of the CAM in the distributor 1200 (eg, the active table 121, the reserved table 120). The offset address is sent to the bus bar 143 WYADDR as the Y write address of the track table 126. A write address for track table 126 may be an address for establishing a track point entry in track table 126, including a row address (X address) corresponding to XADDR and a column bit corresponding to YADDR. Address (Y address).

Thus, generator 130 provides the branch source address as a write address for track table 126 and provides the instruction type and branch target address as the write content for track table 126. Generator 130 generates all of the addresses except the X address in the write address, and the X address is modified or assigned by allocator 1200. The X address may be a block number (BN) corresponding to a particular upper address, which may itself be too long and discontinuous. For example, an 18-bit high-order address corresponds to 256K different memory blocks, but using a BNX number to allocate the high-order address to 256 blocks requires only 8 bits.

The track table 126 can be configured as a two-dimensional table structure in which each row is indexed by an X address or a first address BNX, corresponding to a memory block or a storage row, by a Y address or a second address BNY pair. Each column index corresponds to the offset of the corresponding instruction (data) in the memory block. In simple terms, the write address of the track table corresponds to the branch source instruction address. In addition, for a particular branch source address (eg, high address, index, offset), allocator 1200 (ie, active table 121) assigns a BNX to bus 153 based on the high address and index, and BNY is equal to the offset. Then, the BNX and BNY can form a write address that points to the written entry.

In addition, for the branch point, its branch target address (higher address, offset) is sent to the active table 121 to match the upper address, and the active table 121 may allocate a BNX. The allocated BNX, together with the instruction type and offset (BNY) from the generator 130, constitutes the content of the branch source instruction correspondence entry in the track table.

Track table 126 can also be used for other purposes. For example, in one system, track table 126 can be used to implement automatic power management of processor core 125. For example, one of the tracks in the track table 126 can be designated for storing an idle task (ie, an idle track) that is executed when the processor core 125 is in an idle state. In this way, the system can record the percentage of idle tracks that are used or accessed. The system can adjust the power consumption of processor core 125 and the system by comparing the percentage to a pre-set value or a set of pre-set values. The adjustment method can include changing the clock frequency or adjusting the supply voltage to the processor core 125 and the system.

Tracker 170 can be used to provide a read indicator 151 to track table 126. The read indicator 151 can also be in the form of BNX and BNY. The contents of the track entry pointed to by the read indicator are read along with the BNX and BNY (source BNX and source BNY) of the entry and are checked by the switch 133. If the content of the entry contains a TBN, then TBNX is sent to the distributor 1200 for processing or conversion to a BNX and fills the primary cache, after which the BN (BNY equals the value of the TBNY) is sent by the switch 133. To the tracker 170. The tracker 170 can perform a number of different steps depending on the content. For example, if the entry is not a branch point, the tracker 170 may update the read indicator with a new BNX equal to the source BNX, a new BNY equal to the source BNY plus one.

If the entry is a conditional branch, the tracker 170 acquires the target BNX and BNY (ie, the first address and the second address) and sends the target BNX and BNY to the distributor 1200 (ie, the active table 121). To fill the high-level memory 124 or the first-level cache. In addition, the tracker 170 can wait for a control signal from the processor core 125 corresponding to the branch point. If the control signal indicates that the branch has not occurred, the tracker 170 may update the read indicator with a new BNX equal to the source BNX, a new BNY equal to the source BNY plus one. However, if the branch succeeds, the tracker 170 may update the read indicator with a new BNX equal to the target BNX and a new BNY equal to the target BNY.

If the entry is an unconditional branch (or jump), the tracker 170 can treat it as a conditional branch with conditions, that is, update the read indicator with a new BNX equal to the target BNX and a new BNY equal to the target BNY.

In addition, if the entry is a "call" instruction, the tracker 170 can push the BNX and BNY pairs of the current indicator onto a stack, read the contents of the entry or indicate that the corresponding instruction segment has been stored in the first level cache. BNX. In addition, if the entry is a "return" instruction (eg, the end of the subroutine), the tracker 170 can pop the BNX and BNY pairs from the stack and use the new BNX to be equal to the popped BNX, new BNY. A method equivalent to popping the BNY updates the read indicator. In some cases, if the subroutine asks to return to the next instruction of the "call" instruction, then the new BNY is equal to the stack BNY plus one.

Further, if the entry is an exception handling instruction, the tracker 170 can read out the block number BNX and the offset BNY held in the exception BN register (EXCP), and equalize the abnormal BNX with the new BNX, and the new BNY is equal to the exception. The BNY method updates the read indicator. The start address of a particular processor's exception handler is usually fixed. The start of the exception handler can be filled into the level 1 cache and the corresponding track can be created in the track table (both can be set to not be replaced). ).

The allocator 1200 can be composed of a one-dimensional list of multi-entry items. Each entry includes a CAM with a high address and a RAM with BN, a valid bit, a U bit, and other flag bits. The allocator 1200 includes an auto-incrementer (APT) 129 and an adder to point to an entry that can be indexed (addressed) by a TBNX (Fig. 10A). When a cache fill is required, the entry pointed to by the APT 129, its corresponding memory block, and the track entry are populated.

In some cases, the allocator 1200 (e.g., reservation table 120, active list 121, etc.) can be used to provide an address mapping relationship for an address-BNX-TBNX. For example, TBNX can be used to index high-order addresses or BNX, and high-order addresses can be used to find BNX or TBNX by high-order address matching. When the level 1 cache is filled, the generator 130 calculates the branch target address and sends the upper address address via the bus 141 to the CAM portion of the reservation table 120 for high bit address matching. If the match is unsuccessful, the allocator 1200 can use the entry number pointed to by the indicator 127 as TBNX and use the TBNX as the track table content. At the same time, the allocator 1200 can fill the second level cache block corresponding to the TBNX. On the other hand, if the match is successful, the distributor 1200 can find the corresponding TBNX and use the TBNX as the track table content.

Further, during the operation of the tracker 170, when the track table read indicator 151 points to a track entry containing a TBN, the TBN is read through the read port 161 and sent to the bus bar 180 to index the reservation table 120. (ie, check if there is a corresponding instruction segment in the L2 cache). If there is no valid BN, the BNX pointed to by the APT 129 is stored in the entry of the RAM portion of the TBN, and the TBN in the track table 126 is replaced with the BN. In addition, the corresponding instruction segment in the L2 cache is padded into the L1 cache buffer block indexed by the BN. However, if there is a valid BN, meaning that the instruction segment corresponding to the entry already exists in the primary cache, then the TBN is replaced with the valid BN. Of course, when the track table read indicator 151 points to an entry whose content contains BN, the distributor 1200 does not need to check because the corresponding instruction segment is already stored in the level one cache.

In addition, the distributor 1200 can also support different configurations for the active table 121 and the reservation table 120. For example, for the inclusion relationship of the entries in the active table 121 and the reserved table 120, the distributor 1200 can have two configurations.

In one configuration, as depicted in FIG. 13, an unrelated relationship is created between the active table 121 and the reserved table 120. To generate such a non-containment relationship, the reservation table 120 and the active table 121 each have a CAM for storing a high-order address. The address from the generator 130 is simultaneously sent to the active table 121 and the reserved table 120 to match to obtain TBNX or BNX. However, it is only possible that one of the active table 121 and the reserved table 120 is successfully matched, and it is not possible that the matching between the active table 121 and the reserved table 120 is successful at the same time, that is, a specific instruction may only exist in the first level cache and the second level. One of the caches, not both. As shown in FIG. 11, the reservation table 120 is indexed by TBNX, its CAM stores the upper address, and its RAM stores the corresponding BNX number. You can use an index to select multiple BNXs in the same row or table entry. In addition, the active list 121 is indexed by BNX, its CAM stores the upper address, and its RAM stores the TBNX number.

In one configuration, an inclusion relationship is created between the active table 121 and the reserved table 120. In this relationship, only the upper address is stored in the CAM of the reserved table 120, and the reserved table 120 can be composed of a similar structure in FIG. However, the active table 121 does not have a CAM portion, so an address sent by the generator is only matched in the reserved table 120, which means that if a particular instruction exists in the level 1 cache, it must exist in the second level. In the cache. In addition, the active table 121 is indexed by BNX, and its content is only TBNX. When a level one cache block is cleared (or replaced), the old BNX is sent to the active list 121 to find a TBNX for storage in the track table 126. For the data memory, the level 1 cache block must be stored back into the cache memory corresponding to the reserved table 120.

In some cases, a one-tiered cache system can be used. Thus, the reserved table entry can be indexed by the TBNX corresponding to the primary memory rather than one of the memory blocks in the cache memory, and the upper address of the primary memory address is stored in the corresponding CAM entry. As usual, the RAM section contains BNX. Thus, the TBNX is temporarily saved in the track entry until the read index of the track table 126 is close to the entry, so that the memory block corresponding to the upper address can be filled into the cache (level 1 cache). Thereafter, the BNX can also be assigned to replace the TBNX in the track table 126. This BNX can also be saved in the RAM portion of the reserved entry indexed by the TBNX.

Additionally, the allocator 1200 can be used to assist in the implementation of a level one cache replacement strategy. For example, the allocator 1200 can support the least recently used policy and the least frequently used policy.

In the case of the least recently used policy, the allocator 1200 can use a least recently used window consisting of a primary indicator 129 (APT) and a clear indicator to find the next memory block that can be replaced. The clear indicator moves at the position of the N entries before the main indicator 129 (APT), where N is a variable number and the clear indicator is used to clear the U bit in the pointed entry (set to '0'). On the other hand, the U bit corresponding to the accessed entry is reset to '1'. Check the U bit of the entry pointed to by the primary indicator 129 (APT) to determine whether to replace the entry. If the U bit is '1', indicating that the entry was recently accessed, not the least recently used, then the primary indicator 129 is incremented and the next entry is checked. If the U bit is '0', the main indicator 129 can stay in the entry for replacement.

In the case of the least frequently used policy, the allocator 1200 can use the same window as above, but uses a counter that records the number of accesses (representing the access frequency) instead of the U bit. The value of the counter in the entry pointed to by the primary indicator 129 is compared to an adjustment value set by the processor core 125 or other device. If the count result is less than the adjustment value, the main indicator 129 can stay in the entry for replacement.

Switch 133 can be used to assist in the interaction between track table 126 and distributor 1200. For example, in the track table 126, when a BN is allocated to replace the TBN (for example, when a L2 cache block is filled into a L1 cache block), or when a TBN is allocated to replace the BN (for example, when The cache space is insufficient. When a level 1 cache block is replaced with the level 2 cache and replaced with the level 2 cache, the switch 133 will replace all the old ones in the track table 126 before the old TBNX (BNX) is reused. Replace TBNX (BNX) with the new BNX (TBNX). Thus, the same BNX will not correspond to two different PC addresses.

In particular, the switch 133 can store a set of old TBNX and new BNX pairs at the beginning of the allocation operation, and the switch 133 moves to the end along the track table, starting from the top of the track table 126 until reaching the departure point, utilizing additional readings. Bus 159 and additional write bus 158 replace all old TBNX with new BNX. At the same time, the switch 133 replaces the old TBNX in each readout with the new BNX before sending the BN to the tracker 170.

In addition, other components may be used to provide the functions required for the above operations. For example, processor core 125 may provide a control signal "TAKEN" to control multiplexer 137 in tracker 170.

Processor core 125 may also provide a control signal "BRANCH/JUMP" to control register 138 in tracker 170. The read indicator 151 moves forward (e.g., increases BNY) until the read track table content is a branch/jump type, the read indicator 151 stops and waits for the processor core 125 to catch up. At the same time, the necessity of checking the level 1 cache fill is checked according to the branch target address in the content. The BRANCH/JUMP signal indicates to the tracker 170 that the processor core 125 has reached the branch instruction. At this time, the TAKEN signal is the actual result of the program execution, and the correct lower address can be selected. Thus, when the BRANCH/JUMP signal is detected, the tracker 170 controls the register 138 to be stored in the new address and output as the BN 151. In addition, processor core 125 may also provide a partial address "OFFSET" to L1 cache 124 to index the instructions in the cache block determined by BNX 151's BNX.

The first level memory 124 or the high level memory 124 can be used as a cache block or a memory block indexed by BNX. The primary memory 124 can have a write buffer that receives data from the bus 140. For the write address, the X address (WXADDR) is provided by the allocator 1200, which is generated from the APT 129 via the bus 153, and the Y address (WYADDR, offset address) is acquired by the acquisition engine (synchronized with the filled data) provide. The primary memory 124 can include a read command for outputting data to the processor core 125. For the read address, the X address (BNX) is derived from the BN 151 provided by the tracker 170, and the Y address is derived from the OFFSET provided by the processor core 125.

Figure 15 shows another embodiment 11000 of the cache system of the present invention. Similar to cache system 9000 in Figure 10A, cache system 11000 can be used to obtain data rather than instructions. Thus, the table 120 and the switch 133 may not need to be retained.

The active table 195 for data storage has the same structure as the active table 121. Each entry in the active list 195 corresponds to a data segment in the high level memory 196. In addition, a base address indicator memory 197 is used to store the data segment number corresponding to the base address. The number of base address indices in the base address indicator memory 197 is the same as the number of base addresses used by the processor core 125, for example: 8. Other numbers can also be used. In addition, processor core 125 can address high level memory 196 with a base address plus offset. The offset can ensure that the address data does not exceed the range of the data segment corresponding to the base address.

It can also support multi-threaded programs. For example, as previously discussed, a plurality of stacks 135 can be used to populate instructions in the case of a multi-threaded program, and a plurality of base address pointer memory 197 can be used to populate the instructions in the case of a multi-threaded program. Thus, PID 188 can point to a current stack 135 and a current base address indicator memory 197. However, if only one thread is supported, only one stack 135 and one base address indicator memory 197 can be used, and PID 188 may not be needed.

When the generator 130 scans and analyzes the acquired instruction, if an instruction changes the base address of the data, the corresponding base address, immediate value, and register number are stored in the corresponding track point of the track table 126. in. Moreover, when processor core 125 executes the instructions, the base address or modified base address can be sent to active table 195 to match the content therein.

If the matching is successful, the entry number of the matching success item is sent to the base address memory 197 as the content of the base address index. Since the entry in the active table 195 corresponds to the data segment in the high level memory 196, the current base address index stores the base address of the corresponding data segment in the high level memory 196.

On the other hand, if the match is unsuccessful, the base address is sent to the fill engine 132 for filling the corresponding data segment. When the data segment corresponding to the base address is obtained, the base address is stored in an entry in the active table 195 pointed to by the indicator 198. The entry number of the entry described in the active table 195 is stored in a corresponding base address indicator in the base address indicator memory 197. Similar to the fill instruction, the indicator 198 moves to the next valid entry in the active list 195.

When the processor core 125 executes an instruction to access a material in the high level memory 196, the base address 189 of the instruction is read as an index to read the data segment number from the base address pointer memory 197. In addition, the data read and write address offset 194 is used as an index to find a data item from the data segment pointed to by the data segment number. The processor core 125 can read and write the data item.

Figure 16 is an embodiment of a memory structure implemented using the high performance cache structure of the present invention. The cache structure can be similar to the cache control unit described previously. As shown in FIG. 16, the storage device used by the processor core 201 includes (from high speed to low speed) in order: first level memory 202, second level memory 203, main memory 204, and hard disk memory 205. Generally, the capacity of the first level memory 202 is smaller than the capacity of the second level memory 203; the capacity of the second level memory 203 is smaller than the capacity of the main memory 204; the capacity of the main memory 204 is larger than that of the hard disk 205. The capacity is small. Any level of storage can be of any size.

In addition, a cache structure 206 is placed between the processor core 201 and the first level memory 202; a cache structure 207 is placed between the first level memory 202 and the second level memory 203; a buffer The structure 208 is placed between the second level memory 203 and the main memory 204; a buffer structure 209 is placed between the main memory 204 and the hard disk 205. Other placement methods can also be used. This multi-layered cache structure can improve the performance of the processor core 201.

For example, for the cache structure 207 between the first level memory 202 and the second level memory 203, since the processor core 201 needs to acquire an instruction from the first level memory 202, the first level memory 202 The instructions in the source are derived from the second level memory 203. Thus, when instructions are passed through the cache structure 207, the instructions can be scanned and analyzed, and they are also fetched into the first level memory 202 before the related instructions are executed, thereby simultaneously increasing cache hits for instructions and data. rate.

The cache structure 207 can be similar to the cache structure 206. The interface of the cache structure 207 and the first level memory includes an address bus 210, a read data bus 212, and a write data bus 211, and the interface of the second level memory 203. The address bus 213, the read data bus 214, and the write data bus 215 are included. Thus, the cache structure 207 can increase the hit rate of the first level memory 202.

Similarly, the cache structure 208 between the second level memory 203 and the main memory 204 can increase the hit ratio of the second level memory 203, and the cache structure 209 between the main memory 204 and the hard disk 205 can The hit rate of the main memory 204 is increased. If the hard disk 205 contains all of the instructions required by the processor core 201, the processor core 201 can achieve a high hit rate or performance through this multi-level cache structure.

In addition, the cache structure between slower speed memories can have a wider bandwidth, that is, more instructions or data can be acquired at one time. For example, the bandwidth of the cache structure 209 is wider than the bandwidth of the cache structure 208; the bandwidth of the cache structure 208 is wider than the bandwidth of the cache structure 207; the bandwidth of the cache structure 207 is wider than the bandwidth of the cache structure 206. It can also be configured in other forms.

Additionally, a separate bypass path 216 can be provided between the cache structure 208 and the first level memory 202. The instructions or data in the main memory 204 can be simultaneously filled into the second level memory 203 and the first level memory 202, thereby further improving the performance of the entire system.

The system and method of the present invention can provide a basic solution for the cache structure used by digital systems. Unlike the conventional cache system, which only populates after the cache is missing, the system and method of the present invention fills the instruction cache and the data cache before the processor executes an instruction or accesses a material, which can be avoided or fully hidden. Forced missing. That is to say, the cache system of the present invention integrates the prefetch process and eliminates the label comparison process necessary for the conventional cache. Moreover, the system and method of the present invention essentially provides a fully associative cache structure that avoids or substantially obscures conflicts of absence and capacity. Moreover, the system and method of the present invention supports simultaneous search for a multi-layer cache structure, thereby reducing the lack of penalty for multi-layer cache. The system and method of the present invention can also operate at higher clock frequencies because tag matching on the critical path of the latency of the access cache is avoided. Since the system and method of the present invention require fewer matching operations and a lower rate of misses, the efficiency at the same power consumption is also significantly improved over conventional cache systems. Other advantages and applications of the present invention will be apparent to those skilled in the art.

11, 12, 13, 14, 15, 16, 17. . . Instruction segment

30, 33, 35, 37, 38, 41. . . Program segment

31, 39. . . Conditional branch instruction

32, 34, 40. . . Transfer path

36. . . Unconditional branch instruction

46, 78. . . Instruction memory

48, 136. . . Increase one logic

49. . . Selector

50, 138. . . register

51, 52, 53, 54, 55, 56, 62, 64, 91, 99, 140, 141, 143, 144, 149, 150, 153, 154, 158, 159, 164, 165, 180, 423. . . Busbar

57. . . Type area

58. . . First address XADDR

59. . . Second address YADDR

61, 135. . . Stack

63. . . Thread identifier

65, 92, 93, 137. . . Multiplexer

66, 70, 71, 72, 410, 411, 412. . . track

67, 68, 69. . . Branch point

75. . . Correspondence

79, 83. . . Mapping unit

80. . . Block number or block address

84. . . First address of M bit

85. . . N-bit first address

87. . . Content addressed memory (CAM)

88, 89. . . RAM column

90. . . Index bit high LSB1

94. . . First address BNX3

96. . . Offset (BNY)

97. . . Index bit

98. . . Random access memory (RAM)

100. . . Bidirectional addressing unit

101. . . Entry

102. . . Encoder

104. . . Block address data

105. . . Write indicator

106. . . Read address

107. . . Control logic

108. . . Data output

109. . . Matching address output

110. . . Loop self-increment unit

111. . . V flag bit

112. . . A flag bit

113. . . U flag bit

115. . . Adder

116. . . Window (clear) indicator

119. . . Signal line

120. . . Reserved form

121, 195. . . Active table

126. . . Track table

127, 198. . . index

129. . . Address indicator

130, 186. . . Builder

131. . . Address translation unit (TLB)

132, 185. . . Fill engine

133. . . Exchanger

139. . . Exception handler address register

151. . . BN

152. . . BNX

156. . . BNY (leading indicator)

161. . . Reading mouth

166. . . Next BN

170. . . Tracker

172. . . Entry number (BN)

187. . . Second fill/builder

188. . . Thread identification (PID)

189. . . Base address

190. . . TBNX table

191. . . BNX table

192. . . G position

193. . . Replacement module

194. . . Data read and write address offset

196. . . High-level memory

197. . . Base address index memory

201. . . Processor core

202. . . First level memory

203. . . Second level memory

204. . . Main memory

205. . . Hard disk memory

206, 207, 208, 209. . . Cache structure

213. . . Address bus

214. . . Reading data bus

215. . . Write data bus

216. . . Bypass path

300. . . Address tree

301, 302, 304, 305, 307. . . trunk

303, 306. . . Tree branch

310, 312. . . Tree node

311, 313. . . Branch target

381, 417. . . signal

413, 414, 415, 416. . . Track point

418. . . Output

1200. . . Distributor

2000, 3000, 4000, 5000, 6000, 8000, 9000, 10000, 11000. . . Cache system

1 is an embodiment of a computing environment in accordance with the present invention.

2A is an embodiment of implementing an address tree in accordance with the method of the present invention.

Figure 2B is an embodiment of the operation of the address tree in accordance with the present invention.

Figure 3A is an embodiment of the cache system of the present invention.

Figure 3B is another embodiment of the cache system of the present invention.

4 is another embodiment of the cache system of the present invention.

Figure 5 is another embodiment of the cache system of the present invention.

Figure 6 is another embodiment of the cache system of the present invention.

Figure 7A is another embodiment of the cache system of the present invention.

Figure 7B is an embodiment of an integral part of the cache system of the present invention.

Figure 8 is an embodiment of the active watch of the present invention. Figure 9 is an embodiment of the construction of a new track in accordance with the present invention.

Figure 10A is another embodiment of the cache system of the present invention.

Figure 10B is an embodiment of an integral part of the cache system of the present invention.

Figure 11 is an embodiment of a dispenser or reservation table for a multi-layer cache structure of the present invention.

Figure 12 is an embodiment of the construction of a new track in accordance with the present invention.

Figure 13 is an embodiment of the exchanger of the present invention.

Figure 14A is another embodiment of the cache system of the present invention.

Figure 14B is an embodiment of an integral part of the cache system of the present invention.

Figure 15 is another embodiment of the cache system of the present invention.

Figure 16 is an embodiment of a memory structure implemented using the high performance cache of the present invention.

122. . . Low-level memory

123. . . Fill/builder

124. . . High-level memory

125. . . Processor core

320. . . Tracking engine

Claims (78)

A digital system comprising: a processor core connected to a first memory containing executable instructions and a second memory faster than the first memory, and the processor is configured to execute One or more executable instructions stored in the second memory, and a cache control unit, the cache control unit connecting the first memory, the second memory, and the processor core for executing on the processor core At least one or more instructions in a memory are previously filled into the second memory, wherein the cache control unit is further configured to: be filled from the first memory to the second memory The instructions are reviewed to extract instruction information including at least branch information, and a plurality of tracks are created according to the extracted instruction information, and at least one or more instructions are filled according to one or more tracks in the plurality of instruction tracks. The digital system of claim 1, wherein the instruction type further includes an instruction type that is one of a branch instruction and a non-branch instruction. The digital system of claim 1, wherein the branch information further includes a source address of the branch and a target address of the branch. The digital system of claim 1, wherein the plurality of tracks are arranged in an address tree configuration, each trunk corresponds to a track, and a branch point of each tree corresponds to a branch instruction. The digital system of claim 4, wherein: the executable instructions in the first memory are divided into a plurality of instruction segments, and the second memory comprises a plurality of memory blocks corresponding to the plurality of tracks Each memory block is used to store an instruction segment. If the second instruction memory does not include the first instruction segment of the new track corresponding to the branch instruction or the second instruction segment corresponding to the next sequential execution instruction of the branch instruction, then the processing is performed. The first instruction segment and the second instruction segment are filled from the first memory to the corresponding memory block in the second memory before the branch execution of the branch instruction. The digital system of claim 5, wherein a third instruction segment corresponding to the branch target instruction of the first branch track point in the new track is filled from the first memory to the corresponding memory of the second memory In the block. The digital system of claim 5, wherein before the processor core executes the branch instruction, the third instruction segment corresponding to the second new track obtained from the branch track point on the new track is also A memory is filled into the corresponding memory block in the second memory. The digital system of claim 2, wherein the cache control unit comprises a track table, the track table comprising a plurality of track table rows, each table row corresponding to one track. The digital system of claim 8, wherein each track table row comprises a plurality of entries, each entry corresponding to a track point; the track point corresponding to at least one instruction. The digital system of claim 9, wherein the track point can be found by a first address determined by a track number and a second address determined by an offset within the track. The digital system of claim 10, wherein: when the processor core executes an instruction corresponding to the track point, the cache control unit provides a first address for determining a memory block including the instruction, and The processor core provides an offset of the instruction in the memory block for fetching the instruction from the second memory. The digital system of claim 10, wherein the first address and the second address stored in the entry corresponding to the branch track point point to a new track point; the new track point is the branch track point The track point corresponding to the branch target address of the corresponding branch instruction. The digital system of claim 12, wherein the branch target address can pass the block address corresponding to the instruction segment of the branch track point, the offset of the track point in the track, and the The branch offset of the branch instruction is summed by three. The digital system of claim 10, wherein the cache control unit further comprises a tracker for providing the first address and the second address; the source of the address comprises a track table, and an address Self-energizer. The digital system of claim 14, wherein the source of the address may further include at least one stack and an exception handler register. The digital system of claim 14, wherein the tracker is further configured to: determine whether the current track point corresponds to a branch instruction; if the current track point does not correspond to the branch, in order to provide the first address and the second address The instruction keeps the first address unchanged as the next first address, and uses the address auto-incrementer to increment the current second address as the next second address to reach the next track point. The digital system of claim 16, wherein the tracker is further configured to: if the current trace corresponds to a branch instruction, wait for a control signal given by the processor core indicating whether the branch transfer is successful, and when the branch is transferred Upon success, the first address and the second address in the branch track point entry are respectively provided as the next first address and the next second address. The digital system of claim 17, wherein the tracker is further configured to: when the branch transfer is unsuccessful, keep the current first address unchanged as the next first address, and use the address to increase The device increments the current second address as the next second address to reach the next track point. A method for assisting operation of a processor core, the processor core being coupled to a first memory including executable instructions and a second memory faster than the first memory; the method comprising: aligning Exchanging instructions from the first memory to the second memory to extract instruction information including at least branch information; establishing a plurality of tracks according to the extracted instruction information; and one or more tracks according to the plurality of instruction tracks The track fills at least one or more instructions from the first memory to the second memory before being executed by the processor core, such that the processor core can acquire the at least one or more instructions from the second memory. The method of claim 19, wherein the instruction information further includes an instruction type that is one of a branch instruction and a non-branch instruction. The method of claim 19, wherein the branch information further comprises a source address of the branch and a target address of the branch. The method of claim 19, further comprising: arranging the plurality of tracks in an address tree configuration, wherein one of the trunks corresponds to one track, and the branch point of one tree corresponds to a branch instruction. The method of claim 22, wherein the executable instructions in the first memory are divided into a plurality of instruction segments, and the second memory comprises a plurality of memory blocks corresponding to the plurality of tracks, each The memory block is used to store an instruction segment. If the instruction segment of the new track corresponding to the branch instruction or the instruction segment corresponding to the next sequential execution instruction of the branch instruction is not included in the second memory, the processor core will execute the branch instruction before executing the branch instruction. The instruction segment is filled from the first memory into the corresponding memory block in the second memory. The method of claim 23, wherein a third instruction segment corresponding to the branch target instruction of the first branch track point in the new track is filled from the first memory to the corresponding memory block of the second memory in. The method of claim 23, wherein before the processor core executes the branch instruction, another instruction segment corresponding to the second new track obtained according to the branch track point on the new track is also from the first The memory is filled into the corresponding memory block in the second memory. The method of claim 21, further comprising: creating a track table, the track table comprising a plurality of track table rows corresponding to the plurality of tracks, each table row corresponding to one track. The method of claim 26, wherein each track table row comprises a plurality of entries, each entry corresponding to a track point; the track point corresponding to at least one instruction. The method of claim 27, wherein the method further comprises: finding the track point by the first address determined by the track number and the second address determined by the offset within the track. The method of claim 28, further comprising: when the processor core executes an instruction corresponding to the track point, providing a first address for determining a memory block containing the instruction, in the memory block The desired instruction can be obtained based on the offset provided by the processor core. The method of claim 29, further comprising: storing a first address that points to a new track determined by a branch target address in the branch track point corresponding entry. The method of claim 30, wherein the block address corresponding to the instruction segment by the branch track point, the offset of the track point in the track, and the branch offset of the branch instruction are obtained. The sum of the three sums to obtain the branch target address. The method of claim 28, further comprising: providing a first address and a second address; the source of the address comprises a track table and an address augmenter. The method of claim 32, further comprising: the source of the address further comprising at least one stack and an exception handler register. The method of claim 32, wherein the method of providing the first address and the second address further comprises: determining whether the current track point corresponds to a branch instruction; if the current track point does not correspond to the branch instruction, maintaining the first address The same as the next first address, and the use of the address auto-incrementer to increment the current second address as the next second address to reach the next track point. The method of claim 34, further comprising: if the current trace corresponds to a branch instruction, waiting for a control signal given by the processor core indicating whether the branch transfer is successful; and when the branch transfer is successful, providing the branch The first address and the second address in the track point entry are correspondingly used as the next first address and the next second address. The method of claim 35, wherein the tracker is further configured to: when the branch transfer is unsuccessful, keep the current first address unchanged as the next first address, and use the address auto-incrementer Add one to the current second address as the next second address to reach the next track point. A method for caching a control device to control a processor core cache operation; the processor core is coupled to a first memory including executable instructions and a second memory faster than the first memory; The processor core is configured to execute executable instructions in one or more second memories; the method includes: reviewing instructions being filled from the first memory to the second memory; from the reviewed instructions Extracting instruction information; determining, according to the extracted instruction information, the branch point before the processor core executes the branch point; and filling the instruction segment of the branch target instruction corresponding to the branch point from the first memory to the second memory And causing the second memory to include any instructions caused by the processor core to execute the branch point. The method of claim 37, wherein the filling the instruction segment further comprises: determining whether the instruction segment is already included in the second memory; and when the instruction segment is not included in the second memory, branching The instruction segment corresponding to the target instruction of the branch instruction of the point is filled from the first memory to the second memory, so that the second memory includes any instruction caused by the processor core to execute the branch point. The method of claim 37, further comprising: determining, according to information from the processor core whether branching occurs at the branch point, a next branch point after the branch point performed by the processor core. The method of claim 37, wherein the method of determining a branch point using a look-ahead indicator further comprises: creating a track table, the track table comprising a plurality of track table rows corresponding to the plurality of tracks, Each table row corresponds to one track and includes a plurality of entries, each entry corresponding to one track point, the track point corresponding to at least one instruction; and the leading indicator moves along a track corresponding to the branch point until the branch point entry is reached . The method of claim 40, further comprising: determining a block base address index associated with one or more track points in the track table; and executing the one or more at the processor core Before the track point, the data block corresponding to the one or more track points is filled according to the base address index. The method of claim 41, further comprising: storing the base address indicator in a base address index storage unit corresponding to the track table, the base address in the base address indicator and An offset provided by the processor core addresses the data in the memory block together. The method of claim 40, further comprising: providing a next track point address along the track using a tracker, the address including a first address corresponding to the track table line number and a Corresponding to the second address of the track table column number, wherein the leading indicator corresponds to the second address. The method of claim 43, further comprising: maintaining the current first address unchanged; incrementing the current second address to reach the next track point; determining whether the next track point is a branch track point; And when the next track point is a branch track point, providing a first address and a second address of the branch target address of the branch track point. The method of claim 44, wherein the tracker comprises at least one stack that supports a plurality of stack operation functions of a series of subprograms in the computer program. The method of claim 45, wherein at least one of the stacks can be replaced with a plurality of stacks, the plurality of stacks supporting a multi-threaded program running, wherein each thread corresponds to a separate one of the plurality of stacks Stack. The method of claim 45, further comprising: indicating a first address of the first track point in a first format in the track table; and establishing a target track of the first track point using an active table And a mapping relationship between the first memory block address, wherein when the first track point is established in the first format in the track table, an instruction segment corresponding to the first memory block address is filled into the second memory. The method of claim 47, further comprising: indicating a first address of the second track point in a second format in the track table; and establishing a target of the second track point using a reservation table a mapping relationship between the track and the address of the second memory block, wherein when the second track point is established in the second format in the track table, the instruction segment corresponding to the address of the second memory block is not filled into the second memory . The method of claim 48, further comprising: exchanging the first format and the second format using a switch. The method of claim 40, further comprising: implementing power consumption adjustment to the processor core based on accessing a frequency of an idle track stored in the track table. The method of claim 37, further comprising: filling a plurality of instruction segments related to the branch track points from the first memory into the second memory, wherein: each instruction segment is divided into a plurality of instruction segments; each instruction segment is assigned a priority order; and a plurality of instruction segments of the plurality of instruction segments are alternately padded according to a priority order of each instruction segment. The method of claim 40, further comprising: filling a plurality of data segments related to the one or more track points from the first memory into the second memory, wherein: each data segment Divided into a plurality of data segments; each data segment is assigned a priority order; and a plurality of data segments of the plurality of data segments are alternately padded according to a priority order of each of the data segments. A method for controlling a plurality of cache memories including a first memory and a second memory connected to a processor core and a first memory by using a cache control unit; the method comprising: filling a plurality of memories into a plurality of memories The instruction in the instruction is reviewed; the instruction information is extracted from the instruction being reviewed; the track point is created in the track table according to the extracted instruction information, and the branch target is represented by one of the low level cache memory block number and the high level cache memory block number An entry of a track point; wherein, when a low-level cache memory block number is used to represent a branch target track point, an instruction segment corresponding to the branch target track point is filled into the first memory; and when a high-level cache memory is used When the block number indicates a branch target track point, the command segment corresponding to the branch target track is filled into the second memory instead of the first memory. The method of claim 53, further comprising: using a table to establish a mapping relationship between the low-level cache memory block number and the instruction segment storage address, and the low-level cache memory block number and the plurality of high-level cache memories. The mapping relationship of block numbers. The method of claim 54, further comprising: determining whether the analyzed track point entry includes a preset low level cache memory block number; and when the track point entry includes the preset When the low level cache memory block number, it is judged whether a valid high level cache memory block number can be selected from the table according to the low level cache memory block number addressing. The method of claim 55, further comprising: if the valid high-level cache memory block number cannot be selected, filling the instruction segment from the first memory to the second memory; generating a valid a high level cache memory number; and replacing the low level cache memory block number in the track point with the high level cache memory block number. The method of claim 56, wherein there is a third memory connected between the first memory and the second memory; the method further comprising: when the track point entry includes the When the preset low-level cache memory number is determined, it is determined whether a valid high-level cache memory block number and a valid third memory memory block number can be selected from the table according to the low-level memory block number addressing. The method of claim 57, further comprising: if the valid high-level cache memory block number cannot be selected, but the valid third memory memory block number can be selected, the instruction segment is Filling the third memory with the second memory; and generating a valid high level cache memory number; and replacing the low level cache memory block number in the track point with the high level cache memory block number. The method of claim 53, wherein the low-level cache memory block number is associated with the first table, and the high-level cache memory block number is associated with the second table, the method further comprising: configuring the A table and a second table are used to ensure that the instruction segment is filled into the first memory or the second memory. The method of claim 53, wherein the low-level cache memory block number is associated with the first table, and the high-level cache memory block number is associated with the second table, the method further comprising: configuring the A table and a second table are used to ensure that the instruction segments are filled into the first memory and the second memory. a cache control device for controlling a cache for a processor core; the processor core is coupled to a first memory including executable instructions and a second memory faster than the first memory, and the processing The device is configured to execute one or more of the executable instructions in the second memory; the device includes: a first padding generating unit, configured to review an instruction filled from the first memory into the second memory, and The instruction information is extracted from the reviewed instruction; a tracker is configured to control the leading indicator according to the extracted instruction information, thereby determining the branch point before the processor core executes to the branch point; and an allocator for The instruction segment corresponding to the target instruction of the branch point is filled from the first memory to the second memory, so that the second memory includes any instruction caused by the processor core to execute the branch point. The device of claim 61, wherein the allocator is further configured to: determine whether the instruction segment is already included in the second memory; and if the instruction segment is not included in the second memory, The first pad generation unit controls the instruction segment corresponding to the target instruction of the branch point to be filled from the first memory to the second memory, so that the second memory includes any instruction caused by the processor core to execute the branch point. The device of claim 62, wherein the first padding generating unit comprises a virtual real address converting unit. The device of claim 61, wherein the tracker is further configured to: determine, according to information provided by the processor core to the leading indicator whether a branch transfer occurs at a branch point, determine the execution of the processor core. The next branch point of the branch point. The device of claim 62, wherein the device further comprises: a track table, the track table includes a plurality of track entries corresponding to the plurality of tracks, each table row corresponding to one track and including a plurality of tracks An entry, each entry corresponding to a track point, wherein the track point corresponds to at least one instruction; in the track table, the tracker controls the leading indicator to move along a track corresponding to the branch point until the branch point entry is reached. The apparatus of claim 65, wherein the padding generating unit is further configured to: determine a block base address index associated with one or more track points in the track table; and execute at the processor core Before the one or more track points are described, the data block corresponding to the one or more track points is filled according to the base address index. The device of claim 66, wherein the device further comprises: a base address index storage unit, configured to store the base address index corresponding to the track table, the base address in the base address index, and An offset provided by the processor core addresses the data in the memory block together. The apparatus of claim 63, wherein the tracker is further configured to: provide an address of a next track point along the track, the address address including a first address corresponding to the track table line number and A second address corresponding to the track table number, wherein the leading indicator corresponds to the second address. The device of claim 68, wherein the tracker can be further configured to: keep the current first address unchanged; the current second address is incremented by one to reach the next track point; and determining whether the next track point is a branch track point; and when the next track point is a branch track point, providing a first address and a second address of the branch target address of the branch track point. The device of claim 69, wherein the tracker further comprises a plurality of stacks for supporting multi-threaded program execution, wherein each thread corresponds to a separate stack of the plurality of stacks. The apparatus of claim 68, wherein: the first address of the track point of the first track is represented in the track table by the first format; and the distributor includes an active table for establishing the a mapping relationship between the first track and the first memory block address, wherein when the track point of the first track is established in the first format in the track table, an instruction segment corresponding to the address of the first memory block is filled to Two memory. The apparatus of claim 71, wherein: the first address of the second track point is represented by a second format in the track table; and the distributor includes a reservation table for establishing the second a mapping relationship between the track point and the second memory block address, wherein when the second track point is established in the second format in the track table, the instruction segment corresponding to the second memory block address is not filled into the second memory in. The device of claim 72, wherein: the allocator implements the latest memory of the second memory according to the active table and a clear window defined by the main indicator pointing to the active entry and the cleaning indicator pointing to the active entry. At least one of the least used (LRU) replacement policy and the least frequently used (LFU) replacement policy replaces the policy. The device of claim 72, wherein the device further comprises: a switch converting the first format and the second format in the track table. The device of claim 72, wherein: when the instruction segment corresponding to the first memory memory block number address is replaced by a new instruction segment in the second memory, a corresponding entry is established in the reserved table. An entry; and the switch changes the target address of the track table containing the replaced instruction segment from the first format to the second format. The device of claim 72, wherein the device further comprises: a second padding generating unit connecting the first memory and the third memory; and the second padding generating unit comprises a virtual real-time address converting unit. The device of claim 72, wherein: the second memory is managed by the active table; and the first memory is managed by the reservation table. The device of claim 65, wherein: the track table can be used to store an idle track, and power consumption adjustment of the processor core is implemented according to a frequency of accessing the idle track.