What are Multithreaded Algorithms?

An algorithm that executes a single instruction in a uniprocessor system is called a serial algorithm. In the case of a multiprocessor computer system, a multiprocessor computer can execute multiple instructions in parallel. A multithreaded algorithm is an algorithm that enables multiple instances of the code to be executed concurrently.
Multithreading is a concept that allows the CPU to execute threads independently while sharing similar resources. It is an important CPU feature that works on the process. Thread is a sequence of instructions that executes in parallel with other threads. Because of multithreading, multiple tasks can be performed within a single process, making the execution faster.

Static and Dynamic Multithreading

The programmer can use static threading to create an abstraction of virtual processors that can be managed explicitly. Because the programmer must define how many processors to utilize at each step in advance, it is "static." With regards to changing situations, this might be challenging and rigid.
Rather than manually managing threads, a dynamic multithreading approach can be used to express parallelism opportunities. A concurrency platform handles the mapping of these chances to actual static threads.

Dynamic multithreading

It refers to an architecture that allows a single application to be executed in several threads dynamically. At procedure and loop borders, hardware creates threads implemented speculatively on a simultaneous multithreading pipeline. It is efficient for multiple processing. DMT is used in dynamic multithreading (multiple dynamic threads). The DMT processor uses a simultaneous multithreading pipeline to increase CPU usage, although the threads are generated dynamically from the same software. Even though the DMT processor is based on dynamic simultaneous multiple threads, the execution mechanism is heavily influenced by multi-scalar architecture. The multi-scalar architecture implements mechanisms for various control flows to minimize instruction fetch stalls and leverage control independence.

In DMT, program execution begins with a single thread. As instructions are decoded, hardware separates the program into chunks at loop and procedure borders, then executed as separate threads in the SMT pipeline. The thread order in the program and the start PC of each thread are kept in control logic. When a thread's PC reaches the start of the next thread in the order list, it stops acquiring instructions. The next thread in the ordered list is regarded as unpredicted and crashed if an earlier thread never reaches the starting PC of the next thread in the ordered list. Threads search for parallelism far into the program. Data mispredictions are widespread since the threads do not wait for their inputs.

DMT microarchitecture contains two pipelines: execution pipeline and recovery pipeline. 

Concurrency Constructs

The pseudocode for multithreaded algorithms uses the following three keywords that mirror contemporary parallel computing practice:

• Parallel: To indicate that each iteration can be done in parallel. Use it in loop constructs like for, while and so forth.
• Spawn: Enables parallel execution of newly created process (child process) and the process (parent process) which created it.
• Sync: It enables a process to wait until all active threads created by it finish their execution.

These keywords identify possibilities of parallelism without influencing whether (or not) the sequential program derived by eliminating them is correct. In other words, the program can be identified as a single-threaded program if the parallelism-related keywords are ignored.

Parallel Fibonacci

Take, for example, a slow algorithm and make it parallel. (This is only an example; there are much better techniques to compute Fibonacci numbers using dynamic programming.) Fibonacci numbers are defined as follows:

$$\begin{gathered} F_0=0 \\ {F}_1=1 \\ {F}_i=F_{i-1}+F_{i-2} ,for i\ge 2 \end{gathered}$$

Based on the preceding concept, below is a recursive non-parallel algorithm for computing Fibonacci numbers, along with its recursion tree:

FibonacciSeries(n)if (n<=1){return n}else{a = FibonacciSaries(n-1)b = FibonacciSeries(n-2)return a+b;}

$T\left(n\right)=T\left(n-1\right)+T\left(n-2\right)+\theta \left(1\right)$ is the recurrence relation of the Fibonacci series, which has the solution$T\left(n\right)=\theta \left(F_n\right)$. This is inefficient since it rises exponentially$n$. (A simple iterative algorithm is far superior.)

Given that the recursive calls are independent of one another, let's look at how performing the two recursive calls in parallel can increase performance. This will serve as a demonstration of the concurrency keywords as well as a case study for analysis:

ParallelFib(n)if (n<=1){return n}else{a = spawn ParallelFib(n-1)b = ParallelFib(n-2)syncreturn a+b}

It is worth noting that without the parallelism-related keywords, the program is identical to the serial program above.

Modelling multithreaded application

To begin with, a formal model is needed for parallel calculations.

