Software blog

Tomasulo Data Structure

Tomasulo-Style Register Renaming

• Names
  • Architectural registers
• Locations
  • 레지스터 location은 레지스터 파일과 reservation station 두 곳.
  • Value는 두 곳 모두 있을 수 있음.
    • WAR hazard를 제거하는 카피들.
  • Value 기반 또는 copy 기반 renaming이라고 부름.
• Location은 내부적으로 tag들에 의해 참조 됨.
  • 레지스터 테이블에서 tag로 이름을 변환함.
  • Tag
    • 0인 경우 레지스터 파일 안을 의미하고
    • 0이 아닌 경우 할당된 RS#Tag 안을 의미한다.
  • CDB는 브로드캐스트할때 Tag와 value를 붙여서 한다.
    • 그래서 인스터럭션은 자기들이 찾는 어떤 값이 뜨는 지 알 수 있다.
• Allocation scheme

  

  • RS에 해당 Tag가 비어 있으면 할당 하는데
    • 이때 Functional Unit의 오퍼렌드에 해당 하는 Value를 실제 레지스터로부터 복사하여 값을 넣어 둔다.
      • 값을 RS에 카피하는 것이 이 알고리즘에서는 큰 의미가 있는 것으로 보임.
      • 복사를 통해서 해당 물리 레지스터를 자유롭게 만들어 줌.
      • 인스트럭션이 이슈 되기 전에 이미 해당 레지스터들이 카피 되었기 때문에 anti-dependency와 output-dependency가 해결 될 수 있음.
      • Mapping을 통한 rename이 내가 생각 했던 false 디펜던시들의 레지스터 이름을 교환 하는 것이 아닌 것으로 보임. 실제로 매핑 테이블에는 RS Tag를 넣는데 이 매핑 정보는 true dependency가 존재 할 때만 assign되므로 단순히 인스트럭션의 레지스터 이름들을 각각 변경 한다기 보다는 다음 인스트럭션에서 해당 인스트럭션이 복사 되지 않고 (not ready) 기다려야 하는지에 대한 이름을 통해서 알고(value-based) 실제 인스트럭션이 execution 될 때는 오퍼렌드들이 reservation station에 존재 하기 때문에 레지스터 이름이 V1,V2,T1,T2를 참조하도록 Renaming 했다고 명명 하는 것으로 보여짐.
      • Hennessy가 virtual register들은 실제 물리 레지스터보다 많을 수 있다는 것이 복사 의해서 RS와 실제 물리 레지스터들에 값들이 존재 하는 것으로 볼 수 있음
      • 개인적으로는 인스트럭션마다 4개의 캐시 레지스터를 할 당 할 수 있는 유한 원소의 테이블을 가지고 있는 것으로 Replace victim시 stall을 수행 하고 할당하는 동작 전체가 캐시와 거의 유사하게 보임, 그다지 매력적인 알고리즘으로 보이지는 않지만, 사이클당 인스트럭션의 dependency를 specific하게 판단 할 수 있게 하는데 의의가 있는 것으로 보여짐.
    • 만약에 실제 레지스터가 다른 인스트럭션에 의해 수행 되는 것 때문에 디펜던시가 존재 한다면 태그 값을 카피 하여 넣어 둔다.

Tomasulo's algorithms example

• 기본적인 동작
  • DS는 Stall의 경우를 제외 하고는 들어온 순차적으로 수행(in-order)
  • IS 전에서는 Register Status를 체크하고 Dependency가 없는 경우만 IS에 진입 할 수 있도록 함.
  • EX, IS가 이슈 되고 나면 다음 단계에서는 반드시 실행.
  • WB에서는 Register Status와 RS를 Release해 줌.
• 1 cycle

  

  • 순차적 수행으로 디스패치를 수행, 첫 번째 인스트럭션의 RS를 할당하고 Write의 f0fmf 위한Register status를 할당.
• 2 cycle

  

  • 두번째 사이클에서 Busy인 ldf를 이슈함. Mulf를 위한 RS를 할당하고 fo의 dependency를 copy함
  • Write 대상을 위해 f4에 대한 register status를 할당.
• 3 cycle

  

  • IS된 ldf는 execution 사이클
  • mulf는 확인결과 해당 오퍼랜드1의 레지스터 f0가 release 되지 않았으므로 이슈 시키지 않고 스킵 함.
  • 디스패치에서는 다음 인스트럭션인 stf를 가져와서 RS에 할당. 오버랜드1을 Register Status에서 check해보니 할당된 RS가 존재 하므로 Dependency를 T1을 통해 복사.

       

• 4 cycle

  

  • WB사이클을 마친 ldf는 CDB를 통해서 해당 f0와 함께 tag RS#2를 브로드캐스트
  • CDB의 브로드캐스트에 의해 Register Status의 f0는 해제 되고 또한 RS의 RS#2 값을 가진 RS들을 룩업, CDB의 Value에 해당 값이 존재 하므로 RS#4의 T1을 제거하고 CDB의 Value값을 V1으로 복사 한 뒤 사이클 수행
  • 다음 인스트럭션 add에 대하여 오퍼랜드 레지스터 복사, 타겟 레지스터를 Register Status에서 확인 후 할당된 RS로 교체
• 5 cycle

  

  • Execution단계에서는 mulf를 수행
  • 이슈단계에서 stf를 확인 해보면 stf의 오퍼랜드1이 RS#4와 dependency가 존재하기 때문에 아직 이슈잉 하지 않고 스킵.
  • 다음 인스트럭션인 add를 확인 결과 dependency가 없기에 add를 이슈함.
  • 다음 ldf의 타겟 레지스터를 확인, f0가 이전에 릴리즈되어 free상태이므로 register status를 RS 태그로 할당하고 RS는 해당 오퍼랜드 레지스터를 복사 하면서 할당.
• 6 cycle

  

  • mulf는 수행 사이클이 3이라고 가정 되었기 때문에 execution 사이클에 대기
  • sft 의 오퍼랜드1이 RS#4와 디펜던시가 존재 하므로 이슈 하지 않음.
  • Add는 이슈가 되었으므로 해당 EX 사이클 수행.
  • ldf 의 오퍼랜드를 확인, 오퍼랜드2가 디펜던시가 존재 하므로 이슈 하지 않음.
  • 다음 인스트럭션인 mulf를 수행하기 위해 register status를 확인
    • f4에 RS#4가 할당 되어 있지만 이는 해당 RS가 FP로 동일하고 먼저 이슈가 된 것이 RS에 의해서 확인이 가능 하기 때문에 반드시 앞에서 수행된 RS가 먼저 WB을 할 것이 확실해짐으로 f4가 사용이 가능함.
    • 이러한 이유로 WAW에 의한 스톨이 없음.
    • f4에 RS태그로 값을 할당하고 RS 할당.
• 7 cycle

  

  • mulf는 아직 사이클 소모가 완전히 되지 않았음,
  • stf를 확인, stf는 오퍼랜드2의 값이 클리어 되지 않았으므로 이슈하지 않음.
  • add인스트럭션은 EX를 마쳤으므로 WB수행.
    • WB후 해당 타겟 레지스터는 완료가 되었으므로 CDB에 의해서 브로드캐스트
    • 브로드캐스트 받은 Register Status에 해당 태그가 존재하는 레지스터를 릴리즈.
    • 브로드 캐스트 받은 RS는 해당 태그의 T값이 존재 하는지 룩업 후, T를 클리어하면서 해당 V값에 CDB의 V값을 복사
  • ldf에는 방금 디펜던시가 존재하던 레지스터가 클리어 되었으므로 이슈가 가능.
    • R1의 Antidependency가 없이 수행 된것과 결과가 동일.
  • stf를 디스패치 하기 위해 확인, sft의 RS가 모두 Full이므로 디스패치가 불가능(인스트럭션 버퍼가 꽉 찾으므로) 해당 인스트럭션은 stall됨.

       

• 8 cycle

  

  • mulf가 EX 사이클을 마쳤으므로 WB수행
    • WB후 CDB에 의해서 RS#4태그가 브로드캐스트
    • Register Status는 두번째 mulf때문에 클리어 할 것이 없음.
    • RS 해당 태그 엔트리는 FREE시키고 해당 태그를 가지고 있는 T 오퍼랜드는 클리어 후 해당 값을 V레지스터로 복사.
• 9 cycle

  

  • 이슈된 stf의 EX 사이클 소모
  • EX가 끝난 ldf의 WB
    • CDB를 통해서 RS#2 태그와 값을 브로드캐스트
    • Register Status에서 해당 값 클리어
    • RS에 해당 값을 클리어하고 CDB의 값을 V에 복사
    • 해당 태그의 RS의 엔트리는 Free
  • mulf는 앞에서 수행 되었던 클리어작업에 의해서 이슈가 가능해짐.
• 10 cycle

  

  • 이슈와 EX가 끝난 stf와 mulf를 차례로 수행.

