JPH11282815A - Multi-thread computer system and multi-thread execution control method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a multi-thread computer system which includes a user level interrupt mechanism of reduced overhead and a fast exclusive control mechanism to execute a fine grain multi-thread. SOLUTION: When a thread execution is started by a processor element 11, the value of a counter 26 is decreased for every clock. When the value of the counter 26 is set to zero, an interrupt control part 41 starts the user level interrupt processing to shift its control to the address of a user thread scheduler 101 that is set at a user handler register 20. Meanwhile, a test-and-set instruction performs a lock operation to a lock variable set 30 included in a processor 1 and attains an exclusive control among the elements 11.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a parallel computer system, and more particularly, to a multi-thread computer system for efficiently scheduling a plurality of threads on a shared memory multiprocessor computer without using an operating system.

[0002]

2. Description of the Related Art In order to obtain higher processing performance, there is a computer system having a multiprocessor configuration having a plurality of processor elements in one system. Among such computer systems, a system in which each processor element shares a main memory is called a shared memory type multiprocessor computer system, which has an advantage that a program can be easily described as compared with a distributed memory type system. .

On the other hand, in software, there is a parallel execution method called multi-thread execution in which one process is divided into control flows called threads and a plurality of threads are executed in parallel. On a multiprocessor computer system, processing performance is improved by allocating a plurality of threads to a plurality of processor elements and executing them simultaneously.

The management of threads in a multiprocessor computer system is usually performed by a multiprocessor operating system. That is, when creating a new thread, synchronizing with another thread, or deleting a thread, the thread calls a service of the operating system.

[0005] Thread preemption is also performed through the operating system. Preemption is a process of interrupting the execution of a thread that occupies the processor for a long time and switching to the execution of another thread. The computer system having the preemption function has a hardware timer device and a mechanism for transmitting an interrupt signal from the timer device to the processor when a predetermined time has elapsed. When a certain period of time has elapsed since the start of the execution of the user program, control is transferred to the operating system by a timer interrupt, and the operating system switches the execution thread.

To efficiently execute a plurality of threads on a multiprocessor computer system, thread generation,
It is important to reduce thread management overhead such as synchronization, switching, and extinction.

The Sun Microsystems Solaris
aris) In the operating system, threads can be managed by a user-level library instead of the operating system. This allows
Thread management can be performed with lower overhead, but in the case of preemption, the operating system is involved (Introduction to Multithread Programming, ASCII Publishing, September 1996, p69-p70 and p76-p77).

[0008] The preemption processing circuit described in Japanese Patent Application Laid-Open No. 5-158900 accepts preemption not by an operating system but by dedicated hardware. This is done by an interrupt.

On the other hand, when reading and writing a computer resource shared by a plurality of threads, for example, a shared variable in a main memory, an erroneous processing result may be obtained by a plurality of threads simultaneously accessing the computer resource. In order to avoid this problem, it is necessary to perform a process called exclusive control (for exclusive control, see, for example, AS Tanenbaum, “Basics and Application of OS”, Prentis Hall Toppan, Chapter 2, Section 2.2 Etc.).

Exclusive control is usually realized by an exclusive control processor instruction such as test and set or exchange. These instructions inseparably check the value of a certain memory cell in the main memory and set a new value to that memory cell. For example, the test-and-set instruction performs the following three operations without interruption or division by another processor. (1) Reading the value of a certain memory cell in the main memory to the computer register (2) Writing the value 1 to the memory cell (3) Comparing the value read to the computer register with the value 0

In a shared memory type multiprocessor computer system, since exclusive control is performed between different processors, these exclusive control instructions act on a shared main memory. That is, access to the main storage memory is required for exclusive control itself.

[0012]

A first problem with the prior art is that a sufficiently high-speed interrupt response process cannot be performed due to multi-thread execution, and the overhead of thread switching is large. This is because, since the interrupt processing is processed in the operating system, a context switch from the user program to the operating system occurs.

The second problem is that access to the main memory occurs due to the exclusive control processing itself, and the overhead of exclusive control and synchronization processing between threads, which is indispensable for multi-thread processing, is large. Since the processing speed of recent processors is much faster than the access speed of the main memory, many processors have a high-speed, small-capacity memory called a cache memory between the processor and the main memory. To avoid processing delays due to memory access. However, since the exclusive control instruction always accesses the main storage memory, the processing speed is reduced.

All of the above-mentioned problems cause an increase in the overhead of multi-thread processing. In particular, when multi-thread processing is performed in units of small-grained threads (threads containing a small number of instructions), large effects are caused. Bring.

[0015]

SUMMARY OF THE INVENTION It is an object of the present invention to provide a high-speed user-level interrupt without the intervention of an operating system, and to improve the efficiency of multi-thread processing.

Another object of the present invention is to provide a high-speed locking mechanism between processor elements in a multiprocessor computer system, and to improve the efficiency of multithread processing.

[0017]

The multithreaded computer system of the present invention has a high-speed user-level interrupt mechanism for providing a high-speed user-level interrupt without the intervention of an operating system. Specifically, it includes an interrupt control unit (41 in FIG. 2) in the processor, a counter (26 in FIG. 2) in each processor element, and a user handler register (20 in FIG. 2).

Further, the multi-thread computer system of the present invention has a high-speed lock mechanism for providing a high-speed lock mechanism between processor elements in a multi-processor computer system. Specifically, the first high-speed lock mechanism includes a lock variable set (30 in FIG. 2) shared between the processor elements in the processor, and computer instructions for operating the lock variable set. Further, the second high-speed locking mechanism has lock variables of a queue structure (61, 62 and 69 in FIG. 3). Further, the third high-speed lock mechanism has a shared cache memory (71 in FIG. 4) in the processor and computer instructions for operating a memory area on the cache.

Further, a multi-thread execution control method according to the present invention includes a processor including a plurality of processor elements and a main memory shared by the plurality of processor elements, wherein one user process is divided into a plurality of threads, In a multi-thread execution control method in a multi-thread computer system in which a plurality of threads are allocated to a plurality of processor elements under the control of a thread scheduler in the user process and executed simultaneously, a high-speed user-level interrupt without an operating system is provided. To do so, it involves the following steps: (A) The memory address where the thread scheduler of the user process is placed is set in the user handler register in the processor element to which the thread of the user process is allocated, and the time quantum value to be allocated to the thread in the counter in the processor element. (B) updating the value of the counter in the processor element at a constant period simultaneously with the start of execution of the thread in the processor element, and generating a user-level interrupt when the count value reaches a predetermined count value (C) In the processing of the user-level interrupt, the current value of the program counter of the processor element of the interrupt request source is stored in the user save P
C to transfer control to the thread scheduler in the user process by setting the memory address set in the user handler register in the processor element to the program counter.

Further, the multi-thread execution control method of the present invention provides an exclusive control between a plurality of threads executed by a plurality of processor elements in order to enable a high-speed exclusive control between the processor elements in a multi-processor computer system. By the following (a), (b), (c)
Is realized by any of the above. (A) Exclusive control is performed using a set of 1-bit storage devices accessible from each processor element by a computer instruction set provided in the processor and capable of exclusively operating values between the processor elements. (B) A set of queue structures in a processor that store tokens having identification numbers corresponding to the processor elements in the order of arrival, and are provided by a computer instruction set in which tokens can be exclusively added, searched, or deleted between the processor elements. Exclusive control is performed using a set of queue structures accessible from each processor element. (C) A memory element in a shared cache memory that can be accessed from each processor element through an access arbitration mechanism that arbitrates access to the same address between the processor elements, and is a computer that can exclusively operate values between the processor elements. Exclusive control is performed using a memory element accessible by the instruction set.

[0021]

When the counter reaches zero, the interrupt controller starts user-level interrupt processing. In the user level interrupt processing, the value of the user handler register, which is set in advance as the start address of the thread scheduler of the user process, is set in the program counter, and the control is transferred to the thread scheduler without passing through the operating system.

A fast lock mechanism provided in the processor provides lock acquisition and release functions without having to access main memory.

[0023]

BEST MODE FOR CARRYING OUT THE INVENTION

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a diagram showing an example of a computer configuration in which the present invention is implemented. The processor 1 has a plurality of processor elements 11, 12 and 19 therein, and these processor elements access a common main memory 2.

Referring to FIG. 2, a first embodiment of the present invention is a processor 1 having a plurality of processor elements therein, an operating system 50 operating on the processor, and operating on the operating system. And a user process 100.

Each processor element in the processor 1 includes a counter 26 for generating a user-level preemption interrupt and a zero comparator 25, in addition to a register set, an operation unit, and a control unit of a general computer processor. , A user handler register 20 used for control movement when a user level interrupt occurs, and a user save PC 23.

The value of the counter 26 is decremented for each clock by the clock signal. The zero comparator 25 compares the value of the counter 26 with zero. The user handler register 20 is a register holding a program counter value to which execution control is to be transferred when a user level interrupt occurs, and the user save PC 23 is a register for saving the program counter value immediately before the user level interrupt occurs. is there.

The program counter (PC) 22 and the interrupt controller 41 shown in FIG. 2 have the same functions as the program counter and the interrupt controller of a general computer processor.
The kernel save PC 24 has the same function as an interrupt handler register and a program counter save register used when a normal interrupt occurs in a general computer processor.

The user process 100 is an entity of an execution program generated by the operating system 50. The user process 100 is composed of a plurality of threads 102, 103 and 104 sharing a main memory space, and these threads are assigned to processor elements and executed. The thread scheduler 101 links the user process 1 with the user program 1
00, and manages all the threads constituting the user process.

In the processor, there are a lock variable set 30 and an access arbiter 40 shared by all processor elements. The lock variable set 30 is a set of lock variables that can store a 1-bit state, and the access arbitration mechanism 40 is a mechanism that arbitrates access to the lock variable between processor elements.

[0031]

[Description of Operation] The operation of this embodiment will be described in detail with reference to FIG.

When the operating system 50 starts the user process 100, the user process 100 calls a thread scheduler 101 incorporated therein. The thread scheduler 101 schedules a set of threads in the user process 100 according to a certain scheduling algorithm. When the thread scheduler 101 selects a thread to be executed next (here, the thread 102),
The thread scheduler 101 sets the time quantum value assigned to the thread 102 in the counter 26 of the processor element 11 to which the thread 102 is assigned, and sets the memory address where the thread scheduler 101 is located in the user handler register 20 of the processor element 11. Thereafter, the execution of the thread 102 by the processor element 11 is started.

In parallel with the execution of the thread 102, the value of the counter 26 is reduced at regular intervals by a clock signal. When the value becomes zero, the zero comparator 25 sends an interrupt request signal to the interrupt control unit 41. The interrupt control unit 41 determines that the processor element 1
At step 1, the user level interrupt process is started.

When the user level interrupt processing starts,
The processor element 11 sets the current value of the program counter 22 in the user save PC 23 and sets the value of the user handler register 20 in the program counter 22. As a result, control is quickly transferred to the thread scheduler 101 inside the user process 100 without going through the operating system 50. The thread scheduler 101 saves the execution state of the thread 102 including the value of the register set in a management data area inside the thread scheduler 101, selects the next thread to start execution according to a predetermined scheduling algorithm, and The value of the register set of the thread is restored, and the time quantum value corresponding to the thread is set in the counter 26, and the execution of the next thread is started.

On the other hand, a case where the conventional interrupt processing is used will be described below. First, the context is switched from the user program to the operating system at the start of interrupt processing. This context switching includes: o Kernel save P of the current value of the program counter 22
Setting to C24 ○ Setting of the value of the kernel handler register 21 to the program counter 22 ○ Switching of the processor operation mode to the kernel mode ○ Saving of necessary register set contents to the main memory is included. By this context switching, control is transferred to the kernel level interrupt handler 51 inside the operating system 50 and then to the process scheduler 52. The process scheduler 52 analyzes the cause of the interruption and determines the next process to be executed according to a predetermined scheduling algorithm. Then, the context is switched again and the execution of the next process is started. This context switching includes: (i) setting a register set for the next process; (ii) setting a logical address space for the next process; and (ii) switching processing of the operation mode of the processor to the user mode. After a series of these processes, control is finally transferred to the user process.

In other words, the introduction of the user-level interrupt mechanism makes it possible to use a preemption mechanism, which is faster than the conventional one, without the overhead of passing through the operating system, in the user program.

The interrupt factor of the user-level interrupt mechanism is not limited to the preemption interrupt due to the zero match of the down counter. If only the interrupt control unit is used, it can be used for the purpose of processing an invalid instruction interrupt in a user process, for example.

Next, referring to FIG.
A high-speed lock mechanism using the above will be described. Each processor element accesses a lock variable inside the lock variable set 30 by using a test and set instruction provided in the present processor. When one processor element 11 uses a test-and-set instruction for a lock variable, the access arbitration mechanism 40 temporarily inhibits access to the lock variable from other processor elements, during which the processor element 11 returns to the value of the lock variable. Is compared with zero and reflected in the status flag in the processor element 11, and the value 1 is set in the lock variable. From the viewpoint of software, the operation of the test and set instruction described in the present embodiment is the same as the operation of the test and set instruction provided in the conventional processor, but the access to the main memory causing a large delay is performed. Because it is not accompanied, variables can be locked with much less overhead than before.

