Cache 개념과 구현

Cache 

매번 느린 메인 메모리에서 instruction을 가져오는 것이 아닌 프로세서와 메인 메모리 사이에 위치하여 자주 사용하는 명령어를 더 빠르게 가져올 수 있도록 하는 기술이다. instruction을 fetch 할 때, 특히 같은 구간을 반복해서 fetch 할 때, memory안 어떤 주소의 데이터(명령어)가 바뀌지 않는다면 메모리에서 바로 명령어를 가져오는 것이 아닌 좀 더 작고 빠른 장치에서 해당 주소에 해당하는 데이터를 기억해 두었다가 꺼내쓸 수 있는 임시 공간을 만들어서 메모리 접근을 줄인다.

 

고속의 장치는 비싸다. 가격이 비싸거나, 용량이 적거나, 발열이 크다. 다른 조건(가격, 발열)을 동일하게 한다면 고속의 저장 장치는 더 작은 공간을 갖게 된다. 그 말은 즉 모든 메모리의 데이터가 캐시에 들어갈 수 없고, 기준을 나눠 일부 데이터만 캐시에 매핑되어야 한다. 

 

따라서 메모리 접근을 최소화하는 사용하는 목적과 앞선 저장 공간의 한계라는 특성에 따라 캐시를 사용하는 설계에는 어떤 데이터를 보관할 것이고, 어떤 알고리즘으로 데이터를 교체하는 것이 효율적일 것인지, 궁극적으로 메모리 접근을 어떻게 줄일 수 있을지에 대한 고민이 필요하다.

 

Index 와 Tag

앞선 저장 공간의 크기 차이로, 일반적으로 캐시에 메모리의 모든 데이터를 1:1로 넣는 것은 불가능하다. 캐시 되어야 할 데이터를 선별해야 하고 해당 데이터를 어느 공간에 위치시킬 것인지를 결정하는 것이다.

 

index는 액세스 주소의 한 부분을 기준으로, 캐시의 데이터 다발 중 어느 위치에 데이터가 저장되었는지를 나타내는 값이다. '쓰기'시에는 액세스 주소의 인덱스에 해당하는 캐시 위치에 데이터를 쓰고, 다음번 '읽기'시 해당 주소의 같은 부분을 읽어 캐시의 어떤 위치에서 데이터를 꺼내야 하는지 확인하는 것이다.

 

 

index의 위치를 주소에서 byteoffset 2비트를 제외한 하위 4비트로 예를 들면, A와 B 모두 index 값은 1111로 캐시 내 동일한 위치에 저장되게 된다. A를 저장된다고 하면 캐시의 index : 1111 라인에 A의 값 32가 저장되는 것이다.

 

이때 같은 인덱스 값을 갖는 다른 주소 B가 읽기 요청을 했다고 가정해보자. B의 데이터를 캐시의 인덱스 1111의 데이터 값으로 해도 될까? A는 그 값이 32이고, B는 0으로 서로 다른 값이니 캐시 라인 1111의 데이터를 믿어선 안된다. 즉 캐시에 B의 데이터는 없는 것이다. 이를 구별하기 위한 값이 또 필요하다. index와 마찬가지로 주소의 일부분을 값으로 인덱스 라인에 해당하는 캐시 값이 액세스 주소의 데이터가 맞는지 구분한다. 이를 tag값이라고 한다.

 

 

Block

앞선 예시에선 캐시에는 여러 데이터 다발(line)이 있고, 다발의 주소 index와 데이터를 1:1을 매핑하였다. Block은 캐시의 line에 여러 데이터를 담는 것을 말한다. 데이터는 지역성으로 가까운 시간에 참조된 데이터가, 가까운 메모리 위치에 저장된 데이터가, 다시 참조될 가능성이 크다. 한번 메모리를 캐시 할 때 데이터를 하나씩 가져오는 것이 아니라 곧 다시 사용될 것으로 생각되는 근처 데이터까지 한 번에 묶어 가져오는 것이다.

 

