論理回路の高位合成について

# はじめに
この記事ではFPGA等の論理回路の設計手法の一つのカテゴリーである「高位合成」について概略を説明したいと思います。ただし、筆者の知る限りでも高位合成についてはさまざまな立場の人が各時代の視点で色々なことを語っているので、この記事もそんな中の一つの解釈を述べてるだけととって頂き、他の資料等も参考にして興味を持っていただけると幸いです。

# 論理回路設計について
まずWikipediaの英語の記事(日本語版はありませんでした)によると
https://en.wikipedia.org/wiki/High-level_synthesis
によると
「High-level synthesis (HLS), sometimes referred to as C synthesis, electronic system-level (ESL) synthesis, algorithmic synthesis, or behavioral synthesis, is an automated design process that interprets an algorithmic description of a desired behavior and creates digital hardware that implements that behavior.」
テキトーに訳してみると
「高位合成は時にはC合成、電子回路のシステムレベルの合成、アルゴリズムの合成、動作合成とも呼ばれますが、自動化された設計プロセスであり、望ましい振る舞いのアルゴリズム的な記述を解釈し、その振る舞いが実装された論理回路を作り出すものです。」

要するに「アルゴリズム的な記述をしたらそれが実現される」ということで、ソフトウェアの開発者がいつもやってるようにプログラムを書いたら言語処理系がそれを実行できるようにしてくれるということのようです。
(「合成」という言葉は「コンパイル」とほぼ同じ意味で使われていて、CPU等で実行できるものを出力するのがコンパイルで、ハードウェアになるものの場合は合成と言うのが一般的です。)

では、高位合成でない回路設計ではアルゴリズム的な記述をしてないのかという疑問が湧きますが、それを理解するための資料として論理回路を設計するための言語としてポピュラーなVerilog HDLとVHDLの記事をリンクしておきます。
https://ja.wikipedia.org/wiki/Verilog
https://ja.wikipedia.org/wiki/VHDL
また、これらの言語の足回りを理解するためには「レジスタ転送レベル(RTL)」
https://ja.wikipedia.org/wiki/%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF%E8%BB%A2%E9%80%81%E3%83%AC%E3%83%99%E3%83%AB
や「有限オートマトン」
https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3 の知識も必要なはずです。
これらをハードウェア記述言語(HDL)と呼ぶこともあるので、「ハードウェア記述言語」 https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%BC%E3%83%89%E3%82%A6%E3%82%A7%E3%82%A2%E8%A8%98%E8%BF%B0%E8%A8%80%E8%AA%9E も読んでみてください。
……どうでしょうか？アルゴリズムを書いているというよりはハードウェアとして利用可能な要素にマッピングする作業をしているという感じでしょうか？

# ソフトウェアの向けプログラミング言語からの回路設計
前節で説明したような回路設計手法を使う場合、アルゴリズムを意識すると同時にその実行環境が回路であるという制約を強く意識することが必要です。
では、一般のソフトウェア用のプログラミング言語ではそんなことはないといえるでしょうか？確かに多くの人や状況に対してアルゴリズムを直接を扱うのは楽になっているという点には多くの方が同意してくださると思います。
なんだか煮え切らない書き方をしてしまいましたが、ソフトウェア用のプログラミング言語の方がアルゴリズムを記述し易いとすると、論理回路の設計も同じプログラミング言語を使えば良いのではという発想がでてきます。そして、それを可能にするためにはそれらのプログラミング言語を受け付けて回路を合成するコンパイラ的なものを作ればよいということになり、そのようなツールを使った回路設計を「高位合成」と呼ぶことが一般的です。
そして、入力とするソフトウェア用のプログラミング言語としては歴史的な経緯もあってC言語が選ばれることが非常に多く、2000年頃から商用や研究用の処理系が登場してきています。
このため、「高位合成」===「C言語を用いた論理回路設計」という理解をしてしまってる人やコミュニティも多いようです。

