Translation lookaside buffer match detection using carry of lower side bit string of address addition

[0002] 1. Field of the Invention

[0003] The present invention relates to a TLB circuit for converting a virtual address to a physical address, particularly to a technique of judging at a high speed whether or not a virtual address which has received an access request matches a virtual address stored inside a processor.

[0004] 2. Related Background Art

[0005] To eliminate a speed difference between a processor and a main memory, it is general to dispose a cache memory between them. The cache memory is incorporated in the processor in some cases, or disposed outside the processor in the other cases.

[0006] When data requested by the processor exists in the cache memory (cache hit), the data is transferred from the cache memory to the processor, and therefore, the processor does not have to access the main memory, so that the processor can perform the processing at a high speed. On the other hand, when the data requested by the processor does not exist in the cache memory, the processor has to directly access the main memory, so that it takes much time to perform the processing.

[0007] A recent processor employs a virtual address system in which a part of a virtual address space is allocated to the main memory. By employing the virtual address system, it is possible to access memory, regardless of the main memory.

[0008] The virtual address can be obtained, for example, by adding a base address and an offset address. To perform this addition, an adder is disposed in the processor. Moreover, in the processor, a TLB circuit for converting the virtual address to a physical address is disposed. The TLB circuit outputs a signal indicating whether or not the virtual address which has been received from the outside matches the virtual address stored inside.

[0009] In the recent processor, the virtual address has a large number of bits, so that it takes much time to perform the addition processing in the adder. Therefore, if the address conversion processing in the TLB circuit is started after the addition processing in the adder has been completed, much time is taken until the physical address is outputted. Therefore, when a part of the physical address is used for checking the cache hit, the process in case of the cache hit cannot be performed at a high speed.

[0010] To solve the problem, in U.S. Pat. No. 5,606,683, based on the result of addition of some bit strings of the base address and the offset address and digit overflow information, the match/mismatch of the virtual address is detected. However, also in the above-described document, the adder is used to calculate the address. Since the address conversion processing cannot be performed until the output of the adder is obtained, the cache hit check cannot be performed at a high speed.

[0011] An object of the present invention is to provide a microprocessor in which conversion from a virtual address to be accessed by the processor into a physical address can be performed at a high speed and it is possible to determine at a high speed whether or not cache hit is.

[0012] To attain the above-described object, there is provided a translation lookaside buffer (TLB) circuit for converting a virtual address to a physical address comprising:

[0013] a carry storage section for storing digit overflow information when a lower side bit string of a base address and a lower side bit string of an offset address of virtual address information as a comparison criterion are added to each other;

[0014] a upper side address storage section for storing a upper side bit string of the base address and a upper side bit string of the offset address of the virtual address information as the comparison criterion;

[0015] a carry comparator for comparing a digit overflow information when a lower side bit string of the base address and a lower side bit string of the offset address of the virtual address information which has received an access request are added to each other, with the digit overflow information stored in said carry storage section;

[0016] a upper side address comparator for detecting whether or not the upper side bit string of the base address of the virtual address information which has received the access request matches the upper side bit string of the base address stored in said upper side address storage section, and for detecting whether or not the upper side bit string of the offset address of the virtual address information which has received the access request matches the upper side bit string of the off set address stored in said upper side address storage section; and

[0017] a match detector for outputting a match signal of the virtual address only when comparison results by said carry comparator are matched and comparison results by the upper side address comparator are matched.

[0018] According to the present invention, for the lower side bit strings of the base and offset addresses, instead of comparing the addition results of both addresses, carry signals are compared, so that it can be detected at a high speed whether or not the virtual addresses are matched.

[0019] Moreover, there is provided a translation lookaside buffer (TLB) circuit for converting a virtual address to a physical address comprising:

[0020] a first storage section for storing a upper side bit string of a base address of virtual address information as a comparative criterion;

