(57)【要約】【課題】      プレフィックス演算器に関する合成処理を自動的に行う装置等を提供する。【解決手段】  プレフィックス演算器合成装置９は、第１入力群に対するプレフィックス演算における演算の演算結果及び第２入力群に対するプレフィックス演算における演算のうち所定の条件を満たす演算の演算結果に基づく演算を追加して生成された第１入力群と第２入力群からなる入力群に対するプレフィックス演算を特定可能な情報に基づいて、プレフィックス演算を行う回路を特定可能な回路情報を生成する。【選択図】  図１
2008102632.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の入力ｘｎ，…，ｘ１に対して出力ｙｉ（ｉは１以上ｎ以下の数）が結合則を満たす演算・を用いてｙｉ＝ｘｉ・…・ｘ１により計算されるプレフィックス演算を行う回路を特定可能な回路情報を生成するプレフィックス演算器合成装置であって、
前記入力の一部である第１入力群ｘpos，…，ｘpos-k+1に対するプレフィックス演算における演算の演算結果及び前記入力の一部である第２入力群ｘpos-k，…，ｘpos-k-j+1に対するプレフィックス演算における演算のうち所定の条件を満たす演算の演算結果に基づく演算を追加して前記第１入力群及び前記第２入力群からなる入力群ｘpos，…，ｘpos-k-j+1に対するプレフィックス演算を特定可能な情報を生成するプレフィックス演算情報生成手段を備えるプレフィックス演算器合成装置。
【請求項２】
前記所定の条件を満たす演算は前記第２入力群の全ての入力に関する演算である、請求項１記載のプレフィックス演算器合成装置。
【請求項３】
前記プレフィックス演算を行う回路の制約条件に基づいて前記追加される演算の制約条件を求める制約条件演算手段を備え、
前記プレフィックス演算情報生成手段は、前記制約条件演算手段により求められた制約条件を満たすプレフィックス演算を特定可能な情報を生成する、請求項１又は２に記載のプレフィックス演算器合成装置。
【請求項４】
前記プレフィックス演算情報生成手段は最適化手法を用いて前記プレフィックス演算を特定可能な情報を生成する、請求項１から３のいずれかに記載のプレフィックス演算器合成装置。
【請求項５】
プレフィックス演算における演算の数をヒューリスティックに減少させる処理を行うノード数減少処理手段を備える請求項１から４のいずれかに記載のプレフィックス演算器合成装置。
【請求項６】
ｎ個の入力ｘｎ，…，ｘ１に対して出力ｙｉ（ｉは１以上ｎ以下の数）が結合則を満たす演算・を用いてｙｉ＝ｘｉ・…・ｘ１により計算されるプレフィックス演算を行う回路を特定可能な回路情報を生成するプレフィックス演算器合成方法であって、
プレフィックス演算情報生成手段が、前記入力の一部である第１入力群ｘpos，…，ｘpos-k+1に対するプレフィックス演算における演算の演算結果及び前記入力の一部である第２入力群ｘpos-k，…，ｘpos-k-j+1に対するプレフィックス演算における演算のうち所定の条件を満たす演算の演算結果に基づく演算を追加して前記第１入力群及び前記第２入力群からなる入力群ｘpos，…，ｘpos-k-j+1に対するプレフィックス演算を特定可能な情報を生成するプレフィックス演算情報生成ステップ手段を含むプレフィックス演算器合成方法。
【請求項７】
請求項６記載の方法により生成された回路情報に基づいて生産されたプレフィックス演算器。
【請求項８】
コンピュータに、請求項６記載の方法を実現させるためのプログラム。
【請求項９】
請求項８に記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｎ個の入力ｘｎ，…，ｘ１に対して出力ｙｉ（ｉは１以上ｎ以下の数）が結合則を満たす演算・を用いてｙｉ＝ｘｉ・…・ｘ１により計算されるプレフィックス演算を行う回路を特定可能な情報を生成するプレフィックス演算器合成装置、このプレフィックス演算器合成装置により生成されたプレフィックス演算器、プレフィックス演算器合成方法、コンピュータにプレフィックス演算器合成方法を実現させるためのプログラム、及び、このプログラムを記録する記録媒体に関する。
【背景技術】
【０００２】
演算器合成とは、与えられた制約の下で、加算、乗算等の算術演算を行う回路（演算器）を自動的に生成する処理である。
【０００３】
演算器合成処理においては、多くの場合、ただ機能を実現できればよいのではなく、制約（入力到達時刻や出力要求時刻などのタイミング、最大面積、最大消費電力など）、目的関数（面積最小化、遅延最小化、消費電力最小化など）、コンテクスト（２つのオペランドのビット幅、定数オペランドなど）に応じて適切な構成を生成する必要がある。
【０００４】
演算器は回路全体の品質に与える影響が大きいため、人手で演算器合成処理を行うことが考えられる。
【０００５】
また、最近の論理合成ツールでは、既知の演算器構成を利用して演算器を合成する機能が実現されている。
【０００６】
さらに、加算器のうちプレフィックス加算器（Prefix  adder）と呼ばれるものの合成手法については、例えばZimmermannの手法（非特許文献１参照）やLiuの手法（非特許文献２参照）にあるように、ヒューリスティックな手法が提案されている。
【０００７】
【非特許文献１】R．Zimmermann，“Non-Heuristic  Optimization  and  Synthesis  of  Parallel-Prefix  Adders”，in  Proceedings  of  International  Workshop  on  Logic  and  Architecture  Synthesis，Dec.1996，pp.123-132.
【非特許文献２】Jianhua  Liu，Shuo  Zhou，Haikun  Zhu，and  Chung-Kuan  Cheng,”An  Algorithmic  Approach  for  Generic  Parallel  Adders”，in  Proceedings  of  ICCAD’03，pp.734-740，Nov.2003.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
制約や目的関数が固定であれば人手で作り込むことが可能である。しかしながら、個々の演算器に対する制約や目的関数はその演算が実行される状況によって異なり、設計過程で定まる状況に合わせて各々に適切な回路を人手で作るのは困難である。
【０００９】
また、既知の演算器構成を利用すれば論理合成レベルでの簡単化はなされるが、コンテクストに合わせて概略構成自身を変形することはできない。
【００１０】
さらに、Zimmermannの手法やLiuの手法はヒューリスティックなものであり、例えば遅延制約下での面積最小化問題などに関して最小解を保証することができない。
【００１１】
そこで、本発明の目的は、制約や目的関数が異なっても、演算器、特にプレフィックス演算（Prefix  computation）に関する演算器に関して、ヒューリスティックな手法のみに依存することなく自動的な合成処理をする装置等を提供することである。
【課題を解決するための手段】
【００１２】
請求項１に係る発明は、ｎ個の入力ｘｎ，…，ｘ１に対して出力ｙｉ（ｉは１以上ｎ以下の数）が結合則を満たす演算・を用いてｙｉ＝ｘｉ・…・ｘ１により計算されるプレフィックス演算を行う回路を特定可能な回路情報を生成するプレフィックス演算器合成装置であって、前記入力の一部である第１入力群ｘpos，…，ｘpos-k+1に対するプレフィックス演算における演算の演算結果及び前記入力の一部である第２入力群ｘpos-k，…，ｘpos-k-j+1に対するプレフィックス演算における演算のうち所定の条件を満たす演算の演算結果に基づく演算を追加して前記第１入力群及び前記第２入力群からなる入力群ｘpos，…，ｘpos-k-j+1に対するプレフィックス演算を特定可能な情報を生成するプレフィックス演算情報生成手段を備えるものである。
【００１３】
請求項２に係る発明は、請求項１記載のプレフィックス演算器合成装置であって、前記所定の条件を満たす演算が前記第２入力群の全ての入力に関する演算であるものである。
【００１４】
請求項３に係る発明は、請求項１又は２に記載のプレフィックス演算器合成装置であって、前記プレフィックス演算を行う回路の制約条件に基づいて前記追加される演算の制約条件を求める制約条件演算手段を備え、前記プレフィックス演算情報生成手段が、前記制約条件演算手段により求められた制約条件を満たすプレフィックス演算を特定可能な情報を生成するものである。
【００１５】
請求項４に係る発明は、請求項１から３のいずれかに記載のプレフィックス演算器合成装置であって、前記プレフィックス演算情報生成手段が最適化手法を用いて前記プレフィックス演算を特定可能な情報を生成するものである。
【００１６】
請求項５に係る発明は、請求項１から４のいずれかに記載のプレフィックス演算器合成装置であって、プレフィックス演算における演算の数をヒューリスティックに減少させる処理を行うノード数減少処理手段を備えるものである。
【００１７】
請求項６に係る発明は、ｎ個の入力ｘｎ，…，ｘ１に対して出力ｙｉ（ｉは１以上ｎ以下の数）が結合則を満たす演算・を用いてｙｉ＝ｘｉ・…・ｘ１により計算されるプレフィックス演算を行う回路を特定可能な回路情報を生成するプレフィックス演算器合成方法であって、プレフィックス演算情報生成手段が、前記入力の一部である第１入力群ｘpos，…，ｘpos-k+1に対するプレフィックス演算における演算の演算結果及び前記入力の一部である第２入力群ｘpos-k，…，ｘpos-k-j+1に対するプレフィックス演算における演算のうち所定の条件を満たす演算の演算結果に基づく演算を追加して前記第１入力群及び前記第２入力群からなる入力群ｘpos，…，ｘpos-k-j+1に対するプレフィックス演算を特定可能な情報を生成するプレフィックス演算情報生成ステップ手段を含むものである。
【００１８】
請求項７に係る発明は、請求項６記載の方法により生成された回路情報に基づいて生産されたプレフィックス演算器である。
【００１９】
請求項８に係る発明は、コンピュータに、請求項６記載の方法を実現させるためのプログラムである。
【００２０】
請求項９に係る発明は、請求項８に記載のプログラムを記録した記録媒体である。
【００２１】
なお、請求項３に記載の制約条件演算手段は、第１入力群及び第２入力群の位置、サイズ等に基づいて、追加される演算の制約条件を求めるものであってもよい。
【００２２】
また、本願発明を、プレフィックス演算器を生産する方法の発明としてとらえてもよい。
【００２３】
さらに、プレフィックス演算情報生成手段が、演算数を最小化するように最適化手法を用いてプレフィックス演算を生成するものであってもよい。
【発明の効果】
【００２４】
本願発明によれば、プレフィックス演算情報生成手段により、第１入力群及び第２入力群に対するプレフィックス演算が一定の構造をもつものに限定して生成され、この制限付きプレフィックス演算の演算結果に基づいて最終的な出力ｙｉを演算する回路を生成することが可能となる。そのため、例えば請求項３に係る発明にあるように、プレフィックス演算における各演算に対する制約範囲を求めることが可能となり、さらに、請求項４に係る発明にあるように、例えば動的計画法のような最適化処理を行うことにより構造を制限された中での最適解を厳密に求めることが可能となる。
【００２５】
また、請求項５に係る発明にあるように、ヒューリスティックな方法を利用することにより、一定の構造を持つプレフィックス演算に限定されることなく、回路を改善することが可能となる。
【発明を実施するための最良の形態】
【００２６】
図１は、本願発明の実施の形態に係るプレフィックス演算器生産システム１を示すブロック図である。プレフィックス演算器生産システム１は、制約や目的関数を記録する制約等記録部３と実現対象となるプレフィックス演算を特定可能な実現対象演算データ保持部５とセルライブラリ７とに保持されたデータに基づいてプレフィックス演算器を生産するシステムであって、プレフィックス演算器を自動的に生成するプレフィックス演算器合成装置９と、プレフィックス演算器合成装置９による合成処理に基づいてプレフィックス演算器を生産するプレフィックス演算器生産部１１を備える。
【００２７】
プレフィックス演算器合成装置９は、生成するプレフィックス演算器において行われる演算の制約範囲を求める制約範囲処理部１３と、制約範囲処理部１３により求められた制約範囲を満たす制限付きプレフィックスグラフを求める制限付きＰＧ最適化部１５と、プレフィックス演算における演算数を減少する処理を行うノード数減少処理部１７を有する。
【００２８】
まず、プレフィックス演算と、このプレフィックス演算を表現するために用いられるプレフィックスグラフについて説明する。
【００２９】
プレフィックス演算とは、ｎ個の入力ｘn，ｘn-1，…，ｘ1及び結合則を満たす任意の演算・が与えられたとき、ｎ個の出力ｙi（１≦ｉ≦ｎ）を(1)式により計算するものである。
【００３０】
【数１】
2008102632.tif 000003
【００３１】
プレフィックス演算では結合則が成り立つ。そのため、逐次的に計算する必要はなく、例えば(2)式にあるように、どの順序で計算しても構わない。
【００３２】
【数２】
2008102632.tif 000004
【００３３】
プレフィックス演算と呼ばれる演算で実現できる演算としては、例えば、加算、減算、インクリメンタ、デクリメンタなどがある。また、プレフィックス演算は、加算を構成要素とする乗算等にも間接的に影響を与える。
【００３４】
図２を参照して、並列プレフィックス加算器（Parallel  prefix  adder）を例にして、２進加算とプレフィックス演算との関係について具体的に説明する。
【００３５】
図２は、並列プレフィックス加算器１０１の構成を示すブロック図である。並列プレフィックス加算器１０１は、入力データの各ビットの論理積及び排他的論理和を行う前処理部１０３と、前処理部１０３の演算結果に基づいてプレフィックス演算を行うプレフィックス演算部１０５と、プレフィックス演算部１０５の演算結果に基づいて加算結果を求める後処理部１０７から構成される。
【００３６】
ｎビットの２進加算の入力をＡ＝ａn，…，ａ1及びＢ＝ｂn，…，ｂ1、出力を和ｓ＝ｓn，…，ｓ1及びキャリー出力ｃnとすると、ｓi及び各ビットのキャリーｃiは(3)式のように定義される。
【００３７】
【数３】
2008102632.tif 000005
【００３８】
ｎビット加算は、個々のビットに対するgenerate関数（ｇ）及びpropagate関数（ｐ）、並びに、それらを複数ビットのグループに拡張したグループgenerate関数（Ｇ）及びグループpropagate関数（Ｐ）を用いて、以下のようにプレフィックス演算を用いてとらえることができる。
【００３９】
すなわち、２進加算は、ｇ、ｐ、Ｇ、Ｐを用いると、前処理部１０３によりｇ、ｐを計算し（(4)式）、プレフィックス演算部１０５によりＧ、ＰからＧ[i:1]を計算し（(5)式）、後処理部１０７によりｓiを計算する（(7)式）ことにより達成できる。ここで、(5)式に着目すると、Ｇの計算には同じｋに対するＰの計算が必要であり、Ｇ、Ｐそれぞれに対する計算を（Ｇ，Ｐ）というペアに対する計算として表現したものが(6)式である。
【００４０】
【数４】
2008102632.tif 000006
【００４１】
各ビットのｇ，ｐを計算する前処理部１０３と各ビットの和を計算する後処理部１０７の構成は一意に決まる。しかし、プレフィックス演算部１０５には自由度がある。そのため、高速計算を行うためには、プレフィックス演算部１０５をいかに構成して並列実行するかが問題となる。
【００４２】
次に、図３を参照して、プレフィックス演算における各演算・をノードとし、演算の実行順序を表現するプレフィックスグラフ（Prefix  Graph）について説明する。
【００４３】
まず、図３におけるノードの記号について説明する。入力数ｎに対して、ノードｖi,j（ｉはｊ以下の数であり、ｊはｎ以下の数である。）はｊ番目からｊ−ｉ＋１番目までのｉ個の入力ｘj, …,ｘj-i+1に対するプレフィックス演算の中間結果を表すとする。例えば、図３（ｂ）のｖ2,4は、２つの入力ｘ4（＝ｖ1,4）とｘ3（＝ｖ1,3）に対するプレフィックス演算の中間結果を表すものである。
【００４４】
図３は、プレフィックスグラフの一例を示す図である。図３（ａ）は(8)式の演算を表すプレフィックスグラフであり、図３（ｂ）は(9)式の演算を表すプレフィックスグラフである。
【００４５】
【数５】
2008102632.tif 000007
【００４６】
各ノードは、演算の中間結果を示しており、ノードのファンインは２項演算・の２つのオペランドに対応する。例えば、図３（ｂ）のノードｖ2,4は２つのファンインｖ1,4及びｖ1,3を持ち、ｖ2,4＝ｖ1,4・ｖ1,3という演算の結果を示している。
【００４７】
さらに、演算の２つのオペランドは、連続した入力範囲に対する中間結果となっている。例えば、図３（ｂ）のｖ2,4は２つの入力３と４に対する演算結果であり、ｖ2,2は入力１と２に対する演算結果である。ｖ4,4はそれらに演算を施した結果であり、連続する４つの入力１から４に対する演算結果である。
【００４８】
ここで、演算の２つのオペランドが連続した入力範囲に対する中間結果となっているとは、連続する範囲を分割したものがノードの各ファンインとなっていることであり、入力範囲を［最上位インデックス：最下位インデックス］と記載すると、ノードｖi,jと２つのファンインノードｖi1,j1,ｖi2,j2（j1>j2）の表す入力範囲には、次の関係がある。すなわち、あるｋ（ｋはｊ−ｉ＋１より大きくｊ以下の数）が存在して、(10)式の関係を満たす。
【００４９】
【数６】
2008102632.tif 000008
【００５０】
次に、プレフィックスグラフの深さについて説明する。入力からあるノードまでのパスの長さの最大値をレベルと呼び、すべてのノードにおけるレベルの最大値をプレフィックスグラフの深さＤと呼ぶ。例えば、図３（ａ）のノード数は３、深さは３であり、図３（ｂ）のノード数は４、深さは２である。また、図３（ｂ）のノードｖ2,2及びｖ2,4はともにレベル１、ｖ3,3及びｖ4,4はともにレベル２である。
【００５１】
プレフィックスグラフにおいて、各出力ｙj（ｊは１以上ｎ以下の数）から入力へのパスは、木構造であり、入力ｘk（ｋは１以上ｊ以下の数）に到達する。このように、プレフィックスグラフ全体は各出力への木構造の集合体である。しかしながら、ノードの共有によりＤＡＧ（Directed  Ascyclic  Graph）になり、厳密解を得ることが困難となる。
【００５２】
そこで、以下に説明するように、図１のプレフィックス演算器合成装置９は、構造が限定されたプレフィックスグラフに基づいてプレフィックス演算器を自動的に生成する。
【００５３】
図４を参照して、構造が限定されたプレフィックスグラフについて説明する。図４は、構造が限定されたプレフィックスグラフの一例を示す図である。
【００５４】
まず、G’(1,j)（ｊは１以上全入力数ｎ以下の数）は、リーフノードｖ1,jのみから構成されるプレフィックスグラフとする。すなわち、G’(1,j)のノード集合は｛ｖ1,j｝であり、エッジ集合は空集合であるとする。
【００５５】
次に、図４を参照して、G’(i+j,pos)（ｉとｊは入力数であり１以上の数、posは入力範囲の最上位インデックスでありｉ＋ｊ以上の数）を、より入力数の小さい２つのグラフG’(i,pos)及びG’(j,pos-i))から以下のように構成する。
【００５６】
まず、G’(i+j,pos)のノード集合Ｖは、ノード集合Ｖaddを｛ｖi+j,pos，ｖi+j-1,pos-1，…，ｖj+1,pos-i+1｝として、グラフG’(i,pos)のノード集合Ｖ1とグラフG’(j,pos-i)のノード集合Ｖ2とノード集合Ｖaddの和集合とする。
【００５７】
また、G’(i+j,pos)のエッジ集合Ｅは、G’(j,pos-i)の入力範囲の最大値に対応するノード（以下では、G’(j,pos-i)のベースノードという。）からノード集合Ｖaddの各ノードへのエッジの集合、および、Ｖaddの各ノードからG’(i,pos)において同じ位置をもつノードｖi,pos，ｖi-1,pos-1，…，ｖ1,pos-i+1へのエッジの集合の和集合をＥaddとして、集合Ｅを集合Ｅ1とＥ2とＥaddの和集合とする。
【００５８】
すなわち、G’(i+j,pos)=(V,E)は、G’(i,pos)=(V1,E1)、G’(j,pos-i)=(V2,E2)、Ｖadd及びＥaddより(11)式により生成される。
【００５９】
【数７】
2008102632.tif 000009
【００６０】
図５を参照して、構造が制限されたプレフィックスグラフ（以下では、「制限付きプレフィックスグラフ」という。）について具体的に説明する。
【００６１】
図５（ａ）は、G’(2,4)とG’(2,2)を生成してG’(4,4)を生成した例を示す図である。すなわち、まず、リーフノードｖ1,4、ｖ1,3、ｖ1,2及びｖ1,1に基づいて、それぞれ、制限プレフィックスグラフG’(1,4)、G’(1,3)、G’(1,2)及びG’(1,1)を生成する。次に、G’(1,4)とG’(1,3)に基づいてG’(1,3)のベースノードｖ1,3に対してノードｖ2,4を追加してG’(2,4)を生成し、G’(1,2)とG’(1,1)に基づいてG’(1,1)のベースノードｖ1,1に対してノードｖ2,2を追加してG’(2,2)を生成する。次に、G’(2,4)とG’(2,2)に基づいてG’(2,2)のベースノードｖ2,2に対してノードｖ4,4及びｖ3,3を追加してG’(4,4)を生成する。
【００６２】
ここで、図５（ａ）のプレフィックスグラフの構造が制限されているというのは、例えばG’(2,4)とG’(2,2)に基づいてプレフィックスグラフを生成する場合に、図５（ｂ）にあるように、ｖ1,1を参照して生成することも可能であるが、G’(2,2)のベースノードｖ2,2に対してノードを追加する点で構造が制限されていることを意味する。
【００６３】
また、図５（ｃ）は、G’(2,2)とG’(3,3)とG’(4,4)を順に生成する例を示し、図５（ｄ）は、G’(2,4)とG’(3,4)とG’(4,4)を順に生成する例を示す。
【００６４】
制限付きプレフィックスグラフは、各出力を計算する木構造を重ね合わせる際にノードを共有することによってプレフィックスグラフ全体としてノード数を削減することを意図したものである。
【００６５】
そして、以下に説明するように、プレフィックスグラフの構造を限定することによって動的計画法が適用でき、図１の制限付きＰＧ最適処理部１１は、入力到達レベル及び出力要求レベルの制約を満たす中でノード数が最小となる制限付きプレフィックスグラフの厳密解を得ることができる。
【００６６】
すなわち、動的計画法は、部分問題の最適解は全体問題の最適解の部分であるという最適性の原理に基づくアルゴリズムであり、対象とする問題において最適性の原理が成り立つ必要がある。制限付きプレフィックスグラフでは、この最適性の原理が成り立つ。
【００６７】
なぜなら、制限付きプレフィックスグラフG’(n,n)は、入力数のより少ない２つのグラフG’(n-k,j)，G’(k,j-(n-k))とＶadd,Ｅaddから構成され、これらの３つの部分は、それぞれは互いに重なりをもたない、独立な部分である。したがって、G’(n,n)のノード数は、G’(n-k,j)及びG’(k,j-(n-k))のそれぞれのノード数と｜Ｖadd｜の単純な和となる。また、G’(row,col)に対してｖrow-k,col-k（ｋは０以上row-1以下の数）をルートノードとすると、G’(n-k,j)，G’(k,j-(n-k))のルートノードに対する要求レベルは、もとのプレフィックスグラフG(n,n)に対する要求レベルRLoから唯一に定まる。入力到達レベルは同一である。そして、G’(n,n)が制約の下でのノード数最小の解であるならば、G’(n-k,j),とG’(k,j-(n-k))は、２つの部分問題、すなわち、RLoから生成される制約RL’oの下でのG(n-k,j)最小化という部分問題とRLoの下でのG(k,j-(n−k))最小化という部分問題に対するそれぞれ最小解である。（なぜなら、最小でないとするならば、それぞれの最小解に置き換えることでG’(n,n)に対するより小さい解が生成されるため矛盾するためである。）
【００６８】
よって、制限付きプレフィックスグラフに関しては、最適性の原理が成り立ち、動的計画法を用いて、部分問題を組み合わせて全体の解を求めることが可能となる。
【００６９】
サイズｎ’＜ｎの部分グラフG’(n’,p)に対する部分問題を解くためには、そのグラフのｎ’個のルートノードに対する要求レベルが必要となる。要求レベルは、そのノードの推移的ファンアウトが決まらないと計算できないため、サイズの小さい順に部分問題を解いている段階では定まらない。そこで、そのノードがとりうる要求レベルの範囲を想定して、それぞれの場合について最適解を求めておき、ファンアウトの構成が決まった段階で、定まった要求レベルに対する最適解を選択していくことで、解を生成する。
【００７０】
部分グラフの各ルートノードが、ｒj通りの値を要求レベルとしてとりうるとすると、サイズｎ’のグラフに対する部分問題としては、それらすべての組合せ、すなわち、ｒ1×…×ｒn’通りの制約集合を考慮する必要があることになり、すべての部分問題において、その制約全てに対する解を求めるのは現実的ではない。そこで、図１の制約範囲処理部１３は、以下のようにして、G’の構造の特徴を利用して、考慮すべき制約の個数を削減する。
【００７１】
まず、サイズｎのプレフィックスグラフに対して、制約として入力到達レベル及び出力要求レベルが与えられるとし、この制約を満たす中で、ノード数最小の制限付きプレフィックスグラフG’(n,n)を求めるものとする。
【００７２】
ここで、プレフィックスグラフの各ノードｖに対する要求レベルＲＬ（ｖ）、到達レベルＡＬ（ｖ）は、下記の式で計算される。すなわち、要求レベルＲＬ（ｖ）は、自分自身に与えられた要求レベル（未定の場合は無限大とする）と、そのすべてのファンアウトノードｖ’の要求レベルに依存し、(12)式で計算される。
【００７３】
【数８】
2008102632.tif 000010
【００７４】
また、ノードｖの到達レベルＡＬ（ｖ）は、そのすべてのファンインノードｖ’の到達レベルに依存し、(13)式で計算される。
【００７５】
【数９】
2008102632.tif 000011
【００７６】
制約を満たすということは、すべてのノードｖにおいて、ＲＬ（ｖ）がＡＬ（ｖ）以上となることである。
【００７７】
そして、制限付きプレフィックスグラフにおけるファンアウトには以下の特徴がある。
【００７８】
まず、G’(n’,pos)（n’はｎ以下の数）の各ノードｖi,jのファンアウトノードは、垂直成分ｖi’,j(i<i’)と斜め成分ｖi’,j’（j<j’，i<i’）の２種類に分類される。以下では、ｖi,jと垂直成分のノードを結ぶエッジを垂直エッジ、斜め成分ノードを結ぶエッジを斜めエッジと呼ぶ。
【００７９】
G’(n’,pos)（n’はｎ以下の数）の各ノードｖi,jは、唯一の垂直エッジをもつ、又は、k個（k≧1）の斜めエッジと高々１個の垂直エッジを持つ、のどちらかである。
【００８０】
ベースノードでないノードは、垂直エッジしかもたず、そのファンアウトノードはベースノードにはならない。そのため、ベースノード以外のノードから出力へのパスは一通りである。
【００８１】
したがって、各部分問題に対して、すべての出力ノードに対する要求レベルを考慮する必要はなく、ベースノードの要求レベルと、それ以外のノード集合用の垂直エッジの個数、という２つの要素のみに着目すれば、すべてのノードの要求レベルを計算することができる。
【００８２】
まず、ベースノード以外のノードの要求レベルについて説明する。制限付きプレフィックスグラフG’(n’,pos)のベースノード以外のノードｖi,j(j≠n’)からG’(n,n)のルートノードｖj,jへの垂直エッジの個数mは、すべてのｖi,jにおいて同一である。そのため、ｖi,jの要求レベルは(14)式で与えられる。
【００８３】
【数１０】
2008102632.tif 000012
【００８４】
RL(ｖj,j)は外部より与えられるので、垂直エッジの個数mが決まれば要求レベルが計算できる。そして、垂直エッジの個数mの範囲は、部分グラフのサイズn’とベースノードの位置posより、mの最小値mminが(15)式で決まる。また、図６を参照して、mの最大値mmaxは(16)式より決まる。
【００８５】
図６は、プレフィックスグラフのノードｖi,jを、そのノードをベースとするG’のサイズ（＝ｉ）ごとに整列させて表示させたときの構造を模式的に表したものである。具体的には、例えば図３（ｂ）のプレフィックスグラフについて、ノードを入力範囲の幅で整列したプレフィックスグラフは、図７に示されるように、ノードｖ1,4、ｖ1,3、ｖ1,2及びｖ1,1がリーフノードであり、ｖ4,4がベースノードであり、ノードｖ4,4、ｖ3,3、ｖ2,2及びｖ1,1がルートノードであるプレフィックスグラフとなる。このように、プレフィックスグラフのノードをサイズで整列させると、左上半分のみノードが存在するような三角形になる。
【００８６】
G’(n’,pos)のルートノード（対角線上に位置するノード）ｖi,j=ｖn’-k,pos-kに対するG’(n,n)のルートノードはｖj,j=ｖpos-k,pos-kであり、それぞれが関与する入力の個数の差は、(pos-k)-(n’-k)=pos-n’となる。１個の垂直エッジは１回の演算が行われることに対応し、１回の演算あたり最低１個の入力が新たに関与することになる。(pos-n’)の差を縮めるのに必要な垂直エッジの個数は、最大で(pos-n’)ということになる。したがって、G’(n’,pos)におけるmの最大値mmaxは、部分グラフのサイズn’とベースノードの位置posから、(16)式により決まる。
【００８７】
そして、とりうるmの値それぞれに対して、要求レベルが決まる。
【００８８】
【数１１】
2008102632.tif 000013
【００８９】
次に、ベースノードの要求レベルの範囲については、その下限は、構造の制約がない場合の最小到達レベルをＡＬminとすると、(17)式で与えられる。また、上限については、ベースノードから出力へのパスは複数存在するが、それぞれにおける垂直エッジの数は、同じグラフのベースノード以外のノードから出力への垂直エッジの数mに等しい。要求レベルは最小値で効いてくるため、斜めエッジの存在は要求レベルを厳しくする方向にしか働かない。したがって、(18)式が成立し、要求レベルの範囲の上限として使うことができる。
【００９０】
【数１２】
2008102632.tif 000014
【００９１】
ただし、構造を制約することによって、全体に対する最適解が得られない場合も生じ得る。そのため、図１のノード数減少処理部１５は、前処理、後処理として、ヒューリスティックにノード数を減少させることにより、解を改善する。
【００９２】
以上にあるように、本願実施例においては、並列プレフィックス加算器合成のようなプレフィックス演算器合成問題を、入出力に対するプレフィックスグラフの深さの制約（階層数制約、レベル数制約）の下でのプレフィックスグラフのノード数の最小化問題として捉えた。しかし、制約のないプレフィックスグラフでは、計算量が莫大で、与えられた制約の下で最適解を厳密に求めることは現実的には不可能である。
【００９３】
本願実施例によれば、制約範囲処理部１１が各ノードの制約を求め、この制約に基づいて制限付きＰＧ最適化部１３が例えば動的計画法により制限付きプレフィックスグラフの最適解を厳密に求めることができる。ある一定の構造をもつプレフィックスグラフのみを対象として、その中で最適解を厳密に求めることが可能となる。また、ノード数減少処理部１５によるヒューリスティックなノード数の減少処理を前処理、後処理として追加することにより、解を改善させることが可能となる。
【図面の簡単な説明】
【００９４】
【図１】本願発明の実施の形態に係るプレフィックス演算器生産システム１を示すブロック図である。
【図２】並列プレフィックス加算器１０１の構成を示すブロック図である。
【図３】プレフィックスグラフの一例を示す図である。
【図４】図１の制限付きＰＧ処理部１５により生成される、構造が限定されたプレフィックスグラフの一例を示す図である。
【図５】（ａ）、（ｃ）及び（ｄ）は構造が限定されたプレフィックスグラフの一例を示す図であり、（ｂ）は構造が限定されていないプレフィックスグラフの一例を示す図である。
【図６】図１の制約範囲処理部１３により求められる垂直エッジの個数mの最大値mmaxを示す図である。
【図７】図３（ｂ）のプレフィックスグラフについて、ノードを入力範囲の幅で整列したプレフィックスグラフを示す図である。
【符号の説明】
【００９５】
９  プレフィックス演算器合成装置
１３  制約範囲処理部
１５  制限付きＰＧ最適化部
１７  ノード数減少処理部
【図１】
2008102632.tif 000015
【図２】
2008102632.tif 000016
【図３】
2008102632.tif 000017
【図４】
2008102632.tif 000018
【図５】
2008102632.tif 000019
【図６】
2008102632.tif 000020
【図７】
2008102632.tif 000021