파이프라이닝 개관
 파이프라이닝은 여러 개의 명령어가 중첩해 실행되는 구현기술이다.
 파이프라이닝은 명령어 처리량을 증가시킴으로써 성능을 향상시킨다.


명령어 실행 단계
1. 명령어를 메모리부터 가져온다.
2. 명령어롤 해독하는 동시에 레지스터를 읽는다.
3. 연산을 수행하거나 주소를 계산한다.
4. 데이터 메모리에 있는 피연산자를 접근한다.
5. 결과값을 레지스터에 쓴다.


파이프라인 해저드
 구조적 해저드, 데이터 해저드, 제어 해저드

 구조적 해저드 - 같은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없는 경우. 가령 메모리부터 명령어를 가져옴과 동시에 메모리로부터 데이터를 가져와야 하는 명령어를 수행해야 하는 경우 메모리가 하나만 있다면 도시에 메모리로부터 데이터를 가져 올 수 없기에 하드웨어의 구조적 문제에 직면한다.

 데이터 해저드 - 한 단계가 다른 단계가 끝나기를 기다리기 때문에 파이프라인이 지연되어야만 하는 경우 일어난다.  이는 한 명령어가 파이프라인 상에 있는 앞선 명령어에 종속성을 가질 때 데이터 해저드가 일어난다. 가령 add 명령어 뒤어 바로 sub 명령어가 있다면 add는 명령어 실행 단계 중에서 3,4,5를 수행한 이후에야 결과값을 레지스터에 쓴다. 그렇다면 3 단계의 파이프라인을 포기해야 함을 의미한다. 이런 경우 전방전달(forwarding 또는 bypassing)을 이용해 해결한다.

 제어 해저드 - 다른 명령어들이 실행중에 한 명령어의 결과값에 기반을 둔 결정을 할 필요가 있을때 발생한다. 즉 분기 명령어가 이에 해당한다.

지연분기 : 이는 분기 명령어 다음에 나오는 명령어는 분기조건이 참인지 거짓인지 상관없이 항상 실행된다는 것을 의미한다. 조건이 거짓이면 보통의 분기처럼 실행된다. 조건이 참이면 지연분기는 분기 명령어 바로 다음 명령어를 먼저 실행하고 명시된 분기목적지 주소로 건너뛴다.

분기예측 : 어떤 경우는 분기한다 혹은 분기하지 않는다고 가정하는 것이다. 각 분기가 일어났는지, 안 일어났는지 이력을 기록하고 미래를 예측하기 위해 최근의 과거 이력을 사용한다.

블록배치방식 - 캐쉬에 블록을 위치시키는 방법은 다음의 세가지 방식이 존재한다.
  1. Directed Mapped : 블록이 단지 한곳에만 위치할 수 있는 방법
  2. Fully Associative : 블록이 캐쉬내의 어느 곳에나 위치할 수 있는 방식.
  3. Set associative : n-way 집합연관 캐쉬는 각각 n개의 블록으로 이루어진 다수의 집합들로 구성되어 있다. 빠른 검색을 위해 n개의 블록을 병렬로 수행한다.

집합 연관방식 장,단점
  - 장점
  연관 정도를 늘리는 것의 장점은 대개 실패율이 줄어든다는 것이다.
(부가설명=>n-way 집합 연관방식에서는 n개의 블록을 병렬로 검색한다. 따라서 더 많은 수의 블록을 검색하기 위한 논리 게이트가 증가한다, 반면에 캐쉬 내 집합의 개수는 감소하여 찾을 범위가 더 적어진다.)
  - 단점
  가장 큰 단점은 적중 시간의 증가이다.(비용적 문제도 증가)

집합 연관 방식에서 블록 교체 방식
  집합연관 캐쉬는, 대개 집합내에서 가장 오래전에 사용된 블록을 교체시키는 LRU(least recently used)교체 방식을 사용한다.


문제
  4개의 1워드 블록으로 구성된 캐쉬가 있다(캐쉬 크기가 4워드). 직접사상, 2-way 집합연관, 4-way 집합연관, fully 집합연관방식이다. 각 캐쉬 구현에 대해서 다음 순서에 따른 블록 주소의 참조시 발생하는 실패의 수는 각각 얼마인가? 블록주소 : 0, 8, 0, 6, 8

직접사상캐쉬 : 5번
2-way 집합연관 캐쉬 : 4번
4-way 집합연관 캐쉬(완전 집합연관방식) : 3번

