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

마상백,장호종,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.

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.

알고리즘 : 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.

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

마상백(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.

MultiTriangulation에서의 가변 LOD 추출

양수정(Su-Jung Yang),마상백(Sang-Back Ma) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.2Ⅱ

간소화된 메쉬의 다중해상 표현을 실시간으로 원하는 해상 메쉬의 렌더링이 가능하고 저해상 메쉬에서 고해상 메쉬로의 전환이 시각적인 연속성을 갖는다. 또 메쉬의 공간마다 다른 해상도의 표현이 가능하다. 본 논문에서는 기존의 다중해상모델의 특징과 단점을 알아보고 다중모델링 이슈를 제시한다. 효율적인 가변 LOD를 위한 기존의 다중해상 모델을 일반화시킨 MT(MultiTriangulation)를 제시한다. MT의 구조적 특징, MT에서의 선택적 상세화와 시점과의 거리에 따른 가변 LOD 질의를 알아본다.

메쉬 간략화를 통한 지형데이터의 가변 해상도 모델구축

유동윤(Dong-Yun Yoo),마상백(Sang-Back Ma) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.2Ⅱ

본 논문은 방대한 양의 데이터로 이루어진 삼각형 메쉬의 특성을 유지하면서 보다 적은 양의 데이터로 간략화된 메쉬를 생성해내는 기법을 제안한다. 메쉬 간략화는 기본적으로 에지 축약에 의해서 이루어지며, 에지 축약에 의해 발생하는 에러는 원본 메쉬의 점과 간략화된 메쉬의 평균 평면간의 거리를 사용하여 측정한다. 또한 본 논문에서는 제안한 메쉬 간략화 기법을 사용하여 다단계의 해상도를 가지는 메쉬를 빠르게 구하기 위한 가변 해상도 모델을 구현한다.

문서에서의 구문적 오류 검출

김진우,마상백,김한우 漢陽大學校 工學技術硏究所 1999 工學技術論文集 Vol.8 No.1

본 논문은 기존의 철자 검사기로는 검출해 내지 못했던 구문 오류 일부를 검출해 낼 있는 방법을 제시한다. 일반적으로 문서작업을 할 때의 오타입력은 주로 자판 입력시 주위 문자를 잘못 입력하는 경우의 오류가 대부분이다. 이러한 오류 단어가 형태소 분석에 실패하는 경우는 철자 오류검사로도 교정이 되지만 형태소 분석을 성공한 경우에는 검출이 불가능하다. 따라서 형태소 분석을 통과한 오류 단어를 발견하는 방법을 제안한다. 이 방법은 특정 단어를 자소 대치를 한 후 다른 단어와 비교하여 오류일 확률이 낮은 단어와 매칭이 된다면 일단 오류 후보로 가정한다는 것이다. 여기에는 일부 휴리스틱한 제약이 필요하다. 이 단어간 비교에 의한 추정은 전에 발견하지 못했던 구문 오류 일부를 발견할 수 있게 해준다. In a typed document, spelling errors are cause of word errors. Traditional Critiquing system like a spelling checker detects spelling error using a morphological analyser. If morphological analyser detected a certain error word, it could also correct the error word. In other case, spelling checker can not detect a error word. In this paper, a method that can detect additional syntactic errors by comparing words in a document is proposed. The method is based on word errors appearing frequently in typist's misspelling using word processor. In this the method, a certain word is changed by one-letter substitution, and the changed word is compared with errors of low possibility words in a document. If the changed word matches errors of low possibility words, this method deduces that the word is the error of high possibility word. The method has to be added with various heuristic restrictions. The Deduction Using Words Comparison' method can detect additional syntactic errors.

Parallel solution of linear systems on the CRAY-2 using micro tasking library

Ma, Sang-Back 漢陽大學校 工學技術硏究所 1997 工學技術論文集 Vol.6 No.1

CRAY 에서 마이크로 태스킹은 다수의 CPU를 이용하여 계산속도를 증가시키는 하나의 방법이다. CRAY-2 에는 4개의 CPU 가 있으므로 적절히 설계된 알고리즘을 가지고 최대 4배의 speedup을 실현할 수 있다. 저자는 이 논문에서 CRAY-2에서 마이크로태스킹 라이브러리를 이용한 선형시스템의 해의 병렬화를 제시한다. 문제의 알고리듬은 Radicati di Brozolo 가 제안한 준비행렬을 이용한 대형이산 행렬의 반복적 해법이다. 우리는 크기가 8192인 행렬에서 4개의 CPU에 마이크로 태스킹을 사용하여 3이상의 speedup을 얻었다. Radicati 의 테크닉을 혼합한 ILU(0) 준비행렬은 4개의 프로세서에서 상당히 높은 speedup을 얻었다. 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 a parallelization of linear system solution un the CRAY-2 with the microtasking library. Our algorithm is the iterative solution of large sparse linear systems with the preconditioner proposed by Radicati di Brozolo. We were able to obtain a speedup of around 3 with 4 processors for a matrix of dimension 8192 with the microtasking. The ILU(0) preconditioner with Radicati's technique seem to realize a reasonably high speedup with 4 processors.