CN1842770A - A holistic mechanism for suspending and releasing threads of computation during execution in a processor - Google Patents

Abstract

A processing mechanism in a processor capable of supporting and executing a plurality of program threads, comprising a parameter for scheduling a program thread and an instruction in the program thread, the instruction having access to the parameter. When the parameter equals the first value, and when a program thread issues the instruction, the instruction reschedules the program thread in accordance with one or more conditions encoded in the parameter.

Description

An overall mechanism for suspending and releasing computing threads during execution in a processor Related applications cross-referenced with the present invention

This application claims priority from the following applications:

(1) U.S. Provisional Application No. 60/499,180, dated August 28, 2003, titled "Multithreading Application Specific Extension" (attorney number P3865, inventor Kevin Kissey Kissell (Kevin D. Kissell, Express Mail No. EV 315085819 US),

(2) U.S. Provisional Application No. 60/502,358, dated September 12, 2003, titled "Multithreading Application Specific Extension to a Processor Architecture on a Processor Architecture" (Proxy ID 0188.02US, Inventor Kevin D. Kissell, Express Mail No. ER456368993US), and

(3) U.S. Provisional Application No. 60/502,359, dated September 12, 2003, titled "Multithreading Application Specific Extension to a Processor Architecture on a Processor Architecture" (Proxy No. 0188.03US, inventor Kevin D. Kissell (Kevin D. Kissell), Express Mail No. ER456369013US), the entire content of each application mentioned therein is the reference material that the present invention refers to.

This invention is also related to pending U.S. Nonprovisional Application No. (not yet received), filed October 10, 2003, entitled "Mechanisms for Determining Quality of Service for Programs Executing on Multithreaded Processors" for Assuring Quality of Service for Programs Executing on a Multithreaded Processor)” (Attorney No. 3865.01, Inventor Kevin D. Kissell, Express Mail No. EL988990749 US), the entire content of the application mentioned here is Reference materials referred to in the present invention.

technical field

The present invention is in the field of digital processors (eg, microprocessors, digital signal processors, microcontrollers, etc.), and more particularly, relates to apparatus and methods for managing the execution of multiple threads within a single processor.

technical background

In the field of digital computing, the history of computing power shows continuous progress on all fronts. Continuing advances are taking place all the time, such as processor device density and wire interconnection technology, which can be used to improve computing speed, fault tolerance, use higher speed clock signals, or many other improvements. Another area of research that could improve overall computing power is parallel processing, which involves more than just using multiple separate processors to perform parallel operations.

The concept of parallel processing involves distributing tasks across separate processors, but also includes scenarios in which multiple programs are executed simultaneously on a single processor. This scheme is generally referred to as multithreading.

Next, the concept of multi-threading will be introduced: as the operating frequency of the processor gradually increases, it becomes more and more difficult to hide the inherent delay (latency) in the operation of the computer system. An advanced processor that misses 1 percent of its instructions in its cache in a particular application, if it has 50 cycles of latency to off-chip RAM, can cause stalls about 50 percent of the time. The performance of the processor can be improved if an instruction belonging to a different application can be executed while the processor is stalled due to a missing cache instruction, and some or all of the memory-related delay can also be effectively eliminated. For example, FIG. 1A shows a single instruction stream 101 stalled due to a cache miss. Machines that support this instruction can only execute a single thread or task at a time. In contrast, FIG. 1B shows that instruction stream 102 can be executed while instruction stream 101 is stalled. In this case, the supporting machine can support two threads at the same time, and thus use the resources owned by the machine more efficiently.

More generally, each individual computer instruction has a specific syntax such that different types of instructions require different resources to perform desired operations. Integer loads do not fully utilize the logic or registers of the entire floating-point unit, and any operation other than register shifts requires the use of load/store unit resources. No single instruction uses all the resources of the processor, and when more pipeline stages and parallel functional units are added in order to pursue a higher performance design, it will further reduce the average consumption of the processor used by all instructions ratio of resources.

A large part of the development of multithreading stems from the fact that if a sequential program cannot efficiently use all of the processor's resources, the processor should be able to allocate some of these resources among the multiple threads belonging to the program's execution. to allocate. This approach does not necessarily result in any particular program being executed faster. In fact, some multithreading schemes substantially degrade the performance of single-threaded program execution, yet allow a collection of parallel instruction streams to execute in less time. within and/or use fewer processors. This concept is illustrated in Figures 2A and 2B, which show a single-threaded processor 210 and a dual-threaded processor 250, respectively. Processor 210 supports a single thread 212 , shown using a load/store unit 214 . If a miss occurs while accessing cache 216, processor 210 stalls (as described with respect to FIG. 1A) until the missing data is retrieved. During this process, the multiplier/divider unit 218 is always idle and not actively used. However, processor 250 supports two threads; namely 212 and 262 . Therefore, if the thread 212 is stalled, the processor 250 can still execute the thread 262 and the multiplier/divider unit 218 concurrently, thereby more efficiently utilizing all resources (as described with respect to FIG. 1B ).

Having multiple threads on a single processor has the benefit of better multitasking capabilities. However, bundling multiple program threads on key events can reduce event reaction time, and thread-level parallel processing can in principle be fully exploited within a single application.

Various multithreading approaches have been proposed. One of these is interleaved multithreading, a time-division multiplexing (TDM) scheme that switches from one thread to another for each issued instruction. This scheme has a certain degree of "fairness" in scheduling, but in order to statically allocate multiple issue slots to multiple threads, it usually limits the performance of a single program thread. The dynamic interleaving method can improve this problem, but it is more complicated to realize this method.

Another multithreading scheme is blocked multithreading, which continuously issues consecutive instructions from a single program thread until a specific blocking event occurs, such as a cache miss or reset, for example Say, causing the thread to be suspended while another thread is activated. Because the frequency of changing threads by block interleaved multithreading is relatively small, its implementation may be relatively simple. On the other hand, blocking actions are less "fair" in the process of scheduling threads. A single thread can monopolize the entire processor for a long time, if it is very lucky to find all the data it needs in cache. A hybrid scheduling scheme that combines block-interleaved multithreading and instruction-interleaved multithreading is often used and researched.

There is still another form of multithreading called simultaneous multithreading (simultaneousmultithreading), which is a solution implemented on a superscalar processor. In synchronous multithreading, multiple instructions from different threads can be issued simultaneously. For example, a superscalar reduced instruction set computer (RISC) issues a total of two instructions per cycle, and a synchronously multithreaded superscalar pipeline issues a total of two instructions per cycle from either of two threads. Cycles that are tied to or stalled by a single program thread can cause the processor to be underutilized, so in SMT these cycles can be filled by issuing instructions from another thread.

Synchronous multithreading thus becomes a very useful technique to address and restore lost efficiencies in superscalar pipelines. But it is also arguably considered the most complex method used by multi-threaded systems, because activating more than one thread in a cycle will make the implementation of memory access protection devices more complicated, etc. Another point worth noting is that for a certain workload, the more perfect the pipeline of central processing unit (CPU) operations, the more it will reduce the potential efficiency obtained by its multi-threaded implementation.

Multithreading is very much related to multiprocessing in nature. In fact, it can generally be considered that there is only one difference: that multiprocessors only share memory and/or wires, while multithreaded processors share instruction fetches and wires in addition to memory and/or wires. Issue logic, and possibly other processor resources. In a single multithreaded processor, threads compete with each other for issue slots and other resources, limiting parallel processing capabilities. Certain multithreaded programs and architectural models assume that new threads are assigned to different processors so that the program can be processed effectively in parallel.

At the time this application was filed, there should have been many multi-threaded solutions to solve many different problems in the current field. One of them is the improvement scheme of real-time thread. In general, real-time multimedia algorithms are usually executed on dedicated processors/digital signal processors (DSPs) to ensure quality of service (QoS) and response time, and do not include mixing and sharing threads in multi-threaded solutions, Because real-time software cannot be easily obtained to ensure that the software can be executed in a timely manner.

In this regard, it is very clear that there must be a scheme and mechanism that allows one or more real-time threads or virtual processors to be able to guarantee a specific proportion of instruction issue slots in a multi-threaded processor at a specific interval between instructions, so that Computing bandwidth and response time can be clearly defined. If such a mechanism can be used, threads with strict QoS requirements can be included in the multi-thread mix. In addition, real-time threads in such systems (such as DSP-related threads) can be more or less prevented from changing the execution time due to moving important resources when encountering interrupts. This technology allows the use of a RISC processor and core with DSP enhancements in special cases, instead of the separate RISC and DSP cores typically used in consumer multimedia applications.

Another problem with multithreading solutions in the state of the art at the time of filing of this application is spawning and destroying active threads in the processor. To support relatively fine-grained multithreading, it is desirable to spawn and destroy parallel threads of program execution with the minimum possible overhead and, at least in general, without interfering with essential operating system functions. In this regard, what is clearly needed are instructions such as FORK (thread creation) and JOIN (thread termination). Another problem that exists in multithreaded processors is that the scheduling principle makes a thread keep running until it is blocked by some other resource, while a thread that is not blocked by any resource still needs to cause the processor to switch to other threads. So in this regard, it can be clearly known that there is still a need for PAUSE or YIELD instructions.

Contents of the invention

A basic object of the present invention is to provide a robust system for fine-grained multithreading in which threads can be spawned and destroyed with minimal overhead. According to this purpose, in a preferred embodiment of the present invention, in a processor capable of supporting and executing multiple program threads, a processing mechanism is provided, which includes: a parameter for scheduling a program thread; and an instruction set in the program thread that can access the parameter. When the parameter is equal to the first value, the instruction reschedules the program thread based on one or more conditions encoded in the parameter. In a preferred embodiment of the mechanism, the parameters are stored in a data storage device. And in another preferred embodiment, when the parameter is equal to a second value, wherein the second value is not equal to the first value, the instruction releases the program thread. In some embodiments, the second value is zero.

In some embodiments, when the parameter is equal to the second value, wherein the second value is not equal to the first value, the instruction unconditionally reschedules the program thread. In addition, in some embodiments, the second value is an odd value. In some other preferred embodiments, the second value is negative 1.

In some preferred embodiments, one of the one or more conditions is associated with a program thread that relinquishes execution opportunities to other threads until a condition is satisfied. Additionally, in some embodiments, the one condition is encoded in a bit vector or bit field in the parameter. Also, in some embodiments, where the program thread is rescheduled, execution of the program thread continues after the instruction in the thread. Also, in some other preferred embodiments, when the parameter is equal to a third value, wherein the third value is not equal to the first value and the second value, the instruction reschedules the program thread unconditionally.

In some preferred embodiments of the mechanism, one of the one or more conditions is a hardware interrupt. Also, in some embodiments, one of the one or more conditions is a software interrupt. Also, in many embodiments, when the program thread is rescheduled, execution of the program thread continues at the location in the thread following the instruction.

