chiselで色々なデータを扱ってみた話

chiselというscala baseのalt HDLがあります。それなりに速く動く回路を書けるらしいのでそれなりにいいみたいです。テストもscalaで書けて、C++のテストコードを生成したり、verilogの回路をchiselはscalaのSDLですが、scalaとは別にchiselのレイヤーで型推論器を持っていたりなかなかしっかりしているみたいです。scalaのインスタンスがchiselの型に対応して、chiselのデータもscalaのインスタンスの内部に格納されているっぽいですがその辺は正直良く理解していないので迂闊なことは書かないでおきます。

ラッチ

chiselにはRegというclassというか型があります。Regはハードウェアで言うところのラッチに相当するものを生成するらしく、クロックのライジングエッヂのタイミングで入力データが書き込まれるっぽいです。テストを含めて書いてみたものはこれです。

メモリ

chiselにはメモリを表わすMemという型があります。シーケンシャルかどうかはパラメタで決められてまあメモリっていう感じです。少なくともテストの上ではラッチと同様にライジングエッヂのタイミングで動作するみたいです。テストを含めて書いてみたものはこれです。

Vec型

ところでchiselにはVec型という配列のようなデータ構造があります。ハードウェア的にはROMなんでしょうか。良くわかりません。実はVecのラッチのReg (Vec)型を作ることもできます。これがなんとMemと大体同じような動作をします。コードはこれです。ちなみにverilogを生成すると結構違う感じになります。verilogは良くわからないのでどっちが速いかは何とも言えないですが、Memの方が綺麗なコードが吐かれました。

二次元配列のようなもの

じゃあMemとVecを組み合わせたりすると二次元配列 (rowとcolを指定するメモリ)の様なものを扱えるかという気がしますが、なぜかこれは上手くいきませんでした。 (これがコード)じゃあReg (Vec (Vec))は動くのかというとこっちは動きました(これがコード)。世の中よくわからないものですが、コードの感じから言ってMemを使って線形なメモリとして扱うのが良さそうです。

Runge-Kutta法のまとめ

差分法 (オイラー法) とからめてRunge-Kutta法についてまとめてみた。近似次数とか刻み幅制御とかは省いている。

差分法

一階微分方程式の近似解を求めることを考える。

前進差分法

hが十分小さい場合
$$ f'(x) \approx \frac{f (x+h) - f(x)}{h} $$
と近似することができる。これを用いると

$$ f (x+h) \approx f (x) + h f'(x) $$
と近似することができる。例えば$f' (x) = f (x),f (0) = 1$の場合

$$ f (x+h) \approx (1 + h)f (x) $$

となるので$f (nh) \approx (1+h)^n$となる。厳密解の$f (x) = e^x$と比較してplotするとこんな感じになる。

後退差分法

$f'$は
$$ f'(x) \approx \frac{f (x) - f(x-h)}{h} $$
と近似することもできる。これを用いると

$$ f (x+h) \approx f (x) + h f'(x+h) $$

と近似することができる。例えば$f' (x) = f (x),f (0) = 1$の場合

$$ f (x+h) \approx \frac{1}{1-h}f (x) $$

となる。この場合は容易に解けるが、右辺に$(x+h)$に依存した項が出てくるので一般には連立方程式を解く必要がある。このような解法を陰的解法と呼ぶ。 逆に前進差分法の様に順々に代入していけば求まる解法を陽的解法と呼ぶ。

Runge-Kutta法

差分法では傾きを一次で近似した解法であった。 (テイラー展開と比較すると示せる。)更に良い精度で傾きを近似する方法として (一般の) Runge-Kutta法がある。
Runge-Kutta法は、$f (x,y) = y'(x)$としたときにパラメタとして$s$次行列$A$,$s$次ベクトル$\mathbf{b},\mathbf{c}$を与えて

$$\begin{align*} y (x_0 + (n + 1)h) &= y (x_0 + nh) + h \sum_{i=1}^{s} b_i k_i\\ k_i &= f (x_n + c_ih,y_n + h\sum_{j=1}^{s}a_{ij}k_j) \end{align*}$$

として近似する方法である。通例$c_i = \sum_{j=1}^{s}a_ij,\sum_{i=1}^{s}b_i = 1$となるようにする。Butcher配列

$$\begin{equation*} \begin{array}{c | c} \mathbf{c}& A\\ \hline & \mathbf{b}\\ \end{array} \end{equation*}$$
を用いてRunge-Kutta法を表わすことができる。

例えば前進差分法は

$$\begin{equation*} \begin{array}{c | c} 0& 0\\ \hline & 1\\ \end{array} \end{equation*}$$

