Multithreading

Multithreading

• The performance of a processor can be measured by the rate of instruction execution. It can be calculated by taking product of processor clock frequency (f_clk) in MHz and the average number of instructions executed per cycle (I_pc). Thus, it can be expressed as

MIPS rate = f_clk × I_pc.

• Hence, we can say that the performance of the processor can be increased by increasing its clock frequency and / or by increasing number of instructions executed per cycle.

• The I_pc can be increased by using instruction pipeline. It can be further increased in a superscalar architecture by using multiple parallel instruction pipelines.

• When pipelining is used, it is essential to maximize the utilization of each pipeline stage to improve throughput. It can be accomplished by executing some instructions in a different order rather than executing them sequentially as they occur in the instruction stream and initiating execution of some instructions eventhough it is not required. However, this approach needs complex mechanisms in the design. The designer can not cross the limitations of circuit complexity and power consumption. Therefore, an another approach is used, called multithreading.

• In multithreading, the instruction stream is divided into several smaller streams, called threads, such that the threads can be executed in parallel. Here, a high degree of instruction‒level parallism can be achieved without increasing circuit complexity or power consumption.

Implicit and Explicit Multithreading

Let us discuss some important terms used in multithreaded processors.

■ Process : A process is an instance of a program running on a computer. The process image is the collection of program data, stack and attributes that define the process. The process image is stored at a virtual address space. Two important characteristics of a fer process are discussed below.

■ Resource ownership : A process may get control of resources such as main memory, I/O channels, I/O devices and files from time to time.

■ Scheduling / execution : A process execution takes places through one or more programs. This execution may interleaved with that of other processes. An operating system decides an execution state of each process such as running, ready, dispatching priority.

Process switch : A process switch is an operation that switches the process or control from one process to another. It first saves all the process control data, registers and other information and then replaces them with the process information for the second.

Thread : A thread includes the program counter, stack pointer and its own area for a stack. It executes sequentially and can be interrupted to transfer control to an another thread.

Thread switch : A thread switch is an operation that switches the processor control from one thread to another within the same process. This is cheaper than a process switch.

Comparison of process switch and thread switch

Process switch

1. It is an operation that switches the process or control from one process to another.

2. When the processor control is transferred from one process to another, the control or ownership of resources is also transferred. So process switch is time consuming than thread switch.

3. It is much costly than a thread switch.

Thread switch

1. It is an operation that switches the processor control from one thread to another thread.

2. The multiple threads within a process share the same resources. So a thread switch is much less time consuming than a process switch.

3. It is much less costly than process switch.

Explicit Threads

■ User level threads which are visible to the application program and kernel‒level threads which are visible only to operating system, both are referred to as explicit threads.

Implicit and Explicit Multithreading

■ Implicit multithreading refers to the concurrent execution of multiple threads extracted from a single sequential program.

■ Explicit multithreading refers to the concurrent execution of instructions from different explicit threads, either by interleaving instructions from different threads on shared pipelines or by parallel execution on parallel pipelines.

Approaches to Explicit Multithreading

■ Interleaved or fine‒grained multithreading : The processor executes two or more threads at a time. It switches from one thread to another at each clock cycle. During execution, if a thread is blocked because of data dependencies or memory latencies, that thread is skipped and a ready thread is executed.

■ Blocked or coarse‒grained multithreading : The processor executes instructions of a thread sequentially and if an event (e.g. cache miss) that causes any delay occurs, it switches to another thread.

■ Simultaneous MultiThreading (SMT) : The wide superscalar instruction is executed by executing multiple threads simultaneously using multiple execution units of a superscalar processor.

■ Chip multiprocessing : The processor is replicated on a single chip and each processor executes separate threads. This approach effectively utilizes the available logic data on a chip without increasing pipeline design complexity. This is referred to as multicore. Chip multiprocessing enables simultaneous execution of instructions from different threads. The possible pipeline architectures those involve multithreading and those do not use multithreading are shown in Fig. 5.10.1. The instructions in different threads are indicated as I₁,I₂,I₃, ... and so on. Each row indicates a single clock cycle. The shaded block represents an unused execution slot in one pipeline. A no‒operation is indicated by X.

■ Single‒threaded scalar : Fig 5.10.1 (a) shows a single‒threaded scalar. Here a simple pipeline is used like in RISC and CISC machines.

Interleaved multithreaded scalar :

■ As shown in Fig. 5.10.1 (b), the pipeline stages are kept fully occupied (or close to it) by switching from one thread to another at each clock cycle. The hardware should support this switching operation.

Blocked multithreaded scalar :

■ As shown in Fig. 5.10.1 (c), the instructions of a single thread are executed successively until an event occurs that may cause delay such as cache miss. When such an event occurs, the processor switches to execute an another thread.

■ It is to be noted that in interleaved multithreading (Fig. 5.10.1 (b)), thread switching takes no time since there are no control or data dependancies between threads which simplifies pipeline design. However in block multithreading (Fig. 5.10.1 (c)), thread switching needs one clock cycle.

Fig. 5.10.1 (a) and Fig. 5.10.1 (b) and Fig. 5.10.1 (c) show variations among processors that have hardware capable for issuing four instructions per cycle. The instructions from a single thread are executed in single cycle in each case. All these cases are discussed here.

• Superscalar : As shown in Fig. 5.10.2 (a), the basic superscalar approach does not support multithreading. It provides parallelism within a processor. During some cycles, not all of the available issue slots are used; referred to as horizontal loss. When during different cycles no issue slots are used, this is referred to as vertical loss.

• Interleaved multithreading superscalar

In this approach, as many instructions as possible are issued from a single thread and delays due to thread switching are eliminated. The number of instructions issued in a cycle is limited by dependencies within thread.

• Blocked multithreaded superscalar

In this technique, instructions from only one thread are issued during a cycle and block multithreading is used.

• Very Long Instruction Word (VLIW)

The example of VLIW architecture is IA‒64. It places multiple instructions in a single word. The operations which may be executed in parallel are placed in the same word. If it is not possible to completely fill the word with instructions those are to be issued in parallel, those slots are filled with no‒operation (X).

• Interleaved multithreading VLIW

This approach provides similar efficiencies as that of interleaved multithreading on a superscalar architecture.

• Blocked multithreading VLIW

This approach provides similar efficiencies as that of blocked multithreading on a superscalar architecture.

Fig. 5.10.3 shows two more approaches to execute multiple threads.

• Simultaneous multithreading

A high degree of efficiency can be achieved using system capable of issuing number instructions at a time. Fig. 5.10.3 (a) shows a system capable of issuing 8 instructions simultaneously. All horizontal slots can be filled by a single instruction if the thread has a high degree of instruction‒level parallelism. Also, instructions from two or more threads may be issued during some cycles. Thus, the maximum number of instructions can be issued during each cycle.

• Chip multiprocessor (Multicore)

As shown in Fig. 5.10.3 (b), a chip contains four processors and each has a two-issue superscalar processor.

Review Questions

1. What is multithreading?

2. Define process, resource ownership, process switch, thread and thread switch related to multithreading?

3. Give comparison between process switch and thread switch.

4. What do you mean by implicit and explicit multithreading.

5. Discuss various approaches to explicit multithreading.

6. What is multicore?

7. Write a note on chip multiprocessing.

8. Explain the term: Hardware multithreading.

9. What is hardware multithreading? Compare and contrast Fine grained Multi-Threading and Coarse grained Multi Threading.

10. Explain in detail about hardware multithreading.

11. Explain the four principle approaches to multithreading with necessary diagrams.

12. Explain any three types of hardware multithreading.