Entries

前回の補足と反省

 前回で「並列化効かねぇorz」と唸っていた問題、自己解決しました。
 とは言っても「自己解決」というほどあっさりとしたものではなかったのですが……。

 まず、元ソースで一番重そうなところをコメントアウトしてみました。具体的には、「ゴール地点に付いた時に得点を計算する部分」です。ですが、それでもシングルスレッド<マルチスレッド(処理時間が)だったので、二番目に遅そうな「移動する度に現在の移動経路を記録する部分」をコメントアウトした結果、シングルスレッド>マルチスレッド(処理時間が)となったのです。
 とは言ってももちろん、その部分で改善を怠っていたというわけではありません。具体的には、

・元々そこはvectorで保存していて、push_back()とpop()で付け足し&戻しをしていた

・言うまでもなくpush_back()は遅いので、最終位置を示す変数を新たに用意し、vectorはresize()で前もって確保した

・速度(゚д゚)ウマー

といった感じです。この辺を重点的に見ていくと、
「並列処理時にはresize()するのを忘れていた」
という重大なミスを発見! 速攻で直しました……が、まだ遅い。あれこれ弄っていくと、ふとこんなことを。
「ん? DFS中で『最終位置を示す変数』をインクリメント/デクリメントするところをコメントアウトすると速度が回復するぞ?」
……つまり。なぜか並列処理が遅かった最大の原因は、
その変数を関数では「参照」として扱っていたからなのです!!!

 ……分かりますか? 分かったらあなたは並列処理のプロかエスパーです。自分も驚きました。
参照ではなく普通に値渡ししたら速度が倍になるとは。
「参照」(つーか参照渡し)がいつも最速だとは限らないといういい例でした。わけがわからないよ


 それともう一つ。前回ラストでネタにしていましたが、「当時の技術(ソフト・ハード)で果たして5x7の問題が解けたのか?」
「並列化してDFS」なんて発想は、おそらく当時のプログラマの方々でも普通に思いつけたことでしょう。OpenMPの歴史を紐解くと(ソースはリンク先)、2002年3月で既にOpenMP 2.0 for C/C++が発表されています。少なくともVC2005ではOpenMPが使えますし、そうでなくともMPIなど、他の並列化手段も普通に存在していました。よって普通に作れると仮定します。
 次にハードですが、冷静に考えるとPentium 4が普通にありましたね、すみません。と言うかPentium Dが出るの遅すぎ(Smithfield世代ですら2005年5月末)なので、Pentium 4が最速と言っても過言では……あるかも(Pentium III 的に考えて)。http://hardware-navi.com/cpu.phpを参考にすれば、Willamette世代のものでPass Markスコアが228~339Prescott世代で430~651(Prescott-2M世代はとりあえず除外)。ちなみにCore i5-3210MのPass Markスコアは5256なので……え、マジ?
 前述した「並列化ヒャッホウ!」ネタは、この辺りのPentium 4(1コア1スレッド)には当てはまりません。と言うわけで、前もってシングルスレッドで5x7サイズの問題を解かせると、331.306秒掛かりました。大雑把に(と言うか甘めに)、上記スコアに反比例して計算時間が延びると仮定すると、1回5x7問題を解かせるのに331.306秒×((5256/4)÷339)≒21分掛かることになります(/4しているのは論理4コアだから)。仮に、「The Paper Challeran 25」を解かせるとなると、これを15×16=240回も解かせる(全経路について調べる)必要があるため、24時間ぶっ続けでも3.6日は掛かることに……。ん、なんとかなるっぽい?
 電気代にさえ気をつければ、当時でも十分計算できたっぽいことが分かりました。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/54-9359e8a4

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

08 ≪│2017/09│≫ 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: