โ† Articles

๐Ÿ’ต ์บ์‹œ๊ฐ€ ๋™์ž‘ํ•˜๋Š” ์•„์ฃผ ๊ตฌ์ฒด์ ์ธ ์›๋ฆฌ

ํ•˜๋“œ์›จ์–ด๋กœ ๊ตฌํ˜„ํ•œ ํ•ด์‹œ ํ…Œ์ด๋ธ”

Table of Contents

๊ธฐ์ˆ ์˜ ๋ฐœ์ „์œผ๋กœ ํ”„๋กœ์„ธ์„œ ์†๋„๋Š” ๋น ๋ฅด๊ฒŒ ์ฆ๊ฐ€ํ•ด์˜จ ๋ฐ˜๋ฉด, ๋ฉ”๋ชจ๋ฆฌ์˜ ์†๋„๋Š” ์ด๋ฅผ ๋”ฐ๋ผ๊ฐ€์ง€ ๋ชปํ–ˆ๋‹ค. ํ”„๋กœ์„ธ์„œ๊ฐ€ ์•„๋ฌด๋ฆฌ ๋นจ๋ผ๋„ ๋ฉ”๋ชจ๋ฆฌ์˜ ์ฒ˜๋ฆฌ ์†๋„๊ฐ€ ๋Š๋ฆฌ๋ฉด ๊ฒฐ๊ณผ์ ์œผ๋กœ ์ „์ฒด ์‹œ์Šคํ…œ ์†๋„๋Š” ๋Š๋ ค์ง„๋‹ค. ์ด๋ฅผ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•œ ์žฅ์น˜๊ฐ€ ๋ฐ”๋กœ ์บ์‹œ(Cache)๋‹ค.

์บ์‹œ๋Š” CPU ์นฉ ์•ˆ์— ๋“ค์–ด๊ฐ€๋Š” ์ž‘๊ณ  ๋น ๋ฅธ ๋ฉ”๋ชจ๋ฆฌ๋‹ค. (๊ทธ๋ฆฌ๊ณ  ๋น„์‹ธ๋‹ค.) ํ”„๋กœ์„ธ์„œ๊ฐ€ ๋งค๋ฒˆ ๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌ์— ์ ‘๊ทผํ•ด ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐ›์•„์˜ค๋ฉด ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ์บ์‹œ์— ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด์•„๋‘๊ณ , ํ•ด๋‹น ๋ฐ์ดํ„ฐ๊ฐ€ ํ•„์š”ํ•  ๋•Œ ํ”„๋กœ์„ธ์„œ๊ฐ€ ๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌ ๋Œ€์‹  ์บ์‹œ์— ์ ‘๊ทผํ•˜๋„๋กํ•ด ์ฒ˜๋ฆฌ ์†๋„๋ฅผ ๋†’์ธ๋‹ค.

Principle of Locality

'์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐ์ดํ„ฐโ€™์— ๊ด€ํ•œ ํŒ๋‹จ์€ ์ง€์—ญ์„ฑ์˜ ์›๋ฆฌ๋ฅผ ๋”ฐ๋ฅด๋ฉฐ, ์ง€์—ญ์„ฑ ์›๋ฆฌ๋Š” ์‹œ๊ฐ„ ์ง€์—ญ์„ฑ(Temporal locality)๊ณผ ๊ณต๊ฐ„ ์ง€์—ญ์„ฑ(Spatial locality)์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

์‹œ๊ฐ„ ์ง€์—ญ์„ฑ์€ ์ตœ๊ทผ ์ ‘๊ทผํ•œ ๋ฐ์ดํ„ฐ์— ๋‹ค์‹œ ์ ‘๊ทผํ•˜๋Š” ๊ฒฝํ–ฅ์„ ๋งํ•œ๋‹ค. ๊ฐ€๋ น ๋ฃจํ”„์—์„œ ์ธ๋ฑ์Šค ์—ญํ• ์„ ํ•˜๋Š” ๋ณ€์ˆ˜ i์—๋Š” ์งง์€ ์‹œ๊ฐ„์•ˆ์— ์—ฌ๋Ÿฌ ๋ฒˆ ์ ‘๊ทผ์ด ์ด๋ค„์ง„๋‹ค.

for (i = 0; i < 10; i += 1) {
  arr[i] = i;
}

๊ณต๊ฐ„ ์ง€์—ญ์„ฑ์€ ์ตœ๊ทผ ์ ‘๊ทผํ•œ ๋ฐ์ดํ„ฐ์˜ ์ฃผ๋ณ€ ๊ณต๊ฐ„์— ๋‹ค์‹œ ์ ‘๊ทผํ•˜๋Š” ๊ฒฝํ–ฅ์„ ๋งํ•œ๋‹ค. ์œ„ ๋ฃจํ”„์˜ ๊ฒฝ์šฐ ๋ฐฐ์—ด arr์˜ ๊ฐ ์š”์†Œ๋ฅผ ์ฐธ์กฐํ•˜๋ฉด์„œ ๊ฐ€๊นŒ์šด ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์—ฐ์†์ ์œผ๋กœ ์ ‘๊ทผํ•˜๊ณ  ์žˆ๋‹ค. ๋ฐฐ์—ด์˜ ์š”์†Œ๋“ค์ด ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์—ฐ์†์ ์œผ๋กœ ํ• ๋‹น๋˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

ํ”„๋กœ์„ธ์Šค ์‹คํ–‰ ์ค‘ ์ ‘๊ทผํ•œ ๋ฐ์ดํ„ฐ์˜ ์ ‘๊ทผ ์‹œ์ ๊ณผ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋ฅผ ํ‘œ์‹œํ•œ ์•„๋ž˜ ๊ทธ๋ฆผ์€ ์‹œ๊ฐ„ ์ง€์—ญ์„ฑ๊ณผ ๊ณต๊ฐ„ ์ง€์—ญ์„ฑ์˜ ํŠน์„ฑ์„ ์ž˜ ๋ณด์—ฌ์ค€๋‹ค.

ํ•œ ํ”„๋กœ์„ธ์Šค ์•ˆ์—๋„ ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ๋ถ€๋ถ„๊ณผ ๊ทธ๋ ‡์ง€ ์•Š์€ ๋ถ€๋ถ„์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์šด์˜์ฒด์ œ๋Š” ํ”„๋กœ์„ธ์Šค๋ฅผ ํŽ˜์ด์ง€(Page)๋ผ๋Š” ๋‹จ์œ„๋กœ ๋‚˜๋ˆ  ๊ด€๋ฆฌํ•˜๋ฉฐ, ์œ„ ๊ทธ๋ฆผ์€ ํŽ˜์ด์ง€๋ฅผ ์ฐธ์กฐํ•œ ๊ธฐ๋ก์ด๋‹ค. ๊ฐ€๋กœ ์ถ•์€ ์‹คํ–‰ ์‹œ๊ฐ„์ด๊ณ , ์„ธ๋กœ ์ถ•์€ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋‹ค. ์ฆ‰, ์ˆ˜ํ‰์œผ๋กœ ์ด์–ด์ง„ ์ฐธ์กฐ ๊ธฐ๋ก์€ ๊ธด ์‹œ๊ฐ„์— ๊ฑธ์ณ ๊ฐ™์€ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋ฅผ ์ฐธ์กฐํ•œ ๊ฒƒ์ด๊ณ , ์ˆ˜์ง์œผ๋กœ ์ด์–ด์ง„ ์ฐธ์กฐ ๊ธฐ๋ก์€ ๊ฐ™์€ ์‹œ๊ฐ„์— ๋ฐ€์ ‘ํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋“ค์„ ์ฐธ์กฐํ•œ ๊ฒƒ์ด๋‹ค. ํŽ˜์ด์ง€์— ์ ‘๊ทผํ•  ๋•Œ๋„ ์ง€์—ญ์„ฑ ์›๋ฆฌ๊ฐ€ ์ ์šฉ๋œ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

