[Computer Structure] 병렬 조직

December 10, 2021

병렬 조직

병렬 조직

병렬 처리

병렬 처리란?

여러 개의 프로세서들이 여러 개의 프로그램들 혹은 한 프로그램의 분할된 부분을 분담해 동시에 처리하는 기술이다.
병렬 처리를 통해, 컴퓨터의 수행 능력을 향상시킬 수 있다.

병렬 처리를 위한 조건

많은 수의 프로세서로 하여금 하나의 시스템을 구성할 수 잇도록 작고 저렴한 고속 프로세서 요구
하나의 프로그램을 여러 개의 작은 부분들로 분할이 가능해야 한다.
분할된 부분들을 병렬로 처리한 결과가 전체 프로그램을 순차적으로 경우와 동일해야 한다.

병렬 처리를 위한 기술들

문제 분할
프로세서간 통신
병렬 프로그램 언어와 컴파일러의 개발
상호 배타 메커니즘 지원
공유자원들에 대한 경합을 줄이고, 이용률을 극대화할 수 있는 운영체제의 개발

병렬 처리의 유형

비트 레벨 병렬계산
- CPU의 비트 수를 증가시킨다.
  - 4 → 8 → 16 → 32 → 64비트
명령어 레벨 병렬계산
- 파이프라인
- 슈퍼스칼라
- VLIW
데이터 병렬계산
- 벡터 프로세서
- SIMD
작업 병렬계산
- 다중프로세서
- MIMD

다중 프로세서 컴퓨터의 종류

Untitled

다중 프로세서 조직

컴퓨터 시스템 유형

Untitled

각 유형에 대해 하나씩 알아보자.

단일 명령어, 단일 데이터 스트림 (SISD)

SISD: 명령어와 데이터를 한 번에 한 개씩 순서대로 처리하는 단일 프로세서 시스템
- 단일 프로세서
- 단일 명령어 스트림
- 단일 기억장치에 저장된 데이터
단일 프로세서가 하나의 기억장치에 저장되어 있는 데이터들을 처리하기 위해, 하나의 명령어 흐름을 순차적으로 실행한다.
사용하는 구조
- 명령어 파이프라이닝
- 수퍼스칼라
시각화

단일 명령어, 다중 데이터 스트림 (SIMD)

SIMD: 하나의 명령어 스트림이 다수의 프로세싱 요소들의 동시 처리를 제어한다.
각 프로세싱 요소는 별도의 데이터 기억장치를 갖는다.
각 명령어는 서로 다른 프로세서에 의해 서로 다른 데이터에 대해 실행된다.
명령어 수행 = 순차 수행 , 데이터 처리 = 병렬 처리
SIMD에서 사용하는 프로세서 종류
- 벡터 프로세서
- Array 프로세서
시각화
벡터 프로세서란?
- 복수의 연산장치를 병렬로 연결해, 큰 규모의 행렬이나 배열 연산을 고속으로 처리할 수 있다.
  - 수치해석이나 그래픽 데이터를 처리하는데 유리하다.

다중 명령어, 다중 데이터 스트림 (MIMD)

MIMD: 다수의 프로세서들이 서로 다른 명령어들을 서로 다른 데이터에 대해 동시에 병렬로 실행한다.
- 다수의 프로세서
- 다수의 데이터 집합
병렬 프로세서에서 일반목적용으로 사용된다.
시각화

MIMD 구분

MIMD는 기억장치 모듈을 사용·소유하는 방식에 따라 구분된다.

공유 기억장치 시스템 (밀접 결합)
- 모든 프로세서가 주기억장치를 공유한다. 따라서, 프로세서간 데이터 교환이 필요없다.
- 상호 연결망 상에서의 통신량이 증가한다.
  - 캐시 일관성을 유지하기 위해
- 자원 경합으로 인한 지연 가능성이 존재한다.
- 시스템 예시
  - 대칭적 다중 프로세서
  - 불균일 기억장치 액세스
- 구조 시각화

분산 기억장치 시스템 (느슨 결합)
- 각 프로세서가 자신의 지역 기억장치를 소유한다.
- 프로세서 간 통신은 메시지 전송을 통해 이뤄진다.
- 공유자원에 대한 경합이 감소한다.
- 통신 프로토콜에 의한 지연이 발생할 수 있다.
- 시스템 예시
  - 클러스터
- 구조 시각화

MIMD의 종류

대칭적 다중 프로세서 (SMP)
- 다수의 프로세서들이 공유버스 또는 다른 상호연결 메커니즘을 통해, 하나의 기억장치·기억장치 풀을 공유한다.
- 기억장치의 특정 위치에 대한 액세스 시간이 모든 프로세서에서 거의 동일하다.

클러스터
- 독립적인 단일 프로세서 또는 SMP 들의 집합
- 클러스터를 형성하기 위해서 상호 연결된다.
- 고정 경로 또는 네트워크 연결을 통한 통신을 한다.

비균일 기억장치 (NUMA)
- 기억장치의 특정 위치에 대한 액세스 시간이 다를 수 있다.

대칭적 다중프로세서 (SMP)

대칭적 다중프로세서란?

거의 같은 성능을 가진 두 개 이상의 프로세서들로 구성된다.
프로세서들은 주기억장치와 I/O장치들을 공유한다.
- 기억장치 액세스 시간은 모든 프로세서에서 거의 동일하다.
모든 프로세서들은 I/O 장치에 대한 접근을 공유한다.
모든 프로세서들은 동일한 기능을 수행할 수 있다.
시스템은 하나의 통합 운영체제에 의해서 제어된다.
- 운영체제는 프로세서 간의 상호작용을 지원한다.

대칭적 다중프로세서의 구조

Untitled

대칭적 다중프로세서의 장점

성능 향상
가용성
- 모든 프로세서가 동일한 작업을 하므로 한 프로세서가 고장나더라도 시스템은 중단되지 않는다. (성능은 저하될 수 있다.)
점진적 확장
스케일링

위와 같은 장점을 얻기 위해서는 운영체제가 SMP 시스템의 병렬성을 지원해야 한다.

다중프로세서 운영체제의 기능

여러 개의 프로세서들이 같은 명령어 코드를 동시에 수행할 수 있도록 지원해야 한다.
준비된 프로세스들을 사용 가능한 프로세서에게 할당하는 스케줄링 기능을 제공해야 한다.
주소 공간과 I/O 자원을 공유하는 프로세스들 간의 동기화를 제공해야 한다.
다수의 프로세서가 사용하는 기억장치의 일관성을 유지하기 위해 기억장치 관리가 필요하다.
프로세서에 결함이 발생하더라도 성능이 크게 저하되지 않도록 신뢰성 및 결함허용이 지원되어야 한다.

캐시 일관성 문제

동일한 데이터의 여러 복사본들이 동시에 여러 캐시에 존재할 때, 쓰기 동작이 수행될 경우
- 이때, 데이터 불일치 현상이 발생한다.
쓰기 지연
- 쓰기 동작이 항상 캐시에서만 이루어진다.
- 주기억장치는 그 캐시 라인이 캐시로부터 플러시될 때만 갱신된다.
- 이때, 캐시의 변경 사항이 즉시 주기억장치로 갱신되지 못하므로 불일치가 발생한다.
쓰기 통과
- 모든 쓰기 동작이 캐시 뿐만 아니라, 주기억장치까지 이루어진다.
- 결과적으로 주기억장치의 내용도 모두 유효하게 된다.
- 이때 다른 캐시가 기억장치와의 통신을 모니터링하지 못하거나, 주기억장치가 갱신 통보를 받지 못하는 경우에 불일치가 발생한다.

캐시 일관성 문제 해결법: 소프트웨어 해결법

컴파일러와 운영체제가 담당하게 된다.
동작 방식
- ‘캐싱 시 안전하지 못한 데이터’를 찾기 위해, 코드 분석 및 표시한다.
- 이때 표시한 ‘캐싱 시 안전하지 못한 데이터’를 캐싱할 수 없도록 한다.
- 또는, 코드 일관성을 위한 별도 코드를 삽입한다.
특징
- ‘잠재된 문제 검출을 위한 오버헤드’가 실행 시간에서 컴파일 시간으로 이동한다.
- 설계 복잡도가 소프트웨어에 전이된다.
- 보수적인 결정(단순히 캐싱을 안하도록 하는 방법)을 하므로 캐시 이용률이 낮다.

캐시 일관성 문제 해결법: 하드웨어 해결법

캐시 일관성 프로토콜이라고 불린다.
잠재적인 불일치 조건들을 실행시간 동안 동적으로 검출한다.
- 즉 프로세스 실행 도중, 불일치가 발생했을 때 처리한다.
특징
- 실제로 문제 발생시에만 처리되므로, 캐시를 더욱 효율적으로 사용할 수 있다.
- 소프트웨어 방식보다 우수하다.
- 소프트웨어 개발 시, 불일치 문제를 고려하지 않아도 된다. 따라서 소프트웨어 개발 부담이 줄어든다.

하드웨어 해결법: 디렉토리 프로토콜
- 주기억장치에 여러 지역 캐시들의 전역 정보를 관리하는 디렉토리가 있다.
  - 디렉토리 정보를 기반으로, 중앙제어기가 캐시 정보 변경에 대한 관리를 수행한다.
- 캐시 사용을 요청하는 프로세서에게 배타적 액세스를 허가한다. (독점적 액세스)
  - 다른 프로세서가 해당 캐시를 사용할 경우, 캐시 미스 통보를 보낸다.
- 단점
  - 중앙 병목
  - 캐시제어기와 중앙제어기 간의 통신 오버헤드 발생
- 적용
  - 복잡한 상호연결망으로 갖는 대규모 시스템에서 효과적이다.

하드웨어 해결법: 스누피 프로토콜
- SMP에서 주로 사용한다.
- 다중 프로세서 내의 모든 캐시 제어기가 캐시 일관성을 분산 관리한다.
  - 디렉토리 프로토콜: 중앙 집중형
  - 스누피 프로토콜: 분산형
- 공유 캐시 라인이 갱신되면, 다른 모든 캐시에게 알린다.
- 버스 기반 다중프로세서에 적합하다.
- MESI 프로토콜
  - 여러 캐시에서 공유된 한 라인에 어떤 캐시가 쓰기 동작을 하려면, 먼저 다른 모든 캐시들에게 그 라인을 무효화하도록 한다. 그리고 그 캐시에게 해당 라인을 배타적으로 사용하도록 한다. (쓰기 무효화)

클러스터

클러스터란?

여러 대의 완전한 컴퓨터들이 상호 연결되어 협력하면서 하나의 컴퓨터로 동작하는 통합 컴퓨팅 자원이다.
- 완전한 컴퓨터란: 클러스터로부터 분리되어도 자체적으로 동작할 수 있는 시스템
- 노드: 클러스터를 구성하는 개별 컴퓨터
고성능 및 고가용성을 제공하기 위한 방법으로, 대칭적 다중처리의 대안이다.
서버에 특히 적합하다.

클러스터링의 목표

절대적 확장성
- 가장 큰 독립적 시스템보다, 훨씬 더 큰 클러스터 구성이 가능해야 한다.
- 클러스터는 다중프로세서인 시스템들 수십 개로도 구성할 수 있다.
점진적 확장성
- 클러스터에 새로운 시스템들을 조금씩 추가하여 구성이 가능해야 한다.
- 사용자는 작은 시스템에서 시작하여, 큰 변화없이 점차적으로 필요한 만큼 확장할 수 있어야 한다.
고가용성
- 클러스터의 어떤 한 노드가 고장나더라도 서비스 제공이 가능해야 한다.
- 결함 허용은 소프트웨어적으로 자동 처리한다.
우수한 가격대 성능
- 하나의 큰 시스템보다 더 높은 컴퓨팅 능력을 가진 클러스터를 더 낮은 비용으로 구성할 수 있어야 한다.

