Cell Challenge

今年のテーマはLCS(Largest Common Sequence)に似た問題のようです。
http://www.hpcc.jp/sacsis/2009/cell/
問題としては簡単なんですが、これ、ベクトル演算使ってやろうとすると意外と骨が折れる類の問題の気がする。
基本的な演算量は、文字列長m, nに対してO(mn)で、並列化手法としてはパイプライン並列的なものを使うのが普通ですが、このmとnが非常に近い場合は問題があまりおきません。というのは、O(mn)であるのだから、mとnは高々10000とかそれくらいのオーダーなので、Cellのlocal storeに乗っかるんです。問題は片方が長い場合、たとえばm = 100, n = 1000000くらいだとすると、これをどう並列化するのか、というのは結構難しい。
その理由は、この100 x 1,000,000の配列操作を並列化するときに、たとえば、100 x 200,000 x 5のように切り取ってやったりすると、パイプラインがあまりきれいに動かなかったりするし、20 x 1,000,000 x 5のように切ってやろうとすると、今度は1,000,000がメモリに乗らなくなったりする。そうすると、やはりメモリアクセスと演算と並列化効率をうまーく調整してやらなきゃいけない。

皆様頑張ってください