[CS] #3 Computer Science
컴퓨터 공학 문제 오답 위주로 정리한 내용입니다.
Flynn의 분류 방법(Flynn's taxonomy)
SISD (Single Instruction stream, Single Data stream): 이 유형에서는 하나의 명령어 스트림과 하나의 데이터 스트림이 있는 단일 프로세서가 작업을 수행합니다. 이는 전통적인 단일 프로세서 컴퓨터 아키텍처를 나타냅니다.
SIMD (Single Instruction stream, Multiple Data streams): 이 유형에서는 하나의 명령어 스트림이 여러 개의 데이터 스트림에 대해 병렬로 작업을 수행하는 다수의 프로세서가 있는 아키텍처를 나타냅니다. 예를 들어, 벡터 프로세싱이나 GPU의 구조가 여기에 해당됩니다.
MIMD (Multiple Instruction streams, Multiple Data streams): 이 유형에서는 다수의 프로세서가 각각 독립된 명령어와 데이터 스트림을 가지며 병렬 작업을 수행하는 아키텍처를 나타냅니다. 다양한 유형의 프로세서가 독립적으로 작업하며 데이터를 처리하는 분산 시스템이 여기에 해당됩니다.
NUMA (Non-Uniform Memory Access Model): 이것은 Flynn의 분류 방법에 포함되지 않는 개념입니다. NUMA는 프로세서와 메모리 간의 액세스 속도가 물리적인 거리에 따라 다르게 구성되어 있는 컴퓨터 아키텍처를 나타냅니다.
파이프라인에서의 작업 수행과 클럭 사이클에 대한 관계를 나타내는 공식
클럭 사이클 수 = 세그먼트 수(k) + 작업 수(n) - 1
파이프라인의 구현
하나의 처리 과정(Process)을 여러 세부 처리 과정(Subprocess)으로 나누어 처리하는 기법입니다. 파이프라인에서는 작업을 여러 단계로 분리하고 각 세그먼트가 연속적으로 작업을 처리합니다. 각 세그먼트에서 수행된 중간 결과는 다음 세그먼트로 전달되며, 최종적으로 파이프라인의 끝에서 결과가 생성됩니다. 중간 결과가 계산 후 폐기되지 않고 다음 단계로 전달되어 최종 결과를 생성하는데 사용됩니다. 각 Subprocess는 동시에 다른 데이터를 취급하며 Segment간 데이터 이동은 레지스터(register)를 통해 이루어집니다. 파이프라인의 세그먼트는 각각 다른 작업을 처리하며, 다음 세그먼트로 데이터를 전달할 때는 반드시 해당 세그먼트의 처리가 끝날 때까지 기다려야 합니다. 따라서 세그먼트 간의 데이터 전송은 세그먼트의 수행 속도와 밀접한 관련이 있습니다.실제 구현에서 각 세그먼트의 수행 속도가 서로 다릅니다. 대표적인 설계로 산술 파이프라인과 명령어 파이프라인이 있습니다. 수행시간이 가장 늦는 세그먼트로 인해 레지스터 전송에 싱크를 맞추어 주어야함.
파이프라인에서 각 세그먼트의 처리 시간
총 처리 시간 = (세그먼트 수 - 1) × 각 세그먼트의 처리 시간 + 마지막 세그먼트의 처리 시간
산술 연산을 기준으로 나눈 파이프라인 설계
산술 파이프라인은 연산을 다수의 단계로 분리하여 병렬로 처리하는 기법입니다. 각 단계는 연산의 서로 다른 부분을 처리하며, 다음 단계로 데이터가 전달되어 처리되는 동안 이전 단계에서 새로운 연산을 시작할 수 있습니다. 이를 통해 여러 개의 연산을 동시에 처리하고, 연산 처리 속도를 향상시킬 수 있습니다.
명령어 파이프라인
명령어 파이프라인은 컴퓨터 아키텍처에서 명령어의 처리를 여러 단계로 분리하여 병렬로 처리하는 기법입니다. 명령어 파이프라인에서 분기(브랜치) 명령어가 실행되는 경우, 분기 대상 주소를 알기 전까지 다음에 수행될 명령어를 예측할 수 없습니다. 따라서 분기 명령어가 실행되면 파이프라인 내의 이전 단계에서 발생한 명령어들을 모두 버리고 분기 이후의 명령어들을 기다려야 합니다. 이로써 올바른 명령어의 수행을 보장하며 예측 실패로 인한 잘못된 결과를 방지합니다.
명령어 파이프라인의 정상 동작을 저해하는 요인
Resource Conflict (자원 충돌): 여러 명령어가 동시에 동일한 하드웨어 자원에 접근하려고 할 때 자원 충돌이 발생합니다. 예를 들어, 두 개의 명령어가 동시에 같은 레지스터에 값을 쓰려고 하거나 메모리에 접근하려고 할 때 충돌이 발생할 수 있습니다.
Data Dependency (데이터 의존성): 명령어 간에 데이터 의존성이 존재하는 경우에는 이전 명령어의 실행 결과가 다음 명령어의 실행에 영향을 줄 수 있습니다. 이로 인해 파이프라인에서 데이터가 올바르게 처리되지 않거나 지연될 수 있습니다.
Branch Difficulty (분기 어려움): 분기 명령어가 파이프라인에서 처리되는 동안 다음 명령어들을 예측하는 것이 어려울 수 있습니다. 잘못된 예측은 파이프라인의 비우기를 유발하여 성능 저하를 일으킬 수 있습니다.
명령어 파이프라인에서 분기 명령어 처리
분기로 인한 성능 감소를 해결하기 위해 분기 예측을 이용할 수 있음
Branch Target Buffer (BTB)를 사용해 분기 예측을 구현할 수 있음
BTB를 활용한 분기 예측은 Fetch 과정에서 수행되어야 함
BTB는 이전 분기 명령어의 결과를 토대로 분기 결과를 예측함
메모리 계층 구성
Main Memory (주 기억장치): 메인 메모리는 CPU와 직접 연결되어 있는 주 기억장치로, 프로그램 실행 및 데이터 처리에 사용됩니다.
Auxiliary Memory (보조 기억장치): 여기서 보조 기억장치는 주기억장치인 메인 메모리보다 느린 속도로 데이터를 접근하는 장치를 가리킵니다. 하드 디스크 드라이브와 같은 외부 저장장치가 여기에 해당됩니다.
Cache Memory (캐시 메모리): 캐시 메모리는 CPU와 메인 메모리 사이에 위치하여 CPU가 빠르게 접근할 수 있는 작은 용량의 고속 메모리입니다. 명령어와 데이터의 임시 저장소로 사용되며, 주로 빈번하게 사용되는 데이터를 저장해 빠른 액세스를 가능케 합니다.
주 기억 장치(Main Memory Unit)
SRAM (Static Random-Access Memory): SRAM은 전원이 연결되어 있는 동안 정보를 유지할 수 있는 메모리입니다. 내부 구성이 복잡하고 빠른 액세스 속도를 가지는 특징이 있습니다.
DRAM (Dynamic Random-Access Memory): DRAM은 전원이 연결되어 있더라도 주기적으로 정보를 유지하기 위해서는 주기적인 충전이 필요한 메모리입니다. 정보를 저장하는 셀이 충전 상태를 유지하기 위해 반복적인 재충전이 필요합니다.
ROM (Read-Only Memory): ROM은 읽기 전용 메모리로, 데이터를 기록한 후에는 수정할 수 없습니다. 프로그램 코드나 부트로더와 같이 변경되지 않는 데이터를 저장하는 데 사용됩니다.
보조 기억 장치 (Auxiliary Memory Unit)
보조 기억 장치 내의 자료는 필요한 경우 주 기억 장치로 옮겨져야 함
다른 기억 장치에 비해 대용량 자료의 보관이 용이함
메모리 계층 중 접근 속도는 메인 메모리와 비교하면 상대적으로 느림
보조 기억 장치의 예로 Disk, Magnetic Drum 등이 있음
참조의 국한성 (Locality of Reference)
프로그램이 수행되는 동안 메모리 참조가 국한된 영역에서 이루어지는 경향성을 말함
캐시 메모리 (Cache Memory)는 참조의 국한성을 활용한 메모리 계층임
Cache Memory는 접근 속도가 빠르지만 메인 메모리보다는 비싸고 용량이 작음
원하는 데이터를 Cache Memory에서 찾았을 때를 hit, 찾지 못했을 경우에는 miss라고 함
평균 데이터 접근 시간
평균 데이터 접근 시간 = (Hit 시간 * Hit ratio) + (Miss 시간 * Miss ratio)
- Hit 시간: Cache에서 데이터를 찾는 데 걸리는 시간 (30 ns)
- Hit ratio: Cache Hit의 확률 (0.8)
- Miss 시간: Cache Miss일 때 주 메모리에서 데이터를 가져오는 데 걸리는 시간 (300 ns)
- Miss ratio: Cache Miss의 확률 (1 - Hit ratio)
Cache Memory의 맵핑 기법
Associative Mapping (연관 매핑): Cache Memory의 각 블록이 주 메모리의 어떤 위치에든 할당될 수 있는 방식입니다. 데이터의 주소가 Cache 내에서 어디에 있는지를 검색하기 위해 전체 Cache를 검색합니다. 가장 유연한 매핑 방식이며, Cache 크기에 비해 주 메모리 주소 공간이 크면 좋은 성능을 발휘합니다.
Direct Mapping (직접 매핑): Cache Memory의 각 블록이 주 메모리의 고유한 위치에 대응하는 방식입니다. 각 주 메모리 블록은 오직 한 개의 Cache 라인에만 할당될 수 있습니다. 주 메모리 주소를 Cache 인덱스로 변환하여 특정 위치에 할당됩니다. 이 방식은 간단하지만 충돌 문제가 발생할 수 있습니다.
Set-associative Mapping (집합 연관 매핑): Cache Memory를 여러 개의 집합으로 나누고, 각 집합에 여러 개의 라인을 가지는 방식입니다. 각 집합 내에서는 직접 매핑이 이루어집니다. 집합 내의 라인 중에 원하는 데이터를 찾는 것이므로 충돌 문제를 완화하면서 연관 매핑과 간접 매핑의 장점을 조합한 매핑 방식입니다.
가상 메모리 시스템과 캐시 메모리 시스템
가상 메모리 시스템은 보조 기억 장치와 주 기억 장치 사이에서 데이터 전송을 관리함
캐시 메모리 시스템은 주 기억 장치와 CPU 사이의 데이터 전송을 관리함
두 메모리 시스템 모두 최소 경비로 높은 평균 접근 속도를 얻기 위한 기법
캐시 메모리 시스템은 페이지 기반의 맵핑을 사용하는 것이 아니라, 블록 기반의 맵핑을 사용
주 기억 장치 규격
SDR (Single Data Rate)는 Clock 신호의 변이시 한 차례만 데이터를 전송
SDRAM은 Synchronous DRAM의 약어로, 데이터 전송을 Clock 신호와 함께 동기화하여 수행하며 제어 신호와 Clock Pulse를 별도로 구성하지 않음
DDR (Double Data Rate)는 Clock 신호의 상승과 하강에 총 두 번의 데이터 전송을 수행
작동 전압은 DDR, DDR2, DDR3, DDR4 순으로 낮아짐
보조 기억 장치
SSD: 회전판이 제거되어 제로 스핀 시스템이라고도 불린다. HDD와 달리 플래시 메모리로 구성된다.
RAID(Redundant Array of Independent Disks): 여러 개의 하드 디스크를 묶어 하나의 시스템으로 사용하거나, 데이터의 복제와 분산 저장을 통해 오류 복구 및 고 가용성을 지원하는 기술이다. 여러 개의 하드 디스크를 묶어 하나 처럼 사용할 수 있게 한다.
RAID 1: 복사본으로 구성한다.
RAID 2: Hamming code를 사용한다.
RAID 4: 각 디스크들이 독립적으로 접근이 가능하다.
시스템 버스
시스템 버스는 데이터 전송을 담당하며, Instruction 처리와는 직접적인 연관이 없다.
시스템 버스는 하드웨어 간의 데이터 전송을 위해 사용된다.
하나의 공통 경로를 사용하여 다수의 레지스터, 입출력 장치 들을 연결한다.
시스템 버스의 구성요소로는 제어 유닛(시스템 버스를 통해 데이터와 주소를 관리하고 다른 하드웨어 컴포넌트를 제어하는 역할), 데이터 라인(시스템 버스를 통해 데이터를 전송하는 데 사용되는 선), 주소 라인(시스템 버스를 통해 메모리나 입출력 장치의 주소 정보를 전달하는 데 사용되는 선)이 있다.
입출력 주소 지정 방법 중 Memory Mapped I/O
Memory Mapped I/O는 입출력 장치를 프로세스의 가상 주소 공간에 매핑하여 입출력 장치를 메모리처럼 다룰 수 있게 하는 방식입니다. 이로 인해 입출력 장치에 접근할 때 특별한 입출력 명령이나 별도의 인터페이스를 사용하지 않아도 됩니다. 그러나 주의해야 할 점은 Memory Mapped I/O는 입출력 장치를 메모리 공간으로 매핑하기 때문에 파일 시스템과는 관련이 없습니다. 동일한 주소선과 제어선으로 입출력 관리가 가능하고 지정된 주소 값으로 데이터 저장 공간과 I/O 장치를 구분합니다. 그러므로 주소 값에 따른 H/W를 구분하는 접근 구현이 필요합니다.
중앙 제어 버스와 분산 제어 버스
중앙 제어 버스는 하나의 버스 컨트롤러가 버스 접근 제어를 수행한다.
버스에 연결된 모든 장치가 제어 기능을 분담하여 수행하는 것을 분산 제어 버스라고 한다.
I/O 버스는 주로 중앙 제어 버스 시스템을 이용한다.
중앙 제어 버스의 경우 제어기에 이상이 발생하면 다른 제어기가 그 역할을 대신할 수 없어 시스템 전체의 작동에 문제가 발생할 수 있다.
인터럽트를 사용한 I/O
I/O 장치는 데이터 전송을 위해 인터럽트를 사용하여 전송 준비 상태를 CPU에 알린다.
DMA를 사용하는 경우에도 DMA 채널을 개설하고 설정해야 한다. DMA는 CPU의 개입 없이 메모리와 I/O 장치 간 데이터 전송을 처리하는 기술이다.
인터럽트가 발생하면 CPU는 현재 실행 중인 프로그램을 중단하고 인터럽트 서비스 루틴을 실행하는 등의 동작을 수행한다.
인터럽트를 사용한 I/O에서는 인터럽트 서비스 루틴(SW Routine)을 사용하여 I/O 작업을 처리해야 한다.
인터럽트 우선순위
동시에 발생한 인터럽트에 대해서 우선순위를 결정하여 처리하는 것을 의미한다.
Polling은 하나의 인터럽트를 처리한 후 다음 인터럽트를 처리하기 위해 계속 대기하는 방식이므로 스프트웨어로 우선순위를 결정하는 방법으로는 Polling이 아닌 다른 방법들이 사용된다.
마스크 레지스터는 인터럽트의 요청 상태를 걸러내어 처리할 수 있도록 한다.
데이지 체인 우선순위 인터럽트는 모든 장치를 병렬로 연결하여 처리한다.
병렬 처리를 위한 시스템
병렬 처리 시스템(Parallel Processing System)에는 다중 장치 구조와 파이프 라인 구조기 있다. 다중 장치 구조는 다수의 CPU 또는 처리 장치를 사용하여 병렬 처리를 수행하는 시스템을 의미합니다. 다중 CPU 시스템에서 각 CPU는 별도의 연산을 수행하며, 이를 통해 작업을 동시에 병렬로 처리할 수 있습니다. 따라서 다중 장치 구조는 CPU가 하나뿐인 시스템이 아니라 여러 개의 CPU를 가지고 있는 병렬 처리 시스템을 나타냅니다.
멀티프로세서
메모리와 I/O 장치를 공유하는 두개 이상의 CPU를 갖는 시스템이다.
멀티프로세서 시스템에서 단일 공통 버스를 사용하는 경우, 여러 개의 프로세서가 동시에 데이터를 전송하려고 하면 버스의 대역폭이 한계로 인해 병목 현상이 발생할 수 있다.
다른 말로 멀티 컴퓨터라고도 불린다.
하이퍼큐브 상호연결은 멀티프로세서를 연결하는 방법 중 하나이다.
멀티프로세서를 위한 운영체제
멀티프로세서 시스템에서 Master-slave 모드를 사용하는 경우, Master 프로세서는 운영체제의 주요 기능을 담당하며, Slave 프로세서는 주로 응용 프로그램의 실행을 담당합니다. Master-slave 모드에서 Master 프로세서가 주요한 운영체제 기능을 수행하고 Slave 프로세서에게 실행 허가를 부여하는 방식으로 동작하며 Slave 프로세서는 인터럽트를 통해 OS 기능을 요청합니다.
모든 프로세서가 각자 운영체제를 가지고 운영되는 방식을 분리 운영체제라고 하고, 운영체제의 기능을 여러 프로세스에 분산 시키는 방식을 분산 운영체제 라고 합니다.
Cache Coherence
Cache Coherence는 공유 메모리 멀티프로세서 시스템에서 여러 개의 프로세서가 동일한 메모리를 공유하면서 발생하는 문제 중 하나입니다. 각 프로세서가 개별 Cache를 가지는 경우에도 Cache Coherence 문제가 발생할 수 있습니다. 이는 동일한 메모리 위치를 여러 개의 Cache에서 동시에 변경할 수 있기 때문입니다. 따라서 각 프로세서에 개별 Cache를 허용하지 않으면 Cache Coherence를 해결 할 수 있습니다. 읽기 전용 데이터만 캐시가 가능하도록 설정해도 Cache Coherence 문제를 해결 할 수 있다. Snoopy Cache Controller는 버스를 감시하여 Cache를 제어합니다.