1. Introduction

이장에서는 멀티 컴퓨터 시스템에서 switched networks의 스케쥴링과 흐름제어에 대하여 살펴 본다.

패킷 스위치 네트워크와 같이 parallel한 머신들간의 프로세스를 위해 멀티홉 네트워크가 사용된다. 또한, full-duplex 링크로 연결된 crossbar 스위치로 구성된다.
패킷 스위치 네트워크와 다른점은, 위의 네트워크들은 간단한 라우팅과 흐름제어방식을 사용한다. 이들은 wormhole routing이라 불리운다.

1.1 Wormhole networks

원홈 네트워크란 웜홀 라우팅 프로토콜을 사용하는 네트워크를 의미한다.
메시지들은 매우 작은 flits라는 흐름제어 유닛으로 나누어 진다.
스위치들은 하나의 인풋 링크당 오직 하나의 flit만 저장할수 있는 버퍼공간을 가지고 있다.

1.1.1 Routing and Transmission

각 time step동안 오직 하나의 flit만이 링크를 사용할수 있다. 다른 메시지는 대기 하여야만 하므로 전체 전송시 지연이 발생한다.
Flits of a single packet may occupy multiple consecutive routers and links, like a worm [wikipedia]

1.1.2 Path Selection and Scheduling

확장성을 의하여 경로 설정을 의한 알고리즘은 간단하여야한다.
예를 들어 이차원 메쉬네트워크에서는 각 스위치들은 4개의 이웃 스위치들과 연결되게 된다. 이때 유니 캐스트 메시지는 one-bend path를 이용하는 것이 일반적이다.
두 프로세서 사이의 one-bend path는 segment of column link와 segment of row link로 이루어져 있다.
만일 모든 메시지의 경로가 가로로 먼저 가고 후에 세로로 가게 되어 있다면 데드락은 발생하지 않을 것이다.

일반적으로 논-리얼타임 메시지의 스케쥴링 알고리즘은 메시지에 순위(Priority)를 정하지 않는다.
논-리얼타임 메시지의 스케쥴링은 두가지로 분류 될수 있다.

• Greedy : 발신자가 준비가 되면 각 메시지는 Deadlock-free 경로를 따라서 전송된다.
  
• Throttling : 메시지는 발신처에서 대기 하게 된다. 패킷 스위칭 네트워크의 traffic shapping과 비슷한 목적. 최악의 지연을 막기 위함
  

논-리얼타일 메시지의 원홀 라우팅에서 가장 우선시 되는것은 평균 메시지 지연율이다.

1.2 Priority Driven Flow Control

리얼타일 메시지의 스케쥴링 알고리즘은 우선순위 기반이다.
이를 위해 각 스위치들은 하나 이상의 flit를 저장할수 있는 버퍼를 가지고 있다.
메시지의 발신-목적지간의 연결도 설정된다.
이러한 flit-buffered networks는 패킷 스위치 네트워크와 비슷한 점이 많다.
다른점은 flit이 패킷 보다 작다는거 이외에도 각 스위치에 한 연결당 하나의 flit을 저장할 버퍼만 가지고 있다는 점도 있다.
또 다른점은, 패킷 스위칭에서는 흐름제어등의 목적으로 중간 스위치에서 패킷 드랍이 발생 할수 있지만. 웜홀 네트워크에서는 절대 패킷 드랍을 허용하지 않는다.
웜홀 네트워크에서는 flit는 포워딩 될수 없을때는 스위치에서 대기한다. 이후의 flit들은 upstream 스위치에서 대기 하게 된다.
문제는 이러한 대기 시간을 어떻게 줄일수 있나 하는것이다.

1.2.1 Assumptions and Rationale of the PPCS-RT Scheme

리얼타임 흐름제어 스킴의 예처럼 Preemptive circuit switching(PPCS-RT) 스킴을 적용 시켜 보려한다.
위 스킴에서는 리얼타임 메시지는 주기성을 가지고 있다고 가정한다.
암묵적인 가정으로는 메시지 인스턴스의 길이는 네트워크의 가장긴 경로의 의 전송 시간 보다도 길어야 한다. (시간과 메시지 길이의 연관성???)-위 제안 방식은 작은 메시지에는 낮은 성능 보임

1.2.2 Path Establishment and Data Delivery

PPCS-RT의 스킴에 따르면 각 메시지의 경로 설정이 먼저 이루어진후에 데이터 전송을 실시 한다.
이러한 메커니즘은 flit의 버퍼를 먼저 할당함으로써 메시지 손실을 최소화 하게 된다.


Successful Path Establishment : 헤더 설정 단계에서 flit의 헤더부분만 먼저 전송된다. Request 역할을 수행

작성 : 20080625 by 임헌정
참고 : embeded testing
http://www.4ellene,net