2010. Pengajar. Materi Kuliah. Materi Kuliah #2. Komputasi Paralel. Kuliah 01: Pendahuluan

3/1/2010

Pemrosesan Paralel

Departemen Ilmu Komputer -IPB

Pemrosesan Paralel


Deskripsi

Komputasi Paralel Kuliah 01: Pendahuluan Yeni Herdiyeni http://www.cs.ipb.ac.id/~yeni/paralel Departemen Ilmu Komputer IPB Semester Genap 2010

Pemrosesan Paralel


• Membahas kebutuhan dan klasifikasi mesin paralel (SISD, SIMD, MISD, MIMD, SPMD), komunikasi antar prosesor, memori persekutuan (shared memory), pengiriman pesan (message passing), jaringan interkoneksi (interconnection network), Desain algoritma paralel, efisiensi dan percepatan pemrosesan paralel, dan contoh aplikasi pemprosesan paralel. • Perangkat lunak yang digunakan : MPI (Message Passing Interface)

Pemrosesan Paralel


Materi Kuliah

Pengajar

1. Pendahuluan 2. Definisi dan motivasi pemrosesan paralel 3. Arsitektur system, Shared memory multiprocessor system, Message passing multicomputer distributed, Shared memory dan klasifikasi memori persekutuan MIMD dan SIMD 4. Topologi Network 5. Paradigma pengiriman pesan dengan menggunakan MPI 6. Prinsip-prinsip Desain Algoritme Paralel 7. Analisis kinerja Pemrosesan paralel 8. UTS

• Dr. Yeni Herdiyeni, S.Si, M.Komp • Hendra Rahmawan, S.Si, M.T • Endang Purnama, S.Si, M.Komp Komponen Penilaian • UTS • UAS • Tugas • Quiz • Project

Pemrosesan Paralel


Materi Kuliah #2 9. Pemrograman Paralel : Distributed Memory 10. Pemrograman Paralel 11. Tinjauan ulang critical section dengan menggunakan Pthread, siknronisasi dengan Semaphore, Implementasi Semaphore dilingkungan MPI 12. Sorting 13. Dense Matrix Algorithm 14. Aplikasi pemrosesan (shared memory): problema produsen-konsumen, problema writer reader, problema dining philosophy 15. Presentasi/diskusi proyek 16. UAS

Pemrosesan Paralel


Buku Ajar • Grama, Ananth., Gupta, Anshul., Karypis, George., Kumar, Vipin. 2003. Introduction to Parallel Computing. Second Edition. Pearson Addision Wesley. • Quinn, Michael J. 2003. Parallel Programming in C with MPI and OpenMP . International Edition, McGraw-Hill. • Wilkinson, Barry & Allen, Michael. 2005. Parallel Programming . 2nd Edition,Pearson Educational International. • Jordan, Harry F., Alaghband Gita. 2003. Fundamentals of Parallel Processing. Prentice Hall.

1

3/1/2010

Pemrosesan Paralel

Pemrosesan Paralel



Motivation : Classical Science

Modern Scientific Method

Nature

Nature

Observation

Observation

Physical Experimentation

Numerical Simulation

Theory

Physical Experimentation

Pemrosesan Paralel

Pemrosesan Paralel



Modern Parallel Architectures

What is Parallel and Distributed computing?

• Two basic architectural scheme:

– Solving a single problem faster using multiple CPUs

Distributed Memory

– Parallel = Shared Memory among all CPUs – Distributed = Local Memory/CPU – Common Issues: Partition, Synchronization, Dependencies

Shared Memory

• Now most computers have a mixed architecture

Pemrosesan Paralel

Pemrosesan Paralel



Shared Memory

Distributed Memory CPU

CPU

node

memory

memory memory

NETWORK CPU memory

memory

CPU

CPU

CPU

CPU

CPU

CPU

CPU

node

node

CPU

node

node

memory

memory node

Theory

2

3/1/2010

Pemrosesan Paralel

Pemrosesan Paralel



Seeking Concurrency • • • • •

Interconnection Networks • Uses of interconnection networks

Data dependence graphs Data parallelism Functional parallelism Task Parallelism Pipelining

