[논문]MPI환경에서의 양방향 병렬 탐색의 구현

차광호; 홍정우; 곽재승; 변옥환

MPI환경에서의 양방향 병렬 탐색의 구현
The Implementation of Parallel Bidirectional Search on MPI environment 원문보기

차광호 (한국과학기술정보연구원 슈퍼컴퓨팅센터) , 홍정우 (한국과학기술정보연구원 슈퍼컴퓨팅센터) , 곽재승 (한국과학기술정보연구원 슈퍼컴퓨팅센터) , 변옥환 (한국과학기술정보연구원 슈퍼컴퓨팅센터)

인공 지능 분야 문제의 특성으로 인하여 병렬 처리 기법의 적용이 자주 고려되고 있다. 특히 순차적인 문제 해결 알고리즘이 병렬 처리 개념과 접목되면서 새로운 특징을 갖는 알고리즘으로 발전될 수 있는데 양방향 병렬 탐색을 그 예로 들 수 있으며 특정 슈퍼컴퓨터를 대상으로 한 구현 결과도 보고 된 바 있다. 본 논문에서는 양방향 병렬 탐색 알고리즘을 보다 보편적인 메시지 패싱 인터페이스(MPI)를 이용하여 구현하고 두 종류의 병렬 시스템을 대상으로 테스트함으로서, MPI 환경에서의 양방향 병렬 탐색의 성능을 비교 분석하였다.

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

문제 정의

본 논문에서는 이 양방향 방향 탐색을 보다 보편적인 병렬 프로그래밍 환경인 메시지 패싱 인터페이스 (MPI) 를 이용하여 구현하고, CRAY T3E 와 클러스터 시스템에서 성능을 측정함으로서 양방향 병렬 탐색이 MPI 환경에서 갖는 수행 특성을 조사하였다.

제안 방법

