2016年05月01日

4月度概況

access1604.jpg4月度の弊社HPへのアクセスは図のようになりました。概ね従来通りです。

今月度も引き続きコンサルティング業務が多々入っておりますが、隙間の時間を利用して、mhdlコンパイラに関する考察とコーディングを続行しております。

先月度は、ブロック定義をツリー構造にするアルゴリズムについて述べましたが、今月度は、トークン切り出し部分と組み合わせてコーディングして動作を確認しております。

作成したプログラムは、入力されたソースコードからコメントと空白を除き、閉じかっこ以外の記号で終わる行に次の行を接続しながら、トークンを切り出します。トークンは、コード中に記述された文字列と、種類を示す整数と、ソースコード中の位置情報を含みます。ソースコードの文は、レベルと、ブロック定義文であるか否かを示すフラグ、およびトークンのリストに変換され、次いでブロック定義ツリーに変換されます。

以下のソースコードを処理した例をご紹介します。(段差が正しく表示されるよう、半角ブランク二つを全角ブランク一つに変更しています。)

block1.out(a,b)
  out = block2(a,b)+ //comment
    block3(a,/*comment*/b)
  block2.out(a, b)
    out = a * b
  block3.out(a, b)
    out = a / b
block4.out(a, b)
  out = a - b

“//”から行末までと“/*”と“*/”に挟まれた部分はコメントとして読み飛ばされ、演算子“+”で終わる2行目は3行目に継続して一つの文を形成します。英字に始まる英数字の並びは名前、数字に始まる特定のパターンは定数、記号は一つまたは二つでそれぞれの記号を表し、単一のトークンとはなりえない文字が現れた時点で新たなトークンの始まりとみなされます。ブランクは、トークンを区切りますが、それ自体はトークンとはなりません。

以下が、上のソースコードを変換した結果で、ブロックツリーとして格納されたデータ構造を、今度は字下げで表現しています。“[]”で囲まれたものがそれぞれのトークンです。コメントの削除や継続行の接続も正しく行われ、それぞれ名前や記号に切り分けがなされております。

[root]
  ------ blocks ------
  [block1][.][out][(][a][,][b][)]
    ------ exprs ------
    [out][=][block2][(][a][,][b][)][+][block3][(][a][,][b][)]
    ------ blocks ------
    [block2][.][out][(][a][,][b][)]
      ------ exprs ------
      [out][=][a][*][b]
    [block3][.][out][(][a][,][b][)]
      ------ exprs ------
      [out][=][a][/][b]
  [block4][.][out][(][a][,][b][)]
    ------ exprs ------
    [out][=][a][-][b]

ソースコードとしては許されないのですが、実験的に“out = a <>!==!>< b”なる文字列からトークンを切り出してみました。結果は“[out][=][a][<>][!=][=][!>][<][b]”となります。ここで、“<>”、“!=”および“!>”は2文字からなる演算子として登録しています。最後の“!>”は、普通には見かけない演算子ですが、“<=”と同じ意味としています。
これができますと、次は数式をブロックダイアグラムに変換する処理ということになるのですが、その前に、“リンクリスト”の概念について、改めてまとめておきましょう。

リンクリストが必要になるのは、ブロックの入出力が複数のポートをもつことができるからで、複数の出力ポートをもつブロックを参照する際には、複数の出力信号を参照側で扱う必要があります。このためには、代入文は複数のリンクを扱う機能が必要で、その左辺にも複数のリンクをおく必要が生じます。

複数のリンクをひとまとめにして表現するため、“(link1, link2, ...)”なる形式を用いることとします。この形式は、C言語などでも関数定義や関数呼び出しの引数部にも表れるのですが、mhdlでは、一般の演算においても同様の記述を行うことで複数のリンクを扱えるようにし、これをリンクリストと呼びます。

ブロック定義文は“name.(out1, out2)(in1, in2)”などの形で、ドットに続く最初のリンクリストが出力ポートを、その後のリンクリストが入力ポートを定義します。複数の出力ポートを持つブロックを参照する際には、たとえば次の代入文を用います。

(q, r) = div2(n, d)

ここで、div2は商と余りを返す除算機能ブロックで、この記述により商と余りがそれぞれqとrに入力されます。

代入文左辺やブロック定義文の入出力ポート定義部分に現れるリンクリストは、リンクの並びでなければいけませんが、代入文の右辺では、式の並びをリンクリストとすることも可能です。たとえば次のような記述が許されます。

(sum, dif) = (a + b, a - b)

以上は、これまでのmhdl処理系にも含まれていた機能ですが、これを拡張することで、mhdlにC言語に近い機能を与えることを考えます。これらは現在構想中のもので、当面はこれらの一部のみを実装したサブセット版を作っていく予定ですが、全体を見据えたデータ構造としておく必要があるため、暫定的にフルセット版の仕様を考えておきます。

