컴퓨터구조

[컴퓨터 구조] 제 5장. 메모리 계층 사용

촙발자 2023. 4. 17. 22:17

Principle of Locality

  • 프로그램들은 그들이 최근에 사용한 data와 instructions과 똑같거나 근처의 주소들을 사용하는 경향이 있습니다.

 

  • Temporal locality
    • item을 썼다면, 짧은 시간 안에 다시 참조될 경향이 있다는 것입니다.
    • e.g.) 반복문 안에 있는 instructions

Temporal locality

  • Spatial locality
    • item을 썼다면, 가까운 주소지를 읽을 확률이 높다는 뜻입니다. (순차적)
      → 다른 item을 참조
    • 배열, 순차적인 instruction 접근

Spatial locality

 

 

Principle of Locality: Example

예를 한 번 봅시다.

 

위의 코드가 있을때

sum변수가 Temporal Locality

a 배열이 Spatial locality가 되는 것입니다.

 

 

Taking Advantage of Locality

 

우린 principle of Locality를 이용하여 Memory hierarchy를 구현하였습니다.

  • 메모리 계층은 다른 속도들과 크기들을 가진 다양한 레벨들의 메모리로 구성되어 있습니다.
  • 더 빠른 메모리일수록 더 비싸지만 더 작습니다.
  • 가장 빠른 것을 processor와 가깝게 합니다.

 

 

Memory hierarachy

  • data도 비슷하게 계층적입니다.
    • 모든 데이터들은 가장 낮은 레벨에 저장되어 있습니다.
    • → 즉, 메모리상에 전부 올릴 필요가 없습니다.
    • 데이터가 프로세서에서 멀어질수록 더 긴 access time을 가집니다.
    • 프로세서와 가까운 레벨에 있는 데이터들은 Lower level의 부분집합입니다. 즉, 상위 레벨에 있는 데이터들은 하위 레벨에도 있는 것입니다.
  • 메모리 계층은 다양한 레벨들로 구성될 수 있습니다.
    • 데이터는 한 번에 오직 인접한 두 레벨끼리만 복사됩니다.
    • Upper level (프로세서와 가까운 것)은 Lower level보다 더 작고 더 비싸고 빠릅니다.
    • e.g.) lower level : main memory(DRAM) 
              upper level : cache(SRAM)
    • 메모리 글에서는 SRAM과 DRAM만을 고려할 것입니다.

 

 

Memory Hierarchy Levels

  • 두 레벨 계층에 있는 정보(데이터)의 가장 작은 단위를 Block 혹은 Line이라고 부릅니다.
  • 만약 프로세서가 요구한 data가 Upper level에 존재한다면 이것을 hit이라고 부릅니다.
  • 만약 데이터가 upper level에 있지 않다면 Miss라고 합니다.

 

용어 정리

  • Hit rate (ratio) : hits / accesses
  • Miss rate : misses / accesses
  • Hit time : upper level에 access 하는 시간
  • Miss penalty : lower에서 upper로 복사되는 시간 + upper에서 processor로 가는 시간

 

 

Memory System

upper에서 lower로 내려갈수록 access time이 엄청나게 늘어나는 게 보이실 겁니다.

위로 갈수록 용량은 줄어들고 Access time은 짧아집니다.

 

 

Memory Technologies

오늘날 메모리 계층에서 주로 사용되는 4가지 기술들이 있습니다.

  1. SRAM (static random access memory)는 프로세서에 가깝습니다. (cache)
  2. DRAM (dynamic random access memory)는 main memory에 사용됩니다.
  3. Flash memory는 비휘발성 메모리입니다.
  4. Magnetic disk는 계층에서 가장 크고 느린 레벨에서 사용됩니다.

1 GHz = 1 / 1ns이므로, SRAM은 0.4 Ghz~2 Ghz가 됩니다.

아무튼 SRAM은 DRAM에 비해서 약 100배가량 빠르다고 볼 수 있습니다.

다만 빠르면 빨라질수록 가격도 올라가는 모습도 보입니다.

 

 

Memory System: Cache

  • 캐시는 하드웨어에서 자동으로 관리되는 작고 빠른 SRAM기반의 메모리입니다.
    • 캐시메모리는 메인 메모리에서 자주 사용되는 block들을 가지고 있습니다.
      → 자주 사용되는 것을 캐시에 올려놔야 속도의 이득을 볼 수 있겠죠?
    • 캐쉬 메모리는 multi-level 메모리 구조를 가지고 있습니다. (e.g., L1, L2, L3 caches)

 

Simple Cache

  • 우린 매우 간단한 캐시를 고려할 것입니다.
    • Processor는 한 번에 하나의 word를 요구하고 block은 word 한 개로 이루어져 있다고 합니다.

위의 그림에서 Processor가 Xn을 찾는다고 가정합니다.

Xn을 참조하기 전에는 Cache에 Xn이 존재하지 않기에 Miss가 나고 main memory에서 Xn을 찾을 겁니다.

이후 캐시에는 Xn이 새로 업데이트가 됩니다.

 

 

Direct Mapped Cache

  • 이 방법은 메모리에 있는 word의 주소를 cache에 할당하는 가장 간단한 방법입니다.
    • 이 Cache 구조를 direct mapped라고 합니다.
    • 모든 Direct-mapped cache들은 block을 찾기 위해 이 mapping을 사용합니다.

(Block address) modulo (Number of blocks in the cache)

Direct mapped

캐시의 001 에는 처음엔 메모리주소00001에 있던 값이 들어가고 마지막엔 11001 번지수에 있는 값이 저장되는 것입니다.

 

마찬가지로 101 에는 끝에 메모리 11101 번지수에 있는 값이 들어가겠죠.

 

하지만 이러한 방식은 단점들이 존재합니다.

 

일단 하나는 빈 공간이 존재합니다.

위의 그림에서 7개의 공간을 사용하지 않는 것이 보이죠?

이는 뒤에 후술 할 Associative Mapping에서 꽤나 해결이 됩니다.

 

 

Tags and Valid Bits

캐시에 저장된 데이터가 어떤 block에서 왔는지 어떻게 알 수 있을까요?

  • 각 cache는 어느 메모리에서 데이터가 왔는지에 관한 정보를 포함하고 있습니다.
    • 이는 Tag라는 상위 비트들이 담당하고 있습니다.
    • 위의 예시에서는 11001에서 11 이 tag인 거죠.

  • 또한 우리는 cache block에 있는 정보가 유효한 정보인지 아닌지 확인해야 합니다.
    • 이 역할은 valid bit가 담당합니다.
    • 예를 들어, valid bit가 1이면 유효, 0이면 유효하지 않은 정보이며 처음엔 0으로 시작하게 됩니다.

아래에서, 예를 들어 보도록 하겠습니다.

Accessing a Cache

처음엔 이 상태로 valid bit도 전부 0인 상태이고 cache가 비어있습니다.

 

캐시가 메모리 9개에 접근한다고 해봅시다.

 

조건 1) Direct mapped Cache

조건 2) 캐쉬가 8개 이므로 하위 3비트로 block number 구별

조건 3) 첫 번째 참조는 무조건 Miss로. (처음엔 Cache가 비어있으니까 다 Miss인 것입니다.)

 

10110과 11010 은 둘 다 valid bit가 0이므로 Miss입니다.

 

10110과 11010 이 valid bit도 1이고 Tag도 일치하기 때문에 Hit입니다.

10000과 00011 은 둘 다 valid bit가 0이므로 Miss입니다.

10000 은 valid bit도 1이고 Tag도 일치하기 때문에 Hit입니다.

10010 은 cache의 010을 보면 Valid bit는 1이지만 tag가 다르기에 Miss가 나옵니다.

 

Address Subdivision

Reference address는 3개로 나뉩니다.

  • Tag field : Cache의 Tag field 값과 비교하기 위해 사용합니다.
  • Cache index : block을 선택합니다.
  • Byte offset : word에서 특정 byte를 지정합니다. (word는 4byte로 이루어져 있기 때문에 word안에서 몇 번째 byte인지 특정하는 것)

  1. Cache index를 이용하여 cache의 index로 이동합니다.
  2. tag field가 일치하고, Valid 값이 1이라면 Byte offset에 관한 Data를 반환합니다.

Block Size는 4 Byte이고, Cache index는 10 bit이므로, Cache size는 2^10 * 4 byte = 4KB입니다.

 

 

Cache Size

32비트 address에 cache의 크기가 2^n blocks, block 크기가 2^m words라고 가정해 봅시다.

 

Cache index는 N개의 비트가 필요하고, offset은 m+2개의 비트가 필요하겠죠?

  • word는 4byte이므로 m+2비트.

 

 

 

  • Tag Size : 32 - (n + m +2)
  • Total bits of cache : 2^n * (block size + tag size + valid field size)
  • The number of bits : 2^n * (2^m * 32 + (32-n-m-2) + 1) = 2^n * (2^m× 32 + 31-n-m)
    • block 개수 * (block size + tag size + valid field size)

 

6 byte인 block 64개로 구성된 cache를 예로 들어봅시다.

  1. block이 64개로, cache index bit는 6개입니다.
  2. block size가 16byte이므로 byte offset은 4개의 비트로 이루어져 있습니다.

 

1200 번지수는 cache의 어디에 mapping 되는지 확인해 봅시다.

  1. block size가 16 bytes이므로, Block address는 1200/16 = 75입니다.
  2. 75 % 64 = 11이므로 block number는 11이 됩니다.