Method and system for efficient context swapping

[0001] The invention relates in general to methods and systems for efficient context switching in a processor, and more particularly, to methods and systems for minimizing the overhead associated with context switching utilizing direct memory access.

[0002] With the advent of the computer age, electronic systems have become a staple of modern life, and some may even deem them a necessity. Part and parcel with this spread of technology comes an ever greater drive for more functionality from these electronic systems. To accommodate this desire for increased functionality, these systems may employ high performance processors.

[0003] These high performance processors, in turn, are increasingly adding complex features to increase their performance. At the advent of the computer age operating systems were designed to run a single program sequentially. Thus, a single program would execute on a processor, after the conclusion of this program another program could be executed. Uniprogramming of this type eventually became stifling as users desired the ability to perform multiple tasks simultaneously. To circumvent the limitations of uniprogramming, tweaks such as memory-resident programs which could be invoked asynchronously were added to certain operating systems. These tweaks were somewhat problematic, however, as they introduced a wide variety of difficult bugs into the various programs, as most of these uniprogrammed operating systems lacked a significant amount of memory protection.

[0004] To alleviate these problems, and allow multiple processes to be active simultaneously, multiprogramming operating systems were designed. These multiprogramming operating systems allow multiple programs to share a single processor. In fact, in most cases this sharing is accomplished so seamlessly that it appears to a user that these multiple programs are executing simultaneously.

[0005] These multiprogrammed operating systems are based upon a fundamental concept that a point in the execution of a program is comprised at least partially of a state of a processor. This state, collectively known as the context, may comprise things such as the values of general purpose registers, the stack pointer, the floating point registers, any local store, memory mapped I/O registers, DMA context, etc. Consequently, by saving the state associated with a given instant of a program on a processor, the state can be restored at a later time and the execution of the program resumed. In the interim another program may be executed on the processor.

[0006] The ability to implement a multiprogrammed operating system is not without its detriments, however. In order to save the context from, and restore the context to, the processor the context itself must be stored for this intervening time span. In many cases this context is stored to the system stack in system memory, meaning, that every time the context of the processor is placed on the stack from the processor, or retrieved from the stack to be restored to the processor, the system memory must be accessed through the system bus. Accessing and utilizing the system bus to store context entails a large amount of time and overhead relative to the execution of programs on the processor.

[0007] Recently a new architecture has been developed for computer processors. Known as a multi-core architecture, this processor architecture is comprised of a core processor element and a number of auxiliary processor elements connected by an inter-chip bus. As may be imagined, in a processor architecture such as this many context switches may occur on a much more frequent basis then in a single processor chip, as context switching may occur with respect to not only the core processor element, but each of the auxiliary processor units as well.

[0008] As can be seen then, when accomplishing these context switches in conjunction with multiple auxiliary processor elements, multiple accesses to the system memory and the thus the system bus may be entailed. These repeated access to system memory through the system bus have a soporific effect on the system as a whole, as the time required to achieve these context switches is Brobdingnagian relative to the execution speed of the processor.

[0009] Thus, a need exists for efficient methods of context switching which substantially reduce the overhead of saving the context from, and restoring a context to, a processing element.

[0010] Systems and methods for efficiently switching context between processing elements are disclosed. These systems and methods may transfer the context of a processing element to a storage location. Using the DMA controller of a target processing element, the contents of this storage location may be transferred to another storage location associated with the target processing element. The context may then be restored from this storage location to the proper locations in the target processing element, and the target processing element may then begin processing utilizing this transferred context.

[0011] In one embodiment, a context is transferred from a storage location to another storage location using Direct Memory Access (DMA). The context can then be restored from this second storage location into a target processing element and the target processing element may begin processing using this context.

[0012] In some embodiments, the context may be transferred from a processing element to the storage location using DMA.

[0013] In other embodiments, a context maybe transferred from a storage location to an intermediary storage location using DMA. This context can then be transferred from the intermediary storage location to another storage location, also using DMA. The context can then be restored from this storage location into a target processing element and the target processing element may begin processing using this context.

[0014] Embodiments of the present invention may help to minimize the overhead associated with context switching between, among or within processor elements by allowing contexts to be transferred, at least in part, using DMA or dedicated hardware. Thus, a processing element may only have to be stopped for a relatively short period of time when performing a context swap.

