[Advanced Computer Architecture] Advanced Memory Hierarchy

Advanced Memory Hierarchy

• Review: 6 basic cache optimizations

  • Giving reads priority over writes
  • Avoiding adress translation during cache indexing
  • multilevel cache
  • larger block size(compulsory misses)
  • larger cache size(capacity misses)
  • higher associativity(conflict misses)

• 11 advanced cache optimizations

  • Fast hit time vs. small and simple caches

    메모리 크기가 작으면 인덱싱하는데 시간이 적게 걸리므로 작은 캐시는 hit time을 줄일 수 있다.

    simple: direct mapping

  • Fast hit time vs. way prediction

    hit time이 빠른 direct napped cache와 conflict miss가 적은 2way set associativity cache를 어떻게 혼합할까?

    way prediction: 캐시 내의 여분의  bit을 두어 "way"를 예측한다. set안의 블럭, 다음 캐시 접근 등

  • fast hit time vs. trace cache

    더 많은 ILP 찾기

    메모리의 레이아웃에 의해 결정되는 고정적인 인스트럭션의 순서가 아닌 실행된 인스트럭션의 dynamic trace

    긴 블럭의 경우에 더 좋다. 블럭의 중간에서 나가거나 들어오지 않는다.

    주소가 더이상 2의 워드 크기의 거듭제곱꼴로 정해지지 않기 때문에 주소 매핑이 복잡하다.

    서로 다른 브랜치 결과때문에 여러 dynamic trace에 인스트럭션들이 여러 번 나올 수 있다.

  • increasing cache bandwidth by pipelining

    파이프라인 캐시 접근은 BW를 보장하지만 latency가 크다.

    브랜치 예측 미스에 대한 penalty가 크다,

    load의 issue와 데이터의 사용 사이에 더 많이 사이클이 생긴다.

  • increasing cache bandwidth: non-blocking cache

    미스된 동안에도 데이터 캐시가 계속해서 캐시 힛을 제공하도록 하는 캐시이다; 레지스터에 F/E bit, out-of-order execution, multi-bank memory가 요구된다.

    미스를 수행하는 동안에 hit을 제공하면 유효 마스페널티가 줄어든다.

    다중 미스 중 힛, 미스 중 미스,의 경우 여러개의 미스가 오버랩되므로 유효 미스 패널티는 훨씬 낮다.

    캐시 컨트롤러의 복잡도는 증가, 다중 뱅크 메모리 필요

  • increasing cache BW via multiple banks

    여러 독립적인 뱅크로 나누는 것이 동시 접근을 지원하기에 좋다.

    접근이 뱅크에 자연스럽게 분포되어 있을때 가장 성능이 좋다. -> 즉, 주소의 매핑이 메모리 시스템의 행동에 영향을 준다. 성늘이 좋은 단순한 매핑은 'sequential interleaving'

  • reduce miss penalty: early restart and critical word first

    CPU를 재시작하기 전에 full block을 대기하지 않는다.

    early restart: 요청한 블럭의 워드가 도착하자마자 CPU로 보내고 CPU가 실행을 계속하도록 한다.

    critical word first: 메모리로부터 미스된 워드를 먼저 요청하여, 도착하자마자 CPU로 보낸다. 블럭의 남은 워드를 다 채울동안 CPU는 실행을 계속한다.

  • merging write buffer to reduce miss penalty

    쓰기버퍼는 메모리에 쓰는 것을 대기하는 동안에도 프로세서가 동작하도록 한다.

    버퍼가 수정된 블럭을 갖는다면, 새로운 데이터가 적합한 쓰기 버퍼 엔트리의 주소와 맞는지를 보기위해 그 블럭의 주소를 체크한다. 엔트리가 맞으면, 새로운 데이터는 그 엔트리와 합쳐진다.

    multiword writes는 메모리에 더 효율적이기 때문에 sequential word, byte의 쓰기를 위한 write-through cache의 write의 block size를 증가시킨다.

  • reducing misses by compiler optimization

    instructions: conflict miss를 줄이기 위해 메모리에서 프로시져를 재구성한다. conflict를 프로파일링

    data: merging array: 엘리먼트를 합친 단일 배열은 두 개의 배열보다 spatial locality를 향상시킨다.

    loop fusion: 같은 루핑, 일부 변수의 오버랩이 있는 두 개의 독립적인 루프를 조합

    loop interchange: 메모리에 저장된 순서대로 데이터를 접근하도록 중첩된 루프를 변경

    blocking: 데이터의 "blocks"를 반복적으로 접근하게 함으로서 temporal locality를 증가시킨다.

    • merging array //val과 key의 conflict를 줄이고 spatial locality증가시킨다.

      /* Before: 2 sequential arrays */
         int val[SIZE];
         int key[SIZE];
      /* After: 1 array of stuctures */
      struct merge {
         int val;
         int key;
      };
      struct merge merged_array[SIZE];

    • loop interchange // striding하지 않고 매 100 word를 순차적으로 접근

      /* Before */
      for (k = 0; k < 100; k = k+1)
         for (j = 0; j < 100; j = j+1)
            for (i = 0; i < 5000; i = i+1)
               x[i][j] = 2 * x[i][j];
      /* After */
      for (k = 0; k < 100; k = k+1)
         for (i = 0; i < 5000; i = i+1)
            for (j = 0; j < 100; j = j+1)
               x[i][j] = 2 * x[i][j];

    • loop fusion // a, c에 접근할 때 두 개의 미스가 발생하던 것을 하나로 줄임.

      /* Before */
      for (i = 0; i < N; i = i+1)
         for (j = 0; j < N; j = j+1)
            a[i][j] = 1/b[i][j] * c[i][j];
      for (i = 0; i < N; i = i+1)
         for (j = 0; j < N; j = j+1)
            d[i][j] = a[i][j] + c[i][j];
      /* After */
      for (i = 0; i < N; i = i+1)
         for (j = 0; j < N; j = j+1)
            { a[i][j] = 1/b[i][j] * c[i][j];
              d[i][j] = a[i][j] + c[i][j];}

    • blocking

      /* Before */
      for (i = 0; i < N; i = i+1)
         for (j = 0; j < N; j = j+1)
            {r = 0;
               for (k = 0; k < N; k = k+1){
                  r = r + y[i][k]*z[k][j];};
                  x[i][j] = r;
            };

      z의 N*N element를 모두 read, 반복적으로 y의 첫 row의 N element를 read, x의 첫 row의 N element에 write

      2N^3 + N^2만큼의 capacity miss ==> B* B의 submatrix로 계산

      /* After */
      for (jj = 0; jj < N; jj = jj+B)
      for (kk = 0; kk < N; kk = kk+B)
      for (i = 0; i < N; i = i+1)
         for (j = jj; j < min(jj+B-1,N); j = j+1)
            {r = 0;
               for (k = kk; k < min(kk+B-1,N); k = k+1) {
                  r = r + y[i][k]*z[k][j];};
               x[i][j] = x[i][j] + r;
      };

      B는 blocking factor, capacity miss는 2N^3/B + N^2으로 감소

     

  • reducing misses by hardware prefetching of instructions & data

    prefetching은 페널티 없이 사용될 수 있는 여유의 메모리 BW가 있는가에 의존한다. 

    instruction prefetching: 일반적으로 CPU는 미스에서 두 개의 인스트럭션을 fetch하는데, 요청된 블럭과 연속된 다음 블럭이다. 값이 리턴될때 요천블럭은 인스트럭션 캐시에, prefetch된 인스트럭션은 인스트럭션 스트림버퍼에 위치한다.

    data prefetching: 두개의 연속적인 L2 캐시 미스가 발생하고, 두 캐시블럭의 거리가 256 byte이하이면 prepetching된다.

     

  • reducing misses by software prefetching data

    레지스터나 캐시에 prefetch, prefetching instruction은 speculation execution의 형태로 falut를 일으키지 않는다. prefetching instruction을 issue하는데 시간이 걸리지만, miss를 줄여서 얻는 이익보다 작다. issue BW를 줄이려면 higher superscalar

     