클러스터 구성 방식들

클러스터를 구성하는 방식에는 아래 2가지가 존재한다.

디스크 비공유
- 개별 컴퓨터들이 디스크를 공유하지 않는 클러스터 방법
- 컴퓨터 간의 연결은 LAN 혹은 전용 연결망으로 연결된다.
- 컴퓨터간의 통신은 고속의 메시지 전달로 이루어진다.
디스크 공유
- 컴퓨터들이 디스크를 공유한다.
- 공유 디스크 시스템은 RAID로 구성한다.

클러스터링 방식

기본 용어
- Working System
  - 실제로 사용 중인 각 노드
- Backup · Standby System
  - 백업, 복구용 노드
클러스터링 방식
- Passive Standby
  - Standby System을 장애 발생 시에만 사용한다.
  - 구현하기 쉽다.
  - Standby System을 장애 발생 시에만 사용하므로, 비용적 낭비가 존재한다.
- Active Secondary
  - Standby System을 평소에도 사용한다.
  - 경제적이다.
  - 백업용 System이 실제 운용에 사용되고 있어, 백업 시 사용하기 복잡하다.

운영체제 설계 이슈

모든 자원들이 서비스를 제공할 확률
- $\frac{MTTF}{MTTF+MTTR}$
- MTTF = 시스템 시작 시각부터 장애 발생 시각 사이의 시간
- MTTR = 장애 복구 시간
결함 관리
- 고가용성 클러스터
  - 시스템 고장 또는 결함 없이 정상적으로 운영이 가능한 클러스터
- 결함-허용 클러스터
  - 시스템을 구성하는 부품의 일부에서 결함 또는 고장이 발생하더라도 정상적 혹은 부분적으로 기능을 수행하는 클러스터
- Failover
  - 고장난 시스템으로부터 프로세스들과 데이터 자원들을 클러스터 내의 다른 시스템으로 이동시키는 것
- Failback
  - 원래 시스템이 복구되었을 때 프로세스들과 데이터 자원들을 복원하는 것

부하 균등화
- 클러스터 내의 컴퓨터들 간에 부하를 균등하게 조절해야 한다.
- 새로운 컴퓨터 추가시, 부하 균등화 장치는 스케줄러에 이를 포함시켜야 한다.
  - 선형적인 확장성 보장

병렬화 계산
- 단일 응용 프로세스를 클러스터 상에서 병렬로 처리해야 한다.
- 병렬화 컴파일러
  - 컴파일 시간에 응용 프로세스의 어떤 부분들을 병렬로 실행할지 결정한다.
  - 이들은 클러스터 내의 서로 다른 컴퓨터들로 분할되어 보내진다.
- 병렬화된 응용
  - 프로그래머가 응용 프로세스를 클러스터에서 실행시킬 수 있도록 작성한다.
  - 메시지 전송을 통해서 노드들 간에 데이터를 이동시킨다.
  - 프로그램 구현은 어렵지만, 클러스터에서 실행하기에 가장 좋은 방법이다.
- 파라미터 컴퓨팅
  - 프로그램이 매번 다른 조건/파라미터로 오랜 시간 실행되어야 하는 경우, 사용한다.
  - 순서대로 작업들을 조직화하고, 실행 및 관리하기 위한 도구가 필요하다.

클러스터 미들웨어

사용자가 보기엔 하나의 시스템으로 보이게끔 해준다.
부하 균등화 및 구성요소의 결함에 대비하여 높은 가용성 등을 제공한다.

Untitled

블레이드 서버

블레이드 서버는 클러스터 방식의 보편적인 구현 중 하나이다.
여러 개의 서버 모듈들(블레이드들)을 하나의 섀시(chassis)내에 넣은 서버 구조이다.
특징
- 공간 절약
- 시스템 관리 향상
- 섀시에서 전력 공급
- 각 블레이드는 자신의 프로세서, 메모리, 하드디스크를 보유
- 전력 밀도 ↑

