Bài giảng Tính toán lưới - Bài 5: Truyền thông cộng tác

Truyền thông cộng tác

(Collective communication)

Center of High Performance Computing

Hà nội, 6/2008

Hanoi University of Technology

{hpcc@mail.hut.edu.vn}

Đại học Bách khoa Hà Nội

Nội dung



Truyền thông kết hợp kiểu nhiều-một và truyền

thông quảng bá kiểu một-nhiều



Truyền thông kết hợp/quảng bá kiểu Nhiều-Nhiều

Phép toán All-Reduce và Prefix-Sum

Phép toán Scatter và Gather

Truyền thông Nhiều-Nhiều đặc biệt

Phép dịch vòng

Cải tiến tốc độ của một số phép toán truyền thông

Một số định tuyến truyền thông cộng tác trong MPI

High Performance Computing Center - HUT

2

Truyền thông kết hợp kiểu nhiều-một/ truyền thông quảng

bá kiểu một-nhiều



Truyền thông kết hợp nhiều-một/truyền thông quảng

bá một-nhiều tạo thành một cặp truyền thông.

Truyền thông quảng bá một-nhiều

0

1

p-

1

0

1

p-

1

Truyền thông kết hợp nhiều-một

Được dùng trong nhiều giải thuật quan trọng như: nhân ma trận-vector, phép

khử Gause, tìm đường đi ngắn nhất, nhân vector.

High Performance Computing Center - HUT

3

Topology cho truyền thông quảng bá một-nhiều



Một cách tự nhiên, ta thường tiến hành truyền thông

quảng bá một-nhiều bằng cách gửi tuần tự (p-1)

thông điệp từ nguồn tới (p-1) đích.

Tuy nhiên, cách trên là không hiệu quả:



Tiến trình nguồn bị hiện tượng thắt cổ chai



Giảm hiệu suất mạng truyền thông: tại một thời điểm chỉ có

một cặp nút hoạt động.



Xét truyền thông quảng bá một-nhiều trong các

topology khác nhau:



Topology vòng/ mảng tuyến tính



Topology lưới



Topology siêu lập phương

High Performance Computing Center - HUT

4

Ring or Linear Array Topology



Sử dụng kỹ thuật Nhân đôi đệ qui (recursive

doubling) như sau:



Tiến trình nguồn gửi một thông điệp đến một tiến trình j bất

kỳ



Sau khi kết thúc, hai tiến trình có thể đồng thời gửi thông

điệp cho các tiến trình khác đang đợi



Quá trình tiếp tục cho đến khi toàn bộ tiến trình nhận được

dữ liệu



Dữ liệu có thể được quảng bá chỉ trong log(p) bước

High Performance Computing Center - HUT

5

Truyền thông quảng bá một-nhiều trên vòng 8 nút



Trong mỗi bước, chọn đích cẩn thận, đích ảnh hưởng

đến hiệu năng.

Thông điệp đầu tiên gửi từ nút 0 cho nút xa nhất với

nó (nút 4)

Trong bước 2: khoảng cách bị giảm một nửa

High Performance Computing Center - HUT

6

Truyền thông kết hợp nhiều-một trên vòng 8 nút



Đơn giản, ta đảo ngược hướng và chuỗi truyền thông.

Đầu tiên, các nút lẻ gửi dữ liệu sang nút chẵn ngay trước

nó. Nội dung kết hợp vào nút chẵn



Còn lại 4 nút: 0,2,4,6

Nút 0 + nút 2 = nút 0; nút 4 + nút 6 = nút 4;

Nút 4 + nút 0 = nút 0;

High Performance Computing Center - HUT

7

Ví dụ nhân ma trận-vector



Mỗi dòng của ma trận cần phải

nhân với vector

Bước1: Truyền thông quảng bá

một-nhiều:



Mỗi phần tử của vector là một nguồn



Quảng bá đến cột tương ứng trong ma

trận



Mỗi cột là một mảng tuyến tính n phần t



Bước 2: Với mỗi tiến trình



Nhân phân tử của ma trận với phẩn tử

vừa nhận được

Bước 3: Tiến hành truyền thông

kết hợp nhiều-một:



Trên mỗi dòng của ma trận tiến trình



Tiến trình đầu tiên của ma trận là đích

High Performance Computing Center - HUT

8

Topology lưới



Xét lưới vuông có p nút. Mỗi dòng/cột là một mảng

