레이레이 계수의 최소화에 의한 내부고유치 계산을 위한 병렬준비행렬들의 비교

마상백,장호종,Ma, Sang-back,Jang, Ho-Jong 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.2

최근에 CG 반복법을 이용하여 레이레이 계수를 최소화함으로써 대칭행렬의 내부고유치를 구하는 방법이 개발되었다 그리고 이 방법은 병렬계산에 매우 적합하다. 적절한 준비행렬의 선택은 수렴속도를 향상시킨다. 우리는 본 연구에서 이를 위한 병렬준비행렬들을 비교한다. 고려된 준비행렬들은 Point-SSOR, 다중색채하의 ILU(0)와 Block SSOR이다. 우리는 128개의 노드를 가진 CRAY-T3E에서 구현하였다. 프로세서간의 통신은 MPI 리이브러리를 사용하였다. 최고 512$\times$512 행렬까지 시험하였는데 이 행렬들은 타원형 편미분방정식의 근사화에서 얻어졌다. 그 결과 다중색채 Block SSOR이 가장 성능이 우수한 것으로 판명되었다. Recently, CG (Conjugate Gradient) scheme for the optimization of the Rayleigh quotient has been proven a very attractive and promising technique for interior eigenvalues for the following eigenvalue problem, Ax=λx (1) The given matrix A is assummed to be large and sparse, and symmetric. Also, the method is very amenable to parallel computations. A proper choice of the preconditioner significantly improves the convergence of the CG scheme. We compare the parallel preconditioners for the computation of the interior eigenvalues of a symmetric matrix by CG-type method. The considered preconditioners are Point-SSOR, ILU (0) in the multi-coloring order, and Multi-Color Block SSOR (Symmetric Succesive OverRelaxation). We conducted our experiments on the CRAY­T3E with 128 nodes. The MPI (Message Passing Interface) library was adopted for the interprocessor communications. The test matrices are up to $512{\times}512$ in dimensions and were created from the discretizations of the elliptic PDE. All things considered the MC-BSSOR seems to be most robust preconditioner.

대형이산 행렬 시스템의 초대형병렬컴퓨터에서의 해법을 위한 병렬준비 행렬의 비교

마상백,Ma, Sang-Baek 한국정보처리학회 1995 정보처리논문지 Vol.2 No.4

이 논문에서 우리는 CM-5와 같은 초대형병렬컴퓨터에서 대형 이산선형체제를 풀기 위한 준비행렬로써 두 가지를 소개한다. 대다수의 초대형병렬컴퓨터들은 프로세서간의 통신을 메세지패씽(messagepassing)에 의존하는데 현재의 기술수준하에서는 이 통신속 도가 실수계산속도에 비해 매우 느리므로 종래의 메모리공유컴퓨터에서와는 달리 데이 터통신량을 최소화하는 알고리듬이 요구된다. 블록 SOR에 다중색채기법을 가미한 알고 리듬이 그 한 예로써 우리는 이를 CM-5에서 구현한 결과 N=512x512 행렬에서 프로세서 의 수가 16에서 512의 범위 하에서 50%의 효율을 실현하였다. 반면 종래의 효율적인 병렬 준비행렬로 알려진 AKI알고리듬은 방대한 량의 데이터통신 때문에 매우 열등한 결과를 보여준다. In this paper we present two preconditioners for solving large sparse linear systems arising from elliptic partial differential equations on massively parallel machines, such as the CM-5. Most massively parallel machines do heavily rely on the message-passing for the interprocessor communications. but according to the current manufacturing standards the cost of communications is very high compared to that of floating point arithmetic computations. Due to this we need an algorithm which minimizes the amount of interprocessor communication on the massively parallel machines. We will show that Block SOR(Successive Over Relaxation) method coupled with the multi-coloring technique is one of such preconditioner on the massively parallel machines, by conducting experiments in the CM-5. Also, we implemented the ADI(Alternation Direction Implicit) method in the CM-5, which has been conventionally one of the most powerful parallel preconditioner. Our experiment shows that Block SOR method coupled with the multi-coloring technique could yield a speedup with 50% efficiency with the range of number of processors form 16 to 512 for a matrix with dimension 512x512. On the other hand, the ADI method shows a very poor performance.

대형비대칭 이산행렬의 CRAY-T3E에서의 해법을 위한 확장가능한 병렬준비행렬

마상백,Ma, Sang-Baek 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.3

In this paper we propose a block-type parallel preconditioner for solving large sparse nonsymmetric linear systems, which we expect to be scalable. It is Multi-Color Block SOR preconditioner, combined with direct sparse matrix solver. For the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with Multi-Color ordering. Since most of the time is spent on the diagonal inversion, which is done on each processor, we expect it to be a good scalable preconditioner. We compared it with four other preconditioners, which are ILU(0)-wavefront ordering, ILU(0)-Multi-Color ordering, SPAI(SParse Approximate Inverse), and SSOR preconditiner. Experiments were conducted for the Finite Difference discretizations of two problems with various meshsizes varying up to $1025{\times}1024$. CRAY-T3E with 128 nodes was used. MPI library was used for interprocess communications, The results show that Multi-Color Block SOR is scalabl and gives the best performances.

CRAY-2에서의 대형희귀행렬 연립방정식의 해법을 위한 벡터준비행렬의 재배열 방법

마상백,Ma, Sang-Baek 한국정보처리학회 1995 정보처리논문지 Vol.2 No.6

이 논문에서 우리는 CRAY-2에서 편미분방정식에서 발생하는 대형희귀 연립방정 식의 효과적인 벡터준비행렬을 만들기 위한 재배열방법을 제시한다. 이 재배열방법은 종래의 빨강/검정 배열의 선형 형태로써, ILU 준비행렬의 변형에 사용될 경우 필인 (fill-in)을 크게 하면 종래의 빨강/검정 재배열의 약점이던 수렴율의 감소를 극복할 수 있다. 우리는 CRAY-2에서 여러 가지 실험을 통해 우리의 주장을 입증한다. 또, 에러 행렬의 후로베니우스 놈을 계산한 결과도 우리의 주장과 일치한다. In this paper we present a reordering scheme that could lead to efficient vectorization of the preconditioners for the large sparse linear systems arising from partial differential equations on the CRAY-2, This reordering scheme is a line version of the conventional red/black ordering. This reordering scheme, coupled with a variant of ILU(Incomplete LU) preconditioning, can overcome the poor rate of convergence of the conventional red/black reordering, if relatively large number of fill-ins were used. We substantiate our claim by conducting various experiments on the CRAY-2 machine. Also, the computation of the Frobenius norm of the error matrices agree with our claim.

레이레이 계수의 최소화에 의한 내부고유치 계산을 위한 병렬준비행렬들의 비교

마상백,장호종 한국정보처리학회 2003 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.10 No.2

CM - 5 에서 비정규적 구조를 가진 희소 다원 일차 연립방정식의 해법을 위한 ILU(0) 와 Block SOR / SSOR 조정행렬의 병렬화

마상백(Sangback Ma) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.5

일반적인 크기 N의 희소 다원일차 연립 방정식의 해를 구할때 다중채색방법은 O(N) 의 병렬성을 제공한다. 그러나 이방법은 조정된 CG 방법에서처럼 수렴율이 감소하는 단점을 가지고있다. 이러한 단점을 극복할수 있는 다른 방법은 파동전면방법으로서, 주어진 행렬에서 얻을 수 있는 병렬성을 추구한다. 이 경우 수렴율은 변하지 않으나 파동전면의 길이가 일정치 않기때문에 병렬성이 제한된다. 이 논문에서는 우리는 위의 두가지 방법을 CM-5에서 ILU(0)와 Block SOR/SSOR 조정행렬에 적용하여 그 결과를 비교 분석 하였다. 여러가지 문제에서 검사 해본 후 다중채색하의 ILU(0) 방법이 가장 우수한 것으로 입증되었다. When solving general sparse linear systems multi-coloring techniques can yield a parallelism of order N, where N is the dimension of the matrix. However, this approach suffers from the deterioration of the rate of convergence, as in preconditioned CG method. Another technique that does not suffer from this is the wavefront technique, which exploits parallelism available in the original matrix. The rate of convergence remains the same, but the maximum parallelism is limited by the lengths of the wavefronts, which are often nonuniform. In this paper we compare these two approaches on ILU(0) and Block SOR/SSOR preconditioners on the CM-5. We have found that for the problems tested ILU(0) with multicoloring technique outperforms the other alternatives.