であり、後退差分法は

$$\begin{equation*} \begin{array}{c | c} 1& 1\\ \hline & 1\\ \end{array} \end{equation*}$$

である。

RK4 (古典的Runge-Kutta法)

Runge-Kutta法のなかでも4次のRunge-Kutta法

$$\begin{equation*} \begin{array}{c | c c c c} 0& 0 &0 &0 &0\\ \frac{1}{2} & \frac{1}{2}& 0& 0& 0\\ \frac{1}{2} & 0&\frac{1}{2}& 0& 0\\ 1& 0& 0& 1& 0\\\hline & \frac{1}{6}& \frac{1}{3}& \frac{1}{3}& \frac{1}{6} \end{array} \end{equation*}$$

精度が良く一般に良く用いられる。

RK4のように$A$が狭義下三角行列になる場合陽的に解くことができるので陽的Runge-Kutta法と呼ばれる。 そうでない場合を陰的Runge-Kutta法と呼ぶ。陰的Runge-Kutta法の方が陽的Runge-Kutta法よりも計算は煩雑だが少ない段数でより近似精度が良いという事実が知られている。

HaskellでGraphvizのデータをパースする

Graphvizとはオープンソースのグラフ描画ソフトでDOT言語というグラフを表現するための言語を読み込んでグラフを描画してpngやepsなどの形式で出力することができます。このあたりの詳細はWikipediaを参照したりするとわかると思います。

Haskellでグラフの処理をするときの入出力形式としてDOT言語が使えると便利です。Happyとかを使って自分でパーサを書いても問題ないですが、ライブラリにパーサがあるならそれを使ったほうが楽ですね。Haskell用のGraphvizのライブラリgraphvizがあります。グラフの描画などGrapvhvizを用いた諸々の処理を行えるらしいですが、今回はこれをパーサとして使います。使うのはparseDotGraphで、Textを入力として受け取ってParseDotReprを出力します。ParseDotReprはグラフの表現の型クラスで、例えばDotGraphでラベルとしてStringを用いる場合はparseDotGraphの出力の型がDotGraph Stringに推論されるように型を記述するとよいです。graphNodes (parseDotGraph $ pack "digraph {a -> b}" ::DotGraph String)とか書くとこのグラフのノードのリストが得られます。

PAPIでのFLOPSの計算の方法

PAPI(Performance API)というものがあります。キャッシュヒット率、ミス率、FLOPS、命令の呼び出し回数などを計測できるAPIで、CPUの機能を使います。命令の呼び出し回数を計測できるので、今回は浮動小数点演算の呼び出し回数を計測してFLOPSを計測するのに使おうと思います

PAPIには高レベルAPIと低レベルAPIがあります。高レベルAPIにはまさにFLOPSを計算するためのPAPI_flops関数があります。これを計測したい処理の前後に挟むだけでFLOPSを取得できます。ただし、複数回計測する場合は値がリセットされないので入力時に-1を入れておく必要があります。

普段使う分には高レベルAPIを使えばいいですが高レベルAPIは並列化に対応していないのでopenmpなどで並列化したときは低レベルAPIを使う必要があります。低レベルAPIを使う場合は時間と実行命令数からFLOPSを計算する過程を自分で実装する必要があります。

参考

• http://icl.cs.utk.edu/projects/papi/wiki/PAPITopics:Getting_Started
• https://icl.cs.utk.edu/papi/docs/d0/d64/classPAPI__flops.html
• http://www.comphys.las.shibaura-it.ac.jp/papi

シュトラッセンのアルゴリズムの計算量

シュトラッセンのアルゴリズムという行列積を求めるアルゴリズムがあります。行列積を求めるときに部分行列の積を求めることによって演算回数が少なくて済みます。通常の行列積の演算は$O(n^3)$ですが、シュトラッセンのアルゴリズムを使うと$O(n^{\log_2 7})$で行えます。巷には日本語だとシュトラッセンのアルゴリズムの説明はちらほらありますが計算量について言及している説明はほとんどないのでしてみようと思います。

サイズNの正方行列の掛け算を考える。因みにシュトラッセンのアルゴリズムを使うときは正方行列でなかったら端に0だけの行or列を追加して無理やり正方行列にする必要がある。Nが2のべき乗でない場合は漸化式が途中で計算できなくなるので途中で諦めるか最初から諦める必要があると思う。以下Nは2のべき乗ということにする。サイズNの正方行列のシュトラッセンのアルゴリズムによる計算時間を$T(N)$と書く。シュトラッセンのアルゴリズムでは半分のサイズの行列積を7回求める。行列和の計算量は$O(N^2)$なので $$ T(N) = 7 T(N/2) + O(N^2) $$ となる。マスターの定理を使うと$O(N^{\log_2 7})$となる(らしい)。