Caches

CPU ์นฉ์—๋Š” ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์บ์‹œ๊ฐ€ ๋“ค์–ด๊ฐ€๋ฉฐ, ๊ฐ๊ฐ์˜ ์บ์‹œ๋Š” ๊ฐ์ž์˜ ๋ชฉ์ ๊ณผ ์—ญํ• ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

+-------------+------+------+     +---------------+     +--------+
|             |  I$  |      | <-- |               | <-- |        |
+  Processor  +------+  L2  |     |  Main Memory  |     |  Disk  |
|             |  D$  |      | --> |               | --> |        |
+-------------+------+------+     +---------------+     +--------+
  • L1 Cache: ํ”„๋กœ์„ธ์„œ์™€ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์บ์‹œ. ์†๋„๋ฅผ ์œ„ํ•ด I$์™€ D$๋กœ ๋‚˜๋‰œ๋‹ค.
    • Instruction Cache (I$): ๋ฉ”๋ชจ๋ฆฌ์˜ TEXT ์˜์—ญ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ค๋ฃจ๋Š” ์บ์‹œ.
    • Data Cache (D$): TEXT ์˜์—ญ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ค๋ฃจ๋Š” ์บ์‹œ.
  • L2 Cache: ์šฉ๋Ÿ‰์ด ํฐ ์บ์‹œ. ํฌ๊ธฐ๋ฅผ ์œ„ํ•ด L1 ์บ์‹œ์ฒ˜๋Ÿผ ๋‚˜๋ˆ„์ง€ ์•Š๋Š”๋‹ค.
  • L3 Cache: ๋ฉ€ํ‹ฐ ์ฝ”์–ด ์‹œ์Šคํ…œ์—์„œ ์—ฌ๋Ÿฌ ์ฝ”์–ด๊ฐ€ ๊ณต์œ ํ•˜๋Š” ์บ์‹œ.

์บ์‹œ์— ๋‹ฌ๋Ÿฌ ๊ธฐํ˜ธ($)๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์ด์œ ๋Š” ์บ์‹œ(Cache)์˜ ๋ฐœ์Œ์ด ํ˜„๊ธˆ์„ ๋œปํ•˜๋Š” 'Cashโ€™์™€ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค :)

์˜ค๋Š˜๋‚  CPU ์นฉ์˜ ๋ฉด์  30~70%๋Š” ์บ์‹œ๊ฐ€ ์ฐจ์ง€ํ•œ๋‹ค. 1989๋…„ ์ƒ์‚ฐ๋œ ์‹ฑ๊ธ€ ์ฝ”์–ด ํ”„๋กœ์„ธ์„œ์ธ i486์˜ ๊ฒฝ์šฐ 8KB์งœ๋ฆฌ I/D ์บ์‹œ ํ•˜๋‚˜๋งŒ ์žˆ์—ˆ๋‹ค. ํ•œํŽธ ์ธํ…” ์ฝ”์–ด i7 ์ฟผ๋“œ ์ฝ”์–ด ์นฉ์˜ ๋‹ค์ด ๋งต(Die map)์„ ๋ณด๋ฉด 4๊ฐœ์˜ ์ฝ”์–ด์— ๊ฐ๊ฐ 256KB L2 ์บ์‹œ๊ฐ€ ์žˆ๊ณ , ๋ชจ๋“  ์ฝ”์–ด๊ฐ€ ๊ณต์œ ํ•˜๋Š” 8MB L3 ์บ์‹œ๊ฐ€ ์žˆ๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. (L2 ์บ์‹œ ์œ„์— ์žˆ๋Š” ๊ตฌ์—ญ์ด L1 ์บ์‹œ๋กœ ๋ณด์ด๋Š”๋ฐ, ํ™•์‹คํ•˜์ง€ ์•Š์•„์„œ ๋”ฐ๋กœ ํ‘œ์‹œํ•˜์ง€ ์•Š์•˜๋‹ค.)

Cache Metrics

์บ์‹œ์˜ ์„ฑ๋Šฅ์„ ์ธก์ •ํ•  ๋•Œ๋Š” ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ(Hit latency)์™€ ๋ฏธ์Šค ๋ ˆ์ดํ„ด์‹œ(Miss latency)๊ฐ€ ์ค‘์š”ํ•œ ์š”์ธ์œผ๋กœ ๊ผฝํžŒ๋‹ค.

CPU์—์„œ ์š”์ฒญํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹œ์— ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ๋ฅผ ์บ์‹œ ํžˆํŠธ(Hit)๋ผ๊ณ  ํ•œ๋‹ค. ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ๋Š” ํžˆํŠธ๊ฐ€ ๋ฐœ์ƒํ•ด ์บ์‹ฑ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ฌ ๋•Œ ์†Œ์š”๋˜๋Š” ์‹œ๊ฐ„์„ ์˜๋ฏธํ•œ๋‹ค. ๋ฐ˜๋ฉด ์š”์ฒญํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹œ์— ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๋ฅผ ์บ์‹œ ๋ฏธ์Šค(Miss)๋ผ๊ณ  ํ•˜๋ฉฐ, ๋ฏธ์Šค ๋ ˆ์ดํ„ด์‹œ๋Š” ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•ด ์ƒ์œ„ ์บ์‹œ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ค๊ฑฐ๋‚˜(L1 ์บ์‹œ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์—†์–ด์„œ L2 ์บ์‹œ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๋Š” ๊ฒฝ์šฐ) ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ฌ ๋•Œ ์†Œ์š”๋˜๋Š” ์‹œ๊ฐ„์„ ๋งํ•œ๋‹ค.

ํ‰๊ท  ์ ‘๊ทผ ์‹œ๊ฐ„(Average access time)์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ตฌํ•œ๋‹ค:

Missย rate=Cacheย missesCacheย acessesAverageย accessย time=Hitย latency+Missย rateร—Missย latency \begin{aligned} \text{Miss rate} &= {\text{Cache misses} \over \text{Cache acesses}} \\ \text{Average access time} &= \text{Hit latency} + \text{Miss rate} \times \text{Miss latency} \end{aligned}

์บ์‹œ์˜ ์„ฑ๋Šฅ์„ ๋†’์ด๊ธฐ ์œ„ํ•ด์„œ๋Š” ์บ์‹œ์˜ ํฌ๊ธฐ๋ฅผ ์ค„์—ฌ ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ๋ฅผ ์ค„์ด๊ฑฐ๋‚˜, ์บ์‹œ์˜ ํฌ๊ธฐ๋ฅผ ๋Š˜๋ ค ๋ฏธ์Šค ๋น„์œจ์„ ์ค„์ด๊ฑฐ๋‚˜, ๋” ๋น ๋ฅธ ์บ์‹œ๋ฅผ ์ด์šฉํ•ด ๋ ˆ์ดํ„ด์‹œ๋ฅผ ์ค„์ด๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

