Calculator and calculation method

A calculator includes a processing core and a cache. The cache includes a data memory that holds data transferred from a main memory and a cache controller that controls transfer of data between the main memory and the data memory. The cache controller is configured to calculate, upon occurrence of a cache miss, a cycle count requested for arithmetic processing on one unit amount of data based on a cache miss occurrence interval and a memory access latency requested, and update a prefetch distance based on the calculated cycle count and the memory access latency, the prefetch distance indicating a relative distance on the main memory between a location from which the one unit amount of data transferred from the main memory due to the cache miss and a location from which a next one unit amount of data is to be prefetched.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2020-211064, filed on Dec. 21, 2020, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are related to a calculator and a calculation method.

BACKGROUND

In a processor such as a central processing unit (CPU), a memory access latency, which is an access time for a main memory, is often longer than a running time for an operation. For this reason, in a calculator equipped with a processor, a cache for holding data or instructions used with high frequency is provided between a processor core and a main memory, thereby improving data transfer efficiency. Use of multi-level memories enhances the execution efficiency of operations regardless of the memory access latency, and thus improves the performance of the processor and the calculator.

In order to further improve the execution efficiency of operations, there is known a processor having a prefetch function in which, before execution of an operation instruction, data or an instruction to be used for the operation is transferred from a main memory to a cache in advance. For example, this type of processor holds location information of an instruction that caused a cache miss in the past, and issues a prefetch request when the location information of an instruction causing a current cache miss is included in the location information of the instruction that caused the cache miss in the past.

In this type of processor, the number of cache misses at successive addresses is set in advance by a number-of-cache-misses specifying instruction. When the set number of cache misses occur, the processor prefetches a cache line subsequent to the cache-missed cache line. The location of a cache line to be prefetched may be set in advance by a location specifying instruction.

Japanese National Publication of International Patent Application No. 2009-540429 and Japanese Laid-open Patent Publication No. 2015-60529 are disclosed as related art.

The number-of-cache-misses specifying instruction and the location specifying instruction are written in the source program, and are not allowed to be changed during execution of the source program. The location of the cache line changed by a location change instruction is also referred to as a prefetch distance.

For example, when the source program includes a plurality of loop processes different from each other in arithmetic processing time, the optimal prefetch distance may differ for each loop process. However, it is possible to set the prefetch distance suited to any one of the plurality of loop processes. For this reason, a prefetch distance set suited to a certain loop process may not be suited to another loop process. In this case, the program execution efficiency decreases.

In one aspect, it is an object of the present disclosure to set an optimal prefetch distance depending on a running time that is different in each type of arithmetic processing.

SUMMARY

According to an aspect of the embodiments, a calculator includes a processing core that executes arithmetic processing and a cache including a data memory that holds data transferred from a main memory and a cache controller that controls transfer of data between the main memory and the data memory, wherein the cache controller is configured to calculate, upon occurrence of a cache miss, a cycle count requested for arithmetic processing on one unit amount of data based on a cache miss occurrence interval and a memory access latency requested to transfer the one unit amount of data from the main memory to the data memory unit, and update a prefetch distance based on the calculated cycle count and the memory access latency, the prefetch distance indicating a relative distance on the main memory between a location from which the one unit amount of data transferred from the main memory due to the cache miss and a location from which a next one unit amount of data is to be prefetched.

DESCRIPTION OF EMBODIMENTS

Hereinafter, the embodiments will be described with reference to the drawings. A signal line for transmitting information such as a signal will be denoted below by the same sign as the signal name. A signal line depicted by a single line in the drawings may include a plurality of bits.

FIG. 1illustrates an example of a calculator according to an embodiment. A calculator10illustrated inFIG. 1is, for example, a server, a personal computer (PC), or a supercomputer. The calculator10includes a processor20and a main memory60. The calculator10may include a plurality of processors20. The processor20includes a plurality of processing cores30each including an arithmetic unit32and an L1 cache34, and an L2 cache40.