According to another aspect of the present invention, in a processor capable of supporting and executing multi-program threads, a method for rescheduling execution by a thread or releasing the thread itself is provided, which includes: (a) issuing an instruction, It can access a portion of records in a data storage device that encodes one or more parameters related to one or more conditions that determine whether the thread will be rescheduled; and (b) comply with the conditions, according to One or more parameters in this section record reschedules or releases this thread. In a preferred embodiment, the record is placed in a general purpose register (GPR). Additionally, in a preferred embodiment, one of these parameters is associated with the thread being released rather than being rescheduled. In some preferred embodiments, the value of the one parameter associated with the released thread is zero.

In some embodiments implementing the method, one of the parameters is associated with the thread being requeued for scheduling. In some embodiments, this parameter is any odd value. In some embodiments, this parameter is a negative one's two's complement value. In some embodiments, one of these parameters is associated with an embodiment that relinquishes execution opportunities to other threads until a particular condition is met. Additionally, in other embodiments, the one condition is encoded in a bit vector or one or more bit fields in the record.

In many embodiments implementing the method, in the event that the thread issues the instruction and is rescheduled, when the one or more conditions are met, execution of the thread in the thread instruction stream issues the instruction After the position continues. In some embodiments, one of these parameters relates to threads that are released rather than rescheduled, and another of these parameters relates to threads that are requeued for scheduling. In other embodiments, one of these parameters is related to the thread being released rather than rescheduled, and another of these parameters is related to relinquishing execution opportunities to other threads until a specific condition is met. thread dependent. In other embodiments, one of these parameters relates to threads being requeued for rescheduling, and another of these parameters relates to threads yielding execution to other threads until a specified condition is met relevant. Additionally, in other embodiments, one of these parameters is associated with the thread being released rather than rescheduled, and another of these parameters is associated with the thread that has been requeued for scheduling, and these parameters Yet another parameter in is related to threads that relinquish execution opportunities to other threads until a specific condition is met.

According to another aspect of the present invention, there is provided a digital processor capable of supporting and executing multiple software entities, comprising a portion of records in a data storage device encoding one or more conditions associated with one or more conditions. Multiple parameters, the one or more conditions determine whether a thread will be rescheduled when it yields execution opportunities to other threads.

In some embodiments of the processor, the portion of the record is placed in a general purpose register (GPR). In some other preferred embodiments, one of these parameters is associated with threads being released rather than rescheduled. In some other preferred embodiments, the value of the parameter related to the released thread is zero.

In some other embodiments of the processor, one of the parameters is associated with the thread being requeued for scheduling. In some embodiments, the one parameter is any odd value. In other embodiments, the parameter is a negative one's two's complement value. In other embodiments, one of these parameters is associated with a thread that relinquishes execution opportunities to other threads until a specified condition is met. Additionally, in some cases, the one parameter may be encoded in a bit vector or one or more bit fields in the record.

In some other embodiments of the processor, one of the parameters is associated with the thread that was released rather than rescheduled, and another of the parameters is associated with the thread that was requeued for scheduling. In other embodiments, one of these parameters relates to threads that are released rather than rescheduled, and another of these parameters relates to threads that yield execution to other threads until a specified condition is met relevant. In other embodiments, one of the parameters is associated with threads being requeued for rescheduling, and another of these parameters is associated with threads that yield execution opportunities to other threads until a specified condition is met .

In other embodiments, one of these parameters relates to threads that are released rather than rescheduled, and another of the parameters relates to threads that are requeued for scheduling, and the rescheduling of these parameters Another parameter relates to threads that yield execution opportunities to other threads until a certain condition is met.

According to another aspect of the present invention, there is provided a processing system capable of supporting and executing multiple program threads, comprising: a digital processor; a portion of records in a data storage device encoding and determining whether a thread will one or more parameters associated with the one or more conditions to be rescheduled; and an instruction set including an instruction to reschedule and release the thread. When the thread issues the instruction, the instruction accesses the one or more parameters in the record, and the system follows the one or more conditions to reschedule and Release the thread that issued the instruction.

In some preferred embodiments of the processing system, the record is placed in a general purpose register (GPR). In some other preferred embodiments, one of these parameters is associated with threads being released rather than rescheduled. In some embodiments, the value of the one parameter associated with the thread being released is zero. In some other embodiments, one of these parameters is associated with a thread that is requeued for scheduling. In some embodiments, the parameter used for rescheduling is any odd value. In some other embodiments, the parameter used for rescheduling is a negative 1 two's complement value.

In some embodiments of the system, one of these parameters is associated with threads that yield execution opportunities to other threads until a specified condition is met. Additionally, in some embodiments, the one parameter is encoded in a bit vector or one or more bit fields in the record. In many embodiments of the system, where a thread issues the instruction and is conditionally rescheduled, execution of the thread follows the instruction in the thread's instruction stream when the one or more conditions are met The location continues.

In some embodiments of the processing system, one of the parameters relates to threads that are released rather than rescheduled, and another of the parameters relates to threads that are requeued for scheduling. In other embodiments, one of the parameters relates to threads being freed rather than rescheduled, and another of these parameters relates to threads yielding execution to other threads until a specified condition is met relevant.

In other embodiments, one of the parameters relates to threads being requeued for rescheduling, and another of the parameters relates to yielding execution opportunities to other threads until a specified condition is met. In addition, in some other embodiments, one of the parameters is related to the thread that is released rather than rescheduled, and another parameter is related to the thread that is requeued for scheduling, and among these parameters Yet another parameter of is related to threads that relinquish execution opportunities to other threads until a specific condition is met.

In addition, according to still another aspect of the present invention, a digital storage medium is provided, on which instructions from an instruction set are written, for executing each software thread among a plurality of software threads on a digital processor, the an instruction set comprising an instruction that causes a thread issuing the instruction to abort execution and access a parameter in a portion of a record in a data storage device, wherein a condition for release or rescheduling is associated with the parameter, And follow this condition, perform release or reschedule according to this parameter in this partial record.

In some embodiments of the medium, the record is placed in a general purpose register (GPR). In some other embodiments of the medium, one of the parameters relates to a thread that is released rather than rescheduled. In some embodiments, the parameter associated with the released thread has a value of zero. In some other embodiments of the medium, one of the parameters relates to a thread that is requeued for scheduling. In some embodiments, the one parameter is any odd value. In other embodiments, the one parameter is a negative one's two's complement value.

In other embodiments of the medium, one of the parameters is associated with a thread that yields execution to other threads until a specified condition is met. In other embodiments, the parameter is encoded in a bit vector or one or more bit fields in the record. In other embodiments, one of the parameters relates to threads that are released rather than rescheduled, and another of the parameters relates to threads that are requeued for scheduling. In other embodiments, one of the parameters relates to threads being freed rather than rescheduled, and another of these parameters relates to threads yielding execution to other threads until a specified condition is met relevant.

In some embodiments of the mechanism, one of the parameters relates to threads being requeued for rescheduling, and another of these parameters relates to threads yielding execution opportunities to other threads until a specified condition is met relevant. Additionally, in some embodiments of the digital storage medium, one of the parameters relates to a thread that was released rather than rescheduled, and another of the parameters relates to a thread that was requeued for scheduling, and Yet another of these parameters relates to threads that relinquish execution opportunities to other threads until a specific condition is met.

In some embodiments of the mechanism, the instruction is a YIELD instruction. Also, in some embodiments of the mechanism, the partial record includes a bit vector. Additionally, in some other embodiments of the mechanism, the partial record includes one or more multi-bit fields.

In some embodiments of the method, the instruction is a YIELD instruction. Also, in some embodiments of the processing system, the instruction is a YIELD instruction.

In an embodiment of the digital storage medium, the command is a YIELD command.

According to another aspect of the present invention, there is provided a computer data signal contained in a transmission medium, including computer readable program code, the program code describes a processor capable of supporting and executing multiple program threads, and includes a For the mechanism of releasing and rescheduling a thread, the program code includes: a first program code segment, which is used to describe a part of records in a data storage device, and this part of the records encodes and determines whether a thread will be rescheduled One or more parameters related to one or more conditions; and a second program code segment for describing an instruction capable of accessing the one or more parameters in the record, wherein, when the thread issues the instruction, The instruction accesses the one or more values in the record and, subject to the one or more conditions, reschedules or releases the thread based on the one or more values.

According to another aspect of the present invention, in a processor capable of supporting multiple program threads, a method is provided, comprising: executing an instruction that accesses a parameter related to thread scheduling, wherein the instruction is included in a In the program thread; when the parameter is equal to the first value, release the program thread according to the instruction. In some embodiments of the method, the first value is zero. In some other embodiments of the method, the method further includes a step of: suspending execution of the program thread according to the instruction when the parameter is equal to a second value, wherein the second value is not equal to the first value. In some embodiments of the method, the second value indicates that a condition required to execute the program thread is not satisfied.

In some other embodiments of the method, the condition is encoded in the parameter in the form of a bit vector or value field. In some other embodiments, the program thread is rescheduled according to the instruction when the parameter is equal to a third value, wherein the third value is not equal to the first value and the second value. In some other embodiments, the third value is negative 1. In some other embodiments, the third value is an odd value.

According to another aspect of the present invention, in a processor capable of supporting multiple program threads, a method is provided, comprising: executing an instruction that accesses a parameter related to thread scheduling, wherein the instruction is included in a program In the thread; when the parameter is equal to the first value, the execution of the program thread is suspended according to the instruction. In some other embodiments of the method, the method further includes a step of rescheduling the program thread according to the instruction when the parameter is equal to a second value, wherein the second value is not equal to the first value.

According to another aspect of the present invention, in a processor capable of supporting multiple program threads, a method is provided, comprising: executing an instruction that accesses a parameter related to thread scheduling, wherein the instruction is included in a program In the thread; when the parameter is equal to the first value, reschedule the program thread according to the instruction. In some embodiments of the method, the method further includes a step of releasing the program thread according to the instruction when the parameter is equal to a second value, wherein the second value is not equal to the first value.

Embodiments of the present invention, described in more detail below, provide for the first time a truly robust system for fine-grained multithreading, minimizing the overhead of spawning and destroying threads.

Description of drawings

Figure 1A is a schematic diagram showing a situation where a single instruction stream stalls due to a cache miss;

FIG. 1B is a schematic diagram showing that an instruction flow can still be executed when the instruction flow shown in FIG. 1A is paused;

Figure 2A is a schematic diagram showing a single-threaded processor;

FIG. 2B is a schematic diagram showing a dual-thread processor 250;

FIG. 3 is a schematic diagram illustrating a processor supporting first and second VPEs according to an embodiment of the present invention;

