Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
2000-12-27
2004-08-31
An, Meng-Al T. (Department: 2126)
Electrical computers and digital processing systems: virtual mac
Task management or control
C718S107000, C718S108000
Reexamination Certificate
active
06785887
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of computer system operation control, and in particular, to hardware multi-threading where non-duplicated shared resources, such as special purpose registers, are used by multiple threads.
2. Background Information
The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices, and computer systems may be found in many different settings. Computer systems typically include a combination of hardware (e.g., semiconductors, circuit boards, central processing unit (CPU), etc.) and software (e.g., computer programs). As advances in semiconductor processing and computer architecture push the performance of the computer hardware higher, more sophisticated computer software has evolved to take advantage of the higher performance of the hardware, resulting in computer systems today that are much more powerful that just a few years ago.
Computer systems typically include operating system software that control the basic function of the computer, and one or more software applications that run under the control of the operating system to perform desired tasks. For example, a typical IBM Personal Computer may run the OS/2 operating system, and under the control of the OS/2 operating system, a user may execute an application program, such as a word processor. As the capabilities of computer systems have increased, the software applications designed for high performance computer systems have become extremely powerful.
Many modern computers support “multi-tasking” in which two or more programs are run at the same time. An operating system controls the alternating between the programs, and a switch between the programs or between the operating system and one of the programs is called a “context switch.” Additionally, multi-tasking can be performed in a single program, and is typically referred to as “multi-threading.” A technique to improve the efficiency of hardware within the central processing unit (CPU), or simply the “processor,” is to divide a processing task into independently executable sequences of instructions called threads. This technique is related to breaking a larger task into smaller tasks for independent execution by different processors in a multiprocessor environment, except here the threads are to be executed by the same processor. When a CPU then, for any of a number of reasons, cannot continue the processing or execution of one of these threads, the CPU switches to and executes another thread.
Multiple actions can be processed concurrently using multi-threading. However, some resources may be shared by the threads and conflicts may result. For example, most modern computers include at least a first level and typically a second level cache memory system for storing frequently accessed data and instructions. With the use of multi-threading, multiple program threads are sharing the cache memory, and thus the data or instructions for one thread may overwrite those for another, increasing the probability of cache misses. The cost of a cache miss in the number of wasted processor cycles is increasing, due to the processor speed increasing at a higher rate than the memory access speeds. Thus, ironically, more processors cycles are required for memory accesses, rather than less, as speeds increase. Accordingly, memory accesses are becoming a limited factor on processor execution speed.
A technique for limiting the effect of slow memory accesses is a thread switch. A discussion of the effect of multi-threading on cache memory systems is set forth in the article “Evaluation of Multi-Threaded Uniprocessors for Commercial Application Environments” by R. Eickemeyer et al. of IBM, May 22-24, 1996, 23rd Annual International Symposium on Computer Architecture. The IBM article shows the beneficial effect of a thread switch in a multi-threaded processor upon a level 2 cache miss. The article points out that the use of separate registers for each thread and instruction dispatch buffers for each thread will affect the efficiency. The article assumes a non-blocking level 2 cache, meaning that the level 2 cache can continue to access for a first thread and it can also process a cache request for a second thread at the same time, if necessary. The IBM article points out that there exist fine-grain multi-threading processors which interleave different threads on a cycle-by-cycle basis. Coarse-grain multi-threading interleaves the instructions of different threads on some long-latency event(s). As pointed out in the IBM article, switching in the Tera supercomputer, which switches every cycle, is done in round-robin fashion. The Alewife project is cited as handling thread switching in software using a fast trap.
Therefore, modern microprocessors implement multi-threading to tolerate high latency events, like cache misses. In such implementations, the processor will have multiple (two or more) concurrent threads of execution. It should be noted here that the term “multithreading” as defined in the computer architecture community is not the same as the software use of the term, which means one task subdivided into multiple related threads. In the computer architecture definition, the threads may be unrelated, i.e., independent. Therefore, the term “hardware multithreading” is often used to distinguish the two uses of the term “multithreading”. Also, as used herein in describing the invention, the term “threads” refers to hardware threads and is not to be confused with software threads.
Multi-threaded computer systems are computers with operating systems that allow a machine's resources, for example, central processing unit (CPU), input/output interface, memory, and peripherals, to be used by multiple instruction streams (threads) in parallel. In a multi-threaded computer environment, the operating system may allocate CPU processing among competing threads in a round robin fashion enabling parallel processing of instruction streams. When instruction streams are executing independent processes, multi-threaded environments are an efficient means to maximize use of CPU resources. However, in many cases instruction streams will have interdependencies created by references to certain types of variables in a computer program. Also, with multiple threads being processed in parallel, competition and conflict among the threads can occur.
U.S. Pat. No. 6,061,710 relates in general to a method for and apparatus of a computer data processing system; and in particular, to a multithreaded processor and method embodied in the hardware of the processor, in the presence of branch instructions.
There are two basic forms of multithreading. A traditional form is to keep N threads, or states, in the processor and interleave the threads on a cycle-by-cycle basis. The other form of multithreading is to interleave the threads on some long-latency event, such as a cache miss.
U.S. Pat. No. 5,933,627 relates to microprocessors which execute multi-threaded programs, and in particular to the handling of blocked (waiting required) memory accesses in such programs, and describes a method and apparatus for switching between threads of a program in response to a long-latency event. In one embodiment, the long-latency events are load or store operations which trigger a thread switch if there is a miss in the level 2 cache. In addition to providing separate groups of registers for multiple threads, a group of program address registers pointing to different threads are provided. A switching mechanism switches between the program address registers in response to the long-latency events.
Traditional forms of multithreading involve replicating the processor registers for each thread. For instance, for a processor implementing the architecture sold under the trade name PowerPC™ to perform multithreading, the processor must maintain N states to run N threads. Accordingly, the following resources are replicated N times: gen
Armstrong William Joseph
Nayar Naresh
Vossen Kenneth Charles
An Meng-Al T.
Cao Diem
International Business Machines - Corporation
Lynt Christopher H.
Payne Leslie J.
LandOfFree
Technique for using shared resources on a multi-threaded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for using shared resources on a multi-threaded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for using shared resources on a multi-threaded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301313