Electrical computers and digital processing systems: processing – Instruction fetching – Prefetching
Reexamination Certificate
2001-12-20
2003-05-13
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: processing
Instruction fetching
Prefetching
C711S137000, C711S204000, C711S213000, C712S203000, C712S205000, C712S237000
Reexamination Certificate
active
06564313
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to microprocessor design, and more particularly directed to systems and methods for increasing microprocessor speed through efficient instruction prefetching.
2. Description of the Related Art
The following descriptions and examples are not admitted to be prior art by virtue of their inclusion within this section.
Over the years, the use of microprocessors has become increasingly widespread in a variety of applications. Today, microprocessors may be found not only in computers, but may also be found in devices such as VCR's, microwave ovens, and automobiles. In some applications, such as microwave ovens, low cost may be the driving factor in the design of the microprocessor. On the other hand, other applications may demand the highest performance obtainable. For example, modem telecommunication systems may require very high speed processing of multiple signals representing voice, video, data, etc. Processing of these signals, which have been densely combined to maximize the use of available communication channels, may be rather complex and time consuming. With an increase in consumer demand for wireless communication devices, such real time signal processing requires not only high performance but also demands low cost. To meet the demands of emerging technologies, designers must constantly strive to increase microprocessor performance while maximizing efficiency and minimizing cost.
With respect to performance, greater overall microprocessor speed may be achieved by improving the speed of various related and unrelated microprocessor circuits and operations. As stated above, microprocessor speed may be extremely important in a variety of applications. As such, designers have evolved a number of speed-enhancing techniques and architectural features. Among these techniques and features may be the instruction pipeline, the use of cache memory, and the concept of prefetching.
A pipeline consists of a sequence of stages through which instructions pass as they are executed. In a typical microprocessor, each instruction comprises an operator and one or more operands. Thus, execution of an instruction is actually a process requiring a plurality of steps. In a pipelined microprocessor, partial processing of an instruction may be performed at each stage of the pipeline. Likewise, partial processing may be performed concurrently on multiple instructions in all stages of the pipeline. In this manner, instructions advance through the pipeline in assembly line fashion to emerge from the pipeline at a rate of one instruction every clock cycle.
The advantage of the pipeline may lie in performing each of the steps required to execute an instruction in such a simultaneous manner. However, to operate efficiently, a pipeline must remain full. If the flow of instructions into and out of the pipeline is disrupted, clock cycles may be wasted while the instructions within the pipeline may be prevented from proceeding to the next processing step. Prior to execution, the instructions may typically be stored in a memory device, such that instructions may be fetched into the pipeline by the microprocessor. However, access times for such memory devices may generally be much slower than the operating speed of the microprocessor. As such, instruction flow through the pipeline may be impeded by the length of time required to fetch instructions from memory (i.e. memory latency).
An obvious approach to the above problem may seem to simply use faster memory devices. Unfortunately, although faster memory devices may be available, they are typically more costly and may consume more power than conventional memory. In view of these disadvantages, the use of high-speed memory devices throughout the entire memory hierarchy may be infeasible. Thus, a more practical alternative for high performance microprocessors may be the use of cache memory.
Cache memory is a secondary memory resource that may be used in addition to the main memory, and generally consists of a limited amount of very high-speed memory. Since cache memory may be small relative to the main memory, cost and power consumption of the cache may not be significant factors in some applications. However, factors such as cost and circuit dimension limitations may place constraints on cache size in other applications.
Cache may memory improve microprocessor performance whenever the majority of instructions required by the microprocessor may be concentrated in a particular region of memory. The principle underlying the use of cache may be, more often than not, the microprocessor may fetch instructions from the same area of memory. Such a principle may be due to the sequential nature in which instructions may be stored in memory. In other words, most instructions may be executed by the microprocessor in the sequence in which they may be encountered in memory.
Assuming the majority of instructions required by the microprocessor may be found in a given area of memory, the entire area may be copied (e.g., in a block transfer) to the cache. In this manner, the microprocessor may fetch the instructions as needed from the cache rather than from the main memory. Since cache memory may be faster than main memory, the pipeline may be able to operate at full speed. Thus, cache memory may provide a dramatic improvement in average pipeline throughput. Such an improvement may be achieved by providing the pipeline with faster access to instructions than would be possible by directly accessing the instructions from conventional memory. As long as the instructions are reasonably localized, the use of a cache may significantly improve microprocessor performance.
To further improve access time to information, one or more levels of cache memory may also be included within the system. Typically, the lowest level of cache (i.e. the first to be accessed) may be smaller and faster than the one or more levels above the lowest level in the memory hierarchy. Also, the number of caches in a given memory hierarchy may vary. When an instruction is executed, the address associated with the instruction may typically be directed to the lowest level of cache. The fastest possible operation may be called a “cache hit.” A cache hit may occur when the information corresponding to the instruction address may be stored in the level of cache indicated by the address. If a cache hit occurs, the addressed information may be retrieved from the cache without having to access a higher level of memory in the memory hierarchy. The higher ordered memory may be slower to access than the lower ordered cache memory.
Conversely, a “cache miss” may occur when an instruction required by the microprocessor is not present in the level of cache indicated by the instruction address. In response to a cache miss, the next higher ordered memory structure may be presented with the instruction address. The next higher ordered memory structure may be another cache, such that another hit or miss may occur. If misses occur at each level of cache, “starvation” of the microprocessor may occur. During starvation, the microprocessor may discard the contents of the cache. Subsequently, the necessary information may be fetched as quickly as possible from main memory and may be placed into cache. Obviously, this may be a source of overhead, and if it becomes necessary to empty and refill the cache frequently, system performance may begin to approach that of a microprocessor without cache.
Another advancement in microprocessor technology relates to the concept of prefetching information, where such information may either be data or instructions. A block of information may be prefetched from a storage device, which may be at a relatively high order in the memory hierarchy, and written to a storage device lower in the memory hierarchy, such as a lower order cache. Prefetching may allow the time spent to retrieve such information to occur concurrently with other actions of the microprocessor. In this manner, when the microprocessor requests the prefetched
Conley Rose & Tayon
LSI Logic Corporation
Song Jasmine
LandOfFree
System and method for efficient instruction prefetching... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficient instruction prefetching..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficient instruction prefetching... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004474