http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 김숙연(Sook-Yean Kim) (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
완전이진트리와 트리메쉬의 재귀원형군 G(2^m,4)에 대한 임베딩
박상민(Sang-Min Park),김숙연(Sook-Yean Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.4
주어진 병렬컴퓨터에서 이용가능한 프로세서의 갯수보다 더 많은 프로세서를 요구하는 문제들은 그래프 간의 다대일 임베딩을 적용하여 풀 수 있다. 본 논문에서는 완전이진트리를 병렬컴퓨터 구조로서 새로이 제안된 재귀원형군[2] 중 G(2^m,4)에 다대일 임베딩하는 방법을 제시하고, 그러한 임베딩을 이용하여 트리메쉬도 재귀원형군 G(2^m,4)에 다대일 임베딩한다. 완전이진트리는 분할정복이나 분기제한 탐색 등의 주요 알고리즘들의 기본 구조를 이루며 트리메쉬는 노드 갯수의 로그 또는 로그 제곱 시간만에 수행 가능한 효율적인 병렬 알고리즘들을 제공하므로, 이러한 임베딩들은 재귀원형군의 유용성을 증대시켜 준다. 우리는 임베딩에 있어서 프로세서의 이용도를 최대로 하거나, 프로세서 간 통신의 지연을 최소로 하는 전략을 취한다. 즉 부하율을 최적으로 하면서 연장율도 최적에 가까운 임베딩과 연장율을 최적으로 하면서 부하율도 최적에 가까운 임베딩을 구한다. 또한 완전이진트리의 임베딩에 있어서는 트리의 같은 레벨 노드들이 재귀원형군에 골고루 분산됨은 물론 밀집율이 최소가 되도록 한다. An embedding of arbitrarily large graphs into smaller graphs has important applications to the problems which require more processors than is available in a given parallel architecture. This paper describes methods for embedding a large complete binary tree into the small recursive circulant G(2^m,4) that was recently proposed in [2] as a versatile interconnection network. Using this embedding, we also embed a large mesh of trees into the small recursive circulant G(2^m,4). These embeddings enhance the capabilities of the recursive circulants because complete binary tree is a basic structure for many important algorithms such as divide-and-conquer and branch-and-bound search and mesh of trees enables so fast parallel computations that can be performed in logarithmic or log-squared time. We design these embeddings with the main focus on maximizing processor utilization or minimizing communication delays. So we get two embedding strategies: one with the optimal load factor and the near optimal dilation, and the other with the optimal dilation and the near optimal load factor. Furthermore, in embedding the complete binary tree we evenly distribute the same level nodes to the nodes of the recursive circulants and make the congestion the minimum.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
