내부 매트릭스 전환

In-situ matrix transplosition이라고도 하는 in-place matrix transplosition은 컴퓨터 메모리에서 N×M 매트릭스를 제자리에 전치하는 문제인데, 이상적으로는 O(1)(경계) 추가 스토리지로, 또는 기껏해야 NM보다 훨씬 적은 추가 스토리지로 전치하는 문제가 있다.일반적으로 행렬은 행 주 순서 또는 열 주 순서(즉, 연속적으로 배열된 연속 행 또는 열)로 저장되는 것으로 가정한다.

N ≠ M, 즉 데이터 요소의 복잡한 순열을 수반하는 사각형(직사각형)이 아닌 행렬의 경우 길이의 많은 사이클이 2보다 큰 경우, 현장에서 전치(in-place transpose)를 수행하는 것이 가장 어렵다.이와는 대조적으로 사각 행렬(N = M)의 경우, 모든 사이클이 길이 1 또는 2이며, 전치하는 것은 행렬의 위쪽 삼각형과 아래쪽 삼각형을 맞바꾸는 단순한 루프에 의해 달성될 수 있다.transposition은 본질적으로 비결합 메모리 액세스를 수반하기 때문에 캐시 라인 활용도를 향상시키거나 (매트릭스가 메인 메모리에 맞지 않는 경우) 코어 아웃오브(out-of-core) 운영을 위해 메모리 인접성을 최대화하고자 할 경우 추가적인 합병증이 발생한다.

최소 1950년대 후반부터 비제곱적 사내 전환 문제가 연구되어 왔으며 캐시, 코어 외 또는 유사한 메모리 관련 컨텍스트에 대한 인접성을 최적화하려는 시도를 포함한 몇 가지 알고리즘이 알려져 있다.

배경

컴퓨터에서는 같은 데이터에 다른 순서로 접근하는 것만으로 기억 속의 매트릭스를 명시적으로 전치하는 것을 피할 수 있다.예를 들어, BLAS와 같은 선형 대수용 소프트웨어 라이브러리는 일반적으로 데이터 이동을 피하기 위해 특정 행렬을 전치된 방식으로 해석하도록 지정하는 옵션을 제공한다.

그러나, 기억의 매트릭스를 그것의 전치 순서에 따라 물리적으로 다시 정렬하는 것이 필요하거나 바람직한 여러 가지 상황이 남아 있다.예를 들어 행 주계열 순서로 저장된 행렬의 경우 행렬의 행은 메모리에 연속적이고 열은 연속적이다.예를 들어 고속 푸리에 변환 알고리즘(예: Frigo & Johnson, 2005)에서 칼럼에 대해 반복 연산을 수행해야 하는 경우, 메모리에 매트릭스를 전치(열들이 인접하게 되도록)하면 메모리 인접성을 증가시켜 성능을 향상시킬 수 있다.이러한 상황은 일반적으로 매우 큰 행렬(캐시 크기를 초과함)의 경우와 일치하기 때문에 최소한의 추가 스토리지로 대체 작업을 제자리에 수행하는 것이 바람직하다.

또한, 순전히 수학적인 문제로서, 인플레이스 전환은 수 십 년 동안 해결된 많은 흥미로운 숫자 이론 퍼즐을 포함한다.

예

예를 들어, 2×4 행렬을 고려하십시오.

${\displaystyle {\bmatrix}11&12&13&14\\21&22&23&24\end{bmatrix}.}$

행-주요 형식에서 이것은 시퀀스 (11, 12, 13, 14, 21, 22, 23, 24), 즉 연속적으로 저장된 두 행으로 컴퓨터 메모리에 저장될 것이다.이것을 바꾸면 4×2 매트릭스를 얻을 수 있다.

${\displaystyle {\bmatrix}11&21\\12&22\\13&23\14&24\end{bmatrix}}}$

컴퓨터 메모리에 시퀀스로 저장된다(11, 21, 12, 22, 13, 23, 14, 24).

포지션	0	1	2	3	4	5	6	7
오리지널 스토리지	11	12	13	14	21	22	23	24
전치창고	11	21	12	22	13	23	14	24

저장 위치를 왼쪽에서 오른쪽으로 0에서 7까지 번호를 매긴 경우, 이 순열은 다음 네 가지 사이클로 구성된다.

(0), (1 2 4), (3 6 5), (7)

