Doputer

Victim cache์— ๊ด€ํ•˜์—ฌ๐Ÿงฑ

Summary

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

 

์บ์‹œ๋Š” ํ”„๋กœ์„ธ์„œ์™€ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์ด์—์„œ ๋™์ž‘ํ•˜๋Š” ์ž‘๊ณ  ๋น ๋ฅธ ๋ฉ”๋ชจ๋ฆฌ์ด๋‹ค. ํ”„๋กœ์„ธ์„œ๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์˜ค๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ ์‚ฌ์šฉํ•  ์ •๋ณด๋ฅผ ์บ์‹œ์— ๋ฏธ๋ฆฌ ์ €์žฅํ•ด๋†“๊ณ  ๊บผ๋‚ด๋‹ค ์‚ฌ์šฉํ•œ๋‹ค.

 

Conflict miss

์บ์‹œ์— ํ•„์š”ํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์—†์œผ๋ฉด ๋ฏธ์Šค(miss)๋ผ๊ณ  ํ•œ๋‹ค. ์ด๋Ÿฐ ๊ฒฝ์šฐ ๋‹ค์Œ ์บ์‹œ๋‚˜ ๋ฉ”๋ชจ๋ฆฌ์— ์ ‘๊ทผํ•ด์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์ ธ์™€์•ผํ•œ๋‹ค. ๋ฐ˜๋ฉด์— ํ•„์š”ํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ํžˆํŠธ(hit)๋ผ๊ณ  ํ•œ๋‹ค.

 

๋ฏธ์Šค๋Š” ํฌ๊ฒŒ ๋„ค ๊ฐ€์ง€๋กœ ๋ถ„๋ฅ˜ํ•˜๋Š”๋ฐ ๊ทธ ์ค‘ ๊ฐ€์žฅ ๋งŽ์ด ๋ฐœ์ƒํ•˜๋Š” ๊ฒƒ์ด conflict miss์ด๋‹ค. ์ €์žฅํ•  ๋ฐ์ดํ„ฐ๋“ค์ด ์บ์‹œ์˜ ๊ฐ™์€ ์ฃผ์†Œ์— ํ• ๋‹น๋˜์–ด์„œ ์ƒ๊ธฐ๋Š” ๋ฏธ์Šค์ด๋‹ค.

 

๋ฏธ์Šค์˜ ์ฆ๊ฐ€๋Š” ์„ฑ๋Šฅ์— ํฐ ์˜ํ–ฅ์„ ์ฃผ๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•ด ์—ฌ๋Ÿฌ ๋ฐฉ๋ฒ•๋“ค์ด ์ œ์‹œ๋๋‹ค.

 

Victim cache

๊ทธ ์ค‘ ํ•˜๋‚˜๊ฐ€ ๋ฐ”๋กœ conflict miss๋ฅผ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•œ victim cache์ด๋‹ค. ๋น…ํŒ€ ์บ์‹œ๋Š” direct-mapped cache์™€ next lower cache ์‚ฌ์ด์— ์œ„์น˜ํ•˜๋Š” ์ž‘์€ fully-associative cache์ด๋‹ค. direct-mapped cache์˜ ๋ถ€์กฑํ•œ ์›จ์ด(way)๋ฅผ ๋ณด์ถฉํ•ด์ฃผ๋Š” ์—ญํ• ์„ ํ•œ๋‹ค.

 

๋น…ํŒ€ ์บ์‹œ์˜ ์ž‘๋™ ์›๋ฆฌ๋ฅผ ์ผ€์ด์Šค ๋ณ„๋กœ ๊ตฌ๋ถ„ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

Case 1 : Primary cache hit
์ •์ƒ ์ž‘๋™ํ•œ๋‹ค.

Case 2-1 : Primary cache miss, victim cache miss
Primary cache์˜ ๋ธ”๋ก์ด ๋น„์–ด์žˆ๋Š” ๊ฒฝ์šฐ, primary cache์—๋งŒ ์ €์žฅํ•œ๋‹ค.