[0015] Additionally, embodiments of the present invention offer the advantage that when used with certain multi-core processors they reduce the time taken to transfer a context between processors or memory locations by allowing an on-chip bus to be utilized, at least in part, for the transfer of these contexts.

[0016] These, and other, aspects of the invention will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings. The following description, while indicating various embodiments of the invention and numerous specific details thereof, is given by way of illustration and not of limitation. Many substitutions, modifications, additions or rearrangements may be made within the scope of the invention, and the invention includes all such substitutions, modifications, additions or rearrangements.

[0023] The invention and the various features and advantageous details thereof are explained more fully with reference to the nonlimiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well known starting materials, processing techniques, components and equipment are omitted so as not to unnecessarily obscure the invention in detail. Skilled artisans should understand, however, that the detailed description and the specific examples, while disclosing preferred embodiments of the invention, are given by way of illustration only and not by way of limitation. Various substitutions, modifications, additions or rearrangements within the scope of the underlying inventive concept(s) will become apparent to those skilled in the art after reading this disclosure.

[0024] Reference is now made in detail to the exemplary embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts (elements).

[0025] A few terms are defined or clarified to aid in an understanding of the terms as used throughout the specification. The term “processor element” is intended to mean any software, hardware or combination thereof which supports the execution of instructions.

[0026] Before describing embodiments of the present invention it may be useful to describe an exemplary architecture for a multi-core microprocessor which may be helpful in describing the aforementioned embodiments of the present invention. It will be apparent that though embodiments of the present invention may be particularly advantageous when utilized with embodiments of multi-core microprocessors, and thus embodiments of the present invention may be described in conjunction with exemplary embodiments of a multi-core microprocessor, embodiments of the present invention may also be used advantageously with single core microprocessors or in any other setting in which the transfer of the context of a processing element may be desired.

[0027] Turning to FIG. 1, a block diagram for one such exemplary embodiment of a multi-core microprocessor is depicted. Multi-core microprocessor 100 comprises core processor element 120, Input/Output (I/O) controllers 130, memory controllers 140, and synergistic processor elements (SPE) 110, all linked to one another via element interconnect bus (EIB) 102. Memory controllers 140 may be used to access system memory (not shown).

[0028] In one particular embodiment, core processor element 120 may be a 64-bit processor according to the IBM “Power Architecture” with a 32-KB first-level instruction and data caches and a 512-KB second-level cache. During operation of multi-core processor 100, core processor element 120 may run an operating system and some applications, however, certain parts of the operating system or certain applications, either in part or in whole, may be offloaded to SPEs 110 for execution. Each SPE 110 may comprise a self-contained vector processor capable of acting as an independent processor.

[0029] Moving to FIG. 2, a block diagram of one embodiment of an architecture of the core of an SPE 110 is depicted. Core 200 of SPE 110 comprises a set of general purpose registers 210, context buffer 230, context restore controller 240, direct memory access (DMA) logic 250, which may include a memory management unit and a memory mapped I/O register among other logic, and local store 260. Context buffer 230 may, in some embodiments, be dedicated memory on core 200, in other embodiments context buffer 230 may be a portion of local store 260 while in still other embodiments context buffer 230 may not reside on core 200 of SPE 110. In one embodiment, SPC context buffer 230 is mapped on the address space of system 100 such that context buffer 230 can be seen as part of the address range by DMA devices, and may be operable to store multiple contexts in a queue.

[0030] Context restore controller 240 may be operable to restore a context into an SPE 110 and may have three signal lines: SPE stop 242 which may be asserted when the SPC core 200 has stopped executing a thread or process, for example because of a timing interrupt or an exception, and deasserted when the SPU is executing a thread or process; DMA finish 244 which may be asserted when a DMA operation has completed and deasserted when a DMA operation is taking place, and an event signal 246 which may be asserted by software running on the core processor 120 or any SPE 110 when a software application wishes to force SPE 110 to undergo a context switch. Context restore controller 240 may be programmable, and may be programmed with this functionality, or other functionality, by an operating system executing on multi-core processor 100.