RS Implementation

• Tag/CDB 파트는 각각 인스트럭션 윈도와 스케줄러라는 이름으로 불림.
• Wakeup
  • CDB 태그 브로드캐스트와 매칭 작업을 의미함.
  • 긴 버스와 함께 많은 비교 작업 수행.
• Select
  • 이번 사이클을 이슈하기 위한 인스트럭션을 수행 할 것을 선택하는 
  
  
  
  
  
  
  Example
  http://www.ecs.umass.edu/ece/koren/architecture/Tomasulo1/tomasulo_files/tomasulo.htm

  
  

Tomasulo's Algorithms

• 인스트럭션 버퍼를 RS, reservation station으로 사용 하는 형태.
  • 스코어보드는 중앙 centralized 되었던 것에 비하여 Tomasulo는 분산 제어 스킴임.
    • 데이터 bypassing
    • Common data bus(CDB)가 RS의 결과를 브로드 캐스트 해줌.
    • 레지스터 리네임을 통하여 antidependency와 output dependency를 해결 해줌.
      • 정확히 이야기 하면 RS에 V와 T 레지스터 래치 묶음을 가지고 복사하는 형태로 디펜던시를 해결 함.
  • 다이나믹 스케줄을 FP 유닛에만 적용한 것으로 가정.

       

Tomasulo Data Structure