• Virtual machine

  • Java VM과 같은 표준 SW interface를 제공하는 모든 emulation method를 포함한다. 시스템 가상 머신은 binary ISA에서 완전한 시스템레벨 환경을 제공한다.하나의 컴퓨터는 여러 가상머신을 돌릴수있고 서로 다른 여러 OS를 지원한다. underlying HW platform은 host, guest VM들 사이에서 HW의 리소스를 공유한다.

  • vitrual machine monitor

    hypervisor하고도 하며, VM을 지원하는 소프트웨어이다. 가상 리소스와 물리적 리소스를 어떻게 매핑할 것인지 결정한다. 전통적인 OS에 비해 훨씬 규모가 작다.

  • VMM overhead

    workload에 따라 다르다. user-level processor bound program은 가상화 오버헤드가 없다. I/O intensive workload => OS intensive는 많은 시스템 콜과 privileged 된 인스트럭션이 수행되기 때문에 높은 가상화 오버헤드가 야기된다.  I/O intensive workload가 I/O bound라면 I/O를 기다리는 동안 프로세서 사용도가 낮고, 프로세서의 가상화가 hidden, 가상화 오버헤드가 작다.

• requirements of a virtual machine monitor

  • VMM은 guest SW에게 SW interface를 보여주어야 한다. 게스트의 상태를 각각 독립시켜야 한다. 게스트 소프트웨어로 부터 자신을 보호해야 한다.
  • 게스트 SW는 원래의 HW에서 동작하는 것과 똑같이 VM에서 동작해야 한다. 성능 관련 동작, 여러 VM이 공유해야 하는 고정 리소스에 대한 제한 등의 경우 예외
  • 게스트 SW는 실제 시스템 리소스의 할당을 변경할 수 없다.
  • VMM은 게스트 VM과 OS가 일시적으로 사용한다 하더라도 거의 모든 것을 제어해야 한다.
  • VMM은 게스트 VM보다 높은 선점권을 가져야 한다. 타이머 인터럽트의 경우, VMM은 현재 실행중인 게스트VM을 중지시키고 상태를 저장하고 인터럽트를 핸들하고 다음 실행할 게스트 VM을 결정하고 그 상태를 로드한다. 게스트 VM은 가상 타이머에 의해 제공된 타이머 인터럽트에 관여된다.

