What is Parallel Computing?

• Traditionally, software has been written for serial computation:

​

• To be run on a single computer having a single Central Processing Unit (CPU);

​

• A problem is broken into a discrete series of instructions.

​

• Instructions are executed one after another.

​

• Only one instruction may execute at any moment in time.

​

1

2

​

• In the simplest sense, parallel computing is the simultaneous use of multiple compute resources to solve a computational problem:
• To be run using multiple CPUs

​

• A problem is broken into discrete parts that can be solved concurrently

​

• Each part is further broken down to a series of instructions

​

• Instructions from each part execute simultaneously on different CPUs

​

3

4

Why Use Parallel Computing?�

5

• Save time and/or money:
• Solve larger problem
• Provide concurrency

Parallel Computer Memory Architectures�

6

Shared memory (UMA)

Shared memory (NUMA)

Continued…

7

Distributed Memory

8

Hybrid Distributed Shared Memory

Taxonomy of Architectures

• Simple classification by Flynn:

(No. of instruction and data streams)

• SISD - conventional
• SIMD - data parallel, vector computing (type of parallel computer)
• MISD - systolic arrays (Pipeline Archi)
• MIMD - very general, multiple approaches, Shared memory multiprocessors, Distributed Shared Memory
• Current focus is on MIMD model, using general purpose processors or multicomputers.

​

9

Single Instruction, Multiple Data (SIMD):

10

Single Instruction: All processing units execute the same instruction at any given clock cycle Multiple Data: Each processing unit can operate on a different data element

Multiple Instruction, Single Data (MISD):

11

Multiple Instruction: Each processing unit operates on the data independently via separate instruction streams.

Single Data: A single data stream is fed into multiple processing units.

Multiple Instruction, Multiple Data (MIMD):

12

​

Multiple Instruction: Every processor may be executing a different instruction stream

Multiple Data: Every processor may be working with a different data stream

Main HPC Architectures..1a

• SISD - mainframes, workstations, PCs.
• SIMD Shared Memory - Vector machines, Cray...
• MIMD Shared Memory - Sequent, KSR, Tera, SGI, SUN.
• SIMD Distributed Memory - DAP, TMC CM-2...
• MIMD Distributed Memory - Cray T3D, Intel, Transputers, TMC CM-5, plus recent workstation clusters (IBM SP2, DEC, Sun, HP).

13

Cluster Computer Architecture

14

Definition of cluster computing

• Collection of computers on a network that can function as a single computing resource through the use of additional system management software

​

• Can any group of Linux machines dedicated to a single purpose can be called a cluster?

​

• Dedicated/non-dedicated, homogeneous/non-homogeneous, packed/geographically distributed???

​

15

Clusters Classification

Based on Focus (in Market)

• High performance (HP) clusters
• Grand challenging applications
• High availability (HA) clusters
• Mission critical applications

16

• Based on Workstation/PC Ownership
• Dedicated clusters
• Non-dedicated clusters
• Adaptive parallel computing
• Can be used for CPU cycle stealing

​

17

• Non-dedicated clusters:

network of workstations (NOW)

use spare computation cycles of nodes

background job distribution

individual owners of workstations

• Dedicated clusters:

joint ownership

dedicated nodes

parallel computing

​

18

• Based on Node Architecture
• Clusters of PCs (CoPs)
• Clusters of Workstations (COWs)
• Clusters of SMPs (CLUMPs)

​

19

Relationship among Middleware Modules

20

What is filesystem????

• System that permanently stores data- that usually layered on top of a lower-level physical storage medium.
• Divided into logical units called “files”

21

Parallelization Idea

• Parallelization is “easy” if processing can be cleanly split into n units:

​

22

Worker

​

Wk1

Wk2

Wk3

Wk1

Wk2

Wk3

Spawn worker threads

Thread

​

Thread

​

Thread

​

Master thread

• Multiple threads must communicate with one another, or access a shared resource.

​

• Any memory that can be used by multiple threads must have an associated synchronization system.

​

Thread 1:

void foo(){

x++;

y=x;

}

24

Thread 2:

void bar() {

y++;

x+=3;

}

Cluster configuration

• Passive standby
• Active secondary
• Separate servers
• Servers connected to disks
• Servers with share disks

​

25

Operating system design issues

• Failure management
• Load balancing
• Parallelizing computation
• Parallelizing compiler
• Parallelizing application
• Parametric computation

​

26

Two basic types of clusters

• Non-dedicated clusters:

network of workstations (NOW)

use spare computation cycles of nodes

background job distribution

individual owners of workstations

• Dedicated clusters:

joint ownership

dedicated nodes

parallel computing

27

Taxonomy of clusters

• Network of workstations (e.g. SUN)

​

• Beowulf clusters: (COTS pcs. With SAN)

​

• Cluster farms: existing PCs on a LAN which when idle can perform work.

​

• Supercluster: cluster of clusters (within a campus)

28

NOWs

29

Beowulf clusters

30

31

• 1000 nodes Beowulf Cluster System
• Used for genetic algorithm research by John Coza, Stanford University