The arithmetic unit32includes a plurality of arithmetic elements (not illustrated), and executes instructions written in a program by using data held in the L1 cache34. The arithmetic unit32is an example of a processing unit that executes arithmetic processing. The L1 cache34may hold not only data but also instructions. The following description will be given on the assumption that the L1 cache34and the L2 cache40hold data.

As illustrated inFIG. 1, the calculator10has a multi-level memory structure. Data to be used with relatively high frequency is transferred from the main memory60to the L2 cache40, and data to be used with even higher frequency is transferred from the L2 cache40to the L1 cache34. In a case where each of the L1 cache34and the L2 cache40runs short of a storage area for holding data transferred from a lower level, the data that is already held is purged to the lower level.

The access speed by the arithmetic unit32is higher in the order of the L1 cache34, the L2 cache40, and the main memory60. Therefore, transfer of data to be used with high frequency from the main memory60to the L1 cache34or the L2 cache40in advance makes it possible to shorten a time until the arithmetic unit32executes an instruction after decoding the instruction. As a result, the processing performance of the calculator10may be improved.

The L2 cache40includes a data memory unit42that holds data transferred from the main memory60, and a cache control unit44that controls data transfer between the main memory60and the data memory unit42. For example, the data memory unit42has a tag area for holding a cache status and a most-significant bit group of an address, and a data area for holding data. The cache control unit44includes a prefetcher50.

The prefetcher50predicts an address in the main memory60at which data to be used for an operation by the arithmetic unit32is stored. The L2 cache40outputs the address predicted by the prefetcher50to the main memory60as a prefetch address, and transfers data from the main memory60to the L2 cache40in advance. In this case, the prefetcher50predicts a prefetch address so as to reduce the number of cache misses. As described above, the processor20has a hardware prefetch function.

FIG. 2illustrates an example of the prefetcher50inFIG. 1. The prefetcher50includes a clock counter51, a cycle count holding circuit52, a memory access latency holding circuit53, a prefetch distance calculation circuit54, a prefetch distance holding circuit55, and a prefetch address generation circuit56.

The clock counter51makes a clock count of a clock CLK and outputs the clock count thus obtained as a counter value Cb. For example, the clock counter51operates all the time regardless of whether or not the prefetcher50outputs a prefetch address PFAD. The clock CLK may be an operation clock of the core30or a divided clock obtained by dividing the frequency of the operation clock.

In synchronization with a cache miss signal MISS indicating the occurrence of a cache miss, the cycle count holding circuit52holds the counter value Cb and outputs the counter value Cb as a counter value Ca. The cycle count holding circuit52updates the counter value Ca every time a cache miss signal MISS is received.

A clock cycle count expressed by a difference Cb−Ca between the counter value Cb output from the clock counter51at the occurrence of a cache miss and the counter value Ca held in the cycle count holding circuit52at the occurrence of the cache miss indicates a cache miss occurrence interval.

The memory access latency holding circuit53holds a memory access latency Lm included in a command CMD supplied from the outside of the calculator10before the arithmetic unit32starts the arithmetic processing, and outputs the held memory access latency Lm. The memory access latency Lm is a length of time (clock cycle count) requested by the core30to acquire, from the main memory60, a predetermined amount of data to be used for one loop process to be described later. The predetermined amount of data to be used in one loop process is an example of one unit amount of data.

In response to reception of a cache miss signal MISS, the prefetch distance calculation circuit54calculates a prefetch distance PFD0based on the memory access latency Lm for one unit amount and the counter values Cb and Ca, and outputs the calculated prefetch distance PFD0. For example, the prefetch distance calculation circuit54calculates the prefetch distance PFD0by using Expression (1).
PFD0=CEIL(Lm/(Cb−Ca−Lm))  (1)

In Expression (1), a sign CEIL denotes a ceiling function that gives the smallest integer equal to or larger than the value of the calculation result in the parentheses.

