Memory Hierarchy

이동윤·2024년 11월 11일
0

다중 레벨의 메모리에는 다양한 속도와 크기를 가진 메모리들이 있다.

  • 메모리: 데이터를 저장할 수 있는 모든 매체 (예: DRAM, 디스크 등)

위로 갈수록 단위 가격당 공간이 작아짐

secondary <-> primary

primary = CPU가 직접 접근을 할 수 있는 메모리

  • Ex) instruction에 메모리 주소를 할당하거나, 레지스터의 특정이름을 사용할 수 있는 것과 같음

Secondary : CPU가 직접 접근을 할 수 없음

NVRAM : 사라지지 않는다는 장점, DRAM보다는 느리고 비쌈

Cache Memory Concept

Cache memory

  • 메인메모리보다 더 빠르지만 작은 메모리를 캐시라고 하며 메인메모리의 느린 접근 시간을 개선하기 위해 데이터를 임시로 저장합니다.

  • 투명성 (존재가 외부로 드러나지 않는다는 의미) CPU는 캐시라는게 있다는걸 모른다 (몰라야한다) CPU를 설계할때 메모리가 있다는걸

CPU가 요청을 할때 CPU는 자기가 메인메모리에 요청한다고 알고있지만 사실은 캐시가 중간에 뺏어오는 그런 느낌 (있는듯없는듯) , 캐시들끼리도 서로의 존재를 몰라야한다

사용자나 프로그램이 캐시의 존재를 인식하지 않아도 캐시가 자동으로 동작하여 성능을 향상시킨다
구체적으로, 캐시는 주 메모리에 접근하는 빈도를 줄이고 데이터 접근 속도를 높이기 위해 자주 사용되는 데이터를 일시적으로 저장하는 메모리입니다. 프로그램은 캐시가 존재하는지, 어떤 데이터를 캐시에 저장하고 있는지 알 필요가 없으며, 단지 주 메모리에 접근하듯이 데이터를 요청하면 캐시가 자동으로 적절한 데이터를 반환하거나, 필요시 주 메모리에서 데이터를 가져와 캐시에 저장한 후 전달합니다.

따라서 캐시의 투명성 덕분에 개발자는 캐시의 존재 여부와 관계없이 동일한 방식으로 메모리에 접근할 수 있습니다

Underlying principle of Cache
•
Principle of Locality(프로그램은 같은 데이터를 접근하는 경향이 있다. 한번 읽은 데이터를 또 읽는다는 의미)

캐시의 기본 원리

  • Principle of Locality : 프로그램이 실행되는 동안 특정 데이터에 반복적으로 접근할 가능성이 높다는 성질입니다. 이를 통해 캐시는 성능을 최적화할 수 있습니다
  • Temporal Locality : 특정 데이터에 한 번 접근하면, 가까운 미래에 다시 그 데이터에 접근할 가능성이 높다는 원리입니다. 예를 들어, 반복문 내의 변수는 반복적으로 사용되므로 캐시에 저장해 두면 접근 시간을 단축할 수 있습니다.
  • Spatial Locality : 특정 데이터에 접근하면, 그 데이터의 주변 데이터도 곧 접근될 가능성이 높다는 원리입니다. 예를 들어, 배열의 요소에 순차적으로 접근할 때, 첫 번째 요소에 접근한 후 그 옆의 요소들도 접근할 가능성이 높습니다.

캐시 메모리는 더 낮은 레벨의 메모리보다 작다

• 캐시 메모리는 주 메모리나 디스크와 같은 더 낮은 레벨의 메모리에 비해 용량이 작습니다. 따라서, 모든 데이터를 캐시에 저장할 수 없고 자주 사용될 가능성이 높은 일부 데이터만을 선택적으로 캐시에 저장해야 합니다.

• 이 선택적인 저장 방식은 시간적 및 공간적 지역성 원리에 따라 이루어집니다. 프로그램이 자주 접근하는 데이터를 우선적으로 캐시에 배치하여 접근 속도를 최적화합니다

Cache Terminololgy

  • line(or Block) :Minimum unit of information
    캐시가 한번에 읽고 쓰는 단위가 꼭 Double Word인건 아니다

  • Hit :When data is present in the upper level
    프로세서가 원하는 데이터가 캐시에 존재하면 Hit 아니면 Miss

  • Hit rate (hit ratio) 메모리에 접근할 때, 필요한 데이터가 캐시에 이미 존재하여 Hit 일 비율을 말합니다.

  • Miss, miss rate

  • Hit time : Time to access the upper level (including the time to determine hit or miss)
    히트가 되서 다 처리하는 시간 (작을수록 좋다)

  • Miss penalty : Time to copy a block from the lower level
    못맞췃으니까 low level로 직접가서 갖고오는데 걸리는 시간

  • Replace and transfer data