CRAY -2 에서 멀티 / 미이크로 태스킹 라이브러리를 이용한 선형시스템의 병렬해법

마상백(Ma Sang Back) 한국정보처리학회 1997 정보처리학회논문지 Vol.4 No.11

Multitasking and microtasking on the CRAY machine provides still another way to improve computational power. Since CRAY-2 has 4 processors we can achieve speedup up to 4 with properly designed algorithms. In this paper we present two parallelizations of linear system solution on the CRAY-2 with multitasking and microtasking library. One is the LU decomposition on the dense matrices and the other is the iterative solution of large sparse linear systems with the preconditioner proposed by Radicati di Brozolo. In the first case we realized a speedup of 1.3 with 2 processors for a matrix of dimension 600 with the multitasking and in the second case a speedup of around 3 with 4 processors for a matrix of dimension 8192 with the microtasking. In the first case the speedup is limited because of the nonuniform vector lengths. In the second case the ILU(0) preconditioner with Radicati's technique seem to realize a reasonably high speedup with 4 processors.

2차원 ADI 준비행렬에서 최적 p 변수를 결정하기 위한 다중그리드적인 알고리즘

마상백(Sangback Ma) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.11

준비행렬을 사용한 반복적 방법들은 타원형 편미분방정식을 근사화한 대형 이산 연립방정식을 풀기 위한 효과적인 방법들이다. 특히, 최근의 병렬/벡터 컴퓨터에서는 반복적 방법들이 병렬 계산에 적합한 이유로 더욱 더 관심의 대상이 되고 있다. 그러나 불행히도 널리 인정받는 병렬 준비행렬이 없는 실정이다. 2차원에서 ADI 방법은 벡터 계산에 매우 적합하나 그 성능이 p 변수에 매우 민감하다. 일반적인 행렬에서 최적 p 변수를 결정하는 것은 매우 어려운 일이며 그 행렬의 고유치 에 대한 정보를 요구한다. 이 논문에서 우리는 메쉬크기의 선형의존성에 기초한 간단한 다중그리드 적인 방법을 제시한다. 이 방법은 분리불가능한 편미분방정식에 적용될 수 있으며 주어진 행렬의 고유치 에 대한 정보를 요구하지 않는다. 우리는 이 방법을 가지고 CRAY-C9O 에서 실험을 하였다. 그 결과는 우리의 방법이 최적 p 변수를 예측하는 데 있어서 매우 효과적이며 시간측정결과 또 하나의 벡터 연산에 최적화된 ILUT(8) 준비행렬보다 우수함이 입증되었다. Preconditioned iterative methods are effective methods for solving large sparse linear systems created from discretization of elliptic partial differential equations Especially, on modern parallel/vector computers iterative methods are particularly attractive due to its amenability to parallel computation. Unfortunately, there are no widely accepted parallel preconditioners. In two dimensions ADI(Alternate Directions Implicit) method is well-known for its suitability to vector computations, but its performance is very sensitive to the choice of the p acceleration parameter. For general matrices it is very difficult to determine the optimal p parameter and it requires the knowledge about the eigenvalues of the matrix. In this paper we present a simple multi-grid motivated heuristic determining the optimal p based on the approximately linear dependence of the optimal parameter on the meshsize. This heuristic could also be applied for nonseparable PDEs and does not require the knowledge about the eigenvalues of the given matrix. Experiments were conducted on the CRAY-C9O with the heuristic. Our results show that the heuristic is highly successful in finding the optimal parameter and our timing experiment shows that it is superior to the ILUT(8), one of the preconditioner highly optimized for the vector processing.

