A. What led to the shift towards parallel computing?
A growing need to process large amount of data quickly such as data to represent information on
the earth's weather, pollution, agriculture, and natural resources, reconstruction of 3d image of
patient’s body in preparation for surgery has risen the need for fast computers. Over past forty
years, dramatic increase of computing speed has been achieved due to the use of inherently faster
electronic components by computer manufacturers. This approach will soon come to an end
because of the simple law of physics which is light speed in vacuum 3 x 108. Whilst an electronic
device can perform 1012 operations per second it takes longer for a signal to travel between two
such devices. All the gains of speed by building superfast electronic components are lost when
the component waits to receive input from another. Why then not bring them closer to each
other? Again, physics tells us that the reduction of distance between electronic devices reaches a
point beyond which they begin to interact, thus reducing their speed and reliability. So the only
way around this problem is parallelism. This was from the book The Design and Analysis of
Parallel Algorithm by Selim G. Aki 1989.
B. In detail, classify parallel computers based on Flynn’s classification, and based on memory
Status
Flynn’s Classification:
Flynn’s classification categorizes parallel computers based on the number of instructions and
data they handle at once. The four categories are:
1. SISD (Single Instruction Single Data): A traditional sequential system where only one
instruction operates on a single piece of data at a time (e.g., older personal computers).
You may wonder how is parallelism achieved here? There is a level of parallelism in how
instructions are executed in on instruction execution cycle.
SCENARIO:
Imagine you're baking a cake in a kitchen. You are the chef, and the recipe is your
instruction. You have only one oven (your processor), and you're following the steps of
the recipe to bake a cake for one customer (the data). You can only bake one cake at a
time. This is like SISD, where a single processor executes one instruction on one piece of
data at a time.
EXAMPLE:
A personal computer from the early 2000s. These systems are rarely used in modern
times as they are inefficient for complex tasks.
• Pros: Simple, straightforward.
• Cons: Slow for complex tasks and large datasets.
2. SIMD (Single Instruction Multiple Data): One instruction operates on multiple pieces
of data at the same time. This is common in graphics processing, where the same
operation is applied to many pixels simultaneously (e.g., Graphics Processing Units or
GPUs).
SCENARIO
A factory assembles a product with multiple parts. Each part is assembled separately at
different stations.
EXAMPLE
SIMD: Graphics Processing Units (GPUs) used in gaming and AI applications. For
instance, NVIDIA's Tesla GPUs execute the same instruction on thousands of data
points, such as rendering pixels in a 3D video game.
• Pros: Fast for tasks that involve large amounts of similar data (e.g., graphics, AI).
• Cons: Limited flexibility – only works well when the same operation applies to
multiple data points.
3. MISD (Multiple Instruction Single Data): Multiple instructions operate on a single data
element, a rarely used system because it doesn’t have many practical applications.
SCENARIO
Imagine a security checkpoint where a single piece of luggage (the data) passes through
multiple inspection stations (processors). Each station checks for a different type of
threat: one looks for metallic items, another for explosive residue, another for prohibited
items, etc. Each inspection process is an instruction applied to the same piece of
luggage. This resembles MISD, where different instructions are applied to a single data
stream.
EXAMPLE
They are found in fault-tolerant systems where reliability is critical. One example is in
redundant processing used in space shuttles or certain aircraft control systems, such as
the Space Shuttle's redundant computer systems, which execute multiple algorithms on
the same input data to ensure safety and correctness. This helps cross-verify the results,
so if one algorithm fails or returns an anomaly, others can provide consistent results to
maintain safe operations.
4. MIMD (Multiple Instruction Multiple Data): Different instructions operate on
different pieces of data. This is the most flexible and common classification used today,
particularly in multi-core processors, where each core can execute a different task on
different data simultaneously (e.g., modern multi-core CPUs).
SCENARIO
A call center handles customer queries. Each operator has a unique task based on the
customer’s issue (e.g., tech support, billing, general inquiries).
EXAMPLE
MIMD: Multi-core processors in modern computers, like Intel or AMD processors.
Each core can run different tasks at the same time. For instance, one core may run a web
browser, while another runs an application, and another performs background tasks.
• Pros: Very flexible, great for general-purpose tasks.
• Cons: Can become inefficient if not properly managed because of the need for
synchronization.
Based on Memory Status:
Memory status classification divides parallel systems based on how they manage memory:
1. Shared Memory Systems: All processors share the same memory. This makes it easier
for processors to communicate, but can lead to issues with synchronization, where
multiple processors might try to access or modify the same data at once. Examples
include multi-core processors in computers where all cores share the same memory
pool.
SCENARIO
Imagine an office with a shared whiteboard. Employees (processors) write on and read
from the board. Any update to the board is instantly visible to everyone. This setup is
similar to shared memory systems, where all processors have access to a common
memory space. A practical example is multi-core processors in personal computers
where all cores access the same RAM.
EXAMPLE
Intel multi-core processors where multiple cores share the same memory space. These
are common in home computers or servers.
• Pros: Simple to implement and manage when there are fewer processors.
• Cons: Performance can degrade when many processors are involved due to
synchronization problems.
2. Distributed Memory Systems: Each processor has its own local memory, and
processors communicate by passing messages to each other. While this makes the system
more scalable, it can be more complicated to manage synchronization. Examples include
supercomputers or cloud computing systems where each processor in a cluster operates
independently and communicates via a network.
SCENARIO
Imagine a team of cooks in different kitchens working on a large catering order. Each
cook has their own ingredients and tools (memory) and works on separate dishes (tasks).
They communicate by phone or messages to coordinate, like saying when each dish will
be ready. This setup mimics distributed memory systems, where each processor has its
own local memory and communicates with others over a network.
EXAMPLE
Supercomputers like the IBM Blue Gene or cloud systems such as Amazon Web
Services (AWS), where each processor in a cluster works independently and
communicates via a network.
• Pros: Highly scalable, good for very large tasks.
• Cons: More complex to manage and slower communication between processors.
Flynn’s Classification categorizes computer architectures based on how multiple instruction
streams and data streams are handled by the system, while memory classification focuses on how
memory is organized and accessed in a system. These concepts overlap in that both deal with how
processors interact with data:
• SIMD (Single Instruction, Multiple Data) involves one instruction applied to multiple
data elements, often requiring a shared memory system for efficient data handling.
• MIMD (Multiple Instruction, Multiple Data) typically uses distributed memory
systems, where each processor has its own memory.
Thus, memory classification ties into Flynn’s types based on whether memory is shared (like
SIMD) or distributed (like MIMD).
C. Examples of real parallel systems used today Real-world parallel systems include:
Supercomputers like IBM’s Summit, which uses thousands of processors to run complex
simulations for scientific research and climate modeling.
Imagine a huge team of scientists working on a big project, where each person is solving a
small part of the puzzle. The Summit supercomputer does something similar by using
thousands of processors (like mini-scientists) working at the same time on complex
calculations to speed up research and predictions, such as weather forecasting.
supercomputers often employ a combination of SIMD and MIMD (Multiple Instruction,
Multiple Data) for different types of tasks.
Cloud computing platforms like Amazon Web Services (AWS) and Google Cloud,
where parallel processing capabilities are used to handle massive datasets and run
distributed applications.
Think of cloud computing as a virtual office with many workers (servers) in different
locations. They can access and process huge amounts of data simultaneously, making it
possible for businesses and apps to run efficiently without being limited to just one
computer. Cloud computing primarily uses MIMD (Multiple Instruction, Multiple Data).
Graphics Processing Units (GPUs) used in fields like gaming, AI, and deep learning,
where multiple cores work in parallel to process visual or computational tasks. A GPU is
like a team of artists working on a painting. Each artist (core) works on a small part of the
image at the same time. In the case of a GPU, it's designed for tasks like rendering video
games, AI, or deep learning, where many small calculations need to be done quickly and
in parallel, making it perfect for visual tasks and data-heavy processes. GPUs primarily use
SIMD (Single Instruction, Multiple Data).
d. Research on parallel computational models, their features and complexity
1. Shared memory model.
In this model the underlying hardware is assumed to be a collection of processors
each with access to the same shared memory. Here the processors can synchronize
with each other through shared variables. Example; In an office in it is like writing
the value on the whiteboard so that everyone in the office can read or modify it.
The standard view of parallelism in shared memory is called fork/join.
When a program begins to execute a master thread is created and execute a
sequential portion of algorithm. At the point where parallel operation is required,
the master thread activates additional threads that work concurrent with the master
thread. At the end of the execution the additional threads die or are suspended and
the flow of control returns to the master thread.
1.1 Features of the model
1. Each processor has equal chance of read and right in the shared memory.
2. Synchronization of the processor happens through shared variables
3. On execution, the main thread awakens additional threads for parallelism
4. Additional threads are terminated at the end of parallelism. Their life time
is not to the end of the program
5. There is incremental parallelization, the process of transforming sequential
program into parallel program one block of code at a time.
Notice: The program must indicate parallelism the system doesn’t automatically detect parallelism
Key feature of this model is incremental parallelization where by it gives you the ability to profile
the execution of sequential program, sort the program blocks according to how much time they
consume and stop when the efforts needed for further improvements are not warranted.
COMPLEXITY
Time Complexity.
Since in this module parallelization depends on how the program is written, that is the ability of
the thread to activate the additional threads in program execution, then time complexity depends
on the algorithm of the program.
Space Complexity.
Space complexity is determined by the following factors Program Data O(n), Thread local data O
(p.k) where k is the memory size for each thread and Synchronization overhead such as locks or
barriers.
With an assumption that there is an average number of threads in an algorithm and the frequency
of locking or barriers is average for synchronization the Program Data dominates the overall space
complexity.
2. Message passing model
In this model, the underlying hardware is assumed to be collection of processors
each with its own local memory. This means the processor has direct access only
to the data and instructions stored in its local memory. However, interconnection
network supports communication amongst the processors.
Processor A may send message with some of its local data values to Processor B
hence giving indirect access of the local data values to processor B.
Here the user identifies the number of concurrent processes when the program
begins and typically the number of active processes remains constant throughout in
the execution of the program.
Processes in this model pass message both to communicate and synchronize with
each other.
2.1 Features of the model
1. Each processor has its own local data and instruction memory.
2. There is an interconnection network that supports communication between
processors.
3. The message sent between one processor and the other serves
communication and synchronization purposes.
2.2 Time complexity
Time complexity here depends on algorithm used on each processor. For example,
sorting N elements locally on a processor has a time complexity of O(NlogN)
2.3 Space complexity
Key components to determine space complexity
1. Message Data
• Space is required to store the messages in transit (as discussed earlier).
For N messages of size S, this requires O(N⋅S).
2. Instructional Data (Processing Overhead)
• The process executing the instructions also uses memory for:
• Program variables (e.g., local variables for computations).
• Function call stacks (for nested operations or recursion).
• Intermediate results (e.g., in algorithms like sorting or merging
data).
The memory required for this depends on the complexity of the computation. For
example:
• Simple tasks like adding numbers might require O(1) additional space.
• Complex tasks like sorting might require O(MlogM), where M is the
size of the data being processed.
3. Combined Space for Messages and Instructions
• If messages are processed immediately upon receipt (streaming), the
space complexity is dominated by the message size and the instructions:
O(S+P)
where SS is the message size and PP is the processing overhead.
• If messages are buffered before processing, the space complexity
increases to include both the buffer and the instructions: O(N⋅S+P)
where N is the number of buffered messages.
Since what we are looking is to maximize computation and minimizing
communication therefore the space complexity will be O(P)