“Cb−Ca” denotes an interval between cache misses that occur consecutively, and is equal to the sum of the memory access latency Lm for one unit amount and a processing cycle count that is a length of time requested to execute the arithmetic processing for one unit amount. Thus, the processing cycle count for one unit amount is obtained by subtracting the memory access latency Lm from “Cb−Ca”. By calculating the ceiling function of a value obtained by dividing the memory access latency Lm by the processing cycle count, it is possible to calculate the prefetch distance PFD0indicating a value corresponding to how many times the processing cycle count for one unit amount is the memory access latency Lm.

The prefetch distance holding circuit55holds the prefetch distance PFD0output by the prefetch distance calculation circuit54and outputs the held prefetch distance as a prefetch distance PFD. The prefetch address generation circuit56repeatedly receives a memory address to be used for a read access to the main memory60and detects a tendency of a memory address change or the like (for example, such as an increase or decrease in the memory address by a predetermined amount). The prefetch address generation circuit56detects the start of the loop process of a prefetch target based on the memory address change tendency or the like, and predicts and registers a prefetch candidate based on the change tendency. For example, the prefetch candidate predicted may be a memory address or a range of memory addresses.

The prefetch address generation circuit56determines whether the memory address at the occurrence of a cache miss matches the prefetch candidate predicted in advance. When the memory address matches the prefetch candidate, the prefetch address generation circuit56determines that the prefetch distance PFD held in the prefetch distance holding circuit55is valid. The prefetch address generation circuit56generates a prefetch address PFAD based on the valid prefetch distance PFD.

When the prefetcher50generates the prefetch address PFAD, the L2 cache40illustrated inFIG. 1uses the prefetch address PFAD to perform a read access to the main memory60and read data from the main memory60. For example, the L2 cache40prefetches the data.

FIG. 3illustrates an example of a source list of a program to be executed by the processor20inFIG. 1. In the example illustrated inFIG. 3, the processor20executes IMAX iterations of arithmetic processing func1(A[i]) in a loop process Loop1, and executes IMAX iterations of arithmetic processing func2(B[i]) in a loop process Loop2.

For example, the data sizes (one unit amounts) of data arrays A[i] and B[i] are equal to each other. Therefore, the numbers of cache lines in the L2 cache40used for data of the respective data arrays A and B are the same. A cache line is a unit of data input and output to and from the main memory60and has, for example, 256 bytes.

In this embodiment, the data size of each of the data arrays A[i] and B[i] is equal to the data size of one cache line. The loop processes Loop1and Loop2execute different types of the arithmetic processing func1and func2, respectively. For example, a running time for the arithmetic processing func1(A[i]) is longer than a running time for the arithmetic processing func2(B[i]).

The running time for the arithmetic processing func1(A[i]) is equal to the memory access latency Lm for one unit amount. Therefore, the arithmetic processing func1(A[i]) uses a prefetch distance=“1” based on Expression (1). The running time for the arithmetic processing func2(B[i]) is shorter than the memory access latency Lm and is equal to or longer than half of the memory access latency Lm. Therefore, the arithmetic processing func2(B[i]) uses a prefetch distance=“2” based on Expression (1).

For example, the prefetch distance PFD indicates a location on the main memory60that stores one unit amount of data to be prefetched from the main memory60relative to a location on the main memory60that stores one unit amount of data transferred from the main memory60due to the occurrence of a cache miss.

FIG. 4illustrates an example of an operation of the prefetcher50inFIG. 2.FIG. 4illustrates an example in which the loop process Loop2is executed using the data array B[i] illustrated inFIG. 3. The clock counter51counts clocks and outputs the counter value Cb ((a) inFIG. 4). Although the waveform of a clock CLK inFIG. 4is illustrated as long cycles for easy understanding, the cycles are actually shorter than that inFIG. 4. The counter value Cb sequentially increments in synchronization with the clock CLK.

Every time a cache miss signal MISS is received, the cycle count holding circuit52updates the counter value Ca by holding the counter value Cb as the counter value Ca ((b), (c), and (d) inFIG. 4). Every time a cache miss signal MISS is received, the prefetch distance calculation circuit54calculates the prefetch distance PFD0based on the memory access latency Lm and the counter values Cb and Ca ((e), (f), and (g) inFIG. 4). For example, the prefetch distance calculation circuit54calculates the prefetch distance PFD0by using Expression (1).

