Search on the blog

2020年4月29日水曜日

GCP MPI Cluster

 昔Distributed Code Jamというコンテストがありました。単一のマシンでは解けないような問題を複数のマシンでいい感じに解くというコンテストですが近年は開催されておりません。Distributed Code Jam のような問題を解いて遊びたいなと思い、手軽に並列コンピューティングを行う環境を構築できる仕組みを作ってみたのでブログで紹介したいと思います。

やりたいこと
ローカルマシンからコマンドを実行するだけで以下のことができるようにします。
  • 並列コンピューティング環境が自動構築される
  • 複数ノード上で目的のプログラムをコンパイルできる
  • 複数ノード上で目的のプログラムを実行できる
つくったもの
https://github.com/Kenji-H/gcp-mpi-cluster (このブログを書いているときはv0.9.1のものが最新です)

クラウドサービスに Google Cloud Platform、インフラの構築自動化に Terraform、構成管理ツールに Ansible、並列コンピューティングのライブラリに MPI を使っています。

Getting Started

0. Google Cloud Platform(GCP)のアカウントを持っていない場合は作成してください。また、ローカルマシンにTerraform、Ansible、jq が入っていない場合はインストールしておいてください。

1. GCPのコンソール画面から「Compute 管理者」ロールを付与したサービスアカウントを作成します。

2. サービスアカウントキーを生成し、terraform ディレクトリ直下に account.json という名前で保存します。

3. terraform/terraform.tfvarsというファイルを作成し環境設定をします。YOUR_PROJECT_NAMEのところはあなたのGCPプロジェクトIDに置き換えてください。日本で動かす場合はYOUR_REGION_NAMEのところはnortheast1、YOUR_ZONE_NAMEのところはasia-northeast1-aなどとするとよいでしょう。
project = "YOUR_PROJECT_NAME"
region = "YOUR_REGION_NAME"
zone = "YOUR_ZONE_NAME"

4. ./creater_cluster を実行します。このスクリプトはGCPのcompute engineを複数台起動し、並列コンピューティングに必要な環境設定を自動で行います。

5. ./compile hello でサンプルプログラムをコンパイルします。このスクリプトはローカルマシン上のプログラムをコンピューティングクラスタのノードに転送し、各ノード上でコンパイルを行います。

6. ./run hello でプログラムを実行します。hello は各ノードのプロセッサ名を表示するだけの簡単なプログラムです(app/hello/のソースを参考)。もう少し難しいプログラムを動かしたい場合は app/divisor のソースを見て hello と同様にコンパイル・実行してみてください。

7. 遊び終わったら ./destroy_cluster を実行して、インスタンスを破棄しておきましょう。

注意
このプロジェクトによって発生した如何なるエラー、問題、結果について責任を負いません。意図的に悪意のあるコードは含まれていませんが、利用にあたってはクレデンシャル情報(account.json)が外部に漏れないこと、また、インスタンスを起動しっぱなしにして高額請求されることのないように十分気をつけてください。

2020年2月7日金曜日

c++17 で stg::lcm が追加されててハマった話

 Codeforcesのk-roundingという問題を解いたらWAが出た。

「nとkが与えられるので、末尾に0がk個以上ついてnで割れる最小の自然数を求めよ」という問題で、nと10^k の最小公倍数を求めれば良さそうなので、以下のようなコードをsubmit。

#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()
 
const double PI = acos(-1);
 
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  return gcd(b, a%b);    
}
 
long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int n, k;
  cin >> n >> k;
 
  int x = 1;
  REP (i, k) x *= 10;
 
  cout << lcm(n, x) << endl;
  
  return 0;
}

結果Wong Answer。
詳細なテストケースを見てみると、n = 123456789, k = 8 で 1566078208 と出力されている。試しにローカルで動かしてみると12345678900000000と正答を出力している。

上のコードでは main の中では int を使っているけど引数としてlcmに渡した時点でlong longになるのでオーバーフローはしないはずだが、試しにmainを以下のように変えてsubmitしてみると予想に反してAC。

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  long long n, k;
  cin >> n >> k;
 
  long long x = 1;
  REP (i, k) x *= 10;
 
  cout << lcm(n, x) << endl;
  
  return 0;
}

サーバでは g++17 で実行されるけどローカルだとg++17じゃないなと気づいて、もしやと思って調べると std に gcdlcm が追加されてました。引数を int で渡すとこちらが実行されていたようです。

とりあえずローカルでコンパイルするときに g++17 を使うようにしたものの、サンプルケースにオーバーフローするものがないと意図せず std::lcm の方が呼び出しされていることに気づけないので、自分のライブラリ関数の名前を変えた方がいい気がしています。