Cache Organization

์บ์‹œ๋Š” ๋ฐ˜์‘ ์†๋„๊ฐ€ ๋น ๋ฅธ SRAM(Static Random Access Memory)์œผ๋กœ, ์ฃผ์†Œ๊ฐ€ ํ‚ค(Key)๋กœ ์ฃผ์–ด์ง€๋ฉด ํ•ด๋‹น ๊ณต๊ฐ„์— ์ฆ‰์‹œ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฌํ•œ ํŠน์„ฑ์€ DRAM(Dynamic Random Access Meomry)์—์„œ๋„ ๋™์ผํ•˜์ง€๋งŒ ํ•˜๋“œ์›จ์–ด ์„ค๊ณ„์ƒ DRAM์€ SRAM๋ณด๋‹ค ๋Š๋ฆฌ๋‹ค. ํ†ต์ƒ์ ์œผ๋กœ '๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌโ€™๋ผ๊ณ  ๋งํ•  ๋•Œ๋Š” DRAM์„ ์˜๋ฏธํ•œ๋‹ค.

์ฃผ์†Œ๊ฐ€ ํ‚ค๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ ๊ทธ ๊ณต๊ฐ„์— ์ฆ‰์‹œ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ์บ์‹œ๊ฐ€ ํ•˜๋“œ์›จ์–ด๋กœ ๊ตฌํ˜„ํ•œ ํ•ด์‹œ ํ…Œ์ด๋ธ”(Hash table)๊ณผ ๊ฐ™๋‹ค๋Š” ์˜๋ฏธ๋‹ค. ์บ์‹œ๊ฐ€ ๋น ๋ฅธ ์ด์œ ๋Š” ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐ์ดํ„ฐ๋งŒ์„ ๋‹ด์•„๋‘๊ธฐ ๋•Œ๋ฌธ์ด๊ธฐ๋„ ํ•˜์ง€๋งŒ, ํ•ด์‹œ ํ…Œ์ด๋ธ”์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(1)O(1) ์ •๋„๋กœ ๋น ๋ฅด๊ธฐ ๋•Œ๋ฌธ์ด๊ธฐ๋„ ํ•˜๋‹ค.

์บ์‹œ๋Š” ๋ธ”๋ก(Block)์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ๋ธ”๋ก์€ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด๊ณ  ์žˆ์œผ๋ฉฐ, ์ฃผ์†Œ๊ฐ’์„ ํ‚ค๋กœ์จ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ธ”๋ก์˜ ๊ฐœ์ˆ˜(Blocks)์™€ ๋ธ”๋ก์˜ ํฌ๊ธฐ(Block size)๊ฐ€ ์บ์‹œ์˜ ํฌ๊ธฐ๋ฅผ ๊ฒฐ์ •ํ•œ๋‹ค.

Indexing

์ฃผ์†Œ๊ฐ’ ์ „์ฒด๋ฅผ ํ‚ค๋กœ ์‚ฌ์šฉํ•˜์ง€๋Š” ์•Š๊ณ , ๊ทธ ์ผ๋ถ€๋งŒ์„ ์‚ฌ์šฉํ•œ๋‹ค. ๊ฐ€๋ น ๋ธ”๋ก ๊ฐœ์ˆ˜๊ฐ€ 1024๊ฐœ์ด๊ณ , ๋ธ”๋ก ์‚ฌ์ด์ฆˆ๊ฐ€ 32๋ฐ”์ดํŠธ์ผ ๋•Œ, 32๋น„ํŠธ ์ฃผ์†Œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ธ๋ฑ์‹ฑ ํ•  ์ˆ˜ ์žˆ๋‹ค.

์ „์ฒด ์ฃผ์†Œ์—์„œ ํ•˜์œ„ 5๋น„ํŠธ๋ฅผ ์˜คํ”„์…‹(Offset)์œผ๋กœ ์“ฐ๊ณ , ์ดํ›„ 10๋น„ํŠธ๋ฅผ ์ธ๋ฑ์Šค(Index)๋กœ ์‚ฌ์šฉํ•˜์—ฌ ๋ธ”๋ก์— ์ ‘๊ทผํ–ˆ๋‹ค. ์ธ๋ฑ์Šค๊ฐ€ 10๋น„ํŠธ์ธ ์ด์œ ๋Š” 2n2^n๊ฐœ ๋ธ”๋ก์˜ ๋ชจ๋“  ์ธ๋ฑ์Šค๋ฅผ ํ‘œํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” log2blockslog{_2}\text{blocks}๋งŒํผ์˜ ๋น„ํŠธ๊ฐ€ ํ•„์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์—ฌ๊ธฐ์—์„  ๋ธ”๋ก ๊ฐœ์ˆ˜๊ฐ€ 210=10242^{10} = 1024๊ฐœ์ด๋ฏ€๋กœ, log21024=10log{_2} 1024 = 10์ด ๋˜์–ด 10๋น„ํŠธ๊ฐ€ ์ธ๋ฑ์Šค ๋น„ํŠธ๋กœ ์‚ฌ์šฉ๋˜์—ˆ๋‹ค. (์˜คํ”„์…‹ ๋น„ํŠธ์— ๋Œ€ํ•ด์„œ๋Š” ์•„๋ž˜์—์„œ ์„ค๋ช…ํ•˜๊ฒ ๋‹ค.)

๊ทธ๋Ÿฌ๋‚˜ ์ด๋ ‡๊ฒŒ๋งŒ ํ•˜๋ฉด ์„œ๋กœ ๋‹ค๋ฅธ ๋ฐ์ดํ„ฐ์˜ ์ธ๋ฑ์Šค๊ฐ€ ์ค‘๋ณต๋  ์œ„ํ—˜์ด ๋„ˆ๋ฌด ํฌ๋‹ค.

Tag Matching

์ธ๋ฑ์Šค์˜ ์ถฉ๋Œ์„ ์ค„์ด๊ธฐ ์œ„ํ•ด ์ฃผ์†Œ๊ฐ’์˜ ์ผ๋ถ€๋ฅผ ํƒœ๊ทธ(Tag)๋กœ ์‚ฌ์šฉํ•œ๋‹ค. ๋ธ”๋ก ๊ฐœ์ˆ˜๊ฐ€ 1024๊ฐœ์ด๊ณ , ๋ธ”๋ก ์‚ฌ์ด์ฆˆ๊ฐ€ 32๋ฐ”์ดํŠธ์ผ ๋•Œ, 32๋น„ํŠธ ์ฃผ์†Œ 0x000c14B8์— ์ ‘๊ทผํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž:

  1. ๋จผ์ € ์ธ๋ฑ์Šค(0010100101)์— ๋Œ€์‘ํ•˜๋Š” ํƒœ๊ทธ ๋ฐฐ์—ด(Tag array)์˜ ํ•„๋“œ์— ์ ‘๊ทผํ•œ๋‹ค.
  2. ์ด์–ด์„œ ํ•ด๋‹น ํƒœ๊ทธ ํ•„๋“œ์˜ ์œ ํšจ ๋น„ํŠธ(Valid bit)๋ฅผ ํ™•์ธํ•œ๋‹ค.
  3. ์œ ํšจ ๋น„ํŠธ๊ฐ€ 1์ด๋ผ๋ฉด ํƒœ๊ทธ ํ•„๋“œ(00000000000011000)์™€ ์ฃผ์†Œ์˜ ํƒœ๊ทธ(00000000000011000)๊ฐ€ ๊ฐ™์€์ง€ ๋น„๊ตํ•œ๋‹ค.
  4. ๋น„๊ต ๊ฒฐ๊ณผ(true, 1)๋ฅผ ์œ ํšจ ๋น„ํŠธ(1)์™€ AND ์—ฐ์‚ฐํ•œ๋‹ค.

