제7장: 메모리 시스템(2) 컴퓨터구조

에러 검출 및 정정 데이터의 오류를 검출하거나 발생한 오류를 정정하기 위함 원래의 데이터에 부가적으로 오류 검출/정정 코드를 만들어 함께 저장 C 비트가 커질수록 더 많은 종류의 에러를 검출하거나 정정할 수 있음 오버헤드 -- 적을수록 효율은 높아짐 효율적인 에러의 검출 /정정을 위하여 적절한 길이 C의 선택이 필요 컴퓨터구조

전송(저장)되어지는 데이터는 검사 비트 생성기를 통해 만들어진 제어 코드와 함께 데이터 링크와 같은 에러소스를 통과 그림: 에러 제어 시스템의 블럭도 전송(저장)되어지는 데이터는 검사 비트 생성기를 통해 만들어진 제어 코드와 함께 데이터 링크와 같은 에러소스를 통과 검사비트 생성기를 통하여 만든 새로운 코드와 비교함 에러를 검출 에러 정정기를 통해 전송(저장)되어진 원래의 데이터를 얻음 컴퓨터구조

에러검출 및 정정방식 1) 패리티 비트 검사방식 - 짝수 패리티 검사 방식 2)해밍 코드(Hamming Code) - 홀수 패리티 검사 방식 2)해밍 코드(Hamming Code) 1 그림: 해밍코드 방식의 원리 컴퓨터구조

해밍코드 만드는 방식 하나의 에러가 발생하였을 경우 필요한 코드길이 발생된 에러를 검출하고 정정하기 위한 코드의 길이와 데이터의 길이의 관계식 [예제] - 데이터 비트가 8 일 경우는 검사 비트는 4 개가 필요 - 데이터 비트가 16일 경우에는 5 개의 검사 비트가 필요 해밍코드 만드는 방식 그림: 해밍 코드에서 데이터 비트와 검사 비트의 위치 컴퓨터구조

C1은 이진수 20 위치에 1을 가지는 수를 Ex-OR하여 얻음 C1 = D1  D2  D4  D5  D7 C2 = D1  D3  D4  D6  D7 C4 = D2  D3  D4  D8 C8 = D5  D6  D7  D8 C1은 이진수 20 위치에 1을 가지는 수를 Ex-OR하여 얻음 C2는 이진수 21위치에 1을 가지는 수를 Ex-OR 하여 얻음 C4는 이진수 22 위치에 C8은 이진수 23 위치에 1인 수를 Ex-OR 하여 얻음 위치 10 번째에 있는 비트는 10=8+2 이므로 8 과 2 번 위치의 비트들에 의해 검사되어 짐 컴퓨터구조

단, 가장 좌측에 있는 데이터를 D1이라고 가정한다. 또한 데이터 비트의 4 [예제 7-1] 8 비트의 데이터 10101011 에 대한 검사 비트를 구하라. 단, 가장 좌측에 있는 데이터를 D1이라고 가정한다. 또한 데이터 비트의 4 번째 비트 0가 오류가 발생하여 1로 바뀌었을 때, 에러를 검출하고 정정하는 과정에 대하여 설명하라. [풀이] C1 = 1  0  0  1  1 = 1 C2 = 1  1  0  0  1 = 1 C4 = 0  1  0  1 = 0 C8 = 1  0  1  1 = 1 따라서 저장되어지는 데이터는 원래의 데이터 10101011에 위에서 구한 검사 비트를 위치에 넣은 111001011011 이다. 만약 4 번째 비트가 오류가 발생하였다면, 오류가 발생한 데이터에 대한 검사비트들은 다음과 같다. C1' = 1  0  1  1  1 = 0 C2' = 1  1  1  0  1 = 0 C4' = 0  1  1  1 = 1 C8' = 1  0  1  1 = 1 컴퓨터구조

