Distributed Java 3 - Message Passing

Distributed Parallelism

在一個data center中的電腦群是一個cluster，把其中所有的節點邏輯上抽象化成單一computation unit（有多核可以做parallelism)，這個computation unit的觀點稱為global view。

所以一個program他的global view是看不到cluster內的節點的，例如一個program中access一個array，programmer不會知道哪些部分的資料是存在哪一個節點的，他邏輯上會認可這個array是跟單一一台電腦上的array沒什麼兩樣。

這樣的abstraction稱為 Single Program Multiple Data。

Message Passing Interface

問題是這些節點實際上在底層要怎麼互相溝通？常用的high level interface稱為MPI，可能長得如下：

rank是每個節點的id, 從0,1, ...
上面這個main program應該是在每個節點去init? 課堂中的summary有講：

"It is common for each node to execute one MPI process, but it is also possible to execute more than MPI process per multicore node so as to improve the utilization of processor cores within the node."

不過至少可以確定每個local view of XL在每個node上可以init出不同的連續整數是沒問題。

Point to point communication in MPI

假設有兩個node (rank0 rank1):

用不管什麼方式（可能是同一台電腦上的bus, 或是不同電腦上的網路線）連結再一起，其中rank0想要傳送字串s給 rank1，對programmer來說，只寫一個program再不同的rank上執行，但是由於每個rank執行的程式碼不同，所以可以用conditional:

Message ordering & Deadlock

message passing因為有dependency，就有race condition或是deadlock的可能性。

例如上面四ranks (nodes)，R0收到A以及R3收到B這兩個事件的順序是不能被保證的。
能夠被保證的順序只有當同一對 sender/receiver，傳送同樣type/tag
為什麼要同樣type/tag? 不知道 XDDD

為什麼會有deadlock? 因為send / receive是blocking operation! 以下圖為例：

如果R0 先執行第一行，但是R1還沒收到就執行R1的第一行，由於send是blocking，R0只能一直等R1收，而R1也只能一直等R0收，就deadlock。

一個解決方法就是其中一個rank調換operation order。
另外一個方法就是如果MPI framework有支援sendreceive() function，則runtime會自己avoid deadlock。

Non-blocking Communications

上面提到send/receive是blocking operation，這不是很好的架構，因為容易浪費時間在等待上：

MPI framework可能提供asynchronous send/receive，可以叫做ISEND / IRECEIVE：

當然還是要提供blocking機智，否則某些operation壹定要等待某些message到來才能執行，叫做WAIT(REQUEST D)。

前面講的deadlock例子也可以用non-blocking MPI來解決。

Collective Communications

這就是一個rank要怎麼broadcast/multicast messages給其他multiple ranks。