์œ ํšจ ๋น„ํŠธ๊ฐ€ 1์ด๋ผ๋Š” ๊ฒƒ์€ ํ•ด๋‹น ๋ธ”๋ก์— ์˜ฌ๋ฐ”๋ฅธ ๊ฐ’์ด ์กด์žฌํ•œ๋‹ค๋Š” ์˜๋ฏธ๋‹ค. ํƒœ๊ทธ ํ•„๋“œ์™€ ์ฃผ์†Œ์˜ ํƒœ๊ทธ๊ฐ€ ๊ฐ™๊ณ , ์œ ํšจ ๋น„ํŠธ๋„ 1์ด๋ฏ€๋กœ ์œ„ ์˜ˆ์‹œ์˜ ๊ฒฐ๊ณผ๋Š” ํžˆํŠธ๋‹ค. ํžˆํŠธ๊ฐ€ ๋ฐœ์ƒํ•˜๋ฉด ๋ฐ์ดํ„ฐ ๋ฐฐ์—ด(Data array)์—์„œ ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์ฐธ์กฐํ•œ๋‹ค. (์ฐธ๊ณ ๋กœ ๋ฐ์ดํ„ฐ ๋ฐฐ์—ด๊ณผ ํƒœ๊ทธ ๋ฐฐ์—ด๋„ ๋ชจ๋‘ ํ•˜๋“œ์›จ์–ด๋‹ค.)

๋งŒ์•ฝ ์œ ํšจ ๋น„ํŠธ๊ฐ€ 0์ด๋ผ๋ฉด ๋ธ”๋ก์— ๊ฐ’์ด ์—†๊ฑฐ๋‚˜ ์˜ฌ๋ฐ”๋ฅด์ง€ ์•Š๋‹ค๋Š” ๋œป์ด๋ฏ€๋กœ ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ์ฃผ์†Œ์˜ ํƒœ๊ทธ๋ฅผ ํƒœ๊ทธ ํ•„๋“œ์— ์ž‘์„ฑํ•˜๊ณ , ๋ฐ์ดํ„ฐ ํ•„๋“œ์—๋„ ์ƒ์œ„ ์บ์‹œ๋‚˜ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ์š”์ฒญํ•œ ๊ฐ’์„ ๊ฐ€์ ธ์™€ ์ž‘์„ฑํ•œ ๋’ค, ์œ ํšจ ๋น„ํŠธ๋ฅผ 1๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค.

์œ ํšจ ๋น„ํŠธ๊ฐ€ 1์ด๋ผ๋„ ํƒœ๊ทธ๊ฐ€ ์ผ์น˜ํ•˜์ง€ ์•Š์œผ๋ฉด ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ์ด ๊ฒฝ์šฐ ๊ต์ฒด ์ •์ฑ…(Replacement policy)์— ๋”ฐ๋ผ ์ฒ˜๋ฆฌ๊ฐ€ ๋‹ฌ๋ผ์ง„๋‹ค. ๋จผ์ € ์ž…๋ ฅ๋œ ๋ฐ์ดํ„ฐ๊ฐ€ ๋จผ์ € ๊ต์ฒด๋˜๋Š” FIFO(First-In First-Out) ์ •์ฑ…์„ ์‚ฌ์šฉํ•œ๋‹ค๋ฉด ๋ฌด์กฐ๊ฑด ๊ธฐ์กด ๋ธ”๋ก๋ฅผ ๊ต์ฒดํ•œ๋‹ค. ํƒœ๊ทธ ๋ฐฐ์—ด์˜ ํ•„๋“œ๋ฅผ ์ฃผ์†Œ์˜ ํƒœ๊ทธ๋กœ ๋ฐ”๊พธ๊ณ , ์ƒ์œ„ ์บ์‹œ๋‚˜ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ์š”์ฒญํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์™€ ๋ฐ์ดํ„ฐ ํ•„๋“œ์˜ ๊ฐ’๋„ ์ƒˆ ๋ฐ์ดํ„ฐ๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค. (์‹ค์ œ๋กœ๋Š” ์š”์ฒญํ•œ ๋ฐ์ดํ„ฐ๋ฟ ์•„๋‹ˆ๋ผ ๊ทธ ์ฃผ๋ณ€ ๋ฐ์ดํ„ฐ๊นŒ์ง€ ๊ฐ€์ ธ์˜จ๋‹ค.) ๊ธฐ์กด ๋ฐ์ดํ„ฐ๋Š” ์ƒ์œ„ ์บ์‹œ๋กœ ๋ฐ€๋ ค๋‚œ๋‹ค.

์ฃผ์†Œ์˜ ์ƒ์œ„ 15๋น„ํŠธ๊ฐ€ ํƒœ๊ทธ ๋น„ํŠธ๋กœ ์‚ฌ์šฉ๋œ ์ด์œ ๋Š” ํƒœ๊ทธ ๋น„ํŠธ๊ฐ€ Addressย bitsโˆ’(logโก2Blockย size+Indexย bits)\text{Address bits} - (\log{_2}\text{Block size} + \text{Index bits})๋กœ ๊ฒฐ์ •๋˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ด ๊ฒฝ์šฐ 32โˆ’(5+10)=1732 - (5 + 10) = 17 ๋น„ํŠธ๊ฐ€ ํƒœ๊ทธ ๋น„ํŠธ๋กœ ์‚ฌ์šฉ๋˜์—ˆ๊ณ , ๋‚จ์€ 5๋น„ํŠธ๋Š” ์˜คํ”„์…‹ ๋น„ํŠธ๋กœ ์‚ฌ์šฉ๋˜์—ˆ๋‹ค.

Tag Overhead

ํƒœ๊ทธ ๋ฐฐ์—ด์ด ์ถ”๊ฐ€๋˜๋ฉด์„œ ๋” ๋งŽ์€ ๊ณต๊ฐ„์ด ํ•„์š”ํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ํ•˜์ง€๋งŒ ์—ฌ์ „ํžˆ '32KB ์บ์‹œโ€™๋Š” 32KB ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” ์บ์‹œ๋ผ๋Š” ์˜๋ฏธ๋‹ค. ํƒœ๊ทธ๋ฅผ ์œ„ํ•œ ๊ณต๊ฐ„์€ ๋ธ”๋ก ํฌ๊ธฐ์™€ ์ƒ๊ด€์—†๋Š” ์˜ค๋ฒ„ํ—ค๋“œ(Overhead)๋กœ ์ทจ๊ธ‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