The prefetch distance holding circuit55holds the prefetch distance PFD0as the prefetch distance PFD and outputs the prefetch distance PFD to the prefetch address generation circuit56((h), (i), and (j) inFIG. 4). The prefetch address generation circuit56determines whether the memory address at the time of a cache miss matches the prefetch candidate predicted and registered at the time of the previous cache miss. When the memory address at the time of the cache miss matches the prefetch candidate, the prefetch address generation circuit56generates the prefetch address PFAD based on the prefetch distance PFD ((k), (l), and (m) inFIG. 4).

For example, the prefetch address generation circuit56determines the timing of generating the prefetch address PFAD based on a reception interval of cache miss signals MISS. Thus, after a cache hit (HIT) occurs thanks to prefetching of the data array B[3], the prefetch address generation circuit56is capable of generating the prefetch address PFAD at appropriate timing even when a cache miss signal MISS is not received.

In a case where a cache miss occurs, the L2 cache40refers to the main memory60(MM), and reads the data arrays B ((n), (o), and (p) inFIG. 4). The core30executes the loop process Loop2by using the read data arrays B ((q), (r), and (s) inFIG. 4).

For example, after the start of reading of the data array B[1] from the main memory60, the prefetch address generation circuit56generates a prefetch address PFAD for prefetching the data array B[3], which is the second following data array, according to the prefetch distance PFD=“2”. The L2 cache40prefetches the data array B[3] from the main memory60by using the prefetch address PFAD at timing at which no contention occurs with the reading of the data array B[2] ((t) inFIG. 4).

Thus, in the loop process Loop2, the core30is able to execute the arithmetic processing using the data array B[3] prefetched to the L2 cache40after the arithmetic processing on the data array B[2] ((u) inFIG. 4). As described above, the prefetch address generation circuit56sequentially generates the prefetch addresses PFAD. Thus, the subsequent loop process Loop2by the core30may be executed by using the data arrays B[4] and B[5] prefetched to the L2 cache40.

FIG. 5illustrates an example of an operation of the prefetcher50inFIG. 2. The operation flow illustrated inFIG. 5illustrates an example of a method of controlling a calculator. The operation illustrated inFIG. 5is started based on power-on of the calculator10or the processor20and then repeatedly executed.

First, in step S10, the prefetcher50waits for reception of a cache miss signal MISS, and executes step S12when receiving a cache miss signal MISS. In step S12, the prefetcher50causes the cycle count holding circuit52to hold the cycle count at the time of the cache miss. The prefetcher50registers a prefetch candidate when the cache miss occurs.

Next, in step S14, the prefetcher50causes the prefetch distance calculation circuit54to calculate the prefetch distance PFD0. The prefetch distance PFD0is calculated when two or more cache misses occur. Next, in step S16, the prefetcher50sets the prefetch distance PFD0calculated in step S14in the prefetch distance holding circuit55.

The clock counter51operates all the time, and the prefetch distance calculation circuit54calculates the prefetch distance PFD0every time a cache miss signal MISS is received. Thus, for example, when a cache miss occurs in the first arithmetic processing of the loop process Loop1illustrated inFIG. 3, the prefetch distance PFD0calculated by the prefetch distance calculation circuit54is an invalid value having no meaning. At this time, the prefetch address PFAD held in the prefetch distance holding circuit55is also an invalid value having no meaning.

In this embodiment, the prefetcher50calculates the prefetch distance PFD0in accordance with the cache miss intervals. Thus, the prefetch distance PFD is not set by a dedicated command from the outside of the calculator10. For example, the prefetch distance PFD may be automatically set by the prefetcher50without being set from the outside.

Next, the prefetcher50executes step S20if the prefetch address generation circuit56detects a prefetch target in step S18, or returns to step S10if not. For example, when determining that the memory address at the time of the cache miss matches the prefetch candidate predicted and registered at the time of the previous cache miss, the prefetch address generation circuit56determines that the prefetch target is detected. The prefetch address generation circuit56determines that the prefetch distance PFD0calculated by the prefetch distance calculation circuit54is valid.