Case 2-2 : Primary cache miss, victim cache miss
Primary cache์˜ ๋ธ”๋ก์— ๋ฐ์ดํ„ฐ๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ, ๋ฐ์ดํ„ฐ๋ฅผ victim cache๋กœ ์ด๋™ ํ›„ primary cache์— ์ €์žฅํ•œ๋‹ค.

Case 3 : Primary cache miss, victim cache hit

๋ฏธ์Šค๊ฐ€ ๋ฐœ์ƒํ•œ primary cache ๋ธ”๋ก๊ณผ ํžˆํŠธ๊ฐ€ ๋ฐœ์ƒํ•œ victim cache ๋ธ”๋ก์„ ์Šค์™‘(swap)ํ•œ๋‹ค.

 

๋น…ํŒ€ ์บ์‹œ๋ฅผ ํ†ตํ•ด conflict miss๋ฅผ ์–ผ๋งˆ๋‚˜ ๊ฐœ์„ ํ•  ์ˆ˜ ์žˆ๋Š”์ง€๋Š” ๋‹ค์Œ ํ‘œ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 

Vary cache size & line size

 

์บ์‹œ ํฌ๊ธฐ ๋ณ„ ์ „์ฒด ๋ฏธ์Šค ๊ฐœ์„ ์„ ๋‚˜ํƒ€๋‚ธ ํ‘œ์ด๋‹ค. ๋ผ์ธ ์‚ฌ์ด์ฆˆ๋Š” 16B๋กœ ๊ณ ์ •ํ•˜๊ณ , ๋ผ์ธ ์ˆ˜๋งŒ ๋Š˜๋ ค์„œ ํ”„๋ผ์ด๋จธ๋ฆฌ ์บ์‹œ ํฌ๊ธฐ๋ฅผ ์กฐ์ ˆํ–ˆ๋‹ค.

 

์—ฌ๊ธฐ์„œ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๋Š” ํŠน์ง• ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. ์šฐ์„ , ๋ผ์ธ ์‚ฌ์ด์ฆˆ๋Š” ๊ณ ์ •ํ•˜๊ณ , ์บ์‹œ ํฌ๊ธฐ๋งŒ ๋Š˜๋ ธ๊ธฐ ๋•Œ๋ฌธ์— ์ƒ๋Œ€์ ์œผ๋กœ ์ž‘์€ ๋น…ํŒ€ ์บ์‹œ๊ฐ€ conflict miss๋ฅผ ํฌ๊ฒŒ ๊ฐœ์„ ํ•ด์ฃผ์ง€ ๋ชปํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋ฐœ์ƒํ•˜๋Š” conflict miss๊ฐ€ ์ค„์–ด๋“ค๋ฉด ๋น…ํŒ€ ์บ์‹œ ๊ฐœ์„ ๋Ÿ‰๋„ ์ค„์–ด๋“ค๊ณ , ๋ฐ˜๋Œ€๋กœ ๋ฏธ์Šค๊ฐ€ ๋Š˜์–ด๋‚˜๋ฉด ๊ฐœ์„ ๋Ÿ‰๋„ ๋Š˜์–ด๋‚œ๋‹ค.

 

 

๋ผ์ธ ์‚ฌ์ด์ฆˆ ๋ณ„ ์ „์ฒด ๋ฏธ์Šค ๊ฐœ์„ ์„ ๋‚˜ํƒ€๋‚ธ ํ‘œ์ด๋‹ค. ์บ์‹œ ํฌ๊ธฐ๋Š” 4KB๋กœ ๊ณ ์ •ํ•˜๊ณ , ๋ผ์ธ ์‚ฌ์ด์ฆˆ๋งŒ ์กฐ์ ˆํ–ˆ๋‹ค.

 