Cache access

  • Assume that:
    • CPU requests one word at a time
    • Block size is one word
  • Memory access: X1, …, Xn–1, Xn (메모리 주소값)

  • Cache placement issue

Direct-mapped Cache

특정메모리에 있는 데이터가 캐시에 올라갈때 메모리 주소를 캐시 슬롯 위치로 매핑하여(function 으로 가공) , 특정 메모리 블록이 캐시의 고정된 위치에만 저장될 수 있게 하는 방식입니다

-> 즉, 하나의 메모리 블록은 캐시에 단 하나의 위치에만 저장될 수 있습니다.

  • 캐시 슬롯 결정 방식

    • 캐시 슬롯은 (word address) % (캐시 블록의 개수)로 결정됩니다.
    • 캐시 블록의 개수는 캐시 메모리가 가질 수 있는 고정된 블록의 수를 의미합니다.

Direct-mapped Cache에서 캐시 블록의 수는 2의 제곱수여야 한다
이로 인해 메모리 주소의 일부 비트만으로도 캐시 위치를 쉽게 구할 수 있습니다.

EX) 예를 들어, 8개의 캐시 블록이 있다고 가정하면, 메모리 주소를 8로 나눈 나머지가 그 블록의 위치가 됩니다.

  • Number of Cache block : 8
  • 00001 (1) , 01001 (9), 10001 (17), 11001 (25) % 8 : 001(1)

Tag & Valid

Direct-mapped Cache에서는 여러 메모리 블록이 하나의 캐시 슬롯에 매핑될 수 있습니다.
예를 들어, 001(1)번 슬롯에 00001 , 01001, 10001, 11001 주소의 메모리 블록들이 모두 매핑될 수 있습니다.

이렇게 여러 블록이 동일한 캐시 슬롯에 매핑될 수 있기 때문에, 캐시에 들어온 블록이 실제로 어느 메모리 주소에서 온 것인지 확인할 필요가 있습니다.

  • Tags (태그) : 태그는 메모리 주소의 상위 비트(high-order bits)로 구성되며, 이 태그 값을 통해 같은 슬롯에 들어온 여러 블록을 구분할 수 있습니다. 실제로는 태그의 비트수는 매우 크다

  • Valid bit (유효 비트) : 해당 캐시 슬롯에 저장된 데이터가 유효한지를 나타내는 비트입니다

그림상에는 001 과 101을 제외한 공간이 비워져있지만, 사실은 랜덤으로 초기화된 garbage값이 들어가있다. 따라서 그 값들이 실제로 타당한 값인지 확인하기 위해서이다

value + tag + valid를 모두 합친것이 Cache다!

Accessing a Cache