구현된 양방향 병렬 탐색은 두 종류의 병렬 시스템에서 테스트되었는데, KISTI에서 보유하고 있는 128 노드 클러스터 시스템과 CRAY T3E 에서 각각 성능을 측정하였다.
단일 순차 알고리즘과 두 종류의 병렬 알고리즘들의 실행 시간 올 바탕으로 성능 향상비를 구하였다. [그림 6,7은 각 시스템에서의 성능 시스템에서의 성능 향상비를 보여 주고 있다.
알고리즘이 수행하면서 적용한 휴리스틱 함수 역시 성능올 크게 좌우하는 요소이나, 본 논문에서 확인하고자 하는바 는 휴리스틱 알고리즘 간의 성능이므로, 결과 비교에 용이한 수행 시간을 보인, 맨하탄 거리, 를 모든 알고리즘의 휴리스틱 함수로 이용하였다.
양방향 병렬 탐색을 구현하는 과정에서는, 위에서 설명한단 방향 병렬 탐색 올 기본으로 사용하였다. 전체 프로세서를 두 개의 프로세스 그룹으로 나눈 후, 역방향 탐색을 수행하는 프로세스 그룹은 주어진 문제의 목표 상태를 초기 상태로, 초기 상태를 목표 상태로 설정한 뒤 작업을 수행하도록 하였다. 이와 함께 두 프로세서 그룹이 탐색한 상태들 중에 공통된 상태가 있는지를 확인하기 위하여 타 그룹의 프로세서들이 가지고 있는 오프 리스트에서 현재 상태를 검색하는 기능이 추가 되었다.

대상 데이터

성능 측정을 하기 위하여 적용된 문제들은 [그림 5]와 같다. 해를 찾기 위하여 탐색 되어야 하는 트리의 깊이에 따라 문제의 난이도가 결정되는데, 4종류의 문제를 실험에 이용하였다 [2, 3].

이론/모형

양방향 병렬 탐색은 최적치 탐색 알고리즘의 일종인 A* 알고리즘에 기본을 두고 있으며, 본 논문에서 성능을 측정하는데 사용된. 모든 휴리스틱 알고리즘들이 풀고자 하는 문제는 경로 탐색 중 하나인 8 퍼즐 문제로서 초기 상태에서 목표 상태까지의 중간 변화 과정의 최적화를 찾는 문제이다.

성능/효과

기존의 A* 알고리즘은 [그림 1]처럼 현재 상태에 연산을 적용하기에 앞서 이미 탐색된 상태들이 저장되어 있는 클로즈드 리스트를 탐색하는 과정을 거치게 되며 이는 최종 목표 상태에 도달했는지 여부를 판단하는 중요한 과정이 된다. MPI와 같은 분산 메모리 환경 올 고려할 때, 특정 프로세서가 이 클로즈드 리스트를 관리할 경우, 프로세서들 간의 참조 과정으로 인하여 빈번한 메시지 전달 과정이 발생하게 되며, 클로즈드 리스트를 나누어서 관리할 경우에는 확장성에 문제가 있는 것을 발견하였다. 이러한이유로 단방향 병렬 탐색 올 구현하는 과정에서는 [그림 3]과 같이 클로즈드 리스트는 모든 프로세서가 보유하되, 각각의 프로세서가 서로 다른 오픈 리스트를 보유하고 이를 바탕으로 새로운 다음 상태들의 생성 올 동시에 진행하도록 하였다.
두 시스템에서 공통적으로, 문제의 난이도가 어려워질수록 양방향 병렬 탐색의 성능이 우수한 것으로 나타났으며, 프로 세서 수가 증가함에 따라 양방향 병렬 탐색이 갖는 성능 향상비가 감소됨을 발견할 수 있었다. 따라서 문제의 난이도가 높은 경우에는 단방향 탐색보다 양방향 탐색이 효과적임을 알 수 있었다.
두 시스템에서의 성능 변화의 전반적인 추세는 유사하였지만, 성능 향상의 정도가 CRAY T3E 가 더 우수한 것으로 나타났다. 이는 각 프로세스들의 클로즈드 리스트를 업데이트하는 과정에서 프로세서들 간에 집합 통신(Collective Communication)을 수행하는데, CRAY T3E의 프로세서 간 통신 성능이 클러스터 시스템보다 우수하기 때문인 것으로 예상된다.
두 시스템에서 공통적으로, 문제의 난이도가 어려워질수록 양방향 병렬 탐색의 성능이 우수한 것으로 나타났으며, 프로 세서 수가 증가함에 따라 양방향 병렬 탐색이 갖는 성능 향상비가 감소됨을 발견할 수 있었다. 따라서 문제의 난이도가 높은 경우에는 단방향 탐색보다 양방향 탐색이 효과적임을 알 수 있었다.
성능 향상비에서 기종 간에 차이를 가지고는 있으나, 클러스터 시스템에서는 대부분의 경우 양방향 병렬 탐색이 우수한 성능올가지고 있다는 사실을 확인할 수 있었으며, 특히 프로세서 수가 적은 클러스터 시스템에서 난이도가 높은 문제의 풀이를 시도하고자 하는 경우에는 양방향 병렬 탐색이 유용하다는 결론을 내릴 수 있었다.

후속연구

본 논문에서는 MP1-1 을 기준으로 실험을 진행하여, MPI- 2가 가지고 있는 원격 메모리 접근과 같은 기능을 이용하지는 않았으나, 원격 메모리를 이용한 구현과, 집합통신을 이용한 구현간의 성능 비교도 추후 필요할 것으로 여겨진다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

MPI환경에서의 양방향 병렬 탐색의 구현
The Implementation of Parallel Bidirectional Search on MPI environment 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

MPI환경에서의 양방향 병렬 탐색의 구현 The Implementation of Parallel Bidirectional Search on MPI environment 원문보기

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

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

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

MPI환경에서의 양방향 병렬 탐색의 구현
The Implementation of Parallel Bidirectional Search on MPI environment 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper