平行程式設計模型 : Distributed Memory Model

前言 & 概述

在前一篇文章中，我們介紹了 Parallel Programming Model 中的第一種模型 —— Shared Memory Model，透過此模型經常會開發出所謂的 Multi-Thread 程式。本篇文章將會介紹第二種模型 —— Distributed Memory Model，並比較其與前者的差別。

什麼是 Distributed Memory Model

在介紹 Shared Memory Model 時，我們將一個 Program 視為 Main Memory 中的一個 Process。然而，實作 Distributed Memory Model 時，通常會開發出所謂的「Multi-Process」程式。在 Multi-Process Program 中，一個 Program 由許多 Process 組成，每一個 Process 之間彼此獨立，擁有自己獨立的 Memory，每一個 Process 也同時被不同的 Core/Processor 執行。

如上圖所示，一個 Program 中包含 3 個 Process，分別在 3 個 Processor 上執行。在我們的電腦中，作業系統 (OS) 會將每一個 Process 視為獨立的個體，彼此互不干預與影響，擁有自己的 Memory。當然，Process A 也不能去存取 Process B 的資料。如此一來，一個 Program 中的 Process 彼此應該如何溝通呢？

Message Passing Interface

在 Distributed Memory Model 中，不同的 Process 可以透過「訊息傳遞」(Message Passing) 的方式溝通。Message Passing 就像是現實生活中的「寄信」，由一個人「Send」一封信，另外一個人則會「Receive」這封信。同樣的，在電腦上由一個 Process「Send」資料，由另外一個 Process「Receive」資料。

我們可以發現，不同於 Shared Memory Model 中「Implicit」的溝通方式，Distibuted Memory Model 使用「Explicit」的溝通方式，也就是在實作上真的會有「Send」與「Receive」的動作。

在電腦上，Message Passing 的實作方式有很多種，為了減輕程式開發者的負擔，通常會使用函式庫所提供的 Messaging Interface Interface (MPI) 實現 Process 之間的溝通。

如上圖所示，透過 MPI 程式開發者不需要煩惱實際 Process 之間是如何溝通的，僅需要明確寫出哪一個 Process Send 什麼資料，並由哪一個 Process Receive。

Distributed Memory Model 範例

了解 Distributed Memory Model 的基本觀念後，我們透過一個非常簡單的範例，了解 Distributed Memory Model 可能遇到的問題。

如上圖所示，我們有一個 Array 包含了兩個元素 A1 與 A2。我們希望將這兩個元素經過 f Function 的運算後再總和起來得到 S。

假設目前電腦中有 2 個 Processor，因此我們可以透過 Distributed Memory Model 的概念，寫出一個 Two-Process Program。由 Processor 1 執行 Process 1 對 A1 進行運算；由 Processor 2 執行 Process 2 對 A2 進行運算。

基於上述的想法，上圖呈現 2 個 Processor 執行任務時的虛擬碼。2 個 Processor 分別運算自己負責的元素，並存於 xlocal 中。再將 xlocal 寄 (send) 給另為一個 Processor，並接收 (receive)。

Deadlock

上圖的虛擬碼看似沒什麼大問題，然而其實存在一個非常嚴重的 Bug，會使得電腦運行該程式時陷入 Deadlock！Deadlock 是學習作業系統 (OS) 時，必學的觀念。簡單來說，Deadlock 就是電腦中存在一組 Process 彼此互相等待，無法繼續執行。

以生活中的例子來比喻的話，Deadlock 就像是「我」和「我的同學」一起上美術課，製作自己的作品。做到一半時，我發現「我」需要「他」手上的剪刀才能繼續做下去；「他」發現「他」需要「我」手上的膠水才能繼續做下去。假設我們兩個都堅持握著自己的資源，而等待對方的資源。最後，我們兩個都會無法繼續製作，而停留在原地。

如果你想更深入的理解作業系統中的 Deadlock，可以參考本篇文章！

同理，在上圖中，Processor 1 執行 send xlocal, proc2 時，會將 xlocal 寄給 Processor 2。此時，必須等到 Processor 2 接收訊息，也就是 Processor 2 執行 receive xremote, proc1 後，Processor 1 才會繼續執行程式碼。

然而，如果兩個 Processor 非常巧合地同時寄送訊息給對方，也就是在同一個時間點，Processor 1 執行 send xlocal, proc2，Processor 2 執行 send xlocal, proc1。如此一來，兩個 Processor 就會一直在等待對方接收 (receive) 訊息，而無法繼續執行後續的程式碼。

解決上述 Deadlock 最簡單的方式，即是確保兩個 Processor 不要同時傳送 (send) 訊息。因此，上圖將 Processor 2 的 send 與 receive 順序對調。

Shared Memory vs Message Passing

在 Shared-Memory Model 中，不同的 Thread 透過 「Shared Memory」互相溝通；在 Distributed-Memory Model 中，不同的 Process 透過「Message Passing」互相溝通。然而，哪一中方法比較好呢？！

It depends ! 兩種方法沒有誰優誰劣，必須視情況而定。以下簡單整理兩種方法的優缺點：

• Shared Memory 優點
  – Implicit Communication : 透過 Shared Memory，兩個 Thread 不需要真的 Send/Receive 資訊，而是在 Shared Memory 中 Load/Store 資訊
  – Low Overhead when Cached : 在有 Cache 的系統中，Processor 存取 Cache 中的資料遠遠快於 Main Memory
• Shared Memory 缺點
  – Require Syncronization Operation : 需要大量的同步機制，確保這個 Thread Load Data 前，另外一個 Thread 已經將最新的 Data Store 進去
  – Hard to Control Data Placement in Caching System : 正是所謂的「成也 Cache，敗也 Cache」！有了 Cache，能夠加速 Data 的讀取速度，但是卻產生另一個問題 —— False Sharing。False Sharing  雖然不會導致程式的結果錯誤，但是卻會大大降低程式的效能，完全犧牲掉平行化帶來的好處。
• Message Passing 的優點
  – Explicit Communication : 有時候透過 Explicit 的方式 (Send/Receive) 溝通，更能避免程式出錯。因此沒有哪一種溝通方式最棒 —— It depends !
  – Easy to Control Data Placement in Caching System
• Message Passing 的缺點
  – High Overhead : 相較於 Shared Memory，Process 之間的 Send/Receive Data 有更高的時間成本
  – Complex to Program

結語

在本篇文章中，我們介紹了第二種 Parallel Programming Model，並比較 Shared Memory 與 Message Passing 兩種 Communication 的優點與缺點。在下一篇文章中，將會介紹第三種 Parallel Programming Model —— Data-Parallel Model