[0031] SPE 110 is capable of asynchronous DMA transfers between local store 260 and system memory (not shown) and between local stores on SPEs 110 using DMA logic 250 coupled to EIB 102. Such DMA transfers may be initiated from instructions executing on core processor element 120 or an SPE 110. DMA transfers can be programmed with instructions on SPE 110 that insert DMA commands in a queue of commands associated with DMA logic 250 or by inserting commands in the DMA queue from another processor element 110, 120 in the system by using store or write commands. For programming convenience, and to allow local-store to local-store DMA transactions, local-store 260 may be mapped into the memory map of core processor 120.

[0032] Allowing such asynchronous transfers offers the advantages of parallel computation and transfer of data and/or instructions. These advantages may be utilized to allow a context to be transferred between or among SPEs 110 or between core processor 120 and an SPE 110, while the SPE(s) 110 involved continue to process data. Allowing contexts to be transferred in parallel with processing may help alleviate some of the overhead associated with such context switches.

[0033] Attention is now directed to systems and methods for efficiently switching context between processing elements. These systems and methods may transfer the context of a processing element to a storage location. Using the DMA controller of a target processing element, the contents of this storage location may be transferred to another storage location associated with the target processing element. The context may then be restored from this storage location to the proper locations in the target processing element, and the target processing element may then begin processing utilizing this transferred context.

[0034] FIG. 3 depicts a block diagram of the operation of one embodiment of the systems and methods of the present invention. The context 302 of an SPE 110 comprises the values of various resources utilized by an SPE 110 during execution of a process. These resources may include the value 310 of general purpose registers 210, values 330 associated with direct memory access (DMA) logic 250, which may include values associated with the memory management unit and values 340 associated with a memory mapped I/O register among other logic, values 360 of local store 260 and values 370 associated with one or more SPU channels. It will be apparent that context 302 may encompass a greater or fewer number of the resources of SPE 110 depending on the particular embodiment of the present invention implemented.

[0035] At some point it may be desirable to change the process being executed by an SPE 110 by performing a context swap on the SPE 110. In order to accomplish this, context 302 of the currently executing process may need to be saved so that context 302 may be transferred and restored (either back into the same SPE 110 or into another SPE 110) at a later time.

[0036] To preserve context 302, context 302 may be transferred into SPC context area 380. SPC context area 380 may be an area in the system memory map such that SPC context area 380 appears as a sequential address range from the point of view of DMA logic 250. This particular range of addresses may be associated with SPE 110 such that only context 302 of that SPE 110 may be written to SPC context area 380 and each SPE 110 has its own particular SPC context area 380. SPC context area 380 may alternatively be an area of local store 260.

[0037] No matter the location of SPC context area 380, context 302 of SPE 110 may be transferred to SPC context area 380. The transfer of context 302 of SPE 110 to SPC context area 380 may be initiated by software running on either the core processor element 120 or on an SPE 110. Additionally, this transfer may be initiated at regular intervals, such that at these regular intervals the SPC context area 380 is overwritten with the then current context 302 of the SPE 110. Whether initiated at regular intervals, or on an ad hoc basis by software on SPE 110 or remote from SPE 110, context 302 may be transferred to SPC context area 380 through the use of DMA logic 250 if SPC context area 380 resides in the system's memory map. In one embodiment, initiation of the transfer of context 302 to SPC context area 380 is done through the use of a DMA command issued to DMA logic 250 which is a write command indicating that DMA logic 250 should write context 302 to the address(es) of SPC context area 380. The transfer of context 302 to SPC context area 380 may also be accomplished using memory mapped I/O.

[0038] At some point after transferring context 302, DMA logic 250 on a target SPE 110 (which may be the same SPE 110 from which context 302 was originally gleaned or a different SPE 110) may receive a command to transfer context 302 from SPC context area 380 to SPC context buffer 230 on the target SPE 110. This DMA transfer from SPC context area 380 to SPC context buffer 230 on the target SPE 110 may be initiated by software running on core processor element 120 or on any SPE 110 and may comprise a DMA write command with SPC context area 380 as the source and SPC context buffer 230, or an area of SPC context buffer 230, as the destination. The contents of SPC context area 380 are then transferred to SPC context buffer 230 on the target SPE 110 utilizing DMA logic 250 on target SPE 110. Subsequent to, or before, the completion of the context transfer, context restore controller 240 may detect a condition which triggers a context restore. In cases where such a condition is detected before the completion of the context transfer, context restore controller 240 may have to wait to restore context 302 to SPE 110 until the transfer of context 302 is completed.

[0039] In one embodiment, upon completion of the transfer of context 302 to SPC context buffer 230 from SPC context area 380, DMA logic 250 may assert DMA finish signal 244 coupled to context restore controller 240 on the target SPE 110. Upon assertion of either SPU stop signal 242 or event signal 246 (each of which may have been asserted before the assertion of DMA finish signal or which may subsequently be asserted) context restore controller 240 may copy or restore the values of context 302 resident in SPC context buffer 230 to their corresponding locations associated with the various resources utilized by an SPE 110 during execution of a process. In one particular embodiment, as SPC context buffer 230 may be a queue of contexts, when resorting a context 302 from context buffer 230 context restore controller 240 may copy or restore the values of the context 302 at the top of the queue of contexts in context restore buffer 230. As mentioned above, these values may include the values 310 of general purpose registers 210, values 330 associated with direct memory access (DMA) logic 250, which may include values associated with the memory management unit and values 340 associated with a memory mapped I/O register among other logic, values 360 of local store 260 and values 370 associated with one or more SPU channels.

[0040] After restoring context 302 to SPE 110, context restore controller may start SPE 110 such that SPE 110 may begin processing using context 302. In this manner, a context may be transferred from an SPE 110 to a storage location using DMA, transferred from this storage location to the same or a different SPE 110 using DMA, and restored such that an SPE 110 may begin processing using the context.

[0041] Occasionally, when transferring context 302 from an SPE 110 to SPC context area 380 it may be determined that SPC context buffer 230 of the target SPE 110 contains one or more contexts which have not yet been restored into the target SPE 110 (context buffer 230 is full). This status of SPC context buffer 230 may be kept either in hardware or software. For example, a portion of an operating system responsible for scheduling may have a table with one or more bits associated with each SPC context buffer 230 with the status of the bits depending on the status of the data in SPC context buffer 380. Alternatively, one or more bits in a register of SPE 110 may be associated with SPC context buffer 230 of the SPE 110, with the status of the bits depending on the status of the data in SPC context buffer 230. Thus, by referencing the status of SPC context buffer 230 an initiator can determine if the SPC context buffer 230 associated with the SPE 110 to which a transfer is to be initiated is full.

[0042] In cases where the initiator determines that SPC context buffer 230 associated with an SPE 110 is full the context of the SPE 110 may be transferred to another storage location. FIG. 4 depicts a block diagram of the operation of one embodiment of transferring a context to a memory range. In this embodiment, 302 may be transferred into a storage area comprising range of memory addresses 410 of system memory.

[0043] The transfer of context 302 of SPE 110 to memory range 410 may be initiated by software in either the core processor element 120 or in the SPE 110. The initiator may determine that SPC context buffer 230 associated with SPE 110 is full and determine a range of memory addresses 410. The initiator may then issue a command to DMA logic 250 on SPE 110 which is a write command indicating that DMA logic 250 should transfer context 302 to range of memory addresses 410. DMA logic 250 may then transfer context 302 to the memory addressed by range of memory addresses 410.

[0044] At some later point it may be desirable to restore this context saved in the memory addressed by range of memory addresses 410 into an SPE 110. FIG. 5 depicts a block diagram of the operation of one embodiment of transferring context 302 from memory range 410 to an SPE 110. DMA logic 250 of target SPE 110 (which may be the same SPE 110 from which context 302 was originally gleaned or a different SPE 110) may receive a command to transfer context 302 from memory associated with range of memory addresses 410 to SPC context buffer 230 on target SPE 110. This DMA transfer from range of memory addresses 410 to SPC context buffer 230 on the target SPE 110 may be initiated by software in either the core processor element 120 or in any SPE 110 and may comprise a DMA write command with range of memory addresses 410 as the source and SPC context buffer 230 as the destination. The contents of range of memory addresses 410 are then transferred to SPC context buffer 230 on the target SPE 110 utilizing DMA logic 250 on target SPE 110. Context restore controller 240 may then detect a condition which triggers a context restore, restore the context 302 from the SPC context buffer and start SPE 110 so that SPE 110 may begin processing using context 302.

[0045] In the foregoing specification, the invention has been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of invention.

[0046] Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any component(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature or component of any or all the claims.