초록 close

웜홀 네트웍에서 교착상태의 복구를 기반으로 하는 라우팅 알고리즘은 간단한 하드웨어 구조와 높은 라우팅 적응성으로 인해 관심을 이끌었다. 진보적인 교착상태 복구 방안들은 교착상태에 속한 패킷들을 삭제하는 대신에 소수 전용 리소스들을 통해 전송한다. 교착상태에 속한 패킷은 타임아웃에 의해 선정하는데 다양한 트래픽 형태 및 패킷 길이를 고려하여 가장 바람직한 성능을 가져오는 제한 시간 값을 결정하기는 매우 어려운 일이다. 본질적으로, 타임아웃을 사용하는 현재의 방법들은 네트웍 부하가 심하거나 메시지 길이가 긴 경우에 교착상태의 존재를 잘못 판단할 가능성이 크다. 또한 교착상태가 발생할 경우, 하나 이상의 메시지가 교착상태로 판단되어 복구를 위해 마련된 자원을 과포화시킬 수 있다. 본 논문에서는 타임아웃을 사용하지 않고 보다 정확히 교착상태를 발견하는 방안을 제시한다. 제안한 방안은 교착상태를 잘못 판단하는 확률을 현저히 낮출 수 있다. 또한 순환 구조를 이루는 대기 상태의 메시지들 중에서 하나만을 교착상태라고 선언함으로써 복구에 따른 부담을 감소시킨다.


Deadlock recovery-based routing algorithms in wormhole networks have gained attraction due to low hardware complexity and high routing adaptability. Progressive deadlock recovery techniques require a few dedicated resources to transmit deadlocked packets rather than killing them. Selection of deadlocked packets is primarily based on time-out value which should be carefully determined considering various traffic patterns or packet length. By its nature, current techniques using time-out accompany unignorable number of false deadlock detections especially in a heavy-loaded network or with long packet size. Moreover, when a deadlock occurs, more than one packet may be marked as deadlocked, which saturate the resources allocated for recovery. This paper proposes more accurate deadlock detection scheme which does not make use of time-out to declare deadlock. The proposed scheme reduces the probability to detect false deadlocks considerably. Furthermore, a single message is selected as deadlocked for each cycle of blocked messages, thereby eliminating recovery overheads.