1024๊ฐœ์˜ 32B ๋ธ”๋ก์œผ๋กœ ๊ตฌ์„ฑ๋œ 32KB ์บ์‹œ์˜ ํƒœ๊ทธ ์˜ค๋ฒ„ํ—ค๋“œ๋ฅผ ๊ตฌํ•ด๋ณด์ž:

17bitย tag+1bitย valid=18bit18bitร—1024=18Kbย tags=2.25KB \begin{aligned} 17 \text{bit tag} + 1 \text{bit valid} &= 18 \text{bit} \\ 18 \text{bit} \times 1024 = 18 \text{Kb tags} &= 2.25 \text{KB} \end{aligned}

์ฆ‰, 7%์˜ ํƒœ๊ทธ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค.

๊ณต๊ฐ„๋ฟ ์•„๋‹ˆ๋ผ ์‹œ๊ฐ„ ๋น„์šฉ๋„ ๋ฐœ์ƒํ•œ๋‹ค. ํƒœ๊ทธ ๋ฐฐ์—ด์— ์ ‘๊ทผํ•ด ํžˆํŠธ๋ฅผ ํ™•์ธํ•˜๊ณ , ๊ทธ ์ดํ›„์— ๋ฐ์ดํ„ฐ ๋ฐฐ์—ด์— ์ ‘๊ทผํ•ด ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ค๊ธฐ ๋•Œ๋ฌธ์— ๊ฒฐ๊ณผ์ ์œผ๋กœ ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๊ฒŒ ๋œ๋‹ค.

๊ทธ๋ž˜์„œ ๋‘ ๊ณผ์ •์„ ๋ณ‘๋ ฌ์ ์œผ๋กœ ์‹คํ–‰ํ•œ๋‹ค. ํƒœ๊ทธ ๋ฐฐ์—ด์—์„œ ํžˆํŠธ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๋Š” ๋™์‹œ์— ๋ฏธ๋ฆฌ ๋ฐ์ดํ„ฐ ๋ฐฐ์—ด์— ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ๊ฐ€ ์ค„์–ด๋“ค์ง€๋งŒ, ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ–ˆ์„ ๋•Œ์˜ ๋ฆฌ์†Œ์Šค ๋‚ญ๋น„๋ฅผ ๊ฐ์ˆ˜ํ•ด์•ผ ํ•œ๋‹ค.

Associative Cache

์„œ๋กœ ๋‹ค๋ฅธ ๋‘ ์ฃผ์†Œ๊ฐ€ ๊ฐ™์€ ์ธ๋ฑ์Šค๋ฅผ ๊ฐ€์ง€๋ฉด ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜๊ณ , ๊ต์ฒด ์ •์ฑ…์— ๋”ฐ๋ผ ๋ธ”๋ก์„ ๊ต์ฒดํ•œ๋‹ค. ํ•˜์ง€๋งŒ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•  ๋•Œ๋งˆ๋‹ค ์บ์‹œ ๋‚ด์šฉ์„ ๋ฐ”๊พธ๋ฉด ๋” ๋งŽ์€ ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•˜๊ฒŒ ๋˜๊ณ , ํ•œ ์ž๋ฆฌ์˜ ๋‚ด์šฉ์„ ๋์—†์ด ๋ฐ”๊พธ๋Š” ํ•‘ํ ๋ฌธ์ œ(Ping-pong problem)๊ฐ€ ์ผ์–ด๋‚  ์ˆ˜ ์žˆ๋‹ค.

์ด ๋ฌธ์ œ๋Š” ํƒœ๊ทธ ๋ฐฐ์—ด๊ณผ ๋ฐ์ดํ„ฐ ๋ฐฐ์—ด์„ ์—ฌ๋Ÿฌ ๊ฐœ ๋งŒ๋“œ๋Š” ์‹์œผ๋กœ ๊ฐœ์„ ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ฆ‰, ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ธ”๋ก์ด ์—ฌ๋Ÿฌ ๊ฐœ๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ธ”๋ก์˜ ๊ฐœ์ˆ˜์— ๋”ฐ๋ผ ์บ์‹œ์˜ ์ข…๋ฅ˜๋ฅผ ๋ถ„๋ฅ˜ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค:

  • Direct mapped: ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ณต๊ฐ„์ด ํ•˜๋‚˜์ธ ๊ฒฝ์šฐ. ์ฒ˜๋ฆฌ๊ฐ€ ๋น ๋ฅด์ง€๋งŒ ์ถฉ๋Œ ๋ฐœ์ƒ์ด ์žฆ๋‹ค.
  • Fully associative: ์ธ๋ฑ์Šค๊ฐ€ ๋ชจ๋“  ๊ณต๊ฐ„์„ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ฒฝ์šฐ. ์ถฉ๋Œ์ด ์ ์ง€๋งŒ ๋ชจ๋“  ๋ธ”๋ก์„ ํƒ์ƒ‰ํ•ด์•ผ ํ•ด์„œ ์†๋„๊ฐ€ ๋Š๋ฆฌ๋‹ค.
  • Set associative: ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ณต๊ฐ„์ด ๋‘ ๊ฐœ ์ด์ƒ์ธ ๊ฒฝ์šฐ. n-way set associative ์บ์‹œ๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

direct mapped ์บ์‹œ์™€ fully associative ์บ์‹œ ๋ชจ๋‘ ์žฅ๋‹จ์ ์ด ๊ทน๋‹จ์ ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ณดํ†ต์€ set associative ์บ์‹œ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

Set Associative Cache Organization

๊ฐ„๋‹จํ•˜๊ฒŒ 2-way set associative ์บ์‹œ์˜ ๋™์ž‘์„ ์‚ดํŽด๋ณด์ž:

์ฃผ์†Œ์˜ ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ๋ธ”๋ก์— ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์€ ์ง€๊ธˆ๊นŒ์ง€ ๋ณธ direct mapped ์บ์‹œ์™€ ๋™์ผํ•˜๋‹ค. ๋‹ค๋งŒ 2๊ฐœ์˜ ์›จ์ด(Way)๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹ฑ๋˜์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ ค๋ฉด ํ•˜๋‚˜์˜ ๋ธ”๋ก๋งŒ์ด ์•„๋‹Œ 2๊ฐœ์˜ ๋ธ”๋ก์„ ๋ชจ๋‘ ํ™•์ธํ•ด์•ผ ํ•œ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ๋‘ ์›จ์ด์˜ ๊ฒฐ๊ณผ๋ฅผ OR ์—ฐ์‚ฐํ•˜๋ฉด ์ตœ์ข… ๊ฒฐ๊ณผ๋ฅผ ๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๋ชจ๋“  ์›จ์ด์—์„œ ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•˜๋ฉด ๊ต์ฒด ์ •์ฑ…์— ๋”ฐ๋ผ 2๊ฐœ์˜ ๋ธ”๋ก ์ค‘ ํ•œ ๊ณณ์— ๋ฐ์ดํ„ฐ๋ฅผ ์ž‘์„ฑํ•œ๋‹ค.

