技術

MPI で高性能な分散プログラムを作る

2025年10月27日月曜日 / , , ,
簡体中文日本語
要約：
COMP90025 の二つ目の課題。MPI で辞書を複数のプロセスに分散し、Bloom filter で通信を削減した。BK-tree では 32 分かかっていた処理を、二秒未満に短縮した。

COMP90025 はメルボルン大学の並列・マルチコア計算（Parallel and Multicore Computing）の授業だ。大きな課題が二つあり、合わせると簡単な並列スペルチェッカーになる。最初の課題では OpenMP を使って文書から重複のない単語を集め、二つ目では MPI に切り替えて、それらを辞書と照合し、スペルミスと修正候補を調べる。

この記事は二つ目の課題を終えてから書いたものなので、コードもデータも最終提出版のものだ。コードは xxxbrian/mpi-spell-checker に置いてある。

課題の内容

プログラムの使い方はシンプルだ。

BASH
./spellcheck dictionary.txt word_list.txt

dictionary.txt はソート済みの辞書、word_list.txt はチェック対象の単語リストだ。リスト内の各単語について、辞書にない場合は、文字を一つ置換・削除・挿入して得られる候補をすべて生成する。そのうち辞書に載っているものが、正しい綴りの候補になる。また、大文字・小文字についてもルールがあり、先頭の文字を小文字に変えた単語が辞書にあれば、元の単語も辞書にあるものとして扱う。

出力はスペルミスのある単語ごとに一行で、その後ろに候補が続く。例えば次のようになる。

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

行は候補数の少ない順に並べ、同数なら辞書順にする。

課題にはもう一つ制約がある。各プロセスが保持できるのは辞書の一部だけで、全体をそれぞれに保存してはいけない。授業では BK-tree を使ったシングルスレッドの参考実装が配布され、自分たちのプログラムは大学の HPC クラスター Spartan で動かす。評価はコードとレポートに分かれ、レポートの配点が高いので、実験と分析も手を抜けない。

まずアルゴリズムを変える

実装に取りかかる前に、まず参考実装を動かしてみた。BK-tree で編集距離が 1 以下の単語を辞書から探すもので、最大のデータセットでは辞書が 62 万語以上、単語リストが 65 万語以上あり、約 32 分かかった。

自分の方法はもっと単純だ。編集距離が 1 と決まっているなら、候補をすべて直接生成し、ハッシュテーブルで一つずつ調べればいい。候補を生成するコードも複雑ではない。

C++
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 を一度呼び、全プロセスが自分の分割分を調べ、その結果の論理和を取る。

C++
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 で他のプロセスからリクエストが届いていないか確認し、あれば処理するようにした。

C++
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 を使い、各プロセスが自分の範囲だけを読むようにした。ただし、ファイルはバイト単位で分けるため、境界が単語の途中に来ることがある。そこで開始位置と終了位置をそれぞれ次の改行まで進め、各単語を必ず一つのプロセスだけが読むようにした。

C++
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 は同じプロセスで処理しなければならない。そこでハッシュを計算する前に先頭文字を小文字にし、どちらの表記も同じプロセスに割り当てられるようにした。

C++
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 で全プロセスのフィルターを交換する。これで各プロセスが全員分のフィルターを持つ。リクエストを送る前にローカルで確認し、フィルターが「ない」と判定した候補は確実に存在しないので、送らずに済む。

C++
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 秒になった。

全体の流れは、おおよそ次のようになる。

Mermaid diagram

実験方法

参考実装には簡単なテストが付属していたが、性能を調べるには足りなかった。そこで Python スクリプト batch_srun.py を自分で書き、まとめて実行した。

プログラムは各処理段階の所要時間を記録し、MPI_Reduce で平均値・最小値・最大値を集計して標準出力に出す。単一プロセスなら、例えば次のようになる。

TEXT
[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 に一行ずつ書き込む。

Python
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 などのオーバーヘッドも含まれる。

プロセス数

総所要時間 (s)

内部計測時間 (s)

うち候補処理 (s)

1

20.42

19.99

19.17

2

9.09

8.76

8.11

4

4.89

4.42

4.00

8

2.96

2.30

1.90

16

1.99

1.36

0.93

32

1.83

0.89

0.50

64

1.88

1.06

0.31

候補処理のスケーラビリティーは非常によく、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 を直接プレビューまたはダウンロードできる。

COMP90025 Project 2 Report BOJINLI.pdf436 KB · PDF開く
  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...