[0021] a second storage section for storing a bit string obtained by adding 1 to a upper side bit string of an offset address of the virtual address information in the case where there is a digit overflow when a lower side bit string of the base address and a lower side bit string of the offset address of the virtual address information as the comparison criterion are added to each other, and for storing the upper side bit string of the offset address of the virtual address information in the case where there is no digit overflow;

[0022] a third storage section for storing the upper side bit string of the offset address of the virtual address information in the case where there is the digit overflow when the lower side bit string of the base address and the lower side bit string of the offset address of the virtual address information as the comparison criterion are added to each other, and for storing the bit string obtained by subtracting 1 from the upper side bit string of the offset address of the virtual address information in the case where there is no digit overflow;

[0023] a first comparator for comparing the upper side bit string of the base address of the virtual address information which has received the access request, with the bit string stored in said first storage section;

[0024] a second comparator for comparing the lower side bit string of the base address of the virtual address information which has received the access request, with the bit string stored in said second storage section;

[0025] a third comparator for comparing whether or not the lower side bit string of the base address of the virtual address information which has received the access request matches the bit string stored in said third storage section; and

[0026] a match detector for outputting a signal indicating whether or not the virtual address which has received the access request matches the virtual address as the comparison criterion on the basis of comparison results of said first to third comparators.

[0027] Moreover, according to the present invention, after the offset address is regulated in accordance with a value of carry signal, the addresses are compared. Therefore, regardless of the presence/absence of a carry, it is possible to accurately compare the virtual addresses.

[0028] FIG. 1 is a block diagram showing an inside configuration of a microprocessor according to the present invention.

[0029] FIG. 2 is a diagram showing an inside configuration of MMU 3.

[0030] FIG. 3 is a diagram showing an example of conversion table 100 in JTLB 31.

[0031] FIG. 4 is a diagram showing data structures of base address, offset address, virtual address, and physical address.

[0032] FIG. 5 is a block diagram showing a detailed configuration of the main section of MMU 3 and LSU 4.

[0033] FIG. 6 is a diagram showing concrete operation of FIG. 5.

[0034] FIG. 7 is a block diagram showing a first configuration example of DTLB 33.

[0035] FIG. 8 is a block diagram showing a second configuration example of DTLB 33.

[0036] FIG. 9 is a circuit diagram showing an example of carry lookahead circuit 88.

[0037] FIGS. 10aand 10bare diagrams showing examples of calculation of the base address and the offset address.

[0038] FIG. 11 is a diagram showing an example in which cache hit detection cannot accurately be performed in the first and second configuration examples.

[0039] FIG. 12 is a block diagram showing a third configuration example of DTLB 33.

[0040] An embodiment of microprocessor according to the present invention will be described hereinafter in detail with reference to the drawings. In the following, as an example, MIPS type of microprocessor will be described.

[0041] FIG. 1 is a block diagram showing an inside configuration of the microprocessor according to the present invention. The microprocessor of FIG. 1 comprises a Bus Interface Unit 1 connected to an external bus B1, IFU (Instruction Fetch Unit) 2 which fetches instructions to be executed by a processor, an MMU (Memory Management Unit) 3 which converts virtual addresses to physical addresses, an LSU (Load Store Unit) 4 which executes instructions relating to load/store, a plurality of executing units 5a,5band 5cwhich execute the instructions other than load/store, FPU (Floating Point Units) 6a,6bwhich execute floating point calculation, and a Control Logic 7 which controls each block in the processor.

[0042] The IFU 2 includes a PC-pipe 21 which generates a PC (Program Counter) by referring to the BTAC which stores branch addresses of instructions such as a branch instruction, an ICACHE (Instruction Cache memory) 22 which temporarily stores the instructions, and an Instruction issue & Staging block 23 which recognizes the type of the instruction and selects the executing unit to execute the recognized instruction.