It is appropriate that the number of lock variables mounted in the processor is 8, 16, or 32. The reason is that sophisticated exclusion control and synchronization control mechanisms for users can be easily constructed using more basic exclusion control mechanisms, and such basic exclusion control mechanisms use a small number of lock variables. This is because the instruction field width for specifying the number of the lock variable can be reduced by increasing the number of lock variables to a small power of 2, thereby increasing the instruction efficiency. Further, the number of lock variables is set to 32 or 64 which is a general number of bits of the register set.
Within this range, the entire lock variable set can be treated as one special register. This makes it possible to include the lock variable set in the context corresponding to the process, and to use a logically independent high-speed lock mechanism for each process.

The introduction of the above-mentioned user-level interrupt mechanism and high-speed lock mechanism enables parallel processing in smaller units than before, thereby improving the effective performance of a multiprocessor computer and expanding its application field. Can be. This is the effect of the present embodiment.

[0041]

Next, another embodiment of the user level interrupt mechanism will be described.

In FIG. 2, the input of the counter 26 is a clock signal, but this signal is not limited to the clock signal of the computer system. If the system clock signal obtained by dividing the system clock signal by a suitable frequency divider by a factor of 1 is used as the input to the counter 26, the number of bits of the hardware constituting the counter 26 and the computer instruction for setting the value in the counter 26 are included. The bit width of the counter value field can be reduced, and the efficiency of both hardware and software can be improved. Instead of the system clock signal, a signal of the instruction execution control mechanism of the processor element may be input to the counter 26 so that the counter 26 is decremented each time one instruction is executed.

Next, another embodiment of the high-speed lock mechanism will be described.

Referring to FIG. 3, the second high-speed locking mechanism
In this embodiment, each lock variable has a queue structure. Each of the queues 61, 62 and 69 can store tokens up to the number equal to the number of processor elements. The token is issued by each processor element, and the number of the issued processor element is attached to the token. If there is one or more tokens in the queue, it means that the processor element that issued the token at the head of the queue has locked the lock variable corresponding to the queue. To operate this lock variable, two types of computer instructions, a lock trial instruction and a lock release instruction, are provided. , 19 and the queues 61, 62, ..., 6
The queue control mechanism 60 provided between the queues 61 and 62 when the lock attempt command and the lock release command are executed.
.., 69 are exclusively subjected to token addition, search, and deletion operations among the processor elements.

When the processor element 11 executes the lock attempt instruction, the queue control mechanism 60 determines whether the token of the processor element 11 exists in the queue designated by the operand of the lock attempt instruction (here, the queue 61). Check if it is not, and if a token does not exist, insert a new token. Further, the queue control mechanism 60 checks whether or not there is a token corresponding to the processor element 11 at the head of the designated queue 61, and sets the result in the status flag of the processor element 11. The user program determines whether or not the lock has been acquired by executing a branch instruction that refers to the status flag following the lock attempt instruction.

When the processor element 11 executes the lock release instruction, the queue control mechanism 60 determines whether or not the token of the processor element 11 is present in the queue specified by the operand of the lock attempt instruction (here, the queue 61). Is checked, and if present, the token is removed from the queue 61.

The present embodiment has an advantage that a fairer exclusive control mechanism can be realized in that the order in which locks are requested is stored in a queue and locks are acquired on a first-come, first-served basis.

Referring to FIG. 4, the third type of the high-speed locking mechanism
In this embodiment, a memory area on a cache memory (shared cache) 71 in a processor is used as a lock variable without a special register or the like for a lock variable. An access arbitration mechanism 70 is provided between the cache memory 71 and each of the processor elements 11, 12, and 19, and arbitrates accesses to the same memory address. The processor includes a special test and set instruction for locking the memory area on the cache 71 in addition to the conventional lock processing instruction for the main storage memory. In the case of a conventional lock processing instruction for the main storage memory, when setting the value of the lock variable, the cache line is discharged to the main storage memory, but this special test and set instruction is the same as a normal memory access instruction. Is processed. That is, when a value is set to the lock variable, the cache line is not discharged to the main storage memory. Therefore, as long as the lock variable is not evicted from the cache to the main memory by the normal cache operation, the lock operation can be performed at the same speed as the normal memory access instruction.

[0049]

A first effect of the present invention is that a user-level interrupt mechanism without passing through an operating system can be realized. As a result, overhead for thread switching is reduced, and multi-thread execution with smaller granularity than before becomes possible.

A second effect of the present invention is that exclusive control between processor elements can be realized without accessing a main storage memory having a relatively slow response speed. This reduces overhead related to thread management and communication between threads, and enables multi-thread execution with smaller granularity than before.

Due to these low overhead effects, the application field of the shared memory multiprocessor computer is expanded, and the performance can be improved by multithread execution even for a program with a large granularity and little parallelism.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a configuration example of a computer on which the present invention is implemented.

FIG. 2 is a diagram showing a first embodiment of the present invention.

FIG. 3 is a diagram showing a second embodiment of the high-speed lock mechanism according to the present invention.

FIG. 4 is a view showing a third embodiment of the high-speed lock mechanism according to the present invention.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Processor 2 Main storage memory 11-19 Processor element 20 User handler register 21 Kernel handler register 22 Program counter 23 User save PC 24 Kernel save PC 25 Zero comparator 26 Counter 30 Lock variable set 40 Access arbitration mechanism 41 Interrupt control unit 50 Operating System 51 Kernel level interrupt handler 52 Process scheduler 60 Queue control mechanism 61-69 Queue 70 Access arbitration mechanism 71 Cache memory 100 User process 101 Thread scheduler 102-104 Thread

Claims (9)

[Claims] 1. A user handler register for holding an entry address of a user-level interrupt handler, a user save PC which is a save destination register of a program counter value, and a program counter value stored in the user save PC when an interrupt request signal is input. An interrupt control unit that performs an interrupt process for setting and setting a user handler register value to a new program counter, and performing preemption in managing a plurality of threads in a user space using the above interrupt mechanism. Characterized multi-thread computer system. 2. A down-counter whose value is decreased every clock, a zero comparator that outputs a signal when the counter value becomes zero, and a user-level interrupt process performed by a zero-match output of the zero comparator. The multi-thread computer system according to claim 1, further comprising an interrupt control unit. 3. A storage system comprising: a set of 1-bit storage devices accessible from each processor element; and a computer instruction set for operating each storage device exclusively between processor elements. A multi-threaded computer system as described. 4. A set of queue structures that can be accessed from each processor element and store tokens having identification numbers corresponding to the processor elements in the order of arrival, and tokens are exclusively added and searched between the processor elements with respect to the queue structure. 3. The multi-thread computer system according to claim 1, further comprising: a queue control mechanism for performing a delete operation; and a computer instruction set for performing an operation of adding, searching, or deleting a token to the queue structure. 5. A cache memory shared by each processor element, an access arbitration mechanism for arbitrating access to the same address in the cache memory between the processor elements, and an exclusive value operation for a memory element on the cache memory 3. The multi-threaded computer system according to claim 1, further comprising: a computer instruction set for performing the following. 6. A processor including a plurality of processor elements and a main memory shared by the plurality of processor elements, dividing one user process into a plurality of threads, and controlling a thread scheduler in the user process. In a multi-thread execution control method in a multi-thread computer system in which a plurality of threads are assigned to a plurality of processor elements under a multi-thread execution system, (a) a user process register is assigned to a user handler register in a processor element to which a thread of the user process is assigned Setting the memory address where the thread scheduler is located, and setting the time quantum value to be assigned to the thread to the counter in the processor element. (C) updating the value of the counter in the processor element at a constant period simultaneously with the start of execution of the thread, and generating a user-level interrupt when the count reaches a predetermined count value. , The current program counter value of the processor element that issued the interrupt request
C, and transferring control to a thread scheduler in the user process by setting a memory address set in a user handler register in the processor element in a program counter. . 7. An exclusive control between a plurality of threads executed by a plurality of processor elements is accessed from each processor element by a computer instruction set provided in the processor and capable of exclusively operating values between the processor elements. 7. The multi-thread execution control method according to claim 6, wherein the method is performed using a set of possible 1-bit storage devices. 8. A set of queue structures in a processor for storing exclusive control between a plurality of threads executed by a plurality of processor elements in the order of arrival of tokens having identification numbers corresponding to the processor elements. 7. The multi-thread execution control method according to claim 6, wherein the method is performed by using a set of queue structures accessible from each processor element by a computer instruction set in which a token can be exclusively added, searched, or deleted. 9. A memory on a shared cache memory that can be accessed from each processor element through an access arbitration mechanism that arbitrates access to the same address between the processor elements for exclusive control between a plurality of threads executed by the plurality of processor elements. 7. The multi-thread execution control method according to claim 6, wherein the method is performed by using a memory element which is an element and which can be accessed by a computer instruction set in which a value operation can be exclusively performed between processor elements.