이렇게 Block으로 메모리 fetch, 캐시에 저장하게 되면, 앞선 예시의 index로 어떤 line을 확인할 것인지를 위해 index 값을 결정하고, 해당 라인의 어떤 block을 참조할 것인지 다시 확인해야 한다. 이를 위해 block 위치를 표시하기 위한 주소의 offset 비트를 정하고, 주소를 읽었을 때 해당 offset에 위치에 있는 데이터를 확인한다.

각각의 선은 서로 다른 캐시 설정을 말한다. 서로 다른 4가지 설정의 캐시에서 block 사이즈에 따른 miss rate의 변화를 확인한다.

 

이렇게 한 번에 여러 데이터를 fetch 할 경우, 메모리에서 데이터를 하나씩 액세스하는 것보다 더 많은 시간이 걸리지만, 여러 번 데이터를 읽게 되면 메모리 한 번에 가져오는 것이 훨씬 유리하다. 메모리에 접근하는 시간이 접근 후 여러 데이터를 참조하는 시간보다 훨씬 더 크기 때문이다.

 

그렇다고 블록 사이즈가 캐시 성능에 비례하는 것은 아니다. 위 표는 블록 사이즈에 따른 Miss율을 보여준다. Block 사이즈가 커질수록 한 index line에 포함되는 hit 데이터가 많아지니 일반적으로는 miss율이 낮아진다. 단, 한번 miss가 될 때 memory fetch 시간도 더 커지므로 이 실패 손실과 miss 율 감소를 비교해야 한다. 또 블록 사이즈가 매우 크게 되면 블록 내 데이터들의 공간 지역성을 잃게 된다. 극적으로 블록 사이즈를 엄청 크게 키웠다고 가정해보자. 특정 block 사이즈 이상부터는 더 이상 '저장 공간이 가까운' 데이터라는 특성을 잃은 채 모든 데이터를 fetch 하려 할 것이다. 이에 따라 miss율이 다시 증가하거나, 감소가 둔화되는 모습을 볼 수 있다.

 

Valid bit

valid bit는 해당 line의 값이 더미 값인지 아닌지를 구분하기 위해서 사용한다. 예를 들어 tag 초기 값이 모두 0인 경우에, pc의 tag가 0이라면 이 경우 캐시 된 값이어서 tag가 동일한 것인지, 초기값이 0이라 값이 동일한 것인지 확인할 방법이 없다. 이 상황을 피하기 위해 valid bit를 두고 초기 값을 false로 하여 캐시에 믿을 만한 tag와 데이터가 들어있는지 표시하는 것이다.

 

Hit / Miss

캐시 내에 읽고자 하는 데이터가 존재하는 경우를 hit라고 한다. hit 확인 과정은 다음과 같다. 우선 주소에서 index, tag, blockOffset 부분을 확인한다. 캐시의 index에 해당하는 line에 유의미한 데이터가 존재하는지 valid bit로 확인한다. 유의미한 데이터가 존재한다면 해당 line의 데이터가 원하는 주소의 캐시 값이 맞는지 tag를 비교하여 확인한다. tag까지 일치한다면 이를 hit라고 하고, blockOffset에 해당하는 데이터를 꺼내게 되는 것이다.

 

Set / Direct mapped, Fully associative, N-way set associative

앞선 예시들은 한 인덱스에 한 개의 캐시라인(valid bit, tag, data blocks)이 매핑된다. 이 경우 Miss가 되면 다른 선택지 없이 매번 index에 해당하는 캐시 라인을 비워야 할 것이다. 만약 한 인덱스에 서로 다른 캐시 라인이 번갈아 사용된다고 생각해보자. 매번 해당 인덱스는 miss 가 발생할 것이고, 매번 memory fetch가 요구되며, 그런 현상은 캐시로써의 의미를 잃는다. 

 

