FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages/

ゼロから作る量子コンピュータ・シミュレータ(3. 量子回路で3ビット加算器を作ろう)

前回は半加算器が完成した。という訳で、これを拡張させて全加算器を作成し、さらにこれを数珠つなぎにして3ビットの加算回路を作ろう。

量子回路で全加算器を作ろう

量子回路を使って全加算器を作るにはどうしたらよいのか、少し検索するとすぐ回路を見つけた。 以下のように構成すれば全加算器を作ることができるらしい。

f:id:msyksphinz:20180922164723p:plain
図.  a+b+c_\text{in} = s, c_\text{out} の全加算器

これは私が開発している量子コンピュータシミュレータを使えば、以下のように表現できる。

void FullAdder(Qbits *qbits, int a_idx, int b_idx, int c0_idx, int c1_idx)
{
  qbits->CCNot(a_idx, b_idx, c1_idx);
  qbits->CNot (a_idx, b_idx);
  qbits->CCNot(b_idx, c0_idx, c1_idx);
  qbits->CNot (b_idx, c0_idx);
}

これだとbの値は最終的に崩れてしまうのだけれども、使わないので良しとする。

3ビットの加算器を作ろう

3ビットの加算器を作るためには、この全加算器を3つ並べれば良いわけだ。 もっとも単純に作るためには以下のようにする。 ちなみに、各計算毎にキャリーを保持するために量子ビットを用意している。 なので、3ビットの加算器を作るために用意したビットは、 - 3ビットで表現される入力a - 3ビットで表現される入力b - 4ビットの、答え兼carry-bitを保持するための答えc

という訳で、3+3+4ビットで10ビット必要である。この時点で内部的には 1024\times 1024の行列計算が行われるわけで、こりゃ確かに大変だ。。。

f:id:msyksphinz:20180922165310p:plain
図. 3ビット量子加算回路

一度全加算器を作ったので、これを並べるだけである。 量子ビットは10ビット用意して、{s[3:0], b[2:0], a[2:0]}とした。なので、最後に6ビットシフトしてs[3:0]のみ出力している。

      Qbits qbits (b << 3 | a, 10);
      FullAdder (&qbits, 0, 3, 6, 7);
      FullAdder (&qbits, 1, 4, 7, 8);
      FullAdder (&qbits, 2, 5, 8, 9);
      int res = qbits.Measure();
      res = res >> 6;
      printf ("%x\n", res);

加算回路の実行

とりあえず全部回してみる。目視だが間違いがあればすぐに分かるはずだ。

  for (int a = 0; a < 8; a++) {
    for (int b = 0; b < 8; b++) {
      printf ("%x + %x = ", a, b);

      Qbits qbits (b << 3 | a, 10);
      FullAdder (&qbits, 0, 3, 6, 7);
      FullAdder (&qbits, 1, 4, 7, 8);
      FullAdder (&qbits, 2, 5, 8, 9);
      int res = qbits.Measure();
      res = res >> 6;
      printf ("%x\n", res);
    }
  }

実行すると以下のようになった。ちゃんと動いているな。

$ ./qbit_simulator
0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
0 + 3 = 3
0 + 4 = 4
0 + 5 = 5
0 + 6 = 6
0 + 7 = 7
1 + 0 = 1
...
7 + 4 = b
7 + 5 = c
7 + 6 = d
7 + 7 = e

RISC-V Day Tokyo 2018 / Fukuoka で登壇します

f:id:msyksphinz:20180921223849p:plain

RISC-V Day Tokyo 2018が10/18(木) に開催されます。私はRISC-Vを支える技術周辺、エコシステム周りを発表する予定です。 15分しかしゃべらないのですが、興味のある方はどうぞ。

tmt.knect365.com

やっぱりメインはRISC-V Readerの日本語訳の配布、そしてDavid Ditzel氏が来日して開発中のRISC-Vプロセッサについて登壇される予定です。 またRISC-Vの開発の中心であるKrste Asanovic氏、Andrew Waterman氏も来日されます。いろいろお話が聞けるチャンスです。

ちなみに、1週間前でもないのに今頃告知をしているかというと、今日09/21まで、参加費が安くなるEarly Accessの期間中だからです。 投稿されてから1時間くらいしか残されていないけど、参加したい人は早く参加登録を!!今なら$50で参加可能です。

