Blog

Instruction-level Parallelism (2) Dynamic Scheduling Limitations of simple techniques A major limitation issue and execution in-order instruction issue and execution 명령어가 프로그램 순서에 따라 issue되고 명령어가 파이프라인에서 stall되면 이후 명령어를 처리할 수 없다. 명령어 j가 long-running 명령어 i에 종속성을 가지면, 명령어 j 이후에 실행될 모든 명령어들은 i가 끝나가 j가 실행될 때까지 stall돼있어야 한다. Simple techniques은 약간의 data dependence stalls만 제거할 수 있다. 몇몇 dependence는 런타임까..

Instruction-level Parallelism (1) Concepts and Challenges ILP Basics Instruction level parallelism (ILP) 명령어들의 실행을 오버랩하는 것. Goal: minimize CPI (maxmize IPC) Challenges Challenges: 모든 명령어가 병렬로 실행될 수 없다. 파이프라이닝된 프로세서에서 CPI = ideal CPI + (Structural stalls + Data hazard stalls + Control stalls) 종속성이 있는 명령어는 동시에 실행될 수 없다. 종속성의 세가지 종류 Data dependences Name dependences Control dependences Data Depende..

Way Prediction (to reduce hit time) Idea: 다음 캐시에 어떤 way나 block이 사용될 지 예측하자. - Set-associative cache는 블록을 묶어서 캐시 미스를 줄였지만 태그 매칭하는 것이 오버헤드가 된다. 만약에, 다음 캐시에 어떤 way나 block이 사용될 지 예측하여 캐싱을 해두면 성능 향상을 가져올 수 있을 것이다. 1. 예측이 맞다면, hit time을 줄일 수 있을 것이다. 그리고 다른 엔트리를 훑어보지 않아도 되기 때문에 에너지 소모가 적어진다. 2. 예측이 틀리면, 다른 엔트리를 확인해야 하기 때문에 hit time이 늘어날 것이다. 실행하는 프로그램의 지역성(locality)이 높아서 어떤 way나 block이 사용될 지 쉽게 예측할 수 있..

캐시 메모리 공부를 할 때 Direct-mapped cache, Set-associative cache 를 배운다. 얘들을 잘 살펴보면 캐시 메모리의 인덱스로 중간 비트를 사용한다. 상위 비트를 사용할 수도 있을텐데, 중간 비트를 사용하는 이유가 있을까? 다음과 같이 4개의 블록을 가진 캐시가 있다고 생각해보자. 이때 상위 비트 인덱싱을 하면 다음과 같다. 보는바와 같이 인접한 메모리 블록들이 같은 캐시 엔트리로 매핑된다. 메모리 블록에서 상위 4개는 캐시의 첫번째 블록에, 밑의 3개는 두번째 블록에, 그 밑의 3개는 세번째 블록에 매핑된다. 만약에 어떤 프로그램이 좋은 spatial locality를 갖고 있고, 어레이의 원소를 순차적으로 훑는 걸 생각해보자. 그렇게 되면, 캐시는 그 어레이를 훑을 때..

이때까지 Memory Hierarchy에 대해서 알아보았다. 그리고 메인 메모리에서 캐시 메모리에 매핑하는 방법, CPU에서 데이터를 메모리에 쓰는 방법에 대해서 알아보았다. 그러면 메모리는 계층 구조를 갖고 있다는 것은 알겠는데, 캐시 메모리도 계층 구조를 갖고 있을까? 답은 Yes다. 캐시 메모리도 다음과 같은 'Cache Hierachy'를 갖고 있다. 최근에 개발되고 있는 프로세서들은 보통 세개의 캐시를 갖고 있다. 이들은 각각 L1 Cache, L2 Cache, L3 Cahce라는 이름으로 불리는데, 이러한 계층 구조를 설계했을 때 장점은 무엇일까? 우리가 메모리 계층 구조를 왜 생각했는 지를 돌아보면 된다. 우리는 메모리의 사이즈는 크게, 처리 속도는 빠르게 메모리를 이용하고 싶어서 계층 구조..