まず、リンクリストには固有の名前を付けることを可能とします。“dat1.(q, r)”は、二つのリンクqとrからなるリンクリストdat1を定義します。このリンクリストの要素に参照する際には、dat1.qなどのように、リンクリスト名の後にドットを付けてこの後に要素名を記述します。

リンクは信号線に相当し、リンクリストは信号線の束に相当します。それぞれの信号線には名前がついているのですが、信号線の束にも名前を付ければ、異なる束に同じ名前の信号線があっても、これらは別個のものとして識別されます。

名前付きリンクリストの要素は、それが定義されるごとに追加されます。リンクの定義は、ブロック定義文の入力ポート記述部分と代入文の左辺で行われます。たとえば、次の文

x.a = 式1
x.b = 式2

では、最初の文でリンクx.aをもつリンクリストxが形成され、次の文でこれにx.bが追加されます。

リンクリスト名を用いる利点は、複雑なリンクの集合体を一つの名前で扱えることで、xが上のように定義されている場合、“block1(x.a, x.b)”とせずに“block1(x)”のように、リンクリスト名で複数のリンクをポートに接続することを可能とします

リンクリストの要素として、リンク以外に、リンクリストも許すこととします。リンクリストのリストは、名前で定義する場合はx.y.aのようにドットを二回用いて指定します。また、((a, b), (c, d))のように、かっこを二重に用いることでも定義できます。

カッコを何重にも用いれば、リンクリストのリストのリストなども記述することができます。このようなリンクリストをわかり易く表現するため、「リスト」が何回現れるかを「階数」と呼ぶことにします。単純なリンクは階数0のリンクリストであり、リンクリストのリストは階数2のリンクリストです。

リンクリストの要素の定義、参照は、リンクリスト名に続けて“@”と番号を記述することでもできるようにします。一例を以下に示します。この形式で宣言された個々のリンクは名前をもちません。

x@0 = 式0
x@1 = 式1

@はCにおける“[]”と同じ働きをするのですが、あえて別の記号を用いる理由は、式の優先順位を規定するかっことして“()”“{}”“[]”の三種類を使用できるようにするためです。それぞれのかっこは同じように使用できますが、開きかっこと閉じかっこの対応は同種のものに限定されます。これにより、通常の数式と同じ記述を可能とし、かっこの多い式の可読性が改善されます。

@の後にはリスト(右辺では式のリスト、左辺では定数のリスト)を置くことができ、これにより部分的なリンクリストも指定できます。たとえば、x@(2, 3) = div2(n, d)とすると、x@2およびx@3が定義され、これらにdiv2の二つの出力が接続されます。なお、@の後に置くリストの階数は0または1に限定され、階数2以上のリストは置くことができません。

多数のリンクからなるリンクリストを容易に扱えるよう、“:”を使用して範囲指定できるようにしておきます。すなわち、“x@(0, 2:4)”と記述すると“x@(0, 2, 3, 4)”と記述するのと同じ意味を持ちます。

この形式は、定数リンクリストを作るためにも使用可能とします。すなわち、式の右辺に(0:3)と記述すれば(0, 1, 2, 3)と同じ意味となります。また、(3:0)とした場合は、(3, 2, 1, 0)と解釈します。この機能をCのforと同様の機能を持たせるため、二番目の“:”に続けて増分因子を指定できるようにします。すなわち、(0:6:2)は(0, 2, 4, 6)、(6:0:2)は(6, 4, 2, 0)と解釈します。

@を用いて高階数のリンクリストの要素を指定する場合には、“x@3@2”のように記述することで、階数2のリンクリストであるxの3番目のリンクリストの2番目のリンクを参照します。x@(0, 1)@(0, 1) = ((x00, x01), (x10, x11))と定義されているとき、x@0は(x00, x01)を、x@(0:1)@0は(x00, x10)を参照します。

左辺に表れるリンクリストの要素として、リンク名と@形式を混在させることも許します。リンク名は、現れた順にリンクリストに追加されます。同じリンクが複数回左辺に表れてはならないため、@形式のリンク指定を左辺に使用する際には、名前で指定されるリンクよりも後のリンクを指定する必要があります。なお、右辺で参照する際には、名前をもつリンクも@形式で指定することができます。

@を用いたリンクリストのアクセスは、個々のリンクに名前を付ける必要がないという意味がありますが、そのほかにもいろいろな応用が可能です。

第一に、リンクを配列的に扱うことが可能となります。

第二に、if式の拡張版として使用されます。すなわち、mhdlは論理真で1, 偽で0となりますので、“c ? b : a”は“(a, b)@c”と記述することができます。@形式を用いる利点は、選択が二つに限られないことであり、@の後に整数式を置くことにより、マルチプレクサないしcase文と同様の記述が可能になります。言語仕様を簡素にするため、“?”と“:”を用いるif式は仕様から除外いたします。

リンクリストに対する演算は、リンクリストに含まれるそれぞれのリンクに対する演算を並べて記述する形に展開されます。すなわち、(a, b, c) = (p, q, r) + (x, y, z)は、a = p + x, b = q + y, c = r +zと展開して処理されます。リストの途中に複数の出力を持つブロックが現れた場合は、その部分はまとめて処理されます。

ブロックが配設される際に、ブロックの入力として定義されているよりも高い階数のリンクリストが与えられた場合は、複数のブロックを配置したリストが形成され、これらのブロックの入力にはリンクリストの要素が順次与えられます。たとえば、単一のリンク(階数0)を入力として、1クロック遅れた信号を出力するブロックdelay(in)に複数の入力(階数1)が与えられた場合は、複数のdelayブロックが配設されます。すなわち、

moving_ave.out(in)
  x@(0:6) = delay(in, x@(0:5))
  out = sum(in, x@(0:6)) / 8

とすることで、二行目は以下のように展開され、移動平均が算出されます。

x@0 = delay(in)
x@1 = delay(x@0)
x@2 = delay(x@1)
x@3 = delay(x@2)
x@4 = delay(x@3)
x@5 = delay(x@4)
x@6 = delay(x@5)

sumは任意の数の入力に対して和を演算するブロックで、sumの入力ポートが階数1のリンクリストとして定義されていれば、リンクリストの各要素が単一のsumブロックの入力に与えられます。

リンクリストの演算において、リストに含まれるリンクの数が異なる場合は、次の規則に従って処理します。

・左辺のリンク数が少ない場合は、右辺の余分なリンクに対する演算は無視されます
・右辺のリンク数が足りない場合は、直前に表れたリンクがコピーされます

たとえば、左辺がリンク数3の場合、右辺に表れる(a, b)は(a, b, b)と、aは(a, a, a)とみなします。この規約により、ベクトルのスカラー積も自然に書き下すことができます。

同様に、リンクリストの一部が省略された場合は、その前の最後に書かれたリンクが記述されたものとみなします。この規約は、マルチプレクサで複数のセレクタ値が同じ信号を選択する際に有用となります。たとえば、x = (a,, b)@selは、selが0と1の場合にaを、2の場合にbを選択します。

リンクリストに対するもう一つの演算子として、降階演算子“'”を準備します(かっこを外す「皮むき」という意味で、ピーラーなりストリッパーと呼んだほうが良いかもしれません)。降階演算子は、リンクリストの後ろに記述し、その前のリンクリストの階数を一つ低下させる作用をします。すなわち、((a, b)’, (c, d)’)は(a, b, c, d)を意味します。

この演算子が意味を持つのは、リンクリスト名を用いる場合で、たとえばdat1.(q, r)とdat2.(q, r)に対して(dat1, dat2)とすれば((dat1.q, dat1.r), (dat2.q, dat2.r))と解釈される一方、(dat1’, dat2’)とすれば(dat1.q, dat1.r, dat2.q, dat2.r)とすることができます。

なお、この部分については、現在検討中であり、(dat1, dat2)と書いただけで(dat1.q, dat1.r, dat2.q, dat2.r)と解釈するのが妥当であるかもしれません。なにぶん、(dat1)が(dat1.q, dat1.r)と解釈されますので。この場合は、((dat1.q, dat1.r), (dat2.q, dat2.r))と解釈させたい場合は((dat1), (dat2))と記述することになり、降階演算子は不要になります。

実は、(in, x@(0:5))という書き方は、後者の記法にもとづくもので、降階演算子を用いる場合は(in, x@(0:5)')とするのが正しい書き方です。降階演算子を用いれば厳密な記述が可能となるのですが、記述が少々不自然になる点が悩ましいところです。

リンクリストは、元々は複数の出力を持つブロックを扱うために、入力ポートの記述形式と統合する形で導入されたものですが、インデックス参照を可能とする@演算子といくつかの規約を導入することで、次のような機能も実現されます。

・配列的記述
・if式とcase文(マルチプレクサ)
・ベクトル演算(for文に類似した機能)

CPUには、配列に対応するインデックス付アドレッシングや、if・for・whileに対応する条件付きジャンプ命令があるのですが、パイプライン処理装置には機能ブロックとリンクしかありません。あえてCに類似した記述方法とせずに、リンクリストを用いて記述することで、実装との対応をわかり易くし、効率的な論理の記述が可能となると期待しております。
posted by 管理人 at 07:45| Comment(0) | TrackBack(0) | 日記
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/175117218

この記事へのトラックバック
Powered by さくらのブログ