A multithreaded computation can be represented as a DAG (Directed Acyclic Graph) G = (V, E):

• Instructions are represented by the vertices V. To make the graph easier to understand, each vertex can represent a sequence of non-parallel instructions that will all be treated equally in terms of parallelism.
• Dependencies between instructions are represented by edges E(u, v) which signifies u must execute before v. (Edge is classified in a variety of ways, as detailed below.)
• There exists sequential execution, if G has a directed path from u to v. Otherwise, they are parallel.
• If a node has numerous descendants, all except one must have sprouted. When a node has many predecessors, they all join at the same time at a sync statement.

Consider an ideal parallel computer with sequentially consistent memory, which means that the instructions are executed sequentially in some full order consistent with the thread orderings (i.e., consistent with the partial ordering of the computation DAG).

Visualizing the model

The DAG for the computation of P-FIB(4) can be illustrated as follows:

P-FIB(n)if (n<=1){return n}else{a = spawn P-FIB(n-1)b = P-FIB(n-2)syncreturn a+b}

Vertices are visualized as circles in the figure. The rounded rectangles cannot be considered as part of the formal model. They are used for organizing the visualization by grouping all of the vertices for a particular call.

The background colours used for the vertices signify the associated code: black denotes lines 1-3, grey denotes lines 4–6, and white denotes lines 5–6.

Edges are categorized and visualized as follows:

• Continuation Edges - Used to denote that v is the successor u in the sequential execution.
• Call Edges - Used to indicate that v is a sub procedure of u. In this example, these edges branch out of the grey circles.
• Spawn Edges - Used to illustrate that u spawned v in parallel. In the graph, these edges come out of the black circles.
• Return edges - These edges point upwards to indicate the next vertex to be executed after returning from a normal procedure call or after parallel spawning at a sync point. In the graph, these edges return to the white circles.

Advantages of Multithreading

The various advantages of multithreading are as follows:

• Used to create a responsive UI.
• Helps in efficient processor utilization.
• Improves the performance of the application.

Disadvantages of Multithreading

The various disadvantages of multithreading are as follows:

• Multithreading can degrade performance on a single processor or single-core machine due to the overhead associated with context switching. Assume that a task takes a certain amount of time to accomplish on a single-core system. Suppose multithreaded algorithms are used to complete the task, in that case, the task time is divided evenly among the number of threads, and switching from one thread to another is automatically performed, which takes time. As a result, the overall time spent on the work will be longer than the time spent on the single thread.
• To perform the same goal, one has to write more lines of code.
• Writing, understanding, debugging and maintaining multithreaded applications is complex and cumbersome.

Context and Applications

This topic is significant in the professional exams for graduate and postgraduate courses, especially:

• Bachelors in Computer Applications
• Bachelors in Information Technology
• Masters in Computational Data Science
• Masters in Computer Applications

Related Concepts

• Serial Algorithms
• Multithreaded programming
• Fibonacci Algorithm
• Parallel Computation
• Algorithm for Distributed Computing

Practice Problems

Q1. Multithreading is related to:

1. Recurrence execution
2. Crosscurrent execution
3. Concurrent execution
4. None of the above

Correct Option: (C)

Explanation:-Concurrent execution is when multiple tasks are executed concurrently. It can be achieved with the help of threads.

Q2. .……… is a single sequential flow of control within a program.

1. Task
2. Thread
3. Process
4. Structure

Correct Option: (B)

Explanation:-Thread is a light process and executes a single task within a process.

Q3. The algorithm which executes a single instruction at a time is called ………………. for uniprocessor computers.

1. Serial algorithm
2. Multithread algorithm
3. Concurrent algorithm
4. Simultaneous algorithm

Correct Option: (A)

Explanation:- Single algorithm, also known as the one-pass algorithm, is a serial algorithm. This algorithm reads the input exactly once.

Q4. A thread is also called as _________________.

1. Data segment process
2. Heavyweight process
3. Overhead process
4. Lightweight process

Correct Option: (D)

Explanation:- Thread is also known as a lightweight process. It executes multiple tasks at the same time within a process.

Q5. How many types of threads are there in single-threaded process?

1. 2
2. 4
3. 1
4. 5

Correct Option: (C)

Explanation:- From the figure of single-threaded execution, it is clear that a single-threaded process consists of only one thread.