Javaの計算グリッドを手軽に構築できるようにしました！！
最初にお断り
パフォーマンス計測で時間切れになり、記事を最後まで完成できませんでした。来週には完成版を公開する予定です。
本題
計算グリッドには昔から興味がありました。クックパッドには奥さんが非常にお世話になっています。そしてひょんなことからGridGainというJavaの計算グリッドフレームワークを見つけました。
↓GridGain+Scalaで簡単グリッドコンピューティング 浜本階生さん tllt#1↓
動画は1台のPCの中でGridGianを走らせて、Scala（関数言語onJava？）で分散処理を実行しています。
試しにどんなものか環境を作ってみました
手持ちのDebian Lennyを母艦にしてカスタムKNOPPIXがネットワークブート（PXEBoot）し、それぞれがGridGainの計算ノードになるようにしました。ミソはKNOPPIXなのでどんなPCでも一時拝借して計算ノードをどんどん追加できる点です。
構成
| 用途 | CPU | メモリ | 台数 |
|---|---|---|---|
| 母艦 | Pentium3 800MHz | 256MB | 1 |
| 計算ノード | Pentium3 800MHz | 256MB | 4 |
| 計算ノード | Celeron 2GHzくらい | 512MBくらい | 4 |
これらをハブ2台カスケード接続したネットワークで接続します。全部100Baseでリンクアップです。
計算ノード起動の様子
準備中20010.01.12追記
パフォーマンス計測（Grid vs nonGrid）
| 桁数 | 処理時間(Grid) | 処理時間（nonGrid） | 数 |
|---|---|---|---|
| 14 | 15,889ms | 5,746ms | 56,699,993,299,403＝ 5,674,033×9,992,891 |
| 15 | 12,761ms | 32,584ms | 432,671,265,179,137＝ 9,992,891×43,297,907 |
| 16 | 17,935ms | 139,895ms | 3,151,549,059,914,119＝ 9,992,891×315,379,109 |
| 17 | 16,518ms | 384,152ms | 51,874,848,423,388,477＝ 100,105,519×518,201,683 |
| 18 | 24,895ms | 1,010,127ms | 148,464,226,937,944,979＝ 100,105,519×1,483,077,341 |
| 19 | 213,594ms | 3,650,277ms | 9,223,372,021,822,390,277＝ 2,147,483,647×4,294,967,291 |
走らせた処理は、最初に「素数×素数」の数を与えてそれを素因数分解するというもの。Gridは母艦も含め9Node・9CPUで母艦から処理を実行、nonGridはGridGainを使わずに母艦で通常のJavaプログラムとして実行しています。
nonGridは非常にライナーな処理なので、桁数が多くなるほど処理を分割・並列化しているGridのほうがパフォーマンスが良いです。※数字は書き写しなので不正確かもしれません。
パフォーマンス計測（計算ノード数）
| 計算ノード数 | 処理時間(1回目) | 処理時間(2回目) | 備考 |
|---|---|---|---|
| 1 | 29,545ms | 30,606ms | 母艦のみ |
| 2 | 28,905ms | 27,214ms | ＋Pentium3 800MHz |
| 3 | 29,516ms | 28,760ms | ＋Pentium3 800MHz |
| 4 | 28,066ms | 29,744ms | ＋Pentium3 800MHz |
| 5 | 29,252ms | 26,974ms | ＋Pentium3 800MHz |
| 6 | 30,238ms | 27,177ms | ＋Celeron 2GHzくらい |
| 7 | 25,662ms | 18,717ms | ＋Celeron 2GHzくらい |
| 8 | 17,391ms | 28,192ms | ＋Celeron 2GHzくらい |
| 9 | 26,793ms | 17,696ms | ＋Celeron 2GHzくらい |
走らせた処理は同じで、最初に16桁の数（3,151,549,059,914,119＝9,992,891×315,379,109）を与えてそれを素因数分解するというもの。
処理を分割・並列化しているにもかかわらず、台数と処理時間に相関関係がありません。これはおそらくですが解を含んだ処理が高性能PCに振り分けられたときだけ速いという結果が出ている気がします。分割の粒度をもっと細かくすれば平滑化されるかもしれません。今後の課題です。
ちなみにGridGainに付属するサンプルの「org.gridgain.examples.primenumbers.gridify.GridifyPrimeExample」では台数と処理時間に相関関係が認められたので、ただ単純に計測プログラムの問題かもしれません。
パフォーマンス結果の推察
同じ16桁の処理でも計算ノード1台のGridとnonGridでは、前者295,45ms、後者139,895msと大きな差があります。考え付く限りの理由は以下の通りですが正直謎です。わかる方ご指摘ください。
GridGain実行時のログ
[17:46:46,770][INFO ][main][GridKernal%null] _____ _ _ _____ _ / ____| (_) | |/ ____| (_)
| __ _ __ _ __ | __ __ _ _ _ __ | ||||||||||||||||
| _ | '__ | / _` | _ | / _` | '_ \ | ||||||||||||
| __ | (_ | __ | (_ |
パフォーマンス計測で使ったソース
【Grid版】RSAChallenge.java
package grid; import java.math.BigInteger; import org.gridgain.grid.*; public class RSAChallenge { public static void main(String[] args)throws GridException{ //BigInteger _a = new BigInteger("5674033"); //BigInteger _b = new BigInteger("9992891"); //BigInteger _a = new BigInteger("44147").add(new BigInteger("00660").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("9992891"); BigInteger _a = new BigInteger("19877").add(new BigInteger("04812").multiply(new BigInteger(String.valueOf(256*256)))); BigInteger _b = new BigInteger("9992891"); //BigInteger _a = new BigInteger("08531").add(new BigInteger("07907").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("32047").add(new BigInteger("01527").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _a = new BigInteger("63197").add(new BigInteger("22629").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("32047").add(new BigInteger("01527").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _a = new BigInteger("2").pow(32).subtract(new BigInteger("5")); //BigInteger _b = new BigInteger("2").pow(31).subtract(new BigInteger("1")); BigInteger q = _a.multiply(_b); BigInteger a = bigIntegerSqrt(q); Grid grid = GridFactory.start(); long t1; long t2; try { t1 = System.currentTimeMillis(); a = RSAChallengeLoop.excuteLoop(q, new BigInteger("3"), a); t2 = System.currentTimeMillis(); }finally { GridFactory.stop(grid.getName(), true); } if(a!=null){ BigInteger b = q.divide(a); BigInteger c = q.mod(a); System.out.println(q + " ="); System.out.println(a + " * " + b + " + " + c); System.out.println(); System.out.println("it takes "+(t2-t1)+"ms"); System.out.println(); } } public static BigInteger bigIntegerSqrt(BigInteger x) { BigInteger b1 = new BigInteger(x.toString()), b2 = (b1.pow(2).add(x)).shiftRight(1).divide(b1); while (b2.compareTo(b1) < 0) { b1 = new BigInteger(b2.toString()); b2 = (b1.pow(2).add(x)).shiftRight(1).divide(b1); } return b1; } }
【Grid版】RSAChallengeLoop.java
package grid; import java.math.BigInteger; import org.gridgain.grid.gridify.*; public final class RSAChallengeLoop { private RSAChallengeLoop(){ } @Gridify(taskClass = RSAChallengeTask.class) public static BigInteger excuteLoop(BigInteger q,BigInteger minRange,BigInteger maxRange){ BigInteger a = maxRange; BigInteger b = q.divide(a); BigInteger c = q.mod(a); BigInteger TWO = new BigInteger("2"); if (a.mod(TWO).equals(BigInteger.ZERO)) { a = a.subtract(BigInteger.ONE); c = c.add(b); b = b.add(c.divide(a)); c = c.mod(a); } BigInteger ZERO = new BigInteger("0"); while (!c.equals(ZERO) && a.compareTo(minRange)>=0) { a = a.subtract(TWO); c = c.add(b).add(b); b = b.add(c.divide(a)); c = c.mod(a); } if (c.equals(ZERO)){ return a; }else{ return null; } } }
【Grid版】RSAChallengeTask.java
package grid; import java.math.BigInteger; import java.util.*; import org.gridgain.grid.*; import org.gridgain.grid.gridify.*; public class RSAChallengeTask extends GridifyTaskSplitAdapter<BigInteger>{ protected Collection<? extends GridJob> split(int gridSize, GridifyArgument arg) { Object[] args = arg.getMethodParameters(); BigInteger q = (BigInteger)args[0]; BigInteger taskMinRange = (BigInteger)args[1]; BigInteger taskMaxRange = (BigInteger)args[2]; BigInteger numbersPerTask = taskMaxRange.divide(new BigInteger(String.valueOf(((int)(gridSize*5))))); List<GridJobAdapter<BigInteger>> jobs = new ArrayList<GridJobAdapter<BigInteger>>(gridSize); BigInteger jobMinRange = BigInteger.ZERO; BigInteger jobMaxRange = BigInteger.ZERO; for (int i = 0; taskMaxRange.compareTo(jobMaxRange) >0 ; i++) { System.out.print(i+":"); jobMinRange = new BigInteger(String.valueOf(i)).multiply(numbersPerTask).add(taskMinRange); jobMaxRange = new BigInteger(String.valueOf(i + 1)).multiply(numbersPerTask).add(taskMinRange).subtract(BigInteger.ONE); if (taskMaxRange.compareTo(jobMaxRange)<0) { jobMaxRange = taskMaxRange; } System.out.println("jobRange is from "+jobMinRange+" to "+jobMaxRange); jobs.add(new GridJobAdapter<BigInteger>(q, jobMinRange, jobMaxRange) { public BigInteger execute() throws GridException { BigInteger q = getArgument(0); BigInteger min = getArgument(1); BigInteger max = getArgument(2); return RSAChallengeLoop.excuteLoop(q, min, max); } }); } return jobs; } public GridJobResultPolicy result(GridJobResult result, List<GridJobResult> received) throws GridException { if(result.getData() != null) { return GridJobResultPolicy.REDUCE; } return super.result(result, received); } public BigInteger reduce(List<GridJobResult> results) { for (GridJobResult res : results) { if (res.getData() != null) { return res.getData(); } } return null; } }
【nonGrid版】RSAChallenge.java
package nongrid; import java.math.BigInteger; public class RSAChallenge { public static void main(String[] args){ //BigInteger _a = new BigInteger("5674033"); //BigInteger _b = new BigInteger("9992891"); //BigInteger _a = new BigInteger("44147").add(new BigInteger("00660").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("9992891"); BigInteger _a = new BigInteger("19877").add(new BigInteger("04812").multiply(new BigInteger(String.valueOf(256*256)))); BigInteger _b = new BigInteger("9992891"); //BigInteger _a = new BigInteger("08531").add(new BigInteger("07907").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("32047").add(new BigInteger("01527").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _a = new BigInteger("63197").add(new BigInteger("22629").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _b = new BigInteger("32047").add(new BigInteger("01527").multiply(new BigInteger(String.valueOf(256*256)))); //BigInteger _a = new BigInteger("2").pow(32).subtract(new BigInteger("5")); //BigInteger _b = new BigInteger("2").pow(31).subtract(new BigInteger("1")); BigInteger q = _a.multiply(_b); BigInteger a = bigIntegerSqrt(q); long t1 = System.currentTimeMillis(); a = RSAChallengeLoop.excuteLoop(q, new BigInteger("3"), a); long t2 = System.currentTimeMillis(); if(a!=null){ BigInteger b = q.divide(a); BigInteger c = q.mod(a); System.out.println(q + " ="); System.out.println(a + " * " + b + " + " + c); System.out.println(); System.out.println("it takes "+(t2-t1)+"ms"); System.out.println(); } } public static BigInteger bigIntegerSqrt(BigInteger x) { BigInteger b1 = new BigInteger(x.toString()), b2 = (b1.pow(2).add(x)).shiftRight(1).divide(b1); while (b2.compareTo(b1) < 0) { b1 = new BigInteger(b2.toString()); b2 = (b1.pow(2).add(x)).shiftRight(1).divide(b1); } return b1; } }
【nonGrid版】RSAChallengeLoop.java
package nongrid; import java.math.BigInteger; public final class RSAChallengeLoop { private RSAChallengeLoop(){ } public static BigInteger excuteLoop(BigInteger q,BigInteger minRange,BigInteger maxRange){ BigInteger a = maxRange; BigInteger b = q.divide(a); BigInteger c = q.mod(a); BigInteger TWO = new BigInteger("2"); if (a.mod(TWO).equals(BigInteger.ZERO)) { a = a.subtract(BigInteger.ONE); c = c.add(b); b = b.add(c.divide(a)); c = c.mod(a); } BigInteger ZERO = new BigInteger("0"); while (!c.equals(ZERO) && a.compareTo(minRange)>=0) { a = a.subtract(TWO); c = c.add(b).add(b); b = b.add(c.divide(a)); c = c.mod(a); } if (c.equals(ZERO)){ return a; }else{ return null; } } }
この環境を必要としている方へ
母艦を含め、インストール作業なしにこの環境を構築できるカスタムKNOPPIXを作りました。使い方は以下の通りです。
- 使っていないPC達をハブで繋ぎます。−※1
- カスタムKNOPPIXをCD-Rに焼いて、それの1枚目を使って母艦を起動させます。
- 母艦が起動したら1GB程度のswapを割り当てます。−※2
- 母艦のCD-Rを2枚目に入れ替えます。
- 母艦でコンソールを開き、「su」→「/root/startserver.sh」と実行します。
- 計算ノードの電源を入れ、ネットワークから起動させます。−※3
※1…IPアドレスはAPIPAの範囲（169.254.0.0/16）を使用します。
※2…USBメモリを挿してfdiskとかmkswapとかswaponとかします。
※3…BIOSの設定などでNetwork起動の優先順位を上げてやります。
これで計算グリッドの出来上がりです。後はGridGainのサイトを参照しながらJavaプログラムを組んで実行すればいいだけです。なお、プログラムの実行に際して環境変数・CLASSPATH・javaコマンドオプション等、つまずき所がいくつかあるので、母艦にあるgjavac.shやgjava.shも使ってみてください。
ライセンス
1枚目はKNOPPIXをカスタマイズしただけなのでGPLです。2枚目はGridGainとSunJDKを含みます。GridGainはLGPL、SunJDKは調べたけれどもはっきりとはわかりませんでした。再配布のためにCDを2枚に分けたんですが、「1枚にまとめても問題なし」or「2枚に分けても問題あり」な場合はご指摘ください。
ダウンロード
準備中
まとめ
パフォーマンス測定はなかなか期待通りの結果が得られませんでしたが、久々に大学の頃にやっていたPC相手の実験ができて楽しかったです。
