Virtual shadow registers and virtual register windows

Details Virtual shadow registers and virtual register windows Virtual shadow registers and virtual register windows

2002-10-28

2004-09-28

Eng, David Y. (Department: 2155)

Electrical computers and digital processing systems: processing

Processing control

Branching

Reexamination Certificate

active

06799269

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of microprocessor architectures. More particularly, the invention relates to reducing overhead associated with register set saving and restoring as is required when invoking functions, exception handlers, and interrupt service routines. The invention further relates to register shadowing and windowing strategies to reduce function calling and task switching times in multi-issue processors, especially superscalar RISC processors and very long instruction word (VLIW) digital signal processors (DSPs).
2. Description of the Prior Art
Studies show that register saving and restoring in response to function calls and returns accounts for between 5% and 40% of the data memory traffic in executing programs written in a high level programming language. Also, the registers must be saved whenever a program switches tasks. In a UNIX operating system, for example, this accounts for approximately 20% of the task switching overhead. In more streamlined real-time operating systems as are common with embedded processors and DSPs, register saving and restoring accounts for a much higher percentage of the task switching time. Even interrupt service routines that do not require a full task switch still require at least some of the registers to be saved and restored. This adds significant overhead in many cases.
Register shadowing and windowing techniques have been introduced in an effort to reduce delays associated with register set storing and loading. Prior art processor architectures that incorporate shadow registers or register windows are discussed in detail in John L. Hennessy and David A. Patterson, “Computer Architecture: A Quantitative Approach,” Morgan Kaufmann Publishers, Inc., San Francisco, Calif., 1991. These concepts are by now employed on some high performance RISC processors and DSPs. For example, the Analog Devices ADSP21xx series of DSPs use a shadow register bank. Sun Microsystem's SPARC processors use windowed register banks. These register systems allow the processors to switch register sets in a single cycle.
Register shadowing is a technique whereby a primary register set is shadowed by a mirror image register set. When a register set switch command is issued, the machine context can be switched from the primary register set to the shadow register set. Shadow register sets are useful for fast switching between tasks or between a primary program and an interrupting program. For example, in a DSP, a supervisory task may run in the background while the main signal processing algorithm runs in the foreground. This technique can be supported for example, in the Analog Devices ADSP21xx series of DSPs. In the ADSP21xx processors, there is only one shadow register set. Hence, single-cycle context switching can only occur between one primary task and one secondary task. Also, in the case of the ADSP21xx, the address registers are not saved upon a shadow register switch. Hence in applications, a long sequence of commands is required to save and restore the address registers, requiring a significant time penalty.
As can be seen from the foregoing discussion, a problem with shadow register systems is their inability to provide single-cycle context switching to more than one task. In theory, if N shadow register sets are added, then single-cycle task switching between N+1 tasks is possible. The problem, however is that if more than N+1 tasks need to be supported, the single-cycle task switching will only be possible between a subset of the total number of tasks. Also, a significant amount of silicon area is needed for each added shadow register set. Finally, the software that manages the tasks becomes difficult and less efficient because it has to manage a first type of task that has its context stored in a shadow register set, and a second type of task that has its context stored in memory. Whenever a task of the second type is invoked, context switch oriented register save and restore operations are required. For these reasons, shadow register sets have not gained widespread popularity.
Shadow register sets can optionally be used for register save and restore operations related to function calling and returning. For example, if the processor has a single shadow register set, a base level function can make a call to a first level function, and can perform a register bank switch so that the first level routine can save the registers and then restore them in single cycles. The problem is that this capability only exists for a single level of function calling. If the first level function were to call a second level function, both the primary and the shadow register sets would be occupied, requiring multiple cycles for all register save and restore operations related to subsequent function calls. Again, adding more shadow register sets extends the number of levels of function calls that can be supported with single-cycle register store and restore operations, but only at the price of a significant amount of silicon area. Moreover, the software becomes complicated due to the need to keep track of the current level of function nesting. For these reasons, shadow registers find limited use in function calling.
Register window systems are an extension of the shadow register concept and are designed to accelerate function calling. In a register window system, a group of shadow register sets is typically arranged as a circular buffer. When a function call is made, the active register set advances from one set to the next in the circular buffer. When the buffer wraps, an overflow is said to occur. Upon an overflow, a sequence of memory transfers is needed to save the first register file in the circular buffer arrangement to insure it does not get overwritten. As verified by the analysis of execution patterns of large numbers of benchmark programs, by making the circular buffer deep enough, usually on the order of twelve to sixteen register sets, the overhead associated with register save and restore operations can be made to be negligible.
Prior art register window systems have many drawbacks and are thus not used in most modern high performance processor designs. First of all, a twelve-level to sixteen-level deep register window system requires an excessive amount of silicon area. Secondly, as the total number of registers in the circular buffer of register files increases, the number of register address lines, and hence the amount of time needed for register address decoding increases. Longer register address access times lead to slower system clocks and thus slower overall processors. Thirdly, as the number of register sets in the windowing system increases, the number of registers that must be saved when a task switch occurs increases proportionally. This adds a significant overhead to task switching and adds interrupt latency. Adding multiple copies of shadowed register window systems to provide single-cycle task switching would require an enormous amount of silicon area and would have the same limitations relating to shadow registers as discussed above.
The problems become more severe in DSPs. For example, in machines such as the SPARC, the floating point registers are not included in a register window switch. Rather, floating point registers must be loaded and saved under program control. This would not be acceptable on a floating point DSP. The reason the floating point registers are not added to the register window on the SPARC is because, unlike on floating point DSPs, the floating point registers are not used as widely. DSPs also often contain the ALU core registers as well as address registers and possibly other types of auxiliary registers that would need to be added to the register windowing system. Modern load-store VLIW DSPs have multiple register sets that would need to be windowed multiple times to create an effective register window system. Hence, it can be seen that register windows become prohibitively expensive to implement with most DSP architectures.
In U.S. Pat. No. 3,

Affiliated with

Also associated with

Rating

Virtual shadow registers and virtual register windows does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Virtual shadow registers and virtual register windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual shadow registers and virtual register windows will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3266222