Next, in step S20, the prefetch address generation circuit56starts generating the prefetch address separated by an appropriate distance based on the prefetch distance PFD. The operation then returns to step S10.

FIG. 6illustrates an example of an operation of the calculator10inFIG. 1.FIG. 6illustrates an example in which the loop processes Loop1and Loop2are sequentially executed in accordance with the source list of the program illustrated inFIG. 3. InFIG. 6, a sign MISS indicates a cache miss, and a sign HIT indicates a cache hit.

A sign Lm indicates a memory access latency for reading one unit amount of the data array A or the data array B by referring to the main memory60. The memory access latency Lm is also requested to prefetch one unit amount of the data array A or the data array B from the main memory60. A sign Lc indicates a latency for reading one unit amount of the data array A or the data array B by referring to the L2 cache40.

A sign OP1indicates a cycle count requested for the arithmetic processing on the data array A, and a sign OP2indicates a cycle count requested for the arithmetic processing on the data array B. As described with reference toFIG. 3, for example, the cycle count OP1is equal to the memory access latency Lm, and the cycle count OP2is shorter than the memory access latency Lm and is half or more of the memory access latency Lm. Therefore, according to Expression (1), the loop process Loop1for executing the arithmetic processing func1(A[i]) uses the prefetch distance=“1”, while the loop process Loop2for executing the arithmetic processing func2(B[i]) uses the prefetch distance=“2”.

In the loop process Loop1with the prefetch distance of “1”, the L2 cache40prefetches, for example, the data array A[2], which is the first following data array of the data array A[1] under the arithmetic processing. In the loop process Loop2with the prefetch distance of “2”, the L2 cache40prefetches, for example, the data array B[3], which is the second following data array of the data array B[1] under the arithmetic processing. Although not illustrated inFIG. 6, for example, in a case where the prefetch distance is “3”, the L2 cache40prefetches the third following data array of a data array under the arithmetic processing.

As illustrated inFIG. 6, even in a case where the loop processes Loop1and Loop2with the different cycle counts requested for arithmetic processing are executed by a single program, the prefetcher50is capable of setting the optimal prefetch distances PFD for the respective loop processes Loop1and Loop2. The prefetcher50is capable of prefetching a data array from the main memory60by using the prefetch address PFAD generated in accordance with the set prefetch distance. Even when a program includes three or more loop processes Loop, the prefetcher50is capable of setting the optimal prefetch distances PFD for the respective loop processes.

FIG. 7illustrates an example of an operation of another calculator. The same portions of the operation as those illustrated inFIG. 6are denoted by the same signs and detailed description thereof will be omitted herein. Also in the example illustrated inFIG. 7, the loop processes Loop1and Loop2are sequentially executed in accordance with the source list of the program illustrated inFIG. 3. However, inFIG. 7, before the program is executed, the prefetch distance PFD is set to “1” in advance by a dedicated command from the outside of the calculator10.

Since the prefetch distance PFD is set to “1”, the operation of the loop process Loop1is the same as that inFIG. 6. In the loop process Loop2, the L2 cache40also prefetches, for example, the data array B[2], which is the first following data array of the data array B[1] under the arithmetic processing, as in the loop process Loop1.

The length of time requested to prefetch the data array B from the main memory60is the memory access latency Lm. Thus, the prefetching of the data array B[2] is not completed during the execution of the arithmetic processing on the data array B[1] shorter than the memory access latency Lm.

Therefore, when a load instruction for the data array B[2] is executed, a cache miss MISS occurs and the data array B[2] is read from the main memory60. As a result, the prefetching of the data array B[2] is useless. Similarly, prefetching of the data arrays B[3] and B[4] is not completed during the execution of the arithmetic processing on the data arrays B[2] and B[3], respectively. Therefore, when the load instructions for the data arrays B[3] and B[4] are executed, cache misses MISS occur and the data arrays B[3] and B[4] are read from the main memory60.