네 번째 비트 0가 1로 바뀌었음을 알 수 있음 이 검사 비트들과 원래의 검사 비트들과 비교하면 다음과 같이 에러가 발생한 위치를 구할 수 있음 C8 C4 C2 C1 1 0 1 1  1 1 0 0 0 1 1 1  전체 비트 중에 7 번째, 즉 데이터 비트 중에 4 번째가 오류가 발생 네 번째 비트 0가 1로 바뀌었음을 알 수 있음 컴퓨터구조

캐쉬 메모리(Cache Memory) 주기억 장치와 CPU 사이에 있는 메모리 계층 막기 위하여 사용 1980년 대 초에 마이크로 프로세서의 동작 속도와 DRAM의 액세스 속도 차이가 거의 없었기 때문에 캐쉬가 불필요 마이크로 프로세서의 속도는 1년에 60%의 속도로 증가 DRAM의 액세스 속도는 겨우 1년에 7%의 증가 1990년 초에는 속도의 차이가 거의 10배에 이름 1989년에 처음으로 인텔 마이크로프로세서에 칩 안에 캐쉬를 사용 (온 칩 캐쉬) 현재는 속도의 차이가 거의 100배에 달하므로 1차 캐쉬, 2차 캐쉬 등과 같이 캐쉬도 계층화되어 사용 컴퓨터구조

캐쉬 메모리의 특성 주 메모리에 비하여 매우 크기가 작음 프로세서와 비슷한 속도에서 동작 주 메모리에 비해 매우 가격이 높음 주 메모리는 DRAM으로 구성되어지며, 캐쉬는 SRAM으로 구성되어짐 주 메모리의 블럭의 복사본을 가짐 컴퓨터구조

표: 캐쉬에 사용되어지는 전형적인 파라미터 값 그림: 캐쉬 메모리의 위치 컴퓨터구조

CPU 내부의 1차 캐쉬와 CPU와 주 메모리 사이의 2 차 캐쉬로 구분 있는가를 확인하여, 만약 캐쉬에 저장되어 있으면 캐쉬로부터 읽혀져서 CPU로 보내짐 캐쉬에 원하는 데이터가 없으면, 주 메모리로부터 읽어서 캐쉬에 저장한 후에 CPU로 보냄 원하는 데이터를 캐쉬에서 참조되는 경우: 캐쉬 적중(Hit) 캐쉬에 원하는 데이터가 없는 경우: 캐쉬 미스(Miss) 캐쉬 적중률 적중률(Hit Ratio) = 캐쉬 적중 횟수 전체 기억장치 액세스 횟수 캐쉬 적중률 = H 캐쉬 미스률 = (1-H) 미스 패널티(miss penalty)란 캐쉬 미스가 발생하였을 경우, 데이터를 주 메모리에서 가져오는 시간과 캐쉬에서 CPU로 가져오는데 걸리는 시간 컴퓨터구조

미스일 경우 메모리로부터 데이터를 가져오는 액세스 시간 = tm 전체 평균 기억장치 액세스 시간 캐쉬 액세스 시간 = tc 미스일 경우 메모리로부터 데이터를 가져오는 액세스 시간 = tm 전체 평균 기억장치 액세스 시간 평균 기억장치 액세스 시간 = H x tc + (1-H)x tm 컴퓨터구조

어떤 컴퓨터에서 명령어의 실행에 있어서 캐쉬 히트인 경우 1 사이클이 필요 [예제 7-2] 어떤 컴퓨터에서 명령어의 실행에 있어서 캐쉬 히트인 경우 1 사이클이 필요 하고, 미스 패널티가 10 사이클이라고 한다. 이 컴퓨터를 사용하여 어떤 프로그램을 동작시킬 때 미스율이 20%일 경우, 평균 기억장치 액세스 시간을 구하라. [풀이] 캐쉬 미스율이 20% 이므로, 명령어 실행의 20%는 미스 패널티 시간을 필요 캐쉬 미스가 발생하였을 경우, 미스 패널티 10 사이클과 그 명령어 실행에 필요한 1 사이클이 필요 평균 기억장치 액세스 시간 평균 액세스 시간 = 1x 0.8 + (1+10) x 0.2 = 0.8 + 2.2 = 3.0 [사이클] 컴퓨터구조

캐쉬와 주 메모리 사이의 블럭 전송 그림: 캐쉬와 주 메모리 사이의 블럭 전송 컴퓨터구조

주 메모리와 캐쉬와의 인터페이스 주 메모리에는 2n 개의 메모리로 이루어지며, 각 메모리는 n비트로 이루어진 주소로 액세스 됨 26 비트로 이루어진 주 메모리의 크기는 64M 개 주 메모리와 캐시로의 전송은 K 단어(words)의 블럭(block)으로 이동 주 메모리에는 2n/K 개의 블럭이 존재 전송되어진 블럭은 캐쉬에 K 단어로 이루어진 슬롯(slot)에 저장 주 메모리로부터 전송된 하나의 블록은 캐쉬의 한 슬롯에 적재됨 주 메모리의 전체 블럭의 수는 캐쉬 내의 슬롯의 수보다 매우 크기 때문에 어느 순간에 캐쉬에는 주 메모리의 일부 블럭 만이 저장됨 따라서 캐쉬의 슬롯의 수가 주 메모리 블럭의 수보다 훨씬 적으므로 각 슬롯은 여러 블럭에 의해 공유 여러 블럭을 구분해 주기 위하여 태그(tag) 사용 태그는 주기억장치 주소의 일부 컴퓨터구조

캐쉬의 설계시 고려 사항 캐쉬 사상(Mapping) 방법 주 메모리와 캐쉬 사이의 사상(Mapping)하는 방법 캐쉬 내용(블럭) 구분(block identification) 방법 캐쉬 교체 알고리즘 캐쉬 쓰는 방식 전송되어지는 블럭의 크기 캐쉬의 개수와 타입 캐쉬 사상(Mapping) 방법 ;주 메모리의 블럭을 캐쉬의 슬롯에 어떻게 사상하는 가에 대한 알고리즘 1) 직접(Direct) 사상방식 2) 연관(Associative)사상방식 3) 세트연관(set-associative) 사상 방식 컴퓨터구조

- 주 메모리의 각 블럭은 캐쉬에 있는 특정 슬롯에 할당 - i = j modulo C - 주 기억장치의 블럭 번호: j 1) 직접(Direct)사상 방식 - 주 메모리의 각 블럭은 캐쉬에 있는 특정 슬롯에 할당 - i = j modulo C - 주 기억장치의 블럭 번호: j - 캐쉬 슬롯의 수: C개 - 모듈로 연산에 의해 i 번 째 슬롯으로 사상 (예제) 캐쉬의 슬롯의 수가 4 인 경우에 4 개의 슬롯을 공유하는 주 메모리 블럭 슬롯 0에는 블럭 번호 0, 4, 8, 12, ..... 등이 사상됨 슬롯 1에는 블럭 번호 1, 5, 9, 13, ..... 등이 사상됨 슬롯 2에는 블럭 번호 2, 6, 10, 14, .... 등이 사상됨 슬롯 3에는 블럭 번호 3, 7, 11, 15, ..... 등이 사상됨 컴퓨터구조

직접 사상 방식에서 주 메모리 주소를 이용한 캐쉬의 액세스 주 메모리의 주소는 태그 구분자, 슬롯 번호, 단어 구분자의 세 가지 필드로 나누어짐 태그 구분자는 하나의 슬롯이 여러 개의 블럭에 의해 공유되어 지므로, 이들 블럭을 구분하는데 사용 - 슬롯 번호 필드는 참조될 주소를 가지는 캐쉬 내의 물리적 슬롯을 명시 단어 구분자는 슬롯에 있는 단어 중에 CPU에서 필요한 특정 단어를 구분 하는데 사용 그림: 직접 사상방식에서 주 메모리 주소의 각 필드 구분 컴퓨터구조

그림:직접 사상 방식에 의한 캐쉬와 주 메모리 사이의 블럭의 적재 컴퓨터구조

16 비트의 물리주소가 워드 필드 4 비트, 블럭(혹은 슬롯) 필드가 7 비트, 앞의 그림에서 16 비트의 물리주소가 워드 필드 4 비트, 블럭(혹은 슬롯) 필드가 7 비트, 그리고 태그 필드를 위하여 나머지 5 비트를 사용 이 메모리는 216 = 64 K 개의 메모리 주소공간을 가짐 워드 필드가 4 비트 = 하나의 블럭에는 16 바이트의 데이터 캐쉬는 128 개의 블럭 용량을 가짐. 16 비트의 주소공간 = 216 = 64K 개 각 블록의 워드는 4 비트로 구분 => 1블럭 = 16 바이트 1 블럭 = 16 개의 주소 공간 주 메모리의 전체 블록 수 = 64k/16 = 4 K 개 주 메모리의 용량 = 64 KB 캐쉬 용량 = 128 블럭 = 2k 바이트 컴퓨터구조

직접 사상 방식을 사용할 경우, 주 메모리 주소의 각 필드를 구분하여라. (풀이) [예제 7-3] - 주 메모리 크기가 1 M 개( 20 주소 비트) - 블럭의 크기가 8 바이트 - 캐쉬의 슬롯 크기가 1 K 직접 사상 방식을 사용할 경우, 주 메모리 주소의 각 필드를 구분하여라. (풀이) 주 기억장치의 크기가 1 M 개이므로 각 메모리를 지정하기 위하여 20 개의 주소선이 필요 - 각 주소는 20 비트의 주소로 액세스 - 블럭의 크기가 8 바이트이므로, 단어의 구분은 3 비트로 가능 캐쉬의 슬롯의 수가 1 K 개 이므로, 각 슬롯을 구분하기 위하여 10 비트가 필요 - 따라서 전체 20 비트 중에 나머지 7 비트는 태그 비트로 사용 그림: 예제의 주소 필드 구분 컴퓨터구조

메모리 주소 $ABCDE에 위치한 단어는 캐쉬의 어느 위치에 저장되는가? 주 메모리의 주소가 16진법으로 표현되어질 경우 메모리 주소 $ABCDE에 위치한 단어는 캐쉬의 어느 위치에 저장되는가? $ABCDE = 1010101 1110011011 110 - 슬롯 번호는 $39B, 단어는 6 번째, 그리고 태그 번호는 $55 직접 사상 방식의 장점 1) 구현하기 쉬움 2) 구현함에 있어 상대적으로 적은 비용 3) 원하는 주 메모리의 데이터가 캐쉬 어디에 있는지 결정하기 쉬움 직접 사상 방식의 단점 1) 각 주 메모리의 블록이 특정 캐쉬 슬롯에만 사상됨 2) 따라서 같은 슬롯 번호에 반복적으로 블럭들이 참조될 가능성이 있음 3) 이 경우에 이들 블럭들은 끊임없이 캐쉬로부터(로) in/out을 반복함으로 캐쉬 적중률을 낮춤 컴퓨터구조

[겸손의 그릇은] 교만은 많은 지식을 무용지물로 만들고 겸손은 적은 지식으로도 풍요롭게 합니다. 많은 지식보다는 겸손이 낫고 겸손한 침묵보다는 행동이 낫습니다. 쉬운 것을 어렵게 말하는 것은 교만의 사치요, 어려운 것을 쉽게 말하는 것은 겸손의 저축입니다. 오만한 마음에는 더 이상 채울 것이 없으나 겸손의 그릇은 늘 비어 있어서 채울 준비가 되어 있습니다. 오만의 그릇은 쏟아 보면 나올 것이 없으나 겸손의 그릇은 빈 그릇에서도 지략이 철철 넘쳐 쏟아집니다. - 「행복쌓기 365일」/ 현상수 컴퓨터구조

완전연관사상 (Fully Associative Mapping) 방식 주 메모리의 블럭이 캐쉬의 특정 슬롯에 항상 지정되어 적재되어지지 않고, 비어 있는 슬롯 아무 곳으로나 적재 - 캐쉬의 적중률을 높일 수 있음 - 주 메모리의 블록은 캐쉬의 어느 슬롯으로나 사상이 가능 - 캐쉬의 효율적인 동작을 위하여 다음과 같은 선택을 따름 * 유효비트(valid bit)가 0 인 슬롯을 선택 유효비트가 0 인 것은 현재 해당 슬롯은 비어있음을 나타냄 * 모든 슬롯의 유효 비트가 1인 경우에는 교체되어질 슬롯을 선택 - 이 방식에서 캐쉬 내의 슬롯 번호는 의미가 없음 - 주 메모리의 주소는 태그 필드와 단어 필드만 사용 그림: 연관 사상 방식에서의 주 메모리 필드의 구분 컴퓨터구조

완전 연관사상 방식에서 원하는 캐쉬 슬롯을 찾는 방법 원하는 캐쉬 블럭은 캐쉬 슬롯의 어느 곳에도 적재 가능하므로, 모든 슬롯을 비교 - 먼저 주소의 태그 필드를 사용하여 모든 슬롯의 태그 필드를 비교 비교하기 전에 유효 비트가 1인 것을 확인한 후, 유효비트가 1인 슬롯만 비교는 비교기(comparator)를 이용하는데, 일반적으로 비교기는 XNOR 게이트 사용 - XNOR 게이트는 비교되는 두 비트가 같으면 1을 출력하는 게이트 - 태그 필드가 일치하는 슬롯을 찾은 후에는 단어 필드의 비트를 사용 (장점) 캐쉬로 적재되는 유연성이 좋음 (단점) * 캐쉬 내에 있는 모든 슬롯을 비교해야 하는 문제점을 가짐 * 구현하는 비용 즉 태그를 검사하는 회로가 복잡해지며, 태그를 비교하는 시간이 오래 걸림 컴퓨터구조

[예제] 주 메모리 주소 $ABCDE에 위치한 단어 워드 필드 = 3 비트 태그 필드 = 17 비트 - 캐쉬 슬롯 번호는 비어 있는 슬롯으로 사상되어지므로 알 수 없음 - 워드 필드는 6 - 태그 필드는 $1579D 값을 가짐 컴퓨터구조

캐쉬의 태그는? 컴퓨터구조

컴퓨터구조

세트-연관 사상(Set associative mapping) 방식 - 직접 사상 방식에서의 간단함과 연관 사상 방식의 유연성을 조합하는 방식 - 캐쉬를 여러 개(v 개)의 세트로 나누고, 각 세트는 여러 개(k개)의 슬롯을 가짐 - 주 메모리 블럭은 각 세트의 어느 슬롯에도 저장될 수 있는 유연성을 가짐 - 캐쉬 내의 슬롯은 다음과 같이 정해짐 m = v x k i = j modulo v 여기서 i = 캐쉬 세트 번호 k = 하나의 세트 내의 슬롯 수 j = 주 기억장치의 블럭 번호 v = 세트의 수 m = 캐쉬 내의 슬롯의 수 세트의 선택은 직접 사상 방식으로 이루어지고, 그 세트 내에서는 완전 연관 사상 방식으로 사상 - 세트가 X 개의 슬롯을 가지면 X-way 세트-연관 캐쉬 - 오늘날의 대부분 캐쉬 시스템은 2- 혹은 4-way 세트-연관 사상 방식을 사용 컴퓨터구조

주어진 메모리 주소에 대한 내용이 캐쉬에 있는지를 검사하는 과정 세트 연관사상 방식에서 주 메모리 필드의 구분 주어진 메모리 주소에 대한 내용이 캐쉬에 있는지를 검사하는 과정 1) 세트 필드 비트를 통하여 세트를 선택한다. 세트의 선택은 직접사상 방식과 마찬가지로 이루어 짐 2) 선택되어진 세트 내의 유효 비트가 1인 모든 슬롯의 태그를 비교 태그의 비교는 완전연관 사상 방식과 같은 방법으로 이루어 짐 3) 일치하는 슬롯이 있으면 캐쉬 히트이고, 없으면 캐쉬 미스 4) 캐쉬 히트이면 단어 필드의 비트를 이용하여 선택되어진 슬롯에서 해당 단어를 선택. 캐쉬 미스일 경우에는 하위 메모리 계층으로부터 데이터를 캐쉬로 가져 옴 컴퓨터구조

* 세트 비트(s)를 이용하여 S개의 슬롯(2s) 중에 하나를 선택한다. 컴퓨터구조

선택되어진 세트에서 태그 필드를 이용하여 원하는 내용이 있는지를 검사 이 때 v 비트가 1 인 슬롯만 검사 히트인 경우에 단어 필드를 이용하여 원하는 단어를 선택 컴퓨터구조

[예제 7-4] 캐쉬 전체에 1024 개의 블럭이 있는데, 4-way 세트연관 세트를 가정한다면 다음과 같은 사실을 알 수 있음 4-Way = 하나의 세트에 4 개의 슬롯(블럭)을 가짐 1) 세트의 개수 = 256 개 세트의 개수 = 1024/4 2) 따라서 워드 필드 = 3 비트(하나의 블록은 8 개의 단어로 이루어짐) 세트 필드 = 8 비트 태그 필드 = 9 비트 앞의 예제에서 사용했던 다음의 메모리 주소를 세트연관사상 방식으로 사상하면 다음과 같음 ABCDEH = 101010111 10011011 110 태그 세트 워드 따라서 세트 번호는 9BH, 워드 옵셋은 6H, 마지막으로 태그는 157H 컴퓨터구조

[예제] 세트-연관 사상 캐쉬에서의 적중 검사 1111 1111 0111 1111 1111 1100 0000 0000 0000 0000 0000 0100 1010 0011 1111 1111 1111 0100 (4) 0000 0001 0000 0000 0000 0100 컴퓨터구조

(1) 캐쉬 적중: 현재 1FFF번 세트의 두 번째 슬롯(데이터 = 77777777)에 적재되어 있음. [풀이] (1) 캐쉬 적중: 현재 1FFF번 세트의 두 번째 슬롯(데이터 = 77777777)에 적재되어 있음. (2) 캐쉬 적중: 현재 0001번 세트의 첫 번째 슬롯(데이터 = 11223344)에 적재되어 있음. (3) 캐쉬 미스: 1FFD번 세트에는 태그가 1FF인 블록만 적재되어 있음. (4) 캐쉬 미스 : 0001번 세트에는 태그가 000인 블록만 적재되어 있음. 컴퓨터구조

직접사상 방식 (예제) 주기억장치: 16 MB 블록 = 4 바이트 캐쉬의 크기 = 64K 바이트 컴퓨터구조

[예제] 직접 사상 캐쉬에서의 적중 검사 ---------------------------------- (1) FFFFF4 (2) 8C0004 (3) FEFFFC (4) 000004 [풀이] (1) 캐쉬 적중 : 현재 3FED번 슬롯에 적재되어 있음. (데이터 = 87654321) (2) 캐쉬 미스 : 이 블록이 적재될 수 있는 0001번 슬롯의 현재 태그는 00임. (3) 캐쉬 미스 : 이 블록이 적재될 수 있는 3FFF번 슬롯의 현재 태그는 FF임. (4) 캐쉬 적중 : 현재 0001번 슬롯에 적재되어 있음. (데이터 = 11223344) 컴퓨터구조