이 게시물은 원래 Quansight Labs 블로그에 게시되었으며 Quansight의 허가를 받아 수정되어 여기에 다시 게시되었습니다.
웹 애플리케이션은 고성능 과학 계산 및 AI 지원 최종 사용자 경험을 위한 새로운 영역으로 빠르게 떠오르고 있습니다. ML/AI 혁명을 뒷받침하는 것은 선형 방정식과 벡터 공간 및 행렬을 통한 표현에 관한 수학의 한 분야인 선형 대수학입니다. LAPACK("Linear Algebra Package")은 수치 선형 대수학을 위한 기본 소프트웨어 라이브러리로, 강력하고 검증된 일반적인 행렬 연산 구현을 제공합니다. . LAPACK은 대부분의 수치 컴퓨팅 프로그래밍 언어 및 라이브러리의 기본 구성 요소임에도 불구하고 웹의 고유한 제약 조건에 맞춰진 포괄적이고 고품질의 LAPACK 구현이 아직 실현되지 않았습니다. 그게...지금까지는요.
올해 초 저는 Quansight의 공익 부문이자 Python 과학 생태계의 리더인 Quansight Labs에서 여름 인턴으로 일할 수 있는 행운을 누렸습니다. 인턴십 기간 동안 저는 C와 JavaScript로 작성되고 웹 브라우저와 Node.js 및 Deno와 같은 기타 웹 기본 환경에서 사용하도록 최적화된 과학 계산을 위한 기본 라이브러리인 stdlib에 초기 LAPACK 지원을 추가하는 작업을 했습니다. 이 블로그 게시물에서는 저의 여정, 예상 및 예상치 못한(!) 도전과제, 그리고 앞으로 나아갈 길에 대해 논의하겠습니다. 저는 이 작업이 약간의 행운과 함께 웹 브라우저를 수치 계산 및 기계 학습을 위한 최고 수준의 환경으로 만드는 데 중요한 구성 요소를 제공하고 더욱 강력한 AI 지원 웹 애플리케이션의 미래를 예고하는 것입니다.
재밌을 것 같나요? 가자!
LAPACK에 익숙한 이 블로그 독자들은 웹 기술의 거친 세계에 대해 잘 알지 못할 가능성이 높습니다. 수치 및 과학 계산 분야 출신이고 과학적인 Python 생태계에 익숙한 사람들이 stdlib를 생각하는 가장 쉬운 방법은 NumPy 및 SciPy를 기반으로 한 오픈 소스 과학 컴퓨팅 라이브러리입니다. 수학, 통계 및 선형 대수학을 위한 다차원 배열 데이터 구조 및 관련 루틴을 제공하지만 Python 대신 JavaScript를 기본 스크립팅 언어로 사용합니다. 따라서 stdlib는 웹 생태계와 해당 애플리케이션 개발 패러다임에 중점을 두고 있습니다. 이 초점에는 몇 가지 흥미로운 디자인 및 프로젝트 아키텍처 결정이 필요하며, 이는 수치 계산용으로 설계된 기존 라이브러리와 비교할 때 stdlib를 더욱 독특하게 만듭니다.
NumPy를 예로 들면, NumPy는 OpenBLAS와 같은 선택적 타사 종속성을 제외한 모든 구성 요소가 분할할 수 없는 단일 단위를 형성하는 단일 모놀리식 라이브러리입니다. NumPy를 모두 설치하지 않고 단순히 배열 조작을 위해 NumPy 루틴을 설치할 수는 없습니다. NumPy의 ndarray 객체와 몇 가지 조작 루틴만 필요한 애플리케이션을 배포하는 경우 모든 NumPy를 설치하고 번들링한다는 것은 상당한 양의 "데드 코드"를 포함한다는 것을 의미합니다. 웹 개발 용어로 NumPy는 "트리 쉐이크 가능"이 아니라고 말합니다. 일반적인 NumPy 설치의 경우 이는 최소 30MB의 디스크 공간을 의미하며, 모든 디버그 문을 제외하는 사용자 정의 빌드의 경우 최소 15MB의 디스크 공간을 의미합니다. SciPy의 경우 해당 숫자는 각각 130MB와 50MB로 늘어날 수 있습니다. 말할 필요도 없이, 단지 몇 가지 기능을 위해 웹 애플리케이션에 15MB 라이브러리를 제공하는 것은 시작이 아닙니다. 특히 네트워크 연결이 좋지 않거나 메모리 제약이 있는 장치에 웹 애플리케이션을 배포해야 하는 개발자에게는 더욱 그렇습니다.
웹 애플리케이션 개발의 고유한 제약을 고려하여 stdlib는 상향식 설계 방식을 취합니다. 여기서 모든 기능 단위는 코드베이스의 관련되지 않고 사용되지 않는 부분과 독립적으로 설치되고 사용될 수 있습니다. 분해 가능한 소프트웨어 아키텍처와 근본적인 모듈성을 수용함으로써 stdlib는 사용자에게 원하는 API 세트와 명시적 종속성을 넘어서는 초과 코드가 거의 또는 전혀 없이 필요한 것을 정확하게 설치하고 사용할 수 있는 기능을 제공하므로 더 작은 메모리 공간, 번들을 보장합니다. 크기와 배포 속도가 더욱 빨라졌습니다.
예를 들어 두 개의 행렬 스택(즉, 3차원 큐브의 2차원 슬라이스)으로 작업하고 있고 다른 모든 슬라이스를 선택하고 일반적인 BLAS 연산 y = a * x를 수행한다고 가정합니다. 여기서 x와 y는 ndarray이고 a는 스칼라 상수입니다. NumPy로 이 작업을 수행하려면 먼저 NumPy를 모두 설치해야 합니다
pip install numpy
그런 다음 다양한 작업을 수행합니다
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
stdlib를 사용하면 프로젝트를 모놀리식 라이브러리로 설치할 수 있을 뿐만 아니라 다양한 기능 단위를 별도의 패키지로 설치할 수 있습니다.
npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
그런 다음 다양한 작업을 수행합니다
// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';
// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;
// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
중요한 점은 stdlib의 4,000개 이상의 패키지 중 하나를 독립적으로 설치할 수 있을 뿐만 아니라 관련 GitHub 저장소를 포크하여 해당 패키지 중 하나를 수정, 개선 및 리믹스할 수도 있다는 것입니다(예: @stdlib/ndarray-fancy 참조). ). 추상화 및 종속성 트리의 명시적 계층을 정의함으로써 stdlib는 애플리케이션에 적합한 추상화 계층을 자유롭게 선택할 수 있도록 해줍니다. 어떤 면에서는 이는 단순하고 기존 과학 소프트웨어 라이브러리 설계에 익숙하다면 비정통적인 아이디어일 수도 있지만 웹 플랫폼과 긴밀하게 통합되면 강력한 결과를 가져오고 흥미롭고 새로운 가능성을 만들어냅니다!
좋아요, 아마도 관심이 높아졌을 것입니다. stdlib는 흥미로운 것 같습니다. 그런데 이것이 웹 브라우저의 LAPACK과 무슨 관련이 있습니까? 지난 여름 우리의 목표 중 하나는 LAPACK을 웹에 도입할 때 stdlib 정신(한 가지 일과 한 가지 일을 잘 수행하는 작고 좁은 범위의 패키지)을 적용하는 것이었습니다.
하지만 잠깐만요! 그것은 극단적인 일이다. LAPACK은 약 1,700개의 루틴으로 방대하며, 합리적인 시간 내에 그 중 10%라도 구현하는 것은 중요한 과제입니다. LAPACK을 C, Go, Rust 등 웹 배포가 가능한 프로그래밍 언어의 이식성 있는 컴파일 타겟인 WebAssembly로 컴파일하고 그냥 끝내는 것이 낫지 않을까요?
안타깝게도 이 접근 방식에는 몇 가지 문제가 있습니다.
마지막 요점을 설명하기 위해 y = a*x y 연산을 수행하는 BLAS 루틴 daxpy로 돌아가 보겠습니다. 여기서 x와 y는 스트라이드 벡터이고 스칼라 상수입니다. C로 구현된 경우 기본 구현은 다음 코드 조각과 유사할 수 있습니다.
pip install numpy
WebAssembly로 컴파일하고 WebAssembly 바이너리를 웹 애플리케이션에 로드한 후 JavaScript에서 c_daxpy 루틴을 호출하려면 먼저 일련의 단계를 수행해야 합니다. 먼저, 새로운 WebAssembly 모듈을 인스턴스화해야 합니다.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
다음으로 모듈 메모리를 정의하고 새로운 WebAssembly 모듈 인스턴스를 생성해야 합니다.
npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
모듈 인스턴스를 생성한 후 이제 내보낸 BLAS 루틴을 호출할 수 있습니다. 그러나 데이터가 모듈 메모리 외부에 정의된 경우 먼저 해당 데이터를 메모리 인스턴스에 복사해야 하며 항상 리틀 엔디안 바이트 순서로 복사해야 합니다.
// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';
// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;
// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
이제 데이터가 모듈 메모리에 기록되었으므로 c_daxpy 루틴을 호출할 수 있습니다.
void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
int ix;
int iy;
int i;
if (N <= 0) {
return;
}
if (alpha == 0.0) {
return;
}
if (strideX < 0) {
ix = (1-N) * strideX;
} else {
ix = 0;
}
if (strideY < 0) {
iy = (1-N) * strideY;
} else {
iy = 0;
}
for (i = 0; i < N; i++) {
Y[iy] += alpha * X[ix];
ix += strideX;
iy += strideY;
}
return;
}
그리고 마지막으로 시각화 또는 추가 분석을 위해 D3와 같은 WebAssembly 메모리 "포인터"(즉, 바이트 오프셋)를 지원하지 않는 다운스트림 라이브러리에 결과를 전달해야 하는 경우 모듈에서 데이터를 복사해야 합니다. 메모리를 원래 출력 배열로 되돌립니다.
const binary = new UintArray([...]); const mod = new WebAssembly.Module(binary);
y = a*x y를 계산하는 것만으로도 많은 작업이 수행됩니다. 반면에 다음 코드 조각처럼 보일 수 있는 일반 JavaScript 구현과 비교해 보세요.
// Initialize 10 pages of memory and allow growth to 100 pages:
const mem = new WebAssembly.Memory({
'initial': 10, // 640KiB, where each page is 64KiB
'maximum': 100 // 6.4MiB
});
// Create a new module instance:
const instance = new WebAssembly.Instance(mod, {
'env': {
'memory': mem
}
});
JavaScript 구현을 사용하면 위의 WebAssembly 예시에서 요구되는 데이터 이동 없이 외부에서 정의된 데이터로 daxpy를 직접 호출할 수 있습니다.
// External data:
const xdata = new Float64Array([...]);
const ydata = new Float64Array([...]);
// Specify a vector length:
const N = 5;
// Specify vector strides (in units of elements):
const strideX = 2;
const strideY = 4;
// Define pointers (i.e., byte offsets) for storing two vectors:
const xptr = 0;
const yptr = N * 8; // 8 bytes per double
// Create a DataView over module memory:
const view = new DataView(mem.buffer);
// Resolve the first indexed elements in both `xdata` and `ydata`:
let offsetX = 0;
if (strideX < 0) {
offsetX = (1-N) * strideX;
}
let offsetY = 0;
if (strideY < 0) {
offsetY = (1-N) * strideY;
}
// Write data to the memory instance:
for (let i = 0; i < N; i++) {
view.setFloat64(xptr+(i*8), xdata[offsetX+(i*strideX)], true);
view.setFloat64(yptr+(i*8), ydata[offsetY+(i*strideY)], true);
}
적어도 이 경우에는 WebAssembly 접근 방식이 덜 인체공학적일 뿐만 아니라, 필요한 데이터 이동을 고려할 때 예상할 수 있듯이 다음 그림에서 볼 수 있듯이 부정적인 성능 영향도 있습니다.
그림 1: 배열 길이(x축)를 늘리기 위한 BLAS 루틴 daxpy에 대한 stdlib의 C, JavaScript 및 WebAssembly(Wasm) 구현의 성능 비교. Wasm(복사) 벤치마크에서는 입/출력 데이터가 Wasm 메모리로 복사되고 이로 인해 성능이 저하됩니다.
위 그림에서는 x축을 따라 열거된 대로 배열 길이를 늘리기 위한 BLAS 루틴 daxpy에 대한 stdlib의 C, JavaScript 및 WebAssembly(Wasm) 구현의 성능 비교를 표시합니다. y축은 기준 C 구현을 기준으로 정규화된 비율을 보여줍니다. Wasm 벤치마크에서는 입력 및 출력 데이터가 WebAssembly 모듈 메모리에 직접 할당 및 조작되며, Wasm(복사) 벤치마크에서는 위에서 설명한 대로 입력 및 출력 데이터가 WebAssembly 모듈 메모리로 복사되거나 WebAssembly 모듈 메모리에서 복사됩니다. 차트에서 다음을 관찰할 수 있습니다.
전반적으로 WebAssembly는 성능 향상을 제공할 수 있습니다. 그러나 이 기술은 만병통치약이 아니므로 원하는 이익을 실현하려면 신중하게 사용해야 합니다. 그리고 뛰어난 성능을 제공하는 경우에도 이러한 이점은 복잡성 증가, 잠재적으로 더 큰 번들 크기 및 더 복잡한 도구 체인으로 인한 비용과 균형을 이루어야 합니다. 많은 애플리케이션의 경우 일반 JavaScript 구현만으로도 문제가 없습니다.
이제 LAPACK 전체를 WebAssembly로 컴파일하고 하루라고 부르는 것에 대해 소송을 제기했는데, 그러면 우리는 어떻게 될까요? 글쎄, 우리가 stdlib 정신을 받아들이려면 근본적인 모듈화가 필요합니다.
급진적인 모듈화를 수용하려면 상황에 가장 적합한 것이 최선이라는 점을 인식해야 하며, 사용자 애플리케이션의 요구 사항과 제약 조건에 따라 개발자는 올바른 추상화를 선택할 수 있는 유연성이 필요합니다. 개발자가 Node.js 애플리케이션을 작성하는 경우 이는 뛰어난 성능을 달성하기 위해 OpenBLAS, Intel MKL 또는 Apple Accelerate와 같은 하드웨어 최적화 라이브러리에 바인딩하는 것을 의미할 수 있습니다. 개발자가 작은 숫자 루틴 세트가 필요한 웹 애플리케이션을 배포하는 경우 JavaScript가 해당 작업에 적합한 도구일 가능성이 높습니다. 그리고 개발자가 리소스 집약적인 대규모 WebAssembly 애플리케이션(예: 이미지 편집 또는 게임 엔진)을 작업하는 경우 개별 루틴을 더 큰 애플리케이션의 일부로 쉽게 컴파일할 수 있는 것이 가장 중요합니다. 간단히 말해서, 우리는 획기적인 모듈식 LAPACK을 원합니다.
제 임무는 이러한 노력을 위한 기반을 마련하고 문제점을 해결하고 공백을 찾아내며 웹에서 고성능 선형 대수학에 한 걸음 더 다가가는 것이었습니다. 그러나 급진적인 모듈화는 어떤 모습일까요? 모든 것은 기능의 기본 단위인 패키지에서 시작됩니다.
stdlib의 모든 패키지는 공동 지역화된 테스트, 벤치마크, 예제, 문서, 빌드 파일 및 관련 메타 데이터(종속성 열거 포함)를 포함하고 외부 세계와의 명확한 API 표면을 정의하는 자체 독립형 패키지입니다. . stdlib에 LAPACK 지원을 추가하려면 다음 구조를 사용하여 각 LAPACK 루틴에 대해 별도의 독립형 패키지를 생성해야 합니다.
pip install numpy
간단히
stdlib의 까다로운 문서화 및 테스트 요구 사항을 고려할 때 각 루틴에 대한 지원을 추가하는 것은 상당한 작업량이지만 최종 결과는 강력하고 고품질이며 가장 중요하게는 과학적 계산의 기초 역할을 하는 데 적합한 모듈식 코드입니다. 현대 웹에서. 하지만 예선이면 충분해요! 본론으로 들어가자!
stdlib에 BLAS 지원을 추가한 이전 노력을 바탕으로 우리는 LAPACK 지원을 추가할 때 먼저 JavaScript 구현과 관련 테스트 및 문서의 우선순위를 정한 다음 테스트 및 문서가 제공되면 유사한 다단계 접근 방식을 따르기로 결정했습니다. , C 및 Fortran 구현과 하드웨어 최적화 라이브러리에 대한 관련 네이티브 바인딩을 다시 채웁니다. 이 접근 방식을 통해 우리는 몇 가지 초기 사항을 검토할 수 있습니다. 즉, 사용자에게 신속하게 API를 제공하고, 강력한 테스트 절차 및 벤치마크를 설정하고, 빌드 도구 체인 및 성능의 잡초에 뛰어들기 전에 도구 및 자동화를 위한 잠재적인 방법을 조사할 수 있습니다. 최적화. 하지만 어디서부터 시작해야 할까요?
어떤 LAPACK 루틴을 먼저 대상으로 할지 결정하기 위해 LAPACK의 Fortran 소스 코드를 구문 분석하여 호출 그래프를 생성했습니다. 이를 통해 각 LAPACK 루틴에 대한 종속성 트리를 추론할 수 있었습니다. 그런 다음 그래프를 손에 들고 토폴로지 정렬을 수행하여 종속성이 없고 필연적으로 다른 루틴의 구성 요소가 되는 루틴을 식별하는 데 도움을 주었습니다. 특정 상위 수준 루틴을 선택하고 거꾸로 작업하는 깊이 우선 접근 방식을 사용하면 특정 기능을 얻을 수 있지만, 이러한 접근 방식을 사용하면 복잡성이 증가하는 루틴을 구현하려고 할 때 어려움을 겪게 될 수 있습니다. 그래프의 "잎"에 초점을 맞춰 일반적으로 사용되는 루틴(예: 도가 높은 루틴)의 우선순위를 지정할 수 있었고 나중에 여러 상위 수준 루틴을 제공할 수 있는 기능을 잠금 해제하여 영향력을 극대화할 수 있었습니다. 나의 노력이나 다른 기여자의 노력.
나는 계획을 세우고 일을 시작하게 되어 신났습니다. 첫 번째 루틴에서는 제공된 피벗 인덱스 목록에 따라 일반 직사각형 행렬에서 일련의 행 교환을 수행하고 LAPACK의 LU 분해 루틴을 위한 핵심 구성 요소인 dlaswp를 선택했습니다. 그리고 그때부터 나의 도전은 시작되었다...
Quansight Labs 인턴십 이전에 저는 LLVM을 기반으로 구축된 최신 대화형 Fortran 컴파일러인 LFortran의 정규 기고자였으며(그리고 지금도 그렇습니다!) 제 Fortran 기술에 상당한 자신감을 갖고 있었습니다. 그러나 나의 첫 번째 과제 중 하나는 현재 "레거시" Fortran 코드로 간주되는 코드를 이해하는 것이었습니다. 아래에서 세 가지 초기 장애물을 강조하겠습니다.
LAPACK은 원래 FORTRAN 77(F77)로 작성되었습니다. 버전 3.2(2008)에서 라이브러리가 Fortran 90으로 이동되었지만 레거시 규칙은 참조 구현에서 여전히 유지됩니다. 이러한 규칙 중 가장 눈에 띄는 것 중 하나는 서식 지정입니다.
F77 프로그램을 작성하는 개발자는 펀치 카드에서 상속받은 고정 형식 레이아웃을 사용하여 작업했습니다. 이 레이아웃에는 문자 열 사용에 관한 엄격한 요구 사항이 있습니다.
Fortran 90에서는 열과 줄 길이 제한을 제거하고 정착한 자유 형식 레이아웃을 도입했습니다! 주석 문자로. 다음 코드 조각은 LAPACK 루틴 dlacpy에 대한 참조 구현을 보여줍니다.
pip install numpy
다음 코드 조각은 동일한 루틴을 보여주지만 Fortran 90에 도입된 자유 형식 레이아웃을 사용하여 구현되었습니다.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
알 수 있듯이 열 제한을 제거하고 지정자를 모두 대문자로 작성하는 F77 규칙에서 벗어나 현대 Fortran 코드는 시각적으로 더 일관되고 가독성이 더 좋습니다.
LAPACK 루틴의 또 다른 일반적인 관행은 레이블이 지정된 제어 구조를 사용하는 것입니다. 예를 들어, 라벨 10이 해당 CONTINUE와 일치해야 하는 다음 코드 조각을 생각해 보세요.
npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Fortran 90에서는 end do를 사용하여 do 루프를 종료할 수 있도록 하여 이러한 관행의 필요성을 없애고 코드 가독성을 향상시켰습니다. 이 변경 사항은 위에 제공된 dlacpy의 자유 형식 버전에 표시됩니다.
다양한 크기의 배열을 유연하게 처리할 수 있도록 LAPACK 루틴은 일반적으로 가정된 크기의 배열에서 작동합니다. 위의 dlacpy 루틴에서 입력 행렬 A는 A(LDA, *) 표현식에 따라 가정된 크기를 갖는 2차원 배열로 선언됩니다. 이 표현식은 A에 LDA 수의 행이 있음을 선언하고 *를 자리 표시자로 사용하여 두 번째 차원의 크기가 호출 프로그램에 의해 결정됨을 나타냅니다.
가정 크기 배열을 사용하면 컴파일러가 지정되지 않은 차원에 대해 경계 검사를 수행할 수 없게 됩니다. 따라서 현재의 모범 사례는 범위를 벗어난 메모리 액세스를 방지하기 위해 명시적 인터페이스와 가정된 형태의 배열(예: A(LDA,:))을 사용하는 것입니다. 즉, 부분 행렬을 다른 함수에 전달해야 할 때 가정된 형태의 배열을 사용하면 문제가 될 수 있습니다. 그렇게 하려면 슬라이싱이 필요하고 이로 인해 컴파일러가 배열 데이터의 내부 복사본을 생성하는 경우가 많기 때문입니다.
물론 LAPACK 관습에 적응하고 LAPACK 사고방식을 채택하는 데 시간이 좀 걸렸습니다. 그러나 순수주의자이기 때문에 어쨌든 루틴을 포팅하려면 최소한 코드 가독성과 향후 유지 관리를 개선하기 위해 포팅한 루틴을 보다 현대적인 시대로 가져오고 싶었습니다. 그래서 stdlib 관리자와 논의한 후 루틴을 Fortran 95로 마이그레이션하기로 결정했습니다. Fortran 95는 최신 및 최고의 Fortran 버전은 아니지만 원래 구현의 모양과 느낌을 유지하는 것 사이에서 적절한 균형을 유지하는 것처럼 보였습니다. 충분함) 이전 버전과의 호환성 및 최신 구문 기능을 활용합니다.
LAPACK 지원을 추가하기 위한 상향식 접근 방식을 추구할 때의 문제 중 하나는 하위 수준 유틸리티 루틴에 대한 명시적 단위 테스트가 LAPACK에 존재하지 않는 경우가 많다는 것입니다. LAPACK의 테스트 스위트는 상위 레벨 루틴 테스트를 통해 종속 하위 레벨 루틴이 전체 워크플로우의 일부로 올바르게 작동하는지 확인하는 계층적 테스트 철학을 주로 사용합니다. 모든 루틴에 대한 테스트를 추가하면 잠재적으로 LAPACK 테스트 프레임워크의 유지 관리 부담과 복잡성이 증가할 수 있기 때문에 하위 수준 루틴에 대한 단위 테스트보다 통합 테스트에 초점을 맞추는 것이 합리적이라고 주장할 수 있지만 이는 이전의 루틴에 쉽게 의존할 수 없음을 의미합니다. 단위 테스트를 위한 기술이 필요하며 자체적으로 각 하위 수준 루틴에 대한 포괄적인 독립형 단위 테스트를 마련해야 합니다.
테스트 범위와 비슷한 맥락에서 LAPACK 외부에서는 하위 수준 루틴의 사용을 보여주는 실제 문서화된 예를 찾는 것이 어려웠습니다. LAPACK 루틴 앞에는 입력 인수 및 가능한 반환 값에 대한 설명을 제공하는 문서 주석이 일관되게 앞에 있지만, 코드 예제가 없으면 특히 특수 행렬을 처리할 때 예상되는 입력 및 출력 값을 시각화하고 파악하는 것이 어려울 수 있습니다. 그리고 단위 테스트가 없거나 문서화된 예제가 없다고 해서 세상이 끝나는 것은 아니지만, 이는 stdlib에 LAPACK 지원을 추가하는 것이 예상했던 것보다 더 힘든 일이 될 것임을 의미했습니다. 벤치마크, 테스트, 예제 및 문서를 작성하려면 더 많은 시간과 노력이 필요하므로 인턴십 중에 구현할 수 있는 루틴 수가 제한될 수 있습니다.
선형 메모리에 행렬 요소를 저장할 때 열을 연속적으로 저장하거나 행을 연속적으로 저장하는 두 가지 선택이 있습니다(그림 2 참조). 전자의 메모리 레이아웃을 column-major 순서라고 하고, 후자를 row-major 순서
라고 합니다.
그림 2: (a) 열 주요(Fortran 스타일) 또는 (b) 행 주요(C 스타일) 순서로 선형 메모리에 행렬 요소를 저장하는 것을 보여주는 도식입니다. 어떤 레이아웃을 사용할지는 주로 관례에 따라 선택됩니다.
어떤 레이아웃을 사용할지는 주로 관례에 따라 선택됩니다. 예를 들어 Fortran은 요소를 열 주요 순서로 저장하고 C는 요소를 행 주요 순서로 저장합니다. NumPy 및 stdlib와 같은 상위 수준 라이브러리는 열 및 행 주요 순서를 모두 지원하므로 배열 생성 중에 다차원 배열의 레이아웃을 구성할 수 있습니다.
pip install numpy
두 메모리 레이아웃 모두 본질적으로 다른 것보다 나은 것은 아니지만 기본 스토리지 모델의 규칙에 따라 순차적 액세스를 보장하도록 데이터를 배열하는 것은 최적의 성능을 보장하는 데 중요합니다. 최신 CPU는 비순차 데이터보다 순차 데이터를 더 효율적으로 처리할 수 있는데, 이는 주로 CPU 캐싱으로 인해 참조의 공간적 지역성을 활용합니다.
순차 및 비순차 요소 액세스가 성능에 미치는 영향을 보여주기 위해 MxN 행렬 A의 모든 요소를 다른 MxN 행렬 B로 복사하고 행렬 요소가 주요 열에 저장되어 있다고 가정하는 다음 함수를 고려하세요. 주문하세요.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
A와 B를 다음과 같은 3x2 행렬로 둡니다.
A와 B가 모두 열 우선 순서로 저장되면 다음과 같이 복사 루틴을 호출할 수 있습니다.
pip install numpy
그러나 A와 B가 모두 행 우선 순서로 저장된 경우 호출 서명은
으로 변경됩니다.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
후자의 시나리오에서는 da0이 2이고 da1이 -5이고 db0과 db1도 유사하므로 가장 안쪽 루프 내에서 순차적인 순서로 요소에 액세스하지 못합니다. 대신 배열 인덱스 "포인터"는 선형 메모리의 이전 요소로 돌아가기 전에 반복적으로 건너뜁니다. ia = {0, 2, 4, 1, 3, 5} 및 ib는 동일합니다. 그림 3에서는 비순차적 액세스가 성능에 미치는 영향을 보여줍니다.
그림 3: copy가 열 주요 순서에 따라 순차 요소 액세스를 가정할 때 복사에 정사각형 열 주요 행렬과 행 주요 행렬을 제공할 때의 성능 비교. x축은 증가하는 행렬 크기(즉, 요소 수)를 열거합니다. 모든 비율은 해당 행렬 크기에 대한 열 주요 결과를 기준으로 정규화됩니다.
그림에서 1e5개 이상의 요소(M = N = ~316)를 갖는 정사각 행렬에서 작업을 수행할 때까지 열 및 행 주요 성능이 거의 동일하다는 것을 알 수 있습니다. 1e6개 요소(M = N = ~1000)의 경우 복사할 행 주요 행렬을 제공하면 성능이 25% 이상 감소합니다. 1e7 요소(M = N = ~3160)의 경우 85% 이상의 성능 저하가 관찰됩니다. 행 크기가 큰 행 주요 행렬에서 작업할 때 참조 지역성이 감소하면 성능에 상당한 영향을 미칠 수 있습니다.
Fortran으로 작성되었기 때문에 LAPACK은 열 주요 액세스 순서를 가정하고 이에 따라 알고리즘을 구현합니다. 이는 행 우선 순서를 지원할 뿐만 아니라 이를 기본 메모리 레이아웃으로 만드는 stdlib와 같은 라이브러리에 문제를 나타냅니다. 단순히 LAPACK의 Fortran 구현을 JavaScript로 포팅한다면 행 주요 행렬을 제공하는 사용자는 비순차적 액세스로 인해 성능에 부정적인 영향을 받게 됩니다.
성능에 대한 부정적인 영향을 완화하기 위해 우리는 BLAS 루틴의 행 및 열 주요 메모리 레이아웃을 모두 지원하는 BLAS와 유사한 라이브러리인 BLIS에서 아이디어를 빌려 포트란에서 JavaScript로 루틴을 포팅할 때 수정된 LAPACK 구현을 만들기로 결정했습니다. 각 차원에 대한 별도의 보폭 매개변수를 통해 열 및 행 주요 메모리 레이아웃을 모두 명시적으로 수용하는 C입니다. 위에 정의된 복사 함수와 유사한 dlacpy와 같은 일부 구현의 경우 별도의 독립적인 스트라이드를 통합하는 것이 간단하며 종종 스트라이드 트릭과 루프 교환이 포함되지만 다른 경우에는 수정이 훨씬 덜 간단합니다. 전문화된 행렬 처리, 다양한 액세스 패턴 및 조합 매개변수화.
LAPACK 루틴은 주로 선형 메모리에 저장된 행렬에서 작동하며 해당 요소는 지정된 차원과 선행(즉, 첫 번째) 차원의 스트라이드에 따라 액세스됩니다. 차원은 각 행과 열의 요소 수를 각각 지정합니다. 스트라이드는 행의 다음 요소에 액세스하기 위해 건너뛰어야 하는 선형 메모리의 요소 수를 지정합니다. LAPACK은 동일한 열에 속하는 요소가 항상 연속적(즉, 선형 메모리에서 인접함)이라고 가정합니다. 그림 4는 LAPACK 규칙(구체적으로 회로도 (a) 및 (b))을 시각적으로 표현한 것입니다.
그림 4: 비연속 스트라이드 배열에 대한 LAPACK 스트라이드 배열 규칙의 일반화를 보여주는 회로도. a) 열 주요 순서로 저장된 5x5 연속 행렬. b) 열 주요 순서로 저장된 3x3 비연속 하위 행렬. 하위 행렬은 첫 번째 인덱스 요소에 대한 포인터를 제공하고 선행(즉, 첫 번째) 차원의 스트라이드를 지정하여 LAPACK에서 작동할 수 있습니다. 이 경우 더 큰 행렬의 일부로 저장될 때 선형 메모리의 하위 행렬 요소가 연속되지 않기 때문에 열당 요소가 3개만 있어도 선행 차원의 스트라이드는 5입니다. LAPACK에서는 후행(즉, 두 번째) 차원의 스트라이드가 항상 1로 가정됩니다. c) 단위가 아닌 스트라이드를 갖고 LAPACK 스트라이드 규칙을 선행 및 후행 차원 모두에 일반화하는 열 주요 순서로 저장된 3x3 비연속 하위 행렬. 이러한 일반화는 stdlib의 다차원 배열("ndarrays"라고도 함)을 뒷받침합니다.
NumPy 및 stdlib와 같은 라이브러리는 LAPACK의 스트라이드 배열 규칙을 일반화하여 지원합니다
마지막 차원에서 단위가 아닌 스트라이드를 지원하면 명시적인 데이터 이동 없이 선형 메모리의 비연속 보기 O(1) 생성이 지원됩니다. 이러한 뷰를 종종 "슬라이스"라고 합니다. 예를 들어, stdlib에서 제공하는 API를 사용하여 이러한 뷰를 생성하는 다음 코드 조각을 고려해 보세요.
pip install numpy
마지막 차원에서 단위가 아닌 보폭을 지원하지 않으면 x['::2,::2'] 표현식에서 뷰를 반환하는 것이 불가능합니다. 선택한 요소를 새 선형에 복사해야 하기 때문입니다. 연속성을 보장하기 위해 메모리 버퍼를 사용합니다.
그림 5: 보폭 조작을 사용하여 선형 메모리에 저장된 행렬 요소의 뒤집힌 보기와 회전된 보기를 만드는 방법을 보여주는 회로도. 모든 하위 도식의 경우 보폭은 [trailing_dimension,leading_dimension]으로 나열됩니다. 각 회로도에 내재된 "오프셋"은 행렬 A의 경우 Aij 요소와 같이 첫 번째 인덱스 요소의 인덱스를 나타내는 "오프셋"입니다. i⋅strides[1] j⋅strides[0] 오프셋에 따라 해석됩니다. a) 열 주요 순서로 저장된 3x3 행렬이 주어지면 선행 및 후행 차원의 스트라이드를 조작하여 하나 이상의 축을 따라 행렬 요소가 역순으로 액세스되는 뷰를 생성할 수 있습니다. b) 유사한 보폭 조작을 사용하여 선형 메모리 내의 배열을 기준으로 행렬 요소의 회전된 보기를 생성할 수 있습니다.
음수 스트라이드 지원을 통해 하나 이상의 차원을 따라 요소를 O(1) 반전 및 회전할 수 있습니다(그림 5 참조). 예를 들어, 행렬을 위에서 아래로, 왼쪽에서 오른쪽으로 뒤집으려면 보폭만 무효화하면 됩니다. 이전 코드 조각을 기반으로 다음 코드 조각은 하나 이상의 축에 대한 반전 요소를 보여줍니다.
pip install numpy
음수 스트라이드에 대한 논의에는 선형 메모리에서 첫 번째 인덱스 요소의 인덱스를 나타내는 "오프셋" 매개변수가 필요하다는 암시가 있습니다. 스트라이드 다차원 배열 A 및 스트라이드 목록 s의 경우 요소 Aij⋅⋅⋅n에 해당하는 인덱스 방정식에 따라 풀 수 있습니다
여기서 N은 배열 차원의 수이고 sk는 k번째 스트라이드에 해당합니다.
음수 스트라이드를 지원하는 BLAS 및 LAPACK 루틴(스트라이드 벡터에서 작동할 때만 지원되는 기능(예: 위의 daxpy 참조))에서 인덱스 오프셋은 다음 코드 조각과 유사한 논리를 사용하여 계산됩니다.
pip install numpy
여기서 M은 벡터 요소의 수입니다. 이는 제공된 데이터 포인터가 벡터에 대한 선형 메모리의 시작을 가리키는 것으로 암시적으로 가정합니다. C와 같은 포인터를 지원하는 언어에서는 선형 메모리의 다른 영역에서 작동하기 위해 일반적으로 함수 호출 전에 포인터 산술을 사용하여 포인터를 조정합니다. 이는 적어도 1차원 경우 상대적으로 저렴하고 간단합니다.
예를 들어 위에서 정의한 대로 c_daxpy로 돌아가면 포인터 산술을 사용하여 입력 및 출력 배열의 11번째 및 16번째 요소(참고: 0 기반 인덱싱)에서 시작하는 선형 메모리 내의 5개 요소에 대한 요소 액세스를 제한할 수 있습니다. 다음 코드 조각에 표시된 대로 각각
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
그러나 바이너리 버퍼에 대한 명시적인 포인터 연산을 지원하지 않는 JavaScript에서는 원하는 바이트 오프셋을 가진 새로운 형식의 배열 객체를 명시적으로 인스턴스화해야 합니다. 다음 코드 조각에서 위의 C 예제와 동일한 결과를 얻으려면 형식화된 배열 생성자를 확인하고, 새 바이트 오프셋을 계산하고, 새 형식화된 배열 길이를 계산하고, 새 형식화된 배열 인스턴스를 생성해야 합니다.
npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
큰 배열 크기의 경우 형식화된 배열 인스턴스화 비용은 개별 배열 요소에 액세스하고 작업하는 데 소요되는 시간에 비해 무시할 수 있습니다. 그러나 더 작은 배열 크기의 경우 객체 인스턴스화가 성능에 큰 영향을 미칠 수 있습니다.
따라서 개체 인스턴스화 성능에 부정적인 영향을 주지 않기 위해 stdlib는 ndarray 뷰의 시작 부분에 해당하는 버퍼 요소 위치에서 ndarray의 데이터 버퍼를 분리합니다. 이를 통해 다음 코드 조각에서 볼 수 있듯이 슬라이스 표현식 x[2:,3:] 및 x[3:,1:]가 새 버퍼 인스턴스를 인스턴스화할 필요 없이 없이 새 ndarray 뷰를 반환할 수 있습니다.
// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';
// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;
// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
ndarray 뷰의 시작 부분에서 데이터 버퍼를 분리한 결과, ndarray 데이터로 LAPACK 루틴을 호출할 때 새로운 유형의 배열 인스턴스를 인스턴스화할 필요가 없도록 유사하게 노력했습니다. 이는 모든 스트라이드 벡터 및 행렬에 대한 명시적 오프셋 매개변수를 지원하는 수정된 LAPACK API 서명을 생성하는 것을 의미합니다.
단순화를 위해 이전에 위에서 정의한 daxpy의 JavaScript 구현으로 돌아가겠습니다.
pip install numpy
다음 코드 조각에서 볼 수 있듯이, 첫 번째 색인화된 요소를 해결하는 책임이 API 소비자에게 이전되도록 위의 서명과 구현을 수정할 수 있습니다.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
ndarray의 경우 ndarray 인스턴스화 중에 해결이 이루어지므로 ndarray 데이터로 daxpy_ndarray를 호출하면 관련 ndarray 메타데이터가 직접 전달됩니다. 이는 다음 코드 조각에서 설명됩니다.
npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
BLIS와 유사하게 기존 LAPACK API 서명(예: 이전 버전과의 호환성)과 수정된 API 서명(예: 성능 저하 영향 최소화) 모두에서 가치를 확인하여 기존 및 각 LAPACK 루틴에 대한 API가 수정되었습니다. 코드 중복을 최소화하기 위해 우리는 더 높은 수준의 API로 래핑할 수 있는 일반적인 낮은 수준의 "기본" 구현을 구현하는 것을 목표로 했습니다. 위에 표시된 BLAS 루틴 daxpy의 변경 사항은 상대적으로 간단해 보일 수 있지만 기존 LAPACK 루틴과 예상 동작을 일반화된 구현으로 변환하는 것은 훨씬 덜한 경우가 많습니다.
도전은 이제 그만! 최종 제품은 어떤 모습일까요?!
피벗 인덱스 목록에 따라 입력 행렬에서 일련의 행 교환을 수행하는 LAPACK 루틴인 dlaswp로 다시 돌아가 보겠습니다. 다음 코드 조각은 참조 LAPACK Fortran 구현을 보여줍니다.
// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';
// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;
// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
C에서 Fortran 구현과의 인터페이스를 용이하게 하기 위해 LAPACK은 Fortran 구현을 래핑하고 행 및 열 주요 입력 및 출력 행렬 모두에 대한 조정을 제공하는 LAPACKE라는 2단계 C 인터페이스를 제공합니다. dlaswp의 중간 수준 인터페이스는 다음 코드 조각에 표시됩니다.
void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
int ix;
int iy;
int i;
if (N <= 0) {
return;
}
if (alpha == 0.0) {
return;
}
if (strideX < 0) {
ix = (1-N) * strideX;
} else {
ix = 0;
}
if (strideY < 0) {
iy = (1-N) * strideY;
} else {
iy = 0;
}
for (i = 0; i < N; i++) {
Y[iy] += alpha * X[ix];
ix += strideX;
iy += strideY;
}
return;
}
열 주요 행렬 a와 함께 호출되면 래퍼 LAPACKE_dlaswp_work는 제공된 인수를 Fortran 구현에 전달합니다. 그러나 행 주요 행렬 a와 함께 호출되면 래퍼는 메모리를 할당하고, a를 임시 행렬 a_t로 명시적으로 전치 및 복사하고, 선행 차원의 스트라이드를 다시 계산하고, a_t로 dlaswp를 호출하고, a_t에 저장된 결과를 전치 및 복사해야 합니다. a로 이동하고 마지막으로 할당된 메모리를 해제합니다. 이는 상당한 양의 작업이며 대부분의 LAPACK 루틴에서 일반적입니다.
다음 코드 조각은 선행 및 후행 차원 스트라이드, 인덱스 오프셋, 피벗 인덱스가 포함된 스트라이드 벡터를 지원하는 JavaScript로 포팅된 참조 LAPACK 구현을 보여줍니다.
const binary = new UintArray([...]); const mod = new WebAssembly.Module(binary);
기존 LAPACK과 일관된 동작을 갖는 API를 제공하기 위해 다음 코드 조각과 같이 위의 구현을 래핑하고 입력 인수를 "기본" 구현에 적용했습니다.
pip install numpy
이후에 stdlib의 다차원 배열에 더 직접적으로 API 매핑을 제공하고 피벗을 적용할 방향이 음수일 때 다음 코드 조각과 같이 특별한 처리를 수행하는 별도의 유사한 래퍼를 작성했습니다.
# Import all of NumPy: import numpy as np # Define arrays: x = np.asarray(...) y = np.asarray(...) # Perform operation: y[::2,:,:] += 5.0 * x[::2,:,:]
몇 가지 참고 사항:
OpenBLAS와 같은 하드웨어 최적화 라이브러리를 활용하려는 서버 측 애플리케이션의 경우 일반화된 서명 인수를 최적화된 API 동등 항목에 적용하는 별도의 래퍼를 제공합니다. 이러한 맥락에서 적어도 충분히 큰 배열의 경우 임시 복사본을 만드는 것이 오버헤드를 감당할 가치가 있습니다.
도전과 예상치 못한 난관, 여러 번의 설계 반복에도 불구하고 위의 dlaswp 외에도 다양한 LAPACK 루틴 및 관련 유틸리티에 대한 지원을 추가하여 35개의 PR을 열 수 있었다고 보고하게 되어 기쁩니다. 분명히 1,700개의 루틴은 아니지만 좋은 시작입니다! :)
그럼에도 불구하고 미래는 밝으며, 우리는 이 작업에 대해 매우 기대하고 있습니다. 여전히 개선과 추가 연구 및 개발의 여지가 많습니다. 특히
Quansight Labs 인턴십이 종료되는 동안 제 계획은 계속해서 패키지를 추가하고 이러한 노력을 추진하는 것입니다. 엄청난 잠재력과 LAPACK의 근본적인 중요성을 고려할 때, LAPACK을 웹으로 가져오는 이 이니셔티브가 계속해서 성장하는 것을 보고 싶습니다. 따라서 이를 추진하는 데 관심이 있다면 주저하지 말고 연락해 주세요! 개발 후원에 관심이 있으시면 Quansight 직원과 기꺼이 대화를 나누실 수 있습니다.
그리고 이번 인턴십 기회를 제공해 주신 Quansight에게 감사의 말씀을 전하고 싶습니다. 정말 많은 것을 배울 수 있어서 정말 행운이라고 생각합니다. Quansight에서 인턴이 되는 것은 나의 오랜 꿈이었고, 그것을 성취하게 되어 매우 감사합니다. 저는 놀라운 멘토이자 훌륭한 사람인 Athan Reines와 Melissa Mendonça에게 특별한 감사를 전하고 싶습니다! 그리고 그동안 크고 작은 방식으로 저를 도와주신 모든 stdlib 핵심 개발자와 Quansight의 모든 분들께 감사드립니다.
건배!
stdlib는 프로젝트 개발을 가속화하고 전문적으로 제작된 고품질 소프트웨어에 의존하고 있다는 사실을 확신할 수 있도록 강력한 고성능 라이브러리의 포괄적인 제품군을 제공하는 데 전념하는 오픈 소스 소프트웨어 프로젝트입니다.
이 게시물이 마음에 드셨다면 별표를 남겨주세요. GitHub에서 프로젝트를 재정적으로 지원하는 것을 고려해보세요. 귀하의 기여와 지속적인 지원은 프로젝트의 장기적인 성공을 보장하며 크게 감사드립니다!
위 내용은 웹 브라우저의 LAPACK의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