From the above, in a case where the prefetch distance PFD is fixed and the loop processes Loop1and Loop2with the different cycle counts requested for arithmetic processing are executed by a single program, it is not possible to set the optimal prefetch distances PFD for the respective loop processes Loop1and Loop2. This causes many cache misses MISS, and results in decrease in the program execution efficiency and accordingly decrease in the processing performance of the calculator.

As described above, in this embodiment, when a program including a plurality of loop processes Loop1and Loop2different in arithmetic processing time is executed, an appropriate prefetch distance may be calculated for each of the loop processes Loop1or Loop2. In this case, for example, the prefetcher50may easily calculate the prefetch distance PFD based on the cache miss occurrence interval and the memory access latency Lm in accordance with Expression (1).

Thus, as compared with the case where a common prefetch distance is set for a program including a plurality of loop processes Loop1and Loop2, the hit rate of the L2 cache40may be improved and the execution efficiency of the program may be improved. As a result, the processing performance of the calculator10may be improved. The prefetch distance PFD may be automatically set by the prefetcher50without being set from the outside.

The prefetcher50uses the clock counter51and the cycle count holding circuit52to obtain a cache miss occurrence interval as the clock cycle count, and calculates the prefetch distance PFD using the memory access latency Lm expressed by the clock cycle count. Thus, the prefetch distance PFD may be calculated by using the simple prefetch distance calculation circuit54.

FIG. 8illustrates an example of a prefetcher installed in a calculator according to another embodiment. The same elements as those illustrated inFIG. 2are denoted by the same reference signs and detailed description thereof will be omitted herein. A prefetcher50A illustrated inFIG. 8is installed in the L2 cache40of the calculator10illustrated inFIG. 1. The configuration and function of the calculator10including the prefetcher50A are the same as the configuration and function of the calculator10inFIG. 1except that the L2 cache40includes the prefetcher50A instead of the prefetcher50.

The prefetcher50A includes a prefetch distance calculation circuit54A and a prefetch address generation circuit56A instead of the prefetch distance calculation circuit54and the prefetch address generation circuit56inFIG. 2. The other configuration of the prefetcher50A is the same as the configuration of the prefetcher50inFIG. 2.

In the same way as in the prefetch address generation circuit56, the prefetch address generation circuit56A determines that a prefetch target is detected when determining that a memory address at the time of a cache miss matches a prefetch candidate predicted and registered at the time of the previous cache miss. After that, the prefetch address generation circuit56A determines that the valid prefetch distance PFD0is calculable by the prefetch distance calculation circuit54A, and outputs a prefetch target detection signal PFDET to the prefetch distance calculation circuit54A. The prefetch target detection signal PFDET is an example of a calculation start signal generated when a cache-missed memory address matches a prefetch candidate predicted at the time of the previous cache miss.

Only when receiving a cache miss signal MISS and a prefetch target detection signal PFDET, the prefetch distance calculation circuit54A calculates the prefetch distance PFD0based on the memory access latency Lm and the counter values Cb and Ca. For example, the prefetch distance PFD0is obtained by using Expression (1).

Thus, the prefetch distance calculation circuit54A may not wastefully calculate the invalid prefetch distance PFD0, and the prefetch distance holding circuit55may be inhibited from holding the invalid prefetch distance PFD. As a result, the prefetcher50A may be efficiently operated, and the power consumption of the prefetcher50A may be reduced.

FIG. 9illustrates an example of an operation of the prefetcher50A inFIG. 8. Detailed description will be omitted for the same operation as that illustrated inFIG. 4. Also inFIG. 9, the loop processes Loop1and Loop2are sequentially executed according to the source list of the program illustrated inFIG. 3.

InFIG. 9, even when receiving a cache miss signal MISS, the prefetch distance calculation circuit54A does not calculate the prefetch distance PFD0if a prefetch target detection signal PFDET is not received ((a) and (b) inFIG. 9). Therefore, the prefetch distance holding circuit55does not hold the prefetch distance PFD ((c) inFIG. 9).