[0043] The MMU 3 has three TLBs (Translation Lookaside Buffers) which convert the virtual addresses to physical addresses. Address converting information needed by the processor, such as a physical page number and memory protection information, are written to the TLBs. Based on this information, the MMU 3 executes the conversion to the physical address.

[0044] Three types of the TLBs in the MMU 3 are a JTLB (Joint Translation Lookaside Buffer) 31, an ITLB (Instruction Translation Lookaside Buffer) 32, and a DTLB (Data Translation Lookaside Buffer) 33.

[0045] The ITLB 32 and the DTLB 33 are called a micro TLB as a generic name. The ITLB 32 is a specific TLB connected directly to a datapath of the virtual address of the instruction. The DTLB 33 is a specific TLB connected directly to the datapath of the virtual address of data. These TLBs have a small number of entries, and execute address conversion at a high speed. A portion of a conversion table generated by the JTLB 31 is copied to the ITLB 32 or the DTLB 33 as necessary.

[0046] The JTLB 31 is controlled by software, while the coherency between micro TLBs and the JTLB is maintained by hardware. The microprocessor issues an exception when there is no conversion table in the JTLB 31. An exception handler searches the corresponding page from a page table on an OS memory and writes the information into the JTLB 31.

[0047] The LSU 4 comprises a DCACHE (Data Cache Memory) 41 which temporarily stores data read out from and written into the external memory, an SPRAM (Scratch Pad RAM) 42 used for specific purposes other than caching, and an address generator (Virtual Address Computation) 43 which generates the virtual address necessary to access the DCACHE 41 and the SPRAM 42.

[0048] The Control Logic 7 controls each block in the processor. Inside the Control Logic 7, a Control Register 71 is provided.

[0049] Next, the operation of the microprocessor shown in FIG. 1 will be described. First, the IFU 2 fetches the instructions based on the PC generated by the PC-pipe 21. Additionally, the PC is a virtual address.

[0050] The ITLB 32 converts the PC from the virtual address to the physical address. The converted physical address is employed for searching an ITAG in the ICACHE 22. Specifically, the physical address is used to detect whether or not the instruction designated by the PC exists in the ICACHE 22. When the instruction designated by the PC does not exist in the ICACHE 22, that is, when a cache-miss occurs, the access to the external memory (not shown) is performed using the physical address.

[0051] When the cache-miss occurs, information indicative of the occurrence of the cache-miss and physical address information are transferred to Control Logic in the BIU 1. The BIU 1 accesses the external memory based on these information. When the access to the external memory finishes, a signal informing of acquisition of a cache line is supplied to the IFU 2. The IFU 2 writes the data obtained by the access to the memory into the ICACHE 22. Additionally, among the instructions included in the refilled cache line, the instruction designated by the PC and in certain cases, several instructions following the instruction designated by the PC are supplied to the Instruction issue & Staging block 23.

[0052] On the other hand, if the instruction designated by the PC exists in the ICACHE 22, the corresponding instruction in the ICACHE 22 and in certain cases, several instructions following the instruction designated by the PC are supplied to the Instruction issue & Staging block 23.

[0053] The Instruction issue & Staging block 23 recognizes the types of the instructions and determines the executing unit which executes the instructions, for example, the LSU 4, and other executing units. In this case, the Instruction issue & Staging block 23 dynamically determines any one of the executing units in accordance with the vacant state of each executing unit.

[0054] For example, in the case where the recognized instruction is a load/store instruction, since only the LSU 4 is able to execute the instruction, the Instruction issue & Staging block 23 sends the instruction to the LSU 4 at the time when the LSU 4 is ready to execute the instruction.

[0055] FIG. 2 is a diagram showing the inner configuration of the MMU 3. As described above, three TLBs are provided inside the MMU 3. Among these TABS, the JTLB 31 is a true TLB. The JTLB 31 has, for example, 48 entries, and by mapping the virtual address by each page, generates a conversion table for conversion to the physical address.

