[컴퓨터구조] 1206 (2)

Parallel Processors from Client to Cloud

Introduction

▷ 목표: connecting multiple computers.

- Multiprocessors

• Task 단위 병렬성
• Parallel processing program: 하나의 프로그램이 여러 프로세서 위에서 돈다.
• Multicore multiprocessors: Chips with multiple processors

 

Hardware ans Software

Hardware and Software

▶ 하드웨어

• Serial
• Parallel

▶ 소프트웨어

• Sequential: 행렬 곱셈
• Concurrent(경쟁): 운영체제

 

Parallel Programming

: Parallel software is the problem.

▷ Difficulties: 여러 코어에 대한 프로그래밍

• Partitioning: 병렬 연산 가능한 코어에 각자 할 일을 분배한다.
• Coordination(조정)
• Communication overhead: 병렬 프로그래밍에 대한 통합 과정 속에서의 오버헤드

 

Amdahl's Law

: 순차적으로 연산을 해야 하는 부분과 병렬적으로 연산을 해야 하는 부분으로 구성되어 있다.

• 코어의 개수를 늘려보자. 병렬적으로 연산할 수 있는 부분의 성능은 좋아진다! 그런데 그렇다면, 전체 성능은 얼마나 좋아질까? 병렬적으로 연산할 수 있는 부분이 얼마나 많아야, 전체 성능 향상을 가져올 수 있을까?

Amdahl's Law

: 프로세서 개수를 늘릴 때 성능향상을 가져오기 위해서는, 즉 연산 속도를 빠르게 하기 위해서는 parallel part의 비율이 엄청나게 높아야 한다. 그런데 어쩔 수 없는 sequential part는 항상 존재한다.

--> 프로세서 개수를 늘려도, 성능 향상에는 제약이 있다.

 

 

Instruction and Data Streams

Instruction and Data Streams

• SISD: Single Instruction, Single Data (지금까지 배운 것)
• SIMD: Single Instruction, Multiple Data
• MIMD: Multiple Instruction, Multiple Data

▶ SPMD: Single Program, Multiple Data

: MIMD 컴퓨터에서 사용되는 병렬 프로그램

 

Vector Processors

: Highly pipelined function units.

• Data-parallel programming

 

Example: DAXPY (Y = a x X + Y)

Example: DAXPY (Y = a x X + Y)

• Scalar: Loop가 필요하다.
• Vector: Loop가 필요하지 않다.

 

SIMD (Single Instruction, Multiple Data)

: 모든 프로세서에서 같은 instruction을 수행한다.

• Works best on highly data-parallel applications.

 

Multithreading

• Thread: task를 thread로 나눈 것

: Performing multiple threads of execution in parallel.

• Find-grain multithreading: clock cycle 단위로 thread를 변경한다.
• Coarse-grain multithreading: 하나의 thread를 계속 실행하다가, long stall이 있을 때만 thread를 변경한다.
• Simultaneous multithreading: 여러 thread가 clock cycle과 관련없이 동시에 실행된다.

Multithreading

 

---

Shared Memory vs. Message Passing

• SMP: Shared Memory Multiprocessor

Shared Memory vs. Message Passing

• Shared memory: 여러 개의 프로세서가 하나의 메모리를 공유한다.
• Message passing: 각각의 프로세서가 자신만의 메모리를 가지고 있다. 따라서 프로세서 간에 데이터를 교환하려고 할 때, share memory에 접근할 수 없고, communication이 필요하다.

 

Example: Sum Reduction

1) Shared Memory 방식

1) Shared Memory 방식

1. 100,000개의 task를 100개의 프로세서에게 각자 1,000개씩 나눠준다.
2. 프로세서 별로 sum 수행 결과 100개의 sum이 생긴다.
3. 이 100개의 sum을 두 개의 덩어리로 50개, 50개씩 나눠서, 한 덩어리에서 하나씩 골라서 두 개의 sum을 하는 과정을 반복한다.
4. sum해야 하는 수가 계속 절반으로 줄어든다. log(n)

 

2) Message Passing 방식

2) Message Passing 방식

 

 

 

 

 

출처: 이화여자대학교 이형준교수님 컴퓨터구조, 윤명국교수님 컴퓨터구조