알고리즘 분석에서 우리는 작업과 단계를 계산합니다. 이것은 기본적으로 컴퓨터가 해당 작업에 필요한 데이터를 가져오는 데 걸리는 시간보다 작업을 수행하는 데 더 많은 시간이 소요될 때 정당화됩니다. 오늘날 작업 수행 비용은 메모리에서 데이터를 가져오는 비용보다 훨씬 낮습니다.
많은 알고리즘의 실행 시간은 작업 수보다는 메모리 참조 수(캐시 누락 수)에 의해 좌우됩니다. 따라서 일부 알고리즘을 설계하려고 할 때 작업 수뿐만 아니라 메모리 액세스 수를 줄이는 데 집중해야 합니다. 또한 메모리 지연을 숨기는 알고리즘을 설계하는 데 집중해야 합니다.
컴퓨터의 메모리가 L1 캐시, L2 캐시 및 주 메모리로 구성된 간단한 컴퓨터 모델이 있다고 가정합니다. 레지스터(R)에 있는 데이터에 대해 ALU를 사용하여 일부 산술 및 논리 연산을 수행합니다.
이것은 블록 다이어그램입니다 -
다이어그램에서 메모리와 캐시의 크기에 대한 정보도 얻을 수 있습니다. 주 메모리는 기본적으로 수백 또는 수천 MB입니다. 여기서 L2 캐시는 MB의 일부이고 L1 캐시는 일부 KB입니다. 레지스터 크기는 몇 비트입니다. 프로그램을 실행할 때 메모리의 모든 데이터. ADD와 같은 연산을 추가하면 첫 번째 숫자가 레지스터에 저장되고 레지스터의 데이터가 추가된 다음 결과가 메모리에 기록됩니다.
이미 레지스터에 있는 데이터를 추가해야 하는 시간의 길이를 한 사이클이라고 합니다. L1 캐시에서 레지스터로 데이터를 로드하는 데 필요한 시간은 이 모델에서 두 사이클이라고 가정합니다. 필요한 데이터가 L1 캐시에 없지만 L2 캐시에 있는 경우 L1 캐시 미스가 발생하고 필요한 데이터는 L2 캐시에서 L1 캐시 및 레지스터로 10주기 동안 가져옵니다. 필요한 데이터가 L2 캐시에도 없을 때 L2 캐시 미스가 발생하고 필요한 데이터는 100주기 동안 주 메모리에서 L2 캐시, L1 캐시 및 레지스터로 가져옵니다. 그러면 쓰기가 완료될 때까지 기다리지 않고 다음 작업을 진행하기 때문에 주기억장치에 데이터를 쓰는 경우에도 쓰기 작업을 1주기로 계산합니다.