같은 형의 값을 나란히 기억하고, 인덱스(첨자)로 개별 요소를 지정하는 데이터 구조. 메모리상에 연속으로 놓이므로 인덱스로부터 위치를 계산하여 어느 요소든 일정한 시간에 읽고 쓸 수 있다. 인덱스가 0부터 시작하는 언어와 1부터 시작하는 작성법이 있다.
일본어 명칭: 配列
배열(Array)은(는) 프로그래밍의 기초(의사 코드 트레이스), 자료 구조와 알고리즘, GPU 프로그래밍 등 15개 분야의 연습 문제 73개에 나와요.
정답: A. 각 행의 끝에 패딩을 추가하여 행 크기를 2의 거듭제곱에서 어긋나게 한다
한 행이 정확히 4096바이트이면 열 방향으로 따라가는 요소의 주소는 모두 4096의 배수씩 떨어져 인덱스 중 하위 12비트에 포함되는 부분이 같아지고 극히 적은 수의 세트에 집중됩니다(1웨이가 4 KB 이하인 L1 캐시라면 모두 같은 세트입니다). 같은 세트에 연관도보다 많은 행이 모이면 용량에 여유가 있어도 서로 쫓아내는 충돌 미스가 일어납니다. 각 행에 1라인 분 정도의 패딩을 추가하면 요소마다 대응하는 세트가 어긋나 분산됩니다. 2의 거듭제곱 주소에 맞추어도 문제는 변하지 않으며, 같은 크기의 타입으로 바꿔도 효과가 없습니다.
1행에서 i를 2비트 왼쪽으로 시프트하여 4×i를 만들고, 2행에서 배열의 시작 주소에 더해 a[i]의 주소를 구하며, 3행에서 그 주소로부터 4바이트를 읽고 있습니다.
a0에 int형(4바이트) 배열 a의 시작 주소, a1에 첨자 i가 들어 있다. 위의 코드가 a2에 읽어 …C 언어의 2차원 배열은 행 우선(row-major)으로 저장되어 a[i][0], a[i][1]…이 메모리 상에서 이웃합니다.
C 언어의 2차원 배열 a[i][j]를 위와 같이 안쪽 루프를 j로 하여 순회하면, 안쪽을 i로 하는 것보…연관도를 높여 같은 세트에 둘 이상 둘 수 있게 하거나, 배열의 시작 위치를 어긋나게 하여 다른 세트에 대응시키면 줄일 수 있습니다.
다이렉트 매핑 방식 캐시에서 두 배열의 요소가 같은 캐시 위치에 대응하여, 번갈아 접근할 때마다 서로를 쫓…구조체의 배열(AoS)에서는 x, y, z, mass의 16바이트가 한 세트로 늘어서므로, x만 읽는 처리에서도 64바이트 라인의 4분의 3은 사용하지 않는 데이터가 됩니다.
위와 같이 x 좌표만 합산하는 처리를 배열의 구조체(각 성분을 별도의 배열로 만드는 형태)로 바꾸면 빨라지…배열이라면 다음 주소를 계산으로 알 수 있어 프리페치와 미스 겹치기가 작동합니다.
위 연결 리스트를 따라가는 처리가 같은 수의 요소를 가진 배열을 차례로 읽는 것보다 크게 느려지기 쉬운 이…변수(Variable) 포인터(Pointer) 캐시 라인(Cache Line) 연결 리스트(Linked List) GPU 스택(Stack) 프리페치(Prefetch) 구조체(struct) SIMD 시간 복잡도(Time Complexity)