Address Subdivision (20`00)

  • Address is divided into tag part and index part

    • tag part : 52 bits (캐시의 주소를 제외한 나머지)
    • index part : 10 bits
    • byte offset : 2 bits

세상의 모든 cpu들은 개별 바이트를 구분 및 지칭할 수 있다는 능력을 가져 byte-addressable하다

data를 4byte로 가정했을때, 이 데이터를 지칭하려면 00,01,10,11 총 4개가 필요하다
그럼 offset으로는 2비트만 있으면 표현이 가능하다는 것

또한 현재 index의 갯수가 1024개이므로 index로는 10비트만 있으면 된다

또는 이렇게 생각할 수 있다

Data의 갯수는 1024개, 그리고 개당 4byte이므로 한바이트짜리가 4096개 있다.
그렇다면 4096개 중 하나를 특정하기 위해선 2의 12승이필요하므로 총 12비트가 필요하다

비트는 특정 바이트를 가리키는데 소비되는 자원이다!

Total number of bits in the cache

  • n: number of index bits
  • m: 2^m is the number of words (m=0 if 1 word in a line)

n = 10
m = 0

Block Size and Miss Rate

  • Cache Size = Block Size × Number of Blocks

  • Block Size : 캐시가 한번에 읽고 쓰는 데이터 단위

같은 캐시 크기에서 Block Size가 작아진다는 것은 한 블록에 저장되는 데이터의 양이 줄어든다는 것을 의미한다

하지만, 같은 캐시 크기를 유지하기 위해 더 많은 블록(라인)을 가질 수 있습니다.

블록 크기가 작을수록 블록의 개수가 많아지므로, 캐시를 세로로 길게(라인 수가 많게) 설계하는 효과를 갖게 됩니다.

locality 심화

1. Spatial Locality(공간 지역성)의 개념

Spatial Locality(공간 지역성)은 프로그램이 특정 메모리 주소를 읽거나 쓸 때, 그 근처 주소도 곧 읽거나 쓸 가능성이 높다는 메모리 접근 패턴을 말합니다.

프로그램이 한 번 읽은 메모리 데이터의 연속적인 데이터 범위를 자주 사용합니다

2. Temporal Locality(시간 지역성)란?

Temporal Locality(시간 지역성)은 "최근에 접근한 데이터는 다시 접근될 가능성이 높다"는 메모리 접근 패턴을 의미합니다.

즉, 한 번 사용한 데이터는 가까운 시간 내에 다시 사용될 확률이 높다는 특성입니다.
Temporal Locality를 잘 활용하려면 최근 사용한 데이터를 가능한 많이 캐시에 저장해 두는 것이 중요합니다.

블록 크기가 작을 때

캐시 안에 작은 상자를 많이 두는 것과 같습니다. 다양한 데이터를 저장할 수 있어서 최근 사용한 데이터(Temporal Locality)를 유지하기 쉽습니다.

블록 크기가 클 때

캐시 안에 큰 상자를 몇 개 두는 것과 같습니다. 한 상자에 많은 데이터를 담을 수 있지만, 필요한 데이터 외에 불필요한 데이터도 같이 들어옵니다. 상자 수가 적으니 다른 데이터(Temporal Locality를 가진 데이터)를 저장할 공간이 줄어들게 됩니다. 대신 Spatial Locality가 커진다

Miss Penalty (미스 패널티)

의미: 캐시(Cache)에서 데이터를 찾지 못했을 때 발생하는 시간적 손실.
캐시 미스(Cache Miss) 발생 시, 필요한 데이터를 메인 메모리(Main Memory)에서 가져와야 하므로 추가 시간이 소요된다.

Miss penalty : Set-up time + transfer time

Set-up time : 캐시가 메모리에 정보(주소, 바이트 등)를 전달하고, 실제 데이터를 전달하기 직전까지의 준비 작업 시간

transfer time : 세팅이 끝난 후 순수하게 데이터를 전송하는데 걸리는 시간

Reducing the miss penalty (by hiding the transfer time)

early-restart : 캐시에서 데이터를 가져오는 동안 전체 블록을 로드하기 전에 필요한 데이터(critical data)를 먼저 CPU에게 전달해 읽을 수 있도록 하는 캐시 최적화 기법입니다. 나머지 데이터는 백그라운드에서 계속 로드합니다.

주로 명령어 캐시(instruction cache)에서 효과적입니다.

critical word first :캐시 미스 발생시 CPU가 당장 필요로 하는 데이터(critical word)를 메모리 블록에서 가장 먼저 가져오는 기법입니다. 이 기법은 CPU의 대기 시간을 최소화하는 데 초점을 둡니다.

주로 데이터 캐시(data cache)에서 효과적입니다.

Write Handling in Cache (쓰기 처리)

1. Write-through Cache

1. 동작 원리

쓰기 작업이 발생하면 캐시와 메인 메모리에 동시에 데이터를 업데이트합니다.
데이터 일관성(Data Consistency)이 항상 유지됩니다.

2. 동작 방식

  • CPU가 캐시에 데이터를 쓰면, 해당 데이터는 즉시 메인 메모리로 반영됩니다.
  • 캐시와 메인 메모리의 데이터는 항상 동기화된 상태를 유지합니다.

3. 장점

  • 데이터 일관성을 보장하여 안정적이다
  • 멀티코어 환경에서 각 CPU가 메모리 데이터에 접근할 때 데이터 충돌 위험이 적음.

4. 단점

  • 메인 메모리에 데이터를 지속적으로 반영하기 때문에 속도가 느려질 수 있음.
  • Write buffer를 사용해 메모리 접근 지연을 최소화하려고 함.

2. Write-back Cache

1.동작 원리

  • 쓰기 작업은 캐시에서만 업데이트되고, 메인 메모리는 즉시 동기화되지 않습니다.
    -메인 메모리는 캐시 블록이 교체될 때(Replacement)만 갱신됩니다.

2.동작 방식

  • 쓰기 작업 후 데이터는 캐시에만 기록되며, 메인 메모리에는 반영되지 않습니다.
  • 해당 캐시 블록이 다른 데이터로 교체될 때만 메인 메모리에 동기화됩니다.

3. 장점

  • 메인 메모리로의 쓰기를 줄여 속도가 빨라짐.
  • 쓰기 동작이 빈번할 때 효율적.

4. 단점

-캐시와 메인 메모리 간 데이터 불일치로 인해 데이터 일관성을 보장하기 어려움.

  • 멀티코어 환경에서 데이터 무효화(invalidate) 작업이 필요함.

Cache Performance

CPU time

Normal execution : includes cache hit time

  • 캐시 히트(Cache hit)가 발생했을 때의 실행 시간을 포함합니다.
  • 이 경우, CPU는 캐시에서 데이터를 바로 읽기 때문에 빠릅니다.

Memory stall cycle: cache miss penalty

  • 캐시 미스(Cache miss) 발생 시, 메인 메모리에서 데이터를 가져오는 데 걸리는 시간(미스 패널티)이 추가됩니다.
  • 이로 인해 CPU 실행이 지연됩니다.

Assume the read and write miss penalties are the same

읽기 및 쓰기 미스 패널티가 동일하다는 가정 하에

Write-through : complication from write buffer

  • 쓰기 작업 시 Write Buffer를 사용하여 데이터를 캐시와 메인 메모리에 동시에 쓰기 때문에 복잡도가 증가합니다.
  • CPU는 Write Buffer에 의해 지연될 가능성이 있습니다.

Write-back : potential stall from sync when a block is replaced

  • 쓰기 작업은 캐시에만 반영되고, 메인 메모리는 캐시 블록 교체 시 동기화됩니다.
  • 메모리 동기화로 인해 지연(Potential Stall)이 발생할 가능성이 있습니다

Associative Cache

Direct-mapped cache: a block can be placed in one location
Fully associative cache: a block can be placed anywhere in the cache
Set associative cache : more than one location, but not anywhere

  1. Direct-mapped Cache
    설명:

Direct-mapped 캐시에서는 각 메모리 블록이 특정 캐시 슬롯(한 위치)에만 매핑됩니다.
예를 들어, Block #4는 항상 특정한 슬롯(예: 슬롯 4)에 저장됩니다.
검색(Search) 과정에서 단일 슬롯만 확인하면 되므로 하드웨어 구현이 간단하고 빠릅니다.
특징:

구현이 간단하며 비용이 낮습니다.
충돌(Conflict)이 자주 발생:
서로 다른 메모리 블록이 동일한 캐시 슬롯에 매핑되면, 기존 데이터가 덮어씌워지는 캐시 미스가 발생합니다.
2. Set Associative Cache
설명:

n-way set associative cache는 하나의 세트(Set) 안에 n개의 슬롯을 가지며, 메모리 블록은 해당 세트 내 어디든 저장될 수 있습니다.
예를 들어, Set #0은 2개의 슬롯(2-way associative cache)을 가지며, Block #0과 Block #4가 해당 세트에 저장됩니다.
검색(Search) 과정에서 세트 내의 모든 슬롯을 확인해야 합니다.
특징:

Direct-mapped와 Fully associative의 절충안으로, 성능과 유연성을 동시에 제공합니다.
충돌(Conflict) 가능성이 줄어들지만, 완전히 제거되지는 않습니다.
하드웨어 복잡성이 약간 증가:
세트 내에서 여러 슬롯을 검색해야 하므로 Direct-mapped보다 구현이 복잡합니다.
3. Fully Associative Cache
설명:

Fully associative 캐시에서는 모든 캐시 슬롯이 하나의 세트로 간주됩니다.
따라서, 메모리 블록은 캐시의 어디에나 저장될 수 있습니다.
검색(Search) 과정에서 모든 슬롯을 확인해야 하므로 시간이 오래 걸립니다.
특징:

가장 유연한 방식:
어떤 블록도 캐시 내 아무 위치에 저장 가능.
충돌(Conflict) 없음:
특정 슬롯에 고정되지 않으므로 캐시 미스 확률이 낮아짐.
하드웨어 비용과 복잡성 증가:
모든 슬롯을 검색해야 하므로 구현이 매우 복잡하며, 검색 속도도 느립니다.

profile
이동윤
이전 포스트

ft_printf (과제 설명)

다음 포스트

Process 과 Program의 모든것

0개의 댓글