(57)【要約】  本発明は、一機能を実行する電子回路の合成方法に関する。本方法には、それぞれが１以上の機能的定項を含む１以上の述語を定義することによって、プログラミング言語を用いてその機能をプログラムすることが含まれる。プログラムされた機能の解釈にはゲーム意味論が適用される。各述語は、ムーブに対し定義された１以上のストラテジとして解釈される。プログラムされた機能の各定項は、下位回路に関連付けられる。関連付けられた下位回路の少なくとも１つの入力ポート又は出力ポートを各ムーブに関連付け、ストラテジによって定義されるムーブの発生が関連ポートの状態変化をもたらす。関連付けられた下位回路を組み合わせ、その機能を実行する合成回路を提供する。
2009544091.tif 000002
【特許請求の範囲】
【請求項１】
一機能を実行する電子回路の合成方法であって、
それぞれが１以上の機能定項を含む１以上の述語を定義することによって、プログラミング言語を用いて前記機能をプログラムするステップと、
ゲーム意味論を適用して前記プログラムされた機能を解釈するステップであって、各述語をムーブに対し定義された１以上のストラテジとして解釈するステップと、
前記プログラムされた機能の前記定項の各々に、少なくとも１つの入力ポート及び少なくとも１つの出力ポートを備える下位回路を関連付けるステップであって、前記関連付けられた下位回路の少なくとも１つの入力ポート又は出力ポートを各ムーブに関連付け、ストラテジによって定義されたムーブの発生が関連ポートの状態変化をもたらすステップと、
前記関連付けられた下位回路を組み合わせて、前記機能を実行する合成回路を提供するステップと、
を有する電子回路の合成方法。
【請求項２】
前記プログラムされた機能の各述語は、識別子、手順定義、及び線形手順呼び出しを含むサブプログラムである請求項１記載の電子回路の合成方法。
【請求項３】
各サブプログラムに１以上の型を割り当て、引数に対する処理を記述することによって、前記プログラムされた機能の型とその識別子の型とによって各ムーブを判定する請求項２記載の電子回路の合成方法。
【請求項４】
２以上の引数のコピーを返す引数に対するＳＨＡＲＥ処理の使用によって非線形型を定義する場合を除き、前記言語は線形型の言語である請求項３記載の電子回路の合成方法。
【請求項５】
前記下位回路は、前記ポートへの一連の入力／出力が一ストラテジに対応するよう構成された請求項１〜４のいずれか１項に記載の電子回路の合成方法。
【請求項６】
前記関連付けられた下位回路を組み合わせるステップは、前記関連付けられた下位回路どうしの結線を含む請求項１〜５のいずれか１項に記載の電子回路の合成方法。
【請求項７】
前記関連付けられた下位回路を組み合わせるステップは、前記引数に対応した前記下位回路に対する手続き呼び出しに対応する前記関連付けられた下位回路の結線を含む請求項６記載の電子回路の合成方法。
【請求項８】
ＩＰコアを識別することのできるハードウェア記述言語にて前記合成回路を定義するステップをさらに含む請求項１〜７のいずれか１項に記載の電子回路の合成方法。
【請求項９】
一機能を実行する電子回路の合成方法であって、
それぞれが１以上の機能定項を含む１以上の述語を定義することによって、プログラミング言語を用いて前記機能をプログラムするステップであって、２以上の引数のコピーを返す引数に対するＳＨＡＲＥ処理の使用によって非線形型を定義する場合を除き、前記言語を線形型の言語とするステップと、
ゲーム意味論を適用して前記プログラムされた機能を解釈するステップであって、各述語をムーブに対し定義された１以上のストラテジとして解釈するステップと、
前記プログラムされた機能の前記定項の各々に下位回路を関連付けるステップであって、前記下位回路の少なくとも１つの入力ポート又は出力ポートを各ムーブに関連付け、前記ポートへの一連の入力／出力に一ストラテジを対応させるステップと、
前記関連付けられた下位回路を組み合わせて、前記機能を実行する合成回路を提供するステップと、
を有する電子回路の合成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子回路の合成方法に関する。
【背景技術】
【０００２】
極めて多様な計算及び制御応用分野に、電子デバイスが用いられている。これらのデバイスの設計者は、所定の機能を実行する必要のある電子システムの仕様を定める。これを、そこでデバイス構成要素の実際のハードウェアとレイアウトの仕様へ書き換えねばならない。
【０００３】
電子デバイスと電子システム（例えば、チップに実装したシステムすなわちＳｏＣ）の設計では、半導体の知的所有権コア（ＩＰコア）は知的所有権下にある再使用可能な論理ユニットやセルやチップレイアウト設計である。ＩＰコアは、ＡＳＩＣ（特定用途向けＩＣ）チップ設計又はＦＰＧＡ（書き換え可能ゲートアレイ）論理設計内での構築ブロックとして使用することができる。設計者は、データベース又は入手可能なＩＰコアの資料庫から適当なＩＰコアを選択することができる。
【０００４】
デジタル論理応用では、ＩＰコアは通常は非専売ゲートのネットリストとして提供されている。ネットリストはＩＰコアの論理的機能のブール論理表現であり、売主（所有者）を分解模倣から保護する。一部の版のＩＰコアは合成可能であり、ＶｅｒｉｌｏｇやＶＨＤＬ等のハードウェア記述言語にて提供され、機能レベルでのユーザの改変を可能にしている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＳｏＣ又はＦＰＧＡの設計ならびに構築には、ハードウェア記述言語から必要とされるＩＰコアの時別に用いることのできる形態で実行するのにそのデバイスに必要とされる機能の初期仕様が必要である。一般に、ハードウェア回路の合成に関する出発点は、ＣやＣ＋＋、Ｃ＃、Ｊａｖａ、Ｐａｓｃａｌ等の高級プログラミング言語でのそのデバイスの所要の機能の定義であると考えられている。これらの言語は有用であり、何故なら元来がそれらは表現性が多様であるためである。しかし、この表現多様性はそれらが即ハードウェア仕様へ変換されないことを意味する。１つの主要な障害は、この種言語の非線形性、すなわち手順とその１つの引数が一般に包括的識別子を有することがあるとの事実である。特に、既知の技法を用いて合成される回路はメモリ量（フリップフロップの個数）と必要な結線量の点で過剰な精密さと非効率さとに陥る傾向がある。
【課題を解決するための手段】
【０００６】
本発明の目的は、改善された電子回路の合成方法を提供することである。
【０００７】
本発明によれば、一機能を実行する電子回路の合成方法であって、
それぞれが１以上の機能定項を含む１以上の述語を定義することによって、プログラミング言語を用いて前記機能をプログラムするステップと、
ゲーム意味論を適用して前記プログラムされた機能を解釈するステップであって、各述語をムーブに対し定義された１以上のストラテジとして解釈するステップと、
前記プログラムされた機能の前記定項の各々に、少なくとも１つの入力ポート及び少なくとも１つの出力ポートを備える下位回路を関連付けるステップであって、前記関連付けられた下位回路の少なくとも１つの入力ポート又は出力ポートを各ムーブに関連付け、ストラテジによって定義されたムーブの発生が関連ポートの状態変化をもたらすステップと、
前記関連付けられた下位回路を組み合わせて、前記機能を実行する合成回路を提供するステップと、
を有する電子回路の合成方法が提供される。
【０００８】
本発明の実施形態では、前記プログラムされた機能の各述語は、識別子、手順定義、及び線形手順呼び出しを含むサブプログラムである。各サブプログラムに好ましくは１以上の型を割り当て、引数に対する処理を記述することによって、前記プログラムされた機能の型とその識別子の型とによって各ムーブを判定する。好ましくは、２以上の引数のコピーを返す引数に対するＳＨＡＲＥ処理の使用によって非線形型を定義する場合を除き、前記言語は線形型の言語である。
【０００９】
本発明の実施形態では、前記下位回路は前記ポートの入力／出力系列が一ストラテジに対応するよう構成する。
【００１０】
本発明の実施形態では、前記関連付けられた下位回路を組み合わせるステップは、前記関連付けられた下位回路どうしの結線を含む。また、関連付けられた下位回路を組み合わせるステップは、前記引数に対応した下位回路に対する手順呼び出しに対応する前記関連付けられた下位回路の結線を含んでも良い。
【発明の効果】
【００１１】
ゲーム意味論を適用して（高級）プログラミング言語の定項の型を定義することで、ムーブをハードウェア下位回路の入力ポート及び出力ポートに関連付けることができ、手順とその引数を表わす回路の結線だけで手順呼び出しを解釈できることは、１つの利点である。これを実現可能とするには、それらが可変識別子の一切の共用を所有しない点において、手順の定義及び線形とすべき手順呼び出しを必要とする。プログラムの型に対する回路のポートとの当該関連付けは、そこからＩＰコアを識別することのできるハードウェア記述言語へ容易に変換することができる。
【００１２】
手順呼び出しの合成には線形型が必要とされ、識別子が固有の存在に制限されることを意味する。この制限は、非線形型が許容されたならば高級言語の使用がずっと廉価となることを意味する。共用コマンドがこの制限を軽減することは、１つの利点である。
【００１３】
下記の図面を参照し、本発明の実施形態をここで例示により説明する。
【図面の簡単な説明】
【００１４】
【図１】本発明に係る電子回路の合成に伴う主要段を示すフローチャートである。
【図２Ａ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｂ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｃ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｄ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｅ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｆ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｇ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｈ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｉ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｊ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｋ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｌ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｍ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｎ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｏ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図２Ｐ】本発明に係る合成方法で用いられる下位回路の概略的かつミーリ式の図を含む回路図である。
【図３】本発明に従い合成された回路の概略図である。
【図４Ａ】本発明に従い合成された回路のさらなる例である。
【図４Ｂ】本発明に従い合成された回路のさらなる例である。
【図５Ａ】共用動作用の概略回路図である。
【図５Ｂ】図５Ａの回路の部品に関するミーリ式の図である。
【図６】図５Ｂの図に対応する概略回路図である。
【図７】本発明に従い合成された回路のさらなる例である。
【図８】本発明に従い合成された回路のさらなる例である。
【図９】エラー信号を発する共用動作用回路のミーリ式の図である。
【発明を実施するための形態】
【００１５】
図１を参照するに、電子回路合成における第１のステップ１００は、そのデバイスの機能を特定することにある。これは、適当な高級プログラミング言語を用いるユーザにより、最も簡単に行われる。この機能の仕様を完成すると、さらなるステップを実行して、プログラムされたデバイス機能の定義をデバイスの構築に必要なハードウェア回路へ書き換えねばならない。本発明の原理に従えば、これらのステップには、プログラムされた機能の述語に対するゲーム意味論の適用１０２や、プログラムされた機能の各定項に対する下位回路の関連付け１０４や、デバイス用の合成回路の提供するための関連付けられた下位回路の組み合わせ１０６が含まれる。
【００１６】
第１のステップ１００は、手順又は同様の特徴（機能や方法等）を含む何らかのプログラミング言語を用いて適用することができる。その例には、ＣやＣ＋＋、Ｃ＃、Ｊａｖａ、Ｐａｓｃａｌ等が含まれる。下記の例示目的にとっては、我々がＩＣＡと呼ぶ言語を選択した場合に、より明確となる。ＩＣＡのより詳細な説明は、Ghica,D.R.及びMurawski,A.S.著、「Angelic semantics of Fine-grained concurrency（きめ細かな並列処理の高尚な意味論）」−FoSSaCS（ソフトウェア科学及び計算構造の基礎）、２００４年度、ｐｐ．２１１−２２５に見出すことができる。この言語は必要とされる必須の命令形式の手順上の特徴を有するが、「理論的にすっきりしており」、他の多くの言語よりも明確な構文規則（シンタクス）と意味論（セマンティクス）（より簡単でよりすっきりとした表現）とを有するものである。
【００１７】
我々は、この言語の型直結表現を提供することにする。この言語のベースの型は、コマンド表現、変数表現、及びセマフォー（ブール論理）表現である。
σ：：＝ｃｏｍ｜ｖａｒ｜ｓｅｍ｜ｂｏｏｌ
加えて、この言語はより高次の型形式を含んでいる。
θ：：＝σ｜θ→θ｜θ×θ
すなわち、関数と論理積である。
【００１８】
整数や配列等の幾つかの他の一般の型は簡便さに配慮して省略してある。何故なら、それらはこのより小さな言語にて容易にエンコードできるためである。所与の例において、我々は整数や配列の存在をそれらの自明な符号化を用いて想定することができる。
【００１９】
述語（下位プログラム）は、定項、アブストラクション（手順の定義）及びアプリケーション（手順呼び出し）から形成される。表１に言語定項を示す。
【００２０】
【表１】
2009544091.tif 000003
【００２１】
この機能化構文規則（シンタクス）は特異に見えるが、それは極めて好都合なものである。より在来型の構文規則は、容易にこれにエンコードすることができる。
bool x;
if (y)  {
x = z && t;
}
else  {
x = z || t;
}
例えば、上記プログラムは、関数化された構文規則を用いて、下記のように書き表される。
newvar(λx. if y (asg(and(deref z)(deref t))x)(asg(or(deref z)(deref t))x))
明らかに、前者はより読み取りが可能であるが、後者はその言語の表現にとってより好都合である。この差異は、本旨の１つではない。
【００２２】
述語は、下記の形式の型判断により記述される型を有する。すなわち、
【数１】
2009544091.tif 000004
なお、Γ＝ｘ１：θ１，…ｘｎ：θｎは変数型の割り当てであり、Ｍは述語であり、θは述語の型である。
【００２３】
アブストラクションとアプリケーションに関する規則は、我々がその引数に対し１つの機能を適用する際に、それらが変数識別子の共用が許されないという意味において、線形である。線形型システムは一般にプログラミング言語内で使用され、資源の利用、特にメモリの利用を制御又は制限する。ハードウェアの合成において、各回路又は下位回路は恣意的に共用できない資源であり、これが線形型高度に関連付ける。
【００２４】
非線形型は、線形型よりもずっと広範に用いられている。線形型はより表現力に乏しく、それが変数を唯一無二の生起に限定するためである。例えば、ｘ＝ｘ＋１等の共通述語は線形型に型分けできない。何故なら、変数識別子ｘが２回出現するためである。束ねられた型等の一部の型システムは、どのような文脈で非線形型が安全に使用できるかを特定することでこの問題に対処するが、この種のシステムは極めて制限的でもある。
【００２５】
本発明の実施形態は、異なる手法を採用する。我々は、その言語に新規演算を導入する。すなわち、
ｓｈａｒｅθ：θ→（θ×θ）
この演算は、引数の２つのコピーを返送する。
【００２６】
この処理を用いることで、究極的には、我々が非線形型言語と同じように表現力に富む言語に最後に至ることを数学的に証明することができる。例えば、述語ｘ＝ｘ＋１は、ｓｈａｒｅを用いて次のように書き表すことができる。
【数２】
2009544091.tif 000005
明示的共用を有する線形型言語は暗示的共用を有する非線形型言語と同じく表現性が多様であるが、前者は可変識別子の共用時に極めて正確なハンドルをもたらし、これは回路の共用管理において不可欠と見なされる。
【００２７】
最後に、構文規則上の混乱を最小すべく、我々は必要に応じて関数の取捨選択を自動的に行うことを想定する。
【００２８】
この言語からは、幾つかの共通する特徴が消失している。
［再帰］  我々は、反復や或る種限定された後尾再帰の形態だけを許容できる。その理由は基本に根差すものであり、完全再帰は高出力のコンピュータを必要とし、有限な状態にある密接に関係するハードウェアの合成とは一見して両立しないためである。
［ポインタ］  ダイナミックメモリは、ハードウェアの静的特徴に無骨に適合する。しかし、外部メモリを管理するダイナミックメモリ式の処理を提供することができる。これは概念的な限定とはならないものの、技術的には複雑となる。
［制御］  飛越し処理と例外処理は、制御用のゲーム意味論モデルに従うこの枠組み内に導入することができる。
【００２９】
図１に例示した方法の次のステップ１０２は、プログラム述語へのゲームストラテジの適用が含まれる。ゲーム意味論の全技術的細部に立ち入らないのであれば、主要点は下記の通りである。
１．各述語は、一連の行為群により解釈される。その行為は、ムーブや一連のプレイ、セットストラテジと呼ばれる。
２．述語のストラテジに用いられるムーブは、その述語の型判断により定義する。特定のムーブは１つのストラテジ内で２回以上生起することがあり、ムーブの各生起をムーブ生起と呼ぶ。
３．アプリケーションを通じた述語の組成に対応するストラテジの組成の良好に定義された表記が存在する。
詳細については、読者はGhica,D.R.及びMurawski,A.S.著、「Angelic semantics of Fine-grained concurrency（きめ細かな並列処理の高尚な意味論）」−FoSSaCS（ソフトウェア科学及び計算構造の基礎）、２００４年度、ｐｐ．２１１−２２５を参照されたい。
【００３０】
署名（型判断に出現する型）に関連するムーブは、下記のセット構成により与えられる。
【数３】
2009544091.tif 000006
【００３１】
図１のステップ１０４は、プログラムされた機能の各定項への下位回路の関連付けを含む。述語下位回路は、１つの回路（すなわち、通常の意味での電子回路）を意味するが、結果的にデバイスを構築する電子回路全体とは差別化するよう、これを本願明細書では用いている。一例として、ＩＣＡ定項のゲーム意味論解釈は下記のように有限状態変換器としてモデル化できる。
・デジタル回路（下位回路）に何らかのＩＣＡ定項を関連付ける。
・入力ポートに何らかの入力ムーブ（ブール論理ムーブtt，ffを除く)を関連付ける。
・出力ポートに出力ムーブを関連付ける。
・ポートの変化状態に何らかのムーブ生起を関連付ける。
なお、ブール論理ムーブtt，ffに対するポートの関連付けは異なる。すなわち、
・我々は２ビットバスを使用する。
・ビットの一方はデータ（０＝ff，１＝tt）用である。
・他方のビットは「ready」ビットである。
・データは「ready」ビットが反転する際にクロック周期内でのみ有効と見なすことができる。
・同じ方式（data＋「ready」ビット）を整数ムーブのエンコードに使用する。
特殊ケースとして効率上の理由からブール論理（整数）処理を実行し、可能である場合は常に組み合わせをもって状態回路を置換することでＩＣＡ定項のエンコードに必要とされる回路網の量を低減する。
【００３２】
これらの関連付けが一旦なされると、関連付けられた変換器の合成は標準的となる。好都合であるときは常に、我々は回路の概略を提示する。さもなくば、我々は下記の方法で回路をミーリ式変換器として提示し、遷移に対する１つの働きかけ（入力又は出力のいずれか）は回路のポート上の論理値の切り換わりと解釈しなければならず、我々がポートＡ上に特定の値ｂを必要とする場合、我々はＡ＝ｂと書き込む。
【００３３】
定項である真（１）や偽（０）、処理無し（skip）、割り当て（asg）、逆参照（der）、順序付け（seq）に関する関連付けられた下位回路の例を、図２Ａ〜図２Ｆに示す。コマンドの順序付けだけでなく、セマフォーの定項把握（グラブ）と放出（リリース）（grbとrls）の関連付けも行う例示下位回路は、同様に直截的である。これらの下位回路は極めて高速であり、実装は経済的であることに留意されたい。さらに、これらの下位回路を組み合せてより大規模な回路を合成する際、それらの多くが単純な結線へ切り詰められことになる利点が存在する。この単純化は、フェッチ・アンド・エグゼキュート（取出し実行）型の合成方法を含む先行技術の方法を用いて達成することは出来ない。
【００３４】
分岐（if）定項と反復（while）定項のための例示下位回路が図２Ｇと図２Ｈに示され、ここで我々は回路ＳＷＩＴＣＨが図２Ｉのミーリ式の図に示された挙動を有するものと想定している。局所変数宣言定項（newvar）については、関連付けられた下位回路が図２Ｊに示され、補助回路ＣＥＬＬは図２Ｋのミーリ式の図により規定されている。
【００３５】
局所セマフォー宣言定項（newsem）について、関連付けられた下位回路の一例が図２Ｌに示され、補助回路ＳＥＭは図２Ｍのミーリ式の図により規定されている。これは、これまで定義された最も高価な下位回路となる。Ｘｉｌｉｎｘ  Ｖｅｒｉｌｏｇを用いて合成すると、その回路は５個のフリップフロップを組み込む。しかし、より効率的な回路を設計してこの機能を提供することが可能であろう。また、セマフォー宣言下位回路はミューテックス（相互排他）機能を全く備えておらず、実際に同時並列的に使用した場合（例えば、グラブ定項とリリース定項とを同時に呼び出した場合）、その挙動は不定となる。我々は、共用処理に関連してこの問題をさらに下記に論ずる。
【００３６】
コマンドの同時並列的実行は、図２Ｎに示すミーリＣ素子の形態をとる類似の基本的回路網を必要とする。
【００３７】
論理演算子は、図２Ｏと図２Ｐの下位回路に示すように、逐次版又は並列版のいずれかに提供することができ、同図中、補助ＣＥＬＬ回路はａ１（０）が切り替わったときにａ１（１）の状態となる。
【００３８】
上記は、ゲーム意味論のアプリケーションが経済的な回路へ通ずることを例示する。しかし、本方法の実際の威力はアブストラクション（手続きの定義）とポートの再標識付けとしてのアプリケーション（手続き呼び出し）と、下位回路を組み合わせたときの回路の個々の結線（図１のステップ１０６）の実施にある。
【００３９】
しかし、まず自由識別子を見よう。このコンパイル法は合成式であるため、それはたった１つの変数からなるものを含む何らかの下位プログラムを取り扱わねばならない。この種プログラムに対する型判別を下記に示す。
【数４】
2009544091.tif 000007
自由識別子に関するゲーム意味論解釈はいわゆる模倣ストラテジであり、全ての入力ムーブは出力へ複製される。合成すると、これはθｌ，θｒのムーブに関連する入力ポートから同一種のムーブの出力ポートへの単なる結線となる。
【００４０】
アブストラクションについては、型規則を再度検討する。
【数５】
2009544091.tif 000008
これは、引数ｘを用いる手順の解釈を、自由可変識別子ｘを有する述語の解釈から導出すべきであることを示す。事実、ゲーム意味論にあっては、これは単にΓ，ｘ：θ and θ’に関連するムーブのΓ and θ→θ’に関連するムーブへの再標識付けに過ぎない。換言すれば、自由可変識別子としてｘを用いるプログラムを提示するあらゆる回路は、ｘを引数として用いる１つの手順と見なすことができる。これは、手順の定義が追加の回路網を一切必要としないことを意味する。
【００４１】
最後に、（線形）アプリケーション（手順呼び出し）はゲーム意味論内ではストラテジの構成要素として解釈される。しかし、これは手順入力の引数出力への結線に対応しており、その逆も真であることが見て取れる。下記アプリケーション用に合成された回路が、明示的に図３に示される。
【数６】
2009544091.tif 000009
【００４２】
前記に我々が見た例として、この回路は下記手順を計算（Ｃと同様の構文規則）するものである。
bool add (bool (*f) (bool), bool (*g) (bool), bool x, bool y) {
return f(x) && f(y);
}
我々の関数化構文規則では、
λf, λg, λx, λy, and(fx)(gy):(bool1→bool2)→(bool3→bool4)→bool5→bool6→bool7
と書き表わされる回路が、図４Ａに示されている。しかし、大半のボックスは、図４Ｂに示した回路に到達するよう、直線状とすることのできる内部結線しか含んでいない。
【００４３】
この時点で、我々はプログラム内の全ての構造的情報（変数やアブストラクションやアプリケーション）が回路結線の仕方にて単純にエンコードされることを見て取った。多くのプログラム基本命令（定項や割り当てや変数操作やセマフォー操作や系列化）もまた、まさに結線である。重要な機能だけは、局所的宣言と算術論理演算子とにより行う。その理由はアプリケーション規則の線形性に存し、我々のプログラムでは我々は変数を厳密に一度しか使用しない。これが、鍵を握る単純化である。しかし、既に前記した如く、この単純化はプログラミング言語の表現多様性に対して制限を課す。これらの制限を取り除くため、我々はｓｈａｒｅ処理の使用時に非線形性から逃避する必要がある。
ｓｈａｒｅθ：θ１→（θ２×θ３）
ｓｈａｒｅのゲーム意味論は、下記の通りである。
・第１のムーブはθ２又はθ３となり、それが入力ムーブとなる。
・ムーブが生起する構成要素を記憶する。
・ムーブのコピーを、θ１に対し発行する。
・受け入れる次のムーブは、θ１に対する入力ムーブである。
・このムーブのコピーを記憶済み構成要素に対し発行する。
・このサイクルを反復する。
【００４４】
ｓｈａｒｅ用の簡単な下位回路例が、図５Ａに示されている。補助回路ＭＤは、下記目的に役立つ。すなわち、選択線路が切り替わったときは常に、入力線路ｉはｉ自体が切り換わって図５Ｂのミーリ式の図に示すように「閉成（closed）」に戻されるまで、「開成（open）」状態とされる。
【００４５】
上記に特定された回路ＭＤは実際には極めて複雑であり、標準的な実装には４個のフリップフロップと８個のゲートが必要となる。しかし、手製の特定目的回路は、同じ機能向けより軽量の解決策を提示し得る。
【００４６】
一般に、ｓｈａｒｅθは、下記のアルゴリズムにより合成することができる。
θ内の各入力ムーブｋ毎に、
１個の出力ポートＩ１ｋを生成し、
２個の入力ポートＩ２ｋ，Ｉ３ｋを生成し、
ＸＯＲゲートを用い、これら３個を接続する。
出力Ｉ２を用いて全てのＩ２ｋをＸＯＲゲートへ接続し、
出力Ｉ３を用いて全てのＩ３ｋをＸＯＲゲートへ接続する。
θ内の各出力ムーブｋ毎に、
１個の入力ポートＯ１Ｋを生成し、
２個の出力ポートＯ２ｋ，Ｏ３ｋを生成し、
ＭＤの２つの実体を作成し、
ＭＤのポートＳをＩ２へ、ポートＩをＯ１ｋへ、ポートＯをＯ２ｋへ接続し、
ＭＤのポートＳをＩ３へ、ポートＩをＯ１ｋへ、ポートＯをＯ３ｋへ接続し、
ＭＤの全ての事例を共通のクロックポートへ接続する。
【数７】
2009544091.tif 000010
これは図６に概略が示されてあり、ここではＧＸＯＲはバス内の全てのポートの包括的ＸＯＲであり、ＥＸＯＲは２つのバスのビットに関するＸＯＲである。すなわち、最初のものはｎ列ゲートを必要とし、次のものはｎバイナリーゲートを必要とする。ｎ＝１の場合、我々はＧＸＯＲゲートを結線で置き換える。
【００４７】
単純な例で、その引数を２回実行する手順を見ることにしよう。Ｃと同様の構文規則では、これは下記となるはずである。
void twice (void (*c) () ) {
c() ; c() ;
return ;
}
流線形の構文規則では、この手順はλｃ．ｓｅｑｃｃとなる。共用を用い、線形性を再確立することで、上記はλｃ．ｓｅｑ（ｓｈａｒｅｃｏｍｃ）：ｃｏｍ→ｃｏｍ’のように書き表される。合成された下位回路を図７に示す。
【００４８】
実施に最も高価な処理が共用であり、それが被共用構成要素との間での信号のやや複雑な多重化や多重分離を必要とすることは明らかである。それ故、複製を代替使用することで絶対的必要時のみ共用を使用することが賢明である。複製対共用の最も単純な例示が、我々の基本回路の合成である。我々は、各処理に１つの回路を用い、それがプログラム内で使用されるときは常にそれらを共用するだけとし得る。しかし、これは極めて不十分であるた、その代りに、我々はこの種の各回路の複製を使用する。
【００４９】
((λxλy. F)(share x)) (M)
より具体的には、構成要素Ｍを上記のように共用する場合、このプログラムをより効率的に等価プログラムに変換できる。
(λxλy. F)(M1)(M2)
なお、Ｍ１とＭ２はＭの例であり、全ての自由変数識別子は別個のものに置き換えてある。
【００５０】
共用又は複製がより効率的であるか否かは、Ｍの合成とｘの共用に必要な回路網量を測り、最廉価の代替例を選択することで、コンパイル時間にて厳密に算出することができる。
【００５１】
一般に、混合と共用と同時並列処理は、周知の競合状態の問題に通ずる。共用資源に対する同時並列的なアクセスを試行する２つの工程は、通常は、芳しくない性能に帰結する。同時並列的プログラミングの文脈では、問題を引き起こす共用資源は、一般にメモリ変数である。ハードウェア合成の文脈において、この問題は変数だけでなく全ての回路についても共用を試行するときに常に生ずることがある。例えば、逐次的にではなく同時並列的に２度その引数を実行する手順の場合を考察する。線形化された表記では、これは下記のように書き表される。すなわち、
λｃ．ｐａｒ（ｓｈａｒｅｃｏｍｃ）：ｃｏｍ→ｃｏｍ’
以前の規則を用いて合成して得られる回路が図８に示される。しかし、これは明らかに間違っている。すなわち、２つの入力信号が、ＸＯＲゲートにおいて、単純に互いを相殺することになり、計算は中断する。これは、前記定義した共用が、順次合成において機能するよう保証するに過ぎないことを示す。さらに、得られる芳しくない挙動が全く予測不能となることがある。
【００５２】
ＩＣＡ又は別の高級言語を用いる機能的仕様からのハードウェアの合成を、Ｖｅｒｉｌｏｇ等のハードウェア記述言語を用いることで採用する。合成されたハードウェアは、特にＦＰＧＡに優れて適したものである。これは、プログラミング言語からのハードウェア合成がＦＰＧＡの迅速設計哲学に適するとの理由と、ＦＰＧＡがラッチを多数抱えていて、そのことが得られる設計において最も苛酷に使用される種の回路となる傾向があるとの技術的理由の両方からである。
【００５３】
実装に関する別の留意点は、可能である場合は常に、計算に不要な余分なクロックサイクルが導入されないようにする上で複合的又は非同期実装を用いることが有利となる点である。合成回路網のモジュラー特性が包括的クロックを必要としない点を強調することは価値あることであり、技術的に言うならば、得られる回路は、包括的に非同期で局所的に同期した（ＧＡＬＳ；globally asynchronous locally synchronous）回路となる。
【図１】
2009544091.tif 000011
【図２Ａ】
2009544091.tif 000012
【図２Ｂ】
2009544091.tif 000013
【図２Ｃ】
2009544091.tif 000014
【図２Ｄ】
2009544091.tif 000015
【図２Ｅ】
2009544091.tif 000016
【図２Ｆ】
2009544091.tif 000017
【図２Ｇ】
2009544091.tif 000018
【図２Ｈ】
2009544091.tif 000019
【図２Ｉ】
2009544091.tif 000020
【図２Ｊ】
2009544091.tif 000021
【図２Ｋ】
2009544091.tif 000022
【図２Ｌ】
2009544091.tif 000023
【図２Ｍ】
2009544091.tif 000024
【図２Ｎ】
2009544091.tif 000025
【図２Ｏ】
2009544091.tif 000026
【図２Ｐ】
2009544091.tif 000027
【図３】
2009544091.tif 000028
【図４Ａ】
2009544091.tif 000029
【図４Ｂ】
2009544091.tif 000030
【図５Ａ】
2009544091.tif 000031
【図５Ｂ】
2009544091.tif 000032
【図６】
2009544091.tif 000033
【図７】
2009544091.tif 000034
【図８】
2009544091.tif 000035
【図９】
2009544091.tif 000036
【国際調査報告】
2009544091.tif 000037
2009544091.tif 000038
2009544091.tif 000039