Electrical computers and digital processing systems: processing – Instruction fetching – Prefetching
Reexamination Certificate
2001-02-15
2003-04-01
Kim, Kenneth S. (Department: 2183)
Electrical computers and digital processing systems: processing
Instruction fetching
Prefetching
C711S119000, C711S120000, C712S205000, C712S241000
Reexamination Certificate
active
06542982
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a data processor and a data processing system, and more particularly to a data processing system, which may provide an improved facility for prefetching instructions from an external memory, thereby performing subroutine programs involving fewer branches (including jump instructions) representing the alteration of execution sequence of successive instruction addresses.
There are known instruction cache memories and instruction prefetch buffers embodying conventional techniques for accelerating the speed of consecutive instruction execution in a data processor or the like. Such acceleration techniques take advantage of localities of data to be referenced in the temporal and spatial domains.
As an example, Japanese Published Unexamined Patent Application No. Hei 6 (1994)-243036 (U.S. Pat. No. 5,511,178) discloses a technique concerning a loop lock, which points out to the locality of fetched instructions. According to the disclosed technique, a sequence of instructions in the loop is retained in a cache memory until the program control exits from the loop.
Japanese Published Unexamined Patent Application No. Hei 4(1992)-62637 discloses a microprocessor including instruction queues (instruction prefetch buffers) that may store fetched loop instructions in an FIFO (first-in first-out) buffer in order to improve the execution speed.
SUMMARY OF THE INVENTION
Techniques such as those mentioned above may be effective in processes using many loop instructions since the loop instructions are held in a cache memory or an instruction prefetch buffer for accelerating the execution of sequential instructions. In processes including few loop instructions but sequential execution of almost linear and consecutive addresses, however, the conventional techniques may not be as effective even with some measures taken to prevent any loop instructions from being purged from the buffer or memory. In such cases, the inventors of the present invention have found that even the use of a regular instruction cache memory would have practically no significance.
More specifically, the inventors have studied the execution of subroutine programs such as those for protocol handling or system control processing in a cellular phone system. The protocol processing or system control processing by subroutine programs can be a complicated process, and may become large, storing every necessary processing programs in an internal ROM of a data processor may not be a practical solution. On the other hand, the access speed of external memory is slower than the speed of data processing in a data processor. The discrepancy of speed may be compensated for by use of an instruction cache memory in the data processor. However, the above protocol handling or system control processing frequently uses sequential execution of instructions having their addresses arranged in substantially linear and consecutive, and few loop instructions are included. As a result, not much advantageous effect may be expected from the introduction of a cache memory arrangement.
Under such circumstances, the inventors have decided to exclude the cache memory and utilize instead an instruction prefetch arrangement that is relatively simple in structure. In that case, there is no need for a structure to prohibit the overtaking of any loop instruction given the fact that the processing of interest mostly involves sequential execution of instructions having their addresses arranged in substantially linear and consecutive manner with few loop instructions included. From the standpoint of cost-performance, it was found that the correspondence between prefetched instructions and their addresses needed to be ensured in an appreciably simpler manner when compared with a cache memory address tag control feature or a counter-based read/write pointer control feature.
The inventors have further studied on the instruction prefetching and discovered that, when using a fixed-length burst transfer feature, any invalid instructions were also prefetched if a branch by a branching instruction is encountered, thereby overheads would be resulted in.
The inventors have also found that, when the instruction prefetching was performed by a branch to be executed or a conventional instruction fetch request in combination with lower plural bits, the execution of program would be suspended until instruction fetch from the external memory in the following instruction prefetch would be completed in tha case where all prefetched instruction are executed.
When studying deeply the access to the external memory, instruction prefetch is effective for capturing instruction codes (instructions fetch). However, the external memory will be accessed when capturing data described as operands (data fetch), and we have found that the execution of program would be suspended until all data would be fetched from the external memory.
The inventors have studied a countermeasure by refining the scheme of instruction prefetch with regard to those problems discovered when prefetching instructions. In those circumstances, the correspondence between the instruction prefetched and the address of that instruction should be more simplified than the control feature using address tag of the cache memory or the control mechanism for read-write pointers, from the standpoint of cost-performance.
It is therefore an object of the present invention to provide a data processor of a relatively simple structure, capable of prefetching instructions from the outside in order to improve the efficiency of instruction execution.
It is another object of the present invention to provide a data processing system having an instruction prefetch facility of a relatively simple structure in a data processor, so as to accelerate the processing, whereby sequential execution of instructions of linear or consecutive addresses with few loop instructions are fetched from an external memory and executed.
It is a further object of the present invention to provide a data processing system that executes subroutine programs including few branch processes requiring modification of the order in the execution sequence of successive instruction addresses, thereby offering efficient data processing at relatively lower costs.
Major features of the present invention disclosed herein will now be overviewed herein below.
A data processor in accordance with the present invention comprises an instruction executing means which may fetch instructions and decode thus fetched instructions to execute thus fetched and decoded instructions; and a bus controller which may control access to an external bus in accordance with commands from the instruction executing means. The bus controller may include a plurality of instruction buffers, a flag intrinsic to each of the instruction buffers, and a buffer control circuit. The buffer control circuit may allocate to each of the instruction buffers one of intrinsic values that a plurality of lower bits in each instruction address may have; the circuit may prefetch instructions into the instruction buffers corresponding to the order of instruction addresses, each of which are expressed by the lower plural bits and are next to the address of a fetched instruction of interest; and validate the flag of any instruction buffer when an instruction is prefetched into that buffer while making the flag of any instruction buffer invalid in response to output of a prefetched instruction from that buffer.
With the above structure, prefetching instructions into the instruction buffers need only to be done when any one of the values each expressed by the lower plural bits in an instruction address has reached a predetermined value. Illustratively, in order to simplify measures of instruction prefetch control, when an instruction having a starting offset address expressed by the lower plural bits is fetched, some instructions may be prefetched into the instruction buffers corresponding to the addresses in the range from the one next to the starting offset address to the fin
Kiuchi Atsushi
Matsui Shigezumi
Murakami Yasuyuki
Nishiyama Kunihiko
Takitsune Yuichi
Kim Kenneth S.
Miles & Stockbridge P.C.
LandOfFree
Data processer and data processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processer and data processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processer and data processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3088935