만약 위의 상황에서 해당 인덱스에 두 개의 캐시 라인이 동시에 매핑될 수 있다면 어떨까? 데이터가 요구됐을 때 해당 인덱스에 해당하는 두 개 라인을 모두 확인하고 데이터를 액세스 하는 것이다. 같은 상황에서 일단 각각 memory fetch 해두면, 이 두 Line이 요청에 따라 번갈아 액세스 되어 더 이상 miss가 발생하지 않을 것이다. 각각의 캐시 라인이 서로 다른 tag를 갖고 있으면 어떤 라인을 액세스 해야 하는지의 데이터 확인에는 문제가 없을 것이다.

 

이를 set이라고 한다. 앞선 상황에선 set를 2로 늘린 상황이고, 데이터 read가 발생할 시 이 두 set의 index에 해당하는 cache line을 읽어 tag 값을 비교하여 hit 여부를 확인한다. 위 예시 그림은 32비트 주소 체계에서, byte offset = 2bit, block size = 0bit, set size = 2bit, index = 8 bit인 4-set associative cache의 hit 여부와 data를 얻는 data path이다.

 

이 set의 수를 기준으로, set 수가 0개여서 index와 cache line이 1:1인 캐시를 직접 사상 캐시(direct mapped), 반대로 cache line을 index 접근이 아닌 모든 line 비교 -> 접근, 모든 cache line이 set로 사용되는 캐시를 완전 연관 캐시 (fully associative)라고 한다. 그리고 이 둘 사이에서 n개의 set를 갖는 방식의 캐시는 n-way set associative cache로 불린다. 

 

결국 direct mapped cache는 1-way cache, fully associative cache는 모든 cacheLine이 set인 m-way cache와 같다. direct mapped cache는 캐시 교체에 선택지를 주지 못한다는 것, fully associative는 모든 선택지를 주는 대신 그만큼 비교를 위한 설계가 추가되어야 한다는 것이고, 이 둘 사이에서 적절한 set의 교체 선택지를 줄 수 있는 방식이 set associative cache인 것이다.

 

Write through, Write back

Write through(바로 쓰기), Write back (나중 쓰기)는 '쓰기' 명령에 의해 변형된 데이터를 언제 메모리에 반영할지에 대한 전략 차이이다. 이름 그대로 Write through는 변경 사항을 바로 메모리에 반영하고, Write back은 우선 캐시에 먼저 반영하고, 더 미룰 수 없는 상황이 왔을 때 캐시 라인을 메모리에 반영하게 된다.

 

Write back의 이점은 결국 메모리에 쓰는 메모리 액세스를 줄인다는 것이다. 매 쓰기 명령어마다 메모리 액세스를 하지 않고, 혹 메모리 반영을 위해 쓰기를 하더라도, 각 쓰기는 블록별이 아닌, 블록채로 접근하기 때문에 액세스 횟수를 크게 줄일 수 있다. 

 

Write back 방식을 사용 시 cache line에 변경이 있음을 확인하기 위해 각 line에 dirty 비트를 추가한다. 캐시에 데이터가 반영되는 경우 dirty 비트를 true로 바꿔주고, 해당 cache line이 교체될 때 dirty bit를 확인하여 변경되었으면 이를 메모리에 반영한다. 물론 memory fetch로 새로 cache line이 쓰였거나, 캐시가 초기화된 시점에서 dirty bit는 false여야 한다.

 

Replacement strategy

set가 2개 이상일 때, 캐시 miss가 발생하여 cacheLine을 교체해야 하는 경우, 어떤 set을 교체 대상으로 할지에 대한 전략을 말한다. 대표적으로 사용되는 방식으로 다음의 4가지 방식이 존재한다.

 

1. Random replacement : 후보군에서 랜덤하게 선택한 set를 교체 대상으로 한다.

2. First in, First out : 가장 먼저 등록된 set를 교체 대상으로 한다.