direct mapped ์บ์‹œ์™€ ๋น„๊ตํ•ด์„œ ํžˆํŠธ ๋ ˆ์ดํ„ด์‹œ๋ฅผ ๋†’์ด๋Š” ๋Œ€์‹  ์ถฉ๋Œ ๊ฐ€๋Šฅ์„ฑ์„ ์ค„์ธ ๊ฒƒ์ด๋‹ค.

Concrete Example

2๋ฐ”์ดํŠธ ์บ์‹œ ๋ธ”๋ก์œผ๋กœ ๊ตฌ์„ฑ๋œ 8๋ฐ”์ดํŠธ 2-way ์บ์‹œ๊ฐ€ ์žˆ๊ณ , 4๋น„ํŠธ ์ฃผ์†Œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž.

๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ 0001์„ ์ฐธ์กฐํ•˜๋Š” ๋ช…๋ น์ด ์‹คํ–‰๋˜์—ˆ๋‹ค. ์ธ๋ฑ์Šค ๋น„ํŠธ๋Š” logโก22=1\log{_2} 2 = 1์ด๊ณ , ํƒœ๊ทธ ๋น„ํŠธ๋Š” 4โˆ’(log22+1)=24 - (log{_2} 2 + 1) = 2์ด๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ์˜คํ”„์…‹ ๋น„ํŠธ๋Š” 1์ด ๋œ๋‹ค. ๋”ฐ๋ผ์„œ ์ฃผ์†Œ 0001์˜ ์ธ๋ฑ์Šค๋Š” 0, ํƒœ๊ทธ๋Š” 00์ด๋‹ค. ์ฆ‰, ํ•ด๋‹น ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์œ„์น˜ํ•œ ๋ฐ์ดํ„ฐ๋Š” ์ธ๋ฑ์Šค๊ฐ€ 0์ธ ๋‘ ๊ณต๊ฐ„ ์ค‘ ํ•œ ๊ณณ์— ์บ์‹ฑ๋  ์ˆ˜ ์žˆ๋‹ค.

Way 0์˜ ๋ธ”๋ก์ด ๋น„์–ด์žˆ์œผ๋ฏ€๋กœ Way 0์—์„œ ์ธ๋ฑ์Šค๊ฐ€ 0์ธ ๋ธ”๋ก์— ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ–ˆ๋‹ค. ์ด๋•Œ ์ฃผ์†Œ 0010๋„ ๊ฐ™์ด ์บ์‹ฑ๋˜์—ˆ๋Š”๋ฐ, ์ด๋Š” ์บ์‹œ ํžˆํŠธ ๋น„์œจ์„ ๋†’์ด๊ธฐ ์œ„ํ•ด ๋ฉ”๋ชจ๋ฆฌ์—์„œ ํ•œ ๋ฒˆ์— ์บ์‹œ ๋ธ”๋ก ํฌ๊ธฐ(2B)๋งŒํผ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ค๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. (๊ณต๊ฐ„ ์ง€์—ญ์„ฑ์„ ํ™œ์šฉํ•œ ๊ฒƒ์ด๋‹ค.) ์—ฌ๊ธฐ์„œ๋Š” ์ฐธ์กฐํ•œ ๋ฐ์ดํ„ฐ(0001)์˜ ์ฃผ๋ณ€ ๊ณต๊ฐ„์ธ 0010์„ ํ•จ๊ป˜ ์บ์‹ฑํ–ˆ๋‹ค.

๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ 0101์„ ์ฐธ์กฐํ•˜๋Š” ๋ช…๋ น์ด ์‹คํ–‰๋˜์—ˆ๋‹ค. ์ด๋ฒˆ์—๋„ ์ธ๋ฑ์Šค๊ฐ€ 0์ธ ๋‘ ๊ณต๊ฐ„์— ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค.

ํ•˜์ง€๋งŒ Way 0์—์„œ ์ธ๋ฑ์Šค๊ฐ€ 0์ธ ๋ธ”๋ก์€ ์ด๋ฏธ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์—†๋Š” Way 1์— ์บ์‹ฑ๋œ๋‹ค. ์ด๋ฒˆ์—๋„ ์˜†์— ์žˆ๋Š” 0110 ๋ฐ์ดํ„ฐ๊ฐ€ ํ•จ๊ป˜ ์บ์‹ฑ๋˜์—ˆ๋‹ค. ๋˜ํ•œ Way 0์— ์†ํ•œ ๋‘ ๋ธ”๋ก์˜ LRU(Least Recently Used) ๊ฐ’์ด ์ฆ๊ฐ€ํ–ˆ๋‹ค. LRU๋Š” ์‚ฌ์šฉํ•œ์ง€ ๋” ์˜ค๋ž˜๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์šฐ์„ ์ ์œผ๋กœ ๊ต์ฒดํ•˜๋Š” ์ •์ฑ…์œผ๋กœ, ์šด์˜์ฒด์ œ์˜ ํ”„๋กœ์„ธ์Šค ์Šค์ผ€์ค„๋ง์ด๋‚˜ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ๋„ ์‚ฌ์šฉ๋œ๋‹ค. LRU ๊ฐ’์ด ์ฆ๊ฐ€ํ–ˆ๋‹ค๋Š” ๊ฒƒ์€ ์บ์‹œ ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ–ˆ์„ ๋•Œ ์šฐ์„ ์ ์œผ๋กœ ๊ต์ฒด๋  ๊ฐ€๋Šฅ์„ฑ์ด ๋†’์•„์กŒ๋‹ค๋Š” ์˜๋ฏธ๋‹ค.

์ด์–ด์„œ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ 1000์„ ์ฐธ์กฐํ•˜๋Š” ๋ช…๋ น์ด ์‹คํ–‰๋˜์—ˆ๋‹ค. ์ธ๋ฑ์Šค๊ฐ€ 0์ธ ๋‘ ๋ธ”๋ก์„ ํ™•์ธํ–ˆ์œผ๋‚˜, ํƒœ๊ทธ๊ฐ€ 10์ธ ๋ฐ์ดํ„ฐ๊ฐ€ ์—†์–ด ์บ์Šค ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค.

๊ฒฐ๊ตญ ์บ์‹ฑ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ต์ฒดํ•œ๋‹ค. ๋‘ ๊ณต๊ฐ„ ์ค‘ Way 0 ๋ธ”๋ก์˜ LRU ๊ฐ’์ด ๋” ํฌ๊ธฐ ๋•Œ๋ฌธ์— Way 0์˜ ์ฒซ ๋ฒˆ์งธ ๋ธ”๋ก์ด ๊ต์ฒด ๋˜์—ˆ๊ณ , ์ฐธ์กฐ๊ฐ€ ์ผ์–ด๋‚ฌ์œผ๋ฏ€๋กœ LRU ๊ฐ’์„ 0์œผ๋กœ ์ดˆ๊ธฐํ™”ํ–ˆ๋‹ค. (์บ์‹œ ํžˆํŠธ๊ฐ€ ๋ฐœ์ƒํ•˜๋Š” ๊ฒฝ์šฐ์—๋„ LRU ๊ฐ’์„ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.) ์ฐธ์กฐํ•œ ๋ฐ์ดํ„ฐ์˜ ์ฃผ๋ณ€ ๊ณต๊ฐ„์ธ 0111์˜ ๋ฐ์ดํ„ฐ๋„ ๊ฐ™์€ ์›๋ฆฌ๋กœ ์บ์‹ฑํ–ˆ๋‹ค. ์ด๋•Œ Way 1์— ์†ํ•œ ๋‘ ๋ธ”๋ก์€ ์ฐธ์กฐ๋˜์ง€ ์•Š์•˜๊ธฐ ๋•Œ๋ฌธ์— LRU ๊ฐ’์ด ์ฆ๊ฐ€ํ–ˆ๋‹ค.

