지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술대회자료
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 한국정보과학회 학술발표논문집 한국정보과학회 1995년도 봄 학술발표논문집 제22권 제1호
- 발행연도
- 1995.4
- 수록면
- 895 - 898 (4page)
이용수
초록· 키워드
오류제보하기
최근 병렬 컴퓨터의 하드웨어 구조가, 강력한 여러 프로세서들이 통신 네트워크에 의해 연결되는 경향을 보임에 따라, 병렬 시스템의 네트워크 구조를 프로세서들 사이의 완전 통신 그래프 모양으로 가정하는 경향을 띠게되었다[1,2,3,5,8]. 우편 모델(postal model)[3]은 이러한 특징을 잘 표현하는 모델로 통신 지연(latency) 인자 λ(≥1)를 사용하여 알고리즘의 설계와 분석, 실제 기계에서 알고리즘의 성능평가 모두를 용이하게 한 병렬 모델이다.
본 논문에서는 이러한 우편 모델 상에서 전위합(prefix sums) 문제를 해결하고자 한다. 전위합 문제는 n개의 원소의 집합 S=(x_0, x₁,…,x_n-¹)와 이진 결합 연산자(binary associative operator)* 가 주어질 때, n개의 부분합 S_1=x_0*x₁*… *x₁ (O ≤ i ≤ n-1)를 계산하는 문제이다. 본 논문에서는 이 전위합 문제를 해결하는 두 알고리즘을 제시하는데, 첫째 λ차 트리를 이용한 (4λ-1)[logλn]-1시간의 온라인(on-line) 알고리즘과, 둘째 피보나치트리를 이용한 2fλ(n)-1시간의 오프라인(off-line) 알고리즘이다. 여기서 fλ(n)은 하나의 메세지를 모든 프로세서로 방송(broadcast)하는데 필요한 시간, θ(λlogn/log(λ+1))을 나타내며, 제안한 오프라인 알고리즘은 이 최적 방송시간의 약 2배 정도에 수행되는 효율적인 알고리즘이다.
본 논문에서는 이러한 우편 모델 상에서 전위합(prefix sums) 문제를 해결하고자 한다. 전위합 문제는 n개의 원소의 집합 S=(x_0, x₁,…,x_n-¹)와 이진 결합 연산자(binary associative operator)* 가 주어질 때, n개의 부분합 S_1=x_0*x₁*… *x₁ (O ≤ i ≤ n-1)를 계산하는 문제이다. 본 논문에서는 이 전위합 문제를 해결하는 두 알고리즘을 제시하는데, 첫째 λ차 트리를 이용한 (4λ-1)[logλn]-1시간의 온라인(on-line) 알고리즘과, 둘째 피보나치트리를 이용한 2fλ(n)-1시간의 오프라인(off-line) 알고리즘이다. 여기서 fλ(n)은 하나의 메세지를 모든 프로세서로 방송(broadcast)하는데 필요한 시간, θ(λlogn/log(λ+1))을 나타내며, 제안한 오프라인 알고리즘은 이 최적 방송시간의 약 2배 정도에 수행되는 효율적인 알고리즘이다.
목차
요약
1. 서론
2. 기본알고리즘
3. 온라인 알고리즘
4. 오프라인 알고리즘
5. 결론
참고문헌
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
우편 모델에서 온라인 최적 병렬 방송 알고리즘
정보과학회논문지(A)
1996 .01
-
우편 모델 상에서 합병 문제를 해결하는 효율적인 병렬 알고리즘
한국정보과학회 학술발표논문집
1997 .04
-
왼쪽 한계값을 갖는 정렬 문제에 대한 병렬 알고리즘
한국정보과학회 학술발표논문집
1993 .10
-
병렬 시스템의 최적 프로세서 수 결정
한국정보과학회 학술발표논문집
2002 .04
-
우편 모델 상에서 병렬 합병 알고리즘
한국정보과학회 학술발표논문집
1998 .10
-
[特輯]대규모 병렬 프로세서의 구조
정보과학회지
1987 .03
-
우편 모델 상에서 최적에 가까운 병렬 합병 알고리즘
정보과학회논문지(A)
1997 .12
-
병렬 프로세서 기술 및 동향
[ETRI] 전자통신동향분석
2009 .12
-
대규모 병렬 처리용 노드 구조의 설계
한국정보과학회 학술발표논문집
1994 .04
-
저해상도 병렬처리를 위한 분리형 실행모델
한국정보과학회 학술발표논문집
1996 .10
-
완전 이진 트리와 PARALLEL 정렬 알고리즘
한국정보과학회 학술발표논문집
1988 .04
-
단계별 병렬성 지원을 위한 혼합 병렬 시스템 설계
한국정보과학회 학술발표논문집
1997 .04
-
볼쯔만 기계 시뮬레이터를 위한 병렬 구조
정보과학회논문지(A)
1996 .02
-
구간 그래프와 순열 그래프의 최대 가중치 독립 집합을 찾는 병렬 알고리즘
한국정보과학회 학술발표논문집
1995 .04
-
병렬 부분합 알고리즘에 관한 연구
한국정보과학회 학술발표논문집
1989 .04
-
병렬 화일 시스템을 위한 통신 모듈 설계
한국정보과학회 학술발표논문집
1997 .10
-
완전 그래프를 위한 병렬알고리즘에 대한 연구
한국정보과학회 학술발표논문집
1996 .10
-
병렬형 컴퓨터 구조
전자공학회지
1991 .07
-
MIN-based 다중 처리 시스템을 위한 효율적인 병렬 Branch-and-Bound 알고리즘 설계 및 성능 분석
전기전자학회논문지
1997 .12
-
병렬 알고리즘 사상을 위한 일반화된 체계의 사상 모델
한국정보과학회 학술발표논문집
1995 .04
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017936622