Reference Document: A 1.pdf
Q1
Formula
i
Increase the number of processors from 1 to 8 and parallelise 40% of the code.
ii.
Increase the number of processors from 1 to 4 and parallelise 70% of the code
Upgrade # ii has a better speed up as compared to the other one
Q2
Assume a sequential program S has an execution time of 400 seconds. Further, assume that Sp is a parallel variant of S. After an experimental evaluation over different number of processors, the following running times were achieved
a)
b)
Q3
Explain approaches used for multithreading in the SISD architecture. Use diagrams where required.
Multithreading is a technique used to achieve parallelism by executing multiple threads concurrently. This technique can also be applied in Single Instruction stream Single Data stream (SISD) architecture by primarily running multiple threads on the same core concurrently using different implementations.
Implicit Multithreading
In Implicit multithreading, hardware automatically switches between multiple threads without requiring explicit instructions from the programmer or compiler. These threads are extracted from a single sequential program and the processor hardware itself manages the concurrent execution.
Explicit Multithreading
Explicit multithreading involves the programmer or compiler specifying how threads should be executed. Thus, giving more control to them over thread management. Different explicit threads are used for concurrent execution either by interleaving instructions or parallel execution on parallel pipelines.
The approaches to implement explicit multithreading are as follow:
Interleaved Multithreading
Interleaved Multithreading AKA fine-grained multithreading, is a technique where the CPU switches between multiple threads on every clock cycle. This means that instructions from different threads are interleaved and multiple instructions from different threads are executed in a single cycle.
Block Multithreading
Block Multithreading AKA coarse-grained multithreading, divides the processor’s pipeline into blocks and assigns each block to a different thread. It switches between entire blocks of instructions from different threads. Thus stalling events such as cache miss when fetching from memory produces a switch to a different thread.
Simultaneous Multithreading
A technique where a single physical CPU core appears as multiple logical cores to the operating system. It allows the CPU to execute instructions from multiple threads in parallel within the same core. An example would be Intel’s Hyper Threading Technology.
Q4
i
4x4 two-dimensional mesh with wraparound links
(a) Cost
(b) Diameter
(c) Bisection Width
(d) Arc Connectivity
ii
4x4 two-dimensional mesh with no wraparound links
(a) Cost
(b) Diameter
(c) Bisection Width
(d) Arc Connectivity
iii
Four-dimensional hypercube (size=16 Nodes)
(a) Cost
(b) Diameter
(c) Bisection Width
(d) Arc Connectivity
iv
A complete binary tree of 3 levels as shown in the image below:
