지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 1996.1
- 수록면
- 1 - 8 (8page)
이용수
초록· 키워드
오류제보하기
최근 병렬 컴퓨터의 하드웨어 구조가 강력한 여러 프로세서들이 통신 네트워크에 의해 연결되는 경향을 보임에 따라, 병렬 시스템의 네트워크 구조를 프로세서들 사이의 완전 통신 그래프 모양으로 가정하는 경향을 띠게되었다. 우편 모델(postal model)은 이러한 특징을 잘 표현하는 모델로 통신 지연(latency) 인자 λ(≥1)를 사용하여 알고리즘의 설계와 분석, 실제 기계에서 알고리즘의 성능평가 모두를 용이하게 한 병렬 모델이다.
이러한 병렬모델의 특성을 알아보려는 시도에서 본 논문에서는 메세지 방송 문제와 전위합(prefix sums) 문제에 대해서 생각해 본다. 하나의 메세지를 방송하는 문제는 메세지 M을 가지는 프로세서 P_0가 다른 모든 프로세서(P₁, P₂, ..., P_(n-1))로 M을 전송하는 문제이다. Bar-Noy와 Kipnis는 우편모델에서 이 문제를 해결하는 최적 알고리즘을 제안하였는데, 이 알고리즘은 최적 알고리즘이지만 오프라인으로 수행된다는 단점이 있다. 본 논문에서는 이 문제를 해결하기 위한 간단하면서도 최적인 온라인 알고리즘을 제시하고, 또 여기서 사용된 방법을 이용하여 전위합 문제를 최적 시간에 해결하는 알고리즘을 제시한다.
이러한 병렬모델의 특성을 알아보려는 시도에서 본 논문에서는 메세지 방송 문제와 전위합(prefix sums) 문제에 대해서 생각해 본다. 하나의 메세지를 방송하는 문제는 메세지 M을 가지는 프로세서 P_0가 다른 모든 프로세서(P₁, P₂, ..., P_(n-1))로 M을 전송하는 문제이다. Bar-Noy와 Kipnis는 우편모델에서 이 문제를 해결하는 최적 알고리즘을 제안하였는데, 이 알고리즘은 최적 알고리즘이지만 오프라인으로 수행된다는 단점이 있다. 본 논문에서는 이 문제를 해결하기 위한 간단하면서도 최적인 온라인 알고리즘을 제시하고, 또 여기서 사용된 방법을 이용하여 전위합 문제를 최적 시간에 해결하는 알고리즘을 제시한다.
목차
요약
Abstract
1. 서론
2. 온라인 최적 방송 알고리즘
3. 최적 전위합 알고리즘
4. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
우편 모델에서 전위합을 구하는 효율적인 병렬알고리즘
한국정보과학회 학술발표논문집
1995 .04
-
우편 모델 상에서 합병 문제를 해결하는 효율적인 병렬 알고리즘
한국정보과학회 학술발표논문집
1997 .04
-
An Efficient Parallel Algorithm for Merging in the Postal Model
[ETRI] ETRI Journal
1999 .04
-
병렬 시스템의 최적 프로세서 수 결정
한국정보과학회 학술발표논문집
2002 .04
-
볼쯔만 기계 시뮬레이터를 위한 병렬 구조
정보과학회논문지(A)
1996 .02
-
우편 모델 상에서 최적에 가까운 병렬 합병 알고리즘
정보과학회논문지(A)
1997 .12
-
우편 모델 상에서 병렬 합병 알고리즘
한국정보과학회 학술발표논문집
1998 .10
-
MIN-based 다중 처리 시스템을 위한 효율적인 병렬 Branch-and-Bound 알고리즘 설계 및 성능 분석
전기전자학회논문지
1997 .12
-
완전 그래프를 위한 병렬알고리즘에 대한 연구
한국정보과학회 학술발표논문집
1996 .10
-
충돌을 허용하지 않는 최적 정렬 알고리즘
(구)정보과학회논문지
1989 .02
-
Design of Parallel Algorithms for Conventional Matched-Field Processing over Array of DSP Processors
전자공학회논문지-SP
2007 .07
-
유전 알고리즘을 이용한 6자유도 병렬기구의 최적화 설계
제어로봇시스템학회 논문지
2007 .06
-
병렬 처리를 위한 개선된 루프 최적화 알고리즘
(구)정보과학회논문지
1992 .07
-
자기조직화 신경망 모델을 위한 병렬 알고리즘 ( Parallel Algorithm for Self-Organizing Neural Network Model )
대한전자공학회 학술대회
1991 .01
-
복합병렬형 로봇의 최적설계
한국정밀공학회 학술발표대회 논문집
1997 .11
-
최적 스택필터 설계를 위한 고속병렬기법 ( Fast Parallel Algorithm For Optimal Stack Filter Design )
전자공학회논문지-S
1999 .02
-
새주소체계에 따른 우리나라 우편번호체계의 최적설계에 관한 연구
한국 SCM 학회지
2009 .11
-
수식 표현의 트리 생성을 위한 최적 병렬 알고리즘
(구)정보과학회논문지
1990 .08
-
우편주소 정보화 방안 수립에 관한 연구
산업공학 (IE interfaces)
2005 .03
-
메쉬구조 컴퓨터상에서 C-space 를 위한 병렬 알고리즘 ( The Parallel Algorithm for C-Space on Mesh-Connected Computer )
대한전자공학회 학술대회
1993 .01
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017724304