![synth.PNG](https://qiita-image-store.s3.amazonaws.com/0/193078/44803c1e-3f71-c3ce-bc57-75fdcc54a37a.png)


# 高位合成の仕組みの例
ここでは高位合成の仕組みを簡単に説明します。例として次のコードを用います。

```
  int t = 0;
  for (int i = 1; i <= 10; ++i) {
    t += i;
  }
```
これを脳内でコンパイルした場合、人によって詳細は異なりそうですが、次のような疑似命令の列を得ることになります。

```
  t <= 0
  i <= 1
.L0
  c <= i - 10
  jn .L1
  t <= t + i
  i <= i + 1
  jmp .L0
.L1
```
実際のソフトウェア用の多くのコンパイラでもこのような感じの疑似命令の列を一度作ってからターゲットとなるCPUに存在する命令の列を出力します。
CPUはこの命令列から一つ一つの命令を読み込んで実行し、実行が終わったら次の命令を実行するという動作をします（内部的にはスーパースカラや投機実行になってますが）。
それに対し論理回路の計算は一般的にはクロック単位で動くステートマシンで記述するので、ここでもステートマシンを構成してみます。
(拙作の処理系Karutaではこのような形式で合成を行いますが、このやり方は必ずしも一般的なものではないので興味のある方は調べてみてください)
![fsm1.PNG](https://qiita-image-store.s3.amazonaws.com/0/193078/4423c856-9b17-cbf3-b159-4cee812a8ddb.png)
あるクロックでは一つの行の内容が実行されると解釈します。まず、この回路の動作はリセット状態から始まります。リセット状態が解除されると次のクロックで状態S1へ遷移します。
状態S1では代入命令を二つ同時に処理しています。CPUの場合はそれぞれは別の命令なので順番に実行される扱いになりますが（今時のCPUなら実際には同時に実行します）、論理回路の場合は明示的にタイミングを指定して同時に実行します。
次の状態S2ではi - 10をcに代入して、それが負かどうかで分岐を行っています。(よく見ると代入に 「=」「<=」を使い分けてますが、興味のある方はVerilogのブロッキング代入という概念について調べてみてください)
状態S3では2つの足し算を同時に行うため加算の列を2列分確保しています。これは回路中に加算器を2つ用意するという意味です。
そして、状態S2と状態S3のループが規定の回数実行されて状態S4で処理が終了します。

一般的な論理回路の設計ではこの作業を脳内やメモの上で行ってからハードウェア記述言語でのコーディングを行いますが、高位合成の場合は最初のコードから後は自動的に処理されてハードウェア記述言語が出力されます。

## 最適化の例
ここで状態S3で加算を2つ同時に行うために加算器を2つ用意していますが、もし回路面積が惜しい場合には状態S3を分割して1つの加算器を流用するという選択も可能です。
その場合の動作は次の表のようになります(S3はS3aとS3bに分離されています)
![fsm2.PNG](https://qiita-image-store.s3.amazonaws.com/0/193078/b20e158b-49f0-6e64-a80b-9a9c6ad2444e.png)

演算器の数は2個から1個に減りましたがループを一周するのに必要なクロック数は2から3に増えてしまいました。この変更が良いかどうかは利用者の状況や回路の性質に依存しますが、このような最適化を行うのも高位合成の処理系の非常に重要な役目です。

# 高位合成のメリットとデメリット
ここでは高位合成のメリットとデメリットをいくつか紹介したいと思います。

## コード量が減る
この記事の最初の説明ではアルゴリズムを記述できる(抽象度が高いという言い方をすることもあります)ことをメリットとして挙げましたが、端的に言うと細かいことを言語処理系に任せることができるので少ない記述で同じ回路を得ることができます。
これによって次のようなメリットがあります。

* コーディングの手間が減る
* 望ましい品質の到達するまでの手間が減る
* コード中のコメントが少なくても済む
* 実装仕様書的なドキュメントが少なくて済む
* テストの量も少なくて済む
* 何かを変更する時にコード内の変更も少なくて済む
  * 変更自体の手間が少ない
  * ドキュメント、コメント、テスト等の変更も少なくて済む
* 何かを変更する時のリスクが小さい
* チーム内等で(もしくは将来の自分に)コードを受け渡しする時の手間が減る

どうでしょうか？本当に実現したら素晴らしいですよね。

## 最適化をツールに任せることができる
前の節で最適化の例を挙げましたが、演算器の数や処理に必要なクロック数、あるいは回路全体の周波数を考慮してなるべく良い回路を作るというのは割と難しい作業です。
特に回路を変更して別の設定の方が良いかどうかを見る作業をする場合、実際に目標が達成できないリスクと新たなバグを作りこんでしまうリスクがあり、なるべく避けたいものです。
多くの高位合成のツールはこのあたりをパラメータを指定するだけで勝手にやってくれます。

## デバッグが辛い場合がある
多くのソフトウェア向けの言語処理系がアセンブラを出力するように高位合成の処理系はハードウェア記述言語を出力します。
しかしながらソフトウェアの場合はアセンブラを意識しないでデバッグを行えることが多いのに対し、（シミュレーターであれ実機であれ）デバッグを行う際にはハードウェア記述言語上でどうやって動いているのかを把握し、それが元の言語の記述の上でどんな意味を持っていたのか推測するスキルが必要になることが非常に多いです。

## 普及失敗の歴史がある
どの分野でもそうですが、新しい技術が登場してくると過大評価してすぐに取り入れたがる人と過小評価やスルーするのが妥当だと思う人がでてくるかと思います。
これ自体は業界の常なのでそれぞれの立場で会社や個人のリソースを適切に(全賭けからスルーまで)賭ければ良いのですが、高位合成の界隈では20年間にわたってそろそろ今度こそ本当に使えると言い続けてきたため楽観的な人、悲観的な人、スルーする派の人それぞれが煮詰まって筋金がはいってきて議論がしづらい場合があると感じる今日この頃です（筆者の気のせいなのかもしれませんが…）。
結局のところ自分で実際に使ってみてメリットが感じられるかどうかが大事で、その範囲で語るのことが必要な気がします。

## (多くの場合)C言語を書かないといけない
これはある時代まではメリットだったのですが、近年ではデメリットの側に数えても良いかと思います。
科学技術計算やビジネスの処理を除いたプログラミングの大半がC言語で行われていた時代にはアルゴリズムやデータ構造の実習はほとんどC言語で行われてきました。また、C言語はハードウェアに近いので論理回路の記述にも向いているとされていました。
しかしながら、ここで言う「ハードウェア」とはC言語のコードの実行に適した物であり、一つのアドレス空間を持ってコードとスタックとヒープとして使い、一つのプログラムカウンターがコード領域を動くことを前提にしています。このモデルを論理回路に当てはめるために様々な工夫(マクロや#pragma等やちょっとした言語拡張)がなされてきましたが、C言語の理解の上にそれらの工夫の意味の理解を積み重ねて回路が書きやすくなるかというと正直言って疑問です(そういう人がいること自体は否定しませんが…)。

最近はスクリプト言語をはじめとしてC言語以外の色々な言語の色々な考え方に触れたユーザーや言語処理系の実装者が増えてきており、また、大手のインターネットやソフトウェアの企業が自社製品のエコシステムのために独自言語を作って普及させることも増えてきているため、論理回路の設計手法にもその影響が出てくるのではないかと予想しています。

## 導入のコストが高い
余談：FPGA用ではなくASIC(専用チップ)用の高位合成ツールの場合、1ライセンス1年分で普通のエンジニアの人件費を超える値段がかかることも珍しくありませんでした。そんな場合にはライセンス更新の稟議が通らなくなった瞬間に設計資産がゴミになるリスクのあるギャンブルでした。

# 最後に
この記事では論理回路の高位合成の概要および現状について解説を試みました。
高位合成が実用的になるかも？という雰囲気が漂いはじめてから20年ほどの年月が経ちましたが、イマイチな普及具合なのが現状です。
安心して導入できる高位合成の処理系を手に入れるのは意外と難しいようで、ツールを作った会社が言ってることや売ってる物を受け入れるというだけではなく、どんな処理系が欲しくて、どんな処理系がどんなコストで実現可能かということについて業界の有志で幅広く議論を行うことが必要ではないかと思います。


最後になりましたが、筆者が興味深いと思う各種の取り組みを紹介します。

## Vivado HLS
FPGAベンダーのXilinxによる高位合成の処理系です。
https://japan.xilinx.com/products/design-tools/vivado/integration/esl-design.html
この記事の中ではC言語入力の処理系に対してネガティブなことを色々と書きましたが、Vivado HLSは現時点では一番入手しやすく、ネット上の情報も豊富で、広く使われている処理系です。
## 高位合成友の会
「高位合成友の会」では年に1,2回集まって主に自作の処理系の開発の進捗の発表と議論を行っています。
https://hls.connpass.com/

## Karuta(筆者謹製)
私謹製の独自言語(JavaScriptとGoの間のような文法です)と処理系Karutaに関する記事、コード等です。
https://qiita.com/nekoaddict/items/be418e1eba7eb27264fc 概要
https://qiita.com/nekoaddict/items/30874ccb8b58324d019f チュートリアル(Lチカ)
https://github.com/nlsynth/karuta
https://twitter.com/neonlightdev

## Veriloggen
厳密にいうと「高位合成」からは外れてると解釈する人もいるかもしれませんが、コンセプトが興味深いので紹介しておきます。VeriloggenはPythonのコードでVerilogのコードを組み立てるという仕組みになっています。
https://github.com/PyHDI/veriloggen
(コミュニティによってはScalaを入力とするChiselの方が良いのかもしれませんが、Qiitaの読者層的にはVeriloggenの方がお勧めな気がします)

## 自作してみたい方へ
もし、読者の方で高位合成の処理系を作ってみたいと思われる方は

1. 普通のコンパイラを作る技術
2. VerilogもしくはVHDLを書いてFPGAの開発ツールに入力する方法

辺りを学んでいただければ意外と簡単に動くものを作れるかと思います。
汎用性のあるものを作ろうとすると大変なことになるかもしれないので、特定のジャンルを処理するDSLから始めるのも良いかもしれません。
面白い物ができたら高位合成友の会に持ってきていただければ幸いです。

## FAQ?

* あの言語のあの特徴は論理回路にするのに向いてるんではないでしょうか？
 * そうかもしれませんね、実際に作って試してみましょう！
* この言語処理系のASTモジュールを使うと高位合成の処理系が簡単に作れるんではないでしょうか？
 * 良いところに気付きましたね、実際に作って試してみましょう！
 * 元の言語のセマンティクスと書きたい論理回路の間にギャップがあるかもしれませんが工夫すれば乗り切れるかもしれません。
* LLVMみたいな物はないんですか？
 * 筆者謹製の Iroha https://github.com/nlsynth/iroha という処理系がありますが、今のところ筆者謹製のフロントエンドであるKarutaとの組み合わせでしか使っていません。これを使って頂くか自作していただくかお選びください。
* Javaが好きなのですが
 * Synthesijer http://synthesijer.github.io/web/ も好きになって頂けるかと！
* Pythonが好きなのですが
 * Polyphony https://github.com/ktok07b6/polyphony はどうでしょうか？
 * Veriloggen https://github.com/PyHDI/veriloggen もどうぞ！ 
* MLが好きなのですが
 * 誰かもそんなことを言ってるのを聞いた記憶があります。来年あたりには面白い処理系が登場するかもしれません！
* Elixirが好きなのですが
 * Cockatriceという処理系が開発されているそうです。期待しながら公開を待ちましょう。
* C言語が好きなのですが
 * 色々と言われてますが、足回りのソフトウェアを作るのには最適ですよね！
* 上記にない某言語が好きなのですが
 * ググってみて頂けませんか？無ければ自作しましょう！
* ソフトウェア向けのどの言語も論理回路の合成には向かないと思います
 * 奇遇ですね！筆者も同感です。言語から作るしかありませんね！
* オープンソースが好きなんですか？
 * 非オープンソースでの試行錯誤には限界がある気がします。(技術が成熟するまで)今はビジネスのことは後回しにしてユーザーと開発者が情報やソースコードを共有して有用なツールを作る方法を模索するべきフェーズだと思ってます。
 * ビジネス化してしまってると弱点に関してオープンな議論がし辛くありませんか？
* 低水準なプログラミングが流行ってますが？
 * 筆者および高位合成友の会のメンバー達は高水準なプログラミングを目指します。
* この記事は国内のアマチュアの視点に偏ってませんか？
 * そうですね。
* ディープラーニングはできないんですか？
 * VivadoHLSやVeriloggenはディープラーニングの回路の研究開発に利用されています。
 * ディープラーニング用のDSLを作るのは非常にエキサイティングなテーマだと思います。
 * ディープラーニング＊も＊簡単に実装できる処理系が欲しいです(作りたいです)よね？