マスターの定理はよくわからないのでマスターの定理を使わないで$T(N) = O(N^{\log_2 7})$を示す。 $$2^n := N$$ として $$U(n) := T(N)$$ と書くと $$U(n) = 7 U(n-1) + O(2^{2n})$$ となる。漸化式を解く感じで整理すると \begin{align*} &\frac{U(n)}{2^{2n}} + \frac{4}{3} c \leq \frac{7}{4} \left(\frac{U(n-1)}{2^{2n-2}} + \frac{4}{3}c\right)\\ &\leq \left(\frac{7}{4}\right) ^ n \left( U (0) + \frac{4}{3}c\right)\\ &\leq \left(\frac{7}{4}\right) ^ n c' (c'はなんかしらの定数) \end{align*} となるので $$ \frac{T(N)}{N^2} \leq c'\left(\frac{7}{4}\right) ^ {\log_2 N} $$ \begin{align*} T(N) &\leq c' N^2 \left(\frac{7}{4}\right) ^ {\log_2 N} \\ &= c'7 ^ {\log_2 N}\\ &= c'N ^ {\log_2 7} \end{align*} となり $$ T(N) = O(N^{\log_2 7}) $$ が示せた。

計算量解析をしてみたけれど数値計算的にはシュトラッセンのアルゴリズムはほとんど使われない。というのも

• オーダは小さいけど定数が大きいから普通はシュトラッセンのアルゴリズムの方が時間がかかる
• 疎行列だともっといい方法がある
• 部分行列の計算のところでメモリを一杯食う
• 足し引きを一杯行うから浮動小数点演算の誤差が一杯乗る

だからだそうだ。

参考

• Divide and Conquer | Set 5 (Strassen's Matrix Multiplication) - GeeksforGeeks

Evernoteとmarkdownで幸せになった話

最近 (と言っても結構前からほそぼそと使っていましたが) ノートや簡単なレポートやこのブログを書く環境にevernoteを組み込んでみたので書いてみる。

今までは主にmarkdownで書いてpandocをかましてlatex経由でpdf化していました。mediawikiを出力したかったりhtmlが欲しかったりslideにしたかったりということもありましたが、全部pandocで変換していました。pandocは素晴らしい。基本的に入力はemacsで行っています。この方法は特に悪くないんですが、しいて言うなら全部localのパソコンで完結しているので電車の中でスマホで内容を確認したり推敲したりということが出来ません。以前はDropboxを使っていましたが、容量がいっぱいになってしまって最近使ってませんでした。

そこでevernoteです!!evernoteはスマホとパソコンとの間での連携が非常に簡単です。というかスマホのクライアントが優秀です。スマホからテキストをいじる用途ではDropboxよりずっと使いやすいです。以前からevernoteは使っていましたが、evernoteはemacsで編集できません。 (余談ですが、以前はevernote-modeというものがあって割と便利でしたが今はもうAPIが変わったとかで動きません。)emacsで編集できないとなるとストレスが貯まります。このままでは死んでしまいます。

そこでgeeknoteというものがあります。geeknoteはevernoteをcliで操作できるすぐれものです。好きなエディタでevernoteを編集することができます。勿論editorにはemacsclientを登録します。そして、なんとgeeknoteではevernoteをmarkdownにして扱います。つまり、

スマホ -- evernoteアプリ --- evernote --- emacs --- markdown --- latex,html,...

という風にevernoteで何でも書けます。素晴らしいこれで何でもできますね。ちなみにこのブログを書く際にはgeeknote経由でmarkdownで出力したあとstackedit経由でBloggerに投稿しています。

FlycheckでVHDLのシンタックスチェック

FlycheckはEmacsでコードを書いている途中にリアルタイムでシンタックスチェックやコーディングスタイルのチェックを行ってくれる便利な拡張機能です。Flymakeと似ていますが、デフォルトで多くのシンタックスチェックが書かれています。僕は以前はFlymakeを使っていましたが、大体の言語でデフォルトの設定割とつかえるということと、自分でruleを書くのもFlymakeほどではないがそこまで難しくないのでFlycheckに乗り換えました。

僕は学科の課題などでVHDLを書くことがありますが、VHDLは比較的マイナーな言語だからか、無料でない処理系が多いからかFlycheckのルールがありませんでした。だから作りました。GHDLのシンタックスチェック機能を使いました。

最後のadd-hookのところでvhdl-modeでデフォルトでvhdl-ghdlのcheckerが使われるようになります。