3. Second chance : 한 번이라도 사용되는 경우 교체 대상을 피할 second chance를 부여하고, 다음 set를 교체 후보로 한다. 

4. Least recently used : 사용에 가장 오래된 set를 교체 대상으로 한다.

 

Code work / Implementation

구현한 내용은 다음과 같다.

 

- Set size, Cache line 수, Block size를 조절할 수 있는 캐시를 구현한다.

   - Direct mapped cache를 구현한다.

   - N way set associative mapped cache를 구현한다.

   - Fully associative mapped cache를 구현한다.

 

- 쓰기 정책을 지정할 수 있다.

   - Write through cache 정책을 구현한다.

   - Write back cache 정책을 구현한다.

 

- 다양한 교체 전략을 선택할 수 있다.

   - FIFO 교체 전략을 구현한다.

   - Random 교체 전략을 구현한다.

   - Second chance 알고리즘 교체 전략을 구현한다.

   - LRU 알고리즘 교체 전략을 구현한다.

 

 

0. Class diagram 

 

구현한 Cache와 교체 정책에 대한 Class 다이어그램은 다음과 같다.

 

 

1. AbstractAssociativeMappedCache

 

캐시는 주소 비트, byte offset 비트, 세트 수, cache line 수, 블록 사이즈 수를 변수로 하여 유동적으로 캐시를 구성할 수 있도록 하였다. 주소 비트와 byte offset 비트의 기본 값은 MIPS를 기준으로 하여 각각 32, 2비트이고, 이렇게 입력받은 주소 체계를 기준으로 나머지 indexBits, setBits, offsetBits로 캐시 구성이 가능한지 유효 여부를 확인한다. tag로 사용되는 비트 수는 이때 함께 계산된다.

abstract class AbstractAssociativeMappedCache(
    private val addressBits: Int = 32,
    private val byteOffsetBits: Int = 2,
    private val offsetBits: Int,
    private val indexBits: Int,
    private val setBits: Int,
    protected val replacementStrategy: LruReplacementStrategy
) : ICache {

    open fun read(address: Int): Int { .. }

    abstract fun memoryFetch(tag: Int, lineIndex: Int): Int
 }

 

Set 사이즈, CacheLine 사이즈, 블록 수를 바탕으로 주소의 Tag, Index, Block offset을 다음과 같이 정의할 수 있었다.

fun tag(address: Int) = address ushr (addressBits - tagBits)

fun index(address: Int) = ((address shr byteOffsetBits) shr offsetBits) % lineSize

fun offset(address: Int) = (address shr byteOffsetBits) % blockSize

 

반대로 tag 값, index 값, blockOffset을 기준으로 다음과 같이 원래의 주소 값을 계산할 수 있다.

fun address(tag: Int, index: Int, offset: Int): Int {
    return ((((tag shl indexBits) + index) shl offsetBits) + offset) shl byteOffsetBits
}

 

 

2. Direct mapped cache, N way set associative cache, Fully associative cache

 

위 추상 클래스를 기반으로 하여 주소에서 표현될 비트 수를 달리하는 것만으로 Direct mapped cache, N way set associative cache, Fully associative cache를 표현할 수 있었다. 아래는 Set associative cache의 set 수를 0으로 하여 표현한 DirectMappedCache의 전체 코드이다. 

class WriteBackDirectMappedCache(
    memory: Memory,
    offsetBits: Int,
    indexBits: Int
) : WriteBackSetAssociativeMappedCache(
    memory = memory,
    offsetBits = offsetBits,
    indexBits = indexBits,
    setBits = 0
)

 

반대로 FullyAssociativeMappedCache는 set 수가 최대이고, index 수를 0으로 하여 다음과 같이 표현할 수 있다. DirectMappedCache와의 차이점은 교체 전략이 불필요했던 Direct와 달리 FullyAssociative는 교체 전략이 필요하여 생성 시 주입을 받는다는 점뿐이다.

class WriteBackFullyAssociativeMappedCache(
    memory: Memory,
    offsetBits: Int,
    lineBits: Int,
    replacementStrategy: CacheReplacementStrategy
) : WriteBackSetAssociativeMappedCache(
    memory = memory,
    offsetBits = offsetBits,
    indexBits =  0,
    setBits = lineBits,
    replacementStrategy = replacementStrategy
)

 

 

3. Cache read

 

캐시 값 읽기의 진행은 다음과 같다. 먼저 읽고자 하는 주소의 tag, lineIndex, offset을 계산하고, cacheLine에 해당하는 모든 set를 확인하게 한다. 그 결과로 나온 set의 인덱스가 -1이 아닌 유효한 수이면 hit, -1이면 miss이다. 

 

hit일 경우 교체 전략에 cacheLine의 해당 set가 사용되었음을 알리고 캐시 된 블록 데이터를 반환, miss일 경우 메모리에서 데이터를 fetch 하고 캐시에 담은 후, 요청된 블록 데이터를 반환한다. 

override fun read(address: Int): Int {
    val tag = tag(address)
    val lineIndex = index(address)
    val offset = offset(address)

    var setIndex = setIndex(tag, lineIndex)
    return if (setIndex != -1) {
        replacementStrategy.use(setIndex, lineIndex)
        lineSets[setIndex][lineIndex].datas[offset]
    } else {
        setIndex = memoryFetch(tag, lineIndex)
        lineSets[setIndex][lineIndex].datas[offset]
    }
}

abstract fun memoryFetch(tag: Int, lineIndex: Int): Int

이때 memory fetch는 쓰기 정책에 따라 구현이 달라지므로 추상 메서드로 하여 구현을 강제하였다. 

 

 

4. Cache write

 

Cache의 쓰기 정책으로 Write through(바로 쓰기), Write back (나중 쓰기)을 구현하였다. 먼저 WriteThrough의 경우 hit여부와 상관없이 우선 memory에 데이터를 쓰기 한다. 이후에 setIndex가 존재함에 따라(동일 tag가 존재하는 set의 인덱스 확인), hit와 miss여부를 확인한 후에 hit일 경우 캐시에 요청 데이터를 업데이트, miss일 경우 memory fetch를 하는 것으로 캐시 라인을 메모리와 동기화한다.

override fun write(address: Int, value: Int) {
    val tag = tag(address)
    val lineIndex = index(address)
    val offset = offset(address)

    memory.write(address, value)

    val setIndex = setIndex(tag, lineIndex)
    if (setIndex != -1) {
        replacementStrategy.use(setIndex, lineIndex)
        lineSets[setIndex][lineIndex].datas[offset] = value
    } else {
        memoryFetch(tag, lineIndex)
    }
}

 

WriteBack의 경우 각 캐시라인이 업데이트되었는지 확인하기 위해 (setSize * set 안 cacheLine)의 사이즈만큼의 dirty bit가 추가된다.

protected val dirties = Array(setSize) { Array(lineSize) { false } }

 

Write Through와 마찬가지로 쓰기 요청이 왔을 때 해당 index-tag 값을 갖고 있는 세트 여부를 확인하여 hit, miss여부를 확인한다.  차이점은 Write back에선 hit 시 캐시에만 데이터를 쓰고 해당 캐시 라인에 dirty 임을 표시한다. miss 시 memory fetch로 캐시 라인을 업데이트하고 해당 라인에 쓰기 요청을 반영, 마찬가지로 dirty 임을 표시한다. 

override fun write(address: Int, value: Int) {
    val tag = tag(address)
    val lineIndex = index(address)
    val offset = offset(address)

    val setIndex = setIndex(tag, lineIndex)
    if (setIndex != -1) {
        replacementStrategy.use(setIndex, lineIndex)
        dirties[setIndex][lineIndex] = true
        lineSets[setIndex][lineIndex].datas[offset] = value
    } else {
        val newSetIndex = memoryFetch(tag, lineIndex)
        dirties[newSetIndex][lineIndex]= true
        lineSets[newSetIndex][lineIndex].datas[offset] = value
    }
}

 