Handling Cache Writes

๋ฐ์ดํ„ฐ๋ฅผ ์ฝ๋Š” ๋™์ž‘์ด ์•„๋‹ˆ๋ผ ์ž…๋ ฅํ•˜๋Š” ๋™์ž‘์ด ๋ฐœ์ƒํ•˜๊ณ , ๋ฐ์ดํ„ฐ๋ฅผ ๋ณ€๊ฒฝํ•  ์ฃผ์†Œ๊ฐ€ ์บ์‹ฑ๋œ ์ƒํƒœ(Write hit)๋ผ๋ฉด ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์—…๋ฐ์ดํŠธ๋˜๋Š” ๋Œ€์‹  ์บ์‹œ ๋ธ”๋ก์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์—…๋ฐ์ดํŠธ๋œ๋‹ค. ์ด์ œ '์บ์‹œ์—์„œ ์—…๋ฐ์ดํŠธ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์–ธ์ œ ๋ฉ”๋ชจ๋ฆฌ์— ์“ธ ๊ฒƒ์ธ๊ฐ€?'์— ๊ด€ํ•œ ๋ฌธ์ œ๊ฐ€ ์ƒ๊ธด๋‹ค. ์—ฌ๊ธฐ ๋‘ ๊ฐ€์ง€ ์“ฐ๊ธฐ ์ •์ฑ…(Write policies)์ด ์žˆ๋‹ค.

ํ•˜๋‚˜๋Š” Write-through ๋ฐฉ์‹์ด๋‹ค. ์บ์‹œ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์ž‘์„ฑ๋  ๋•Œ๋งˆ๋‹ค ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ๋งŽ์€ ํŠธ๋ž˜ํ”ฝ์ด ๋ฐœ์ƒํ•˜์ง€๋งŒ, ๋ฉ”๋ชจ๋ฆฌ์™€ ์บ์‹œ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๋™์ผํ•˜๊ฒŒ ์œ ์ง€ํ•  ์ˆ˜ ์žˆ๋‹ค.

๋˜ ๋‹ค๋ฅธ ๋ฐฉ์‹์€ Write-back ๋ฐฉ์‹์ด๋‹ค. ์ด ๋ฐฉ์‹์€ ๋ธ”๋ก์ด ๊ต์ฒด๋  ๋•Œ๋งŒ ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์—…๋ฐ์ดํŠธํ•œ๋‹ค. ๋ฐ์ดํ„ฐ๊ฐ€ ๋ณ€๊ฒฝ๋๋Š”์ง€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด ์บ์‹œ ๋ธ”๋ก๋งˆ๋‹ค dirty ๋น„ํŠธ๋ฅผ ์ถ”๊ฐ€ํ•ด์•ผ ํ•˜๋ฉฐ, ๋ฐ์ดํ„ฐ๊ฐ€ ๋ณ€๊ฒฝ๋˜์—ˆ๋‹ค๋ฉด 1๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค. ์ดํ›„ ํ•ด๋‹น ๋ธ”๋ก์ด ๊ต์ฒด๋  ๋•Œ dirty ๋น„ํŠธ๊ฐ€ 1์ด๋ผ๋ฉด ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๋ณ€๊ฒฝํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

๋ฐ์ดํ„ฐ๋ฅผ ๋ณ€๊ฒฝํ•  ์ฃผ์†Œ๊ฐ€ ์บ์‹ฑ๋œ ์ƒํƒœ๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด(Write miss) Write-allocate ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•œ๋‹ค. ๋‹น์—ฐํ•œ ์–˜๊ธฐ์ง€๋งŒ, ๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•˜๋ฉด ํ•ด๋‹น ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹ฑํ•˜๋Š” ๊ฒƒ์ด๋‹ค. write-allocate๋ฅผ ํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋‹น์žฅ์€ ๋ฆฌ์†Œ์Šค๋ฅผ ์•„๋‚„ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ ์บ์‹œ์˜ ๋ชฉ์ ์„ ๋‹ฌ์„ฑํ•˜์ง€๋Š” ๋ชปํ•  ๊ฒƒ์ด๋‹ค.

Software Restructuring

์—ฌ๊ธฐ๊นŒ์ง€ ๋กœ์šฐ ๋ ˆ๋ฒจ์—์„œ์˜ ์บ์‹œ ๊ตฌ์กฐ์™€ ๋™์ž‘์„ ์‚ดํŽด๋ดค๋Š”๋ฐ, ์ฝ”๋“œ ๋ ˆ๋ฒจ์—์„œ ์บ์‹œ์˜ ํšจ์œจ์„ ์ฆ๊ฐ€์‹œํ‚ฌ ์ˆ˜๋„ ์žˆ๋‹ค. ๋‹ค์Œ ์ด์ค‘ ๋ฃจํ”„๋ฅผ ๋ณด์ž:

for (i = 0; i < columns; i += 1) {
  for (j = 0; j < rows; j += 1) {
    arr[j][i] = pow(arr[j][i]);
  }
}

2์ฐจ์› ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ œ๊ณฑํ•˜๋Š” ๋ฃจํ”„๋‹ค. ํฐ ๋ฌธ์ œ๊ฐ€ ์—†์–ด๋ณด์ด์ง€๋งŒ ๊ณต๊ฐ„ ์ง€์—ญ์„ฑ์„ ๋”ฐ์ ธ๋ณด๋ฉด ๋น„ํšจ์œจ์ ์ธ ์ฝ”๋“œ๋‹ค. ๋ฐฐ์—ด arr์˜ ์š”์†Œ๋“ค์€ ๋ฉ”๋ชจ๋ฆฌ์— ์—ฐ์†์ ์œผ๋กœ ์ €์žฅ๋˜๋Š”๋ฐ, ์ ‘๊ทผ์€ ์ˆœ์ฐจ์ ์œผ๋กœ ์ด๋ค„์ง€์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

0          4          8          12         16         20         24
+----------+----------+----------+----------+----------+----------+
|  [0, 0]  |  [0, 1]  |  [0, 2]  |  [1, 0]  |  [1, 1]  |  [1, 2]  |
+----------+----------+----------+----------+----------+----------+
  1. i = 0, j = 0: ์ฒซ ๋ฒˆ์งธ ๊ณต๊ฐ„ [0, 0]์— ์ ‘๊ทผํ•œ๋‹ค.
  2. i = 0, j = 1: ๋„ค ๋ฒˆ์งธ ๊ณต๊ฐ„ [1, 0]์— ์ ‘๊ทผํ•œ๋‹ค.
  3. i = 1, j = 0: ๋‘ ๋ฒˆ์งธ ๊ณต๊ฐ„ [0, 1]์— ์ ‘๊ทผํ•œ๋‹ค.