[0056] The conversion table 100 generated by the JTLB 31 is copied to the ITLB 32 and the DTLB 33, as required. Thus, the reason for dividing the TLBs into three pieces is that it takes much time to perform an address conversion processing, because the JTLB 31 has many entries. Therefore, only a portion which is actually necessary for the conversion in the conversion table 100 is copied to the ITLB 32 or the DTLB 33 in order to perform the conversion processing at a high speed.

[0057] FIG. 3 is a diagram showing an example of the conversion table 100 in the JTLB 31. As shown in FIG. 3, in the conversion table 100, the page number of the virtual address, the corresponding physical address, and flag information are recorded.

[0058] The flag information includes a C flag showing whether or not the cache is allowable, a D flag showing whether or not the writing to the memory is allowable, a V flag showing whether or not conversion entry is valid, and an S flag showing whether or not the access to the SPRAM is performed.

[0059] FIG. 4 is a diagram showing data structures of base address, offset address, virtual address, and physical address. Upper side 20 bits of the virtual address indicate VPN (Virtual Page Number), and lower side 12 bits of the virtual address Indicate page offset.

[0060] The VPN is constituted of upper side 20 bits [31:12] of the base address, upper side 3 bits [14:12] of the offset address, a sign bit S indicating a positive or negative sign added to the offset address, and a carry bit C obtained by adding the lower side 12 bits of each of the base address and the offset address.

[0061] The page offset of the virtual address is a result of adding the lower side 12 bits of the base address and the lower side 12 bits of the offset address.

[0062] In FIG. 1, DTLB 33 converts the VPN to PFN (Physical Frame Number) Upper side 20 bits of the physical address indicate PFN. and lower side 12 bits indicate the page offset. Additionally, the page offset of the physical address is the same as that of the virtual address.

[0063] FIG. 5 is a block diagram showing a detailed configuration of the main section of MMU 3 and LSU 4. An adder 34 shown in FIG. 5 adds the base address and the offset address in the virtual address which has received a request for access to the external memory. In this case, after the offset address is sign-extended to 32 bits, the address is added to the base address.

[0064] The adder 34 outputs the VPN (Virtual Page Number) indicating the addition result, and a carry signal indicating the presence/absence of digit overflow of the lower side bit string of the virtual address.

[0065] The DTLB 33 has a CAM (Contents Addressable Memory) 35 for detecting whether or not the virtual address which has received the access request matches the virtual address corresponding to the data stored in the DCACHE 41, and a physical address storage section 36 for storing the physical address of the data stored in the DCACHE 41, and the like.

[0066] The CAM 35 detects whether or not the address which has received the access request matches the address of the data stored in the DCACHE 41, based on the base and offset addresses which has received the access request and the carry signal outputted from the adder 34, and outputs a match/mismatch signal.

[0067] When the match signal is outputted from the CAM 35, the physical address storage section 36 outputs the physical address corresponding to the match signal Moreover, when the match signal is outputted from the CAM 35, a gate circuit 37 outputs a hit signal of the DTLB 33. The output of the gate circuit 37 is used for judging whether or not the processing of the processor is to be stalled.

[0068] The VPN outputted from the adder 34 is applied to the JTLB 31. The JTLB 31 refers to the conversion table, and outputs the PFN corresponding to the VPN, and the above-described C and D flags. Here, after the adder 34 performs addition, the VPN is applied to the JTLB 31 in order to minimize penalties in the case where there is no match entry in DTLB 33.

[0069] Moreover, the lower side bit string of VPN outputted from the adder 34 is applied as an index address to DTAG 44 and DCACHE 41. Each of the DTAG 44 and the DCACHE 41 decodes the index address to set an entry. Specifically, the bit string obtained by shifting the index address toward the lower side bit side by six bits is set as the entry when a cache line holds 16 word. The DTAG 44 outputs the physical address of the corresponding entry, and the DCACHE 41 outputs the data of the corresponding entry.