컴퓨터구조 : 대형이산 행렬 시스템의 초대형병렬컴퓨터에서의 해법을 위한 병렬준비 행렬의 비교

마상백(Ma Sang Back) 한국정보처리학회 1995 정보처리학회논문지 Vol.2 No.4

이 논문에서 우리는 CM-5와 같은 초대형병렬컴퓨터에서 대형 이산선형체제를 풀기 위한 준비행렬로써 두 가지를 소개한다. 대다수의 초대형병렬컴퓨터들은 프로세서간의 통신을 메세지패씽(message-passing)에 의존하는데 현재의 기술수준하에서는 이 통신속도가 실수계산속도에 비해 매우 느리므로 종래의 메모리공유컴퓨터에서와는 달리 데이터통신량을 최소화하는 알고리듬이 요구된다. 블록 SOR에 다중색채기법을 가미한 알고리듬이 그 한 예로써 우리는 이를 CM-5에서 구현한 결과 N=512x512 행렬에서 프로세서의 수가 16에서 512의 범위 하에서 50%의 효율을 실현하였다. 반면 종래의 효율적인 병렬 준비행렬로 알려진 ADI알고리듬은 방대한 량의 데이터통신 때문에 매우 열등한 결과를 보여준다. In this paper we present two preconditioners for solving large sparse linear systems arising from elliptic partial differential equations on massively parallel machines, such as the CM-5. Most massively parallel machines do heavily rely on the message-passing for the interprocessor communications, but according to the current manufacturing standards the cost of communications is very high compared to that of floating point arithmetic computations. Due to this we need an algorithm which minimizes the amount of interprocessor communication on the massively parallel machines. We will show that Block SOR(SuccessiveOverRelaxation) method coupled with the multi-coloring technique is one of such preconditioner on the massively parallel machines, by conducting experiments on the CM-5. Also, we implemented the ADI(AlternatingDirectionImplicit) method on the CM-5, which has been conventionally one of the most powerful parallel preconditioner. Our experiment shows that Block SOR method coupled with the multi-coloring technique could yield a speedup with 50% efficiency with the range of number of processors from 16 to 512 for a matrix with dimension 512x512. On the other hand, the ADI method shows a very poor performance.

알고리즘 : CRAY-2 에서의 대형희귀행렬 연립방정식의 해법을 위한 벡터준비행렬의 재배열방법

마상백(Ma Sang Back) 한국정보처리학회 1995 정보처리학회논문지 Vol.2 No.6

이 논문에서는 우리는 CRAY-2 에서 편미분방정식에서 발생하는 대형희귀연립방정식의 효과적인 벡터 준비행렬을 만들기 위한 재배열방법을 제시한다. 이 재배열방법은 종래의 빨강/검정 배열의 선형 형태로써, ILU 준비행렬의 변형 형태에 사용될 경우 필인(fill-in)을 크게 하면 종래의 빨강/검정 재배열의 약점이던 수렴율의 감소를 극복할 수 있다. 우리는 CRAY-2 에서 여러 가지 실험을 통해 우리의 주장을 입증한다. 또, 에러 행렬의 후로베니우스 놈을 계산한 결과도 우리의 주장과 일치한다. In this paper we present a reordering scheme that could lead to efficient vectorization of the preconditioners for the large sparse linear systems arising from partial differential equations on the CRAY-2. This reordering scheme is a line version of the conventional red/black ordering. This reordering scheme, coupled with a variant of ILU(Incomplete LU) preconditioning, can overcome the poor rate of convergence of the conventional red/black reordering, if relatively large number of fill-ins were used. We substantiate our claim by conducting various experiments on the CRAY-2 machine. Also, the computation of the Frobenius norm of the error matrices agree with our claim.