Reference : Introduction to Parallel Computing, Edition Second by Vipin Kumar et al
Message Passing Cost
- Startup Time (t_s): prepare the message (header, trailer, error correction information), execute the routing algorithm, establish an interface betw local node ane the router. —> Delay is incurred only once for a single msg
- Per-hop Time (t_h): after a msg leaves a node, takes a finite amount of time to reach the next node (=node latency). 어느 채널, 아웃풋 버퍼로 보내야 하는지 라우팅 스위치가 판단하는 동안 대기하는 시간과 직결된다.
- Per-word Transfer Time (t_w): if channel bandwidth is r words per second, t_w = 1 / r to traverse the link.
Store and Forward Routing - 전체 메세지 수신후 저장, 다음 노드로 전송
msg sizeof m, l links, t_h for header, t_w speed.
Total time = t_s + (t_h + t_w * m ) * l = t_s + mlt_w as t_h is comparatively small.
Packet Routing - Modification of SF.
Adv : 통신 자원 활용, 패킷 손실 (오류)로 인한 오버 헤드 감소, 다른 경로 선택 확률, 더 나은 오류 수정 기능.
이로 인해 장거리 네트워크 (인터넷 - 오류율, 홉 수, 그리고 네트워크 상태 변화 변수) 에 쓰임
Total Time = t_s + t_h * l + t_w * m where t_w = t_w1 + t_w2 * (1 + s/r)
각각의 패킷들이 다른 루트를 통해 전송 될수 있고, 잃어버린 패킷들의 재전송 때문에 지역/글로벌 네트워크에 많이 쓰임.
Cut Through Routing
- 모든 패킷이 같은 경로를 사용하도록 해서 라우팅 정보 오버 헤드를 제거
- 시퀀스 내 전달을 강제함으로 시퀀스 정보 제거
- 메세지 레벨 오류 정보 (패킷 레벨 말고)를 연관함으로 오류 검출 및 정정 오버 헤드 감소
- 병렬 시스템 오류율이 낮기 때문에, 값 비싼 오류 수정 체제대신 싼 오류 잠지 메커니즘 사용 가능
메세지를 flow control digits or filts 라는 고정 단위로 나눔 이는 패킷 오버 헤드를 미포함 하기에 패킷보다 작을수 있음
Tracer 가 목적지 노드에 먼저 도착후, 연결을 설정, 플릿이 차례대로 전송 (모두 동일한 경로, 중간에 기다림 없음 따라서 버퍼 미필요)
이 와 같은 특성으로 중간 노드에서 더 적은 memory and memory bandwidth and faster
Total Time = t_s + l * t_h + t_w * m
** 메세지가 작거나, 거리가 가까운 경우, 저장후전송과 컷쓰루 방식의 통신시간은 비슷하다.
제어 회로의 속도는 플릿 속도로 작동해야 하는데, 플릿 크기가 작으면 제어 회로 속도가 빨라지는데, 이는 라우터 설계에 상당한 어려움을 줌
플릿 크기가 크면, 내부 버퍼 크기가 증가하므로, 메세지 전송 대기 시간 (첫 시작노드) 이 늘어남.
요즘 플릿 크기는 4-32 바이트.
Total Time = t_s + l * t_h + t_w * m - 컷 쓰루 라우팅 공식
메세지 전송 비용 최적화를 위해
- Communication in Bulk: 조그만 메세지에 각각 t_s를 주느니, 큰 메세지 하나에 한번 주는것. 왜냐하면 클러스터/메세지 전달 시스템 같은 일반 플랫폼에서 t_s가 t_w 보다 훨씬 커서
- 데이터 볼륨 최소화: t_w로 인한 오버헤드 최소화를 위해, 통신되는 데이터 양을 줄이기
- 데이터 거리 최소화: 메세지가 통과해야 하는 홉 수를 최소화.
첫 1,2번의 경우 쉬우나 통신 노드 거리를 줄이는 (3)은 알고리즘 설계자에게 불필요한 부담을 줌. 왜냐하면
- MPI 에서 프로그래머가 물리적 프로세서에 프로세서들을 맵핑하는것에 권한이 조금 밖에 없음. 가까운 이웃간에 통신은 괜찮을 수 있으나, 전체적인 매핑에 손상을 줄 수 있기 때문
- 대부분의 아키텍처가 2단계 랜덤 라우팅을 이용하는데 (처음 한번 중간 한번). 이는 네트워크의 핫스팟과 부담감 (contention)을 줄여줌. 무작위 라우팅의 홉을 최소화 하면 이득이 없음
- 홉당 시간은 t_s 와 t_w * m 에 비하면 굉장히 작아, 홉당 시간을 무시해도 된다.
따라서 Total Time = t_s + t_w * m 으로 정리될 수 있다. —> 이 식은 혼잡하지 않은 네트워크에만 유효하다.
위 식은 런타임 예측 정확성과 독립적 알고리즘 설계에 중요한 영향을 미친다. 위의 식은 모든 노드간 통신에 같은 시간이 걸림으로, 완전히 연결된 네트워크에 해당함.
따라서 각 아키텍처 알고리즘 설계 하는 대신 비용을 생각한 알고리즘을 병렬 컴퓨터에 설계할 수 있게 한다.
물론 간소화된 공식으로 알고리즘을 설계 하면, 예측 정확도 손실이 발생하나, 홉당 시간이 굉장히 작다는 가정만 따른다면, 그 손실액은 미미하다.
For communication patterns that do not congest the network, the effective bandwidth is identical to the link bandwidth. However, for communication operations that congest the network, the effective bandwidth is the link bandwidth scaled down by the degree of congestion on the most congested link.
네트워크 정체 시키지 않는 대역폭은 링크대역폭. 네트워크 정체 시키는 통신의 경우 유효 대역폭은 가장 정체된 링크의 정체 정도에 따라 축소된 링크 대역폭. 이 값은 구하기 어려울 떄가 있음.
따라서 우리는 하한선을 이용하는데, link bandwidth = p/b (b = bisection width)
Communication Costs in Shared-Address-Space Machines
Cache Coherence에서 비용줄이기가 더 어려운 이유
- 메모리 레이아웃은 보통 시스템에 의해 결정된다. 프로그래머는 특정 데이터 아이템의 위치와, 순열 데이터 구조 최적화에 권한이 적음. 이는 이 공유 주소 공간 아키텍처에서 중요한데 로컬 및 원격 엑세스를 식별하기 어렵기 떄문. 로컬 과 원격 엑세스의 시간이 차이가 나면, 통신 비용은 데이터 레이아웃에 의해 크게 달라지기 때문.
- 유한 캐시 크기로 인한 캐시 스래싱 발생 가능. 사용 가능한 캐쉬보다 필요한 데이터가 클 경우, 특정부분이 덮어 쓰기 되어 여러번 엑세스 될 수 있음. 이 오버헤드로 인한 프로그램 성능이 크게 저하됨. 이 문제를 피하기 위해서는 작업 세트 크기를 최소화 한 실행 스케쥴이 필요. 멀티 프로세서의 경우 페널티가 심각해지는데, 이는 프로세서간 통신과 coherence 작업이 연관되기 때문.
- 무효화 프로토콜과 업데이트 작업은 수량화 하기 어렵다. 업데이트시 발생하는 트래픽의 경우 프로세서마다의 작업에 따라 확연히 달라지는데, 이 동시화된 데이터 갯수와 스케쥴은 프로그래머 권한 밖인 경우가 대부분.
- 공간적 지역성 (Spatial locality) 는 모델링 하기 어렵다. 캐쉬라인은 보통 한 단어(데이터)보다 길기에 여러개를 부르는데, 이에 따른 접근 시간이 단어마다 다르다. 이전에 불려진 데이터가 불려지는 경우 (다른것은 새거) 등은 프로그래머가 최소한의 제어를 가지기 떄문에, 프로그래머가 할 수 있는것은 순열 데이터 구조를 극대화 시켜 공간적 지역성을 최대화 하는것 밖에 없다.
- prefetching 은 데이터 엑세스와 관련된 오버헤드를 줄이는데 중요함. 컴파일러는 미리 로드를 진행할 수 있으며, 만약 자원이 충분할 경우 이에대한 오버헤드를 숨길수 있다 (현재 진행하는 작업을 느리게 하지 않으니, 몰래 미리 스윽 해놓기 때문에 오버헤드가 없는것) 이 와 관련된 사항은, 컴파일러, 레지스터, 캐쉬의 기능이므로 정확한 모델링이 어렵다.
- False Sharing 은 두 프로세서가 각각 사용하는 두 단어가 동일 캐쉬 라인에 있을수 있음 (공유하지 않아도) 이때 일관성 작업과 통신 오버헤드가 발생할수 있는데, 프로그래머는 이를 최소화 하기 위해 데이터 구조를 채우는 수밖에 없다.
- Contention in shared access 는 공유 주소 공간 기계에서 오버헤드를 발생시키는 주요 이유중 하나. 하지만 이는 실행 스케쥴의 기능이므로, 정확한 모델링이 어렵다 (스케줄링 알고리즘 문제가 아니니까). 계산해서 점근 추정값은 가능하나, 이 수치는 의미가 없다.
공유 주소 공간 머신의 모든 비용 모델은 이러한 오버 헤드를 고려해야 함.
Total Time = t_s + t_w * m
유한 캐쉬에서 발생하는 영향은 각 시스템마다의 다양한 캐쉬 사이즈로 인해 다르므로 무시됨
공간적 지역성의 최대화 (캐시 라인 효과)는 명시적으로 미포함
거짓 공유는 데이터 레이아웃과 같이 명령 스케줄의 기능
비용 모델은 공유 데이터 구조가 잘 채워져 있다고 가정하기에, 잘못된 비용 미포함
중복된 통신 및 계산을 설명하지 않음