[0070] A comparator 45 compares the physical address outputted from the DTAG 44 with the physical address which is outputted from the physical address storage section 36 after the detection of the match by the CAM 35, and outputs a signal indicative of cache hit when both addresses are matched.

[0071] FIG. 6 is a diagram showing the concrete operation of FIG. 5. FIG. 6 shows the case where the base address which has received the request for access to the external memory is 0x12344567, and the offset address is 0x1111.

[0072] In this case, the output of the adder 34 is 0x12344567+0x00001111=0x12345678, the carry signal is 0, the upper side bit string of the base address applied to the DTLB 33 is 0x12344, and the upper side bit string of the offset address is 0x1111.

[0073] Moreover, FIG. 6 shows an example where there are four entries in the DTLB 33, and the data corresponding to the entries as shown in FIG. 6 are stored in the CAM 35 and the physical address storage section 36. In FIG. 6, “V” indicates that the DTAG 44 is valid, and “I” indicates that the DTAG 44 is invalid.

[0074] In the example of FIG. 6, a topmost entry is matched, and physical address 0x43215 is outputted along a bold arrow in FIG. 6. Additionally, C indicates that cache is allowable, and W indicates that data can be read/written. Moreover, U indicates that cache is inhibited, while R indicates that data can be read, but data writing is inhibited.

[0075] Moreover, index address 0x678, which is the lower side bit string of output 0x12345678 of the adder 34, is supplied to the DTAG 44 and the DCACHE 41. The DTAG 44 sets bit string 0x1b obtained by shifting 0x678 to the lower side by six bits as the entry, and outputs physical address information V_—0x43215 stored in the DTAG 44.

[0076] The comparator 45 compares the physical address 0x43215 outputted from the DTAG 44 with the physical address 0x43215 outputted from the DTLB 33. In this case, since both addresses are matched, the comparator outputs a signal indicating cache hit.

[0077] Furthermore, the DCACHE 41 sets the bit string 0x1b obtained by shifting the index address 0x678 to the lower side by six bits as the entry, and outputs data 0x12345678_—9abcef0 stored in the DTAG 44.

[0078] (First Configuration Example of DTLB 33)

[0079] FIG. 7 is a block diagram showing a first configuration example of the DTLB 33. The DTLB 33 of FIG. 7 has a sign extender 81 for sign-extending the offset address from 16 bits to 32 bits; an adder 82 for adding the base address to the sign-extended offset address; a comparator (upper side address comparator) 84 for judging whether or not upper side 20 bits [31:12] of the base address match the base address stored in a upper side address storage section 83 in the CAM 35, and upper side 4 bits [15;12] of the offset address match the offset address stored in the upper side address storage section 83 in the CAM 35; a comparator (carry comparator) 86 for judging whether or not the carry signal outputted from the adder 82 matches the carry signal stored in a carry storage section 85 in the CAM 35; and a match detector 87 for outputting a match signal when the comparison results of the comparators 84 and 85 are matched. The comparator 84 is constituted of, for example, an EXOR gate, and the match detector 87 is constituted of, for example, an AND gate.

[0080] The operation of the DTLB 33 of FIG. 7 will next be described. The comparator 84 compares upper side 20 bits [31:12] of the base address of 32 bits with the base address stored in the upper side address storage section 83 in the CAM 35, additionally compares upper side 4 bits [15:12] of the offset address of 16 bits with the offset address stored in the upper side address storage section 83 in the CAM 35, and outputs a match signal when the addresses are matched.

[0081] On the other hand, the comparator 86 outputs a match signal when the carry signal outputted from the adder 82 matches the carry signal stored in the CAM 35. As described above, with respect to the lower side 12 bits of the virtual address, the judgment of match/mismatch is performed only with the carry signal. Therefore, the judgment of match/mismatch can be performed before the addition processing in the adder 82 is completed, and the speed of address conversion is improved.