– Connect processors to shared memory – Connect processors to each other

• Interconnection media types – Shared medium – Switched medium

Pemrosesan Paralel

Pemrosesan Paralel



Most Common Networks

switched

Real Shared

Cube, hypercube, n-cube

switch

Memory banks

Torus in 1,2,...,N Dim

Fat Tree System Bus

CPU

CPU

CPU

Pemrosesan Paralel

CPU

CPU

Pemrosesan Paralel



Virtual Shared

Mixed Architectures

Network memory memory

HUB

HUB

HUB

HUB

HUB

HUB

CPU

CPU

CPU

CPU node

node

CPU node

CPU node

CPU node

CPU node

CPU node

CPU

memory

CPU

CPU node

NETWORK

node

3

3/1/2010

Pemrosesan Paralel

Pemrosesan Paralel



General MPI Program Structure

The Message-Passing Programming Paradigm

MPI include file

variable declarations

Initialize MPI environment

Do work and make message passing calls

#include <mpi.h> void main (int argc, char *argv[]) { int np, rank, ierr; ierr = MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD,&rank); MPI_Comm_size(MPI_COMM_WORLD,&np); /* Do Some Works */ ierr = MPI_Finalize(); }

Terminate MPI Environment

Pemrosesan Paralel

Pemrosesan Paralel



Message

Foster’s Design Methodology • • • •

Partitioning Communication Agglomeration Mapping

Pemrosesan Paralel

Pemrosesan Paralel


Foster’s Methodology

Example program (1) Calculating the value of

Partitioning Problem


Communication

by:

1

4 dx 1 x2 0

Mapping

Agglomeration

24

4

3/1/2010

OK! Pemrosesan Paralel

OK!

Pemrosesan Paralel



Sequential Algorithm =3.141... Start calculation!

1

0

4

1

2 5 9

3

2

1

1

3

4

3

1

2

4

13 17 19 4

3

0

2

0

1

11 3

13 14 3 9 =

Calculated by process 301 Calculated Calculatedby byprocess process2

OK!

2

OK! 25

Pemrosesan Paralel

Pemrosesan Paralel



Phases of Parallel Algorithm

Contoh

Inner product computation

b

4x0

Row i of A b

b

2x0

ci

Row i of A

+6x1

+2x2

– 2x3

=

8

+5x2

– 2x3

=

4

–4x0

– 3x1

– 5x2

+4x3

=

1

8x0

+18x1

– 2x2

+3x3

=

40

c

Row i of A

All-gather communication

Pemrosesan Paralel

Pemrosesan Paralel


Partitioning

P0

P1


Communication

4 2 4

6 0 3

2 5 5

8

18

2

2 8 2 4 4 1 3

40

P0 P1

4 2 4

6 0 3

2 5 5

2 2 4

8 4 1

8

18

2

3

40

5

3/1/2010

Pemrosesan Paralel

Pemrosesan Paralel


Communication (cont..)

Communication (CONT..)

P0 P1


4 0 0

6 3 3

2 4 3

2 1 2

8 0 9

0

6

6

7

24

P0 P1

4 0 0

6 2 3 4 0 1

2 1 1

8 0 9

0

0

5

24

2

Pemrosesan Paralel

Pemrosesan Paralel


Communication (cont..)

P0 P1


Shared memory multiprocessor using a single bus

4 0 0

6 3 0

2 5 5

2 8 1 0 1 9

0

0

0

3

6

Pemrosesan Paralel

Pemrosesan Paralel


Process • “A program in a run”, a program in the memory. • A high level view of a UNIX process


Threads • A stream of control in a process. • A high level view of threads in a UNIX process

6

3/1/2010

Parallel Bubble Sort

Pemrosesan Paralel


Iteration could start before previous iteration finished if does not overtake previous bubbling action:

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen, @ 2004 Pearson Education Inc. All

37

Pemrosesan Paralel


Virtual Topology

38

7

2010. Pengajar. Materi Kuliah. Materi Kuliah #2. Komputasi Paralel. Kuliah 01: Pendahuluan

Recommend Documents