なお、10/20(土)にはIEEE MICRO51のワークショップとしてRISC-V Dayが開催される予定です。 こちらは西日本在住で東京に来られない方、IEEEの会員の方は是非どうぞ。MICROとの併設なので参加費めっちゃ高いですけど。

f:id:msyksphinz:20180921225219p:plain

ゼロから作る量子コンピュータ・シミュレータ(2. 複数量子ビットをモデル化して加算回路を作ろう)

前回は1量子ビットC++でモデル化したのだが、それだけではほとんど何も表現出来ないので複数量子ビットに拡張したい。

複数量子ビットが表現できるようになれば、まずは例として加算器を動かしてみよう。 半加算器と全加算器が実現できればかなり面白い。

量子計算に大規模なコンピュータが必要な理由

最初は複数量子ビットを表現するのに量子ビットの数に線形比例するサイズの配列を用意すればよいのかと思っていたが、 考え方を完全に勘違いしていた。

そもそも量子ビットの表現には\alpha, \betaの2種類が必要というところから始まる。 量子ビットが0であるということは\begin{pmatrix}
\alpha \\
\beta
\end{pmatrix} = \begin{pmatrix}
1 \\
0
\end{pmatrix}
であり、一方で量子ビットが1であるということは\begin{pmatrix}
\alpha \\
\beta
\end{pmatrix} = \begin{pmatrix}
0 \\
1
\end{pmatrix} であるということを示している。 これはつまり量子ビットの1ビットを表現するために空間としては2通り必要と言う事である。 「0である場合」の量子ゲートの処理と「1である場合」の量子ゲートの処理が一度に表現できる。

つまり、上記の1量子ビットに対して2\times 2の行列積を適用すると言う事は「量子の状態はわからないけれども、0にときはこっちの計算、1のときはこっちの計算を適用するよ」ということを同時に表現しているに等しい。

例えば、量子を向きを反転させるゲートだと$$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} \alpha \\ \beta \end{pmatrix}$$ という行列を適用するが、量子ビット\begin{pmatrix}
\alpha \\
\beta
\end{pmatrix}

  • 上側の要素は量子が0であることを示す。
  • 下側の要素は量子が1であることを示す。

というようにデコードできるとする。 上記のゲートを適用すると\begin{pmatrix}
\beta\\
\alpha
\end{pmatrix} となり、量子が0である確率と1である確率は反転する。

このように考えると、量子状態の表現では、量子ビットの数が増えるとその量子の状態を示す数だけ行列の大きさが増えると言う事がわかる。 つまり、

  • 2量子ビットの場合 : 00, 01, 10, 11 の4状態 →行列のサイズは4
  • 3量子ビットの場合 : 000, 001, 010, 011, 100, 101, 110, 111 の8状態 → 行列のサイズは8

となり、量子ビットの数がn_qbitsであるとすると、シミュレータ上で確保しなければならない行列のサイズは 2^\text{n_qbits}となり指数関数的に増大する。 これが例えば50量子ビットになると2^{50}となり膨大な空間が必要なため、メモリを節約しつつコンピュータ上で計算する方法が必要不可欠となる訳だ。(といってもかなり疎行列なので圧縮する方法は沢山ありそうだが)

複数量子ビットC++で表現しよう

量子ビットを表現する原理が少しわかってきたので、次にこれをどのようにプログラムで表現するか考えた。 基本的には、nビットの量子ビットを定義する場合、2^{n}長の配列を定義するのがよさそうだ。 配列の各要素には、量子がその状態をとる確率が入るという理解で良い気がする。

理解があいまいなのだが、複数量子ビットを表現する場合は行列の値にはどのような制限があるのだろうか? 1量子ビットだと、ブロッホ球上で\alpha^{2}+\beta^{2}=1という空間内に収まっている必要がある (重ね合わせの状態だと\alpha=\dfrac{1}{\sqrt{2}}, \beta=\dfrac{1}{\sqrt{2}}とか)。

これが複数量子ビットになるとどうなるんだ? 基本的にはブロッホ球が複数あるとして、それを1つの行列で表現したときにどのように制約を付け加えればよいのか良く分からない。

2018/09/22 追記。複数量子ビットの場合、それぞれの量子ビット\psi_iと表現すると、制約は\sum \psi_{i}^2 = 1 となるらしい。 コメントで教えていただいた。ありがとうございます。

複数量子ビットを表現するためにQbitsクラスを定義した。

class Qbits {
  std::complex<double> *m_comp_amp;
  const size_t m_size;

コンストラクタでは量子ビットの初期値と、量子ビットのビット長を指定する。

