JP3445873B2 - Data prefetch method and information processing apparatus therefor - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of prefetching data contained in a so-called pointer type data structure, which is composed of a plurality of element data each containing data and addresses of other data, and an information processing apparatus therefor.

[0002]

2. Description of the Related Art Since the speeding up of memory cannot keep up with the high performance of a processor, a method of improving the performance of an information processing apparatus using a cache memory is often used. However, the cache memory only holds a part of the main memory copy, and the data to be read may not exist in the cache memory (cache miss). At this time, the processor cannot start the next operation until the data is read from the main memory, resulting in an overhead cycle. Various methods have been devised to eliminate this overhead, and one of them is the data prefetch method. The idea is to read the data that is likely to cause a cache miss into the cache before using the data. At this time, the performance of the information processing apparatus can be improved by prefetching data from the main memory to the cache and executing other processing in parallel.

Regarding this data prefetch method,
Reference 1: Callahan et al., "Software Prefetching" (ASPLOS-IV Proceedings, 1991, pp. 40-52 (D
avidCallahan, et. al., "Software Prefetching," ASP
LOS-IV Proc ee dings, April1991 , pp.40-52) is on describing the hardware prefetching known already in the past, we have proposed prefetching by software as being superior to that . For example, what is already known as hardware prefetching is the use of circuitry to prefetch the next line, for example, when the last address of any line is accessed in the cache. On the other hand, prefetching by software executes an instruction for prefetching and storing the data in the cache before the data that is expected to be accessed by software later is accessed.

The above-mentioned document 1 shows that such prefetching by software can be applied to, for example, an array type data structure. The array-type data structure is composed of data held in storage locations of a plurality of addresses which are continuous or are separated by a constant address interval. Therefore, the address of the data to be fetched next can be determined by using the address of the head data of the array-type data structure and the address interval before actually reading the array-type data structure. Therefore, it is possible to keep read into cache by to be able to direct the data to be read next in advance from the software.

The array-type data structure as described above is used as a reference.
Hardware for the pitch has also been proposed separately. For example, Reference 2: “Structure and Evaluation of Ochanomizu No. 1,” Information Processing Society of Japan, Research Report, Computer Architecture 101-8, 19
In 93.8.20, pp.57-64, before the timing when the processor uses the array type data structure, the array type data structure is read from the main memory, and a buffer memory for prefetch provided separately from the cache is provided. When the processor processes any element data in the array type data structure, the element is read from the prefetch buffer. This prevents the processor from seeing the time when the array data is read from the main memory.

As another data structure often used in software similar to the array type data structure, there is a pointer type data structure having a structure connected by pointers.
The software structure of this data structure is shown in FIG. 6, and an example of this type of data structure arranged in the main memory is shown in FIG. Each element data 10, 20, 30 constituting such a data structure includes a plurality of entries 11 to 14, 21 to 24, 31 to 34, respectively.
Each element data has one entry, for example, 11,21.
Alternatively, 31 includes a pointer for designating subsequent element data. In the example of FIG. 7, this pointer is the address itself of the subsequent element data.

When reading a plurality of element data belonging to such a pointer type data structure from the memory 90, first, a load instruction for reading the first element data, for example, 10 from the memory 90 is first executed, whereby The top element data is read from the memory. Next, a plurality of instructions for processing the data included in the entries 12 to 14 of the element data are executed. Furthermore, the first entry 1
A load instruction for fetching the next element data is issued from the storage location having the address of the second element data included in 1. Therefore, the address of the element data other than the element data at the head is not known until the immediately preceding element data is fetched from the memory.

[0008]

Therefore, the above-mentioned document 1
The software prefetching method shown in
The effect of prefetching cannot be expected so much for pointer type data structures. Further, the above-mentioned Document 2 describes a method of executing hardware prefetching on array data, but how can hardware fetching be executed on a pointer type data structure or another data structure? Not shown. After all, in the related art, the technique of prefetching the pointer type data structure has not been known.

Pointer type data structures are not only frequently used by programs written in the list processing language, but also often by the OS. Therefore, O
To increase the execution speed of S, it is desirable to improve the time required to fetch this pointer type data structure.

An object of the present invention is to provide a method of prefetching a pointer type data structure and an information processing apparatus therefor.

[0011]

In a data prefetch method according to the present invention, when a first instruction requesting reading of first data from a memory holding data is executed by a processing device, the first prefetch of the memory is performed. Read the first data from the storage location, supply the read first data to the processing device, and the first instruction causes the second data in which the first data is held in the memory. When the specific information to be included when including the address information of the data is included in the first instruction, the first instruction read from the second storage position of the memory, which is determined by the first data read, Prefetching the second data, temporarily holding the prefetched second data, and executing a second instruction executed by the processing device after the second data is read from the memory. The second day from memory When requesting the read, and supplies the second data that is held in the processing apparatus.

More specifically, the first instruction is a load instruction, and in the prefetch, the pointer hint information contained in a specific field in the instruction is the data to be loaded by the instruction. Other data is prefetched using the data loaded by the load instruction when indicating that it includes a pointer for loading the other data.

[0013]

When the instruction that requests to read the data from the memory is executed and the data includes the address information of other data, the data read from the memory according to the request of the instruction is used. Other data can be read. Originally, the program including the instruction is read out from the memory Lud over data knows whether pointers to other data by any instructions. Therefore, according to the present invention, the execution of the load instruction designating the pointer is used to prefetch other data designated by the pointer, so that the timing of prefetching can be easily determined. Moreover, each time such one instruction is executed, the data used by the instruction subsequent to the instruction is prefetched, so that the circuit required for prefetching becomes simple. In addition, because prefetched data is often certain to be used, it is unlikely that it will never be used after it has been prefetched, so prefetching can be wasted. Is few.

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The data prefetch method according to the present invention will be described in more detail below with reference to some embodiments shown in the drawings. In the following, the same reference numbers represent the same or similar items.

<First Embodiment> In FIG. 1, 600 is a processor, and 700 is
A main memory, 100 is a memory interface circuit.

The processor 600 has a CPU 610, a cache 620, and a cache control circuit 630. As will be described later, the CPU 610 can execute a load instruction including pointer hint information for prefetching data, and supplies the pointer hint information to the memory interface circuit 100 via the line 609. ing.

The memory interface circuit (100) is
It has a processor interface circuit 200, an I / O bus interface circuit 400, a prefetch circuit 300, and a memory access arbitration circuit 500. The processor interface circuit 200 includes a bus 601, a control signal line 6
03, the main memory 700 connected to the processor 600 via the hint signal line 609.
To the memory access arbitration circuit 500. The I / O bus interface circuit 400 is connected to the I / O control circuit 800,
Is connected to 810, Installing receives main memory access requests from the I / O control circuit 800 and 810, and supplies to the memory access arbitration circuit 500. Prefetch circuit 300
Is a circuit characteristic of this embodiment. When the data requested by the load instruction accepted by the memory interface circuit 200 is a pointer to other data, the data requested by the load instruction is transferred from the main memory 700. It is a circuit for prefetching other data using the read data at the time of reading. The memory access arbitration circuit 500 is connected to the main memory 700 via an address bus 701, a data bus 702, and a control signal line 703, and the processor interface circuit 20.
0, one of the memory access requests given from the prefetch circuit 300 is selected and supplied to the main memory 700. Since the read / write processing for the main memory is normally performed in block units, memory read and memory write are hereinafter performed in block units for the main memory.

(CPU) In this embodiment, the instructions executed by the CPU 610 are:
For example, the manual "P published by Hewlett Packard
A-RISC 1.1 Architecture and Instruction Set Refere
nce Manual, Third Edition, "Hewlet-Packard, Feb. 1
You can use the instructions listed in 994. In particular, in this embodiment, the load word short (L) described on page 5-42 of the above manual is used as the instruction to load the memory data.
DWS) instruction can be used. This instruction 40 has the format shown in FIG. 8 and has fields 50 to 59. The field 50 holds an instruction code, and this instruction is a value obtained by sign-extending the 5-bit immediate data IM5 held in the field 52 and the field 5
Requests that data having a sum of the contents of a general-purpose register (not shown) held in 1 as a memory address be read from the main memory and stored in the general-purpose register indicated by the field 59. 5th of the above manual
According to pages 17 to 5-18, cc of field 56
Consists of 2 bits called cache control hint bits. When the value is 2, spatial localization (Spat
It is used as a hint of (ial Locality), but when the value is 1 or 3, its use is not yet defined. When the value of this hint bit is 0, it is treated as having no hint. Therefore, in this embodiment, when the instruction of this format is used as the conventional load instruction, the value of this hint is set to 0. However, when an instruction of this format is used as a load instruction that also performs prefetch characteristic of this embodiment, the value of this hint is set to 1, for example. Therefore, when the CPU 610 executes this instruction, it outputs the value of this hint to the line 609.
It is configured to output to the memory interface circuit 100 via the. That is, when the data to be loaded by the load instruction is a pointer, that is, data related to the address of other data, and the prefetching of the other data is requested as an address, the value of this hint is set to 1. . In the following, this hint of an instruction is called a pointer hint, a load instruction with a pointer hint that requires such prefetch is called a load instruction with a pointer hint, and a load instruction with a pointer hint that does not require such prefetch is a pointer hint. None Sometimes called load instruction.

The CPU 610 calculates the address of the data to be read from the memory and outputs this address and the read request, as in the prior art.
Supply to 30. In the present embodiment, the memory address supplied by the CPU to the cache control circuit 630 indicates the real address of the main memory 700, and the data read from the main memory 700 by any load instruction is the address of other data. , It is assumed that the data points to the real address of the other data. The CPU also executes a store instruction having a similar format, but its description is omitted.

(Cache Control Circuit 630) The cache control circuit 630 operates in the same manner as that known per se. That is, when the CPU 610 executes an instruction requesting access to the main memory, such as a load instruction or a store instruction for data at any address in the main memory 700, cache control of a read request or a write request for the data is executed. Supply to the circuit 630. Cache control circuit 630
Cache 6 for the data specified by the instruction.
20 is hit-checked, and if the cache 620 hits for this data, if the instruction is a load instruction, the data requested by the instruction is read from the cache 620 and supplied to the CPU 610. At this time, the data specified by the instruction is written in the cache 620. As a result of the hit check, when the cache miss occurs, the cache control circuit 620 issues a read request including a memory address to be loaded to the memory via the control line 603 and the bus 601 when the executed instruction is a load instruction. It is supplied to the interface circuit 100. Later, as a response to the read request, the memory interface circuit 10
When a block containing the requested data is supplied from 0, the requested data in the block is transferred to the CPU 61.
0 and transfers the block to the cache 62
Write to 0. When the executed instruction is the store instruction, the write request including the write data and the store address sent from the CPU 610 is supplied to the memory interface circuit 100.

(Memory Interface Circuit 100) The operation of the memory interface circuit 100 in response to a read request supplied from the processor 600 will be described below. Since the process for the write request can be easily analogized from now on, the description will be limited to the range necessary for understanding the present embodiment.

(Memory Read Operation) When performing a memory read, the memory interface circuit 100 controls the main memory 700 via the control signal line 703 to read data from the main memory 700 and use the read data as a read request source. return.

Upon receiving a read request from the processor 600, the memory interface circuit 100 requests the memory access arbitration circuit 500 for the bus right of the internal buses 105 and 106 by setting the read request signal p-rd201 to high. The memory access arbitration circuit 500 performs arbitration and outputs the bus right acquisition signal p-gnt to the line 203, thereby passing the bus right to the processor interface circuit 200. Processor interface circuit 200
When the bus right acquisition signal p-gnt is received via the line 203, it transfers the read address given from the processor 600 to the memory access arbitration circuit 500 via the address bus 105 in the next cycle. The memory access arbitration circuit 500 reads the main memory 700 at this address and transfers it to the processor interface circuit 200 via the data bus 106. At this time, the memory access arbitration circuit 500 sends the data valid signal p-vld to the line 504.
Output to. This signal is also OR gate 260, line 2
Is supplied to the processor interface circuit 200 via 04, thereby informing the circuit 200 that the data on the data bus 106 is valid. The processor interface circuit 200 receives the data valid signal p-
In response to vld, the data on the data bus 106 is fetched and transferred to the processor 600. The memory access arbitration circuit 500 and the processor interface circuit 200 repeat the same operation as above so as to further read a plurality of other data in the block to which the data having this read address belongs, that is, three data in this embodiment. In this way, four data are sequentially transferred between the memory access arbitration circuit 500 and the processor interface circuit 200, and a total of four data valid signals are given to them from the former to the latter. In this way, the processor interface circuit 200 and the memory access arbitration circuit 500 complete the read process. This operation is basically the same as the conventional memory interface circuit or memory access arbitration circuit 500.

(Memory Write Operation) In the write processing, the memory interface circuit 100 controls the main memory 700 via the control signal line 703 to write the data passed from the write request source in the main memory 700. That is, in the write processing, the processor interface circuit 200 makes the write request signal p-wr high instead of the read request signal p-rd, and when the bus right acquisition signal p-gnt is received, the address bus 1 in the next cycle.
The address is transferred via 05, and the data is transferred to the memory access arbitration circuit 500 via the data bus 106 in the following 4 cycles, thereby ending the write processing.

The processor interface circuit 200 includes
It differs from the prior art only in that it is configured to provide a control signal to a delay circuit 250 described later. The function of the memory access arbitration circuit 500 is basically the same as that used in the prior art,
In this embodiment, the processor interface circuit 200,
It is configured to arbitrate the memory access request from the prefetch circuit 300 in addition to the memory access request from the I / O bus interface circuit 400, and, as will be described later, a memory read from the processor interface circuit 200. after access to memory by request from the prefetch circuit 300, when the prefetch hit signal p f-h it is given from the line 302, in that it is configured to invalidate the memory read operation, the prior art Different from the memory arbitration circuit.

(Prefetch Circuit 300) The memory interface circuit 100 of the present embodiment is mainly different from the conventional memory interface circuit in that it is connected to the processor 600 by a hint signal line 609, and a pointer on this hint signal line 609. The point is to have a prefetch circuit 300 that performs prefetch based on hint information.

The processor interface circuit 200 is
The delay circuit 250 is controlled via the signal line 208, and the read request signal p-rd is sent to the memory access arbitration circuit 500.
Hint signal line 609 at the same timing as issuing 201
The hint signal of the prefetch circuit 30 via the line 209.
Tell 0.

When the hint signal 209 is a hint with a pointer, that is, when the hint signal 209 is 1, the prefetch circuit 300 uses the data read by the read process of the processor interface circuit 200 as an address as described later in detail. It is configured to issue a read request to the main memory 700, prefetch a block including the data of the address, and temporarily hold it in the prefetch circuit 300. Thereafter, it is monitored whether the read request p-rd or the write request p-wr is output by the processor interface circuit 200 due to the subsequent load or store instruction executed by the prefetch circuit 300 or the CPU 600. This read request p-rd or write request p-rd
When wr is output, it is determined whether the block address portion of the read address or write address output to the address bus 105 at that time matches the address of the prefetched block. If a match is detected and the request is a read request,
The prefetched block held in the prefetch circuit 200 is supplied to the processor via the processor interface circuit 200. As a result, before the data requested by the read request is read from the main memory 700, the prefetched data can be supplied to the processor 600 instead of the data. If the request is a write request, the prefetched block is invalidated. In this case,
This is because the data on the main memory is rewritten, and the prefetched block becomes the old block before rewriting.

The prefetch circuit 300 and its operation will be described in detail below with reference to FIGS. FIG. 2 is a block diagram of the prefetch circuit 300.

(Starting Circuit 380) The starting circuit 380 is the processor interface circuit 20.
Read request p-rd and write request p output from 0
-Wr, pointer hint p-hin given from the processor 600 via the delay circuit 250 (FIG. 1)
t, and bus right acquisition signals p-gnt, i o-g nt and I / I provided from the memory access arbitration circuit 500.
By monitoring the write request i o-wr provided from the O interface circuit 400, the write control circuit circuit 350,
The read control circuit 340 and the invalidation control circuit 360 are selectively activated.

The write start signal 355 is sent to the processor 6
00 in response to the read request p-rd from the processor interface circuit, the pointer hint signal p-hint given by the processor 600 has a value of 1, and the memory access The memory access arbitration circuit 700 gives the bus right to the processor interface circuit 200 when the arbitration circuit 500 outputs the bus right acquisition signal p-gnt, that is, in response to a read request caused by a load instruction with a pointer hint. Sometimes, it is output from the AND gate 385.

The read start signal 345 is given from the AND gate 381 only when the read request from the processor interface circuit 200 acquires the bus right.

The invalidation start signal 365 is output to the AND gates 382 and 384 and the OR gate 383 only when the write request from the processor interface circuit 200 or the I / O bus interface circuit 400 acquires the bus right.
Given by the set of.

(Write Control Circuit 350) In the figure, the write control circuit 350 is the processor 6
When a load instruction with a pointer hint is executed by 00, the date read by this load instruction is used as a memory address to prefetch the block to which the data at that address belongs from the main memory 700 and write it in the prefetch buffer 320. Circuit.

As described above with respect to the memory read operation, the processor interface circuit 200 sends the read request p-rd and the memory address to the memory access arbitration circuit 500 in response to the read request from the processor 600, and this circuit 500. Responds to the read request, returns a bus right acquisition signal p-gnt, accesses the main memory 700, and returns a plurality of data, for example, four data and a data valid signal p-vld for each data. To do.

Similarly, the write control circuit 350 issues a read request pf-rd for prefetching to the memory access arbitration circuit 50 when the processor interface circuit 200 outputs the read request p-rd.
0 to line 0 through line 301. In response to the read request, the circuit 500 returns the bus right acquisition signal pf-gnt via the line 303 and accesses the main memory 700 in the same manner as the read request p-rd described above. Then, a plurality of data are sent to the data bus 105, and the data valid signal pf-vld for each data is sent back via the line 304.

More specifically, the write control circuit 350.
Then, the write start signal 355 sets the flip-flop 3570 after the 1-bit latch 3540 for timing adjustment is fetched. This flip-flop 3570 supplies its output via line 357 to register 310 (FIG. 1) as a set signal. The flip-flop 3570 subsequently receives a data valid signal pv from the memory access arbitration circuit 500 in response to a read request output by the processor interface circuit 200 for a pointer instruction load instruction currently being executed.
When Id is first applied to line 504, this signal is passed through OR gate 3595 to flip-flop 3570.
To reset. This signal is repeatedly supplied thereafter, but does not affect the reset of the flip-flop 3570. Output signal 357 of this flip-flop 3570
While the signal is high, the register 310 takes in the data on the data bus 106 every clock. Therefore, the register 310 requests the data output to the data bus 106 at the time when the data valid signal p-vld is first given by the memory access arbitration circuit 500, that is, the load instruction with pointer hint currently being executed. You will eventually capture the data and then retain this data. In this way, the data requested by the load instruction with pointer currently being executed, that is, the pointer indicating the address of other data is fetched into the register 310.

The output of this flip-flop 3570 is
The flip-flop 3580 is set in the next cycle. The flip-flop 3580 supplies its output to the memory access arbitration circuit 500 via the line 301 as a read request signal pf-rd for performing prefetch.

[0039] Once returned bus right acquisition signal pf-gnt via line 303 from the memory access arbitration circuit 500 with respect to the read request p f-r d, the bus right acquisition signal p f-g nt, the timing Set to the adjust latch, this latch 3550 provides its output on line 354 to tristate buffer 390 (FIG. 2). In response to the signal on this line 354, this buffer 390 uses the pointer held in the register 310 (FIG. 2) as a prefetch address and sets the address bus 10
5 to the memory access arbitration circuit 500.
Thus, prefetching of data having this address is started. When this data is read from the main memory 700, it is supplied to the prefetch buffer 320 (FIG. 2) via the data bus 106.

In the present embodiment, it is assumed that reading and writing from the main memory 700 are performed in block units. Therefore, also in the data prefetch, a plurality of other data in the block to which the data of the above address belongs, for example, three data in this embodiment are successively read from the main memory 700 to the data bus 106 in sequence. This is the same as the case of the memory read request from the processor interface circuit 200. Note that the bus right acquisition signal pf - gnt given on the line 303 from the access arbitration circuit 500 resets the flip-flop 3580 at the time when this signal arrives at the latch 3550, and this flip-flop The output of the read request pf-rd that has already been output is stopped.

The data read from the main memory 700 is stored in the prefetch buffer 320 as follows.
Stored in.

The prefetch buffer 320 is composed of four registers in order to hold a plurality of data belonging to the same block, that is, four data in this embodiment. Write register numbers for writing data to these registers are generated as follows. The lower 2 bits of the prefetch address held by the register 310 is supplied to the selector 3520 via the line 346 as the initial value of the write register number. The selector 3520 is
When the output instruction signal 354 supplied from the latch 3550 to the tri-state buffer 390 (FIG. 2) is high, this initial value 346 is selected, and when this output instruction signal is low, the output of the latch 3560 is selected. Is configured. The output 359 of this selector is
It is also supplied to the 2-bit incrementer 3510. The main memory access arbitration circuit 500 includes a main memory 700.
Each time four of the four pieces of data are sent to the data bus 160, the data valid signal pf -v ld is sent via the line 304.
Is configured to supply.

The 2-bit incrementer 3510 is provided for the selector 3 when the data valid signal pf-vld 304 is high.
Write register number 359 output from 520 to 1
When it is incremented and low, the write register number 359 is output as it is. The output of the selector 359 is the 2-bit latch 3560.
Once, and then supplied again to the selector 3520. Therefore, the selector 3520 first selects the initial register number on line 346 when the bus mastership acquisition signal pf - gnt goes high, which causes the output of the latch 3550 to go high. The initial value of the selected register number is supplied to the prefetch buffer 320 and further to the 2-bit incrementer 3510. Since the data valid signal pf -v ld is still low at this point, the 2-bit incrementer 3510 sets the initial value of this register number in the latch 3520 as it is. At this point, the output of the latch 3550 is already low, so the selector 3520 selects the output of the latch 3560 as the write register number,
It is supplied to the prefetch buffer 320. After that, the selector 3 continues until the data valid signal pf -v ld becomes high.
520 repeatedly supplies this initial value to the prefetch buffer. Then, each time the data valid signal pf-vld becomes valid, the incrementer 3510 increments the output of the selector 3520 by one. The updated register number is transferred to the selector 3520 via the latch 3560.
And is supplied to the prefetch buffer 320. In this way, four register numbers are sequentially generated.

The write signal to the prefetch buffer 320 is generated as follows. Bus right acquisition signal p
f-g nt is flip-flop 3590 one cycle after the timing set in the latch 3550.
Set. The set output of the flip-flop 3590 is used as a write signal of the data prefetched from the main memory 700, and is output to the prefetch buffer 320.
To line 358. The prefetch buffer 320 is configured to fetch the data on the data bus 106 into the register of the register number given by the line 359 every clock while this signal 358 is high. Therefore, the register having the initial value of the register number in the prefetch buffer 320 takes in and holds the data existing on the data bus 106 when the data valid signal pf-vld becomes valid first. The other registers are also newly provided with the data valid signal pf-vld.
Every time is output, the data existing on the data bus 106 at that time is held.

The 4 counter 3530 is reset to 0 by the output instruction signal 354 sent to the tri-state buffer 390, and the data valid signal pf− on the line 304 is reset.
The number of times vld is high is counted, and when it becomes 4, the signal 3531 is made high and the flip-flop 3590 is reset. In this way, the write signal is generated for the four data.

It should be particularly noted that in the above operation, the subsequent load instruction is a load instruction with a pointer hint, and the hit check circuit 37 for this instruction is present.
The same applies when the hit check at 0 is hit, except for the following differences. In this case, as will be described later, the data held in the prefetch buffer 320 at that time is output to the data bus 106, and the data is transferred to the processor interface circuit 2.
Not only is it sent to 00, but it is also set in the address register 310 and used for prefetching for this subsequent load instruction, which is different from the above operation. further,
In this case, as will be described later, the read control circuit 34
From 0, the prefetch hit signal pf-hit is line 302
Is output to. This signal is OR'd into the flip-flop 3570 in place of the data valid signal p-vld described above.
The operation is also different in that it is given through the gate 3595 and is used to reset the flip-flop 3570.

(Hit Check Circuit 370) In the hit check circuit 370, the address supplied to the address bus 105 in association with the read request or the write request subsequently issued by the processor interface circuit 200 or the I / O interface circuit 400 is It has a comparator 330 held in the register 310 for judging whether or not it matches the pointer. The determination result 331 of this circuit is used by the read control circuit 340 and the invalidation control circuit 360.

(Read Control Circuit 340) The read control circuit 340 reads the prefetched block from the prefetch buffer 320 when the subsequent load instruction requests the data in the prefetched block after the prefetch is executed. From the processor 60 via the processor interface circuit 200
It is a circuit for supplying 0. That is, in the case where the instruction executed by the CPU after the prefetch is the load instruction, when the hit is detected by the hit check circuit 370, the block held in the prefetch buffer 320 is read out, and the block is held via the processor interface circuit 200. Supply to the processor 600.

More specifically, the cache control circuit 63
0 outputs a read request to the processor interface circuit 200 when the cache 620 does not have the data requested by the subsequent load instruction. This circuit 200
Responded to this read request, as already mentioned,
A read request p-rd is issued. Read control circuit 34
0 responds to this read request. That is, the read control circuit 340 is activated when the read activation signal 345 is given from the activation circuit 380, and at that time, the hit check circuit outputs the match signal 33.
When 1 is given and the prefetch buffer valid signal 366 is input from the invalidation control circuit 360, the data in the blocks in the prefetch buffer are sequentially read by the method described later, and the hit signal pf-hit is sent via the line 302. Tristate buffer 395 (Fig. 2)
And OR gate 260 (FIG. 2) and memory access arbitration circuit 500. Tri-state buffer 395
Transfers the data read from the prefetch buffer 320 to the data bus 106 when the prefetch hit signal pf-hit is applied. The OR gate 260 receives the prefetch hit signal pf-hit.
To the processor interface circuit 200 by the memory access arbitration circuit 500.
It is given instead of vld to instruct the acquisition of data on the data bus 106. In this way, the processor interface circuit 200 takes in the data on the data bus 106 in exactly the same way as when the data is provided from the memory access arbitration circuit 500, and the processor 60 receives the data.
Send to 0. In this way, the block held in the prefetch buffer 320 can be supplied to the processor 600 faster than reading from the main memory 700. The memory access arbitration circuit 500 starts data reading from the main memory 700 in response to the read request p-rd already given from the processor interface circuit 200. It is configured to invalidate this read operation when pf-hit is given. Specifically, even when this data is read, this data is not supplied to the data bus 106, and the data valid signal p-vld is not output to the line 504.

Reading of the prefetch buffer 320 is performed as follows. Read register number 34
9 generates by using the lower 2 bits 346 of the memory address held by the register 301 as the initial value of the read register number.

More specifically, the read control circuit 340.
Is the read address 3 of the prefetch buffer 320.
2-bit incrementer 3410 for generating 49, selector 3420, 3 counter 3430 for counting the number of data transfer cycles, and hit signal pf-hit 302
For generating a 1-bit latch 3440, 3450, 347 for timing adjustment
0 and 2 bit latch 3460 and AND gate 349
It consists of zero. 2-bit incrementer 3410
Is the read register number 3 of the prefetch buffer 320 when the hit signal pf-hit on the line 302 is high.
49 is incremented by 1, and when it is low, the read register number 349 is output as it is. 3 counter 343
The 0 is reset to 0 by the signal 3455 and the line 30
The flip-flop 34 which counts the number of times the hit signal pf-hit on 2 is high, and when the hit signal pf-hit reaches 3 sets the signal 3435 to high to generate the hit signal pf-hit 302.
Reset 80. The selector 3420 outputs the signal 345.
When 5 is high, the initial register number 346 delayed by one cycle by the latch 3470 is selected, and when it is low, the output of the 2-bit incrementer 3410 is selected and the read register number 349 of the prefetch buffer 320 is selected.
And The AND gate 3490 uses the read start signal 3
45, the match signal 331, and the prefetch buffer valid signal 366 are all high, the flip-flop 3480
And the signal 3455 is set high after one cycle to reset the 3 counter 3430, and the selector 34
Let 20 select the initial number 346.

(Invalidation Control Circuit 360) The invalidation control circuit 360 is used when the instruction executed by the processor 600 after prefetching is a store instruction or when a write request is issued from the I / O control circuits 800 and 810. In the hit check circuit 370
Invalidates this prefetched block if a hit is detected by. That is, the invalidation control circuit 3
When the set signal 357 is given to the register 310 (FIG. 2) holding the prefetch address in the data prefetch, the signal 60 generates the prefetch buffer valid signal 366 by this signal, and then the prefetched block. When a write request for rewriting the data inside is executed, it is started by the invalidation start signal 365, and the pre-feffer valid signal 366 is reset using the coincidence signal 331.

More specifically, in FIG. 5, the invalidation control circuit 360 uses the prefetch buffer valid signal 366.
, A 1-bit latch 3610 for timing adjustment, and an AND gate 3630. Flip-flop 3620
Is set by the set signal 357 of the register 310, and is reset when the signal obtained by delaying the invalidation start signal 365 by one cycle and the match signal 331 are both high.

(I / O Bus Interface Circuit 400) The I / O bus interface circuit 400 is basically the same as a known circuit, and the I / O control circuits 800 and 810.
The read request signal io-rd and the write request signal io-wr are supplied to the access arbitration circuit 500 in response to the read / write request of the memory requested from the I / O bus 801 by the lines 401 and 402, respectively. , The bus right acquisition signal io-gnt and the data valid signal io-vld are received from the circuit 500 via the lines 403 and 404, respectively, and the data is transmitted via the address bus 105 and the data bus 106 by the same protocol as the processor interface circuit 200. Transfer.

<Embodiment 2> FIG. 9 shows an embodiment in which a prefetch circuit according to the present invention is provided in a processor. In the present embodiment as well, as in the case of the first embodiment, the processor 1600 has the main memory 700 and the I / O control circuit 8 via the memory interface circuit 100.
Connected to 00. Processor 1600 is different from that of Example 1, CPU 1610, data cache 162
0, a data cache control circuit 1630, a memory access control circuit 1640, and a prefetch control circuit 1300 which is a feature of this embodiment. further,
In this embodiment, a prefetch circuit is provided in the processor and the prefetched block is stored in the data cache 1620. Therefore, in this embodiment, the prefetch buffer 320 of the first embodiment is unnecessary. The hit check by the hit check circuit 370 in the first embodiment is realized by using the hit check function of the data cache itself in the present embodiment. Therefore, in this embodiment, the address comparator 3 in the first embodiment is
30 is unnecessary. As can be seen by comparing the prefetch control circuit 1300 in the present embodiment with the prefetch circuit 300 in the first embodiment (FIG. 2), in the present embodiment,
Since the functions of the read control circuit 340 and the invalidation control circuit 360 are realized by using the read function and the data invalid function that the data cache control circuit 1630 originally has for the data cache 1620, the prefetch of this embodiment is performed. Circuit 1300 is such a circuit 340, 36.
0 is not required. In the present embodiment, there is an instruction cache that holds an instruction and an instruction cache control circuit that controls the instruction cache, but they are not shown for simplification. Nor will it be described below.

First, the execution of the conventional load / store instruction in this embodiment will be briefly described. The operation of the processor at this time is basically similar to that in the conventional technique. When the CPU 1610 executes the load instruction, it sets the read request signal rd1301 to high, puts the address of the data to be loaded on the address bus addr1105, and requests the data cache control circuit 1630 for read processing. The data cache control circuit 1630 first sets the cache search instruction signal chk1634 to high to search the data cache 1620, and hits the hit signal hit16.
Receive results by 35. If there is a hit, the data cache control circuit 1630 outputs the cache read signal c.
The data is read from the data cache 1620 using the rd1632, and the data is transferred to the data bus data1106.
And set the data valid signal vld1634 to high to C
The data is returned to the PU 1610. In the case of a miss, the data cache control circuit 1630 uses the control signal 1639 to inform the memory access control circuit 1640 of the main memory 70.
Request block read from 0, main memory 700
Data from the cache write signal cwr1633
Write to the data cache 1620 using
The data is returned to the PU 1610.

When the CPU 1610 executes the store instruction, the write request signal wr1302 is set to high, an address is placed on the address bus addr1105, and data to be stored is placed on the data bus data1106 to request the write processing to the data cache control circuit 1630. The data cache control circuit 1630 first sets the cache search instruction signal chk1634 to high, and the data cache 1
Search 620 and if there is a hit, data cache 1
Write to 620, main memory 700 if missed
After reading the block from, the data to be stored is written in the data cache 1620.

Also in this embodiment, the CPU 1610 executes the load instruction with pointer hint as in the first embodiment.
When the CPU 1610 decodes the load instruction with pointer hint, it sets the hint signal hint to high, and the line 1209
To the prefetch control circuit 1300. The prefetch control circuit 1300 includes a prefetch address register 1310, an address selector 1320, a timing control circuit 1350, delay circuits 1370 and 1380 for timing adjustment, and a gate 1 for correcting control signals of the data cache control circuit 1630.
It is composed of 330, 1340 and 1360. When the prefetch circuit 1300 detects a read request with a pointer hint, the data bus 110 is sent to the address register 1310 when the data valid signal 1634 is high.
Take in the value of 6. Thereafter, the selector 1320 selects the address register 1310, and the prefetch request signal 1
351 is set high, and the data cache control circuit 1630
Issue a read request to.

The data cache control circuit 1630 searches the data cache 1620, and if there is a miss, reads the data from the main memory 700 into the data cache 1620. That is, the data is prefetched.

The data cache control circuit 1630 attempts to return the data from the cache if there is a hit, and the data from the main memory 700 to the CPU 1610 if there is a miss. However, the prefetched data is returned to the CPU 1610.
Prefetch control circuit 1300 since it does not need to be returned to
Controls the cache read request signal 1361 and the data valid signal 1304 so as not to be high, and suppresses the read processing of the data cache 1620 and the processing of returning data to the CPU 1610.

This prefetched block becomes available for subsequent load instructions, like the block fetched from main memory 700 with a normal load request.

Unlike the first embodiment, this embodiment does not require a prefetch buffer different from the cache, and does not require the invalidation control circuit and the read control circuit used in the first embodiment. Is easy. Further, when the block including the data requested by the load instruction with pointer hint is already held in the data cache, prefetch is not started, so that such a block that may occur in the first embodiment is The useless operation of prefetching does not occur.

Third Embodiment In the first and second embodiments, the address from the processor 600 and the address indicating another block included in the block read from the main memory 700 are both in the main memory 70.
The description has been given assuming that the address is used for reading 0. However, an address (logical address) seen by the program is different from an address (physical address) of the main memory in a normal program other than the OS, and the logical address is converted into a physical address by the TLB in the processor.

In the OS, the memory may be accessed by the physical address, and the memory may be accessed in the area where the logical address and the physical address are associated with each other. The OS can be used by using the load instruction with pointer hint only when the memory is accessed to such an area.
The performance of can also be improved.

FIG. 10 shows a prefetch circuit 2300 in which a circuit for performing address conversion processing is added to the prefetch circuit 300 of FIG. 2 in order to apply the present invention to a normal program which operates at a logical address.

In this embodiment, the processor 600 includes the information about the address conversion for the pointer prefetch.
Bit hint information p-hint1 (signal 2208) and p-hint0 (signal 2209) are output. For example, hint information p-hint1 and p-hint0
If 00 is no prefetch hint, if 01 is 4K
Prefetch pointer within byte page, 1 for 10
Mbyte page pointer prefetch, 11 means pointer prefetch by physical address.

Hint information p-hint1 and p-hint
The operations when 0 is 00 and when 11 are the same in the prefetch circuit 2300 as the read processing without pointer hint and the read processing with pointer hint described in the first embodiment. The difference is the hint information p-hi
When nt1 and p-hint0 are 01 or 10, at this time, the loaded data is not used as a prefetch address as it is, but the physical address used for the previous load is used as a page address according to the page size. The prefetch operation at this time will be described below.

Compared to the prefetch circuit 230 of FIG. 2, the prefetch circuit 2300 receives 2 bits as prefetch hint information, the register 2310, the selectors 2320 and 2330, and the delays 2340 and 235.
0, an EOR circuit 2360 and an OR circuit 2370 are added, and the delay 23 is added to the write control circuit 350.
The difference is that a circuit for generating a signal 2357 for controlling 30, 2350 is added. Others operate in the same manner as the prefetch circuit 230 of FIG.

The OR circuit 2370 notifies the activation circuit 380 that the load instruction is a pointer hint. The register 2310 is the register 310 during the prefetch process.
The address is latched at the timing when the address is output to the address bus 105. This address is a physical address for accessing the main memory 700. The delays 2330 and 2350 are controlled by the write control circuit 350 via the signal 2357, and the hint information p-hin is set at the same timing as the set signal 357 of the register 310.
It outputs t1 and p-hint0 to signals 2341 and 2351. When writing the address to be prefetched next from the block read by the load instruction with pointer hint to the register 310, the selectors 2320 and 2330 store the address (logical address) in the read block and the physical value held by the register 2310. One of the upper addresses is selected according to the control signals 2351 and 2361. That is, in this embodiment, the EOR circuit 2360 causes the hint information p-hint1 and p-hint0 to be 01.
In the case of, the lower 12 bits of the 32-bit address are set from the data bus 106, but the upper 20 bits of the higher 20 bits of the physical address in the register 2310 are set via the selector 2320, and the hint information p-hi.
When nt1 and p-hint are 10, the lower 20 bits are set from the data bus 106, but the upper 12 bits are control signals so that the upper 12 bits of the physical address in the register 2310 are set via the selector 2330. 2351 and 2361 are generated.

Therefore, when the hint information p-hint1 and p-hint0 are 01, the address determined by the pointer read by this instruction from the data belonging to the 4 Kbyte page to which the address designated by the load instruction with hint belongs When the hint information p-hint1 and p-hint0 are 10, the block of the address determined by the pointer read by this instruction is read from the 1 Mbyte page to which the address specified by the hinted load instruction belongs. Prefetch.

[0071]

According to the present invention, when an instruction for reading data from a memory is executed, if the data includes address information of other data, the instruction is read from the memory according to the request of the instruction. The issued data can be used to read other data. Originally, the program including the instruction is read out from the memory Lud over data knows whether pointers to other data by any instructions. Therefore, according to the present invention, the execution of the load instruction designating the pointer is used to prefetch other data designated by the pointer, so that the timing of prefetching can be easily determined. Moreover, each time such one instruction is executed, the data used by the instruction subsequent to the instruction is prefetched, so that the circuit required for prefetching becomes simple. In addition, because prefetched data is often certain to be used, it is unlikely that it will never be used after it has been prefetched, so prefetching can be wasted. Is few.

[Brief description of drawings]

FIG. 1 is a diagram showing a first embodiment of an information processing apparatus according to the present invention.

2 is a schematic circuit configuration diagram of a prefetch circuit used in the device of FIG.

3 is a schematic circuit configuration diagram of a read control circuit used in the device of FIG.

4 is a schematic circuit configuration diagram of a write control circuit used in the device of FIG.

5 is a schematic circuit configuration diagram of an invalidation control circuit used in the device of FIG.

FIG. 6 is a diagram showing an example of a conventional pointer type data structure.

FIG. 7 is a diagram showing an example of storage locations in a memory in which the pointer type data structure of FIG. 6 is held.

8 is a diagram showing an example of a format of an instruction used in the apparatus of FIG.

FIG. 9 is a diagram showing a second embodiment of the information processing apparatus according to the present invention.

FIG. 10 is a diagram showing a third embodiment of the information processing apparatus according to the present invention.

[Explanation of symbols] 100 ... Memory interface circuit, 200 ... Processor
Interface circuit, 250 ... Delay circuit, 300
... prefetch circuit, 400 ... I / O bus interface
Circuit, 500 ... Memory access arbitration circuit, 600 ...
Processor, 610 ... CPU, 620 ... Cache, 63
0 ... Cache control circuit, 700 ... Main memory, 80
0 ... I / O control circuit, 810 ... I / O control circuit.

─────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-4-44139 (JP, A) JP-A-7-56755 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) G06F 9/30-9/42 G06F 12/02-12/12

