Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

TopCoder CUDA Superhero Challenge 2

CUDA Superhero Challenge 2 に参加しました。

CUDAには前々から興味があったのですが,なかなか触れる機会もなく,そんな中でASCII.technologiesの先月号でGPGPU特集があり,TopCoderでもタイミング良くCUDAのコンテストが行われるということで,今回チャレンジしてみました。ちなみに,ASCII.Technologiesの記事はHack The Cellでお馴染みの(株)フィックスターズさんによるものでした。

 今回の問題は,N台の飛行機のメンテナンスを行う問題で,1日に1台,飛行機は1日ごとにいる位置が異なるという条件でメンテナンスする人の移動距離をより少なくする順番を求めよというものでした。巡回セールスマン問題で,訪問する度に都市がシャッフルされるような問題です。

今回はCUDAのコンテストということで,如何に多くの経路を評価することができるかがポイントなのだろうと考えました。全通りはN!(30<=N<=100)なので,CUDAと言えども現実的ではないように思います。
色々考えたのち,動的計画法的なアプローチで行くことにしました。完全な動的計画法を実行すると,最大で100C50個の中間値を管理しなければならないため,かなり端折って各ステップでTop-Mのケースのみを拾っていくような方法を考えてみました。Tesla(C1060)の性能が未知なため,Mを計算時間の調整項目として残せる点も良いかと考えました。(最終的には,このMをどう決めるかで悩むことになるのですが・・・)

 結果としては最後にスコアが伸びず,暫定20位で終えました。 本業が忙しい中では頑張ったのではないかと思います。おかげで土日を丸々つぶしてしまいましたが・・・

 今回,Teslaの計算パワーのすごさを体感しました。ローカルPC(CUDA DeviceEmulationですが)では実行が完了するのを待てないぐらいものが,10数秒で終わります。コードを書き始めてから知ったのですが,C1060というのは演算コアが240個もあるんですね。これは先に知っておくべきだったと後悔しています。結局,半分も使い切れないコードとなってしまいました。たかだか十数個程度だろうと甘く見てました。

Superhero Challenge 3があれば,またチャレンジしたいと思います。

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/43-4816d4a9
この記事にトラックバックする(FC2ブログユーザー)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。