みなさんこんにちは！
Habréでの先週は、
VoIPと
オンラインの交通渋滞の両方をハッキングする一連のハッカー投稿によって特徴付けられました。
今週をより建設的に続けることを提案します-並列プログラミング
における遺伝学 の世界的な問題を解決するために。
月に何もする必要はありません。
文字A、T、G、Cのヌクレオチドで構成される2行で共通部分文字列の最大長を見つけます。賞品は以前に比べて成長し、
獲得しました-今日、
6つの Asus Zenbook UX31Eウルトラブックと
10のSSDドライブがあり、合計容量800ギグが
かかってい ます 。
魅力的ですか？
何言ってるの？
参照文字列（たとえば、これは
GATGAGCATGTGTTGAATCCTCA ）と多くの長い入力文字列（ここにそのうちの1つは
GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT ）が与えられています。 参照文字列と入力文字列の各ペアは、最も長い共通部分文字列を見つけて、それらの「座標」を返す必要があります。 例では、答えは
(5 13 15 23)と
(5 13 44 52)になります。つまり、2つのサブストリングが見つかります。
自由に使える
参照コードがありますが、この問題は力ずくで非常にゆっくりと解決されます。
それは簡単に聞こえますか？
決定方法
ここから楽しみが始まります。 役に立つかもしれないいくつかのオプションを提供します：
- 最も簡単な方法：データで参照コードを並列化します。たとえば、OpenMPを使用し、入力テストの作業をスレッド間で分割します。 ただし、さまざまな方法で作業を共有できます。 入力文字列のみ？ 参照文字列の断片？ それはそのサイズと量に大きく依存します-あなたが決めます。
- より興味深い方法：参照コードを取得し、 Intel VTune Amplifier XEを介して実行し、アルゴリズムをスマートな方法で並列化します
- よりスマートなアプローチ： 文字列で9000を超える部分文字列検索アルゴリズムの 1つを使用し、このタスクに最適なものを見つけようとします。
- 最も高度なアプローチ：前の段落を結合し、スマートアルゴリズムを使用して、指示とデータに従って並列化します
何を選ぶ？ ヒントが欲しい！
選択できるものはお勧めできません。 pthreadで書くのが好きな人、OpenMPで書く人、そしてTBBや多分MKLの並列関数を使うのが好きな人がいます。
一つのことは確かです-非常にスマートなアイデアと思考がしばしば私たちの
フォーラムで議論されています。 たとえば、SSE4.2の手順を見る価値があります。
何を書くことができますか？
残念ながら、自動化されたテストシステムは若すぎて、すべてのプログラミング言語をサポートできません。
今回は（PythonとJava Scriptに対する私の誠実な愛にもかかわらず）C ++を理解するように彼女に教えたので、古き良きC ++で書く必要があります。
開発プラットフォームはどのようなものでもかまいませんが、コードはgcc（pthreads愛好家向けバージョン4.6.2）およびIntel Parallel Studio XE 2011（Intelを選択した人向け）がインストールされたLinuxマシン（Debian安定版-カーネル2.6.32）で収集およびテストされますコンパイラー、プロセッサーのコードを最適化する）。
賞品はどうですか？ ウルトラブックが欲しい！
5月16日までに最速のコードを作成してソリューションを送信した最初の3チームは、参加者ごとに
Asus Zenbook UX31Eを提供します。
2番目の3チーム
-SSD 320シリーズ80Gb 。
Intel Software Networkで最も興味深い
ブログ記事を書いてくれた別の4人の参加者もSSDを入手します。
だから、もう一度：ロシアとCISからの最高の参加者のための
1タスク 、1ヶ月、
6ウルトラブックと10 SSD 。
参加することに決めたすべての人に幸運を！
コンテストの主催者と審査員は、コメントであなたの質問に答える準備ができています。