Scribd
Upload
60 views16 pages

ParallelProcessing 1 Intro-1

The document discusses parallel processing and distributed systems. It introduces parallel processing as an approach to solve problems that cannot be solved in a reasonable time using sequential processing on a single CPU. Parallel processing uses multiple processors working simultaneously to solve problems. There are different types of parallelism including pipeline parallelism, data parallelism, and control parallelism. Data parallelism applies the same operation to different data elements simultaneously and generally provides better scalability than other approaches as the problem and number of processors increase.

Uploaded by

Hoai Bao
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
60 views16 pages

ParallelProcessing 1 Intro-1

The document discusses parallel processing and distributed systems. It introduces parallel processing as an approach to solve problems that cannot be solved in a reasonable time using sequential processing on a single CPU. Parallel processing uses multiple processors working simultaneously to solve problems. There are different types of parallelism including pipeline parallelism, data parallelism, and control parallelism. Data parallelism applies the same operation to different data elements simultaneously and generally provides better scalability than other approaches as the problem and number of processors increase.

Uploaded by

Hoai Bao
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

Parallel Processing & Distributed Systems

Thoai Nam

Chapter 1: Introduction

Introduction
What is parallel processing? Why do we use parallel processing?

Applications Parallelism

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Sequential Processing

1 CPU Simple Big problems???

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Application Demands

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

New Approach

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Grand Challenge Problems

A grand challenge problem is one that cannot be solved in a reasonable amount of time with todays computers Ex:
Modeling large DNA structures Global weather forecasting Modeling motion of astronomical bodies

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Solutions

Power processor
50 Hz -> 100 Hz -> 1 GHz -> 4 Ghz -> ... -> Upper bound?

Smart worker
Better algorithms

Parallel processing

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

N-body

The N2 algorithm:
N bodies N-1 forces to calculate for each bodies N2 calculations in total After the new positions of the bodies are determined, the calculations must be repeated 107 stars and so 1014 calculations have to be repeated Each calculation could be done in 1s (10-6s) It would take 10 years for one iteration But it only takes 1 day for one iteration with 3650 processors
Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

A galaxy:

Parallel Processing Terminology


Parallel processing Parallel computer


Multi-processor computer capable of parallel processing

Throughput:
The throughput of a device is the number of results it produces per unit time.

Speedup S = Time(the most efficient sequential algorithm) / Time(parallel


algorithm)

Parallelism:
Pipeline Data parallelism Control parallelism
Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Pipeline

A number of steps called segments or stages The output of one segment is the input of other segment
Stage 1

Stage 2

Stage 3

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Data Parallelism

Applying the same operation simultaneously to elements of a data set

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Pipeline & Data Parallelism


1. Sequential execution A B C
w2 w1

2. Pipeline

A B C

w5 w4 w3 w2 w1

3. Data Parallelism

A B C A B C A B C

w4

w1

w5

w2

w6

w3

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Pipeline & Data Parallelism


Pipeline is a special case of control parallelism T(s): Sequential execution time T(p): Pipeline execution time (with 3 stages) T(dp): Data-parallelism execution time (with 3 processors) S(p): Speedup of pipeline S(dp): Speedup of data parallelism
widget T(s) T(p) T(dp) S(p) S(dp) 1 3 3 3 1 1 2 6 4 3 1+1/2 2 3 9 5 3 1+4/5 3 4 12 6 6 2 2 5 15 7 6 2+1/7 2+1/2 6 18 8 6 2+1/4 3 7 21 9 9 2+1/3 2+1/3 8 24 10 9 2+2/5 2+2/3 9 27 11 9 2+5/11 3 10 30 12 12 2+1/2 2+1/2

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Pipeline & Data Parallelism


3.5 3 2.5 2 1.5 1 0.5 0 1 2 3 4 5 6 7 8 9 10 S(p) S(dp)

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Control Parallelism

Applying different operations to different data elements simultaneously

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

Scalability

An algorithm is scalable if the level of parallelism increases at least linearly with the problem size. An architecture is scalable if it continues to yield the same performance per processor, albeit used in large problem size, as the number of processors increases. Data-parallelism algorithms are more scalable than controlparallelism algorithms

Khoa Cong Nghe Thong Tin ai Hoc Bach Khoa Tp.HCM

You might also like