CS

How to Locate a Block in the Cache? - direct mapping cache에서는 index를 찾고, index의 valid bit와 tag를 확인한다. - set associative cache에서는 set을 찾고, 해당 set 내의 모든 블록에 대해 valid bit와 tag를 확인한다. N-way associtaive cache에서는 set 내의 n개의 블록을 비교해야 한다. 예를 들어, 1024개의 1word block으로 구성된 4-way set associative cache는, 1 word block의 byte offset에 2bit, 1024/4 (256=2^8)에 8bit, tag에는 22bit를 할당한다. 만약 miss가 발생한다면, 요청한 데이터 블록이 캐..

** 가정 ** 32비트 주소 (vs 5비트 주소), 캐시의 크기가 2^10 (vs 2^3), 각 entry의 크기는 2^2 bytes Byte offset 각 캐시 블록은 22B의 데이터를 포함할 수 있다. 데이터 항목의 기본 단위는 Byte이다. 캐시 블록 내에서 데이터의 Byte를 식별해야 한다. 주소의 앞 20bit는 tag, 10bit는 index로 사용된다. 마지막 2bit는 Byte offset으로 사용된다. 데이터의 Byte가 참조되면, 참조된 데이터와 인접한 데이터를 포함한 22Byte의 데이터를 메모리에서 캐시로 가져온다. 이 동작은 캐시가 spatial locality(공간적 지역성)을 활용할 수 있도록 한다. 주소가 주어지면, 10bit의 index값으로 대상 캐시 블록에 접근한다...

reader-writer 문제에서 한쪽을 선호하는 방향으로 구현하는 것은 reader를 선호하는 방법과 writer를 선호하는 방법이 존재한다. 먼저 reader prefer 를 살펴보자. reader prefer는 대기하는 reader가 없을 때서야 writer가 출력될 수 있다. 따라서 writer의 mutex를 reader가 가지고 있다가, 실행중인(또는 대기중인) reader의 개수가 0이 될 때 놔준다. reader-prefer : reader while (alive) { pthread_mutex_lock(&mutex); read_count++; if(read_count == 1){ pthread_mutex_lock(&wmutex); } pthread_mutex_unlock(&mutex); //..

캐시의 각 entry에는 index + valid bit + tag + data로 구성된다. 캐시에는 8개의 entry가 있고, 각각 3bit의 index를 기반으로 식별된다. 1bit의 V에는 entry의 정보가 valid한지 여부를 나타낸다. 데이터가 해당 엔트리에 배치되면 해당 데이터를 지칭하기 위해 2bit의 tag가 설정된다. 처음에는 캐시가 비어있기에, 처음의 모든 valid bit는 N으로 설정된다. 태그와 데이터도 비어있다. 참조된 데이터에 캐시가 있는 경우, hit가 발생하고 데이터는 캐시로부터 제공된다. 없는 경우엔 miss가 발생하고 기존 데이터는 메인메모리에서 복사된, 참조된 데이터로 대체된다. 만약 데이터 10110(2)이 요청되면 index가 110인 캐시 블록에 배치될 것이다...

뮤텍스는 락 획득을 시도한 순서대로 접근이 가능한 FIFO 형식으로 작동한다. reader는 동시에 출력이 가능하지만, writer는 동시 출력이 불가하기에 출력중인 reader가 있다면 writer의 출력은 막아준다. 동시에, 대기중인 writer가 있다면 reader는 접근하면 안된다. 따라서 뮤텍스 3개를 사용하여 구현할 수 있었다. Reader while (alive) { pthread_mutex_lock(&mutex); pthread_mutex_lock(&rmutex); read_count++; if(read_count == 1){ pthread_mutex_lock(&wmutex); } pthread_mutex_unlock(&rmutex); pthread_mutex_unlock(&mutex); ..

모든 데이터(위 이미지에서, Instruction memory와 Data memory)가 컴퓨터의 메모리에 저장된다. load와 store 명령어는 메모리에 액세스하여 데이터를 읽거나 쓴다. 이상적으로는, 프로그래머들은 무제한이고 빠른 메모리를 바란다. 현재의 메모리들인 SRAM, DRAM, SSD, HDD를 비교하면, 가격 : SRAM > DRAM > SSD > HDD 성능 : SRAM > DRAM > SSD > HDD 용량 : HDD > SSD > DRAM > SRAM 이 된다. 크고 빠른 메모리를 동시에 제공하는 단일 메모리는 없지만, 현대 컴퓨터는 크고 빠른 메모리의 illusion을 제공한다. 메모리 시스템은 계층(hierarchy)적인 방식으로 다양한 메모리 기술을 포함한다. - 가장 낮은 레..

이전 장에서, data forwarding만으로 data hazard를 해결할 수 없음을 보았다. 따라서 pipeline을 정지시키는 stall을 사용한다. 이는 시간을 낭비하며 아무런 작업을 수행하지 않는 과정이다. ID단계에서 and 명령어와 IF단계에서 or명령어를 1CC동안 prevent하고, 파이프라인에 nop(아무 동작을 하지 않는 명령어)를 삽입해서 진행시킨다. 이렇게 1CC를 기다린 후, data forwarding을 통해 문제를 해결할 수 있다. and와 or을 1CC동안 진행하지 못하게 막는다. (prevent) IF/ID 파이프라인 레지스터 변경을 막으면 and는 다시 ID단계로 들어간다. PC의 변경을 막으면 or은 다시 IF단계로 들어간다. 즉, 레지스터에 상태를 기록하는 것을 막..

만약 아래와 같은 명령어가 실행됐다고 가정하자. sub $2, $1, $3 and $12, $2, $5 이 때, $1 - $3 값이 -20이라 할 때, and 연산에서 $2는 -20을 기대하지만 아직 sub 연산이 끝나지 않았으므로 10을 가져온다. 이 문제를 Data Hazard 라고 한다. 이를 위한 해결책으로 Data Forwarding을 사용할 수 있다. sub 명령의 EX/MEM 레지스터 값을 and 연산의 Rs 포트로 보낼 수 있다. 즉, 다른 명령의 레지스터를 ALU의 소스로 사용하는 것이다. datapath는 data hazard를 감지할 수 있어야 한다. 즉, destination register가 source register로 사용되는지 확인해야 한다. 여기서 and 연산의 경우, su..