tuyến tính p^1/2phần tử. Từ lưới này có thể mở rộng

cho các lưới khác.

Toán hạng truyền thông tiến hành theo 2 pha:



Pha 1: Tiến hành trên một hoặc nhiều dòng. Mỗi dòng là một

mảng tuyến tính.



Pha 2: Tiến hành như pha 1, nhưng trên các cột

High Performance Computing Center - HUT

9

Truyền thông quảng bá một-nhiều trên lưới vuông

16 nút



Pha 1: truyền thông quảng bá

một-nhiều từ nguồn đến (p^1/2–

1) nút cùng hàng



Bước 1, 2



Sau khi các nút trong hàng đã

có dữ liệu, tiếp tục bước 2

Nguồn

Pha 2: truyền thông quảng bá

một-nhiều cho các cột tương

ứng



Bước 3, 4

High Performance Computing Center - HUT

10

Topology siêu lập phương

Topology siêu lập phương 2^dnút được coi như một

lưới d chiều, trong đó mỗi chiều gồm 2 nút.



Giải thuật lưới mở rộng cho topology siêu lập phương

bằng cách thực hiện trong d bước, hay thực hiện trên

từng chiều của lưới.

High Performance Computing Center - HUT

11

Truyền thông quảng bá một-nhiều trên siêu lập

phương 8 nút

Siêu lập phương 2³chiều



Coi như lưới 3 chiều, mỗi

chiều 2 nút



Nút 0 là nguồn

Chiều thể hiện bằng bit

có ý nghĩa nhất trong

biểu diễn nhị phân của

tên nút



Bắt đầu từ chiều lớn nhất

Kết quả không phụ thuộc

việc chọn chiều truyền

thông.

High Performance Computing Center - HUT

12

Phân tích chi phí truyền thông



Giả sử có p tiến trình tham gia quá trình truyền thông

Dữ liệu quảng bá hoặc kết hợp gồm m từ (word)

Các thủ tục truyền thông quảng bá một nhiều/kết hợp

nhiều-một bao gồm log(p) lần truyền thông điệp đơn



Thời gian để một truyền thông điệp đơn là: (t_s+t_wm)



T_s: thời gian khởi tạo thông điệp



T_w: thời gian truyền một từ (word)



Tổng thời gian truyền thông:

(t_s+t_wm)log(p)

High Performance Computing Center - HUT

13

Truyền thông quảng bá/kết hợp kiểu Nhiều-Nhiều



Truyền thông quảng bá nhiều-nhiều và truyền thông

kết hợp nhiều nhiều tạo thành một cặp truyền thông.

High Performance Computing Center - HUT

14

Topology tuyến tính



Các tiến trình liên tục truyền thông đồng thời cho

đến khi toàn bộ quá trình truyền thông kết thúc.

Đầu tiên, mỗi nút gửi dữ liệu của nó cho nút hàng

xóm

Các bước tiếp theo, mỗi nút chuyển tiếp dữ liệu nó

nhận được từ nút hàng xóm trong bước trước đến

một nút hàng xóm khác.

High Performance Computing Center - HUT

15

Truyền thông quảng bá nhiều-nhiều trên vòng 8 nút

Cách đánh nhãn:



2(7) nằm giữa nút 0 và

nút 1: trong bước thứ 2,

nút 0 đã nhận dữ liệu

của nút 7 từ bước trước



(0,7) nằm cạnh nút 0:

Gồm nhãn của các nút

mà nút 0 đã nhận trong

các bước trước đó.

High Performance Computing Center - HUT

16

Giải thuật thông điệp quảng bá nhiều-nhiều trên vòng p

nút

High Performance Computing Center - HUT

17

Giải thuật thông điệp kết hợp nhiều-nhiều trên vòng p nút

High Performance Computing Center - HUT

18

Topology lưới

Xét lưới 2 chiều, gồm p nút, mỗi chiều gồm p^1/2nút.



Giải thuật tiến hành dựa trên giải thuật cho topology

tuyến tính, gồm 2 pha:



Pha 1: áp dụng giải thuật tuyến tính cho từng dòng.



Pha 2: áp dụng giải thuật tuyến tính cho từng cột.

High Performance Computing Center - HUT

19

Giải thuật thông điệp quảng bá nhiều-nhiều trên

lưới p nút

High Performance Computing Center - HUT

20

Bài giảng Tính toán lưới - Bài 5: Truyền thông cộng tác - Nguyễn Hữu Đức