4-way 집합연관 캐쉬

  위 그림은 4-way 집합연관 캐쉬이다. 하나의 블럭은 1워드이다. 집합의 개수는 256개(0~255)이다. 따라서 캐쉬의 사이즈는 4byte * 집합의 개수 * n-way(블럭개수) 로 계산이 가능하므로, 4byte * 256 * 4 = 4096 byte, 즉 4K이다.
  그림에서 보는거와 같이 색인값은 필요한 주소를 가지고 집합을 선정하는데 이용되고, 선정된 집합 내부의 모든 블록의 태그는 비교되어야 한다. 선정된 모든 태그는 빠른 속도를 위하여 병렬로 검색한다.
  완전연관 캐쉬의 경우, 실제 한 개의 집합만이 존재하며 모든 블록들은 병렬로 검사되어야 한다. 따라서 색인이 필요 없고, 블록 변위를 제외한 전체주소는 모든 블록의 태그와 비교된다. 즉 색인을 사용하지 않고 전체 캐쉬를 검색해야 한다.

문제
연관정도를 늘리는 것은 캐쉬 블록 당 더 많은 태그 비트를 요구할 뿐만 아니라, 더 많은 비교기를 필요로 한다. 4K개의 블록을 갖고 하나의 블록은 4개의 워드를 가지며 32 비트 주소를 갖는 캐쉬에 대해 직접 사상, 2-way 집합연관, 4-way 집합연관과 완전연관 방식을 적용하였을때 각각에 대해 전체 집합의 수와 전체 태그 비트 수는 ?
  정답 : 직접사상, 2-way, 4-way, 완전연관 => 64Kbits, 68 Kbits, 72 Kbits, 112Kbits

출처 : 컴퓨터 구조 및 설계 - 하드웨어/소프트웨어 인터페이스 -

즉시 쓰기(write-through) : 쓰기 발생 시, 항상 데이터를 메모리와 캐쉬에 같이 쓰는 것.
나중 쓰기(write-back) : 쓰기 발생 시, 새로운 값은 캐쉬 내의 블록에만 쓰여진다. 그리고 수정된 블록은 교체될 때 메모리 계층 구조의 더 낮은 계층(버퍼 혹은 메모리)으로 쓰여지게 된다.

출처 : 컴퓨터 구조 및 설계 -하드웨어/소프트웨어 인터페이스 -

- 메모리의 각 워드에 대한 캐쉬의 위치를 할당하는 가장 간단한 방법은 메모리 주소에 기반을 두고 할당하는 것이다. 이 캐쉬 구조를 직접 사상(direct mapped)이라 한다. 즉 각 메모리 위치가 캐쉬 내의 정확히 한 곳에만 사상되는 캐쉬 구조이다.

 
 캐쉬 내의 각 위치는 여러 메모리 주소의 내용을 적재할 수 있다. 이때, 어떻게 캐쉬 내의 워드가 프로세스가 요구하는 것과 일치하는지를 알 수 있는가 ? 즉 요구하는 워드가 캐쉬 내에 있는지 없는지 어떻게 알 수 있는가? 이것은 캐쉬에 태그(빨간 글씨로 표현)를 추가함으로써 해결할 수 있다. 태그는 캐쉬의 색인으로 사용되지 않은 비트들에 해당하는 주소의 윗부분을 포함하기만 하면 된다.

또한 유효비트(valid bit)를 캐쉬에 첨가하여 캐쉬 블록이 유효한 정보를 가지고 있는지 알아내도록 한다.

이것을 심화시키면 다음 그림과 같다.[Intrinsity사의 FastMATH 프로세서에 사용되는 16KB Cache]

Index : 블록을 고르는데 쓰이는 캐쉬 색인
Tag : 캐쉬의 태그 필드 값과 비교되어 지는 태그 필드
Block offset : 블록 내부의 워드 구별(위 그림에서는 16개 중 하나를 선택)
Byte offset : 워드 내부의 바이트

크기가 큰 블록의 공간적 지역성은 실패율을 감소하게 한다. 그러나 블록의 크기를 캐쉬 크기의 상당 부분을 차지하도록 크게 만들면 실패율이 올라갈 수도 있다. 왜냐하면, 캐쉬 내에 존재할 수 있는 전체 블록의 수가 작아져서 블록들 간에 상호충돌이 생길 수 있기 때문이다. 결과적으로 블록 내의 많은 워드들이 접근되기도 전에 그 블록이 캐쉬로부터 방출될 수도 있기 때문이다.

출처 : 컴퓨터 구조 및 설계 -하드웨어/소프트웨어 인터페이스 -

원칙

- 프로그램이 동작하는 방법에는 다음과 같은 지역성의 원칙(principle of locality)이 적용된다.

- principle of locality