[0082] (Second Configuration Example of DTLB 33)

[0083] In FIG. 7 since the adder 82 is used to generate the carry signal, there is a problem that much time is required until the carry signal is generated. To solve the problem, in a second configuration example, a carry lookahead circuit is disposed to generate the carry signal at a high speed.

[0084] FIG. 8 is a block diagram showing the second configuration example of the DTLB 33. The DTLB 33 of FIG. 8 is constituted in the same manner as that of FIG. 7, except that the adder 82 is replaced with a carry lookahead circuit 88.

[0085] FIG. 9 is a circuit diagram showing one example of the carry lookahead circuit 88. In the example, four bits A0 to A3, B0 to B3 are added to output the carry signals. The circuit of FIG. 9 can output the carry signal before the final addition result is calculated.

[0086] By providing the carry lookahead circuit 88 as shown in FIG. 9, it is possible to quickly judge whether or not the carry signals are matched, and as a result, it is possible to judge at a high speed whether or not DTLB hit is.

[0087] (Third Configuration Example of DTLB 33)

[0088] In the above-described first and second configuration examples, with respect to the lower side 12 bits of the virtual address, only the match/mismatch of the carry signals is detected. Therefore, there is a likelihood which is erroneously judged as a mismatch, even if the addition result of the base address and the offset address is originally matched.

[0089] For example, FIG. 10ashows an example where the base address stored in the CAM 35 is ‘0x80000000’, and the offset address is ‘0x1234’. Since the addition result of both addresses is ‘0x80001234’, the carry signal is 0 (no digit overflow).

[0090] On the other hand, FIG. 10bshows an example where the base address which has received the access request is ‘0x8000fff’, and the offset address is ‘0x0125’. In this case, although the addition result of both addresses is ‘0x80001234’, the offset address value and carry signal value of the latter example are different from those of the former example. Therefore, the comparison results of the comparators 84, 86 of FIG. 7 are not matched, and the match detector 87 finally outputs a signal indicative of DTLB miss hit.

[0091] FIG. 11 is a diagram showing an example that the first and second configuration examples cannot perform accurately DTLB hit detection As shown in (1) of FIG. 11, when upper side four bits of the offset address is A, and the carry signal from the lower side 12 bits is 0, the addition result is A. Moreover, as shown in (2) of FIG. 11, also when upper side four bits of the off set address is (A−1), and the carry signal from the lower side 12 bits is 1, the addition result is A, but cache miss hit is judged in the first and second configuration examples.

[0092] Similarly, as shown in (3) of FIG. 11, when upper side four bits of the offset address is (A+1), and the carry signal from the lower side 12 bits is 0, the addition result is (A+1). Moreover, as shown in (4) of FIG. 11, also when upper side four bits of the offset address is A, and the carry signal from the lower side 12 bits is 1, the addition result is (A+1), but also in this case, cache miss hit is judged in the first and second configuration examples.

[0093] When the DTLB 33 makes a mistake, the conversion by the JTLB 31 is necessary, and consequently, penalty is generated

[0094] FIG. 12 is a block diagram showing a third configuration example of the DTLB 33. In FIG. 12, the carry signal values differ, but the addition results of the base and offset addresses are the same, then the DTLB 33 judges DTLB hit.

