Raspberry Pi スパコン (11)　ナンプレ

ナンプレの高速化

サイズが９×９のナンプレ（SUDOKU）の問題の自動生成プログラムを「パズルナンプレ自動生成エンジン」で公開している。そこには、Java, Python, Cythonで書かれたプログラムがあり、その中の高速なCython版を、MPIを利用して複数のマシンで分担して問題を作ることを考えよう。また、ここの説明で作っていくMPI版のプログラムは、MPI版資料リンクに用意するので、適宜参照されたい。

普通に組まれたプログラムは、問題を１問ずつ作っていく。

でも、せっかくマシンがたくさんあるのだから、図の右側のように、マスターで全体の制御を行いながら、残りのマシンを全部ワーカーに仕立てて、それぞれのワーカーに、問題が出来たら次の問題生成を連続的に行わせることを考えよう。

一気にこれを作るのは大変だし、説明も混乱するので、元のプログラムを徐々に変更して目的を達成しようと思う。

準備

オリジナルのプログラムのサイズ（行数）は以下のようになっている。

  239 NP.py
  168 generator.py
    9 parameter.py
   62 solution.py
  299 solver.pyx
  720 合計

solverだけは、Cythonのソースになっている。

Raspberry Pi上でCython版を動かすには、Raspberry Pi上の/beta上に適当なフォルダを作って、公開しているプログラムやデータを全部入れる。/betaは全コンピュータで共有しているフォルダになっているので、/beta以下はここで並列に動かす全マシンで共通になっているので、/beta下に置いておくことで、環境は同じになる。

そして、*.c, *.soを消去してから、Cythonのコンパイルを実行する。

$ rm *.c, *.so
$ python3 setup.py build_ext --inplace

これだけで動くはずである。

ナンプレ自動生成エンジンのCython版を利用するのだが、MPIを利用して並列処理をするために変更するのは、NP.py のファイルだけである。

整理

このままでMPI対応にしても良いのだが、少し整理して、わかりやすくしよう。

NP.pyの中に、ユーティリティの関数がごちゃごちゃ入っているのを全部追い出して、すっきりさせよう。
そのために、以下の変更を行った。要するに、リファクタリング。

• parameter.pyの中に、NP.pyの中から以下を移動
  • Problemクラス宣言
  • 問題、パターンファイルの読み込み関数
  • 問題盤面、パターン盤面などのプリント関数
  • ヒント数のカウント関数
  • 問題盤面のコピー関数
• parameter.py を util.py に変更

Problemクラスには、MPI関連のメンバーを４つ追加した。
Pythonのクラスは、他のコンパイラ言語と違ってクラスも動的で、メンバーの追加が後からでもできるので、このような変更はしなくても良いのだが、メンバーを並べておいた方が分かりやすいので明記しておいた。
クラス生成時には、引数なしで中身のないオブジェクトを生成する。
使い方については、使うときに説明する。

class Problem:
	def __init__(self):
    	self.index   = None
    	self.retrycount = None
    	self.time	= None
    	self.rank	= None
    	self.problem = None
    	self.id  	= None
    	self.blanks  = None
    	self.answer  = None
    	self.pattern = None

こうすると、NP_ORG.py(NP.pyから上記の部分を除いたもの)ができ、プログラムの起動部分と、問題を延々と解くのと、問題を延々と生成する部分だけが残る。

バッファリング

オリジナル版では、sys.stderrがかなり使われているが、標準出力(sys.stdout)を使うようにした。

こうしてしまったのは、標準出力はバッファリングされてしまい、その他のエラー出力等との順序が狂ってしまい、特にデバッグ時によろしくないので、派手にバッファリングしないエラー出力を使うようにしていた。

標準出力のバッファリングを無くす処理をプログラムの最初に入れることで、プログラム全体で標準出力のバッファリングを無くした。

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', buffering=1)

これによる影響は、print文で、file=sys.stderr の指定や、sys.stderr.write()を使っていた部分を、すべて普通のprintに置き換えたことで、ちょっとスッキリした。

  146 NP_ORG.py
  173 generator.py
   60 solution.py
  298 solver.pyx
  127 util.py
  804合計

１つの問題を解くモジュールはsolver.py、１つの問題を自動生成するモジュールはgenerator.pyであり、これらには手を付けない。

整理したRaspberryCython版で、用意されている500問を解いてみた。

$ python3 NP_ORG.py
===== arguments input error =====
python3  NP_ORG.py  -s  problem_file   [answer_file]
python3  NP_ORG.py  -g  pattern_file   [problem_file]

$ python3 NP_ORG.py -s data/Problem500.tx

　　　　ーーー中略　ーーー

No.500   H 24
- - 2 3 - - - - -
- - 4 - - 5 - - -
- - - - - 6 - 1 8
- 2 8 5 - 7 - - 6
- - - - - - - - -
7 - - 6 - 1 5 9 -
9 5 - 7 - - - - -
- - - 2 - - - - -
- - - - - 3 7 - -
0
8 9 2 3 1 4 6 7 5
6 1 4 8 7 5 9 2 3
3 7 5 9 2 6 4 1 8
1 2 8 5 9 7 3 4 6
5 6 9 4 3 2 1 8 7
7 4 3 6 8 1 5 9 2
9 5 1 7 6 8 2 3 4
4 3 7 2 5 9 8 6 1
2 8 6 1 4 3 7 5 9

Total 500	Success 500
Time    0.398069 sec

とりあえず、問題を解くのは動いたようだ。

次回は、問題生成について考えよう。