이렇게 dirty로 표시된 캐시라인은 memory fetch가 이뤄지면서 교체 알고리즘에 의해 해당 라인이 교체 대상이 되는 경우에 메모리에 반영된다. 아래는 WriteBack에서 재정의된 memory fetch 코드이다. 교체 알고리즘에 의해 lineIndex의 교체되어야 하는 set가 결정되면 해당 라인이 dirty인지 확인하여 그때서야 memory write가 일어난다. 이후 dirty 여부를 다시 false로 초기화하고 캐시 라인에 메모리 동기화가 일어나게 된다.

override fun memoryFetch(tag: Int, lineIndex: Int): Int {
    for (setIndex in 0 until setSize) {
        //cacheLine의 valid가 fale인 경우 해당 set를 바로 반환
    }

    val victimSet = replacementStrategy.nextVictim(lineIndex)
    updateDirties(victimSet, lineIndex)
    dirties[victimSet][lineIndex] = false
    lineSets[victimSet][lineIndex].fetch(tag, readBlockLine(tag, lineIndex))
    return victimSet
}

 

WriteBack 쓰기 전략은 해당 캐시 라인이 교체될 때 메모리 쓰기가 일어난다. 따라서 프로세스가 완료되는 시점에서 캐시에 쓰였지만 메모리에는 반영되지 않은 데이터가 남아있을 수 있다. 아래 코드처럼 프로세스의 모든 명령어 처리 완료 후에는 cache를 flushAll, 즉 모든 라인의 dirty 비트를 확인하여 캐시에만 반영된 데이터 쓰기 작업을 메모리에 반영하는 작업이 필요하다.

override fun process(): List<Int> {
    var cycle = 0
    var cycleResult = CycleResult()

    Logger.init()
    while (true) {
        Logger.printCycle(cycle)
        if (cycleResult.nextPc == -1) {
            break
        }
        cycleResult = cycleExecution(cycleResult.nextPc)
        cycle++
    }
    cache.flushAll()
    return listOf(cycleResult.value)
}

 

 

5. Replacement strategy

 

교체 전략은 FIFO(first in, first out), Random, SecondChance, LRU 교체 정책 네 가지를 구현하였다. 그리고 이들을  CacheReplacementStragy이라는 인터페이스로 묶어 Cache에서 교체 전략을 자유롭게 선택할 수 있도록 구성하였다. 아래는 CacheReplacementStrategy의 구현 관계와 이 인터페이스와 AbstractAssociativeMappedCache의 의존성 관계를 보여주는 클래스 다이어그램이다. 

 

 

CacheReplacement 전략은 cache hit 여부가 다음번 victim 결정에 영향을 미치는가에 따라 크게 정적 교체와 동적 교체로 나눴다. 정적 교체의 경우 Random, FIFO, 동적의 경우 SeconChance와 LRU가 있다. CacheReplacementStrategy 인터페이스는 아래와 같고, use는 동적 교체의 hit 시 반영을 위해, nextVictim은 전략에 따라 다음 교체될 set index 반환을 위해 존재한다. 

interface CacheReplacementStrategy {
    fun use(setIndex: Int, lineIndex: Int)
    fun nextVictim(lineIndex: Int): Int
}

 

5-1. 정적 교체 전략 / FIFO, Random

 

정적 교체 전략의 경우 해당 세트가 사용되었어도 이것이 다음 전략에 반영되지 않는다. 그래서 hit시 호출되는 use 메서드의 구현은 비어있다.

override fun use(setIndex: Int, lineIndex: Int) {}

 

Random의 경우 0~setSize-1 까지의 인덱스를 반환하여 교체될 setIndex를 결정하게 된다.

override fun nextVictim(lineIndex: Int): Int {
    return random.nextInt(setSize)
}

 