Fig. 4 is a schematic diagram, has described in one embodiment of the present invention, a processor can support single VPE, and this VPE can further support three threads;

Figure 5 shows the format of a FORK instruction according to one embodiment of the present invention;

Figure 6 shows the format of a YIELD instruction according to one embodiment of the present invention;

Figure 7 is a table showing a sixteen-bit limit mask for GPR rs;

Figure 8 shows the format of an MFTR instruction according to an embodiment of the present invention;

Figure 9 is a table illustrating the fields of an MFTR instruction according to one embodiment of the present invention;

FIG. 10 shows the format of an MTTR instruction according to an embodiment of the present invention;

Figure 11 is a table illustrating the u and sel bits of an MTTR instruction according to one embodiment of the present invention;

Figure 12 shows the format of an EMT instruction according to an embodiment of the present invention;

Figure 13 shows the format of a DMT instruction according to an embodiment of the present invention;

Figure 14 shows the format of an ECONF instruction according to an embodiment of the present invention;

Fig. 15 is a description table of a system coprocessor privileged resource according to an embodiment of the present invention;

Fig. 16 is according to an embodiment of the present invention, the architecture of a ThreadControl register;

Fig. 17 is according to one embodiment of the present invention, the explanatory form of each field in a ThreadControl register structure;

Fig. 18 is according to an embodiment of the present invention, the architecture of a ThreadStatus register;

Fig. 19 is according to one embodiment of the present invention, the explanatory form of each field in a ThreadStatus register structure;

Fig. 20 is according to an embodiment of the present invention, the architecture of a ThreadContext register;

Fig. 21 is according to an embodiment of the present invention, the architecture of a ThreadConfig register;

Fig. 22 is according to one embodiment of the present invention, the explanatory form of each field in a ThreadConfig register structure;

Fig. 23 is according to an embodiment of the present invention, the architecture of a ThreadSchedule register;

FIG. 24 is a structure of a VPESchedule register according to an embodiment of the present invention;

FIG. 25 is a structure of a Config4 register according to an embodiment of the present invention;

Fig. 26 is an explanation form of each field in a Config4 register architecture according to an embodiment of the present invention;

Figure 27 is a table that defines the exception code value of the Cause register required by the thread exception;

Figure 28 is a table that defines the ITC indicator;

Figure 29 is a table that defines each field in the Config3 register architecture;

Figure 30 is a table describing the VPE disable bits for each VPE context;

Figure 31 is a table describing the operation of ITC storage;

Figure 32 is a schematic diagram describing the operation of the YIELD function according to one embodiment of the present invention;

Figure 33 is a schematic diagram illustrating a computer operating system according to an embodiment of the present invention;

FIG. 34 is a schematic diagram illustrating the implementation of scheduling using VPEs in a processor and threads in a VPE according to an embodiment of the present invention.

Detailed ways

According to a preferred embodiment of the present invention, a processor architecture includes an instruction set, and the instruction set includes features, functions, and instructions capable of generating multi-threaded operations on a compatible processor. The present invention is not limited to any specific processor architecture and instruction set, but can be roughly classified into the well-known and referenced MIPS architecture, instruction set and processor technology (in a word, MIPS technology). And the embodiments described in detail in addition to the present invention can also be classified as MIPS technology. Additional information on MIPS technology, including the documents referenced below, is available from MIPS Technology, Inc. (located in Mountain View, California) and from its website at www.mips.com (the company's website).

References to "processor" and "digital processor" include any programmable device (for example, microprocessor, microcontroller, digital signal processor, central processing unit, processor core, etc. ), in terms of hardware (e.g., dedicated silicon chips, field-programmable gate arrays (FPGAs), etc.), in terms of software (e.g., hardware description languages, C language, C+ language, etc.), or any components thereof (or combination).

The terms "thread" and "program thread" are used synonymously herein.

Summary description

In an embodiment of the present invention, a "thread context" is a collection of processor states, which is used to describe the execution state of an instruction stream on a processor. Said state is usually reflected in the contents of processor registers. For example, in a processor compatible with the industry specification MIPS32 and/or MIPS64 instruction set architecture (MIPS processor), the thread context is composed of general purpose registers (GPRs), high and low (Hi/Lo) multiplication result registers, and program The counter (PC) function and some related privileged system control state registers. System control state is reserved in a portion of the MIPS processor commonly referred to as coprocessor zero (CP0), and a large portion is maintained by the system control registers and the Translation Lookaside Buffer (TLB) (if used TLB). In contrast, a "processor context" is a larger collection of processor state that includes at least one thread context. Referring again to the previously mentioned MIPS processor as an example, a processor context includes at least one thread context (as mentioned above), that is, CP0 and the necessary system state to describe the known MIPS32 and MIPS64 exclusive resources or privileged resource architectures (PRA). (Simply put, PRA is a set of environment and capability parameters related to the operation of an instruction set architecture. The PRA provides the mechanism necessary for the operating system to manage processor resources, such as virtual memory, high-speed caching, exception operations, and user contexts).

According to one embodiment of the present invention, multithreading application-specific extensions (Multithreading ASE) on an instruction set architecture and a PRA allow two different, but not mutually exclusive Multi-threaded performance. First, a single processor can have a certain number of processor contexts, each of which operates as an independent processing unit by sharing some of the processor's resources and supporting an instruction set architecture. These separate processing units are referred to herein as virtual processing units (VPEs). To software, a processor with N VPEs is seen as a symmetric multiprocessor (SMP) with N paths. This allows existing SMP-capable operating systems to manage sets of VPEs, that is, transparently share the processor's execution units.

FIG. 3 depicts the associated performance with a single processor 301 supporting a first VPE (VPE0 ), which contains a zeroth register state 302 and a zeroth system coprocessor state 304 . The processor 301 also supports a second VPE ( VPE1 ), which includes a first register state 306 and a first system coprocessor state 308 . VPE0 and VPE1 share these portions of processor 301 , including instruction fetch, decode, pipelined execution, and cache 310 . An SMP-compatible operating system 320 is executed on the processor 301 and supports VPE0 and VPE1. As shown in the figure, software process A 322 and process C 326 are executed on VPE0 and VPE1 respectively, as if they were executed on two different processors. Process B 324 is in a queue state, and may execute on either of VPE0 or VPE1.

A second capability allowed by multi-threaded ASE is that each processor or VPE can contain a certain number of thread contexts in addition to the single thread context required in the base architecture. Multi-threaded VPEs require special operating system support and provide a simple, fine-grained multi-threaded program model with its support, in which threads can be spawned and destroyed, so that the operating system will not be disturbed in general, and the system service thread Scheduling can be scheduled in response to external conditions (eg, events, etc.) without interruption delays.

FIG. 4 depicts this second capability and uses processor 401 to support a single VPE, which includes register states 402, 404 and 406 (supporting three threads 422) and system coprocessor state 408. The difference from Figure 3 is that in this example the three threads are in a single application address space and share CP0 resources (and hardware resources) on a single VPE. Also depicted is a dedicated multi-threaded operating system 420 . In this example, the multi-threaded VPE is processing a data packet from a broadband network 450, and the download of this data packet is distributed across an entire set of first-in-first-out buffers (FIFOs) 452 (in the input/output memory space of the multi-threaded VPE). Each FIFO in has a different address). The controlling application spawns as many threads as there are FIFOs used, and applies each thread in a tight loop reading the FIFOs.

A thread context can be in one of four states. It can be free, activated, halted or wired. An idle thread context has no valid content and cannot be scheduled to issue instructions. An active thread context can be scheduled according to enforced rules, fetching and issuing instructions from the program counter. A stopped thread context can have valid content, but cannot fetch and issue instructions. A thread context for a thread can be designated as a shadow register, that is, it is reserved exclusively for the exception handler, to avoid the overhead of storing and restoring the memory context in the exception handler. An idle thread context cannot be activated, stopped or connected. Only active thread contexts can be scheduled. Only idle thread contexts can be allocated to spawn new threads.

To allow fine-grained synchronization of co-threads, a memory space for inter-thread communication (ITC) is created in virtual memory with empty/full bit syntax to allow threads to load or store is blocked until data is produced or consumed by other threads.

Thread creation/destruction and synchronization features generally do not interfere with the operating system, but the resources they manipulate can be virtualized by the operating system. This allows multithreaded programs to execute with more virtual threads than there are thread contexts on a VPE, enabling thread migration to balance the load on multiprocessor systems.

Looking carefully at a certain point in the execution process, a thread is tied to a specific thread context on a specific VPE. The combined index of the VPE's thread context provides a unique identifier at that point in time. But context switching and migration can enable the execution of a single successive thread with a sequence of different thread indices, for example on a sequence of different VPEs.

Performs dynamic binding of thread contexts, TLB entries, and other resources to multiple VPEs on the same processor in a particular processor reset state. Each VPE inputs its reset vector as if it were an independent processor.

Multithreaded Execution and Exception Model

The multithreaded ASE does not impose any special implementation or scheduling model for the execution of parallel threads and VPEs. Scheduling can be round-robin, time-cut at any granularity, or simultaneous. However, none of the implementations allow a blocked thread to monopolize any shared processor resource, thus deadlocking the hardware operation.

In a MIPS processor, multiple threads execute on a single VPE, and all share the same system coprocessor (CP0), the same TLB and the same virtual address space. Each thread has an independent kernel/supervisor/user state for memory access and instruction decoding. When an exception occurs, all threads except the one executing the exception are stopped or suspended until the EXL and ERL bits of the status string are cleared. Or, in case of an EJTAG debug exception, exit the debug state. This status string is placed in the status register in CP0. Details on the EXL and ERL bits and EJTAG debug exceptions can be obtained from the following two publications, which are available from MIPS Technologies, Inc. and are hereby incorporated by reference in their entirety in each case: : MIPS32 ^TM Architecture for Programmers Volume III: The MIPS32 ^TM Privileged Resource Architecture, Rev. 2.00, MIPS Technologies, Inc. (2003) and MIPS64 ^TM Architecture for Programmers Volumn III: The MIPS64 ^TM Privileged Resource Architecture, Rev. 2.00, MIPS Technologies, Inc. (2003) .

Exception handlers for synchronous exceptions caused by executing an instruction stream, such as TLB misses and floating-point exceptions, are executed by the thread used to execute the instruction stream. When an unmasked asynchronous exception, such as an interrupt, is raised to a VPE, its implementation is relative to the thread that executed the exception handler.