즉, 위치 0의 값은 위치 0(길이 1, 데이터 이동 없음)으로 간다.Next, the value in position 1 (in the original storage: 11, 12, 13, 14, 21, 22, 23, 24) goes to position 2 (in the transposed storage 11, 21, 12, 22, 13, 23, 14, 24), while the value in position 2 (11, 12, 13, 14, 21, 22, 23, 24) goes to position 4 (11, 21, 12, 22, 13, 23, 14, 24), and position 4 (11, 12, 13, 14, 21, 22, 23, 24) goes back to posit이온 1(11, 21, 12, 22, 13, 23, 14, 24).위치 7과 위치(3 6 5)의 값도 이와 유사하다.

순열의 속성

다음에서는 N×M 행렬이 0 기반 지수와 함께 행 주계열 순서로 저장된다고 가정한다.즉, n = 0에 대한 (n,m) 원소를 의미한다.,N-1 및 m = 0,...,M-1은 주소 a = Mn + m에 저장된다(그리고 우리가 무시하는 메모리에 일부 오프셋도 있다).전치된 M×N 행렬에서 해당 (m,n) 요소는 주소 a' = Nm + n에 저장되며, 다시 행 주계열 순서로 저장된다.우리는 전환 순열을 함수 a' = P(a)로 정의하는데, 다음과 같다.

