Posts Issued in March, 2019

FSMのcall, returnメカニズム

posted by sakurai on March 31, 2019 #94

前記事の共通シーケンスの続きとなります。

FSMのcall, returnメカニズムとして、returnレジスタを設置し、caller側で戻り先ステート(通常は現ステートの次)をreturnに格納しておいて、calleeを呼ぶ機構にしていることは、前記事で記載しました。

単純な場合はこれで動作しますが、callが2段以上になると、returnレジスタが1段であるため、returnレジスタの退避等が必要になります。言うまでもなくプロセッサではスタックがこの自動化を行うわけで、プロセッサの場合の疑似コードを書くと次のようになります。

call CALEE;
:
CALEE:
:
return;

コール、リターンの動作的は、32bitプロセッサの場合、

rs[--sp] ← PC + 4;
PC ← CALEE;
:
CALEE:
:
PC←rs[sp++];

FSMの場合はPCはstateレジスタに相当しますが、それを退避するRS(リターンスタック)配列を設置し、SP(スタックポインタ)も設置します。とはいえ、ハードウェアでありリカーシブコールがあるわけでもないため、4段程度の簡素なスタックとします。2bitですがSPも実装します。実際にはreturnを除いて2段で済んだので(トータルで3段)、SPは1bitとしています。

さらに、上記のようにプリディクリメント、ポストインクリメントの処理とせず、ポスト処理のみとします。その理由はサイクルをかければプリ処理も可能ですが、Verilogが遅延代入であることから、簡単のためポスト処理のみとしています。

また、通常のスタックがpush down(積むと上から下にスタックが伸びる)であるのに比べて、実装するスタックは本当のスタック(地面に積むため、下から上に伸びる)にします。これはどちらでもコストは同等です。

以上のような設計だと、FSMのコールは、図94.1のような疑似コードとなります(caller saved)。

図94.1
図94.1 コールの疑似コード

これは全ての場合に動作しますが、リーフコールが多いのにも関わらず、リーフではスタックは不要です。従って、call先を見分ける必要はありますが、コードの効率化を考えて呼び出しをリーフ(緑)コールと非リーフ(赤)コールに分け、リーフをコールする際は以下の図のようなコードを用います。

図94.2
図94.2 リーフコールの疑似コード

これは、元から使用していたコードと同じものとなります。returnを破壊する一般FSMを赤、returnを破壊しないリーフFSMを緑で表しています。

今回はcaller savedで実装しましたが、callee savedのほうが若干容易かもしれません。caller savedでは呼ぶ前にcalleeがreturnを壊すか壊さないかを調べてからcallしなければならないのに比べて、callee savedであれば、全てreturnレジスタに入れてcallし、callee側でさらに呼ぶときは(つまりreturnを壊す場合は)スタックに入れるという流れであるためです。


左矢前のブログ 次のブログ右矢

posted by sakurai on March 24, 2019 #93

FusionPCBにオーダーしていた基板が届きました。以前の設計時のブログの続きです。

非常に小さい基板で、以下に基板の100円硬貨との比較写真を示します。基板業者は前回と同じFusionPCBで、今回はOSCという速達配送業者を利用して9.9USDでした。基板のみで製造に7.94日、OSCによる配送にシンセンから日本まで3.13日かかっています。シンガポール郵便よりはだいぶ早いですね。9.9USDの内訳は、7.9USDが基板制作代、2.0USDがOSCの配送料のようです。

前回はソルダーレジストを白で製造しましたが、今回は黒にしてみました。Ultra96toPMODボードもオーダーしています。レベル変換ICのみSMDだったので、手ハンダはマイクロスコープ下のハンダ付け作業となり厳しいため、レベル変換ICのみ実装もオーダーしました。

図93.1
図92.1 基板写真

これに部品を実装したものを次の図に示します。

図93.2
図92.2 基板に部品を実装した

UltratoPMODボードに取り付けて正常に動作することを確認しました。


左矢前のブログ 次のブログ右矢

posted by sakurai on March 21, 2019 #92

最急降下法は問題があります。例えば、 $$f(x_1,x_2,x_3)=x_1^2+\frac{x_2^2}{20}+x_3^2$$ のような関数があったときの収束曲線を見てみると次のような図になります。

図92.1
図91.1 座標位置の推移

こうなるのは、出発点から見て、関数の最小値(あるいは極小値)のある方向が、出発点の最も傾斜が急な方向と、必ずしも一致しないためです。

前述のように、一段のニューロンだとフィッティングに制限がありますが、さらに隠れ層のレイヤを加え、活性化関数の非線形性を導入することで、より自由な関数へのフィッティングが可能となります。