• ISA supports for VM

  • ISA를 설계할 때 VM이 계획된다면 VMM에 의해 실행되어야 하는 인스트럭션을 줄이기 쉽고, 이를 에뮬레이트하는데 얼마나 시간이 걸리는가를 알기 쉽다.
  • VMM은 게스트 시스템이 오직 가상 리소스와 상호작용하는것을 보장해야 한다. conventional guestOS는 user mode로 VM의 최상위에서 동작한다. 게스트 OS가 HW 리소스와 관련된 정보를 수정하려고 시도하면 이는 VMM으로 넘어간다.
  • 그렇지 않은 경우, VMM은 이 인스트럭션을 가로채서 정보의 가상버젼을 게스트 OS에 제공한다.

• impact of VMs on virtual memory

  • VMM은 real memory와 physical memory를 나눈다. real memory는 가상 메모리와 물리적 메모리의 중간단계이다. machine memory라고도 한다. 게스트 OS는 자신의 페이지 테이블에 가상 메모리와 real memory를 매핑하고, VMM 페이지테이블은 real memory와 physical memory를 매핑한다.
  • VMM은 shadow page table을 유지하는데 이는 virtual memory와 physical memory를 직접 매핑한다.

• ISA support for VMs & virtual memory

  • sw TLB를 virtualize하기 위해 VMM은 real TLB와 게스트 VM의 TLB의 내용의 카피를 갖는다. TLB에 접근하는 어떤 인스트럭션도 trap된다. 프로세스 ID tag를 갖는 TLB는 전체 서로다른 VM과 VMM의 mix를 지원하기때문에 VM이 스윗치될때 TLB를 flushing하는것을 피할 수 있다.

• Impact of I/O on virtual memory

  • 가장 어려운 virtualization이다. 컴퓨터에 추가되는 I/O device의 종류나 수가 증가하였고, 여러 VM들이 I/O device를 공유하고, 디바이스 드라이버 또한 무수히 많다.
  • I/O device driver의 각 타입의 일반적인 VM버전을 제공하고, VMM이 real I/O를 다루도록한다.
  • 가상 I/O device와 physical device의 매핑 방법은 디바이스의 타입에 따라 다르다.