병렬처리

병렬처리

 

• 병렬처리의 개념
  - 여러 개의 프로세서를 장착한 컴퓨터에서 실행될 수 있는 처리방식
  - 하나의 프로그램에서 서로 다른 태스크를 동시에 처리할 수 있음
  - 처리 부하를 분담하고 처리 속도를 향상시킴
  - 프로그램 분할, 스케줄링, 동기화 등의 새로운 문제점이 발생

 

 

 

병렬 컴퓨터의 분류

 

 

마이클 J. 플린의 병렬 컴퓨팅 분류

 

* 플린의 분류 용어

제어장치 : 명령어를 인출하고 해독하여 제어신호를 만듦

처리장치 : 제어장치에서 만들어진 제어신호에 근거하여 처리할 데이터와 주소 등의 오퍼랜드를 인출하고 명령어를 수행하는 장치

명령어 스트림 : 순서대로 나열한 명령어 코드들의 집합

데이터 스트림 : 명령어들을 실행하는 데 필요한 순서대로 나열된 데이터의 집합

 

• SISD (Single Instruction stream Single Data stream)
  - 한 번에 하나의 명령어와 데이터를 순서대로 처리하는 단일 프로세서 시스템
  - 명령어 파이프라이닝, 슈퍼스칼라 구조를 이용하여 처리 효율을 향상시킬 수 있음
  
  
• SIMD (Single Instruction stream Multiple Data stream)
  - 명령어 스트림 하나가 다수의 처리장치에서 동시 처리되도록 제어하는 방법
  - 처리장치는 처리요소기라고도 하며, 내부에 독립된 데이터 기억장치가 있음
  - 하나의 제어장치는 하나의 명령어를 인출하여 해독하고, 여러 개의 처리장치는 여러 데이터를 동시에 인출하여 명령어를 실행
  - 배열 처리기, 벡터 처리기 
  
  
• MISD (Multiple Instruction stream Single Data stream)
  - 여러 제어장치는 동시에 여러 명령어를 인출하여 각각 해독하고 하나의 처리장치는 여러 명령어를 실행하여 하나의 데이터 스트림을 가짐
  - MISD 구조는 비현실적이어서 범용 컴퓨터 형태로 구현될 수 없음
  
  
• MIMD (Multiple Instruction stream Multiple Data stream)
  - 다수의 처리장치가 서로 다른 명령어를 동시에 병렬로 실행하는 형태
  - 제어장치들은 동시에 여러 명령어를 각각 인출하고 해독하며, 처리장치들은 여러 데이터를 동시에 인출하여 각각 명령들을 실행
  - 일반 목족의 다중 프로세서 구조
  
  
  

명령어 파이프라이닝 (instruction pipeline)

 

• 명령어 파이프라이닝
  - 한 번에 하나의 명령어만 실행하는 것이 아니라 하나의 명령어가 실행되는 도중 다른 명령어의 실행을 시작하는 방법으로 동시에 여러 개의 명령어를 시간적으로 중첩하여 실행
  - 하나의 명령어를 여러 단계로 나누어 처리하므로 한 명령어의 특정 단계를 처리하는 동안 다른 부분에서는 다른 명령어의 다른 단계를 처리할 수 있음
  - 전체적인 처리 속도와 처리량을 향상시킴
  - 하나의 명령어 처리 속도가 빨라지는 것은 아님
  
  
• 2단계 명령어 파이프라인
  - 명령어를 실행하는 하드웨어를 인출 단계와 실행 단계라는 독립적인 파이프라인 모듈로 분리하여 수행
  - 각 명령어의 인출 단계와 실행 단계의 처리 시간이 동일해야 파이프라인으로 인한 효율 향상을 얻을 수 있음

• 4단계 명령어 파이프라인
  - 명령어 인출(IF), 명령어 해독(ID), 오퍼랜드 인출(OF), 실행(EX) 단계로 분리하여 수행
  - 첫 번째 클록 주기를 제외하고 나머지 클록은 병렬로 처리되며 최대 4개의 명령어 단계가 동시에 처리

 

• 파이프라인에 의한 속도 향상
  - 파이프라인의 단계 수 K, 실행할 명령어들의 수 N, 각 파이프라인 단계의 클록 주기 T, 파이프라인에 의한 전체 명령어 실행 시간 S

S = (K + N - 1) * T

 