์ด์ฒ˜๋Ÿผ ๊ณต๊ฐ„์„ ๋งˆ๊ตฌ ๊ฑด๋„ˆ๋›ฐ๋ฉฐ ์ ‘๊ทผํ•˜๊ฒŒ ๋œ๋‹ค. ๋”ฐ๋ผ์„œ ์•„๋ž˜ ์ฝ”๋“œ์ฒ˜๋Ÿผ ์™ธ๋ถ€ ๋ฃจํ”„๋Š” rows๋ฅผ, ๋‚ด๋ถ€ ๋ฃจํ”„๋Š” columns๋ฅผ ์ˆœํšŒํ•ด์•ผ ํ•œ๋‹ค.

for (i = 0; i < rows; i += 1) {
  for (j = 0; j < columns; j += 1) {
    arr[i][j] = pow(arr[i][j]);
  }
}

๋น„์Šทํ•˜์ง€๋งŒ ์‹œ๊ฐ„ ์ง€์—ญ์„ฑ์„ ํ™œ์šฉํ•˜๋Š” ์˜ˆ์‹œ๋„ ์žˆ๋‹ค. ๋‹ค์Œ ๋ฃจํ”„๋ฅผ ๋ณด์ž:

for (i = 0; i < n; i += 1) {
  for (j = 0; j < len; j += 1) {
    arr[j] = pow(arr[j]);
  }
}

๋ฐฐ์—ด arr์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ œ๊ณฑํ•˜๋Š” ๋™์ž‘์„ nํšŒ ๋ฐ˜๋ณตํ•˜๋Š” ์ด์ค‘ ๋ฃจํ”„๋‹ค. ํ˜„์žฌ ์ฝ”๋“œ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹ฑํ•œ ๋’ค, ๋‹ค์Œ ์ ‘๊ทผ ๋•Œ ์บ์‹ฑํ•œ ๋ฐ์ดํ„ฐ์— ์ ‘๊ทผํ•œ๋‹ค๋Š” ๋ณด์žฅ์ด ์—†๋‹ค. ์ „์ฒด ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹œ ํฌ๊ธฐ๋ณด๋‹ค ํฌ๋‹ค๋ฉด ๋ฐฐ์—ด์„ ์ˆœํšŒํ•˜๋Š” ๊ณผ์ •์€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์„ ๊ฒƒ์ด๋‹ค.

๋ฃจํ”„์˜ ์ „๋ฐ˜๋ถ€์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹ฑํ•˜์ง€๋งŒ, ๋ฃจํ”„๊ฐ€ ๋๋‚  ๋•Œ ์บ์‹œ๋Š” ํ›„๋ฐ˜๋ถ€์— ์ ‘๊ทผํ•œ ๋ฐ์ดํ„ฐ๋กœ ๋ฎ์–ด์”Œ์›Œ์ง„ ์ƒํƒœ๊ฐ€ ๋œ๋‹ค. ๊ทธ๋ž˜์„œ ๋‘ ๋ฒˆ์งธ ๋ฃจํ”„๋ฅผ ๋Œ ๋•Œ๋Š” ์ „๋ฐ˜๋ถ€ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ค์‹œ ์บ์‹ฑํ•ด์•ผ ํ•œ๋‹ค. ์บ์‹ฑํ•œ ๋ฐ์ดํ„ฐ์— ๋‹ค์‹œ ์ ‘๊ทผํ•˜๊ธฐ๋„ ์ „์— ์บ์‹œ ๋ธ”๋ก ์ „์ฒด๊ฐ€ ๊ต์ฒด๋˜์–ด ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์ด๋‹ค. ๋ฐฐ์—ด ์ˆœํšŒ ์ฃผ๊ธฐ๋ฅผ ์บ์‹œ ํฌ๊ธฐ๋งŒํผ ๋Š์–ด์ฃผ๋ฉด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ฃจํ”„๋ฅผ ๋„๋Š” ํšŸ์ˆ˜๋Š” ๋Š˜์—ˆ์ง€๋งŒ ์บ์‹œ ํžˆํŠธ ๋น„์œจ์€ ๋” ๋†’์•„์กŒ๋‹ค. ์„ธ ๋ฒˆ์งธ ๋ฃจํ”„๊นŒ์ง€๋Š” ์ „๋ฐ˜๋ถ€ ๋ฐ์ดํ„ฐ๋งŒ ์ฒ˜๋ฆฌํ•˜๊ณ , ๊ทธ ์ดํ›„๋กœ๋Š” ํ›„๋ฐ˜๋ถ€ ๋ฐ์ดํ„ฐ๋งŒ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์‚ผ์ค‘๋ฃจํ”„(!)๊ฐ€ ๋œ๋‹ค:

for (i = 0; i < len; i += CACHE_SIZE) {
  for (j = 0; j < n; j += 1) {
    for (k = 0; k < CACHE_SIZE; k += 1) {
      arr[i + k] = pow(arr[i + k]);
    }
  }
}

๋ฌผ๋ก  ์š”์ฆ˜์€ ์ปดํŒŒ์ผ๋Ÿฌ๊ฐ€ ๋ชจ๋‘ ์ตœ์ ํ™”๋ฅผ ํ•ด์ฃผ๊ธฐ ๋•Œ๋ฌธ์— ์‚ฌ์šฉ์ž ์–ดํ”Œ๋ฆฌ์ผ€์ด์…˜ ๊ฐœ๋ฐœ์ž๊ฐ€ ์ด๋Ÿฐ ๋ถ€๋ถ„๊นŒ์ง€ ์‹ ๊ฒฝ์“ธ ํ•„์š”๋Š” ์—†๋‹ค. โ€˜๋กœ์šฐ ๋ ˆ๋ฒจ์—์„œ ์ด๋Ÿฐ ์‹์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์ตœ์ ํ™”ํ•  ์ˆ˜ ์žˆ๊ตฌ๋‚˜โ€™ ์ •๋„๋งŒ ์•Œ๊ณ  ์žˆ์–ด๋„ ๊ดœ์ฐฎ์„ ๊ฒƒ ๊ฐ™๋‹ค.

References

  • David Patterson, John Hennenssy, โ€œComputer Organization and Design 5th Ed.โ€, MK, 2014.
  • Abraham Silberschatz, Peter Galvin, Greg Gagne, โ€œOperating System Concepts 9th Ed.โ€, Wiley, 2014.
  • K. G. Smitha, โ€œPara Cache Simulatorโ€.
โ†

ํ•˜๋‚˜์˜ ํƒ€์ž…์— ๊ฐ•์•„์ง€์™€ ๊ณ ์–‘์ด ๋‹ด๊ธฐ

ํŒŒ๋ผ๋ฏธํ„ฐ์˜ ๋‹คํ˜•์„ฑ๊ณผ ์ œ๋„ค๋ฆญ

โ†’

Git ์‚ฌ์šฉ ์ค‘ ์ž์ฃผ ๋งŒ๋‚˜๋Š” ์ด์Šˆ ์ •๋ฆฌ

์ฝ”๋”ฉ๋ณด๋‹ค ์–ด๋ ค์šด ๋ฒ„์ „ ๊ด€๋ฆฌ

โ† Articles