유한 요소 연산자 평가
동기 및 문제 설명
유한 요소법은 주로 물리 시뮬레이션에 사용되는 이산화 기법입니다. 물리 문제가 정의되는 물리적 영역(보통 2D 또는 3D)은 요소라고 불리는 작고 기하학적으로 단순한 부분 영역들의 메시로 분할됩니다(컴퓨터 그래픽스에서 곡면을 삼각형들로 분할하는 것과 매우 비슷합니다). 물리량(예: 밀도, 압력, 온도)을 나타내는 연속장은 유한 개의 값을 사용해 근사되며, 이 값들은 요소의 꼭짓점(절점)에서의 장의 값을 나타냅니다. 이러한 이유로 이 값들은 보통 절점값이라고 부릅니다. 시뮬레이션할 물리 현상을 기술하는 편미분 방정식은 절점값을 미지수로 하는 선형 대수 방정식계로 표현됩니다. 이러한 대수 방정식계는 보통 상당히 크기 때문에 (슈퍼)컴퓨터를 사용해 풀어야 합니다.
이렇게 얻은 대수 방정식계는 보통 반복법(예: 켤레 기울기법)으로 풀기 때문에, 이를 기술하는 행렬을 메모리에 명시적으로 저장할 필요가 없습니다. 이 행렬이 벡터에 작용한 결과를 평가할 수 있기만 하면(행렬-벡터 곱을 계산할 수 있기만 하면) 충분합니다. 이러한 접근 방식을 보통 행렬 없는(matrix-free) 방식이라고 부릅니다.
이번 실습에서는 트러스를 다루는 구조 문제에 대해 앞서 언급한 행렬-벡터 곱을 평가하는 코드를 최적화해야 합니다. 트러스는 여러 개의 부재로 이루어지며, 각 부재는 하나의 유한 요소로 표현됩니다. 행렬 없는 연산자를 평가하기 위해, 모든 요소를 순회하면서 지역 4x4 행렬을 계산하고, 요소 4개짜리 지역 좌변 벡터를 수집(gather)하고, 곱셈을 수행한 다음, 그 결과를 전역 우변 벡터에 분산(scatter)합니다. 이 예제는 상당히 단순하지만(기계공학 2학년 강의 수준), 전 세계의 다양한 시뮬레이션 코드에서 흔히 볼 수 있는 gather-scatter 메모리 접근 패턴을 잘 보여 줍니다.
참고: 위의 유한 요소법 설명은 극도로 단순화한 것이며, 문제에 대한 개괄적인 개요를 제공하기 위한 것일 뿐입니다.
힌트
컴파일러가 부동소수점 연산에 대해서는 상당히 최적에 가까운 코드를
생성하므로, 이 부분을 최적화해서 얻을 수 있는 이득은 거의 없다는 점에
유의하십시오. 그 대신 메모리 접근 패턴에 집중하십시오. 이 패턴은 극도로
무작위적이어서 서로 멀리 떨어진 많은 메모리 주소에 빠르게 연속적으로
접근하게 되며, 이는 TLB에 부담을 줍니다. 이 상황은 무작위 방식으로
접근되는 메모리를 대용량 페이지에 할당함으로써 완화할 수 있습니다(HugePagesSetupTips 참고). 풀이의 편의를
위해, 이러한 할당은 모두 allocateDoublesArray 함수를 사용해
이루어집니다. 실제로 모범 풀이에서 수정되는 코드는 이 부분뿐입니다.
작성자: @kubagalecki
힌트
힌트 1:
운영 체제가 가상 메모리와 물리 메모리 사이를 어떻게 매핑하는지에 대해 알고 있는 지식을 바탕으로, 이번 실습에서 생성되는 배열의 메모리를 매핑하는 데 필요한 일반 페이지(예를 들어 Linux에서는 크기가 대략 ~4kB)의 수에 대해 무엇을 말할 수 있습니까? 이 수가 성능에 좋지 않을 수 있는 이유는 무엇입니까?
힌트 2:
메모리 주소를 캐시하여 극도로 빠른 조회(즉, CPU 사이클 몇 번)를 가능하게 하는 변환 색인 버퍼(Translation Lookaside Buffer, TLB)는 크기가 제한되어 있다는 점을 떠올려 보십시오. TLB에 가해지는 부담을 줄이기 위해 프로그램에서 대용량 페이지를 어떻게 활용할 수 있습니까?
힌트 3:
시스템에서 대용량 페이지 지원을 설정하고,
allocateDoublesArray에서 double 배열을 일반
메모리 페이지가 아닌 대용량 페이지에 생성하는 방법을 찾아 보십시오.
이론에 근거할 때 어떤 성능 향상을 기대할 수 있으며, 그 이유는
무엇입니까?
풀이:
배경:
이 실습에서는 원소가 수천만 개에 이르는 double 배열 여러 개를 처리합니다. 배열의 엄청난 크기와 원소에 대한 무작위 접근은 캐시 친화적인 알고리즘의 특성이 아니므로 본질적인 문제를 일으킵니다.
풀이 (Linux)
이 문제는 대용량 페이지를 사용하여 다소 완화할 수 있습니다. 대용량 페이지가 무엇이며 어떻게 동작하는지 설명하기에 앞서, 페이징과 가상 메모리에 대해 간단히 설명하겠습니다.
운영 체제(OS)가 프로세스(예: 우리 알고리즘의 프로그램)를 실행하면, OS는 프로세스와 머신의 물리 메모리 사이에 가상화 계층을 제공합니다. 이 가상화는 프로세스가 읽기와 쓰기에 사용할 수 있는 가상 주소를 프로세스에 제공하며, 프로세스가 모르는 사이에 OS는 이 가상 주소를 실제 물리 메모리 주소에 매핑합니다.
Linux를 비롯한 많은 OS 플랫폼은 페이지를 사용하여 가상 메모리와 물리 메모리 간의 매핑을 구현합니다. 페이지는 가상 메모리에서 물리 메모리로의 매핑을 항목으로 기술하는 테이블이라고 생각할 수 있습니다. 프로세스가 어떤 메모리 주소를 처음 조회하면, CPU는 이를 가져오기 위해 주 메모리(RAM)에 접근합니다. 이 조회는 매우 느리므로, 조회 결과는 하드웨어 칩의 캐시에 저장됩니다. 각 칩에는 메모리 관리 장치(MMU)에 연결된 캐시가 있으며, 이를 변환 색인 버퍼(Translation Lookaside Buffer, TLB)라고 합니다. TLB의 목적은 프로세스가 자주 가져오는 데이터를 매우 빠르게 조회할 수 있도록 하는 것입니다.
수백 메가바이트, 심지어 기가바이트 규모의 큰 메모리 공간을 매핑할 때는 가상 메모리를 물리 메모리에 매핑하는 데 필요한 페이지 수가 엄청나서 TLB에 부담을 줍니다. Linux의 표준 페이지 크기는 4 kB이므로, 이와 같은 알고리즘에서 배열이 사용하는 모든 메모리를 매핑하려면 수천 개(혹은 수백만 개)의 페이지가 필요합니다. 이는 TLB가 한 번에 보유할 수 있는 항목 수(보통 약 4,000개)를 초과합니다. 여기에 이 알고리즘이 데이터를 무작위 순서로 조회한다는 점까지 더해지면, 비용이 큰 TLB 캐시 미스가 매우 많이 발생할 가능성이 높습니다.
대용량 페이지(2MB)를 사용하면 페이지 하나(따라서 TLB 항목 하나)가 매핑하는 메모리 양을 512배로 대폭 늘릴 수 있습니다. 캐시가 훨씬 더 넓은 메모리 영역에 대한 매핑을 저장할 수 있게 되므로(각 페이지 항목이 4kB 페이지를 사용할 때보다 512배 큰 영역을 나타내므로) TLB 미스의 위험이 줄어듭니다. 이를 통해 성능이 향상될 것입니다.
원래 코드를 실행하면 다음과 같은 성능을 확인할 수 있습니다:
-------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-------------------------------------------------------------------------------------
Apply matrix-free operator 7.09 s 7.09 s 1 bytes_per_second=206.508Mi/s대용량 페이지(2MB)를 사용하도록 수정한 코드에서는 다음과 같습니다:
-------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-------------------------------------------------------------------------------------
Apply matrix-free operator 6.02 s 6.02 s 1 bytes_per_second=243.305Mi/s바이트 처리량이 약 20% 높아지고 전체 실행 시간이 약 1초 줄어드는 것을 확인할 수 있습니다.
아래는 Linux용 코드입니다. 이 코드는 mmap과
munmap을 사용하여 메모리를 할당하고 해제합니다.
allocateDoublesArray 함수는 배열을 할당하며, 이 배열은 각각
2MB 크기의 대용량 페이지로 뒷받침됩니다. 사용자 정의 삭제자와 함께
std::unique_ptr를 사용하므로, 프로그램에서 객체가 스코프를
벗어나는 즉시 할당된 메모리가 자동으로 정리됩니다.
#include <sys/mman.h>
inline auto allocateDoublesArray(size_t size) {
size_t total_array_size = size * sizeof(double);
constexpr size_t page_2mb = 1UL << 21;
auto pages_needed = total_array_size / page_2mb + (total_array_size % page_2mb != 0);
size_t total_to_alloc = pages_needed * page_2mb;
void* ptr = mmap(nullptr, total_to_alloc, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1 , 0);
if (ptr == MAP_FAILED) {
throw std::bad_alloc{};
}
madvise(ptr, total_to_alloc, MADV_HUGEPAGE);
auto deleter = [total_to_alloc](double *p) { munmap(p, total_to_alloc); };
return std::unique_ptr<double[], decltype(deleter)>(static_cast<double*>(ptr), std::move(deleter));
}