[0095] In the same manner as in FIG. 7, the DTLB 33 of FIG. 12 has the sign extender 81 and the adder 82. Additionally, the DTLB 33 has a first storage section 91 for storing upper side 20 bits [31:12] of the base address; an inverter IV1 for inverting the logic of the carry signal from the adder 82; an inverter IV2 for inverting the output logic of the inverter IV1; an adder 92 for adding 1 to upper side 4 bits [15:12] of the offset address only when the output of the inverter IV2 is a upper side (carry signal is 1); a subtracter 93 which subtracts 1 from upper side 4 bits [15:12] of the offset address only when the output of the inverter IV1 is a upper side (carry signal is 0); a second storage section 94 for storing the output of the adder 92; a third storage section 95 for storing the output of the adder 93; a first comparator 96 for comparing 20 bit data stored in the first storage section 91 with the upper side 20 bit data of the base address which has received the request for access to the external memory; a second comparator 97 for comparing four bit data stored in the second storage section 94 with upper side 4 bits of the offset address which has received the access request; a third comparator 98 for comparing four bit data stored in the third storage section 95 with upper side 4 bits of the offset address; a gate circuit 99 for outputting a match signal when the comparison results of the comparators 96, 97 are matched; a gate circuit 110 for outputting a match signal when the comparison results of the comparators 96, 98 are matched; and a match detector 111 for selecting and outputting either one of outputs of the gate circuits 99, 110 in accordance with the logic of the carry signal. The first to third storage sections 91, 94, 95 are arranged in the CAM 35 shown in FIG. 5.

[0096] The operation of the circuit of FIG. 12 will next be described. When the upper side 4 bits of the offset address in the virtual address refilled in the DTLB 33 are A, and the carry signal is 0, the adder 92 outputs A as it is, and A is stored in the second storage section 94. Moreover, the subtracter 93 outputs (A−1), and (A−1) is stored in the third storage section 95.

[0097] Thereafter, when the upper side 4 bits of the offset address which has received the request for access to the external memory are A, and the carry signal is 0, the comparison result of the second comparator 97 is matched, and the comparison result of the third comparator 98 is mismatched. Therefore, the output of the gate circuit 99 becomes a high level, and the output of the gate circuit 110 becomes a low level. In this case, since the carry signal is 0, the match detector 111 selects the output of the gate circuit 99. In this case, since the output of the gate circuit 99 is a high level, the match detector 111 outputs a match signal.

[0098] When the upper side 4 bits of the offset address which has received the request for access to the external memory are (A−1), and the carry signal is 1, the comparison result of the third comparator 98 is matched, and the comparison result of the second comparator 97 is mismatched. Therefore, the output of the gate circuit 110 becomes a high level, and the output of the gate circuit 99 becomes a low level. In this case, since the carry signal is 1, the match detector 111 selects the output of the gate circuit 110. In this case, since the output of the gate circuit 110 becomes a high level, the match detector 111 outputs a match signal.

[0099] On the other hand, when the upper side 4 bits of the offset address in the virtual address refilled in the DTLB 33 are A, and the carry signal is 1, the adder 92 outputs (A+1), and (A+1) is stored in the second storage section 94. Moreover, the subtracter 93 outputs A as it is, and A is stored in the third storage section 95.

[0100] Thereafter, when the upper side 4 bits of the offset address which has received the request for access to the external memory are A, and the carry signal is 1, the comparison result of the third comparator 98 is matched, and the comparison result of the second comparator 97 is mismatched. Therefore, the output of the gate circuit 110 becomes a high level, and the output of the gate circuit 99 becomes a low level. In this case, since the carry signal is 1, the match detector 111 outputs a match signal which is the output of the gate circuit 110.

[0101] Moreover, when the base address which has received the request for access to the external memory is (A+1), and the carry signal is 0, the comparison result of the second comparator 97 is matched, and the comparison result of the third comparator 98 is mismatched. Therefore, the output of the gate circuit 99 becomes a high level, and the output of the gate circuit 110 becomes a low level. In this case, since the carry signal is 0, the match detector 111 outputs the match signal which is the output of the gate circuit 99.

[0102] As described above, in the circuit of FIG. 12, the value of the offset address stored in the CAM 35 is regulated by the value of the carry signal. Therefore, even if, as shown in FIG. 10, the original offset addresses are mismatched, but the addition results of the offset and base addresses are the same, then it is judged that the virtual addresses are matched. Therefore, this can improve the hit ratio without any timing penalty and with minimum hardware, and the processing speed of the processor is improved.