2007-06-26

■

久しぶりに見て、レイアウトおかしいなぁと思ったら、OS変わったせいだった

2007-06-26

Automated Empirical Optimizations of Software and the ATLAS project

http://citeseer.ist.psu.edu/whaley00automated.html

以前、FFTWをちょろっと眺めたので、ATLASについても眺めて見た。論文は、どうでもいい話が長いので、
http://www.ueda.info.waseda.ac.jp/~ishizaki/pukiwiki/pukiwiki.php?%BF%F4%C3%CD%B7%D7%BB%BB%A5%E9%A5%A4%A5%D6%A5%E9%A5%EAATLAS#content_1_1

コンセプト的には、ATLASは、FFTWの線形代数版みたいな感じで、色んなアーキテクチャに対して、ライブラリを人間が手でチューニングすんのは面倒、自動的にチューニングしようぜ、というような話。けどまあ、FFTWとは、大分やり方が違う

FFTWの方針は、
・原則として、コードレベルでは、"portable"で、マシンレベルの最適化は、plannerが実行時に最適なcodelet(固定したサイズのDFTを計算するコードみたいなもん)の組み合わせを見つけることで行われる
・codelet部分は、genfftが自動生成。codeletは、とにかく、単純に足し算と掛け算の数を減らす
みたいな感じだと思う。

FFTWで、codeletの演算回数を絞るのが、どの程度高速化に寄与してるのかは知らんけど、ATLASの方は、演算量減らすとかはどうでもよくて、メモリアクセスが重要という考えで、うまくレジスタやらキャッシュを使おうというような(FFTWが、そういうのを無視してるというのは言いすぎだけど、でもまぁ直接的には何もしてないし)。そういう最適化は、多分すごい昔から知られてるので、ATLASがやったことってのは、(インストール時に)色んなコードを自動生成して、自動でベンチマークかけて、一番効率のよいのを選ぶ、という人間が手動でやってたことを、ほとんどそのまま自動化した感じっぽくて、あんまり面白みはないような。

あとまあ、ソフトウェアをハードウェアに合わせてチューニングするんじゃなくて、ハード作ろう的な流れはあると思うんだけど。BLAS API(まあ、大体は、行列の掛け算なDGEMM)をFPGAで実装したとかいう論文は、結構あるけど、今のとこ、そういうのが特に利用されてるようでもないし、実際んとこ、汎用CPU+ATLASの組合せと比較して、そんな速いわけでもないか、むしろ遅いというのが実態らしい。遅い理由は、実装が悪いとか、データ転送がボトルネックになってとか色々あるだろうけど。FFTの方は、DSPとかはあるけど、HPCでFFT on FPGAが利用されてるとかって話もあんま聞かないし、どうなんだろう。

2007-06-26

そんなわけで、FPGAでも勉強しよう

<言い訳>まぁ、色々分からないことだらけなのでアレだけども言い訳>。

方針
・ハードウェア記述言語というと、VHDLとかVerilogとかあるらしいけど、Haskellに埋め込まれたLavaというHDLがあるらしいので、それを使ってみる。理由は特にない
・経済的事情により、当面FPGAボードなし、シミュレータでがんばる
・飽きたらやめる

(たぶん)Lavaの最初の論文
http://citeseer.ist.psu.edu/69503.html
サイト
http://raintown.org/lava/

インストールはmake一発。もしくは、

runhaskell Setup.hs configure
runhaskell Setup.hs build
runhaskell Setup.hs install

GHC6.4.2で何の問題もなし。

論文の頃とは、微妙に色々変わってるようで、結構はまる。まぁ、10年近く前の論文だし。10年経っても、まだバージョン0.1というのは、なんか色々事情があったのかもしれないし、単に中の人が飽きたのかもしれない

あんまり意味ないけど、NANDな例。

import Lava

nand :: Combinational m bit => (bit,bit) -> m bit
nand = and2 >-> inv

nand_top :: Out ()
nand_top
 = do a <- input_bit "a"
      b <- input_bit "b"
      c <- nand (a,b)
      output_bit "c" c 

main
  = do nl <- netlist nand_top
       putXST_VHDL "nandGate" nl

これをコンパイル&実行すると、nandGate.vhdというVHDLファイルが作られる。それが正しいのかどうかは，いまのところ私には分からない(ダメ。まぁ、いくらなんでも、これくらいなら間違えないだろうと信じてる。本体は、
nand=and2>->inv
の部分で、Combinationalとかいう謎のモナドは何かよく分からんがどうでもいいこととする。論文では、Circuitとかいうモナドが登場してたけど、なくなったっぽい(というか、CombinationalとSequentialに分離したのか?)。(>->)は、
(>->) :: (Monad m) => (a -> m b) -> (b -> m c) -> a -> m c
という型。型を見ただけで、何するか大体分かるけど，
f>->g = (\x -> (f x)>>=g)
みたいな定義だと思う(確認してないけど)。Arrowの(>>>)に相当する演算子だと思えばよいっぽい。

mainの部分のnetlistというのは、何してるのかよく分からん。その後のは、なんかVHDLに吐き出してるだけ。VHDLと比べて、劇的に記述量が減るということもない気がする。まぁ、この例だけでは、何とも言えないけど。それでも、私には、VHDLよりはLavaの方がsyntax的に馴染むし、あとまあ、(>->)とか(<|>)みたいなコンビネータが使えるのはよい(<|>は今のLavaでは、消えたっぽい。代わりにpar2とかいう名前になってる)。コンビネータが使えて嬉しいのは、別に記述量が減るからいうより、2つの回路の等価性を機械的に判定できる可能性を示唆しているような気がするので。trivialな例だと、
(a <|> b) >-> (c <|> d) = (a >-> c) <|> (b >-> d)
(a >-> b) >-> c = a >-> (b >-> c)
みたいな。まぁ、一般的にそんなことできるなら、とっくに誰かがやってそうな気もするけど。あと、そもそも、ふるあだーと程度でも、基本関数+コンビネータだけで書くのはしんどいかもしれない

んで、VHDL生成してくれても、それだけではなんもできん。開発ツールには、XilinxのISE WebPackを使おうと思った(使えと書いてあるから)。Linuxのサポートは適当らしいけど、とりあえず、普通にインストールできたと思ったら、何かSynthesizeとかで失敗する。同じことをWindowsでやると、なんか警告はでるけど、成功する。よくわからん。そして、シミュレータを使おうと思っても使えないので、そのうちカーズは考えるのをやめた。

次回以降の目標
・FreeHDLというシミュレータがあるらしいので、そっち試す
・もうちょっと複雑な回路をつくる
・わからんって書いた部分を調べる