On the other hand, when receiving the cache miss signal MISS and the prefetch target detection signal PFDET together, the prefetch distance calculation circuit54A calculates the prefetch distance PFD0((d) and (e) inFIG. 9). The prefetch distance holding circuit55holds the prefetch distance PFD0calculated by the prefetch distance calculation circuit54A as the prefetch distance PFD ((f) inFIG. 9). The subsequent operation is the same as that inFIG. 4.

FIG. 10illustrates an example of an operation of the prefetcher50A inFIG. 8. The same processing as that in the operation flow illustrated inFIG. 5will be denoted by the same step numbers as inFIG. 5, and detailed description thereof will be omitted herein. The operation flow illustrated inFIG. 10is the same as the operation flow illustrated inFIG. 5except that step S18inFIG. 5is moved before step S14.

After step S12, in step S18, the prefetch address generation circuit56A of the prefetcher50A determines whether the prefetch candidate registered in advance and the cache-missed memory address match each other (whether a prefetch target is detected). The prefetcher50A executes step S14if the prefetch address generation circuit56A detects the prefetch target or returns to step S10if not. For example, the prefetcher50A executes step S14when determining that the valid prefetch distance PFD0is calculable by the prefetch distance calculation circuit54A based on the prefetch candidate registered in advance.

Only when the prefetch candidate and the cache-missed memory address match each other, the prefetch distance calculation circuit54A calculates the prefetch distance PFD0. The operation of the calculator10including the prefetcher50A is the same as that inFIG. 6.

As described above, this embodiment is also capable of producing the effects similar to or the same as those in the foregoing embodiment. For example, it is possible to calculate an appropriate prefetch distance for each of the loop processes Loop1and Loop2, and it is possible to improve the hit rate of the L2 cache40. This results in improvement of the program execution efficiency and accordingly improvement of the processing performance of the calculator10.

In this embodiment, the prefetch distance calculation circuit54A may not wastefully calculate the invalid prefetch distance PFD0, and the prefetch distance holding circuit55may be inhibited from holding the invalid prefetch distance PFD. As a result, the prefetcher50A may be efficiently operated, and the power consumption of the prefetcher50A may be reduced.

FIG. 11illustrates an example of a prefetcher installed in a calculator according to another embodiment. The same elements as those illustrated inFIG. 2are denoted by the same reference signs and detailed description thereof will be omitted herein. A prefetcher50B illustrated inFIG. 11is installed in the L2 cache40of the calculator10illustrated inFIG. 1. The configuration and function of the calculator10including the prefetcher50B are the same as the configuration and function of the calculator10inFIG. 1except that the L2 cache40includes the prefetcher50B instead of the prefetcher50.

The prefetcher50B has the same configuration as that of the prefetcher50inFIG. 2except that the prefetcher50B includes a clock counter51B and a prefetch distance calculation circuit54B instead of the clock counter51and the prefetch distance calculation circuit54inFIG. 2.

The clock counter51B makes a clock count of a clock CLK until a cache miss signal MISS is received, and outputs the clock count thus obtained as a counter value Cb. The clock counter51B clears the counter value Cb to, for example, “0” in synchronization with the cache miss signal MISS. For example, the clock counter51B is cleared every time a cache miss occurs. Therefore, the counter value Cb before being cleared when the cache miss signal MISS is received indicates an interval between cache misses that occur consecutively, and is equivalent to “Cb−Ca” in Expression (1).

In synchronization with the cache miss signal MISS, the cycle count holding circuit52holds the counter value Cb indicating a cache miss interval and outputs the counter value Cb as a counter value Ca. For example, the counter value Ca updated every time a cache miss signal MISS is received indicates the cache miss interval.

In response to reception of the cache miss signal MISS, the prefetch distance calculation circuit54B calculates the prefetch distance PFD0based on the memory access latency Lm and the counter value Ca, and outputs the calculated prefetch distance PFD0. For example, the prefetch distance calculation circuit54B calculates the prefetch distance PFD0by using Expression (2).
PFD0=CEIL(Lm/(Ca−Lm))  (2)

Since the counter value Ca in this embodiment represents “Cb−Ca” in Expression (1), Expression (2) is substantially the same as Expression (1).