Even when using the shadow register set to execute the exception handler, each exception is associated with a thread context. The associated thread context is the target of the RDPGPR and WRPGPR instructions executed by the exception handler. A detailed description of the RDPGPR and WRPGPR instructions (used to access shadow registers) can be obtained from the following two publications, available from MIPS Technologies, Inc., the entire contents of which are in each case incorporated herein by reference Documents: MIPS32 ^™ Architecture for Programmers Volumn III: The MIPS32 ^™ Instruction Set, Rev. 2.00, MIPS Technologies, Inc. (2003) and MIPS64 ^™ Architecture for Programmers Volumn III: The MIPS64 ^™ Instruction Set, Rev. 2.00, MIPS Technologies, Inc. (2003).

The multithreaded ASE contains two exception conditions. The first is the thread unacquired condition, where a thread allocation request cannot be satisfied. The second is a thread underflow condition, where the termination and release of a thread causes no threads to be allocated on a VPE. Both exception conditions are mapped to a new single-threaded exception. When this exception occurs, they can be distinguished according to the bit setting of the CP0 register.

instruction

In a preferred embodiment, the multithreaded ASE contains seven instructions. The FORK and YIELD instructions control thread allocation, release, and scheduling, and are available in all execution modes that are executed and enabled. The MFTR and MTTR instructions are system coprocessor (Cop0) instructions that can be used by privileged system software to manage thread state. A new EMT instruction and a new DMT instruction are privileged Cop0 instructions, which are used to enable and disable multi-threaded operation of a VPE. Finally, a new ECONF instruction is a privileged Cop0 instruction used to exit a specific processor configuration state and reinitialize the processor.

FORK - allocates and schedules a new thread

The FORK instruction can drive an idle thread context to be allocated and activated. Its format 500 is shown in FIG. 5 . The FORK instruction takes two operand values from a GPR (general purpose register) identified by fields 502(rs) and 504(rt). The content of GPR rs is the address used to start fetching and executing the new thread. The content of GPR rt is a value to pass to the new thread's GPR. The destination GPR is determined by the value of the ForkTarget field of the ThreadConfig register of CP0, which is illustrated in Figure 21 and described later. The kernel/supervisor/user state of the new thread is set in the thread processed by FORK. If there is no free thread context for the FORK instruction, a thread exception is raised for the FORK instruction.

YIELD - rescheduling and conditional release of a thread

The YIELD instruction causes the current thread to be rescheduled. Its format 600 is shown in FIG. 6, and the flowchart 3200 in FIG. 32 describes system operation according to one embodiment of the present invention to illustrate the function of the YIELD instruction.

The YIELD instruction takes a single operand value, for example, from the GPR specified in field 602(rs). A GPR is used in one preferred embodiment, but in other embodiments, the operand value may be stored in virtually any data storage device accessible by the system (e.g., non-GPR registers, memory, etc.) or obtain. In one embodiment, the content of GPR rs can be viewed as a descriptor describing the circumstances under which an emitted thread should be rescheduled. If the content of this GPR rs is zero (i.e. the value of the operand is zero), as shown in step 3202 of Figure 32, then this thread will not be rescheduled, but will be released as shown in step 3204 (i.e. , terminate or permanently stop further execution), and its associated thread context storage (that is, the above-mentioned register for saving state) becomes free, so that it can be issued by other threads for the next FORK instruction to allocate. If the least significant bit of the GPR rs is set (i.e., rs0=1), the thread is immediately rescheduled as shown in step 3206 of FIG. thread. In this embodiment, the contents of the GPR rs are treated as a 15-bit qualifier mask, as described in table 700 in FIG. 7 (ie, a bit vector for encoding various conditions).

Please refer to table 700, bits 15 to 10 of the register rs indicate the hardware interrupt signal provided to the processor, bits 9 to 8 indicate the software interrupt signal generated in the processor, and bits 7 to 6 indicate the most basic MIPS architecture The operations of the associated load (Load Linked) and conditional storage (Store Conditional) synchronization primitives, and bits 5 to 2 represent external non-interrupt signals provided to the processor.

If the content value of GPRrs is an even number (i.e., bit 0 is not set), and any other bit in the qualifier mask of GPRrs is set (step 3208), then the thread is suspended until At least one corresponding condition. If and when this happens, the thread is rescheduled (step 3210), and execution resumes from the instruction after YIELD. The enabling of this process is not affected by the CP0.Status.iMn interrupt mask bits, so there are a total of ten external conditions (e.g., event etc.) and the four software conditions encoded by bits 9 through 6 (as shown in Figure 7), are used in the current embodiment to respond to external signals to enable separate threads without requiring the processor to perform exception handling . In this particular example, there are six hardware interrupts and four non-interrupt signals, plus two software interrupts and two non-interrupt signals, and finally one signal dedicated to the rescheduling function (i.e. rs0), for a total of Corresponding to fifteen conditions. (The CP0.Status.iMn interrupt mask bit is a set of eight bits in the CP0 Status register that selectively masks the eight basic interrupt inputs of the MIPS processor. If one IM bit is set, the other The associated interrupt input will not cause a processor exception event.)

In the EIC's interrupt mode, bits IP2 to IP7 encode the interrupt with the highest priority, not just a vector with quadrature instructions. When the processor uses the interrupt mode of the EIC, the bits of GPR rs associated with bits IP2 to IP7 in a YIELD instruction can therefore no longer be used to re-enable a thread for a specific external event. In the interrupt mode of the EIC, only external event indicators associated with the system (eg, in this embodiment, bits 5 to 2 of GPR rs) can be used as qualifiers for YIELD. The interrupt modes and bits IP2 to IP7 of the EIC have been further described in the following publication, which was noted above and cited in its entirety: MIPS32 ^™ Architecture for Programmers Volume III: The MIPS32 ^™ PrivilegedResource Architecture, and MIPS64 ^™ Architecture for Programmers Volume III: The MIPS64 ^™ Privileged Resource Architecture.

If the result of executing YIELD is the release of the most recently allocated thread on the processor or VPE, then a thread exception is generated for the YIELD instruction, with an underflow indication in the ThreadStatus register of CP0 (as shown in Figure 18 and later on will be explained).