클러스터 vs 대칭적 다중프로세서

대칭적 다중프로세서
- 관리와 구성이 더 쉽다.
- 단일 프로세서 시스템에 가깝다.
  - 스케줄링 기능에 차이가 있을 뿐이다.
- 물리적 공간을 적게 차지한다.
- 전력 소모가 적다.
- 잘 검증되었으며, 안정적이다.
클러스터
- 점진적, 절대적 확장이 아주 우수하다.
- 모든 시스템이 중복되어 가용성이 우수하다.

불균일 기억장치 액세스

프로세서가 기억장치에 액세스하는 두가지 방법

균일 기억장치 액세스: UMA
- 모든 프로세서들이 주기억장치의 모든 부분에 접근할 수 있다.
- 프로세서가 기억장치의 특정 영역에 액세스하는 시간이 동일하다.
- 다른 프로세서의 기억장치 액세스 시간도 동일하다.
- SMP에서 사용한다.
불균일 기억장치 액세스: NUMA
- 모든 프로세서들이 주기억장치의 모든 부분에 접근할 수 있다.
- 프로세서의 기억장치 액세스 시간이 위치에 따라 다르다.
- 다른 프로세서의 기억장치 액세스 시간도 다르다.

캐시 일관 NUMA: CC-NUMA

여러 프로세서들의 캐시들 사이에 캐시 일관성이 유지되는 NUMA 시스템이다.
클러스터 vs NUMA 시스템
- 클러스터: 각 노드의 Main Memory를 각 노드만 사용한다.
- NUMA: 각 노드의 Main Memory를 모든 노드가 사용한다.

CC-NUMA의 출현 동기

SMP 시스템에서는 사용할 수 있는 프로세서의 수가 제한된다.
- 캐시 일관성 유지를 위한 트랙픽 증가로 버스 병목 현상이 발생한다.
클러스터에서는 각 노드가 별도의 주기억장치를 보유한다.
- 응용프로그램이 큰 용량의 전역 기억장치를 사용하지는 못한다.
- 일관성이 소프트웨어에 의해서 유지된다.
NUMA는 SMP의 장점을 갖는 대규모 다중프로세서 구성 방법이다.

NUMA의 목표

시스템 전체 기억장치의 투명성을 유지한다.
다수의 다중프로세서 노드들을 사용할 수 있도록 한다.
각 노드는 자신의 버스나 내부 상호연결 시스템을 갖도록 한다.

CC-NUMA의 구성

Untitled

CC_NUMA의 구성 및 동작

다수의 독립적인 노드들로 구성된다.
- 각 노드는 사실상, 하나의 SMP 조직이다.
각 노드는 여러 개의 프로세서들을 포함한다. 각각은 자신의 L1, L2 캐시와 주기억장치를 가지고 있다.
노드들은 네트워킹 장치에 의해서 연결된다.
각 기억장치는 시스템 전체적으로 유일한 주소를 갖는다.
각 노드는 디렉토리를 가지고 있어, 기억장치의 여러 부분에 대한 위치와 상태 정보를 유지한다.
- 캐시 일관성은 중앙집중식으로 이루어진다. (디렉토리 프로토콜)
기억장치 요구 순서
- L1 캐시 → L2 캐시 → 주기억장치(노드 내부) → 원거리 기억장치(노드 외부)

NUMA 장단점

소프트웨어를 거의 변경하지 않고도, SMP보다 더 높은 수준의 병렬성을 이용하여 효과적인 성능을 제공한다.
원격 노드에 대한 기억장치 액세스로 인한 성능 저하를 피할 수 있다.
시스템 구성에 따라 가용성 문제가 발생할 수 있다.

성결대학교 컴퓨터 공학과 최정열 교수님 (2021)
William Stalling, 『컴퓨터시스템구조론(10판)』

본 게시글은 위 강의 및 교재를 기반으로 정리한 글입니다.