On the other hand, Expression (2) is simpler than Expression (1). Thus, the prefetch distance calculation circuit54B may have a simpler circuit configuration and more easily calculate the prefetch distance PFD0than the prefetch distance calculation circuit54illustrated inFIG. 2does. As a result, the circuit size and power consumption of the prefetch distance calculation circuit54B may be made smaller than the circuit size and power consumption of the prefetch distance calculation circuit54, respectively.

FIG. 12illustrates an example of an operation of the prefetcher inFIG. 11. Detailed description will be omitted for the same operation as that illustrated inFIG. 4. Also inFIG. 12, the loop processes Loop1and Loop2are sequentially executed according to the source list of the program illustrated inFIG. 3.

InFIG. 12, the counter value Cb is cleared every time a cache miss occurs. As inFIG. 4, the counter value Cb sequentially increments in synchronization with the clock CLK.

The cycle count holding circuit52holds, as the counter value Ca, the counter value Cb before being cleared in synchronization with a cache miss signal MISS. When a cache miss occurs, the prefetch distance calculation circuit54B uses the memory access latency Lm and the counter value Ca to calculate the prefetch distance PFD0based on Expression (2). The operation illustrated inFIG. 12is the same as the operation illustrated inFIG. 4except that the counter value Cb is cleared and the prefetch distance PFD0is calculated by the prefetch distance calculation circuit54B in a different method.

FIG. 13illustrates an example of an operation of the prefetcher inFIG. 11. The same processing as that in the operation flow illustrated inFIG. 5will be denoted by the same step numbers as inFIG. 5, and detailed description thereof will be omitted herein. The operation flow illustrated inFIG. 13is the same as the operation flow illustrated inFIG. 5except that step S13is inserted between steps S12and S14.

In step S14, the prefetch distance calculation circuit54B calculates the prefetch distance PFD0by using Expression (2). In step S13, the prefetcher50B clears the counter value Cb of the clock counter51B. The operation of the calculator10including the prefetcher50B is the same as that inFIG. 6.

As described above, this embodiment is also capable of producing the effects similar to or the same as those in the foregoing embodiments. For example, it is possible to calculate an appropriate prefetch distance for each of the loop processes Loop1and Loop2, and it is possible to improve the hit rate of the L2 cache40. This results in improvement of the program execution efficiency and accordingly improvement of the processing performance of the calculator10.

In this embodiment, the prefetch distance calculation circuit54B may have a simpler circuit configuration and more easily calculate the prefetch distance PFD0than the prefetch distance calculation circuit54illustrated inFIG. 2does. As a result, the circuit size and power consumption of the prefetch distance calculation circuit54B may be made smaller than the circuit size and power consumption of the prefetch distance calculation circuit54, respectively.

The above embodiments have been described for the example in which the prefetcher50(or50A or50B) is installed in the L2 cache40. However, the prefetcher50may be installed in each of the L1 caches34inFIG. 1, or may be installed in each of the L1 caches34and the L2 cache40. For example, when the prefetchers50are installed in both of the L1 caches34and the L2 cache40, the hit rates may be improved in both of the L1 caches34and the L2 cache40. As a result, the processing performance of the calculator10may be further improved.

Instead of the clock counter51, the prefetcher50A illustrated inFIG. 8may include a clock counter51B (FIG. 11) whose counter value Cb is cleared every time a cache miss occurs. Only when receiving a cache miss signal MISS and a prefetch target detection signal PFDET, the prefetch distance calculation circuit54A may calculate the prefetch distance PFD0based on the memory access latency Lm and the counter value Ca. In this case, the prefetch distance PFD0is calculated by using Expression (2).

The features and advantages of the embodiments are apparent from the above detailed description. The scope of claims is intended to cover the features and advantages of the embodiments described above within a scope not departing from the spirit and scope of right of the claims. Any person having ordinary skill in the art may easily conceive every improvement and alteration. Accordingly, the scope of inventive embodiments is not intended to be limited to that described above and may rely on appropriate modifications and equivalents included in the scope disclosed in the embodiment.