${\displaystyle N}$ ${\displaystyle m}$+ ${\displaystyle n}$= ${\displaystyle P}$( M ${\displaystyle n}$+ m${\displaystyle }$) ${\$ 모든$$ $(,{\displaystyle m}$) ${\displaystyle \in }$[ ${\displaystyle 0,}$ N${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle \times }$[ ${\displaystyle 0,\mathrm{N}}$ - ${\displaystyle 1}$]${\displaystyle }$.${\displaystyle (n,m)\time$ [0,M-1$]\$time [0$,M-1]\.$

$이것$은 $숫자{\displaystyle }$a = ${\displaystyle 0,}$ ${\displaystyle \dots ,}$ ${\displaystyle MN}$ - $1$에 대한 순열을 정의한다$.$

P와 그 역에 대한 간단한 공식을 정의할 수 있다는 것이 밝혀졌다(Cate & Twigg, 1977년).첫 번째:

${\displaystyle P(a)={\begin{case}MN-1&{\text}{{}a=MN-1,\\Na{\bmod}{{{{{MN-1)&{\text{otherwise},\end{case}}}}}$

여기서 "mod"는 모듈로 작동한다.

둘째, 역순열은 다음과 같이 주어진다.

${\displaystyle P^{-1(a')={\begin{case}MN-1&{\text{{}a'=MN-1,\\\Ma'{\bmod{{{{MN-1)&{\text{otherwise}}.\end{case}}}$

(이것은 단지 N×M transpose의 역이 M×N transpose라는 사실의 결과일 뿐이지만, P로 구성된 P가⁻¹ 그 정체성을 부여한다는 것을 명시적으로 보여주기도 쉽다.)

케이트 앤 트위그(1977년)에 의해 증명되었듯이 순열의 고정점수(길이 1의 주기)는 정확히 1 + gcd(N-1,M-1)이며 여기서 gcd는 가장 큰 공통점이다.예를 들어, N = M으로 고정 점의 수는 간단히 N(행렬의 대각선)이다.N - 1과 M - 1이 동일시라면, 반면에 고정점 두 가지는 행렬의 왼쪽 위와 오른쪽 아래 모서리뿐이다.

길이 k>1의 사이클 수는 다음과 같다(Cate & Twigg, 1977).

${\displaystyle {\frac {1}{k}\sum _{d k}\mu(k/d)\gcd(N^{d}-1,MN-1)}$

여기서 μ는 뫼비우스함수이고 합은 k의 divisors d를 초과한다.

또한 a=1을 포함하는 사이클(즉, 행렬의 첫 번째 행의 두 번째 요소)은 항상 최대 길이 L의 사이클이며, 다른 모든 사이클의 길이 k는 L의 구분자여야 한다(Cate & Tigg, 1977).

$주어진$ 사이클 C의 ${\displaystyle \mathrm{경우}}$, 모든 요소 $x{\displaystyle }$ ${\displaystyle \in }$ C ${\displaystyle x\in C}$은$($는) 동일한 최대 공통 디비저 $d{\displaystyle }$=$MN-1)$를 갖는다$$$.$

이 정리는 효율적인 검색은 MN-1의 분할자 배수만을 바라볼 수 있기 때문에 순열의 주기를 찾는데 유용하다(Brenner, 1973).

라플린&브레브너(1970년)는 사이클이 한 번에 사이클 쌍을 허용하는 여러 알고리즘에 의해 악용되는 경우가 많다고 지적했다.특히 길이 k의 일부 사이클 C에서 가장 작은 요소가 되도록 하자.MN-1-s도 길이 k 사이클의 한 요소(아마도 같은 사이클일 것이다)라는 것을 따른다.

알고리즘

다음은 내부 매트릭스 전위치를 수행하기 위해 발표된 알고리즘을 간략히 요약한 것이다.이러한 알고리즘 중 일부를 구현하는 소스 코드는 아래 참조에서 확인할 수 있다.

접근자 전치

물리적으로 매트릭스를 전치하는 것은 컴퓨팅적으로 비용이 많이 들기 때문에, 메모리의 값을 이동하는 대신에 접근 경로가 전치될 수 있다.CPU 액세스를 위해 이 작업을 수행하는 것은 사소한 일이며, 하드웨어 가속화는 물리적으로 재조정되어야 할 수 있기 때문이다.^[1][2]

제곱 행렬

정사각형 N×N 행렬 A_n,m = A(n,m)의 경우, 모든 사이클이 길이 1(대각선_n,n A) 또는 길이 2(상각 삼각형이 하부 삼각형과 교환됨)를 가지기 때문에 인플레이스 전환이 쉽다.이를 달성하기 위한 유사 코드(영(0-based array index)는 다음과 같다.

for n = 0 ~ N - 2 for m = n + 1 ~ N - 1 스왑 A(n,m), A(m,n)

이러한 유형의 구현은 간단하지만 캐시 라인 활용률이 저하되어 성능이 저하될 수 있으며, 특히 N이 2의 전력(연관성이 제한된 CPU 캐시의 캐시 라인 충돌로 인해)인 경우 더욱 그러하다.그 이유는 내측 루프에서 m이 증가함에 따라 A(n,m) 또는 A(m,n)에 해당하는 메모리 어드레스가 N에 의해 (배열이 각각 컬럼-메이저 형식인지-행-메이저 형식인지에 따라)에서 불만스럽게 점프를 하기 때문이다.즉, 알고리즘은 기준의 지역성을 이용하지 않는다.

캐시 활용도를 향상시키기 위한 한 가지 해결책은 캐시 라인 크기에서 주어진 블록으로 한번에 여러 숫자로 작동하는 알고리즘을 "차단"하는 것이다. 불행히도 이는 알고리즘이 캐시 라인의 크기("캐시 인식")에 따라 달라지며, 여러 단계의 캐시를 가진 현대 컴퓨터에서는 여러 수준의 마치가 필요하다.네모난 차단대신, 매트릭스를 대략 같은 크기의 4개의 하위 계수로 나누고, 대각선을 따라 2개의 하위 계수를 재귀적으로 바꾸고, 대각선 위아래 2개의 하위 계수를 전치 및 스와핑하는 재귀 알고리즘을 통해 더 나은 성능을 얻을 수 있다는 것이 제안되었다(Frigo 등, 1999).(N이 충분히 작을 경우, N=1까지 순진하게 반복하면 과도한 함수 호출 오버헤드가 발생하기 때문에 위의 간단한 알고리즘을 베이스 케이스로 사용한다.)캐시 라인 크기가 명시적 매개 변수가 되지 않아도 캐시 라인을 이용할 수 있다는 점에서 캐시 취약 알고리즘이다.

비제곱 행렬:주기 따라하기

정사각형이 아닌 행렬의 경우 알고리즘이 더 복잡하다.1980년 이전의 많은 알고리즘은 "계속 주기" 알고리즘으로 설명될 수 있다.즉, 사이클을 반복하여 데이터를 사이클의 한 위치에서 다음 위치로 이동시킨다.유사 코드 형식:

각 길이>1주기 C에서 시작 어드레스 s를 선택한다. C에서 시작 어드레스 s를 선택한다. s let x = s의 이전 x = 이전 x let x = 이전 x let x = 이전 x let x = 이전 x let x = 이전 x let x = 이전 x let x = 이전 x let x = 이전 x let d에서 후속 x의 이전 x move 데이터.

알고리즘 간의 차이는 주로 사이클의 위치 파악 방법, 각 사이클에서 출발 주소를 찾는 방법, 각 사이클이 정확히 한 번 이동하는지 확인하는 방법에 있다.일반적으로 위에서 논의한 바와 같이, s와 MN-1-s는 길이가 같은 사이클(아마도 동일한 사이클)이기 때문에 사이클은 쌍으로 이동한다.때때로, 일반적으로 길이 M+N인 작은 스크래치 배열(예: Brendner, 1973; Cate & Tigg, 1977)을 사용하여 방문했던 배열의 위치의 하위 집합을 추적하고 알고리즘을 가속화한다.

주어진 사이클이 이미 이동되었는지 여부를 판단하기 위해, 가장 간단한 계획은 요소당 1비트씩 O(MN) 보조 저장소를 사용하여 주어진 요소가 이동되었는지 여부를 표시하는 것이다.O(M+N) 또는 O(log MN) 보조 저장장치만 사용하려면 더욱 복잡한 알고리즘이 필요하며, 알려진 알고리즘은 Knuth(Fich et al., 1995; Gustavson & Wirdszzz, 2007)에 의해 처음 증명된 것처럼 기껏해야 O(MN log MN)의 최악의 선형 계산 비용을 가지고 있다.

그러한 알고리즘은 각 데이터 요소를 정확히 한 번 이동하도록 설계된다.단, 사이클 계산에는 상당한 양의 산술도 포함되며, 위에서 설명한 바와 같이 사이클의 인접 요소가 N의 곱셈 인자에 의해 다르기 때문에 상당히 비첨가적인 메모리 액세스가 필요하다.

더 많은 총 데이터 이동 비용으로 메모리 인접성 향상

몇 가지 알고리즘은 데이터 이동의 증가와 스토리지 요구 사항의 약간 더 큰 비용으로 더 큰 메모리 인접성을 달성하도록 설계되었다.즉, 각 데이터 요소를 두 번 이상 이동할 수 있지만, 연속적인 데이터 블록 처리에 최적화된 SIMD 아키텍처뿐만 아니라 캐시에 의존하는 현대 CPU의 성능을 향상시킬 수 있는 연속 메모리 액세스(공간적 인접성)가 더 많이 수반된다.전환의 공간적 인접성이 연구된 것으로 보이는 가장 오래된 문맥은 코어 외 연산(Alltop, 1975년 기준)으로, 매트릭스가 너무 커서 메인 메모리에 맞지 않는다("core").

예를 들어 d = gcd(N,M)가 작지 않으면 소량의 추가 저장(NM/d)을 사용하여 전치 작업을 수행할 수 있으며, 어레이 위로 최대 3회 패스(Alltop, 1975; Dow, 1995)가 가능하다.패스의 2개에는 (작은 완충기를 사용하여 효율적으로 제자리에 있지 않게 수행될 수 있는) 개별적인 작은 전이 순서가 포함되며, $1개$에는 ${\displaystyle \mathrm{NM}/{d\mathrm{}}^{}}$ 2$${\$디스플레이 스타일$ NM$/d^{2$}}블록$$(이동되는 블록이 크고 연속적이기 때문에 효율적이며, 사이클은 ar)이 포함된다.e 길이가 최대 2이다.이는 N이 M의 배수(또는 그 반대)인 경우, 두 개의 아웃오브 패스 중 하나만 필요하기 때문에 더욱 단순화된다.

다중 종속 전이가 포함된 비복사 시간 치수에 대한 또 다른 알고리즘은 Catanzaro 외(2014년)에 의해 설명되었다.N - M이 작은 경우, 다우(1995)는 최소(N, M) ⋅ 최소(N, M) 제곱 전치 또는 그 다음에 작은 위치 전치 전치(Small of place transse)를 포함하는 N - M m 최소(N,M) 추가 보관이 필요한 또 다른 알고리즘을 설명한다.Frigo & Johnson(2005)은 공간적 지역성을 이용하기 위해 캐시 라인에 의존하는 범용 CPU에 캐시 집중 기술을 사용하기 위해 이러한 알고리즘의 적응을 설명한다.

매트릭스가 메인 메모리에 맞지 않고 하드 디스크에 주로 저장되어야 하는 코어 외 매트릭스 전환 작업에서는 일부 예외를 제외하고 N = M 사각 매트릭스 사례에 주로 초점을 맞추었다(예: Alltop, 1975)특히 병렬 컴퓨팅에 적용되는 Out-of-Core 알고리즘의 최근 리뷰는 예에서 확인할 수 있다.Su & Prasanna(2002)와 Krishnomoorth 외 연구진.(2004).

참조

외부 링크

소스 코드

• OFFT - Fortran에서 사각 행렬의 내부 전치물 재귀 블록
• Jason Stratos Papadopulos, C, sci.math.num-analysis 뉴스그룹(1998년 4월 7일)에서 사각 행렬의 내부 전이를 차단했다.
• 정사각형 및 비 정사각형 행렬의 인플레이스 전환을 수행하기 위한 추가 코드는 위의 참조 섹션에 있는 "소스 코드" 링크를 참조하십시오.
• libmarshal GPU에 대한 직사각형 행렬의 내부 전치 차단.