• 이상적인 효과가 나올 수 없는 문제점
  - 각 단계의 클록 주기는 실제 가장 긴 시간으로 정함
  - 오퍼랜드 인출이 필요없는 명령어도 모든 단계를 통과해야 함
  - 4단계 파이프라이닝에서 IF단계와 OF단계가 동시에 기억장치에 접근하는 경우 기억장치 충돌이 발생하며 지연이 발생
  - 조건 분기 명령어가 실행되면, 미리 인출하여 처리하던 명령어들이 무효화됨
  
  
  

파이프라인 해저드

 

• 해저드
  - 명령어나 데이터가 준비되지 않아서 파이프라인을 멈춰야 하거나 새로운 명령어를 파이프라인에 투입할 경우 잘못된 결과가 초래되는 모든 상황이나 조건
  
  
• 구조적 해저드
  - 파이프라인에서 실행 중인 2개 이상의 명령어가 동일한 하드웨어 자원을 동시에 요구하기 때문에 파이프라인을 멈춰야 하는 상황
  - 자원 헤저드라고도 함
  - 구조적 해저드를 해결하려면 충돌되는 자원을 추가로 제공하여 파이프라인을 재구성하거나 예약표를 이용하여 자원 충돌을 방지
  
  
• 명령어 해저드
  - 실행할 명령어가 결정되지 않았거나 준비되지 않아서 파이프라인을 멈춰야 하는 상황이나 조건
  - 분기 명령어에 의해 발생하므로 분기 해저드 또는 제어 헤저드라고도 함
  
  
• 데이터 해저드
  - 연산할 데이터가 준비되지 않아 파이프라인을 멈춰야 하는 모든 상황이나 조건
  - 주로 선행 명령어가 사용하는 데이터와 후행 명령어가 사용하는 데이터 사이의 종속관계로 인해 발생
  - 파이프라인 방식의 데이터 접근 순서와 순차적인 방식과 다를 수 있기 때문
  
  
  

슈퍼스칼라 (superscalar)

 

• 슈퍼스칼라
  - 파이프라인으로 구현된 여러 개의 기능 유닛이 명령어들의 병렬 처리를 지원
  - 슈퍼스칼라 등급이 m이면, m개의 명령어를 병렬 처리한다는 것

등급이 m인 k단계의 슈퍼스칼라 프로세서에서 N개의 명령어를 실행하는데 걸리는 전체 시간

(k + N/m - 1) * T

 

 

 

 

슈퍼 파이프라인

 

• 슈퍼 파이프라인
  - 파이프라인에서 단계의 클록 주기를 절반 이하로 줄여서 명령어 실행 속도를 두 배 이상 높이는 방법
  - 슈퍼 파이프라이닝의 등급이 m이면, 기능 유닛의 클록 사이클 시간을 기본 사이클의 1/m이 됨

등급이 m인 k단계의 슈퍼파이프라인 구조에서 N개의 명령어를 실행하는데 걸리는 전체 시간

(k + (N - 1) / m) * T

 

 

 

 

 

암달의 법칙 (Amdahl's law)

 

• 암달의 법칙
  - 초기의 IBM 컴퓨터 설계자인 진 암달이 제안한 법칙으로 시스템의 일부분을 개선하는 경우 전체 시스템에서 얻을 수 있는 최대 성능 향상을 구할 때 사용
  - 시스템 일부의 기능을 아무리 향상하더라도 성능이 향상되지 않은 부분에 의해 전체 시스템의 성능이 제한된다는 것
  - 주로 병렬화에 의한 시스템 성능 향상의 한계를 지적하는 데 사용
  
  
• 최대 성능 향상

어떤 시스템을 개선하여 전체 작업 중 p%의 부분에서 s배의 성능이 향상되었을 때 전체 시스템에서 최대 성능 향상 배수

1 / (1 - p) + p / s

 

부동 소수점 연산의 수행 시간이 50%를 차지하는 프로그램이 있다.

 

1. 부동 소수점 연산을 위한 하드웨어를 2배 빠르게 만든다면 수행 시간이 얼마나 향상되는가?

시스템의 전체 성능 향상 = 1 / (1 - 0.5) + 0.5 / 2 = 1.33...

따라서 전체 프로그램은 이전보다 약 1.33배 빨라진다.

 

2. 이 프로그램을 2배 빠르게 수행하려면 부동 소수점 연산을 위한 하드웨어를 얼마나 개선해야 하는가?

2 = 1 / (1 - 0.5) + 0.5 / s

0.5 / s = 0 즉, s = 무한대가 되어야 한다.

따라서 부동 소수점 연산의 부하가 50%를 차지하는 경우, 부동 소수점 연산을 위한 하드웨어에 아무리 투자하더라도 전체 성능을 2배 향상할 수 없다.