The foregoing embodiment uses the operand contained in the GPR rs of the YIELD instruction as a parameter for thread scheduling. In this example, this parameter is viewed as a 15-bit vector of orthogonal indications (see Figure 7, bits 1 and 15 are reserved, so only fifteen conditions are encoded in the preferred embodiment). This embodiment also treats this parameter as a specified value (ie, for determining whether a given thread should be released, see step 3202 of FIG. 32). However, the nature of such a parameter may be changed to suit various instruction embodiments. For example, instead of relying on the least significant bit (i.e., rs0) to determine whether a thread is immediately reschedulable, the value of the parameter itself (e.g., negative one {-1} in two's complement form) is used to determine whether a thread is Should not be immediately rescheduled (ie, requeued for scheduling).

In other embodiments of this instruction, such thread scheduling parameters can be viewed as fields containing one or more multi-bit values, so that a thread can determine that it will be associated with a large temporal namespace (e.g., 32-bit or larger) from a single event. In such an embodiment, at least the bits associated with the target event are accessible by the current YIELD instruction. Of course, more bit fields may be passed to the instruction (associated with more events) as desired for a particular embodiment.

In other embodiments of the YIELD instruction, a thread scheduling parameter accessed by the instruction may include a combination of the aforementioned bit vector and value field, or other specific application improvements and enhancements, (for example) to meet the needs of specific implementations. Alternative embodiments of the YIELD instruction can use any known method to access the parameters of a thread schedule as previously described, for example, from a GPR (as shown in Figure 6), from any other data storage device (including memory) and as an immediate value in the instruction itself.

MFTR - move from thread register

The MFTR instruction is a privileged (Cop0) instruction that allows an operating system to execute a thread to access a different thread context. Its format 800 is depicted in FIG. 8 .

The thread context to be accessed is determined by the value of the AlternateThread field of the ThreadControl register of CP0, which is shown in Figure 16 and described later. In the selected thread context, the register to be read is determined by the value of the rt operand register designated by field 802, and the u and sel bits in fields 804 and 806 of the MFTR instruction, respectively, and according to FIG. 9 Form 900 is shown for illustration. The resulting value is written to the destination register rd identified by field 808 .

MTTR - move to thread register

The MTTR instruction is the opposite of the MFTR instruction. It is a privileged Cop0 instruction that copies register values in the thread context of the current thread to registers in another thread context. Its format 1000 is shown in FIG. 10 .

The thread context to be accessed is determined by the value of the AlternateThread field of the ThreadControl register of CP0, which is shown in Figure 16 and described later. In the selected thread context, the register to be written is determined by the value in the rd operand register identified by field 1002, in conjunction with the u and sel bits provided in fields 1004 and 1006, respectively, of the MTTR instruction, and according to Table 1100 shown in Fig. 11 for interpretation (coded similarly to MFTR). The value in register rt identified by field 1008 is copied to the selected register.

EMT - enable multithreading

The EMT instruction is a privileged Cop0 instruction that enables parallel execution of multiple threads by setting the TE bit of the ThreadControl register of CP0, which is shown in FIG. 16 and described later. The format 1200 of this command is shown in FIG. 12 . The value of the ThreadControl register containing the TE (Thread Enabled) bit value before the EMT execution will be passed back to the register rt.

DMT - disable multithreading

The DMT instruction is a privileged Cop0 instruction, which disables parallel execution of multiple threads by clearing the TE bit of the ThreadControl register of CP0, which is shown in FIG. 16 and described later. The format 1300 of this command is shown in FIG. 13 .

Except for the thread that issued the DMT instruction, all threads are prohibited from further instruction fetching and execution. This is independent of any thread suspension state. The value of the ThreadControl register containing the TE (Thread Enabled) bit value before the DMT is executed will be returned to the register rt.

ECONF - Ends the configuration of the handler

The ECONF instruction is a privileged CopO instruction that notifies the end of VPE configuration and enables execution of multiple VPEs. The format 1400 of this command is shown in FIG. 14 .

When an ECONF instruction is executed, the VPC bit of the Config3 register (described later) is cleared, and the current value of the MVP bit of the register becomes read-only, and all VPEs of the processor, including the one that is executing ECNOF VPE, all generate a Reset exception.

Privileged Resource

Table 1500 of FIG. 15 lists privileged resources of the system coprocessor related to multi-threaded ASE. Unless otherwise specified, the registers described below are accessible (i.e., written to and read from) on both new and modified coprocessor zero (CP0) just like conventional zeroth The system control registers of coprocessors (ie, MIPS processors) are the same.

New Privileged Resources

(A) ThreadControl register (CP0 register number 7, selection number 1)

The ThreadControl register is in each VPE as part of the system coprocessor. Its structure 1600 is shown in FIG. 16 . The fields of the ThreadControl register can be set according to the table 1700 of FIG. 17 .

(B) ThreadStatus register (CP0 register number 12, selection number 4)

The ThreadStatus register exists per thread context. Each thread has a copy of its ThreadStatus, and privileged program code can access the ThreadStatus of other threads through the MFTR and MTTR instructions. Its structure 1800 is shown in FIG. 18 . The fields of the ThreadStatus register can be set according to the table 1900 of FIG. 19 .

Writing a 1 to the Halted bit of an active thread causes the active thread to stop fetching instructions and resets the internal restart program counter (PC) to the next issued instruction. Writing a 0 to the Halted bit of an active thread causes that thread to be scheduled to fetch and execute instructions from the internal restart program counter (PC) address. As long as either the Activated bit or the Halted bit of the unactivated thread is 1, the thread can avoid being allocated and activated by a FORK instruction.

(C) ThreadContext register (CP0 register number 4, selection number 1)

The ThreadContext register 2000 exists in each thread context, and its length is the same as the processor's GPR as shown in FIG. 20 . This is purely a software read/write register that can be used by the operating system as a pointer to thread-specific storage, such as an area where the thread context is kept.

(D) ThreadConfig register (CP0 register number 6, selection number 1)

The ThreadConfig register exists in each processor or VPE. Its structure 2100 is shown in FIG. 21 . The fields of the ThreadConfig register are defined in table 2200 of FIG. 22 .

The WiredThread field of the ThreadConfig register allows the set of thread contexts available on a VPE to be split between the set of shadow registers and parallel execution threads. If the index of the thread context is less than the value of the WireThread, the thread context can be obtained from the shadow register.

(E) ThreadSchedule register (CP0 register number 6, selection number 2)

The ThreadSchedule register is optional, but when implemented, is preferably implemented per thread. Its structure 2300 is shown in FIG. 23 .

The schedule vector (Schedule Vector) (as shown in the figure, its width is 32 bits in a preferred embodiment) is a description of the issue bandwidth required for scheduling related threads. In this embodiment, each bit represents 1/32 of the issue bandwidth of the processor or VPE, and the position of each bit represents a specific time slot in the 32 time slot scheduling loop.

If a bit is set in a thread's ThreadSchedule register, then the thread is guaranteed to get a corresponding issue slot for every 32 possible consecutive issues on the associated processor or VPE. Writing a 1 to a bit in the ThreadSchedule register will generate a thread exception when other threads on the same processor or VPE already have the same ThreadSchedule bit set. Although here, the preferred width of the ThreadSchedule register is 32 bits, it is contemplated that the width may vary (ie, increase or decrease) in other embodiments.

(F) VPESchedule register (CP0 register number 6, selection number 3)

The VPESchedule register is optional and preferably present in each VPE. It can only be written when the MVP bit of the Config3 register is set (refer to Figure 29). Its format 2400 is shown in FIG. 24 .

A scheduling vector (as shown, which is 32 bits wide in a preferred embodiment) is a description of the required outgoing bandwidth for scheduling the associated VPE. In this embodiment, each bit represents 1/32 of the total issue bandwidth of a multi-VPE processor, and the position of each bit represents a specific time slot in the 32 time slot scheduling loop.

If a bit in the VPE's VPESchedule register is set, then the thread is guaranteed a corresponding issue slot for every 32 possible consecutive issues on the associated processor. Writing a 1 to a bit of the VPESchedule register of a VPE will generate a thread exception when other VPEs already have the same VPESchedule bit set.

According to the current default thread scheduling principle of the processor (for example, round robin, etc.), as long as the issue period is not specially scheduled by any thread, it can still be freely allocated to any executable VPE/thread.

The VPESchedule register and the ThreadSchedule register create a structure for issuing bandwidth allocations. The setting of the VPESchedule register specifies the bandwidth for the VPE, which is a certain percentage of the total available bandwidth on a processor or core, and the ThreadSchedule register specifies the bandwidth for threads, which is available in a VPE containing threads A certain percentage of the total bandwidth.

Although here, the preferred width of the VPESchedule register is 32 bits, it is contemplated that the width may vary (ie, increase or decrease) in other embodiments.

(G) Config4 register (CP0 register number 16, selection number 4)

Register Config4 exists in each processor. It contains the necessary configuration information for dynamic multi-VPE processor configuration. If the processor is not in the VPE configuration state (ie, the VMC bit of the Config3 register is set), the values of all fields except the M (Continuous) field become implementation-dependent and their results are unpredictable. Its structure 2500 is depicted in FIG. 25 . The fields of the Config4 register are defined as shown in table 2600 of FIG. 26 . In some implementations or embodiments, the VMC bit of the Config3 register may be a reserved/unassigned bit.

Modifications to the Existing Privileged Resource Architecture

The multithreaded ASE has made changes to some units of the current MIPS32 and MIPS64PRA.

(A) Status register

The CU bit in the Status register has some additional meaning for multithreaded configurations. The act of setting the CU bit also requires binding a coprocessor context to the thread associated with the CU bit. If a coprocessor context is available, it is bound to the thread so that instructions issued by the thread can be delivered to the coprocessor, and the CU bit retains the 1 written to this bit. If no coprocessor context is available, the CU bit will read back 0. Writing a 0 to set the CU bit causes any associated coprocessors to be released.

(B) Cause register

As shown in Figure 27, thread exceptions need to have a new exception code value of the Cause register.

(C) EntryLo register

As shown in FIG. 28, a previously reserved cache flag becomes an ITC indicator.

(D) Config3 register

As shown in table 2900 of FIG. 29 , a field of a new Config3 register is defined to indicate whether the multi-thread ASE and multiple thread contexts are available.

(E)Ebase

As shown in Figure 30, a previously reserved bit 30 of the Ebase register becomes a VPE disable bit in each VPE context.

(F)SRSCtl

The previously preset HSS field is now a function of the WiredThread field of the ThreadConfig register.

Thread allocation and initialization without using the FORK instruction

In a preferred embodiment, the process of an operating system "manually" generating a thread is as follows:

1. Execute a DMT to stop the execution of other threads or possibly the execution of the FORK instruction.

2. Identify an available thread context by setting consecutive values in the AlternateThread field of the ThreadControl register and reading the ThreadStatus register with the MFTR instruction. An idle thread will not have the Halted or Activated bits set in its ThreadStatus register.

3. Set the Halted bit of the ThreadStatus register of the selected thread to prevent it from being configured by other threads.

4. Execute an EMT instruction to re-enable multithreading.

5. Use the MTTR instruction with its u field set to 1 to copy any required GPRs to the selected thread context.

6. Use the MTTR instruction with the u and sel fields set to 0 and the rt field set to 14 (EPC) to write the required start execution address into the thread's internal restart address register.

7. Use the MTTR instruction to write 0 and 1 to the Halted and Activated bits of the selected ThreadStatus register, respectively.

This newly allocated thread can then be scheduled. If EXL or ERL is set during this process, since they implicitly prohibit multi-threaded execution, the steps of executing DMT, setting the Halted bit of the new thread and executing EMT can be omitted.

Termination and release of threads that do not use the YIELD instruction

In a preferred embodiment of the present invention, the process that an operating system is used to terminate the current thread is as follows:

1. If the operating system does not support thread exceptions about thread underflow status, then use the MFTR instruction to scan the ThreadStatus register setting to check that there is another runnable thread on the processor, otherwise, report to the program Signal an error.

2. Write the value of any important GPR register to memory.

3. In the Status/ThreadStatus register, set the kernel mode (Kernel mode).

4. When the current thread remains in a privileged state, clear EXL/ERL to allow other threads to be scheduled.

5. Use a standard MTC0 instruction to write a value of 0 to the Halted and Activated bits of the ThreadStatus register.

The normal procedure is for a thread to terminate itself in this way. In a privileged mode, a thread can also use the MTTR instruction to terminate another thread, but there will be additional problems. At this time, the operating system needs to decide which thread context should be released, and at what point the thread's computing state is stable.

Inter-Thread Communication Storage

Stores for inter-thread communication (ITC) is an optional feature that can replace the associative load/conditional store synchronization method for fine-grained multithreading. This ITC store is invisible in the instruction set architecture because it operates through load and store actions, but it is visible in the privileged resource architecture and requires efficient microarchitectural support.

Referring to virtual memory pages, which contain TLB entries marked as ITC storage, can be classified as a storage with certain attributes. Each page is mapped to a set of 1-128 64-bit storage locations, each of which has an Empty/Full bit associated with it, and can be accessed in one of four ways using standard load and store instructions to access the storage location. The access mode is encoded in the least significant (and untranslated) bits of the generated virtual address, as shown in table 3100 of FIG. 31 .

Therefore, each storage location can be described by the structure of C language:

struct{

unit64 ef_sync_location;

unit64 force_ef_location;

unit64 bypass_location;

unit64 ef_state;

}ITC_location;

where all four locations refer to the same 64 bits of underlying storage space. The stored reference may have a less than 64-bit access type (eg, LW, LH, LB) while each access implements the same Empty/Full protocol.

The Empty and Full bits are not the same, so uncoupled multi-entry data buffers, such as FIFOs, can be mapped into the ITC memory space.

The ITC's storage can be saved and restored by copying {bypass_location, ef_state} pairs to and from general storage. Strictly speaking, only the least significant bits of ef_state need to be manipulated while the 64-bit bypass_location must be preserved. In a multi-entry data buffer, each location must be read up to the Empty bit to read the contents of the buffer by copying.

The number of locations per 4K page and the number of ITC pages per VPE are parameters that can be set by the VPE or the processor.

The "physical address space" stored by ITC can be global, spanning all VPEs and processors in a multiprocessor system, so that a thread can be synchronized from a VPE where the thread is executing to a location in a different VPE . The global ITC storage address can be obtained from the CPUNum field of each VPE's EBase register. The 10 bits of this CPUNum correspond to the 10 significant bits of the ITC storage address. Generally, a processor or core designed for uniprocessor applications does not need to output a physical interface to the ITC storage, and can use it as a resource inside the processor.

Multiple VPE processors

A core or processor can implement multiple VPEs that share resources, such as shared functional units. Each VPE sees its own implementation of MIPS32 or MIPS64 instructions and privileged resource structures. Each can see its own register file or thread context array, and also see its own CP0 system coprocessor and its own TLB state. To software on a SMP multiprocessor with 2-CPU cache coherence, two VPEs on the same processor are indistinguishable.

Each VPE on a processor can see a different value in the CPUNum field of the Ebase register on CP0.

Processor architectural resources, such as thread contexts, TLB storage, and coprocessors, can be bound to the VPE in a hardware-based configuration, or can be dynamically configured in a processor that supports the necessary configuration capabilities.

Reset and virtual processor configuration

To be backward compatible with MIPS32 and MIPS64PRA, a configurable multi-threaded/multi-VPE processor must have the full default thread/VPE configuration at reset. This is true in general, but not necessarily so for a single VPE with a single thread context. The MVP bit of the Config3 register can be retrieved at reset to determine if dynamic VPE configuration is possible. If this capability is ignored, such as in conventional software, the processor will operate according to each specific setting in the default configuration.

If the MVP bit is set, the VPC (Virtual Processor Configuration) bit of register Config3 can be set by software. This allows the processor to enter a setup state where the contents of the Config4 register can be read to determine the number of available VPE contexts, thread contexts, TLB entries, and coprocessors, and enable The "preset" fields of some normally read-only Config registers have become writable. Some restrictions can be imposed on configuration state instruction flow, for example they can be prohibited from using cached or TLB mapped memory addresses.

In the configuration state, the total number of configurable VPEs is encoded in the PVPE field of the Config4 register. Each VPE can be selected by writing its index into the CPUNum field of the EBase register. For the selected VPE, the following register fields can be set by writing.

· Config1.MMU_Size

· Config1.FP

· Config1.MX

· Config1.C2

· Config3. NThreads

· Config3.NITC_Pages

· Config3.NITC_PLocs

· Config3.MVP

·VPESchedule

Not all of the setting parameters mentioned above need be configurable. For example, even though the ITC pages per VPE are configurable, the number of ITC locations per page can be fixed, or both parameters can be fixed, for each VPE, the FPU can be pre-allocated or Hardwired, etc.

Coprocessors are assigned to VPEs as separate distinct units. The degree to which a coprocessor can be multithreaded should be indicated and controlled via coprocessor specific control and status registers.

By clearing the VPI disable bit of the EBase register, enable a VPE for execution after configuration.

This configuration state can be exited by issuing an ECONF command. This instruction causes all non-disabled VPEs to take a reset exception and start executing concurrently. If the MVP bit of the Config3 register is cleared during configuration and is held to zero by an ECONF instruction, the VPC bit can no longer be set and the processor configuration is effectively frozen until the next processor reset place. If MVP is still set, setting the VPC bit again can put an operating system into configuration mode again. However, if a running VPE for that processor re-enters configuration mode, there may be unpredictable results.

Quality of Service Scheduling for Multithreaded Processors

The specification so far describes an application-specific extension of a MIPS-compatible system for implementing multithreading. As mentioned above, the described MIPS implementation is for illustrative purposes only, and is not intended to limit the scope of the present invention. The functions and mechanisms as previously described can be applied to systems other than MIPS.

The issue of special services in multithreading of real-time and near-real-time threads is raised in the background paragraph, which has been briefly covered in the previous description of the ThreadSchedule register (FIG. 23) and the VPESchedule register (FIG. 24). The following sections of this specification will deal with this issue in more detail; specific extensions to deal specifically with thread-level Quality of Service (QoS) will also be more clearly explained.

background

Generally, the network design for transmitting multimedia data will involve the concept of Quality of Service (QoS), which is used to describe the need to use different strategies to process different data flows in the network. Taking voice transmission as an example, the requirements for bandwidth are relatively low, but delays of tens of milliseconds cannot be tolerated. In a broadband multimedia network, the QoS protocol can ensure that any special processing and priority can be obtained in the transmission where time is the key factor, which is a necessary guarantee for timely transmission in time.

One of the main problems affecting program execution on a combined RISC and DSP on a single chip is that it is very difficult to ensure strictly real-time execution of DSP program code in a combined multitasking environment. The DSP application can thus be viewed as requiring a QoS condition within the processor bandwidth.

Multithreading and QoS

There are many ways to schedule instruction issuance from multiple threads. An interleaved scheduler can change threads every cycle, while a block-interleaved scheduler can change threads when a cache miss or other severe stall occurs. The multithreaded ASE, described in detail above, provides an architecture for multithreaded processors that avoids any dependence on a particular thread scheduling mechanism or strategy. However, scheduling policies can have a significant impact on what Qos guarantees for the execution of various threads.

A RISC with DSP extensions becomes more useful in situations where QoS ensures that real-time DSP code can be executed. Implement multi-threading on the processor, so that the DSP program code is executed on an independent thread, and it is even possible to execute the DSP program code on an independent virtual processor, so that the hardware scheduling of the DSP thread can be programmatically determined To guarantee the QoS, which of course removes a major obstacle of RISC with DSP-enhanced functions.

QoS thread scheduling algorithm

The scheduling of quality of service threads can be loosely defined as a set of scheduling mechanisms and policies that allow a programmer or system designer to make confident and predictable statements about the execution time of a particular piece of program code. Generally, these statements are of the form "this program code will execute for no more than Nmax and no less than Nmin cycles". In many cases, only the Nmax number is considered in actual execution, but in some applications, the execution of the program code ahead of schedule can also cause problems, so Nmin should also be considered. If the difference between the Nmax number and the Nmin number can be smaller, the behavior of the entire system can be more accurately predicted.

simple priority scheme

A simple model was proposed to provide some degree of QoS when multiple threads issue a schedule, which is to simply assign the highest priority to a given real-time thread, so that when that thread is executable, it is always chosen to issue instructions. This approach can provide a minimum value of Nmin and seems to provide the minimum possible value of Nmax for the specified thread, but there are still some unfavorable consequences.

First, only one thread can have QoS guarantee in this scheme. The algorithm implies that in a thread other than the designated real-time thread, Nmax for arbitrary program code becomes substantially unbound. Second, exceptions must be included in the model when the Nmin number of a piece of program code within that particular thread is to be minimized. If the specified thread generates the exception, the value of Nmax becomes more complicated and in some cases impossible to determine. If the exception is generated by a thread other than the designated thread, the Nmax of the program code in the designated thread is strictly constrained, but the interrupt response time of the processor becomes unconstrained.

Such simple priority schemes may be useful in some situations, and have practical advantages in hardware implementation, but they still do not provide a general QoS scheduling solution.

reservation-based scheme

Another more powerful and unique thread scheduling model is based on reserved issue windows. In this scheme, a hardware scheduling mechanism allows one or more threads to be assigned N of M consecutive issue periods. In a non-disruptive environment, for a real-time code segment, this scheme does not provide the low Nmin value offered by the priority scheme, but has other advantages.

• More than one thread can be guaranteed QoS.

• The interrupt latency can be bound even when the interrupt is bound to a thread other than the one with the highest priority. This results in a lower Nmax for the real-time program code section.

A simple form of reservation-based scheduling assigns every Nth issue period to a real-time thread. There is no intermediate value of N between 1 and 2, which means that real-time threads in a multithreaded environment can take up to 50% of the processor's issue time. When a real-time task needs to use more than 50% of the embedded processor's bandwidth, a solution that allows more flexible allocation of the issue bandwidth is highly desirable.

Hybrid thread scheduling with QoS

The multithreading system described above focuses on a neutral scheduling strategy, but can also be extended to allow a hybrid thread scheduling model. In this model, real-time threads can be given a fixed schedule for a proportion of the thread issue slots, and use an implementation-dependent default schedule to allocate the remaining slots.

Bind thread to issue period

Instructions in the processor are issued sequentially in rapid succession. In a multi-threaded environment, among the majority of threads, a thread can calculate the bandwidth used by the ratio of the number of slots it occupies in a given number of slots. Instead, the present invention recognizes that a certain number of time slots can be arbitrarily declared, and the processor is restricted to reserve a certain number of time slots within that fixed number for a particular thread. Thus, a fixed portion of the bandwidth can be specified to guarantee a real-time thread.

Clearly, slots can be distributed proportionally to more than one real-time thread, and the granularity at which the scheme operates is constrained by the fixed number of issue slots on which the ratio is based. For example, if 32 slots are chosen, any one particular thread may be guaranteed to have 1/32 to 32/32 of the bandwidth.

Perhaps the most general model for allocating fixed issue bandwidth to threads is to associate each thread with a pair of integers {N, D} denoting the numerator and denominator of the fraction of the issue period allocated to that thread, For example 1/2 or 4/5. This allows almost arbitrarily fine-grained tuning of thread priority assignments if the allowed integer range is large enough, but there are some substantial disadvantages to doing so. One of the problems is that it is not trivial to convert a large set of pairs {N0, D0}, {N1, D1}, ... {Nn, Dn}} into an issue schedule using a piece of hardware logic, and The error case that more than 100% of the slots are allocated cannot be detected very easily. Another problem is that this scheme allows a thread to be assigned N/D ratios of issue slots over a considerable period of time, but it doesn't necessarily allow arbitrary statements about which issue slots are assigned to a shorter subroutine code Fragment's thread.

