2025-11-18T22:43:13.755250

Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms

Mukunoki, Ozaki

To obtain accurate results in numerical computation, high-precision arithmetic is a straightforward approach. However, most processors lack hardware support for floating-point formats beyond double precision (FP64). Double-word arithmetic (Dekker 1971) extends precision by using standard floating-point operations to represent numbers with twice the mantissa length. Building on this concept, various multi-word arithmetic methods have been proposed to further increase precision by combining additional words. Simplified variants, known as quasi algorithms, have also been introduced, which trade a certain loss of accuracy for reduced computational cost. In this study, we investigate the performance of quasi algorithms for double- and triple-word arithmetic in sparse iterative solvers based on the Conjugate Gradient method, and compare them with both non-quasi algorithms and standard FP64. We evaluate execution time on an x86 processor, the number of iterations to convergence, and solution accuracy. Although quasi algorithms require appropriate normalization to preserve accuracy - without it, convergence cannot be achieved - they can still reduce runtime when normalization is applied correctly, while maintaining accuracy comparable to full multi-word algorithms. In particular, quasi triple-word arithmetic can yield more accurate solutions without significantly increasing execution time relative to double-word arithmetic and its quasi variant. Furthermore, for certain problems, a reduction in iteration count contributes to additional speedup. Thus, quasi triple-word arithmetic can serve as a compelling alternative to conventional double-word arithmetic in sparse iterative solvers.

academic

준 다중 단어 알고리즘을 이용한 고정밀 산술을 사용하는 희소 반복 해석기

기본 정보

논문 ID: 2510.13536
제목: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
저자: Daichi Mukunoki (나고야 대학교), Katsuhisa Ozaki (시바우라 공과 대학교)
분류: cs.MS (수학 소프트웨어)
발표 시간: 2025년 10월 15일 (arXiv 사전 인쇄본)
논문 링크: https://arxiv.org/abs/2510.13536

초록

수치 계산에서 정확한 결과를 얻기 위해 고정밀 산술은 직접적인 방법이다. 그러나 대부분의 프로세서는 배정밀도(FP64) 이외의 부동소수점 형식에 대한 하드웨어 지원이 부족하다. 이중 단어 산술(Dekker 1971)은 표준 부동소수점 연산을 사용하여 두 배의 가수 길이를 가진 숫자를 나타냄으로써 정밀도를 확장한다. 이 개념을 기반으로 추가 단어를 결합하여 정밀도를 더욱 증가시키는 다양한 다중 단어 산술 방법이 제안되었다. 간소화된 변형인 준 알고리즘도 도입되었으며, 이들은 계산 비용 감소를 위해 일정한 정밀도 손실을 감수한다. 본 연구는 켤레 기울기 방법을 기반으로 하는 희소 반복 해석기에서 이중 단어 및 삼중 단어 산술의 준 알고리즘 성능을 조사하고, 이를 비준 알고리즘 및 표준 FP64와 비교한다.

연구 배경 및 동기

핵심 문제

하드웨어 제한 문제: 대부분의 프로세서는 배정밀도(FP64) 이외의 부동소수점 형식에 대한 하드웨어 지원이 부족하여 고정밀 수치 계산의 구현을 제한한다
희소 반복 해석기의 정밀도 요구: 대규모 희소 선형 시스템을 풀 때, 반올림 오차는 수렴에 필요한 반복 횟수를 증가시켜 해석 정밀도와 효율성에 영향을 미친다
성능과 정밀도의 균형: 전통적인 다중 단어 산술 방법은 정밀도를 향상시킬 수 있지만 계산 오버헤드가 크다

연구의 중요성

희소 반복 해석기는 과학 계산 및 공학 응용에 광범위하게 적용된다
고정밀 산술은 수렴성을 개선하고 반복 횟수를 감소시킬 수 있다
메모리가 제한된 응용에서 다중 단어 산술의 추가 오버헤드는 메모리 지연에 의해 숨겨질 수 있다

기존 방법의 한계

전통적인 다중 단어 산술(DW, TW 등)의 계산 비용이 높다
준 알고리즘은 계산 비용을 감소시키지만 정밀도 손실을 초래할 수 있다
반복 해석기에서 준 알고리즘 성능에 대한 체계적 평가가 부족하다

핵심 기여

준 알고리즘 성능의 체계적 평가: 희소 반복 해석기에서 QDW 및 QTW 알고리즘 성능을 처음으로 체계적으로 평가
정규화의 핵심 역할 발견: 적절한 정규화가 준 알고리즘 수렴성에 미치는 중요성을 입증
QTW를 효과적인 대안으로 제시: 준 삼중 단어 산술(QTW)이 전통적인 이중 단어 산술의 효과적인 대안이 될 수 있음을 입증
포괄적인 성능 분석: 실행 시간, 반복 횟수 및 해석 정밀도의 세 가지 차원에서 종합 평가

