CS Elective 3 : Week 2

Review of Parallel Computing

Parallel Computing means breaking computational problem into smaller parts and allowing multiple processing units to work on those parts at the same time.

Task Decomposition

Breaking a large problem into smaller task than can be potentially executed independently.

Concurrency

Means that multiple task are making progress during the same period , but they don't necessarily executed at the same instant.

Parallelism

Means that Multiple Task are Actually executing at the same time using multiple processing unit.

Key Idea

Divide the work > Assign the work > Execute simultaneously> Combine the results.

Data Parallelism

Means applying the same operation to different portions of data simultaneously.

The Operation is the same but the data is different.

Important point (Concurrency vs Parallelism)

concurrency doesn't not always mean parallelism,a program can be concurrent without being parallel.

Difference between concurrency vs parallelism

Concurrency : is a person alternating between one task to another.

Parallelism : A group of people each doing their own set of task.

Task Parallelism

Means Different Processing units perform different task at the same time

Data Parallelism Vs. Task parallelism

Data Parallelism = Same task, Different Data.

Task Parallelism= Different tasks, Potentially same or related data.

A.K.A Different cores perform different jobs

Flynn’s Taxonomy

Is a classification system in computer architecture based on the number of :

•Instruction streams

•Data Streams

Introduce by Michael J. Flynn

Four Major Categories of Flynn's Taxonomy

•SISD

•SIMD

•MISD

•MIMD

SISD (Single Instruction, Single Data)

The Traditional Sequential computing Model,

One processor Execute one Instruction stream on one data stream

SIMD (Single Instruction, Multiple Data )

One instruction is applied to Multiple pieces of data Simultaneously

SIMD In Gaming

Games perform huge numbers of calculations Involving :

•Coordinates

•Colors

•Physics

•Vectors

•Transformation

This processing Style Can help process multiple values Efficiently

MIMD (Multiple Instruction, Multiple Data)

Common in modern Multi-Core and multiprocessor Systems. Different processors can execute different structions on different data.

MISD (Multiple Instruction, Single Data )

Multiple Instructions Operate on the same data stream.

This is a less common Architecture in general-purpose computing.

Multi-Core Processor

Contains multiple processing core inside a single CPU

Ex. Dual core, Quad Core, Octa Core

Dependency (parallelism + Dependency)

Occurs when one task need the result of another task before it can continue.

ex. online shopping

Graphics processing Unit (GPU)

Originally designed primarily for graphics processing. But GPUs are excellent at performing large number of similar computations.