|
本プロジェクトでの開発成果は、
1. 実際に実機で動作するHDML言語の実装を作り上げたこと
2. その上でいくつかの設計パターンの動作を確認しライブラリとして実現できることを示したこと
である。
その開発成果に付随する成果として、ソフトウェア記述言語の高度な抽象化機構を実際にハードウェア記述言語で実現する過程で、ソフトウェアとハードウェアとの間の本質的な違いを明確化し、それに対する解決策を見出したことがあげられる。
１．HDMLコンパイラの開発
本プロジェクトでは、高い抽象化機構を持つHDML言語を設計し、そのためのコンパイラを作成した。本言語が持つ、現代的な抽象化機構を次に挙げる。そして、ハードウェアでその項目を実現する際にソフトウェアと異なる点を説明する。
本プロジェクトでは、高い抽象化機構を持つHDML言語を設計し、そのためのコンパイラを作成した。本言語が持つ、現代的な抽象化機構を次に挙げる。そして、ハードウェアでその項目を実現する際にソフトウェアと異なる点を説明する。
（１）高階関数
現代的な言語では、「関数」を第一級の値として扱うことができる。言い換えれば、関数そのものを値として関数の引数や関数の返値として扱うことができる。高階関数は、HDML言語が持つ最も強力な抽象化手段である。
※高階関数：
関数を引数に取る関数のこと。例えば大枠が決まっているが、細かな詳細が決まっていないプログラムについて、細かな詳細を引数として渡すことで一つの操作手順を定義することが出来る。HDMLではパイプライン、ステートマシンと言った単位について高階関数を用い操作手順を定義している。
以下、高階関数がハードウェア記述に実際にどのように活用できるのかを例を挙げて説明する。
ハードウェアでは、組み合わせ回路を組み合わせ、高度な回路を構成するために、しばしば「パイプライン化」が用いられる。パイプラインを構成するためには、各組み合わせ回路間の信号をラッチで保存し、ストール信号やイネーブル信号などの制御信号を用いて適切に信号が伝播するように制御する。通常既存のハードウェア既述言語でパイプラインを記述するときは、組み合わせ回路をモジュール化し、一つ上の階層で制御信号を定義し、モジュールを結合することが必要である。
高階関数を利用することにより、この「モジュールを適切な制御信号で結合してパイプラインを構成する」という一連のプロセスの抽象化が可能である。つまり、「組み合わせ回路」という関数を受け取ってパイプラインを構成する、という機能を関数として実現する。これは、高階関数が「関数」を値として利用することができるために実現できる抽象化である。
また、より強力な例として「ステートマシン」の抽象化が挙げられる。ステートマシンを抽象的に捕らえれば、「あるステートを受け取って次のステートを返す関数」と「タイミングにあわせてステート遷移関数によってステートを変化させていくモジュール」の２つから構成される、と捕らえることができる。従来ならば、この２つは一つのモジュールとして実現され、タイミングとステートが入り混じったものとなる。しかしながら、HDML言語では、ステート遷移関数を受け取って、タイミングにあわせて動作するステートマシンを出力する、という関数の記述が可能である。この仕組みによりステートマシンの記述を自然に抽象化することが可能になる。
高階関数をハードウェアで実現する際のポイントとなることは、ソフトウェアでは関数は「関数へのポインタ」で示すことができるのに対し、ハードウェアでは関数ポインタという仕組みが存在しないことである。関数ポインタを渡すということによって高階関数を実現することは（効率的には）できないので、同等の仕組みをハードウェアの枠組みの中で実現する必要がある。本コンパイラでは、関数の定義から「ディスパッチャー」と呼ばれるものを生成し、関数の出現ごとに関数の中身を適切に制御することにより、この仕組みを実現する。つまり、関数の引数に関数が存在する場合、渡された関数に応じて適切な回路を（関数ごとに）生成する必要があるので、そのための仕組みを実現したわけである。
（２）高度な型システム
現代的な言語の多くが持つ言語機能の一つとして、強力な「型システム」の存在が挙げられる。HDMLもその例外ではなく、強力な型システムを持つ。HDMLは、ビット列だけでなく、タプル（値の組）、バリアント（Ｃ言語での共用体）などの型を持つ。それらを組み合わせて、複雑なデータ構造を表現することが可能となる。
このようないろいろな型の存在は、しばしばプログラミングの記述を煩雑にする。引数にとる型ごとに関数を書き直したり、面倒な変数宣言が必要となる。しかしながら、「多相型」と「型推論」の概念を用いることによりこれらの問題はスマートに解決することができる。多相型は、JavaのGenericsやC++言語のTemplateと同様の概念で、様々な型の値をとることができる関数の実現を可能にする機構である。
また、型推論は、変数宣言からユーザーを解放し、かつ、型によるプログラムの静的チェックを可能にする機構である。より分かりやすく言うと、A+Bという記述があったとき、Aの型がわからなくても、Bが整数であることが分かっていればAの型は整数と決定することができる。このような推論を用いることによって型を決めていくことにより、明示的に型を指定しなくても、プログラムのほとんどの式の型を決定することができる。
HDMLコンパイラは、完璧ではないが、「多相型」と「型推論」の大部分の仕組みを実装している。
※多相型：
どのような型を入れても成り立つような型のこと。例えば演算子
"+"は、(0100b + 1010b)と4bitの整数に対して用いることが出来るが、(0b + 1b)と1bitの整数に対して用いることも出来る。この演算子は左右が同じビット幅の整数であれば、どのような値を入れても構わない。これは任意の型aに対して成り立つ、((a, a) -> a)という型を持つ関数として定義される。
（３）パターンマッチ
VHDL言語では、選択信号の値に応じてどの入力信号を出力信号として出力するかを記述するための「select文」が存在する。マルチプレクサやデコーダを記述する際に非常に有効な記述方法であるが、HDMLではさらにその機構を進化させ、「型」を含めた形でのselect文を実現する。つまり、従来の言語では
選択信号
"000" ->
"101"を出力
"001" ->
"110"を出力
"010" ->
"011"を出力
others -> "111"を出力
という記述が可能であったのに対して、HDMLでの選択は、
("000","111")
-> "111"を出力
("000",_) ->
"101"を出力
_ -> "000"を出力
という、タプルやバリアントで表現される値を、「パターン」をマッチさせることにより出力信号の値を選択することのできる強力な仕組みを持つ。この機能と、HDMLの持つ型機構を組み合わせることにより、ビット列を直接記述することなく、柔軟な選択回路の構成が可能となる。
この仕組みをハードウェアで実現するためには、多彩な入力のパターンをハードウェアで効率的に実装するための手法をコンパイラに実装する必要がある。そのため、単に値をビット列として扱うのではなく、型情報のタグを表現する信号線を適切に追加する、などの機構を実装した。
次に、今回作成したコンパイラのワークフロー図を掲載する。HDMLプログラムが入力されると、このようなフェーズによりプログラム変換が施され、最終的に合成可能なVHDLを生成する
以下、各フェーズでの処理について説明する。
●
字句解析・構文解析
文字列→構文データの変換。文法が正しいかはここで確認している。
字句析器ocamllex, 構文解析器ocamlyacc（どちらもOCaml言語に付属のツール）を用い、字句解析、構文解析を行う。字句解析はソースプログラムを文節に区切り（def x = 100b; を "def"
"x" EQUAL BITS'100' SEMICOLON など）、構文解析ではこれを構文木と言われる「プログラムを木のデータ構造で表したもの」に変換する。
●
型推論
序盤の山場。それぞれの単語が、どういった「型」を持っているかを調べる。
例えば"a =
0001b" とあればaは4bitの信号線であることが分かる。又、c = a + 0001b とあれば、a, cは共に4bitの信号線を持っていることが分かる。このようにして判別可能な型を順番に決めていく。
型には人の手で制約を掛ける事もできる。このとき、人の指定と矛盾がないかどうかも確認する。
このとき、最後まで型が決められない場合がある。例えば、除算回路result
= div(x, y)が存在したとした場合、xは4bit,
6bit, 10bit のいずれでも構わない。この場合、この時点では型を決定せず、"result,
x, yの型は一致している"という情報だけを決定し、次に回す。
この「一致している型はどれか？」という情報は更に複雑になることもある。例えば、パイプライン結合演算子は、前のパイプラインの出力と、後のパイプラインの入力のみが等しい型を持つ演算子として定義される。このような一致関係も正確に把握することが出来る。
●
インライン展開・単相化
型が決まらなかった定義について、「どこでどう使われているか」の情報から型を決め、実体を作る。先の除算の例で言えば、もし除算が8bitで使われる場所があれば、divをコピーし、"div_8bit"という別名の定義を作成する。これにより、「何を入れても動く」関数（例えば今のdivや、liftP, state_machine_mealy等）を正しく扱うことが出来るようになっている。
●
関数使用解析
HDMLには「関数の関数」、高階関数が存在する。高階関数は非常に便利だが、VHDLではサポートされていない。これを実現するために必要なギミックの一つがこの関数使用解析。
HDMLでは、関数そのものを値として使うことを認めている。例えば、
def mul(x,
y): { .. }
def div(x,
y): { .. }
def
rand_select(f, g):{
if
random () then f else g
}
..
def value =
(rand_select(mul, div))(foo, bar);
では、mul, divの関数をランダムに適応して結果を得る、という意味になる。これは以前述べたパイプラインの複雑化などの時に威力を発揮する。
●
クロージャ変換
関数を呼ぶとき、外部の信号線を用いている場合がある。この場合、外部の変数の情報を、呼び出し時に追加する必要がある。
以下に例を挙げる；
def div(x,
y):{
def
internal_table_lookup(topbits):{
def table = table(topbits, y);
};
do_something()
}
この例の中で、yはdiv()で定義されているが、関数internal_table_lookupの中ではそのまま使われている。こういった「関数の引数として与えられていない信号線を使う」ことを、この後で行う高階関数消去のための情報として与える必要がある。例えばこの場合では、internal_table_lookupについて、「tableとyを外から使うよ」という情報を保持し、このための構文木変換を行っている。
●
高階関数消去
中盤の山場。「関数の関数」高階関数を消去し、VHDLやVerilogで記述できる形に翻訳する。
高階関数はVHDLではサポートされないため、これを次のようなアルゴリズムで消去している。まず、関数の定義を、データ信号線の作成に置き換える。続いて、関数を使用している場所を、与えられたデータ線から関数の内容を復元するように書き換える。
基本になったアルゴリズムは
Journal of Functional
Programming, 8(4):367-412
のものだが、ハードウェア向きにアルゴリズムをほぼ全部書き直している。
●
一列化
プログラムをVHDL形式の代入文の集合に置き換えている。すでに必要な変換はほぼ完了しているので、複雑な代入をする必要はなく、途中の計算結果などに信号線の名前を付けるだけで完了。
●
パターンマッチ分解
終盤の山場。
HDMLでは次のような表記を可能にした。
def (a, b) =
(0001b, 0000b)
また、次のような「より強力なselect文」を可能にしている。
def print_value_iter(in,
state):{
case
(in, state) of{
Some x, 00000000b ->
(None, x
+ 00000001b, false)
|
_, 00000000b ->
(None,
00000000b, false)
|
_, 00000001b -> (Some
(cr),
00000000b, true)
|
_,
y -> (Some (asterisk), y
- 00000001b, true)
}
}
case .. of .. 文とprocess,
select文との違いは次のような部分。
●
「この値は問わない」という指定が可能である
●
複数の条件に合致する場合は、より上にある方が採用される
●
しかし、合成される回路はselect-when文で構成され、無駄な条件比較を生成することはない。
●
出力
VHDLのプログラムを出力する。
すでにこの時点で、VHDLとして出力可能な情報はすべて揃っている。最後のフェーズでは、これをファイルにまとめ、またHDMLだけでは合成できないVHDL（多くの場合、process文など書き方が重要になるものです）を生成している。
２．ハードウェア設計パターンの整備
HDML言語は、ハードウェア記述の抽象化をハードウェアの特性に適合した形で表現できる抽象化機構の実現が主目的である。そのため、本プロジェクトを遂行するに当たって、我々は多くのハードウェアの設計パターンを整理し、抽象化のために必要な機能の洗い出しを行った。
我々は、まず設計パターンを、１．入出力、２．内部構造を記述するためのパターン、に分類する。また、クロックによるタイミング制御の問題は、設計パターンそれぞれにタイミングの概念を内包させる。これにより、ユーザーは設計パターンにしたがって記述することにより、明示的なタイミング制御を行わなくて済む。
（１）入出力パターン
入出力パターンは、大きくわけて、
1. ストリームモデル
2. ２．RAMモデル
3. CAMモデル
に分類される。ストリームモデルは、RS232Cなどの入力や出力が一種のストリームとして表現されるモデルである。RAMモデルは、ストレージに格納されたデータのランダムアクセスを可能にする。CAMモデルは、内容が入力された時、対応するアドレスを出力とするようなモデルである。
HDMLでは、RAMモデル及びCAMモデルはストリームモデルの派生モデルであると捉える。RAMモデルは、アドレスのストリームを与えることによって対応するデータのストリームを出力する。CAMモデルは、データのストリームを与えることによって対応するアドレスのストリームを出力する、という具合である。ストリームモデルに帰着させることにより、クロックの概念を「ストリームの流れ」の中に押し込めることが可能になり、クロックを意識しないコーディングが可能となる。
例として、HDMLでストリームを扱った例を見てみる。
def main =
def bigpipe = (input |>
(liftP(pipe1))) ||> output;
eval(bigpipe)
この例では、inputを評価することにより、RS232Cからの入力を受け取ることができる。そして、outputを評価することにより、outputの入力がRS232Cモジュールに送信される。このように、HDMLでは、ストリームモデルにクロックの概念が内包されているため、クロックを記述することなく、時間を扱ったプログラムの記述が可能となる。
（２）内部構造を記述するためのパターン
内部構造を記述するパターンは、主に、組み合わせ回路を組み合わせ複雑な回路を構成する設計パターンである。これには、パイプラインパターンやステートマシンパターンなどが挙げられる。HDMLの設計にあたっては、最も多く適用例が多いであろうパイプラインパターンを簡潔に表現することを目標に設計を行った。パイプラインパターンでは、時間の概念や、必要な制御線の概念をパターンに押し込めることによって、煩雑な制御線の定義や時間の概念を意識せずパイプラインを構成することが可能となる。
例として、実際のパイプラインがどのようにHDMLで表現されるのかを次に挙げる。
def pipe1(in):{
Pass(in xor 00000011b)
}
def main =
def bigpipe = (input
|> (liftP(pipe1))) ||> output;
eval(bigpipe)
本質的な部分はこれだけである。|>や||>は、パイプラインモジュール間の結合を示す演算子である。pipe1は、ユーザーが作成した組み合わせ回路である。この組み合わせ回路を、liftPという高階関数に渡すことにより、必要な制御線やタイミング制御が生成される。そのような仕組みは、HDMLのライブラリ及び言語機能を用いて実現されている。パイプラインパターンでは、入力が来ていないときや、出力側がfullのときにも適切な制御を行い、ストールやバブルを意識せずにユーザーはパイプラインを記述することが可能である。
３．HDMLによる設計パターンライブラリの作成
２．に挙げた設計パターンをユーザーが利用できるようにするために、本プロジェクトでは設計パターンを実現するためのライブラリを開発した。ライブラリは、VHDL及びHDMLで記述され、ストリームモデル、パイプラインパターン、ステートマシンパターンなどが現在用意されている。前述したパイプラインの記述もライブラリが用いられている。
また、VHDLで記述されている部分は、入出力の記述などに限定されており、ライブラリ自体の多くがHDMLで記述されている。これは、HDMLが様々な設計パターンを抽象化可能であることを示す例である。
例えば、組み合わせ回路からパイプラインモジュールを生成する関数は、ライブラリでは
def liftP(fn):{
def result (input,
future):{
def (out,
stall) =
def enable = not stall;
def really_input = primitive("enable_reg", input, enable);
def _ = if 1b then None else really_input;
case really_input of {
None -> (None, 0b)
|
Some x ->
def res = fn((x: 8bit));
def (out_cur, stall_cur) = case res of {
Stall -> (None, 1b)
| Bubble -> (None, 0b)
| Pass y -> (Some(y), 0b)
};
(out_cur, stall_cur or future)
};
(out, stall)
};
result
}
のようにHDMLで記述されている。HDMLで記述されることの大きなメリットの一つに、「HDMLの強力な型システムによりライブラリが検証されている」ということが挙げられる。ライブラリをHDML言語そのもので記述することにより、HDMLによる強力な型チェックを利用することができる。
４．評価
（１）パラレルシリアル変換回路・シリアルパラレル変換回路
HDMLの高い記述能力を示すために、ステートマシンを用いたパラレルシリアル変換回路・シリアルパラレル変換回路を記述し、VHDLでの同等な機能を持つ回路とその行数を比較した。
|
|
HDML
|
VHDL*
|
|
パラレル/シリアル変換
|
11行 (2.970ns)
|
63行
|
|
シリアル/パラレル変換
|
10行 (2.619ns)
|
80行
|
*: 「実用HDLサンプル記述集」, CQ出版社. コメント行を除く
（２）CPU
もう一つの例として、簡単なCPUを記述した例について示す。
作成開始から、実装３時間、検証10時間で動作させることができた。HDML記述の行数はわずか231行である。
|
CPU
|
HDML
|
|
実装
|
3時間
|
|
検証
|
10時間
|
|
|
231行 (12.531ns)
|
|
回路規模
|
FF 215/21504
|
|
LUT 725/21504
|
５．開発成果の特徴
本プロジェクトで作成したHDML言語は、これまで多くのハードウェア記述言語で採られて来たアプローチである「ハイレベルシンセシス」とは大きく異なる特徴を持っている。ハイレベルシンセシスを行う言語では、Ｃ言語などの手続き的な言語から、ビヘイビアを解析しハードウェアの回路を合成する。しかし、本プロジェクトではまったく別のアプローチである「ハードウェア設計の枠組みを抽象化する」というアプローチを採用する。
本プロジェクトの成果のポイントは、
●
アプローチを成し遂げるための言語機能の選定
●
言語機能をハードウェアで実現するための手法の開発
●
そして、機能を実際にハードウェアで動作させること
である。
ハードウェア設計の枠組みの抽象化において、時間の概念を抽象化することは非常に難しい課題の一つである。それを、自然な方法で解決したことも、本プロジェクトの大きな成果の一つと言える。ラッチを明示的に扱わずに、抽象化の枠組みの中に組み入れることにより、ユーザーに抽象的な記述を可能にしながら時間の概念を扱ったハードウェアを記述することができるようになった。
また、VHDLなどの広く利用されているハードウェア記述言語とHDML言語は、表現力はさほど変わることがない。ただしそれを表現するためのスタイルは大きく異なっている。VHDLでは、信号線、タイミング合わせなどを事細かに記述するのに大して、HDMLではそのような細かい記述を隠蔽し、抽象化された表現として記述する。そのため、事細かなチューニングをHDMLで行うことはできないが、あるデザインをより簡潔に表現できることが可能である。そして、タイミング制約が重要な回路を含んだ回路も記述できるように、HDMLは、VHDLでかかれたコードを取り込む仕組みを用意している。
HDMLの設計スタイルは、配線を一本一本定義するのではなく、機能をどう抽象化するのか、というところから始まる。そして、一旦抽象化が可能になれば、細かい信号線の制御を考えることなくハードウェアの記述が可能になる。そのための豊富な抽象化の枠組みを提供するのがHDMLであり、VHDLでは、モジュール単位での抽象化機構しか存在しない。ここが、HDMLと既存のハードウェア記述言語との大きな違いである。
HDMLはVHDLとの連携が可能であるという事実は、HDMLからVHDLへの段階的な移行も可能であることを示している。一部のコードに対して、HDMLによる高度な抽象化を実現し、他の部分に既存のコードを利用することができる。また、基本はHDMLで記述し、本当にタイミングが重要な部分だけVHDLで記述することもできる。
|