방법 상세 설명

작업 정의

대칭 양정치 선형 시스템 Ax = b를 풀기:

A는 n×n 대칭 양정치 희소 행렬
b는 우변 벡터
x는 구하려는 벡터

켤레 기울기(CG) 방법을 사용하여 반복적으로 풀고 다양한 정밀도 산술의 성능을 평가한다.

다중 단어 산술 아키텍처

기본 알고리즘

오류 자유 변환 알고리즘:

TwoSum(a,b): a+b를 부동소수점 결과 x와 반올림 오차 y로 분해
QuickTwoSum(a,b): TwoSum의 효율적 변형, |a|≥|b|를 요구
TwoProdFMA(a,b): FMA 연산을 사용하여 a×b를 결과와 오차로 분해

이중 단어 산술(DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- 피연산자: 11개 FP64 연산
- 정규화 단계(QuickTwoSum) 포함

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- 피연산자: 7개 FP64 연산
- 정규화 단계 포함

준 이중 단어 산술(QDW)

정규화 단계 생략, 높은 낮은 단어 겹침 허용
QDWadd: 8개 연산, QDWmul: 4개 연산
계산 비용 대폭 감소

준 삼중 단어 산술(QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- 피연산자: 21개 FP64 연산
- fl(c1+c2)=c1 및 fl(c2+c3)=c2를 강제하지 않음

QTWmul: [c1,c2,c3] = QTWmul(a1,a2,a3,b1,b2,b3)
- 피연산자: 24개 FP64 연산

기술 혁신점

SIMD 벡터화 최적화:
- AVX2 및 AVX-512 명령어 집합을 사용한 벡터화
- QTW 알고리즘은 조건부 분기를 제거하여 벡터화에 더 적합
정규화 전략:
- CG 방법의 잔차 벡터 업데이트 후 정규화 수행
- VecSum3 알고리즘을 사용하여 삼중 단어 산술의 비트 겹침 완화
혼합 정밀도 구현:
- 계수 행렬 A 및 우변 벡터 b는 FP64로 저장
- 내부 계산은 해당하는 다중 단어 산술 사용

실험 설정

데이터 집합

SuiteSparse 행렬 컬렉션의 8개 대칭 양정치 행렬 사용:

행렬	차원 n	0이 아닌 원소 nnz	응용 분야
Hook_1498	1,498,023	60,917,445	구조 문제
bone010	986,703	47,851,783	모델 축소
nd24k	72,000	28,715,634	2D/3D 문제
crankseg_2	63,838	14,148,858	구조 문제

평가 지표

실행 시간: 반복당 시간 및 총 수렴 시간
반복 횟수: 수렴에 필요한 반복 수
해석 정밀도: 상대 오차 범수 ||xk-x*||2/||x*||2

비교 방법

CG-FP64: 표준 배정밀도 구현
CG-DW: 이중 단어 산술 구현
CG-QDW: 준 이중 단어 산술 구현
CG-TW: 삼중 단어 산술 구현
CG-QTW: 준 삼중 단어 산술 구현

구현 세부 사항

하드웨어 플랫폼: Intel Xeon Gold 6230 CPU (20 코어, 2.10-3.90 GHz)
컴파일러: g++ 11.3.0, 최적화 옵션 -O3 -march=native
병렬화: OpenMP + SIMD 벡터화
수렴 허용 오차: ε = 10^-16, 10^-24, 10^-32

실험 결과

주요 결과

성능 오버헤드 분석

FP64 대비 실행 시간 오버헤드(100회 반복):

CG-QDW: 약 1.3배
CG-DW: 약 2.1배
CG-QTW: 약 2.4배
CG-TW: 최대 67배

수렴 성능 비교

ε=10^-16 수렴 허용 오차에서의 전형적 결과:

행렬	FP64 시간(s)/반복 수	QDW 시간(s)/반복 수	QTW 시간(s)/반복 수
bone010	170/21780	120/12547	150/11352
pdb1HYS	5.4/12807	3.4/6285	4.9/5346

주요 발견

정규화의 필요성:
- 정규화를 수행하지 않으면 준 알고리즘이 수렴하지 않음
- 잔차 벡터 업데이트 후 정규화를 수행하면 수렴을 보장할 수 있음
QTW의 장점:
- TW 대비 계산 오버헤드 대폭 감소
- TW와 동등한 정밀도 달성
- SIMD 벡터화 지원으로 성능 향상
반복 횟수 감소의 이점:
- 고정밀 산술은 반복 횟수를 감소시킬 수 있음
- 총 실행 시간이 FP64 구현보다 낮을 수 있음