フィッティングをどのように実施するかですが、バックプロパゲーションを行います。バックプロパゲーションは、結果値が正解値とどれだけ乖離しているかを損失関数により評価し、それを各レイヤの重みベクトル$\boldsymbol{w}$に変換して、後段から前段に向かって伝えるものです。

このときに勾配テンソルが偏微分のチェインルールにより、後段から前段に向かって次々に簡単に求められるところがミソです。


左矢前のブログ 次のブログ右矢

posted by sakurai on March 5, 2019 #91

最急降下法

最適化の手法として最急降下法がしばしば用いられます。本来は、n次元ベクトル空間でのコスト関数の最小解が知りたい場所ですが、最小解を解くことは困難なので、極小解を求めます。出発点のまわりの谷底を見つけるわけであり、谷に下っていく方法のひとつとして、最も傾斜のきつい方向に降りることを最急降下法と呼びます。

最も勾配の大きい方向ベクトルを求めるため、以下の式のようにベクトル要素の偏微分をとるハミルトニアン演算子を使用します。 $$\nabla f=\left(\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},\frac{\partial f}{\partial x_3}\right)$$ このハミルトニアン演算子を用いると、最急降下法による変位ベクトルは以下のように簡略に記述できます。 $$\varDelta\boldsymbol{x}=-\eta\nabla f$$ ここで$\eta$は正の小さい数、例えば0.1とします。これは学習率と呼ばれます。

これを具体的に見てみます。例えば、 $$f(x_1,x_2,x_3)=x_1^2+x_2^2+x_3^2$$ という関数があるとき、その偏微分は $$\frac{\partial f}{\partial x_1}=2x_1, \frac{\partial f}{\partial x_2}=2x_2, \frac{\partial f}{\partial x_3}=2x_3$$ となります。点$(1.0, 2.0, 3.0)$から開始して最急降下法による漸化式をExcelで実行させてみました。

繰り返し回数 $x_1$ $x_2$ $x_3$ $\frac{\partial f}{\partial x_1}$ $\frac{\partial f}{\partial x_2}$ $\frac{\partial f}{\partial x_3}$ $\Delta x_1$ $\Delta x_2$ $\Delta x_3$
0 1.000 2.000 3.000 2.000 4.000 6.000 -0.200 -0.400 -0.600
1 0.800 1.600 2.400 1.600 3.200 4.800 -0.160 -0.320 -0.480
2 0.640 1.280 1.920 1.280 2.560 3.840 -0.128 -0.256 -0.384
:
41 0.000 0.000 0.000 0.000 0.000 0.001 -0.000 -0.000 -0.000
42 0.000 0.000 0.000 0.000 0.000 0.001 -0.000 -0.000 -0.000
43 0.000 0.000 0.000 0.000 0.000 0.000 -0.000 -0.000 -0.000

のように、43回目で偏微分が全て小数点3桁までゼロとなり、局所最小値$(0.0, 0.0, 0.0)$が求められました。図91.1にこの座標$(x_1, x_2, x_3)$の推移を示します。偏微分で求めた勾配を逆に下っていく様子が現れています。

図91.1
図91.1 座標位置の推移

前稿のシグモイドニューロンを多層化することにより、任意の分類が行えるようになります。


左矢前のブログ 次のブログ右矢

Neural NetworkをFPGAに実装する

posted by sakurai on March 1, 2019 #90

Neural Network (以下NN)の理論を確認していきます。以下にシグモイドニューロンの図を示します。

図90.1
図90.1 シグモイドニューロン

図90.1のように入力値$\boldsymbol{x}$及び係数$\boldsymbol{w}$をそれぞれn次元ベクトルとし、その積が閾値$\theta$より大きい時に発火する場合、活性化関数をシグモイド$\sigma(x)$として、

$$y=\sigma(\boldsymbol{w}\cdot\boldsymbol{x}-\theta)$$

のように表せます。ここで、$-\theta=b$(bはバイアス)とおけば、

$$y=\sigma(\boldsymbol{w}\cdot\boldsymbol{x}+b)$$

となります。このシグモイド関数$\sigma(x)$は、

$$\sigma(x)=\frac{1}{1+e^x}$$

で定義され、その微分は、シグモイド関数自身を用いて

$$\sigma'(x)=\sigma(x)\left(1-\sigma(x)\right)$$ と表せます。シグモイドは微分が簡単な形で表されるので、学習時のバックプロパゲーションにおいて非常に便利な性質です。一方、勾配消失の問題があることから、近年は使用されず、ReLUにとってかわられています。

図90.2
図90.2 シグモイド関数

左矢前のブログ 次のブログ右矢