Therefore, in a preferred embodiment of the present invention, instead of using integer pairs, a bit vector is associated with each thread requiring real-time bandwidth QoS, and the bit vector represents the scheduling period to be allocated to the thread . In this preferred embodiment, this vector is the content of the aforementioned ThreadSchedule register (FIG. 23), which can be seen by the system software. Although the ThreadSchedule register has a 32-bit wide scheduling "mask," there may be longer or shorter bit widths in the mask in other embodiments. A thread scheduling mask with a width of 32 bits may allow a thread to be allocated from 1/32 to 32/32 of the processor's issue bandwidth, and may further assign specific issue bandwidth patterns to specific issuing threads. For a 32-bit mask, the value 0xaaaaaaaa will be assigned to the thread every second epoch. A value of 0x0000ffff also assigns 50% of the issue bandwidth to this thread, but in blocks of 16 consecutive periods. The value 0xeeeeeeee is assigned to thread X and the value 0x01010101 to thread Y, giving thread X three of every four cycles (24 of 32) and thread Y one of every eight cycles (32 4 of them), and 4 of the remaining 32 cycles in each group are allocated to other threads by other possibly less deterministic hardware algorithms. Further, thread X will have three of every four cycles, and thread Y will have no more than eight cycles between two consecutive sets of instructions.

Scheduling conflicts in this embodiment can be detected very simply because no bit will be set in the ThreadSchedule register for more than one thread. That is, if a particular bit is set for one thread, that bit must be zero for all other threads that are assigned an emit mask. Therefore, if there is any conflict, it can be easily detected.

The issue logic of real-time threads is relatively simple and straightforward: each issue opportunity is associated with a 32-modulus index, which will be sent to all ready threads, and at most one of these ready threads will be assigned the associated issue period . If the slot is obtained, the associated thread issues its next instruction. If no thread owns the slot, the processor selects an executable non-real-time thread.

If the hardware implementation of the ThreadSchedule register uses less than 32 bits, it can reduce the storage and logic size of each thread, but it will reduce the scheduling flexibility at the same time. In principle, this register could be extended to 64 bits, or even implemented (in the case of MIPS processors) as a chain of registers, increasing the select value in the MIPS32 CP0 register space, thus providing longer scheduling vectors.

exempt thread from interrupt servicing