  Qbits (uint8_t val, const size_t size)
      : m_size(pow(2, size))
  {
    m_comp_amp = new std::complex<double>[m_size];
    for (size_t i = 0; i < size; i++) {
      m_comp_amp[i] = 0.0 + 0.0i;
    }
    m_comp_amp[val] = 1.0 + 0.0i;
  }

例えば3ビットの量子ビットを定義して、初期値が4である場合は配列の4番目が1.0で、それ以外は0.0とする。

複数量子ビットに採用する量子ゲートを作ろう

さて、複数量子ビットが定義できたのでさっそく何かしたい。 まずは半加算器を作る工程を考えて、必要なゲートを定義することにする。

半加算器は一般的に以下のような量子回路で定義されるらしい。

f:id:msyksphinz:20180920230051p:plain
図. 半加算器

ここでCCNOTはトリフォゲートと呼ばれる。詳しくはWikipediaを参照のこと。 要するにある量子ビットを反転させるときに、その量子ビット以外の量子ビットがすべて1ならば反転し、そうでないときは反転しない。

トフォリゲート - Wikipedia

f:id:msyksphinz:20180920230146p:plain
図. トフォリゲートの行列表現 (https://ja.wikipedia.org/wiki/トフォリゲートより抜粋)

一方でCNOTはこれの2ビット版である。2量子ビット(q1, q0)において、q1が1ならばq0が反転し、q1が0ならばq0は反転しない。

行列式では下記のように表現できるが、3ビット以上の量子ビットにも対応させたいことと、 反転するターゲットの量子ビットと残りの2量子ビットを指定する必要がある。

このため、CCNot()では3引数を取り、

  • 反転のターゲットとなる量子ビットのインデックス: v_idx
  • 反転の判断をするための量子ビットのインデックス : c0_idx, c1_idx

とした。CNOTはその特殊版である(c0_idx == c1_idx)。

f:id:msyksphinz:20180920231536p:plain
図. 3量子ビットにおけるCNOT(Q1, Q0)
f:id:msyksphinz:20180920231739p:plain
図. 3量子ビットにおけるCNOT(Q2, Q0)
f:id:msyksphinz:20180920231728p:plain
  void CNot (int c_idx, int v_idx) {
    CCNot (c_idx, c_idx, v_idx);
  }
  void CCNot (int c0_idx, int c1_idx, int v_idx) {
    std::complex<double> *new_comp_amp = new std::complex<double>[m_size];

    uint8_t c_bitmask = (1 << c0_idx) | (1 << c1_idx);
    uint8_t v_bitmask = 1 << v_idx;
    for (int idx = 0; idx < m_size; idx++) {
      int act_idx = idx;
      if ((idx & c_bitmask) == c_bitmask) {
        act_idx = idx ^ v_bitmask;
      }
      new_comp_amp[act_idx] = m_comp_amp[idx];
    }
    for (int idx = 0; idx < m_size; idx++) {
      m_comp_amp[idx] = new_comp_amp[idx];
    }
  }

たぶんもっと簡単に実装できると思う。プログラミング力が無い。。。 要するにbitmaskとなっているビットがすべて1であれば、ターゲットのビット位置を反転する。

勘違いしがちだが値を反転するのではなくて、配列の要素を入れ替える。 例えば、3ビットの量子ビット[xyz]=[110]で、反転するターゲットの量子ビットzとする。 判断を行うxyの2ビットが両方1なので、zは反転するのだが、あくまで8要素(3ビットの量子ビットなので) [110](=6)[111](=7)の要素を入れ替えるだけなのだ。 Wikipediaに乗っている8\times 8の配列はまさにそれを示している。

量子ビットを使って半加算器を作ろう

というわけで、さっそく作ったCNot()CCNot()を使って半加算器を構成した。

  for (int val = 0; val < 4; val++) {
    Qbits qbits(val, 3);
    qbits.CCNot(1, 0, 2); // 量子ビット0,1の値によって、量子ビット2を反転させる
    qbits.CNot(0, 1);     // 量子ビット0の値によって、量子ビット1を反転させる
    printf("qbit val = %d\n", qbits.Measure());
  }

3量子ビットを定義した。

  • ビット0 : 入力a
  • ビット1 : 入力b, かつ計算後にはsum
  • ビット2 : 計算後にcarryが入る

とする。入力を0から3まで変えて計算すると、それぞれ以下のようになった。

qbit val = 0
qbit val = 3
qbit val = 2
qbit val = 5

そっけない結果だが、

  •  0+0 : sum=0, carry=0([000]->[000])
  •  0+1 : sum=1, carry=0([001]->[011])
  •  1+0 : sum=1, carry=0([010]->[010])
  •  1+1 : sum=0, carry=1([011]->[101])

というビットが正しく表現できている。半加算器の完成だ。

ゼロから作る量子コンピュータ・シミュレータ(1. 1量子ビットの表現)

次世代計算機講座に参加して、量子コンピュータについて俄然興味がわいてきた。

手っ取り早く量子コンピュータを試すためには、最近になっていろいろ手段が出てきている。

MicrosoftからはQ#、GoogleからはフレームワークとしてCirqがリリースされている。 これらの環境を使うのもいいけれども、あまり情報もないし折角なので自分で作ってみたい。

という訳で量子コンピュータシミュレータを1から自分で作るにはどうすればよいのか調べてみる。

参考にしたのは、次世代計算機講座で講演なされた京都大学の藤井啓祐先生の資料と、同じく藤井先生がCQ出版のInterfaceに寄稿された量子コンピュータC言語モデルだ。 Interfaceに分かりやすい形で量子コンピュータのモデルが解説されているのは非常にありがたい。

という訳で、まずはInterfaceの記事のコードをどんどんコピペしていく。

1量子ビットの表現

1量子ビット複素数の変数として\alpha, \betaの組で表現されるので、複素型として2変数を用意する。

class Qbit {
  double _Complex m_comp_amp[2];

1量子ビットに対する操作

\alpha, \beta がどの程度傾いているかにより、0に近いか1に近いかが決まる。 そのランダム性は観測時に影響を与える。 ここでは、 0.0<= val <1.0 の乱数を生成して、その値と\alpha, \betaの大小で最終的な0/1を決める。

  int Measure () {
    double rand_val = rand() / static_cast<double>(RAND_MAX);
    double measure_val = pow(cabs(m_comp_amp[0]), 2);
    if (rand_val < pow(cabs(m_comp_amp[0]), 2)) {
      m_comp_amp[0] = 1;
      m_comp_amp[1] = 0;
      return 0;
    } else {
      m_comp_amp[0] = 0;
      m_comp_amp[1] = 1;
      return 1;
    }
  }

各種ゲートの適用

とりあえずは、アダマールゲートと回転ゲートを作ってみる。 アダマールゲートは以下のように表現される。

$$ \dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} $$

次に、回転ゲートは以下のように表現される。

$$ \dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{pmatrix} $$

というわけで、それぞれQbitクラスのメソッドとして以下のように表現した(というかかなりコピペした)。

  void Hadamard () {
    m_comp_amp[0] = (m_comp_amp[0] + m_comp_amp[1]) / sqrt(2);
    m_comp_amp[1] = (m_comp_amp[0] - m_comp_amp[1]) / sqrt(2);
  }

  void Rotate (double theta) {
    m_comp_amp[0] = m_comp_amp[0];
    m_comp_amp[1] = (cos(theta) + 1.0i * sin(theta)) * m_comp_amp[1];
  }

回転ゲートの動作確認

という訳で、簡単な1量子ビットとそれに適用できるゲートは作ったので、藤井先生の例に出てくる1量子ビット演算を実行してみる。

f:id:msyksphinz:20180919003653p:plain

ここで、回転ゲートの回転量を \dfrac{2\pi}{10}ずつ細切れにして回転させて、1が出現する確率を測定する。

出現する確率は、1000回同様の量子計算を繰り返して測定する。つまり、以下のようになる。

  for (int trial = 0; trial <= 10; trial++) {
    int count_one = 0;
    for (int count = 0; count < 1000; count++) {
      Qbit q_bit;
      q_bit.SetZero();
      q_bit.Hadamard();
      q_bit.Rotate(2 * M_PI * 0.1 * trial);
      q_bit.Hadamard();

      if (q_bit.Measure() == 1) {
        count_one++;
      }
    }
    printf ("Trial = %d : count_one = %d\n", trial, count_one);
  }

上記のプログラムを実行すると、以下のようになった。

$ ./qbit_simulator
Trial = 0 : count_one = 277
Trial = 1 : count_one = 340
Trial = 2 : count_one = 515
Trial = 3 : count_one = 737
Trial = 4 : count_one = 918
Trial = 5 : count_one = 982
Trial = 6 : count_one = 914
Trial = 7 : count_one = 748
Trial = 8 : count_one = 495
Trial = 9 : count_one = 331
Trial = 10 : count_one = 278

グラフを書くと、以下のようになった。

f:id:msyksphinz:20180919003956p:plain

綺麗な三角関数が描けている。正しく計算できているようだ。

とりあえずはここまで。

NVDLAのConvolution DMAが実行する畳み込みの手順の解析

NVDLAというか、畳み込み演算をどのようにハードウェアで実現するかということをさらに掘り下げている。

  • NVDLA : Unit Description

Unit Description — NVDLA Documentation

NVDLAのConvolution DMAは、以下のような画像に対して入力画像とカーネルを畳み込むことを考える。ここではチャネルについては無視している。

上記の図における、各パラメータは以下の通りである。

  • Top Padding(TP) : 画像データに対して上部に何ピクセルパディングを入れるか。
  • Bottom Padding(BP) : 画像データに対して下部に何ピクセルパディングを入れるか。
  • Left Padding(LP) : 画像データに対して左部に何ピクセルパディングを入れるか。
  • Right Padding(RP) : 画像データに対して右部に何ピクセルパディングを入れるか。
f:id:msyksphinz:20180917161117p:plain
図. 画像畳み込みの前提条件パラメータ

これに対して、カーネルの畳み込みを行うと以下のようになる。ここでSXSYは畳み込みのストライド数である。 それぞれSX=4SY=3として表現している。

W', H' というのは畳み込み後の画像のサイズであるが、これを以下のように表現している。

  • W′=LP+W+RP−S′SX+1
  • H′=TP+H+BP−R′SY+1

ただし、

  • S′=(S−1)\times DX+1
  • R′=(R−1)\times DY+1

畳み込みをしていくのは以下のようなイメージだ。ここではX方向のストライド数=4, Y方向のストライド数=3としている。

f:id:msyksphinz:20180917161941p:plain
図. 画像に対する畳み込みの適用。

NVDLAにおける畳み込み演算

NVDLAにおけるアトミック操作

アトミック操作は重みカーネルの1ドットに対して掛け算を実施する計算に相当する。

f:id:msyksphinz:20180917163050p:plain
図. カーネルK0 - K15 に対してドット0を掛け合わせる。

これは以下の計算をしていることに相当する。

  • [0] × [00](K0)
  • [0] × [00](K1)
  • [0] × [00](K2)
  • [0] × [00](K3)
  • [0] × [00](K15)

ここでは、カーネルの数を1として考えてみる。そうすると、上記の図における画像の座標0と、カーネルの座標00の乗算を行っていることに相当する。

f:id:msyksphinz:20180917164000p:plain

NVDLAにおけるストライプ操作

ストライプ操作は、上記のアトミック操作を連続して実行することに相当する。カーネルの位置は変えずに、入力画像の位置をずらす。

先ほどの式を拡張して考えると、上記の図における画像の座標0から座標21までの四角形の16要素と、カーネルの座標00の乗算を行っていることに相当する。

f:id:msyksphinz:20180917164204p:plain

NVDLAにおけるブロック操作

ブロック操作は、上記のブロック操作をさらに連続して実行する。画像の位置と、カーネルの位置を変えながら演算を行う。カーネルのサイズは3\times 3なので、画像の位置を0,1, 2, 6, 7, 8, 12, 13, 14とずらす。 一方でカーネルの位置も、00, 01, 02, ... 08 までずらす。

先ほどの式を拡張して考えると以下のような演算を実行している。

f:id:msyksphinz:20180917164548p:plain

最終的な畳み込みは以下のように行方向に加算することで計算できる。

f:id:msyksphinz:20180917165553p:plain

NVDLAの内部構造調査(10. NVDLAのConvolution DMA)

NVDLAの内部構造についてもう少し詳しく解析したいのだが、割としっかりと解説してあるページがあったので読み進めていこう。

参考ににしたのは以下。っていうかNVDLA本家のページである。 今回はConvolutionのためのモジュール。Convolution DMA(CDMA)である。

  • Unit Description (NVDLA)

Unit Description — NVDLA Documentation

畳み込みDMA

概要

畳み込みDMA(CDMA)は畳み込みパイプラインを実行するパイプラインステージである。SRAM/DRAMからデータをフェッチしデータを畳み込みエンジンの処理できるようにバッファ(Convolution Buffer: CBUF)に格納する。サポートしている入力フォーマットは:

  • ピクセルデータ
  • 特徴データ
  • 圧縮・非圧縮の重みデータ
  • WMB
  • WGS

CDMAからAXIに2つのチャネルが接続されている。重みデータの読み込みチャネルと、データ読み込みのためのチャネルである。上記の入力フォーマットをフェッチするために、チャネルは上記のフォーマットのために構成してある。以下の表には、読み込みチャネルにマッピングするための入力データフォーマットを示してある。

入力フォーマット Image Case Uncompressed Feature Case Uncompressed Weight Case Compressed Weight Case
Pixel data data channel NA NA NA
Uncompressed feature data NA data channel NA NA
Uncompressed weight NA NA weight channel NA
Sparse compressed weight NA NA NA weight channel
WMB NA NA NA weight channel
WGS NA NA NA weight channel

畳み込みDMAはメモリの読み込みリクエストしか発行しない。すべてのメモリリクエストは64-byteのアドレスにアラインされて発行される。

../../../_images/ias_image17_cdma.png

図 53 畳み込みDMA

CDMAは3つのサブモジュールから構成されており、ピクセルデータと特徴データをフェッチする: CDMA_DC, CDMA_WG, CDMA_IMGである。これらのサブモジュールの役割は似通っているが、データをCBUF RAMへ書き込むか順番が異なる。 どのような場合にも、サブモジュールのうちの1つがピクセル・特徴データをフェッチするためにアクティベートされる。

ここでは、CDMA_DCを例として取り上げる:

  • Convolution Bufferの空き領域をチェックする。
  • 読み込みトランザクションを生成する。
  • フェッチデータを共有バッファにキャッシュする。
  • 特徴キューブを正しい順番に整形する。
  • Convolution Bufferの書き込みアドレスを生成する。
  • CDMA_STATUSサブモジュール内のConvolution Bufferの状態をアップデートする。

Convolution DMAはWinogradの処理を実行するために所望のエンジンを使用する。CDMA_WGはCDMA_DCと非常に似通った構造をしているが、Convolution Buffer内の最終的な特徴データの構造は異なっている。したがってCDMA_WGは特殊なフェッチシーケンスを持っている。さらに、CDMA_WGはWinogradチャネル拡張を事項している。

CDMA_IMGエンジンはピクセルデータを外部メモリからフェッチする。データフォーマットに応じてアドレスを生成し、ピクセルの要素の順番を変更してConvolution Bufferの適切なエントリに書き込む。CDMA_IMGの動作はCDMA_DCに似ているが、ピクセルデータを扱うというところが異なる。

CDMA_DCエンジンのみがマルチバッチモードをサポートしている。したがって、1つ以上の入力特徴データキューブを1つのHWレイヤでフェッチすることができ、性能を向上させることができる。最大バッチサイズは32である。

CDMAは重みのフェッチにも所望のエンジンを使用する: CDMA_WTである。CDMA_WTは他のDMAエンジンと比較するとシンプルであるが、同時に3つのRead steamをサポートしているところが異なる。もし入力重みフォーマットが圧縮されていないと、重みデータのみをフェッチする。もし重みフォーマットが圧縮されていると、WMBとWSGはすべてフェッチされる。重みフォーマットについては、Data Formats の項目を参照すること。

入力重みデータが圧縮されていると、2つのアービタが有効差化されてRead streamが読み込まれる。最初の重みラウンドロビンアービタが重みストリームもしくはWMBストリームのリクエストを受け付ける。次にそのアービトレーションの勝者がWGSの読み込みストリームと静的なアービトレーションを行う。WGSは常に高い優先度を持っている。最終的に勝利したリクエストが重みチャネルにデータフェッチリクエストを発行する。

CDMA_WTは可能な限り重みのフェッチが完了するか、Convolution Bufferのエントリが空いている限りConvolution Bufferを埋めようとする。

CDMAはCBUF中の重みバッファと入力データバッファの通信状態を管理している。CDMACSCには2つの状態コピーが存在している。データ要素が解放されたときに、2つのモジュールがアップデートとリリース情報を交換し、新しい特徴データ・ピクセルデータ・重みデータをいつフェッチするのかを決めている。

電力について

Convolution DMAはデータパス上にクロックゲーティングが実施されている。Convolution DMAのデータパスのクロックは、データが存在しないか、プログラムレジスタにおいてハードウェアレイヤが構成されていないときにゲーティングさえっる。CDMAレジスタファイルのサブモジュールはクロックゲーティングされないため、新しいコマンドは常に受け付けることができる。

Convolution Buffer

概要

Convolution Buffer(CBUF)は畳み込みパイプライン中のステージである。512KBのSRAMで構成される。SRAMCDMAモジュールからの入力ピクセルデータ・特徴データ・重みデータとWMBデータを読み取る。これにはConvolution Sequence Generatorモジュールを使用する。CBUFは2つの書き込みポートと3つの読み込みポートを持っている。

CBUFは32KBのメモリが16バンク用意されている。各バンクは512-bit幅であり、256エントリの2ポートのSRAMで構成されている。これらのバンクは3つの論理Circularバッファとして動作する。

  • Input data buffer
  • Weight buffer
  • WMB buffer
  • 入力データバッファ
  • 重みバッファ
  • WMBバッファ

重みフォーマットが圧縮されているとき、バンク15はWMBバッファとして割り当てられ、残りの2種類のバッファはバンク0~バンク14に格納される。重みフォーマットが圧縮されていないとき、WMBバッファはどのバンクにも割り当てられず、データバッファと重みバッファは16バンクのすべてを使用する。必要なバンク数が16よりも小さい場合は、残ったバンクは使用されない。

各バッファはCircularバッファとして使用される。新しい入力データ・重み・WMBはエントリアドレスを持っており、常に上位方向に加算される。もしアドレスが最大値に到達すると、0にラッピングされて0から再度インクリメントされる。

../../../_images/ias_image18_cbuf.png

図54 Convolution Buffer

電力について

Convolution Bufferにはデータバス中のレジスタに対してクロックゲーティングが適用されている。Convolution Bufferのデータパスは、アイドル状態の場合か、プログラマブルレジスタによりどのHWレイヤも割り当てられていないとき、SLCGによりクロックゲーティングされる。Convolution Buffer内のコンフィグレーションレジスタはクロックゲーティングされず、したがって常にレジスタをプログラムすることができる。

畳み込みシーケンスコントローラ

概要

畳み込みシーケンスコントローラ(CSC)は入力特徴データ、ピクセルデータ、重みデータをCBUFからConvolution MACユニットに転送する役割を持つ。畳み込みパイプライン部において、畳み込みシーケンスの計算及び制御を行うためのカギとなるモジュールである。

畳み込みシーケンスコントローラ(CSC)3つのサブモジュールから構成されている: CSC_SG, CSC_WL, CSC_DLである。図55を参照のこと。

CSC_SGは畳み込みシーケンスジェネレータである。このモジュールは畳み込み操作の制御シーケンスを生成する。

CSC_SGのフローは以下の通りである。

  1. CBUF中に十分なデータと重みが格納されるまでポーリングする。
  2. シーケンスパッケージを生成する。シーケンスパッケージには、重みパッケージをロードするシーケンスと、データをロードするシーケンスが含まれる。各パッケージは1つのストライプ操作として表現される。
  3. 2つのパッケージをFIFOに挿入する。
  4. 重みと特徴・ピクセルのための2つのカウンタである。ダウンカウンタである。
  5. カウンタが0になると、Convolution Accumulatorからの信号をチェックしてバックプレッシャをチェックする。
  6. 全ての状態がReadyであれば、適切な時間に重みとデータパッケージをCSC_WLとCSC_DLに転送する。

../../../_images/ias_image19_csc.png

図55 畳み込みシーケンスコントローラ

CSC_DLは畳み込みデータローダである。このモジュールは特徴・ピクセルローディングのシーケンスを実行する論理が入っている。このモジュールはシーケンスジェネレータからパッケージを受け取り、特徴・ピクセルデータをCBUFからロードしてConvolution MACに転送する。データバッファの状態を管理し、CDMAとやり取り行って状態を常に最新に保つ。Winogradモードのために、入力特徴データを変換するためにPRA(Pre-addition)も行う役割がある。

CSC_WLはConvolution Weight Loaderの略である。このモジュールは重みをロードするシーケンサの論理が入っている。シーケンスジェネレータからパッケージを受け取り、CBUFから重み情報を受け取り、必要な回答処理を行ってからConvolution MACに転送する。重みバッファの状態を管理し、CDMA_WTと通信を行って状態を最新に保つ。

電力について

畳み込みシーケンスコントローラはデータパス中のレジスタに対してクロックゲーティングが適用される。畳み込みシーケンスコントローラのデータパス中のクロックは、アイドル中であるかプログラマブルレジスタによって有効化されていない場合、クロックゲーティングが適用される。畳み込みシーケンスコントローラのサブモジュールのレジスタファイルはクロックゲートされないため、常に最新の情報を入力できる。

次世代計算機講座 <入門編> ~ゲート式量子コンピュータとアニーリングマシン~ に参加した

09/15に早稲田大学で行われた次世代計算機講座に参加した。

量子コンピュータについは何冊か本を読んでわかっているつもりだったのだが、独学の部分がほとんどなのでいろんな講演を聞いてみたいと思い参加した。

最初の京都大学の先生の話は量子コンピュータの基礎なので、私もYoutubeとか資料を読みまくってなんとなく分かっていた。 それ以降の量子アニーリング専用マシン・デジタルアニーラ等々までは詳しくは知らなかったので初耳の話が多かった。

ちなみに京都大学の先生の講義には、CQ出版のインタフェースも参考文献として出ていたのでもう一度読み直してみよう。

以下は私が講義中にとったメモ:


量子コンピュータ入門:基本原理からプログラミング環境まで 京都大学 藤井先生

多くのパタンを重ね合わせるが、高い確率で答えを出すためにはもう少し工夫が必要で、波の干渉による強めアイ・弱めあいを使って答えを算出する必要がある。

量子ビットの実現方法

量子コンピュータの種類

量子ビットの操作

アダマール変換。量子ビットをリンギング(重ね合わせ状態)させる操作。 アダマール演算を2回実行すると単位行列なので基本的にはそのままになるはず。 1回アダマール行列を掛けることにより重ね合わせになって確率が分散するはずなのだが、そうでないのが量子計算。

2量子ビットの演算

CNOT : Conditional Not

量子ビットは数が増えると表現できる数の種類が指数関数状に増える → 量子コンピュータの強いところ。

万能量子コンピュータ

CNOT / H / T の演算が実現できれば、万能量子コンピュータが実現できる。

観測も確率で表現されるので、内部の行列を適切に使用して確実に答えが観測できるように工夫する必要がある。

最近の動向

NISQ : 50~100量子ビットで、ノイズがあるけれども中規模の量子コンピュータ

大規模化を行うためには、ノイズ対策が不可欠。

アニーリングマシンの研究開発現状と使い方入門 早稲田大学 田中先生

アニーリング問題→組み合わせ問題を高速に解きたい。

イジングモデル

イジングモデルは磁石の相転移を書き下すことができる。

組み合わせ最適化問題の最適解=イジングモデル基底状態(最も安定した状態)

詳しくは https://quantum.fixstars.com を見てね。

0-1整数計画問題で、2次の項まで落とせていればイジングマシンに変換できる。

数分割問題の場合、集合1に属するものを-1, 集合2に属するものを+1と考えるとイジングモデルに変換できる。 分割点を最小化する問題は$\dfrac{1-s_is_j}{2}$として表現できる。 2つの項を足し算することで、ハミルトニアンを構成することができる。

組み合わせ最適化問題はすべての項に対して乗算を行う必要があるが、D-Waveの量子ビットネットワークはすべての量子ビットは接続されていない。したがってグラフを変換する必要がある。

https://www.rco.recruit.co.jp/career/engineer/blog/46/

富士通 デジタルアニーラの話 東さん

  • デジタル回路を使って、量子アニーリング問題を解決する → デジタルアニーラ(DAU)
  • 1024量子ビット・ビット完全結合が特徴。
  • 特徴
    • 局所解から脱出しやすいようなオフセットを挿入できる機能がある
  • 活用例
    • 投資ポートフォリオ
    • 生産管理スケジューリング
    • デジタルアニーラで、医療における放射線量の計算を高速化する

CMOSアニーリングマシンの概要 山岡さん

  • ナチュラルコンピューティング。物理現象を問題に写像する。

  • スパースなイジングモデルを作成した。これでは問題を写像するのが難しい。

  • 特徴
  • アニーリングの手法
    • ランドスケープに基づいて最適解を求める
    • ランダムジャンプにより局所解に陥ることを防ぐ。
      • 疑似乱数列をチップ内に入れていき、スピンの値を壊す。
  • 最大カット問題を解かせる。
  • CMOSアニーリングに量子アニーリングの手法を取り入れられないか?(第3世代)。