Claims (9)

(57) [Claims] 1. An information processing apparatus having a memory for holding data and a processing device for executing an instruction, wherein a first request for reading first data from the memory is made.
In response to execution of the data read instruction, reads the data of the first from the first storage location of the memory, the first data read is supplied to the processing unit, further said second data Requesting a prefetch of the first
The first data read in response to the data read command
Prefetching the second data from a second storage location of the memory that is selected depending on the data, temporarily holding the prefetched second data, and storing the second data of the second data from the memory. Subsequent read request
Execution of the second data read instruction of
In response to the above , the data prefetch method of supplying the temporarily held second data to the processing device. 2. The information processing apparatus further comprises a cache for holding a part of the data held in the memory, and the method is responsive to the execution of the first instruction, Detecting whether or not data is held in the cache, and supplying the first data from the cache to the processing device when the first data is held in the cache, The method further comprises activating the read to read the first data from the memory when the data is not held in the cache, and the step of temporarily holding the second data comprises:
Holding prefetched said second data to said cache
Comprising the step of lifting, the method, in response to execution of the instruction of the second, the second data is detected whether or not it is held in the cache, the second data is the cache When the second data is not held in the cache, the step of supplying the second data is started to supply the second data from the cache to the processing device when the second data is not held in the cache. 2. The data prefetch method according to claim 1, further comprising the step of issuing a read request for the second data to the memory. 3. The step of reading the first data comprises the step of reading a first block containing the first data from the memory and writing the read first block to the cache. said step of supplying the first data read from the first block to select said first data includes a step of supplying to the processing apparatus, the prefetching the second data The step comprises prefetching a second block containing the second data from the memory, and the step of temporarily holding the prefetched second data comprises the prefetching the second prefetched second data . block
The has a step of writing to said cache, said step of providing data of said second, said cache
Data prefetching method according to claim 2, wherein the written second blocks in Interview by selecting said second data having a step of supplying to the processing apparatus. 4. The step of prefetching the second data retains an address of the first storage location of the memory in which the first data is retained, and the first data is stored in the memory. When read,
A generated address is generated by combining the held address of the first storage location and the first data to generate an address of a second storage location of the memory where the second data is to be prefetched. The second from the memory based on the address
1. Pre-fetching the data of
Data prefetch method described. 5. A memory for holding first and second data, a processing device for executing an instruction, and a data read instruction for requesting reading of the first data from the memory are executed by the processing device. In response to the request, a read request that requests reading of the first data held in the storage location of the memory designated by the data read command is supplied to the memory, and the memory is responsive to the read request. A first data read circuit connected to the memory and the memory for supplying the first data read from the memory to the processor, and the memory selected according to the first data. Second
The memory and the processing unit, in response to the data read command that further requests prefetching of the second data held in the memory location, supplying a read request that requests reading of the second data to the memory. Second connected to
And a temporary read circuit connected to the memory for temporarily holding the second data read from the memory in response to the read request supplied from the second data read circuit. A data storage device and reading the second data from the temporary data storage device in response to execution of another data read instruction in the processing device that requests reading of the second data from the memory. An information processing device connected to the temporary data storage device and the processing device, the information processing device having a data supply circuit for supplying the processing device. 6. The processing device comprises: a processing unit for executing an instruction; a cache for holding a part of the data held in the memory; and a data read instruction when a data read instruction is executed by the processing unit. Detecting whether or not the data requested by the instruction is held in the cache, and supplying the data from the cache to the processing unit when the data requested by the data read instruction is held in the cache Further, a cache control circuit connected to the processing unit, the cache, and the memory, wherein the first read circuit does not hold the data requested by the data read instruction in the cache. Sometimes, the read command included in the cache control circuit that supplies the data read command to the memory is read. 6. The information processing apparatus according to claim 5, further comprising a read request circuit, wherein the cache is used as the temporary data storage device, and the cache control circuit includes the data supply circuit. 7. The data read command requesting to read the data from the memory includes a field indicating whether the data read command further includes a read request for the other data, and the second data. The information processing apparatus according to claim 5, wherein the read circuit responds to the field of the data read command. 8. The information processing apparatus according to claim 5, further comprising a pointer that uses the first data to point to the second storage location that holds the second data. 9. An information processing device having a memory for holding data and a processing device for executing instructions, wherein a first request for reading first data from the memory is made.
Reading the first data from the first storage location of the memory, supplying the read first data to the processing device, and reading the first data. When the instruction indicates prefetching of the second data, the second data is prefetched from the second storage location of the memory indicated by the first data, and the second prefetched data is temporarily fetched. And temporarily storing the second data in response to execution of a subsequent second data read command by the processing device, the second data being stored in the memory and requesting the second data to be read from the memory. The information processing apparatus according to claim 5, wherein the information processing apparatus supplies the information to a processing device.