As mentioned earlier, interrupt servicing can cause the thread executing the exception program to have great variability in execution time. Therefore, it is desirable to enable threads requiring strict QoS guarantees to be interrupt service free. A preferred embodiment is presented here that utilizes a single bit per thread, visible to the operating system, to delay any asynchronous exception until a non-exempt thread is scheduled (i.e., the ThreadStatus register IXMT bit, please refer to Figure 18 and Figure 19). This will increase the delay of the interrupt, but through the selection of the value of the ThreadSchedule register, the interrupt delay can be limited to a constrained and controllable level. If the interrupt handler is only executed in those issue slots that are not assigned to exempt real-time QoS threads, naturally the interrupt servicing does not have any priority impact on the execution time of the real-time program code.

Issue slot allocation for threads and virtual processing units

The multithreaded ASE described in detail above describes a hierarchical allocation of thread resources where some number of VPEs (Virtual Processing Units) each have some number of threads. Each VPE has a hardware implementation of CP0 and a privileged resource architecture (when configured on a MIPS processor), so the operating system software (OS) running on one of the VPEs cannot directly know and control what is required by other VPEs issue period. The issue window namespace for each VPE is thus associated to that VPE, which forms a hierarchy of issue window assignments.

FIG. 34 is a block schematic diagram of a scheduling circuit 3400 depicting such a hierarchical allocation of thread resources. The processor scheduler 3402 (ie, the overall scheduling logic of the host processor) passes an issue slot number via the "slot select" signal 3403 to all VPESchedule registers in all VPEs within the host processor. Signal 3403 corresponds to a bit position (in the preferred embodiment, one of thirty-two positions) in the VPESchedule register. By shifting the bit position to an incremental position each emission period occurs, and resetting to the least significant bit position when the most significant bit position is reached (ie, bit 31 in the preferred embodiment) bit position (ie, bit 0), the scheduler 3402 repeatedly cycles the signal 3403 .

Referring again to FIG. 34 , taking this figure as an example, bit position 1 (ie, period 1 ) is passed to all VPESchedule registers of the host processor, ie, registers 3414 and 3416 , via signal 3403 . In any VPESchedule register, if its corresponding bit is "set" (ie, the bit is logic 1), the register notifies the processor scheduler with a "VPE issued request" signal. In response, the scheduler will allow the VPE to use the current issue slot with a "VPE issue allow" signal. Referring again to FIG. 34 , the bit position 1 of the VPESchedule register 3414 (in VPE0) is set, so a VPE sends a request signal 3415 to the processor scheduler 3402, and then the processor scheduler 3402 also responds to a VPE sent Allow signal 3405.

When a VPE is granted an issue, it uses similar logic at the VPE level. Referring again to FIG. 34 , the VPE scheduler 3412 (i.e. the scheduling logic of VPE0 3406) responds to the signal 3405, and transmits a sending period number to all ThreadSchedule registers in the VPE via the period selection signal 3413. Each of these ThreadSchedule registers is associated to a thread supported by the associated VPE. Signal 3413 corresponds to a bit position (in this embodiment, one of thirty-two bits) in the ThreadSchedule register. By shifting the bit position to an incremental position at the occurrence of each issue period, and resetting to the least significant bit position when the most significant bit position is reached (ie, bit 31 in the preferred embodiment) (ie, bit 0), the scheduler 3412 loops the signal 3403 repeatedly. This slot number is independent of the slot number used at the VPESchedule level.

Referring to FIG. 34 and taking it as an example, bit position 0 (ie, "Period 0") is passed via signal 3413 to all ThreadSchedule registers in the target VPE, ie, registers 3418 and 3420 . If any thread's ThreadSchedule register bit in the selected location has been set, the thread notifies the VPE scheduler that it is allowed to use the current issue slot. Referring to FIG. 34, bit position 0 of the ThreadSchedule register 3418 (of thread 0) is set so that a thread issue request signal 3419 is sent to the VPE scheduler 3412, which in turn responds to a thread issue enable signal 3417 ( Thus allowing thread 0 to use the current issue period). During some cycles, if the bit corresponding to the specified time period is not set in the VPESchedule register, or if the bit corresponding to the specified time period is not set in the ThreadSchedule register, the processor or VPE scheduler will execute according to some other The default scheduling algorithm to allocate the next emission slot.

According to the foregoing, in a preferred embodiment, each VPE, such as VPE0 (3406) and VPE1 (3404) of FIG. 34, has a VPESchedule register (its format is shown in FIG. 24) to allow The length of the register content is modulo a specific period that can be deterministically assigned to the VPE. The VPESchedule registers in FIG. 34 are the register 3414 of VPE0 and the register 3416 of VPE1. Those emission slots that are not allocated to any VPE are allocated by an implementation-specific allocation policy.

Also according to the description above, the time slots allocated to threads within a VPE are allocated from the time slots given to that VPE. As a concrete example, if a processor has two VPEs, as shown in Figure 34, and one of the VPEs has a VPESchedule register with a value of 0xaaaaaaaa and the other VPE has a VPESchedule register with a value of 0x55555555, the issue slots are alternately assigned to These two VPEs. If a thread's ThreadSchedule register in one of these two VPEs contains the value 0x55555555, the thread gets one of every two issue slots for the VPE that contains that thread, or every fourth issue slot for the entire processor one of the.

Therefore, the value of the VPESchedule register associated with each VPE determines which processing time slots each VPE will get. Specific threads are assigned to each VPE, such as thread 0 and thread 1 shown in VPE0. Other threads not shown are similarly assigned to VPE1. Each thread has an associated ThreadSchedule register, eg register 3418 for thread 0, register 3420 for thread 1. The value of the ThreadSchedule register determines the allocation of processing time slots for each thread in a VPE.

The schedulers 3402 and 3412 can be implemented with simple combinational logic to perform the above-mentioned functions. According to the disclosure of the present invention, the construction of these schedulers can be implemented by those skilled in the art without complicated experiments. For example, the scheduler can also be constructed using conventional methods, such as combinational logic, programmable logic, software, etc., to achieve the described functions.

FIG. 33 depicts a general form of computer system 3300 upon which various embodiments according to the invention may be implemented. The system includes a processor 3302 (as should be apparent to those of ordinary skill in the art) with the necessary decoding and execution logic to support one or more of the above instructions (i.e., FORK, YIELD, MFTR, MTTR, EMT, DMT and ECONF). In a preferred embodiment, the core 3302 also includes a scheduling circuit 3400 as shown in FIG. 34 and represents the above-mentioned "main processor". System 3300 also includes: system interface controller 3304, which can communicate bidirectionally with the processor; RAM3316 and ROM3314, which can be accessed by the system interface controller; Interface controller communication. With the detailed description of the apparatus and program code used herein, the system 3300 can operate as a multi-threaded system. It should be clear to those skilled in the art that many alternatives to the general form shown in Figure 33 are possible. For example, bus 3312 may be implemented in many forms, and in some embodiments may be an on-chip bus. Similarly, the number of I/O devices is only for convenience of description, and can be changed arbitrarily in different systems in essence. Additionally, although only device 3306 has issued an interrupt request in the figure, it is obvious that other devices can also issue interrupt requests.

further improvement

In the embodiments described so far, the 32-bit ThreadSchedule and VPESchedule registers do not allow precise allocation of odd proportions of issue bandwidth. If a programmer wishes to allocate exactly one-third of all issue slots to a given thread, he can only approximate to 10/32 or 11/32. In one embodiment, a register with a programmable mask or length allows the programmer to specify a subset of bits in the ThreadSchedule register and/or the VPESchedule register to be used by the issuing logic before restarting the sequence. In the example presented, the programmer set only 30 bits to be valid, and programmed the VPESchedule register and/or the ThreadSchedule register to have a value of 0x24924924 as appropriate.

The multithreaded ASE described herein can of course be implemented in hardware, for example, in a central processing unit (CPU), microprocessor, digital signal processor, processor core, system on chip (SOC) or any other programmable device , or connect with each of the above devices. In addition, the multithreaded ASE can also be implemented in software (for example, computer readable program code, program code, instructions and/or data in any form, such as source language, target language or machine language), the software is set on the computer A usable (eg, readable) medium is used to store the software. The software enables the function, fabrication, modeling, simulation, description and/or testing of the devices and processes described herein. For example, these can be realized by using the following tools: general-purpose programming languages (such as C language, C++ language), GDSII database, hardware description language (HDL), which includes Verilog HDL, VHDL, AHDL (Altera HDL), etc., or Other available programs, databases and/or circuit (ie, schematic) design tools. The software may reside on any known computer-usable medium, including semiconductor, magnetic disk, optical disk (e.g. CD-ROM, DVD-ROM, etc.), or as any computer-usable (e.g., readable) A computer data signal embodied in a transmission medium such as a carrier wave, any other medium including digital, optical, or analog based. Accordingly, the software may be transmitted across communication networks including the Internet and intranets.

A software-implemented multithreaded ASE can be included within a semiconductor intellectual property core, such as a processor core (eg, implemented in HDL), and can be converted to hardware during the production of integrated circuits. Alternatively, a multithreaded ASE as described here can also be implemented as a combination of hardware and software.

It is obvious to those skilled in the art that modifications and modifications can be made to the disclosed embodiments of the present invention without departing from the spirit and scope of the present invention. For example, the previously described embodiments mostly use the MIPS processor, architecture and technology as specific examples. The present invention has various embodiments and can be applied in a wider range without being limited to these specific examples. Furthermore, one skilled in the art may find ways to make minor changes to the described functionality of the invention and still remain within the spirit and scope of the invention. When describing QoS, the contents of the ThreadSchedule register and the VPESchedule register are not limited to the described lengths, and can be modified within the spirit and scope of the present invention.

Accordingly, it is intended that the scope of the invention be limited essentially only by the scope of the appended claims.

Claims (87)

1. can support and carry out in the processor of multiprogram thread at one, a kind of mechanism of processing comprises:

A parameter is used to dispatch a program threads; And

An instruction places this program threads, and can this parameter of access;

Wherein, when this parameter equaled first numerical value, this instruction rescheduled this program threads according to one or more conditions that are encoded in this parameter.

2. mechanism as claimed in claim 1, wherein this parameter is kept in the data storage device.

3. mechanism as claimed in claim 1 wherein equals second value when this parameter, and this second value is when being not equal to this first numerical value, and this instruction discharges this program threads.

4. mechanism as claimed in claim 3, wherein this second value is zero.

5. mechanism as claimed in claim 1 wherein equals second value when this parameter, and this second value is when being not equal to this first numerical value, and this instruction unconditionally reschedules this program threads.

6. mechanism as claimed in claim 5, wherein this second value is an odd number.

7. mechanism as claimed in claim 5, wherein this second value is negative 1.

8. mechanism as claimed in claim 1, wherein to convey other thread this program threads till this condition is satisfied relevant with carrying out chance for condition in these one or more conditions.

