초록 close

하이퍼큐브 컴퓨터는 정규적 구조(regular structure)와 짧은 지름(short diameter) 등 병렬 처리에 적합한 특징을 지니고 있기 때문에 이에 대해 많은 연구가 있어 왔다. 하이퍼큐브의 성능을 좌우하는 중요한 요소 중 하나는 프로세서간의 통신인데, 이 중 다중전송(multicast)은 하나의 전송데이터의 복제, 신호처리 등과 같은 다양한 응용 프로그램에서 이용되는 중요한 통신패턴이다. 병렬 컴퓨터에서 프로세서의 수가 증가함에 따라 구성요소들이 오류가 날 확률도 높아졌다. 이러한 이유로, 오류 난 구성요소들이 있어도 다중 전송이 가능하게 효율적으로 설계하는 것이 중요하다. 이러한 오류 허용 라우팅과 다중 전송은 오류 정보에 따라, 국지적 오류 정보를 바탕으로 하는 전략, 전역적 오류 정보를 바탕으로 하는 전략, 제한된 오류 정보를 바탕으로 하는 전략 등이 있는데, 이 중에서 후자가 정보 수집비용이 적으면서도 좋은 성능을 보인다. 본 논문에서는 최근에 제안된 완전 도달성 정보와 새로 추가한 국지적 정보를 이용해서 라우팅 알고리즘을 제안하고, 이것을 바탕으로 다중 전송 성공률이 높은 새로운 다중 전송 알고리즘을 제안한다. 제안 기법은 완전 도달성 정보와 국지적 정보를 이용하여 우회하는 경우와 다중전송 실패하는 경우를 줄임으로써, 기존의 기법보다 통신량의 차이는 거의 없으면서도 다중전송 성공률을 향상시킬 수 있음을 시뮬레이션을 통해 검증하였다.


Hypercube multicomputers have been drawing considerable attention from many researchers due to their regular structure and short diameter. One of keys to the performance of Hypercube is the efficiency of communication among processors. Among several communication patterns, multicast is important, which is found in a variety of applications as data replication and signal processing. As the number of processors increases, the probability of occurrences of fault components also increases. So it would be desirable to design an efficient scheme that multicasts messages in the presence of faulty component. In fault-tolerant routing and mulicast, there are local information based scheme, global information based scheme and limited information based scheme in terms of information. In general, limited information is easy to obtain and maintain by compressing information in a concise format. In this paper, we propose a new routing scheme and a new multicast scheme using recently proposed fully reachability information scheme and new local information scheme. The proposed mulicast scheme increases multicast success possibility and reduce deroute cases. Experiments show that multicast success possibility can increase at least 15% compared to previous method.