2016年11月02日

10月度概況

access1610.jpg10月度の弊社HPへのアクセス状況は図のようになりました。ブログを移動して以後、急増しておりましたが、どうやら落ち着いてきた様子です。

今月度は、コンサルティング業務も一段落したことから、CodeSqueezerの開発に注力しております。

先月度述べましたように、まずは誤差キャンセルの問題はいったん棚上げとして、リンクリストの処理を含むコンパイラ部分を先に作ることといたします。

以下、少々入り組んだ話ですので、節に分けて記述します。

0. パイプライン数値演算処理記述言語“mhdl”

CodeSqueezerは、FPGAなどの論理演算デバイスを用いて数値演算をパイプライン処理によりおこなうための論理を自動形成するツールで、その演算仕様を記述するための新言語“mhdl”を開発しています。

mhdlはMeta Hardware Description Languageを略した命名で、Metaの本来の意味は「後の」つまりは「次世代」を意味するのですが、メタフィジックスの「メタ」から「抽象的」との意味合いでも広く使われており、より抽象度の高いハードウエア記述言語という意味も兼ね備えています。

裏話をすれば、将来の標準化を目指して“?hdl.org”というURLを確保しようと考えたのですが、“?”にあたる文字にたまたま“m”が空いていた、というのが実情です。他に“n”も空いており、New Hardware Description Languageにするという手も、ないではありませんでしたが、考えた末に“m”を選んだ次第です。

mhdl.orgは、既にページを作成済みですが、現在のところ放置状態となっております。いずれは、mhdl committeeなどを組織化して、このページを広報に利用できればと考えております。もちろんその前に、きちんとした言語処理系を作るのが先決であることはいうまでもありません。

FPGAで数値演算する論理を記述するためには、Verilog HDLやVHDLなどのハードウエア記述言語が広く用いられていますが、これらは、数値のビット幅やタイミングを設計者が記述する必要があり、複雑な演算を表現することが難しいという問題があります。

一方、C言語で記述されたソースコードをパイプライン化する方法も種々用いられているのですが、Cの言語仕様は、CPUの機能にあわせて設計されており、パイプライン処理の記述にはあまり向かないという問題があります。

パイプライン処理とCPU処理の異なる最大のポイントは、パイプライン処理ではそれぞれの演算に専用の演算器が用いられるということ。演算器ごとに、最適なビット幅(浮動小数点数の場合は、仮数部のビット幅と指数部のビット幅)を独立に設定できるという点があります。

これらの数値型は、きわめて自由度が高いのですが、これをプログラマーが設定するということは、非常に煩雑な作業となります。

mhdlないしCodeSqueezerの着想は、それぞれの演算器に要求されるビット幅は入力(あるいは出力)の仕様が与えられれば自動的に定まるという点にあり、これを利用すれば、型なしの言語仕様が可能となる点にあります。

また、こうして形成される論理は、必要最小限の論理のみを含むため、演算処理全体の論理規模を圧縮することが可能となります。これは、論理規模が大きくなりがちなパイプライン処理論理の開発に際しては大きな利点といえるでしょう。

mhdlの言語仕様を定めるに際しては、パイプライン処理論理の表現であるブロックダイアグラム(多数の演算機能ブロックを配置してこれらの入出力間を信号を伝達するリンクで接続したもの)を念頭においています。配置されるブロックは多入力・多出力が一般的であることから、複数のリンクをまとめて扱う「リンクリスト」という概念を導入しています。

リンクリストの概念を利用すると、複雑で大規模な演算論理も簡単に記述することができます。これが今回の改良の大きな部分です。また、リンクリストの概念を明確に定め、統一された思想にもとづく言語仕様として文書化することも、今回の作業の重要なポイントです。

その他、mhdlの言語仕様では、CPUの機能に即して定められたCの言語仕様から、CPU命令に則して定められたと思われる、ビットごとの演算、インクリメント・デクリメント演算、シフト演算などを除去し、一般に用いられている数式表現に近い形で数式を記述するようにしています。

また、CPUのシーケンシャル処理と、ブロックを配置してダイアグラムを形成するパイプライン処理では、アルゴリズムも異なったものとならざるを得ません。このため、forは、多数の論理を形成するマクロ的な記法に改め、ifやcaseは、制御の切り替えではなく、マルチプレクサの配置であることを明確化する言語仕様といたしました。

その他、現在ではごく普通に用いられているフルスクリーンエディタを前提に、今日ソースコードの論理構造を表すためにごく一般的に行われている段差付けに意味を持たせて、実行文のブロック化を行う記号(Cの場合は“{”と“}”、biginとendを用いるプログラミング言語もある)を排除して、ソースコードの可読性を高め、つまらないエラーが入り込むことを防止しています。

今日のFPGAでの算術演算には固定小数点演算が多く用いられています。固定小数点演算は、確かに高速演算が可能なのですが、有効な情報を落とす恐れがあり、安全な論理変換手続きが存在しないという問題があります。

CPU(マイクロプロセッサやDSP)でも、古くは固定小数点演算が主流でしたが、今日では浮動小数点演算が広く利用されています。FPGAをはじめとするパイプライン演算の世界でも、いずれは浮動小数点演算が主流になるのではなかろうか、と私は考えております。

このような背景により、シグナル・プロセス・ロジック社では、mhdlという新しい言語仕様を策定するという選択をした次第です。

これらの言語仕様の一部は、既にDAシンポジウム2012で発表したほか、リンクリストの概念を強化した新しい仕様につきましても3月度概況4月度概況でご紹介しております。

また、旧版のmhdl処理系を含むCodeSqueezerの評価版はこちらのページからダウンロード可能で、各種マニュアルなどもここに置いてあります。

言語仕様全般につきましては、これらをご参照いただくこととして、以下では、今回改良を試みておりますコンパイラの構成と、特にパーサの構成とアルゴリズムについて解説いたします。

1. コンパイラの構成とパーサの処理内容

mhdlコンパイラは、三つの段階に分けて処理します。

第一段階は、いわゆるパーサで、この部分で次の三つの処理により、ブロックダイアグラムを形成します。

・ ソースコードをブロック定義のツリーに変換し、各ブロック定義に(トークンのリストとして)ブロック定義文とブロック内部の式(代入文)をもたせる処理

・ 式を、かっこや演算子の優先順位に従い、項の木構造に変換する処理

・ リストに対する演算を個々のリンクに対する演算に分解するmhdl言語特有のリスト処理

第二段階は、いわゆる最適化の段階で、ブロックダイアグラムをより効率的な形に変形します。誤差キャンセルへの対応も、この段階で行います。

最後の第三段階で、各ブロックをVerilog HDLで記述されたモジュールに変換します。この処理は、各ブロックに準備された「コーダ」と呼ばれる関数により行います。

標準ブロックのコーダは、入力ポートに接続されたリンクの数値型に基づき、それぞれのブロックの機能を実現するために必要な、最小限の演算論理を形成します。

今月度は、パーサの数式解釈部分の文書化を行いました。本日はこの内容について、簡単にご紹介します。なお、パーサの最初の部分(ソースコードのトークン化とブロック定義ツリーへの割りあて)は、既に3月度概況4月度概況でご紹介しましたので、こちらをご参照ください。

2. class Ope:演算子

ope.jpgmhdlの演算子には、表に示すものがあります(クリックで拡大します。)この表の各項目は、class Opeのメンバーで、演算子の配列static array<Ope^>^ ope_tblを準備して同表の内容を与えておきます。表中、“?”は異常な演算子、“$”は末尾を表す演算子で、これらはコンパイラが内部的に使用するものです。symbol欄は、ソースコード上の文字列であり、ソースコード上に記号が現れた場合は、この文字列に従ってトークンへの切り出しがおこなわれます。このとき、class TokenのメンバーであるOpe^ opeもセットします。

パーサは演算子の優先順位であるint levelを用いて式のツリー化をおこないます。同じ優先順位に複数の演算子が割り当てられるため、これを識別するためにbool invとint selの二つの変数を用います。これらの変数は、歴史的な事情で二つに分けていますが、将来一つにまとめるかもしれません。

ソースコード記述段階でブロック入力ポートにinvとselの情報を与えることができるよう、リスト化演算子には、“,”の他にinvとselの異なる、合計6種類の演算子を割り当てています。これらは標準ブロックをテストするための演算子です。

同じ優先順位の二項演算子は一つの標準ブロック(binary std_block)により一括処理されます。

標準ブロック欄が空白またはかっこ内の演算子は、コンパイラ内部で処理されます。かっこは式解釈の段階で処理され、リスト演算に関わる演算子(“.”、“@”、“'”および“,”など)はリスト処理の段階で処理されます。

3. class Term:項とそのデータ構造

パーサは、最終的に、式を項に変換します。

項(class Term)は、名前(リンク名またはブロック名)もしくは定数に相当する単純項(String^ str)であるか、同じ優先順位の演算子で結ばれた項のリスト(List<Term^>^ flat_expr)のいずれかです。後者は最終的に標準ブロック(binary std_block)配置に変換され、全ての項は単純項となります。

項を先導する演算子(Ope^ pre_ope)と項に続く演算子(Ope^ post_ope)も項のメンバとします。pre_opeは、項に対応するリンクをブロックの入力ポートに接続する際にinvとselを入力ポートに与えるために用いられます。post_opeは、パーサの段階で、項の処理がいかなる演算子により修了したかを呼び出し元に伝えるために用いられます。

さらに項は、単項演算子のリスト(List<Ope^>^ unary_opes)と後置項のリスト(List<Term^>^ post_terms)を持つことができます。後置項には、“@”や“.”に先導されるリストの要素を指定する後置項と、ブロック配置の引数を指定する後置項があります。後置項を先導する記号は、後置項のpre_opeに格納して、後続するリスト処理に伝達します。

4. proc_term:項の形成

Term^ proc_term(int exit_level)はトークンを項に変換する関数です。exit_levelは、処理を終了する条件を示すもので、これ以下のレベルの(優先度の低い)演算子が現れた際に処理を終了します。式全体の処理は、proc_term(LV_END)でおこなわれます。

proc_termは、まず、最初のトークンをチェックして、閉じかっこが現れてそのレベルがexit_level以下である場合、および文末が現れた場合は、これをpost_opeとする空の項を返します。これは、空の式や“()”などの記述に対する処理です。

次いで、ひらきかっこ以外の演算子が現れる限り、これを単項演算子とみなして、unary_opesに追加します。

開きかっこが現れた場合は、そのselを保存して以後をproc_term(LV_BRA)で処理して、閉じかっこまでの項を得ます。また、得られた項のunary_opesを新しく作成する項のunary_opesに追加します。これは“-(-x)”などの記述がされた場合に備えてのものです。

開きかっこでない場合は、名前または定数が現れるはずです。これをString^ strに置きます。

次に現れるものが“@”、“.”、開きかっこである場合は、以降を後置項と見做してproc_termにより項を得、これをpost_termsに追加します。次に現れるものが名前もしくは定数である場合、エラーメッセージを出力し、proc_term(LV_MAX)により演算子を含まない項を得て、これを後置項とします。これは“sin x”などとしてしまった場合の救済処理です。後置項が“@”か“.”に先導される場合は、これらを後置項のpre_opeに置きます。後置項は複数置くことができますので、この処理は“@”、“.”、開きかっこ以外の演算子が現れるまで繰り返し行います。

後置項とみなすことのできない演算子が現れたら、すでに形成された項を処理中の項(resとします)とし、そのpost_opeに現れた演算子を置きます。演算子のレベルがexit_level以下の場合はresを返して処理を終わります。そうでない場合は、“res = proc_expr(res, exit_level)”により式の処理を行い、その結果を返します。

なお、ここで閉じかっこが現れた場合は、警告メッセージを出力してこれを無視します(次の演算子を読んで、処理を継続します。)閉じかっこは、開きかっことの対として処理されているはずですので、ここで現れる閉じかっこは、開きかっこに対応していないことになります。

5. proc_expr:式の形成

Term^ proc_expr(Term^ first_term, int exit_level)は、flat_exprを含む項を形成して返す関数で、引数に与えられた項が第一項となります。また、flat_exprの演算子レベル(first_term->post_ope->levelとして与えられます)をint cur_levelに保持します。

次いで、next_term = proc_term(exit_level)により次の項を読み込み、next_term->post_opeのレベルを参照しながら、以下の処理を繰り返し実行します。

cur_levelに等しい場合は、得られた項にpre_opeをセットしてこれをflat_exprに追加し、次の項をnext_termに読み込み、処理を繰り返します。

cur_levelよりも大きい(優先度の高い)場合は、next_term = proc_expr(next_term, cur_level)によりcur_levelよりも優先度の高い演算が続く限り項をflat_exprの形に変換し、これをnext_termとし、そのpre_opeにfirst_term->post_opeをセットして処理を繰り返します。

cur_levelよりも小さい(優先度が低い)場合は、next_termまでをflat_exprに追加して形成される項を第一項(first_term)とし、cur_levelをfirst_term->post_opeのレベルに変更します。これがexit_level以下の場合は、first_termを返して処理を終わります。そうでない場合は、next_termを読み直して処理を継続します。第一項のpre_opeはセットされません。

6. まとめと今後の計画

前回述べましたように、mhdlソースコードはパーサの第一段階でブロック定義の木構造にまとめられており、それぞれのブロックに内部で定義されたブロックと内部で定義された式(class Expr)のリストを含んでおります。式のリストは、パーサの前段階では、トークンのリストとして保持されているのですが、class ExprにTerm^ termを含めて、この中にパーサの第二段階の結果を置くこととします。

ここまでできていれば、次は、リンクリストを許す形で記述された項を、個々のリンクに分解する処理を記述することとなります。もちろんその前に、上にご紹介したアルゴリズムを実際にコーディングするという作業が残っております。これらが11月以降の作業ということになるのですが、さて、11月はどこまで進みますことか。

HPCSの論文締め切りが来年1月となっておりますことから、あまり残された時間はありません。できることなら、11月中に、リンクへの分解までを終わらせたいところですが、またしても、コンサルティングの業務が入っておりますことから、この先のスケジュールもかなりタイトになると予想しております。

これが1月までにできなければ、次は6月締め切りのDAシンポジウムを目指すだけのことなのですが、、、
posted by 管理人 at 08:22| Comment(0) | TrackBack(0) | 日記
Powered by さくらのブログ