이전 포스팅에서는 Cache Miss가 일어났을 때, 블록을 교체해주는 Eviction Policy에 대해서 알아보았다. 이는 CPU에서 메인 메모리에 데이터를 요청하였을 때 캐시를 잘 활용해보자. 그리고 데이터를 효율적으로 읽어와보자는 관점에서의 이야기였다. 그러면 반대로 CPU에서 연산한 것을 캐시에 써주고, 메모리에 써줄 때는 어떻게 해야할까? CPU에서 연산이 끝난다면 변경된 값을 캐시에 돌려줘야 할 것이고, 캐시에 있는 데이터도 변경된 값을 언젠가는 메인 메모리에 돌려줘야 할 것이다. 이번 포스팅에서는 CPU에서 연산한 값을 언제, 어떻게 메인 메모리에 쓸 것이냐는 관점의 'Write Policy'를 다룰 것이다. 우선, 언제 다음 계층에 변경된 데이터를 써줄 것이냐부터 알아보자. 이에 관한 정..

이전 포스팅에서는 메인 메모리와 캐시 메모리간의 매핑하는 방법을 배웠다. Direct-mapped Cache는 쉽고 간단하지만 Hit rate이 낮은 단점이 있었고, 이를 보완하기 위한 Fully Associative Cache는 아무런 규칙없이, 인덱스없이 아무데나 저장하는 방식이어서 원하는 데이터를 찾으려면 캐시 메모리 전체를 탐색해야 하기 때문에, 탐색 시간이 긴 단점이 있다. 그래서 이 둘의 단점을 보완할 수 있는, 둘의 장점을 절충한 방법인 Set Associative Cache는 어레이의 특정 행을 지정해서 그 행이 비어있으면, 행의 아무 열에 데이터를 저장하는 방식이다. 이는 Direct-mapped 방식보다 검색은 느리지만, 저장은 빠르며 Fully Associative 방식보다 저장은 느..

이전 포스팅에서 'Memory Hierarchy'를 배웠습니다. 계층도를 살펴보면 L1, L2 Cache 이런게 나오는데 'Cache Memory'는 뭘까요? Cache Memory : 속도가 느린 메인 메모리의 접근 시간을 향상시키기 위해 일시적으로 데이터를 갖고 있는 작지만 빠른 메모리를 이야기합니다. 캐시 메모리는 'Locality'를 활용하기 위한 구조를 갖고 있습니다. 그리고 낮은 계층의 메모리보다 크기가 작습니다. 즉, L1 Cache는 L2 Cache의 크기보다 작고, L2 Cache는 L3 Cache보다 크기가 작습니다. 그림에서 알 수 있듯이 L1 Cache는 크기가 매우 작으며 내부는 메모리의 텍스트 영역을 다루는 Instruction Cache와 이외의 영역을 다루는 Data Cach..

멀티코어 프로세서를 다루며 Memory Hierarchy Design은 우리에게 더 중요해졌습니다. 프로그램을 짜는 입장에서는 메모리 걱정없이 작업을 하는 게 가장 이상적일텐데, 그러려면 이상적인 메모리가 필요하겠죠. 그러면 어떤 메모리가 이상적인 메모리일까요? 이상적인 메모리는 다음과 같은 특징을 가진 메모리입니다. Ideal Memory - Zero access latency - Infinite bandwidth - Infinite capacity - Zero cost 하지만 이런 특징은 서로 상충합니다. - 메모리가 크면 읽거나 쓸 때 긴 시간이 걸릴 것이고 - 빠르고 큰 대역폭을 가진 메모리는 비쌉니다. (SRAM vs DRAM vs Disk vs Tape) SRAM은 리프레쉬가 필요없고 capa..

컴퓨터공학에서 성능의 향상은 는 크게 두가지 측면에서 이뤄졌다. 첫번째는 '반도체 스케일링', 두번째는 '컴퓨터 아키텍쳐의 발전'이다. 반도체 스케일링 : CMOS 트랜지스터의 피져 사이즈를 줄임으로써 이뤄졌다. 1) 작아진 트랜지스터의 사이즈는 더 많은 트랜지스터를 집약시킬 수 있게 했고 2) 빨라진 트랜지스터는 더 많은 성능(높은 클럭)을 가져다 줬고 3) 적은 에너지 소모는 저전력으로도 충분히 반도체를 사용 가능케 해주었다. 컴퓨터 아키텍쳐의 발전 : 컴퓨터 마켓에서 두가지 변화가 이를 가능케했다. 1) 발전된 컴파일러는 어셈블리 프로그래밍을 하지 않더라도 개발을 할 수 있게 해주었고 2) 표준화되고 벤더와 독립적인 운영체제는.. 컴퓨터 아키텍쳐의 발전은 꾸준히 이뤄졌으나 싱글 프로세서의 성능 향상..