[논문]시스톨릭 구조 기반의 효율적인 양방향 중앙 병렬 가우스 소거법

이연규; 김학원; 이광희; 이충세

시스톨릭 구조 기반의 효율적인 양방향 중앙 병렬 가우스 소거법
An Efficient Central Two-Sided Parallel Gaussian Elimination Method Based on Systolic Structure 원문보기

이연규 (충북대학교 전산학과) , 김학원 (충북대학교 전산학과) , 이광희 (충북대학교 전산학과) , 이충세 (충북대학교 전산학과)

이 논문에서는 새로운 중앙 소거 방식과 행렬 이분법의 개념을 시스톨릭한 구조 위에 결합시켜{{{{ { O}^{ } }}}}({{{{ { N}^{ 3} }}}})의 문제를 해결한다. 새로운 중앙 소거 방식은 주어진 시스톨릭한 구조의 병렬성을 최대한 증가시키는 것을 가능하게 해주며, 행렬 이분법은 기존의 가우스 소거 방식 상에서 나타나는 {{{{ { O}^{ } }}}}({{{{ { N}^{ 2} }}}})의 복잡도를 요구하는 후진 대입을 효과적으로 제거 시켜준다. 새로운 소거 방법은 독립적인 선형방정식으로 이루어진 시스템의 차수를 N이라 할 때 2N(N+1)의 저장 공간과 4N+2log2N-4의 시간 복잡도를 갖는다. 제안 한 새로운 소거 방식은 단순한 구조와 연결 방식을 가진 그물 구조의 시스톨릭 병렬 시스템에 적용되기에 충분히 적합한 단순한 알고리즘을 사용하면서도 이전의 방법과 동일한 구조의 저정공간을 요구하고 동시에 훨씬 우수한 시간 성능을 나타내는 것이 가능하다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

한다. 따라서 이 절에서는 다음절에서 소개 할 새로운 가우스 소거 방법이 최대의 효과를 얻는 것이 가능하게 해줄 수 있는 시스톨릭 시스템의 단위 셀의 구조와 단위 셀 간의 연결 형태를 제안한다. 물론 단위 셀 간의 통신 부하를 줄이기 위해서는 단위 셀 당 많은 저장 공간과 복잡한 연결 구조를 갖는 것이 유리하지만 이것은 곧바로 비용 상승과 구조상의 복잡성을 유발하므로 결국 이 두 가지 요소 사이에 적절한 타협점이 존재한다는 것을 알 수 있다.

가설 설정

·N을 시스템의 차수라고 할 경우 전체 소거 과정은 log₂N의 단계를 거친다.
·단계 s 에서의 차수를 m이라 할 경우 단계 s에서의 총 처리 시간은 2m+1 이 된다.

제안 방법

앞 절에서 제안한 양방향의 행렬 이분법을 수행하는 과정에서 주어진 행렬을 반으로 줄이는데 사용하게 되는 양방향 행렬 이분법에 적절하게 결합될 수 있는 새로운 중앙 소거 방식을 소개한다. 새로운 중앙 소거 방식은 일반적인 소거 방식과는 다르게 피벗이 되는 기준열을 행렬의 중앙에서부터 좌 우측으로 이동시켜 가는 것이다.
이 논문에서 제안하는 단위 셀의 구조는 그림 1의 일반적인 형태의 단위 셀의 구조상의 검은 사각형 즉 저장 요소에 다음과 같은 다섯 가지의 요소에 대한 저장 공간을 필요로 한다. 여기서 P_i,j는 행렬 요소 a_i,j와 일대일로 대응된다.
이 논문에서는 가우스 소거 과정에서 나타나는 순차적인 후진대입을 제거시킬 수 있는 양방향으로 진행되는 행렬 이분법과 새로운 중앙 소거 방식을 결합하여 시스톨릭한 구조의 병렬 프로세싱 시스템에 적용시켰다. 새로운 소거 방법은 병렬적인 행과 열 단위의 단순한 기본 연산만을 수행하였기 때문에 기존의 5N--logN· 4 [1]보다 개선된 4N+21ogN—4의 시간 복잡도와 동일한 수준의 2N(N+1)의 공간을 요구함을 확인할 수 있었다.
이 논문에서는 시스톨릭 병렬 프로세싱 시스템의 병렬성을 최대한 살릴 수 있는 효과적인 수단으로서 새로운 중앙 소거 방식을 제안하고, 또한 가우스 소거 방식 상에 존재하는 O(N²)의 복잡도룰 요구하는 순차적인 후진 대입의 필요성을 제거하는 효율적인 해결책으로서 양방향으로 진행되는 행렬 이분법의 개념을 사용한다[1]. 새로운 소거 방법은 단순한 구조의 연결 형태를 갖는 그룹 구조의 병렬 프로세싱 시스템과 결합되기에 충분히 적합할 정도로 단순한 기본 연산과 적은 저장 공간을 요구하면서도 이전의 연구에서 제시 된 방법들 보다 우수한 성능을 나타냄을 직접 확인할 수 있다.
이 절에서는 앞에서 제안한 중앙 소거 방식을 양방향 행렬 이분법과 결합시킨 효율적인 시스톨릭 알고리즘을 세사한다.

성능/효과

1]. 새로운 소거 방법은 단순한 구조의 연결 형태를 갖는 그룹 구조의 병렬 프로세싱 시스템과 결합되기에 충분히 적합할 정도로 단순한 기본 연산과 적은 저장 공간을 요구하면서도 이전의 연구에서 제시 된 방법들 보다 우수한 성능을 나타냄을 직접 확인할 수 있다.
새로운 소거 방법은 병렬적인 행과 열 단위의 단순한 기본 연산만을 수행하였기 때문에 기존의 5N--logN· 4 [1]보다 개선된 4N+21ogN—4의 시간 복잡도와 동일한 수준의 2N(N+1)의 공간을 요구함을 확인할 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

시스톨릭 구조 기반의 효율적인 양방향 중앙 병렬 가우스 소거법
An Efficient Central Two-Sided Parallel Gaussian Elimination Method Based on Systolic Structure 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

시스톨릭 구조 기반의 효율적인 양방향 중앙 병렬 가우스 소거법 An Efficient Central Two-Sided Parallel Gaussian Elimination Method Based on Systolic Structure 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

시스톨릭 구조 기반의 효율적인 양방향 중앙 병렬 가우스 소거법
An Efficient Central Two-Sided Parallel Gaussian Elimination Method Based on Systolic Structure 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper