20181228

Algorithm

locality

• 지역성 : 데이터는 자주 참조되는 데이터와 그렇지 않은 데이터가 있다. 즉 데이터 참조에는 패턴이 있다

• CPU가 한번 참조한 데이터는 다시 참조할 가능성이 높고, 그 주변의 데이터 역시 참조될 가능성이 높다는 것

  • Temporal locality (시간 지역성)
    • 최근 사용되었던 메모리에 다시 접근하게 될 확률이 높다
    • 데이터 참조
  • Spatical locality (공간 지역성)
    • 최근 접근했던 메모리 근처를 다시 접근하게 될 확률이 높다
    • 명령어 가져오는 것

cache

• 교체 알고리즘
  • LRU
    • 캐시 내에서 가장 오랫동안 참조되지 않은 블록을 교체
  • FIFO
    • 캐시 내에서 들어온지 가장 오래 된 블록을 교체
  • LFU
    • 캐시 내에서 가장 적게 참조되었던 블록을 교체
• 쓰기 정책
  • 캐시 데이터와 메모리 데이터의 동일성 유지를 위함
  • Wirte Through
    • 캐시의 변화가 일어나는 즉시 메모리도 변화
  • Wirte back
    • 캐시의 데이터만 변화하고, 나중에 메모리가 캐시의 데이터에 접근할 때 갱신

quick sort가 빠른 이유

• 캐시 효율성이 높다