用 MPI 實作高效能分散式程式

COMP90025 是墨大的平行與多核心運算（Parallel and Multicore Computing）。這門課有兩份大型作業，合起來正好是一個簡單的平行拼字檢查器。第一份作業用 OpenMP，從文件裡收集不重複的單字；第二份則換成 MPI，把這些單字拿去和字典比對，看看哪些拼錯了，又該改成什麼。

這篇是在第二份作業完成後寫的，所以文中的程式碼和資料都是最後繳交的版本，程式碼放在 xxxbrian/mpi-spell-checker。

題目

程式的用法很簡單。

./spellcheck dictionary.txt word_list.txt

dictionary.txt 是排好序的字典，word_list.txt 是要檢查的單字。對單字清單裡的每個詞，如果它不在字典裡，就要產生所有可能的候選詞，也就是替換一個字元、刪除一個字元，或插入一個字元。這些新詞裡，凡是出現在字典中的，都是可能的正確拼法。另外還有一條大小寫規則：一個詞的首字母轉成小寫後，如果在字典裡，也算是符合。

輸出中每個拼錯的詞占一行，後面接著候選詞，像這樣。

appel:  appeal apple rappel
stap:  sap snap stab step stop strap tap

各行依候選詞數量由少到多排序，數量相同時，再按字典序排列。

題目還加了一個限制：每個行程只能保留字典的一部分，不能各自存一整份。課程提供了一份單執行緒的參考實作，使用 BK-tree，而我們的程式則要放到學校的 HPC 叢集 Spartan 上執行。成績分為程式碼和報告兩部分，因為報告占分比較高，實驗和分析也不能馬虎。

先換一個演算法

動手之前，我先跑了一遍參考實作。它用 BK-tree 在字典裡找編輯距離不超過 1 的詞。最大的一組資料有 62 萬多個字典詞、65 萬多個待檢查單字，結果要跑大約 32 分鐘。

我的做法簡單得多。既然編輯距離固定是 1，就直接產生所有候選詞，再到雜湊表裡逐一查詢。產生候選詞的程式碼並不複雜。

std::vector<std::string> GenerateEditDistance1Candidates(const std::string& word) {
  std::vector<std::string> out;
  const std::string alphabet = "abcdefghijklmnopqrstuvwxyz"
                               "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                               "0123456789";

  for (size_t i = 0; i < word.size(); ++i)  // 删除
    out.push_back(word.substr(0, i) + word.substr(i + 1));

  for (size_t i = 0; i < word.size(); ++i)  // 替换
    for (char c : alphabet)
      if (c != word[i]) {
        std::string s = word;
        s[i] = c;
        out.push_back(s);
      }

  for (size_t i = 0; i <= word.size(); ++i)  // 插入
    for (char c : alphabet)
      out.push_back(word.substr(0, i) + c + word.substr(i));

  return out;
}

長度為 L 的詞會產生大約 124 × L 個候選詞，所以八九個字母的詞，候選數也就是一千左右。這個數量對雜湊表來說完全不算什麼，單一行程跑完只要 20 秒左右，其中 19 秒花在產生候選詞和查詢上。

這組資料一共有 30627 個詞拼錯，每個詞有一千多個候選詞，加起來要查三千多萬次。

所以，快了差不多一百倍的這一步，其實和平行化無關，只是換了一個演算法。剩下的問題就是，怎麼把這 20 秒分給多個行程。

最早的版本

最早的版本寫得很直接，目標就是先讓它跑起來。

每個行程各自讀取字典，再依雜湊值挑出屬於自己的分片。要判斷一個詞是否在字典裡，就對每個詞做一次 MPI_Allreduce，讓所有行程查詢自己的分片，再把結果做邏輯或運算。

for (size_t i = 0; i < word_list.size(); ++i) {
  bool local_hit = local_dict.Contains(word_list[i]);
  bool global_hit = false;
  MPI_Allreduce(&local_hit, &global_hit, 1, MPI_C_BOOL, MPI_LOR, MPI_COMM_WORLD);
  in_dict[i] = global_hit;
}

驗證候選詞也是類似的想法：把候選詞送給每個行程，各自查詢，再把命中的結果傳回來。傳送和接收都是阻塞式的。

這個思路沒問題，但缺點也很明顯。單字清單有 65 萬個詞，就表示要做 65 萬次集合通訊。每個候選詞都要送給所有行程，資料量也隨之增加。更麻煩的是，阻塞式傳送和接收可能造成死結：兩個行程同時傳送一大塊資料給對方，誰都傳不出去，程式就卡住了。

死結是最先處理的問題。一開始，我只是把交換改成 MPI_Sendrecv，後來乾脆把整個驗證流程改成請求與回應。等待回覆時不能什麼都不做，因為對方可能也在等我，所以每次迴圈都用 MPI_Iprobe 看看有沒有其他行程送來的請求，有的話就順手處理。

std::vector<int> WaitForResponse(int target, const DistributedDict& dict) {
  while (true) {
    DrainIncomingRequests(dict);  // 等回复的时候，也在帮别人查
    int flag = 0;
    MPI_Iprobe(target, kResponseHeader, MPI_COMM_WORLD, &flag, MPI_STATUS_IGNORE);
    if (flag)
      return ReceiveResponse(target);
  }
}

這樣一來，等待回覆時仍然會處理其他行程的請求，避免大家只等回覆、卻不回答請求的僵局。

接著是讀檔問題。既然題目要求分散式字典，我就改用 MPI-IO，讓每個行程只讀自己負責的區段。不過檔案是按位元組切分，切點很可能落在單字中間，因此起點和終點都要往後移到下一個換行，確保每個詞只屬於一個行程。

MPI_Offset chunk = file_size / world_size;
MPI_Offset start = rank * chunk;
MPI_Offset end = (rank == world_size - 1) ? file_size : (rank + 1) * chunk;

if (rank > 0)              start = SkipToNextLine(fh, start);
if (rank < world_size - 1) end = SkipToNextLine(fh, end);

MPI_File_read_at(fh, start, buffer, end - start, MPI_CHAR, MPI_STATUS_IGNORE);

上面是示意程式碼，省略了緩衝區配置、EOF 和大檔案計數處理。實際尋找行邊界時，是用 MPI_File_read 逐位元組往後讀，直到遇到換行。

字典怎麼分

最後的版本裡，每個詞都有一個負責的行程，也就是把這個詞的雜湊值對行程數取模得到的行程。字典中的詞會送到各自負責的行程，再存進該行程的雜湊表裡。

這裡有個小細節。因為首字母大小寫的規則，Apple 和 apple 必須由同一個行程處理。因此計算雜湊值之前，我會先把首字母轉成小寫，讓兩種寫法都落到同一個行程。

int GetOwnerRank(const std::string& word, int world_size) {
  std::string key = word;
  if (!key.empty())
    key[0] = std::tolower(static_cast<unsigned char>(key[0]));  // 首字母统一转小写
  return std::hash<std::string>{}(key) % world_size;
}

上面的程式碼只展示歸屬規則，報告中的實作使用 FNV-1a 計算雜湊值。

同樣的規則也適用於單字清單。負責某個詞的行程，既要判斷它是否在字典裡，也要在拼錯時產生候選詞。每個行程都有一份單字清單，按索引輪流負責其中一部分，再把詞送到對應的負責行程查詢。因為查詢者和之後需要結果的是同一個行程，結果就不必再廣播。順帶一提，原本那 65 萬次 Allreduce 在這裡變成了一次 Alltoallv。

候選詞怎麼查

負責的行程拿到拼錯的詞後，就會產生候選詞，再查詢它們是否在字典裡。不過候選詞不一定由自己負責；如果在本地，直接查雜湊表就行，如果在其他行程，就得送出請求。

這裡的請求數量其實很驚人。64 個行程時，三千六百多萬個候選詞幾乎都由其他行程負責。但這些候選詞絕大部分根本不是詞，傳過去再傳回來，完全是白費工夫。

於是我替每個行程加了一個 Bloom filter。各行程把自己那份字典放進 Bloom filter，再用 MPI_Allgather 交換所有行程的過濾器，讓每個行程都持有全體的過濾器。送出請求前先在本地查一次；過濾器說不存在，就一定不存在，這個候選詞也就不必傳送。

for (const std::string& cand : candidates) {
  int owner = GetOwnerRank(cand, world_size);
  if (owner == rank) {
    if (local_dict.Contains(cand)) verified.insert(cand);   // 在本地，直接查
  } else if (MayContain(bloom_of[owner], cand)) {
    remote[owner].push_back(cand);                          // 过滤器说可能在，才发出去
  }                                                         // 说不在的，直接丢掉
}

for (int owner = 0; owner < world_size; ++owner) {
  if (remote[owner].empty()) continue;
  SendCandidateBatch(owner, word_idx, remote[owner]);
  for (int i : WaitForResponse(owner, local_dict))
    verified.insert(remote[owner][i]);
}

每個行程的過濾器位元數是字典總詞數的 12 倍，也就是 750 萬位元，約 940KB，使用 3 個雜湊函式。64 個行程時，每個行程要存 64 份，合計大約 60MB。

效果很明顯：三千六百多萬個候選詞中，約 99.7% 在本地就被擋下，最後只有 93897 個真的送了出去。我也關掉 Bloom filter 做比較：64 個行程時，候選階段需要 0.93 秒，開啟後則是 0.31 秒。

整個流程串起來，大概是這樣。

實驗怎麼做

參考實作附了一個簡單測試，但要分析效能還不夠，所以我另外寫了 Python 指令稿 batch_srun.py，用來批次執行。

程式會記錄每個階段的耗時，再用 MPI_Reduce 彙整出平均值、最小值和最大值，印到標準輸出。例如單一行程的結果如下。

[MPI][timing] dict_build avg=0.339734s min=0.339734s max=0.339734s
[MPI][timing] candidate_phase avg=19.1703s min=19.1703s max=19.1703s
[MPI][timing] total_mpi avg=19.9893s min=19.9893s max=19.9893s

指令稿用 srun 啟動程式，再以正規表示式擷取這些數字，逐行寫入 CSV。

cmd = ["srun", "-n", str(parallel), "--cpus-per-task=1", "build/spellcheck", dict_path, words_path]
proc = subprocess.run(cmd, text=True, capture_output=True)

RE_TIMING = re.compile(r"^\[MPI\]\[timing\]\s+([a-zA-Z0-9_]+)\s+avg=([0-9.]+)s\s+min=([0-9.]+)s\s+max=([0-9.]+)s")

每次執行完，指令稿還會把輸出檔的 MD5 與事先記錄的正確結果比對，不一致就直接報錯。因此表裡每一筆效能資料，都是在結果正確的前提下量到的。

資料共有五組，分別是字典與單字清單各 1 萬或 10 萬個詞的不同搭配，再加上最大的一組。每組都從 1 個行程跑到 64 個行程，共 320 次，所有行程都在 Spartan 的同一個 sapphire 節點上。這裡的資料按 MPI 行程分配，沒有測試跨運算節點網路下的擴充性。

不過每個點只跑了一次，所以曲線難免有些起伏。例如 12 個行程的那次，就比相鄰的 11 個和 13 個慢了一截。

結果

下面是最大的一組資料：62 萬個字典詞、65 萬個待檢查單字，開啟 Bloom filter。總耗時由外部指令稿量測，內部計時採用程式輸出的 total_mpi。兩者的差額還包括啟動，以及未納入這個計時區間的 I/O 等開銷。

候選階段的擴充性非常好，從 19 秒降到 0.31 秒，64 個行程大約快了 62 倍。但整個程式沒有這麼快：64 個行程的總耗時是 1.88 秒，只比單一行程快了 10.9 倍。

問題在其他地方。候選階段變短後，原本不起眼的部分，突然就占了很大的比例。

• 每個行程都要自行解析一遍單字清單，這一步一直在 0.09 秒左右，行程再多也不會減少。
• 建立字典時，先讀檔，再把詞送到負責的行程。行程數從 1 增加到 8 時，確實從 0.34 秒縮短到 0.09 秒；但再增加就開始上升，64 個行程時變成 0.51 秒。畢竟行程愈多，各自讀取的區塊愈小，訊息數量卻隨行程數的平方成長。
• 內部計時區間以外的啟動和 I/O 等開銷，也反映在總耗時比內部計時多出的約 0.8 秒裡。

所以到了 64 個行程，候選階段占內部計時不到三成，建立字典反而占了將近一半。

這樣就不難解釋曲線的形狀。大約超過 32 個行程後，曲線基本上就平了，總耗時落在 1.3 到 2 秒之間。最快的一次是 38 個行程的 1.35 秒，大約快了 15 倍；再增加到 64 個行程，反而比 32 個行程稍慢。

轉送請求中實際命中的比例，也隨行程數改變。因為每個行程的過濾器大小固定，行程少時，各自的分片較大，過濾器也較滿，因此誤判更多。2 個行程時，轉送的候選詞只有 19% 真的在字典中；8 個行程是 88%，16 個行程是 98%，64 個行程則達到 99.96%。

最後再和最早的 BK-tree 比較：32 分鐘縮短到兩秒內，其中約一百倍來自更換演算法，其餘十到十五倍則來自平行化。

報告

作業最後還有一份完整報告，包含實驗設定、結果與分析。下面可以直接預覽或下載原始 PDF。