FIFO의 경우 마지막으로 교체된 index를 기억하고 여기에 매 교체시마다 1을 더하여 반환하게 된다. (기존 값+1)을 setSize로 나눈 값을 저장하게 되어 인덱스 오버플로우를 방지한다.

override fun nextVictim(lineIndex: Int): Int {
    lastUsed = (lastUsed + 1) % setSize
    return lastUsed
}

 

5-2 동적 교체 전략 / SecondChance, LRU

 

동적 교체 전략은 hit시 사용된 set를 기억하고, 다음 교체 대상에 이를 사용한다. SecondChance의 경우 (set*set당 cache line 수)만큼의 chance를 담는 배열을 만들어 사용한다. hit 되는 경우 이 set에 chance를 부여하고, 교체 대상으로 해당 set가 지정되는 경우 chance를 제거하는 전략을 구현하였다. 

override fun use(setIndex: Int, lineIndex: Int) {
    chanceHistories[lineIndex][setIndex] = true
}

override fun nextVictim(lineIndex: Int): Int {
    while (true) {
        lastUsed = (lastUsed + 1) % setSize
        if (!chanceHistories[lineIndex][lastUsed]) {
            return lastUsed
        }
        chanceHistories[lineIndex][lastUsed] = false
    }
}

LRU는 hit시 사용을 기록하고 사용에 가장 오래된 set를 교체 대상으로 하는 정책이다. 각 cacheLine 마다 사용된 set 인덱스를 기록하는 리스트를 선언하고 교체 대상 구하기에 이를 사용한다. hit 시 리스트에서 사용된 setIndex의 값을 리스트의 가장 마지막으로 순서를 이동하고, 교체 대상을 확인할 때는 리스트의 첫 요소를 반환하는 것으로 사용에 가장 오래된 set를 구할 수 있었다.

override fun use(setIndex: Int, lineIndex: Int) {
    val history = usedHistories[lineIndex]
    history.remove(setIndex)
    history.add(setIndex)
}

override fun nextVictim(lineIndex: Int): Int {
    val history = usedHistories[lineIndex]
    return history[0]
}

 

Test result

 

0. Test List

 

- 쓰기 방식에 따른 Memory write 횟수를 비교한다. (Write back, Write through)

- 교체 Set 수에 따른 Hit률을 비교한다. (Direct mapped, 2way, 4way, 16way, 32way, 128way, 256way, Fully associative)

- 교체 알고리즘에 따른 Hit률을 비교한다. (FIFO, Random, Second chance, LRU)

- Block 사이즈에 따른 Hit률을 비교한다. (4, 16, 64, 256, 1024)

- 캐시를 사용의 성능 향상률을 확인한다.

 

1. 쓰기 방식에 따른 Memory write 횟수를 비교한다. (Write back, Write through)

- Block size : 16, Cache line : 256, Direct mapped cache

 

 

2. 교체 Set 수에 따른 Hit률을 비교한다. (Direct mapped, 2way, 4way, 16way, 32way, 128way, 256way, Fully associative)

- block size : 16, Cache line : 256, Replacement strategy : FIFO, Write policy : write back

 

 

3. 교체 알고리즘에 따른 Hit률을 비교한다. (FIFO, Random, Second chance, LRU)

- block size : 16, Cache line : 256, Set size : 4, Write policy : write back

 

 

4. Block 사이즈에 따른 Hit률을 비교한다. (4, 16, 64, 256, 1024)

- Cache line : 4096 / blockSize, DirectMapped, Replacement strategy : FIFO, Write policy : write back

 

 

5. 캐시를 사용의 성능 향상률을 확인한다.

- Block size : 16, Cache line : 256, Set size : 4, Replacement strategy : Random, Write policy : write back

- Input4 기준, 99.76%의 hit율로 메모리 쓰기에선 99.76%의, 메모리 읽기에선 99.75%의 접근 횟수 감소율을 얻을 수 있었다.