์บ์‹œ ํฌ๊ธฐ๋ฅผ ๊ณ ์ •ํ•˜๊ณ  ๋ผ์ธ ์‚ฌ์ด์ฆˆ๋งŒ ๋Š˜๋ฆฌ๊ฒŒ ๋˜๋ฉด ๋ธ”๋ก ์ˆ˜๊ฐ€ ์ค„์–ด๋“ ๋‹ค. ์ด๋Ÿฐ ๊ฒฝ์šฐ ๊ณต๊ฐ„์  ์ง€์—ญ์„ฑ(spatial locality)์ด ๊ฐ์†Œํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ผ์ธ์ด ์ผ์ • ์ด์ƒ ์ปค์ง€๊ฒŒ ๋˜๋ฉด ๋ฏธ์Šค๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฏธ์Šค๊ฐ€ ์ฆ๊ฐ€ํ•˜๋ฉด ๋น…ํŒ€ ์บ์‹œ์˜ ๊ฐœ์„ ๋Ÿ‰์ด ๊ฐ™์ด ์ฆ๊ฐ€ํ•œ๋‹ค.

 

Conclusion

์œ„์— ๋‘ ๊ฐ€์ง€ ๊ทธ๋ž˜ํ”„๋ฅผ ๋ณด๊ณ  ์˜คํ•ดํ•˜๋ฉด ์•ˆ๋˜๋Š” ์ ์ด ์žˆ๋‹ค. ๋น…ํŒ€ ์บ์‹œ์˜ ๋ฏธ์Šค ์ œ๊ฑฐ์œจ์ด ๋†’๋‹ค๊ณ  ํ•ด์„œ ์ปดํ“จํ„ฐ์˜ ์„ฑ๋Šฅ์ด ๋ฌด์กฐ๊ฑด ์ข‹๋‹ค๊ณ  ๋งํ•  ์ˆ˜ ์—†๋‹ค. ์˜คํžˆ๋ ค ๋น…ํŒ€ ์บ์‹œ์˜ ์—ญํ• ์ด ์ปค์ง€๋Š” ๊ฒƒ์€ ํ”„๋ผ์ด๋จธ๋ฆฌ ์บ์‹œ์˜ ๋ฏธ์Šค๊ฐ€ ์ปค์ง„๋‹ค๋Š” ๊ฒƒ๊ณผ ๊ฐ™์€ ๋ง์ด๋‹ค.

 

์ปดํ“จํ„ฐ ์„ฑ๋Šฅ ํ–ฅ์ƒ์„ ์œ„ํ•ด์„œ๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ์š”์†Œ๋“ค์„ ์ข…ํ•ฉ์ ์œผ๋กœ ๋ฐ”๋ผ๋ด์•ผํ•œ๋‹ค. ๋งŒ์•ฝ์— ๋น…ํŒ€ ์บ์‹œ๋ฅผ ๊ตฌํ˜„ํ•˜๋ ค๊ณ  ํ•œ๋‹ค๋ฉด ์บ์‹œ ํฌ๊ธฐ, ๋ผ์ธ ์‚ฌ์ด์ฆˆ ๋“ฑ์˜ trade-off๋ฅผ ๊ณ ๋ คํ•ด์„œ ์ฃผ์–ด์ง„ ์ƒํ™ฉ์— ๋งž๋Š” ์ตœ์ ์˜ ์กฐ๊ฑด์„ ์ฐพ๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๋‹ค.

 

Reference

  • Norman P. Jouppi, “Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers”, IEEE, 1990.
  • David Patterson, John Hennenssy, “Computer Organization and Design : The Hardware and Software Interface 5th Ed”, MK, 2014.
๋ฐ˜์‘ํ˜•

๋ธ”๋กœ๊ทธ์˜ ์ •๋ณด

Doputer

#๊น€๋„ํ˜„

ํ™œ๋™ํ•˜๊ธฐ