알고리즘에 대한 캐시 및 적중률 코드 작성

Question

적중률은 발견 된 데이터의 캐시에 대한 비율입니다. 하지만 알고리즘에 대한 히트를 찾는 방법을 모르겠습니다. 나는 코드 1에 대해 각각 4 개의 엘리먼트로 11 개의 블록을 가질 것이고 코드 2에 대해서는 11 개의 엘리먼트로 4 개의 블록을 가질 것이며 매번 4 개의 엘리먼트를 놓친다는 것을 알게 될 것이라고 생각했다. 그것이 의미가 있는지 확실하지 않습니다. 어떤 조언은 각 메모리 블록 들고,도 10 개의 메모리 블록 완전 연관 단일 레벨 캐시 가정이 [0][0], [0][1], [0][2], [0][3], [1][0], [1][1], …[10][2], [10][3]

같은 메모리에 저장

4 열로 11 개 행이 2 차원 어레이 A를 가정 환영 4 바이트 및 FIFO 대체 정책이 있습니다.

각 행은 정확히 하나의 캐시 블록에 적합하지만 불행히도 전체 배열은 캐시에 맞지 않습니다. 캐시가 너무 작은 한 행입니다 ...

1- 어떻게 캐시 방문 시간이 5ns이고 메모리 액세스 시간이 70ns라고 가정하면 2를 계산합니까? 메모리 및 캐시에 대한 중복 액세스, 각 코드의 EAT는 어떻게 계산합니까?

코드 1 :

for (int row = 0; row < 11; row ++) 
{ 
    for (int column = 0; column < 4; column ++) 
    { 
     myByte = A [ row, column ]; 
    } 
} 

코드 2 : 어떤 도움에 감사드립니다

for (int column = 0; column < 4; column ++) 
    { 
    for (int row = 0; row < 11; row ++) 
    { 
     myByte = A [ row, column ]; 
    } 
} 

. 감사합니다

Answer 1

그럼 우리는 알고리즘에 대한 적중률을 계산하지 않습니다. 우리는 캐시의 개념을 활용하여 최대 히트 율을 얻는 알고리즘을 작성합니다. 귀하의 질문은 실제로 컴퓨터 조직 및 아키텍처에 속합니다.

어쨌든 2D 배열은 행 주요 순서로 메모리에 저장됩니다. 코드 1의 경우, 첫 번째 inner for 루프가있는 은 캐시에서 아무것도 발견되지 않았으므로 (메모리 액세스 시간 70ns) 아무 것도 발견되지 않았기 때문에 네 개의 요소가 포함 된 메모리에서 블록을 가져옵니다. 다음 세 요소 즉, [ 첫 번째 네 요소 = 70 + 3 * 5 = 85ns에 대한 총 시간 즉, 3 * 5 = 15ns)에서 가져올 수 있습니다.

위 프로세스는 10 개의 블록을 사용하여 배열의 10 개 행에 대해 반복됩니다. 하지만 FIFO를 사용하는 마지막 블록의 경우에는 블록의 개념 스왑이 발생하지만 시간은 동일하게 유지됩니다. 이렇게 총 시간 = 85 * 11 = 935ns 코드 2

, 블록들이 페치 될 내부 루프의 각 반복에 대한

. 따라서 메모리에 액세스 할 때마다 캐시 개념 즉 나쁜 코드 조각을 사용하지 않습니다. 코드 2는 배열이 메모리의 열 주요 순서로 저장되는 경우 가장 잘 작동합니다.