• RS
  • Busy, FU, op R : 목적지 레지스터의 이름
  • T1, T2는 소스 레지스터 태그(RS#)임.
    • 값을 만들 RS#레지스터
    • CA Textbook에는 Qj. Qk라는 이름으로 호칭함.
  • T는 목적지 레지스터 태그임.
    • RS#이 T#의 레지스터에 값을 쓸 것임.
    • CA Textbook에는 Qi로 표기
  • V1, V2
    • 소스레지스터의 값.
    • CA Textbook에는 Vi, Vj로 표기.
• Register Table(Register Status)
  • T의 값을 컨텐츠로 가짐
  • 다시 말해 필드 값들이 RS엔트리 인덱스임.
• CDB
  • 완료된 인스트럭션의 <Value, Tab>를 브로드캐스트 함.
• TAG는 일종의 Ready bit과 유사하게 사용 됨.
  • Tag가 0이면 값에 대한 동작은 이미 마치거나 해당 사항 없음.
  • 만약 0이 아니라면 아직 그 값에 대한 결과가 나오지 않았으므로 해당 TAG가 CDB에 의해서 브로드캐스트 될 때 까지 기다려야 함.

  

Scoreboard Vs. Tomasulo

• 레지스터 리네이밍을 위한 Tomasulo의 구현사항
  • RS내의 Value 복사
  • 인스트럭션은 RS내에 자기가 소유한 Input value를 쥐고 있음.
    • 쥐고 있다는 것이 해당 V,T레지스터에 실제 입력값을 복사한 형태임을 의미함.
  • 다음 인스트럭션은 RF 레지스터 복사본을 오버라이트 할 수 있음.
    • 이슈가 된 상태에서는 RS의 구분이 확실히 가능 하기 때문에 순서상 WAW와 같은 Hazard가 발생하지 않음을 확신 할 수 있음.

Tomasulo Pipeline1

• 새로운 파이프라인 구조
  • DS(Dispatch)
    • RS의 Available 한지 확인.
    • 가능하다면 RS를 할당하고 copy ready value, non-ready tags를 RS에 할당함.
      • Non-read tags는 레지스터 태그 인덱스를 의미함.
      • 차후 디펜던시를 파악하는데 사용
    • 가능하지 않다면 Stall
      • 캐시의 full상태와 유사함.
  • IS(Issue)
    • 오퍼랜드가 준비 되었는지 확인
      • 준비 되었다면 execute
      • 아니라면 wait하면서 CDB를 Monitor함.
  • WB(Writeback)
    • CDB가 Available 한가를 확인
      • 하다면 결과를
        • 브로드캐스트 하고
        • 레지스터에 write 한 뒤
        • RS를 해제함.
      • 아니라면 Wait

Tomasulo Dispatch, DS

Tomasulo Issue, IS

Tomasulo Execute, EX

Tomasulo Writeback, WB

Dynamic Scheduling

• 싱글 사이클 오퍼레이션일때는 기본 파이프라인이 순서적 동작(In-order issue)로 부터 시작 되었음
• 기본 파이프라인이 멀티 사이클 오퍼레이션으로 확장되고 멀티플 이슈가 가능 해짐에 따라 다이나믹 스케줄링이 필요해짐.
• 다이니믹 스케줄링은 Out-of-order로 동작을 가능하게 함.

Dynamic Scheduling Motivation

• 
• Cycle 4에 addf 인스트럭션의 stall은 RAW의 True dependency에 의해서임.
  • 이 부분은 펀더멘털 문제이기 때문에 괜찮다고 가정
• 문제는 mulf의 cycle4도 pipline hazard때문에 stall 된다는 것임.
  • mulf 가 스톨되는 이유는 addf가 ID 단계에서 멈춰 있기 때문임.
  • 특정한 펀더멘털 이슈가 존재 하지 않기 때문에 이러한 부분을 해결 하고자 하는 것이 다이나믹 스케줄링의 기본 컨셉.
• 이러한 문제를 해결 할 수 있으면 아래와 같은 이점이 존재
  • Stall을 줄임.
  • Functional unit의 utilization을 증가시킴.
  • Out-order이기에 병렬 수행이 가능함.

Scheduling definition

• 퍼포먼스를 최대화 하기 위한 인스트럭션 re-arrange과정임.
  • 프로세서 구조에 대한 지식이 필요함.
  • 디펜던시와 레이턴시에 대한 기본적 지식도 필요함.
  • Static scheduling은 컴파일러에 의해서 수행.
• 소프트웨어는 하드웨어가 할 수 있는 대부분의 것들을 구현 할 수 있는데도 불구하고 하드웨어적으로 이를 해결 하고자 하는 이유는 무엇인가?
  • 퍼포먼스 Portability
    • 컴파일러는 새로운 머신에 대한 지식이 없음.
  • 하드웨어의 정보를 더욱 잘 알 수 있음.
    • Cache miss
    • Branch prediction
    • Addresses
  • 하드웨어에 대한 추론이 더 쉬움.
  • 하지만 컴파일러는 더 광범위한 인스트럭션을 볼 수 있기 때문에
    • 이 두 가지 어프로치를 모두 결합하여 성능을 향상시킴.

In-Order 파이프 라인의 문제점.

• 자주 IF, ID, EX, WB의 래치들이 Write됨.
• Structural hazard로 스테이지 마다 하나의 래치가 존재 한다는 것이 문제임.
  • 사이클당 하나의 스테이지에 한 개의 인스트럭션만 수행됨.
  • 나중에 이슈되는 인스트럭션은 하자드에 의한 스테이지가 그것을 해결 할 때까지 수행 될 수 없음.

Instruction Buffer

• In-Order 파이프라인의 문제점을 개선하기 위해 래치들의 묶음을 만들고 인스트럭션들을 홀딩 시키는 인스트럭션 버퍼를 제작.
• ID를 분리시킴.
  • IF뒤에 디코딩은 ID1에서 In order로 수행.
  • ID2S는 인스트럭션 버퍼에서 out-of-order형태로 인스터럭션을 가져옴.

Dispatch and Issue

• Dispatch (DS)
  • ID1이 DS임.
  • 인스트럭션 버퍼에서 새로운 리소스를 할당.
  • DS는 새로운 Structural hazard를 가지고 있음.
    • 인스트럭션 버퍼가 가득 찰 경우 다음 인스트럭션은 수행 될 수 없음.
• Issue (IS)
  • EX로 인스트럭션 버퍼의 인스트럭션 유닛을 보냄.
  • 여기서 중요한 점은 이때 out-of-order가 만들어진다는 것도 있지만 다음 인스트럭션으로 stall과 같은 wait을 전가 시키지 않는 것에 있음.

Virtual Memory Concept

• 사용자로 부터 메모리의 모든 물리적 성질을 감춤.
  • 메모리는 논리적으로 VAS에 바운드 됨.
  • VAS에 대한 부분은 언제나 물리 메모리 안에 있음.

Mapping from V2P Address

Paging

• Mapping
  • Virtual Address Translation
  • 
  • Translation Lookaside Buffer
    • 모든 virtual memory reference는 2번의 메모리 레퍼런스를 요구함.
    • 이를 해결 하기 위하여 TLB를 사용함
    • TLB는 Key로 페이지 index를 가지고 있고 value로 frame index를 가지고 있음.
    • 일종의 page table cache임.
  • 
• Protection and Sharing
  • Protection
    • 페이지 마다 protection이 명세 되어 있음
  • Sharing
    • 각기 다른 프로세스의 페이지 테이블 엔트리의 값을 같은 physical frame을 가리키게 하면 됨.

      

• Demand Paging
  • 필요할 때만 물리 메모리로 페이지를 가져옴.
  • 이점
    • 물리 메모리 사이즈에 프로그램 사이즈가 제약 당하지 않아도 됨
    • 적은 물리 메모리로 시스템을 구성 할 수 있음, 다시 말해 물리 메모리가 가용 할 수 있는 프로세스보다 많은 프로세스를 사용 할 수 있음.
    • IO가 적음.
  • 페이징 자체에 대한 이점
    • Contiguous 할당이 필요 없어짐에 따라 External fragment가 없어짐.
    • 필요에 따라 페이지의 위치를 재조정 할 수 있고 이를 중재 할 수 있음
    • 가변적인 size의 IO가 더 이상 필요 없음.
• Page faults
  • 맵핑 된 페이지가 없을 때 page fault.
  • 핸들링
    • Trap 서비스
    • 만약 free frame이 없다면 victim이 될 페이지를 결정해야 함.
    • Unmapped 페이지를 읽어옴
    • Restart faulting process.
• Virtual Memory reference
  • Memory Access time, 100ns, Disk access time, 25ms, page fault probability P = 0.000000004
    • Effective access time = 100(1-p) + 25,000,000 * p

Page replacement algorithm

• LRU
  • 최근에 사용된 페이지의 스텍을 유지 하고 있음.
    • TOP은 MRU, Most Recently Used page
    • Bottom은 LRU, Lest Recently Used page.
  • LRU의 케이스는 항상 bottom 부터 replace
• ALRU, Second chance Algorithms
  • Clock 알고리즘으로도 불림, 다양한 형태로 UNIX에서 사용.
  • 메모리에 거주하는 page들의 circular list를 유지하고 있음.
    • 매 레퍼런스마다 레퍼런스 bit이 하드웨어에 의해 세팅됨.
    • Page fault시에 clock은 reference bit이 0인 페이지를 sweep해봄.
      • Clock의 한번 돌 때 까지 레퍼런스 되지 않은 페이지를 replace함.
        다시 말하면 clock이 sweep할때 reference bit을 0으로 초기화 하고 다음 해당 페이지에 왔을 때 reference bit이 0이면 해당 페이지는 한번의 complete revolution 동안 참조 된 적이 없는 것임.

  

Page size concern over

• 페이지 사이즈가 작을 경우
  • Internal fragment가 적게 생길 것이고 memory utilization이 높아질 것임.
  • 페이지가 많아지니까 테이블 사이즈가 커지고 fault시 적은 사이즈를 fetch하므로 fault handling 오버헤드가 존재함.
• 페이지 사이즈가 클 경우
  • 상대적으로 페이지 테이블의 크기가 작아질 것이고 fault 핸들링 오버헤드가 적어짐
  • Internal fragment가 심해지고 memory utilization이 떨어짐.

IO Interlock

• DMA문제
  • Global page를 replacement한다고 가정
  • IO operation시 블럭 되어 있는 프로세스가 replace가 될 때 IO Operation에 corruption이 생길 수 있음
    • Asynchronous IO중 IO completion이 나지 않은 상황에서 memory의 컨텐츠가 변경되는 상황.
• 해결책
  • 물리 메모리가 사용 중 일 때는 lock bit를 사용하여 page를 lock시킴.
  • 모든 IO 수행 시에는 OS 영역 밖에서 처리.

Memory hierarchy

• 
• Memory Technology
• 
  • 메모리 테크놀러지와 두 타입의 로컬리티 사이의 매칭으로부터 최적화 결과를 얻음.
    • Temporal locality (in time)
      한번 참조된 아이템은 계속 참조 될 가능성이 높다.
    • Spatial locality (In space)
      참조된 아이템의 주변의 것들은 가까운 시일 내에 다시 참조 될 가능성이 높다.
  • 메모리 하이라키의 골은 highest level 메모리의 액세스 시간을 가지면서도 lowest 레벨 메모리 비용과 사이즈를 가진 가상의 Virtual Memory를 제공하는 것.

Memory Hierarchy Terminology

• HIT, 액세스 된 데이터를 Upper level에서 찾음
  • Hit Rate, upper level에서 찾아 액세스 되는 비율(Fraction)
  • Hit Time, upper level에서 액세스 되는 시간.
  • 
• Miss, 액세스 되는 데이터를 Lower level에서만 찾을 수 있음
  • 프로세서는 다음 레벨로 부터 데이터가 패치 될 때 까지 기다려야 함, 패치가 된 뒤에는 액세스를 리스타트 하여 계속 진행
  • Miss rate = 1 - hit rate
  • Miss penalty = lower 레벨로부터 블럭을 가져 오는 시간 + 위의 레벨에서 replace되는 시간
  • Hit time << miss penalty
    • 평균 메모리 액세스 시간 << worst case 액세스 시간.
    • 평균 메모리 액세스 시간 = hit time + miss rate * miss penalty

     

CPU Cache

• Upper level, SRAM
• Lower level, DRAM
• Cache의 목적은 SRAM 액세스 시간을 가지면서도 DRAM의 사이즈와 코스트를 제공 할 수 있는 메Virtual memory 테크놀러지를 제공.
• 추가적인 이익
  • 프로세서에 의해서 소비되는 메모리 bandwidth를 줄여서 IO를 위한 메모리 bandwidth를 좀 더 확보함
  • ISA 변경이 필요 없음.

     

Direct-mapped Cache

• 각 메모리 블록은 싱글 캐시 블록에 맵핑 됨.
• 맵된 캐시 블록은 메모리 블록 어드레스에 캐시 블록 개수를 나눈 나머지로 선택 할 수 있음.
• 
• Implementation Example
  • 블록 사이즈가 4바이트 이고 총 캐퍼시티가 4KB인 다이렉트 맵드 캐시를 고려.
    • 블록 당 1워드라고 가정.(4byte)
    • LSB 에서 2비트는 블럭 내에서 바이트(Offset)을 명세함. (2²)
    • 그 다음 10개의 어드레스는 캐시 내의 블록 인덱스 (2¹⁰ = 1024)
    • 그 다음 MSB로 부터 20비트는 메모리 블록을 위한 유니크한 태그로 구성
    • Valid 비트는 블럭이 정확한 메모리의 카피인지 아닌지를 명세함
    • Temporal 로컬리티를 이용(Exploit)함.
    • 
• Memory reference sequence example
  • Ref. address = { 0, 4, 8188, 0, 16384, 0 }
    • 0, (000000000000000000000, 0000000000, 00)
      Cache miss, Place block at index 0

      

    • 4, (000000000000000000000, 0000000001, 00)
      Cache miss, Place block at index 1

      

• 8188, (0000000000001, 1111111111, 00)
  Cache miss, Place Block at index 1023

  

• 0, hit
• 16384, (000000000000000000100, 0000000000, 00)
  Cache miss, 0주소 번지와 같은 인덱스, replace block a index 0

  

• 0
  방금 교체한 캐시블럭에서 다시 miss

  

• Spatial Locality를 Exploit하기 위한 하드웨어 구성.
  • 
  • 맵 캐시의 블록을 4 word 단위로 로드 되도록 구성함.
  • Block size vs. Cache miss

    

Cache Policy

• Write through
  • 캐시와 메인 메모리 양쪽으로 항상 데이터를 씀
  • 간단하지만 느리고 메모리 트래픽을 늘리는 경향이 있음.
  • Write buffer가 필요함.
• Write back
  • 캐시에만 Write하고 메인 메모리는 더티 블록이 replace될 때만 업데이트함.
  • 빠르지만 구현하기가 복잡하고 컨시스턴시에 문제를 가져 올 수 있음.

       

Set-Associative Caches

• Hit rate를 개선하기 위해서 인덱스당 멀티플 엔트리를 허용한 캐시 맵핑
  • N-Way Set associative cache는 캐시 레퍼런스시 n번의 conflict가 나는 것을 허용함.
    • N이 의미하는 것은 각 셋에서 캐시 블록의 개수.
    • N 비교 시 셋 내에서 병렬로 모든 블록을 검색 하는 것이 필요함.
    • 그 안에서 conflict 나는 경우, 각 블록은 replace됨.
  • Fully associative cache.
    • Single set이 캐시 블록 어디에나 메모리 로케이션이 replace될 수 있도록 매핑
  • Direct-mapped 캐시는 1 way, set-Associative cache임.
• 고정된 캐시 캐퍼시티에서 높은 Associativity는 높은 hit rate를 가지게 도움이 됨.
• Associativity는 캐시 컨텐츠를 최적화함.
• Cache Organization Spectrum
• 
• Implementation of Set Associative Cache
  • 소프트웨어로 구현 하는 것과 동일함.
  • Address에서 index 비트(offset을 제거한 값)로 block을 선택하고 tag값을 각 엔트리와 비교하여 히트 여부를 MUX를 통해 선택하게 함.
  • 
  • Cache organization Example
  • 
• Cache Block Replacement Policy
  • Direct-mapped Caches
    • 각 메모리 블록이 오직 하나의 Cache block을 차지 하기 때문에 Cache block replacement 정책이 없음.
  • N-way set-associative Caches.
    • 각 메모리 블록은 mapped set 내에서 어떤 n cache block이든 차지할 수 있음.
    • LRU replacement 정책은 mapped set 내에 블록들 사이에서 replace되어야 하는 블록을 선택 할 때 가장 일반적으로 사용 됨.
    • LRU는 가장 오랜 시간 동안 사용되지 않은 블록으로 교체함.
  • Miss rate vs. block size

    

  • Memory reference sequence examples
    • Ref. address = { 0, 4, 8188, 0, 16384, 0 }
    • 2 way set associate cache, block size는 1way당 2 word를 사용. (8byte)
    • 0, (0000000000000000000000, 00000000, 000)
      Initially cache miss

      

    • 4(0000000000000000000000, 00000000, 100)
      Cache hit to first block in set 0
      히트가 난 것은 set에 의한 것이 아니라 block 사이즈가 direct cache 보다 2배 큰 8byte를 수용 함으로서 pre-fetch 효과가 난 것으로 보임.
       

      

    • 8188
      Cache miss first block of set 255
       

      

    • 0, hit
    • 16384
      Cache miss, place in second block of set 0

      

    • 0, hit
       

         

Improving Cache Performance

• 캐시 퍼포먼스는 평균 메모리 액세스 타임으로 결정됨.
  • 평균 메모리 액세스 타임 = hit time + (miss rate * miss penalty)
• Hit time 감소하기 위해서는
  • 캐시를 좀 더 작게 만들면 됨, 대신에 miss rate는 증가.
  • Direct mapped를 사용 하면 됨, 마찬가지로 miss rate는 증가.
• Miss rate 감소
  • 캐시를 크게 만들면 됨, 그러나 hit time은 증가.
  • Associativity 를 늘리면 됨, 마찬가지로 hit time은 증가.
  • Block size를 늘리면 됨, 대신 miss penalty 증가.
• Decrease miss penalty
  • Miss penalty의 요소인 트랜스퍼 타임을 줄임.
  • 다른 레벨의 캐시를 하나 더 추가함.

     

Pipeline

• 파이프 라인은 명령들을 중첩 실행하여 CPU 성능을 향상 시키는 방법임
• 파이프라인을 구현하면 단일 태스크의 수행 시간이(Length) 줄어들지 않지만 전체 시간(throughput)이 줄어든다.
• Potential speedup = number pipe stages.

Stages

• IF, Instruction Fetch Cycle

  IR ¬ MEM[PC]

  NPC ¬ PC + 4

     

• ID, Instruction Decode / Register Fetch Cycle

  A ¬ Regs[IR 16 . .10], B ¬ Regs[IR 11 . . 15]

  Imm ¬ ( (IR₁₆)¹⁶ ## IR _{16 . . 31})

     

• Ex, Executive / Effective Address Cycle

  ALUOutput ¬ A + Imm ( MEMory reference)

  ALUOutput ¬ A op B (Register-Register ALU)

  ALUOutput ¬ A op Imm (Register-Immediate ALU)

  ALUOutput ¬ NPC + Imm, Cond ¬ (A op 0) (Branch)

     

• MEM, Memory Access / Branch completion Cycle

  LMD ¬ MEM[ALUOutput] ( MEMory access - load)

  MEM[ALUOutput] ¬ B ( MEMory access - store)

  IF (cond) PC ¬ ALUOutput ELSE PC <- NPC (Branch)

• Wr, Write-Back cycle

  Regs[IR 16..20] ¬ ALUOutput (Register-Register ALU)

  Regs[IR 11..15] ¬ ALUOutput (Register-Immediate ALU)

  Regs[IR11..15] ¬ LMD (Load)

     

Structural Hazard

• 프로세서의 하드웨어 포트가 두 개나 그 이상의 인스트럭션에서 같은 시간에 쓰려 하는 경우에 발생함.
• 
• 핑크색으로 표시된 부분이 Structural hazard가 발생 하는 이유
  • IF - MEM
    • IF는 PC값을 통하여 메모리를 액세스하는 Operation이 존재,
    • MEM는 Data를 Load하거나 Store하는 동작이 존재
    • 결국 IF-ME는 같은 메모리 리소스를 같은 시간에 쓰려고 하는 Structural hazard 발생.
  • ID, MEM
    • ID시에 브랜치 할 주소를 미리 계산하는데 이때 ALU와 ALUOutput 레지스터가 사용됨.
    • MEM에서 브랜치 오퍼레이션은 A와 B레지스터의 값을 비교 하는데 ALU를 사용하며 그 결과 Mux의 input으로 사용 하기 위해서 ALUOutput 레지스터를 사용
• Solution
  • 메모리 액세스 충돌을 피하기 위해서 I와 D 캐시를 분리.
  • Time-multiplexed나 레지스터 파일 액세스 충돌을 위한 멀티 포트 파일 레지스터 제공.

Data Hazard

• RAW, WAW, WAR의 종류가 존재
• RAW 예제 (Read and Write Example)
  • 
  • Pipeline의 두 번째 스테이지에서 사용되는 오퍼랜드가 첫 번째 인스트럭션의 결과 변화에 따라 영향을 받는 케이스임.
  • Read after write-back
• Solution
  • Freezing the pipeline
    • NOP를 추가 하는 것과 같으며 버블링이라고 부르기도 함.
    • ALU 결과를 다음 인스트럭션으로 가져는 법.
      • 데이터 Hazard가 생성되는 레지스터 가 WB 뒤에 오도록 나머지 시작 인스트럭션을 stall 시킴,

        

         

    • Load 결과를 다음 인스트럭션에서 로드 하는 법

      

  • (internal) Forwarding
    • 여기서 포워딩은 이전 상태의 결과 값을 피드백으로 이용 하는 것임
    • ALU 결과를 다음 인스트럭션으로 가져 가는 방법
      • Executive 가 끝나자 마자 ALUOut의 레지스터 값을 두 번째 인스트럭션의 ID로 피드 백 시킴,

        

      • 이런 식의 접근은 stall이 없어도 됨.
    • 결과를 로드 하는 방법
      • 앞에서 피드백 받는 것과 유사하지만 메모리 결과로 나오는 것을 로드.

        

  • Compiler scheduling

Control hazard

• PC를 변화 시키는 인스트럭션에 의한 문제
• Branch, Jump, Call, return 등에 이루어지며 다음 인스트럭션에 대한 예상을 미리 할 수 없기 때문에 생기는 현상.
• 
• Stall이라고 이야기 하는 것은 해저드의 요인이 소멸 될 때 까지 파이프라인을 소멸 시키는 동작임.
• Solution
  • 문제 정의
    • 다시 이야기 해서 Execution 단계에서 타겟 어드레스로 PC를 변경하여 코드를 실행 하게 되는데 이때 다음 인스트럭션이 벌써 ID(디코드)단계에 들어와 있으므로 이를 버리게 된다.
      • 버리기 위해 파이프라인의 스테이지들을 cancel하는 것을 pipeline flush라고 함.
    • 이때 이 버리게 되는 사이클을 의미 있게 하는 것이 hazard solution의 목적임
      (주로 브랜치 다음의 인스트럭션이 한 사이클 소비하게 되므로(틀렸을 때 )이 때 의미 있는 값을 넣어주거나 비워둠.
    • 하드웨어적으로는 WB에서 브랜치 되어야 하는 타겟을 아는 것이 아니라 ID에서 다음 타겟 주소를 IF에 피드백.
    • 
  • Optimized Branch Process
    • 미리 브랜치를 찾아서 그 브랜치를 사용 할 것(PC값을 바꾸는 것을 taken)인지 아닌지(not taken)를 선택함.
      브랜치 컨디션을 간단히 만듦
    • 타겟 어드레스를 미리 계산 하는 것으로 특별한 하드웨어의 지원이 필요함.
  • Branch prediction
    • Not taken으로 prediction 하는 경우, 기존 인스트럭션의 흐름 그대로 이며 taken branch instruction을 하는 경우 Idle(NOP)를 넣어서 한 사이클을 버려버림.
  • Delayed branch.
    • 브랜치 바로 다음에 오는 인스트럭션(i + 1)은 taken에서도 반드시 실행이 되고 untaken에서도 실행이 되므로 이 인스트럭션에 어차피 반드시 실행 되어야 하는 Delay slot을 넣어 인스트럭션을 세이브 하는 방법
    • Delay slot은 이전의 오퍼레이션의 영향을 받지 않는 인스트럭션을 이야기 함.
    •