9. mechanism as claimed in claim 8, wherein this condition is encoded in one of bit vector in this parameter or bit field.

10. mechanism as claimed in claim 5, wherein, under the situation that this program threads is rescheduled, the execution meeting of this program threads should continue instruction position afterwards in this thread.

11. mechanism as claimed in claim 3 wherein equals third value when this parameter, and this third value is when being not equal to this first numerical value and this second value, this instruction unconditionally reschedules this program threads.

12. mechanism as claimed in claim 1, wherein a condition in these one or more conditions is a hardware interrupts.

13. mechanism as claimed in claim 1, wherein a condition in these one or more conditions is a software interruption.

14. mechanism as claimed in claim 1, wherein, under the situation that this program threads is rescheduled, the execution meeting of this program threads should continue instruction position afterwards in this thread.

15. can support and carry out in the processor of multiprogram thread at one, a kind ofly reschedule the method for carrying out or discharging this thread itself by a thread, comprising:

(a) send an instruction, the part of records in data memory storage of this instruction accessing, this part record coding with the relevant one or more parameters of one or more conditions that whether rescheduled of this thread of decision; And

(b) reschedule this thread or discharge this thread according to this condition according to these the one or more parameters in this partial record.

16. method as claimed in claim 15, wherein this record is placed in the general-purpose register (GPR).

17. method as claimed in claim 15, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled.

18. method as claimed in claim 17, this wherein relevant with this d/d thread parameter is a null value.

19. method as claimed in claim 15, wherein a parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

20. method as claimed in claim 19, wherein this parameter is any odd number value.

21. method as claimed in claim 19, wherein this parameter is negative 1 two's complement value.

22. method as claimed in claim 15, wherein to convey other thread this thread till specified conditions are satisfied relevant with carrying out chance for parameter in these parameters.

23. method as claimed in claim 22, wherein this parameter is encoded in one of bit vector in this record or one or more value fields.

24. method as claimed in claim 15, wherein, send under this instruction and the quilt situation that reschedules at this thread, when these one or more conditions were satisfied, continued the position after the execution meeting of this thread this instruction that this thread sent in this thread instruction stream.

25. method as claimed in claim 15, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

26. method as claimed in claim 15, wherein parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

27. method as claimed in claim 15, wherein parameter in these parameters waits for that the thread that reschedules is relevant with being requeued, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

28. method as claimed in claim 15, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, another parameter in these parameters is relevant with the thread of being waited for scheduling by requeuing, and another parameter again in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

29. support and the digital processing unit of carrying out a plurality of software entitys comprise:

Part of records in data storage device, this partial record one or more parameters relevant of having encoded with one or more conditions, these one or more conditional decisions when a thread will be carried out chance and convey other thread this thread whether rescheduled.

30. digital processing unit as claimed in claim 29, wherein this partial record is placed in the general-purpose register (GPR).

31. digital processing unit as claimed in claim 29, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled.

32. digital processing unit as claimed in claim 31, this wherein relevant with this d/d thread parameter is a null value.

33. digital processing unit as claimed in claim 29, wherein a parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

34. digital processing unit as claimed in claim 33, wherein the value of this parameter is any odd number value.

35. digital processing unit as claimed in claim 33, wherein the value of this parameter is negative 1 two's complement value.

36. digital processing unit as claimed in claim 29, wherein to convey other thread relevant up to the thread that specified conditions are satisfied with carrying out chance for parameter in these parameters.

37. digital processing unit as claimed in claim 36, wherein this parameter is encoded in one of bit vector in this record or one or more value fields.

38. digital processing unit as claimed in claim 29, wherein parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters and the quilt thread that wait dispatches that requeues is relevant.

39. digital processing unit as claimed in claim 29, wherein parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

40. digital processing unit as claimed in claim 29, wherein parameter in these parameters waits for that the thread that reschedules is relevant with being requeued, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

41. digital processing unit as claimed in claim 29, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, another parameter in these parameters is relevant with the thread of being waited for scheduling by requeuing, and another parameter again in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

42. the disposal system that can support and carry out a plurality of program threads comprises:

A digital processing unit;

Part of records in data storage device, this partial record one or more parameters relevant of having encoded with one or more conditions, these one or more conditional decisions a thread whether rescheduled; And

An instruction set comprises an instruction that is used to reschedule and discharge this thread;

Wherein when this thread sends this instruction, this instruction accessing this one or more parameters in should record, and this system reschedules according to these one or more conditions according to these the one or more parameters in this partial record or discharges the thread that this sends instruction.

43. disposal system as claimed in claim 42, wherein this partial record is placed in the general-purpose register (GPR).

44. disposal system as claimed in claim 41, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled.

45. disposal system as claimed in claim 44, this wherein relevant with this d/d thread parameter is a null value.

46. disposal system as claimed in claim 44, wherein a parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

47. disposal system as claimed in claim 46, wherein the value of this parameter is any odd number value.

48. disposal system as claimed in claim 46, wherein the value of this parameter is negative 1 two's complement value.

49. disposal system as claimed in claim 41, wherein to convey other thread relevant up to the thread that specified conditions are satisfied with carrying out chance for parameter in these parameters.

50. disposal system as claimed in claim 49, wherein this parameter is encoded in one of bit vector in this record or one or more value fields.

51. disposal system as claimed in claim 44, wherein, a thread send this instruction and the situation that rescheduled conditionally under, when these one or more conditions were satisfied, continued the position of the execution meeting of this thread after should instruction in this thread instruction stream.

52. disposal system as claimed in claim 42, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

53. disposal system as claimed in claim 42, wherein parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

54. disposal system as claimed in claim 42, wherein parameter in these parameters waits for that the thread that reschedules is relevant with being requeued, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

55. disposal system as claimed in claim 42, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, another parameter in these parameters is relevant with the thread of being waited for scheduling by requeuing, and another parameter again in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

56. digital storage medium, be written into instruction on it from an instruction set, be used on a digital processing unit, carrying out each software thread of a plurality of software threads, this instruction set has comprised an instruction, be used to make the thread that sends instruction to abandon carrying out, an and parameter in the record of the some in data storage device of access, wherein, the condition and this parameter correlation that discharge or reschedule, and discharge according to this condition according to this parameter in this partial record or reschedule.

57. digital storage medium as claimed in claim 56, wherein this record is placed in the general-purpose register (GPR).

58. digital storage medium as claimed in claim 57, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled.

59. digital storage medium as claimed in claim 58 should the parameter relevant with d/d thread be a null value wherein.

60. digital storage medium as claimed in claim 56, wherein a parameter in the middle of these parameters is relevant with the thread of the wait scheduling of being requeued.

61. digital storage medium as claimed in claim 60, wherein the value of this parameter is any odd number value.

62. digital storage medium as claimed in claim 60, wherein the value of this parameter is negative 1 two's complement value.

63. digital storage medium as claimed in claim 16, wherein to convey other thread relevant up to the thread that specified conditions are satisfied with carrying out chance for parameter in these parameters.

64. as the described digital storage medium of claim 63, wherein this parameter is encoded in one of bit vector in this record or one or more bit fields.

65. digital storage medium as claimed in claim 56, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters is relevant with the thread of the wait scheduling of being requeued.

66. digital storage medium as claimed in claim 56, wherein parameter in these parameters is relevant with thread d/d rather than that rescheduled, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

67. digital storage medium as claimed in claim 56, wherein parameter in these parameters waits for that the thread that reschedules is relevant with being requeued, and another parameter in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

68. digital storage medium as claimed in claim 56, wherein a parameter in these parameters is relevant with thread d/d rather than that rescheduled, another parameter in these parameters is relevant with the thread of being waited for scheduling by requeuing, and another parameter again in these parameters with will carry out chance and convey other thread and be satisfied relevant up to specified conditions.

69. mechanism as claimed in claim 1, wherein this instruction is a YIELD instruction.

70. mechanism as claimed in claim 1, wherein this partial record comprises bit vector.

71. mechanism as claimed in claim 1, wherein this partial record comprises one or more multiple bit fields.

72. method as claimed in claim 15, wherein this instruction is a YIELD instruction.

73. disposal system as claimed in claim 42, wherein this instruction is a YIELD instruction.

74. digital storage medium as claimed in claim 56, wherein this instruction is a YIELD instruction.

75. a computer data signal that is included in the transmission medium comprises:

Computer-readable program code, it is used to describe the processor that can support and carry out a plurality of program threads, and it comprises a kind ofly in order to discharge and to reschedule the mechanism of a thread, and this program code comprises:

First program code segments is used for describing the part of records of a data memory storage, this partial record one or more parameters relevant with the one or more conditions that determine a thread whether to be rescheduled of having encoded; And

Second program code segments, be used for describing an instruction of these one or more parameters that can this record of access, wherein when this thread sends this instruction, the one or more values of this instruction accessing in should record, and come to reschedule or discharge this thread according to these one or more conditions according to these one or more values.

76. in the processor that can support a plurality of program threads, a kind of method comprises:

Carry out an instruction, this instruction can an access parameter relevant with thread scheduling, and wherein this instruction is included in the program threads; And

When this parameter equals first numerical value, discharge this program threads in response to this instruction.

77. as the described method of claim 76, wherein this first numerical value is zero.

78., also comprise as the described method of claim 76:

When this parameter equals second value, hang up the execution of this program threads in response to this instruction, wherein this second value is not equal to this first numerical value.

79. as the described method of claim 78, wherein this second value is represented, carries out the required condition that possesses of this program threads and does not satisfy.

80. as the described method of claim 79, wherein this condition is encoded in this parameter as bit vector or value field.

81., also comprise as the described method of claim 78:

When this parameter equals third value, reschedule this program threads in response to this instruction, wherein this third value is unequal in this first numerical value and second value.

82. as the described method of claim 81, wherein this third value is negative 1.

83. as the described method of claim 81, wherein this third value is an odd number value.

84. in the processor that can support a plurality of program threads, a kind of method comprises:

Carry out an instruction, parameter relevant of this instruction accessing with thread scheduling, wherein this instruction is contained in the program threads;

When this parameter equals first numerical value, hang up the execution of this program threads in response to this instruction.

85., also comprise as the described method of claim 84:

When this parameter equals second value, reschedule this program threads in response to this instruction, wherein this second value is not equal to this first numerical value.

86. in the processor that can support a plurality of program threads, a kind of method comprises:

Carry out an instruction, the parameter that this instruction accessing is relevant with thread scheduling, wherein this instruction is contained in the middle of the program threads; And

When this parameter equals first numerical value, reschedule this program threads in response to this instruction.

87., also comprise as the described method of claim 86:

When this parameter equals second value, discharge this program threads in response to this instruction, wherein this second value is not equal to this first numerical value.

Images