米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 レジスタ転送レベルフロアプラン方法及びその装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−219976
公開日 平成7年(1995)8月18日
出願番号 特願平6−9328
出願日 平成6年(1994)1月31日
代理人 【弁理士】
【氏名又は名称】前田 弘 (外2名)
発明者 岩▲崎▼ 知恵
要約 目的
レジスタ転送レベルにおいて、動作速度に関する設計制約を考慮しながら全体の面積の最小化を図る。

構成
ブロックの配置情報とパス情報と動作速度に関する設計制約とが入力ファイル7から入力され、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が形状候補テーブル2に登録される。ブロック形状決定部5は、形状候補テーブル2を用いて、ブロックの配置情報に基づき全体の面積を最小にするブロックの形状を決定する。パス遅延計算部6によりブロックの配置情報とパス情報とに基づきパス遅延が求められ、ブロック形状決定部5が動作速度に関する設計制約を満足するまでブロックの形状の変更を繰り返す。これにより、動作速度に関する設計制約を満足するブロックの形状のうち全体の面積を最小にするブロックの形状を求める。
特許請求の範囲
【請求項1】 レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有するレジスタ転送レベルのデータパス設計におけるフロアプラン方法であって、ブロック配置情報とパス情報と動作速度に関する設計制約とを入力する入力処理と、各ブロック毎に、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補を形状候補テーブルに登録する形状候補設定処理と、上記形状候補テーブルを用いて、ブロック配置情報に基づき全体の面積を最小にするブロック形状を初期形状として決定する初期形状決定処理と、ブロック配置情報とパス情報とに基づきパス遅延を求め、動作速度に関する設計制約を満足するまで上記形状候補テーブルを用いてブロック形状の変更を繰り返すタイミング形状最適化処理と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述を出力する構造記述出力処理とを備えていることを特徴とするレジスタ転送レベルフロアプラン方法。
【請求項2】 レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有し、各ブロックをデータの流れの方向に一次元配置するレジスタ転送レベルのデータパス設計におけるフロアプラン方法であって、パス情報と全体のアスペクト比と動作速度に関する設計制約とを入力する入力処理と、各ブロック毎に、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補を形状候補テーブルに登録する形状候補設定処理と、上記形状候補テーブルを用いて、全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小化するブロック形状を初期形状として決定する初期形状決定処理と、各ブロックについて、高さが初期形状の高さ以下であり、伝搬遅延が初期形状の伝搬遅延よりも小さく、且つ幅が最大の幅を持つブロックの幅以下である形状候補が上記形状候補テーブル内に存在する場合に当該形状候補を新たな初期形状として設定することによりブロック形状を変更する形状変更処理と、パス情報に基づいて、動作速度に関する設計制約に対するパス遅延の超過分の総和及び総配線長が最小になるように初期形状のブロックを一次元配置することによってブロック配置情報を生成する配置処理と、上記ブロック配置情報とパス情報とに基づきパス遅延を求め、動作速度に関する設計制約を満足するまで上記形状候補テーブルを用いてブロック形状の変更を繰り返すタイミング形状最適化処理と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述と上記ブロック配置情報とを出力する構造記述出力処理とを備えていることを特徴とするレジスタ転送レベルフロアプラン方法。
【請求項3】 上記タイミング形状最適化処理は、各ブロックの遅延上限値を無限大に設定することにより初期化するステップと、ブロック配置情報とパス情報とに基づいてパス遅延を計算するステップと、現在のブロック形状では動作速度に関する設計制約を満たさない場合に、クリティカルパス上の各ブロック毎に、動作速度に関する設計制約を満足する伝搬遅延を持つブロック形状のうち面積が最小のブロック形状である速度制約満足形状の面積と、現在のブロック形状の面積との差である形状面積差を求めるステップと、クリティカルパス上のブロックのうちの形状面積差が最小の一のブロックの速度制約満足形状の伝搬遅延を当該一のブロックの新たな遅延上限値として設定する一方、クリティカルパス上の上記一のブロックを除く他のブロックの現在のブロック形状の伝搬遅延をそれぞれ当該他のブロックの新たな遅延上限値として設定するステップと、上記形状候補テーブル内の形状候補のうちの遅延上限値以下の伝搬遅延を持つ形状候補から、全体の面積を最小にするブロック形状を求め該ブロック形状を新たな現在のブロック形状として設定するステップとを有していることを特徴とする請求項1又は2に記載のレジスタ転送レベルフロアプラン方法。
【請求項4】 上記タイミング形状最適化処理と上記構造記述出力処理との間に、最大の幅を持つブロックi の幅Wiに対して、幅Wjが条件 Wj <Wi×α(ただし、αは0 <α<1 を満たす定数)を満たすブロックj が存在する場合に、仮に、ブロックj と該ブロックj に隣接するブロックk とをデータの流れの方向に対して垂直に並べて配置することによってブロック配置情報を変更する仮配置処理と、仮に、全体の空き領域が最小になるように上記形状候補テーブルを用いてブロックj 及びk のブロック形状を変更する仮形状変更処理と、上記仮配置処理及び仮形状変更処理の実行後の仮の全体の面積が上記タイミング形状最適化処理の実行直後の全体の面積に比較して減少している場合に、上記仮配置処理によるブロックの配置と上記仮形状変更処理によるブロック形状の変更とを正式に受け入れる配置形状変更処理とをさらに備えていることを特徴とする請求項2に記載のレジスタ転送レベルフロアプラン方法。
【請求項5】 レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有するレジスタ転送レベルのデータパス設計におけるフロアプラン装置であって、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が格納されたライブラリと、ブロック配置情報とパス情報と動作速度に関する設計制約とが記述された入力ファイルと、各ブロック毎に、上記ライブラリに格納された複数の形状候補が登録される形状候補テーブルと、上記入力ファイルに記述されたブロック配置情報及びパス情報に基づいてパス遅延を計算するパス遅延計算手段と、上記形状候補テーブルを用いて、上記入力ファイルに記述されたブロック配置情報に基づき全体の面積を最小にするブロック形状を初期形状として決定すると共に上記入力ファイルに記述された動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返し実行するブロック形状決定手段と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述が記述される出力ファイルとを備えていることを特徴とするレジスタ転送レベルフロアプラン装置。
【請求項6】 レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有し、各ブロックをデータの流れの方向に一次元配置するレジスタ転送レベルのデータパス設計におけるフロアプラン装置であって、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が格納されたライブラリと、パス情報と全体のアスペクト比と動作速度に関する設計制約とが記述された入力ファイルと、各ブロック毎に、上記ライブラリに格納された複数の形状候補が登録される形状候補テーブルと、上記入力ファイルに記述されたパス情報に基づいて、動作速度に関する設計制約に対するパス遅延の超過分の総和及び総配線長が最小になるようにブロックを一次元配置することによってブロック配置情報を生成する配置決定手段と、上記ブロック配置情報と上記入力ファイルに記述されたパス情報とに基づいてパス遅延を計算するパス遅延計算手段と、上記形状候補テーブルを用いて、上記入力ファイルに記述された全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小にするブロック形状を初期形状として決定すると共に上記入力ファイルに記述された動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返し実行するブロック形状決定手段と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述とブロック配置情報とが記述される出力ファイルとを備えていることを特徴とするレジスタ転送レベルフロアプラン装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、レジスタ転送レベルのデータパス設計におけるフロアプラン方法及びその装置に関し、特に、動作速度に関する設計制約を考慮しながら全体の面積の最小化を図るレジスタ転送レベルフロアプラン方法及びその装置に関するものである。
【0002】
【従来の技術】従来、集積回路の設計は、面積制約、動作速度制約を満足するように機能設計、論理設計、レイアウト設計の3つの段階で進められ、徐々にチップの面積、動作速度が具体化されていく。すなわち、機能設計では経験的、概略的な見積りでしかないが、論理設計ではゲート数、セル数、論理接続を基にさらに詳細な見積りを得ることができ、レイアウト設計では実際の面積、配線遅延を含めたタイミング情報を得ることができる。
【0003】さらに、機能設計を、変数のレジスタへの割り付けやオペレーションの演算器への割り付けを行なったレジスタ転送レベルと、それ以前の上位レベルとに分けると、レジスタ転送レベルにおいてはレジスタや演算器の数が明確であるため、より正確な見積りを得ることができる。
【0004】また、集積回路が複数の固まり(ブロック)で表現される場合、各ブロックの配置や形状を決定する処理をフロアプランという。再設計を減らし、全設計工数を短縮化するためには、設計の早い段階におけるブロックの面積やタイミングの見積りの正確さが要求されると共に、その見積りを用いてチップ全体の面積、タイミングを最適化するようなフロアプランを求めることが必要である。
【0005】以下、従来のレジスタ転送レベルにおけるフロアプラン方法について述べる。
【0006】従来のレジスタ転送レベルにおける形状に関するフロアプラン方法としては、チップのアスペクト比、幅又は高さに関する制約を満足し、チップ面積が最小となるブロックの形状を求めるものが、インフォメーション アンド コントロール、59、(1983年)の第91頁から第101頁(Information and Control, Vol. 59, (1983) pp.91-101)において論じられている。
【0007】ここで、従来のレジスタ転送レベルにおける形状に関するフロアプラン方法としてのStockmeyerの形状最適化方法について説明する。
【0008】矩形がn 個の異なる幅w1,...,wn とn 個の異なる高さh1,...,hn とを持ち、90度回転できるとき、その矩形の形状(x,y) の関係R は、R = {(x,y)|y ≧h1,x≧w1 or ... or y≧hn,x≧wnor y ≧w1,x≧h1 or ... or y≧wn,x≧hn}で表される。
【0009】もし、2つの矩形が上下に隣接している場合には、その2つの矩形を囲む矩形の形状の関係R12 は、R12 = {(x,y)|(x,y1)はR1に属する and (x,y2) はR2に属するand y = y1 + y2}となり、左右に隣接している場合には、R12 = {(x,y)|(x1,y)はR1に属する and (x2,y) はR2に属するand x = x1 + x2}となる。
【0010】この関係は図9(a)〜(c)に示すようにx-y の平面グラフで表現できる。図9(a)は矩形Aの形状を示すグラフ、図9(b)は矩形Bの形状を示すグラフ、図9(c)は2つの矩形AとBとが上下に隣接している場合の2つの矩形を囲む矩形A+Bの形状を示すグラフである。このとき、もし矩形A+Bの形状が外部制約により固定である場合、矩形Aの形状及び矩形Bの形状は容易に求まる。例えば、矩形A+Bの幅が3である場合、矩形Aの幅及び矩形Bの幅の何れの幅も3になり、矩形Aの高さ及び矩形Bの高さは共に2となる。
【0011】同様にして、チップ全体の形状関係R をボトムアップに作成し、チップのアスペクト比、高さ又は幅の制約に基づき、トップダウンで各ブロックの形状を決定していく。
【0012】以上のようなStockmeyerの形状最適化方法は基本的な方法であり、その他にも多数の形状最適化方法が提案されている。例えば、上記Stockmeyerの形状最適化方法の改良法が、第29回 エー・シー・エム/アイ・イー・イー・イー デザイン・オートメーション・カンファレンス (1992)の第62頁から第68頁(29th ACM/IEEE Design Automatic Conference (1992) pp.62-68 ))に記載されている。
【0013】一方、従来のレジスタ転送レベルにおける配置に関するフロアプラン方法としては、ビットスライス方式のデータパス設計において、レイアウトモデルに関して、レジスタ、マルチプレクサ、アダー、ALU 、シフタ等の各ユニットをビット幅の大きい順に上から配置し、下方に生じた空き領域を埋めるために、配置を所定の位置で水平にカットし、折り畳む方法が提案されている(アイ・イー・イー・イー インターナショナル・カンファレンス・オン・コンピュータエイディッド・デザイン(1990)の第144頁から第147頁(IEEE International Conference on Computer-Aided Design (1990)pp.144-147 )参照)。
【0014】
【発明が解決しようとする課題】しかしながら、上記のような従来のレジスタ転送レベルにおける形状に関するフロアプラン方法においては、全体の面積又はアスペクト比や、動作速度に関する制約が与えられ、それらを満足するフロアプランを求める問題において、同一機能で形状や伝搬遅延の異なる部品がライブラリに存在する場合や、回路方式により面積や速度が異なると推定される場合にでも、ブロックの遅延を考慮することなく形状を決定するため、面積に対する制約を満たすことはできるが、動作速度制約を満たすことは保証できない。特に、データパス設計においては、ブロックの種類、数は決定しているが、各ブロックの面積、形状、伝搬遅延は未定であるため、全体の面積や動作速度を評価することができないので、例えば、アダーの実現方法として、キャリールックアヘッドを採用するか又はリップルキャリーを採用するかを決定することはできない。
【0015】以上のように、従来のレジスタ転送レベルにおけるフロアプラン方法においては、形状最適化の際にタイミングを考慮した方法が存在しない。このため、設計の早い段階における正確な見積りができないので、再設計を幾度も繰り返すこととなり、膨大な設計工数を要するという問題点がある。
【0016】また、上記のような従来のレジスタ転送レベルにおける配置に関するフロアプラン方法としての、ビットスライス方式のデータパス設計において各ユニットをビット幅の大きさの順に配置する手法では、配線長やパス遅延を考慮していないため、タイミング制約を満足する設計を得ることはできないという問題点がある。
【0017】本発明は、上記に鑑みなされたものであって、レジスタ転送レベルにおいて動作速度に関する設計制約を考慮しながら全体の面積の最小化を図ることが可能なフロアプラン方法及びその装置を提供することを目的とする。
【0018】
【課題を解決するための手段】上記の目的を達成するため、具体的に請求項1の発明が講じた解決手段は、レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有するレジスタ転送レベルのデータパス設計におけるフロアプラン方法を対象とし、ブロック配置情報とパス情報と動作速度に関する設計制約とを入力する入力処理と、各ブロック毎に、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補を形状候補テーブルに登録する形状候補設定処理と、上記形状候補テーブルを用いて、ブロック配置情報に基づき全体の面積を最小にするブロック形状を初期形状として決定する初期形状決定処理と、ブロック配置情報とパス情報とに基づきパス遅延を求め、動作速度に関する設計制約を満足するまで上記形状候補テーブルを用いてブロック形状の変更を繰り返すタイミング形状最適化処理と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述を出力する構造記述出力処理とを備えている構成とするものである。
【0019】また、具体的に請求項2の発明が講じた解決手段は、レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有し、各ブロックをデータの流れの方向に一次元配置するレジスタ転送レベルのデータパス設計におけるフロアプラン方法を対象とし、パス情報と全体のアスペクト比と動作速度に関する設計制約とを入力する入力処理と、各ブロック毎に、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補を形状候補テーブルに登録する形状候補設定処理と、上記形状候補テーブルを用いて、全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小化するブロック形状を初期形状として決定する初期形状決定処理と、各ブロックについて、高さが初期形状の高さ以下であり、伝搬遅延が初期形状の伝搬遅延よりも小さく、且つ幅が最大の幅を持つブロックの幅以下である形状候補が上記形状候補テーブル内に存在する場合に当該形状候補を新たな初期形状として設定することによりブロック形状を変更する形状変更処理と、パス情報に基づいて、動作速度に関する設計制約に対するパス遅延の超過分の総和及び総配線長が最小になるように初期形状のブロックを一次元配置することによってブロック配置情報を生成する配置処理と、上記ブロック配置情報とパス情報とに基づきパス遅延を求め、動作速度に関する設計制約を満足するまで上記形状候補テーブルを用いてブロック形状の変更を繰り返すタイミング形状最適化処理と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述と上記ブロック配置情報とを出力する構造記述出力処理とを備えている構成とするものである。
【0020】請求項3の発明は、具体的には、請求項1又は2の発明の構成に、上記タイミング形状最適化処理は、各ブロックの遅延上限値を無限大に設定することにより初期化するステップと、ブロック配置情報とパス情報とに基づいてパス遅延を計算するステップと、現在のブロック形状では動作速度に関する設計制約を満たさない場合に、クリティカルパス上の各ブロック毎に、動作速度に関する設計制約を満足する伝搬遅延を持つブロック形状のうち面積が最小のブロック形状である速度制約満足形状の面積と、現在のブロック形状の面積との差である形状面積差を求めるステップと、クリティカルパス上のブロックのうちの形状面積差が最小の一のブロックの速度制約満足形状の伝搬遅延を当該一のブロックの新たな遅延上限値として設定する一方、クリティカルパス上の上記一のブロックを除く他のブロックの現在のブロック形状の伝搬遅延をそれぞれ当該他のブロックの新たな遅延上限値として設定するステップと、上記形状候補テーブル内の形状候補のうちの遅延上限値以下の伝搬遅延を持つ形状候補から、全体の面積を最小にするブロック形状を求め該ブロック形状を新たな現在のブロック形状として設定するステップとを有している構成を付加するものである。
【0021】請求項4の発明は、具体的には、請求項2の発明の構成に、上記タイミング形状最適化処理と上記構造記述出力処理との間に、最大の幅を持つブロックi の幅Wiに対して、幅Wjが条件 Wj <Wi×α(ただし、αは0 <α<1 を満たす定数)を満たすブロックj が存在する場合に、仮に、ブロックj と該ブロックj に隣接するブロックk とをデータの流れの方向に対して垂直に並べて配置することによってブロック配置情報を変更する仮配置処理と、仮に、全体の空き領域が最小になるように上記形状候補テーブルを用いてブロックj 及びk のブロック形状を変更する仮形状変更処理と、上記仮配置処理及び仮形状変更処理の実行後の仮の全体の面積が上記タイミング形状最適化処理の実行直後の全体の面積に比較して減少している場合に、上記仮配置処理によるブロックの配置と上記仮形状変更処理によるブロック形状の変更とを正式に受け入れる配置形状変更処理とをさらに備えている構成を付加するものである。
【0022】具体的に請求項5の発明が講じた解決手段は、レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有するレジスタ転送レベルのデータパス設計におけるフロアプラン装置を対象とし、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が格納されたライブラリと、ブロック配置情報とパス情報と動作速度に関する設計制約とが記述された入力ファイルと、各ブロック毎に、上記ライブラリに格納された複数の形状候補が登録される形状候補テーブルと、上記入力ファイルに記述されたブロック配置情報及びパス情報に基づいてパス遅延を計算するパス遅延計算手段と、上記形状候補テーブルを用いて、上記入力ファイルに記述されたブロック配置情報に基づき全体の面積を最小にするブロック形状を初期形状として決定すると共に上記入力ファイルに記述された動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返し実行するブロック形状決定手段と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述が記述される出力ファイルとを備えている構成とするものである。
【0023】また、具体的に請求項6の発明が講じた解決手段は、レジスタ、マルチプレクサ又は演算ユニットのブロックを実現するために複数の形状候補を有し、各ブロックをデータの流れの方向に一次元配置するレジスタ転送レベルのデータパス設計におけるフロアプラン装置を対象とし、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が格納されたライブラリと、パス情報と全体のアスペクト比と動作速度に関する設計制約とが記述された入力ファイルと、各ブロック毎に、上記ライブラリに格納された複数の形状候補が登録される形状候補テーブルと、上記入力ファイルに記述されたパス情報に基づいて、動作速度に関する設計制約に対するパス遅延の超過分の総和及び総配線長が最小になるようにブロックを一次元配置することによってブロック配置情報を生成する配置決定手段と、上記ブロック配置情報と上記入力ファイルに記述されたパス情報とに基づいてパス遅延を計算するパス遅延計算手段と、上記形状候補テーブルを用いて、上記入力ファイルに記述された全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小にするブロック形状を初期形状として決定すると共に上記入力ファイルに記述された動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返し実行するブロック形状決定手段と、上記形状候補テーブルを用いて決定された最終のブロック形状を示す部品名を用いた構造記述とブロック配置情報とが記述される出力ファイルとを備えている構成とするものである。
【0024】
【作用】請求項1の発明の構成により、レジスタ転送レベルのデータパス設計におけるフロアプランにおいて、形状候補設定処理で、各ブロック毎に、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が形状候補テーブルに登録される。この形状候補テーブル内の各ブロック毎の複数の形状候補から、初期形状決定処理により、全体の面積を最小にするブロック形状を初期形状として決定できる。そして、タイミング形状最適化処理により動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返すことによって、動作速度に関する設計制約を満足するブロック形状のうち全体の面積を最小にするブロック形状を求めることができる。
【0025】また、請求項2の発明の構成により、各ブロックをデータの流れの方向に一次元配置するフロアプランにおいて、初期形状決定処理で、全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小化するブロック形状を初期形状として決定する。さらに、形状変更処理により、各ブロック毎に、伝搬遅延が初期形状の伝搬遅延よりも小さく、空き領域を縮小可能なブロック形状に変更することができる。そして、配置処理により、配線長及びパス遅延が最小になるようにブロックの配置を決定することによって、配線長、パス遅延及び面積を最小化する、一次元配置及びブロック形状を求めることが可能になる。
【0026】請求項3の発明の構成により、タイミング形状最適化処理において、パス遅延を計算し、動作速度に関する設計制約に対するクリティカルパスの遅延超過分を改善するようにブロックの遅延上限値を設定し、形状候補を遅延上限値以下の伝搬遅延を持つ形状候補に制限して全体の面積を最小化するブロック形状を求める。全てのパスが動作速度に関する設計制約を満足するまで以上のステップを繰り返し実行することによって、動作速度に関する設計制約を満足するブロック形状のうち全体の面積を最小にするブロック形状を求めることが可能となる。
【0027】請求項4の発明の構成により、各ブロックをデータの流れの方向に一次元配置した後、2つのブロックをデータの流れの方向に対して垂直に並べて配置し、その2つのブロックにより生じる空き領域を最小化するようなブロック形状に変更することによって、全体の面積を最小化する、配置及びブロック形状を求めることが可能になる。
【0028】請求項5の発明の構成により、レジスタ転送レベルのデータパス設計におけるフロアプランにおいて、ライブラリに格納された、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が形状候補テーブルに登録される。この形状候補テーブル内の各ブロック毎の複数の形状候補から、ブロック形状決定手段により、全体の面積を最小にするブロック形状を初期形状として決定できる。そして、ブロック形状決定手段が、動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返すことによって、動作速度に関する設計制約を満足するブロック形状のうち全体の面積を最小にするブロック形状を求めることができる。
【0029】また、請求項6の発明の構成により、各ブロックをデータの流れの方向に一次元配置するフロアプランにおいて、ブロック形状決定手段が、全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小化するブロック形状を初期形状として決定する。さらに、ブロック形状決定手段により、各ブロック毎に、伝搬遅延が初期形状の伝搬遅延よりも小さく、空き領域を縮小可能なブロック形状に変更することができる。そして、配置決定手段により、配線長及びパス遅延が最小になるようにブロックの配置を決定することによって、配線長、パス遅延及び面積を最小化する、一次元配置及びブロック形状を求めることが可能になる。
【0030】
【実施例】以下、本発明の一実施例を図面に基づいて説明する。
【0031】ここで、ブロックとは、レジスタ転送レベルのデータパス設計を構成するレジスタ、マルチプレクサ、演算ユニット(アダー、ALU 、シフタ等)を示し、パスとは、入力ピンからレジスタへのデータの流れ、レジスタ間のデータの流れ、レジスタから出力ピンへのデータの流れ、入力ピンから出力ピンへのデータの流れの4タイプのデータの流れを示すものとする。
【0032】図1は本発明の一実施例に係るレジスタ転送レベルフロアプラン装置の構成を示すブロック図である。
【0033】図1において、1は部品ライブラリ、2はブロック別の形状候補テーブル、3はCPU、4は配置決定部、5はブロック形状決定部、6はパス遅延計算部、7は入力ファイル、8は出力ファイルである。
【0034】部品ライブラリ1に格納されている部品は、機能、幅、高さ、伝搬遅延、レジスタのセットアップ時間、マルチプレクサの入力数、ビット数を持つ。さらに、ビット展開用の1ビットの部品が存在し、Nビットのブロックが1ビットの部品を横一列に並べた構造をとる場合には、Nビットの幅は1ビットの幅のN倍で得られる。
【0035】図2は本実施例のレジスタ転送レベルフロアプラン装置の第1の動作例を示す流れ図である。
【0036】図2において、10は入力処理、11は形状候補設定処理、12は初期形状決定処理、13はタイミング形状最適化処理、14は構造記述出力処理である。
【0037】入力処理10では、入力ファイル7から、ブロックの配置情報とパス情報と動作速度に関する設計制約とを入力する。ただし、配置は、水平又は垂直な直線により階層的に2つの領域に分割可能なスライシング構造とする。パス情報は、パスに含まれるブロックの集合及びそのパスのタイムステップ数により表現する。また、動作速度に関する設計制約は、クロック周期又は動作周波数で与える。
【0038】形状候補設定処理11では、各ブロックに対して、部品ライブラリ1からそのブロックの機能を実現する、幅(W)、高さ(H)、伝搬遅延(T)が異なる複数の形状候補を抽出し、ブロック別の形状候補テーブル2に登録する。
【0039】初期形状決定処理12では、ブロック形状決定部5において、ブロック別に、形状候補の幅と高さとの組が(w1,h1),...,(wn,hn) である場合に、 R = {(x,y)|y ≧h1,x≧w1 or ... or y≧hn,x≧wn} …(式1)
となるように図9に示すような形状グラフを作成し、ブロックの配置情報を基に、従来の形状最適化方法を用いて、全体の面積を最小にする初期形状を決定する。
【0040】次に、タイミング形状最適化処理13では、ブロックの配置情報とパス情報とを基にパス遅延を求め、動作速度に関する設計制約を満足するまでブロックの形状変更を繰り返す。
【0041】最後に、構造記述出力処理14では、ハードウエア記述言語を用い、選択された形状を示す部品名と接続関係とを含む構造記述の出力ファイル8を出力する。
【0042】図3はタイミング形状最適化処理13の詳細な処理の流れを示す流れ図である。
【0043】図3において、20は各ブロックの遅延上限値初期化を行なうステップ、21はパスの遅延計算を行なうステップ、22は速度制約違反判定を行なうステップ、23は形状変更による面積差の計算を行なうステップ、24は遅延上限値の変更を行なうステップ、25は形状変更を行なうステップである。
【0044】ステップ21及びステップ22はパス遅延計算部6が実行し、その他のステップはブロック形状決定部5が実行する。
【0045】ステップ20では、各ブロックの遅延上限値を無限大に初期化する。
【0046】ステップ21では、ブロックの配置情報とパス情報とを基にパス遅延Tpを計算する。
【0047】パス遅延Tpは、(1)入力ピンからレジスタまでのパス又はレジスタ間のパスの場合、Tp = Σ(ブロックの伝搬遅延)+Σ(配線遅延)
+レジスタのセットアップ時間で求め、(2)レジスタから出力ピンまでのパス又は入力ピンから出力ピンまでのパスの場合、Tp = Σ(ブロックの伝搬遅延)+Σ(配線遅延)
で求める。
【0048】ここで、配線遅延は、パス上の2つのブロックを接続するネットの遅延を示し、Krc × L2 で近似する。ただし、Krc は定数、L はブロックの中心間のマンハッタン長である。
【0049】ステップ22では、パス遅延Tpをそのパスのタイムステップ数steps で割った値の最大値が、動作速度に関する設計制約により与えられるクロック周期Tcを超過するか否かの判定を行ない、速度制約を満たすならば本処理を終了する。一方、速度制約を満たさない場合にはステップ23に進む。
【0050】ステップ23では、パス遅延をそのパスのタイムステップ数で割った値が最大であるクリティカルパス上の各ブロックi に対して、{Tp -(Tbi - Tbi')}/steps < Tc(Tbi は現在選択されている形状の伝搬遅延)
を満たす伝搬遅延Tbi'を持つ形状の中から面積が最小である形状を形状候補テーブル2から探索し、その形状の面積と、現在選択されている形状の面積との差ΔAi を求める。
【0051】ステップ24では、クリティカルパス上の各ブロックi の中から、ステップ23で求めた面積の差ΔAi が最小であるブロックを選択し、そのブロックの遅延上限値をステップ23で探索した形状の遅延値に変更する。一方、クリティカルパス上の他のブロックの遅延上限値を、現在選択されている形状の遅延値に変更する。
【0052】このステップにより、面積の増加を最小限にし、クリティカルパスの遅延を速度制約値以下に抑えることができる。
【0053】ステップ25では、各ブロックの形状候補テーブル2内の遅延上限値以下の形状から、(式1)を満たす形状グラフを作成し、従来の形状最適化方法を用いて全体の面積を最小にするブロックの形状を求める。
【0054】その後、ステップ21に戻り、全パスが速度制約を満足するまでステップ21〜25を繰り返し実行する。
【0055】以上のように、本実施例によれば、各ブロックに対して、幅、高さ、伝搬遅延が異なる複数の形状候補が存在し、動作速度に関する設計制約が与えられた場合においても、速度制約を満足し且つ面積が最小のフロアプランを求めることができる。
【0056】図4は本実施例のレジスタ転送レベルフロアプラン装置の第2の動作例を示す流れ図である。
【0057】第2の動作例は、本実施例のレジスタ転送レベルフロアプラン装置を、各ブロックがデータの流れの方向に一次元配置されるレイアウトモデルのデータパス設計に用いるものである。
【0058】図4において、30は入力処理、11は形状候補設定処理、31は初期形状決定処理、32は形状変更処理、33は配置処理、13はタイミング形状最適化処理、34は構造記述出力処理である。
【0059】初期形状決定処理31及び形状変更処理32はブロック形状決定部5が実行し、配置処理33は配置決定部4が実行する。
【0060】入力処理30では、入力ファイル7から、パス情報と全体のアスペクト比と動作速度に関する設計制約とを入力する。さらに、パス情報からデータフローグラフを作成する。データフローグラフの始点は入力ピンを示し、節はレジスタ、マルチプレクサ又は演算ユニットのブロックを示し、終点は出力ピンを示す。枝はそれらの間のデータ転送を示す有向枝である。
【0061】形状候補設定処理11は、第1の動作例と同様の処理である。
【0062】初期形状決定処理31では、第2の動作例では一次元配置を前提としているため、未配置の状態で初期形状を決定する。全体のアスペクト比を満足するブロックの形状の中から、全体の空き領域を最小化するブロックの形状を決定する。
【0063】図5(a)〜(e)は第2の動作例の初期形状決定処理31を説明するための図である。4つのブロックA 、B 、C 、D を一次元配置する場合の例であり、図5(a)、(b)、(c)、(d)はそれぞれブロックA 、B 、C 、D の形状グラフを示し、図5(e)は4つのブロックを一次元配置した全体の形状グラフを示すものである。第1の動作例及び従来例のように2つずつ形状グラフを組み合わせる必要はなく、一括して全体の形状グラフを求めることができる。各ブロックの形状は従来の形状最適化方法を用いる。
【0064】初期形状決定時には、形状グラフ上の最大幅が極端に小さいブロックが存在する場合に、ブロックの幅に凹凸が生じることがある。そこで、形状変更処理32では、任意のブロックが、初期形状と比較して高さが同等以下であり且つ伝搬遅延が小さく、幅が最大の幅を持つブロックの幅以下である形状候補を有する場合、形状変更を行なう。この処理は、空き領域の縮小と遅延時間の短縮とを目的としている。
【0065】配置処理33では、動作速度に関する設計制約により与えられるクロック周期Tcに対するパスの遅延値の超過分の総和及び配線長L の総和が最小になるように一次元配置する。評価関数F を(式2)に示す。
【0066】
F = a ・ΣL + b ・Σ(Tp/steps - Tc) …(式2)
ここで、配線長L 及びパス遅延Tpの求め方は第1の動作例と同様である。(式2)において、a、bはパラメータである。本動作例では、2項目の最適化を優先するために、a=1、b=100と設定する。データフローグラフに従い初期配置を決定し、評価関数F の値を最小化するように配置改善を行なう。改善方法としてはシミュレーティッド・アニーリング法等の手法を用いる。
【0067】図6(a)〜(c)は第2の動作例の配置処理33を説明するための具体例である。図6(a)はデータフローグラフ、図6(b)は配置例、図6(c)は一次元配置最終結果である。図6(b)と(c)とを比較した場合、下から2番目のブロックを通過する配線はどちらも2本であるが、“*”のブロックと“+”のブロックとの高さを比較すると、“*”のブロックの方が大きく、配線長及び配線遅延を最小にするのは図6(c)の配置である。
【0068】タイミング形状最適化処理13は、第1の動作例と同様の処理である。
【0069】最後に、構造記述出力処理34では、ハードウエア記述言語を用い、選択された形状を示す部品名及び接続関係を含む構造記述と、ブロックの配置情報との出力ファイル8を出力する。
【0070】以上のように、本実施例によれば、データの流れの方向に一次元配置するレイアウトモデルに対するデータパス設計において、配線長、パス遅延及び面積を最小化する一次元配置及びブロックの形状を求めることが可能になる。
【0071】図7は本実施例のレジスタ転送レベルフロアプラン装置の第3の動作例を示す流れ図である。
【0072】第3の動作例は、図4に示す第2の動作例の各処理を実行し、さらに、タイミング形状最適化処理13と構造記述出力処理34との間に以下に述べるような処理40〜44を実行するものである。
【0073】図7において、40はブロック幅評価判定処理、41は仮配置処理、42は仮形状変更処理、43は面積評価判定処理、44は配置形状変更処理である。
【0074】仮形状変更処理42はブロック形状決定部5が実行し、その他の処理は配置決定部が実行する。
【0075】ブロック幅評価判定処理40では、最大の幅を持つブロックi の幅Wi、定数α(0 <α<1 )に対して、幅 Wj が条件 Wj <Wi×αを満たすブロックj が存在するか否かを判定する。本動作例ではαを0.5とする。
【0076】仮配置処理41では、ブロックj とブロックj の上又は下に隣接するブロックk とに対して、ブロックj とk とをデータの流れに対して垂直に並べて配置する。
【0077】仮形状変更処理42では、ブロックj の幅とブロックk の幅との和がブロックi の幅Wiよりも小さく、且つ、ブロックj 及びk の高さが最小になるように、遅延上限値の制約の基で、ブロックj 及びk の形状を変更する。
【0078】面積評価判定処理43では、タイミング形状最適化処理13の実行後の全体の面積と仮形状変更処理42の実行後の全体の面積とを比較し、減少しているか否かを判定する。
【0079】配置形状変更処理44では、面積が減少している場合に仮配置処理41の配置及び仮形状変更処理42の形状を受け入れる。
【0080】図8(a)〜(c)は第3の動作例を説明するための具体例である。図8(a)はタイミング形状最適化処理13の実行後の配置であり、図8(b)は配置形状変更処理44の実行後の配置であり、図8(c)はレイアウトモデルである。図8(a)〜(c)において、50は最大の幅を持つブロックi 、51はブロック幅評価判定処理40で求められるブロックj である。フロアプランにおいては図8(b)に示すようにブロックj とk とを横に並べたモデルを扱うが、実際のレイアウトは、ビットスライス方式であるため、図8(c)のようにj とk とがビット順に交互に配置される。
【0081】以上のように、本実施例によれば、ビットスライス方式のデータパス設計の場合でも、部分的に二次元配置を行ない、全体の面積を最小化する配置及び形状を求めることが可能になる。
【0082】
【発明の効果】以上説明したように、請求項1の発明に係るレジスタ転送レベルフロアプラン方法及び請求項5の発明に係るレジスタ転送レベルフロアプラン装置によると、各ブロック毎の、幅、高さ又は伝搬遅延が互いに異なる複数の形状候補が登録された形状候補テーブルを用いて、全体の面積を最小にするブロック形状を初期形状として決定し、動作速度に関する設計制約を満足するまでブロック形状の変更を繰り返すことによって、動作速度に関する設計制約を満足するブロック形状のうち全体の面積を最小にするブロック形状を選択することができる。これにより、レジスタ転送レベルにおいて、タイミングも考慮された形状最適化が可能となる。
【0083】また、請求項2の発明に係るレジスタ転送レベルフロアプラン方法及び請求項6の発明に係るレジスタ転送レベルフロアプラン装置によると、全体のアスペクト比を満足するブロック形状のうち全体の空き領域を最小化するブロック形状を初期形状として決定し、各ブロック毎に伝搬遅延が初期形状の伝搬遅延よりも小さく空き領域を縮小可能なブロック形状に変更し、配線長及びパス遅延が最小になるようにブロックの配置を決定することによって、配線長、パス遅延及び面積を最小化する、一次元配置及びブロック形状を求めることが可能になる。これにより、レジスタ転送レベルにおいて、タイミングも考慮された形状及び配置の最適化が可能となる。
【0084】請求項3の発明に係るレジスタ転送レベルフロアプラン方法によると、パス遅延を計算し、動作速度に関する設計制約に対するクリティカルパスの遅延超過分を改善するようにブロックの遅延上限値を設定し、形状候補を遅延上限値以下の伝搬遅延を持つ形状候補に制限して全体の面積を最小化するブロック形状を求め、全てのパスが動作速度に関する設計制約を満足するまで以上のステップを繰り返し実行することによって、動作速度に関する設計制約を満足するブロック形状のうち全体の面積を最小にするブロック形状を求めるタイミング形状最適化処理を実現することができる。
【0085】請求項4の発明に係るレジスタ転送レベルフロアプラン方法によると、各ブロックを一次元配置した後、部分的に二次元配置することによって、全体の空き領域を縮小することができるため、チップ面積の最小化に優れた効果をもたらす。以上のように、本発明によると、レジスタ転送レベルにおいて、各ブロックの面積及び伝搬遅延の正確な見積りを可能とし、動作速度に関する設計制約を考慮しながら全体の面積の最小化を図ることができる。したがって、集積回路の設計がレイアウト設計へと進んだ後での面積や動作速度の改善のための再設計が不要になり、設計工数の短縮に優れた効果をもたらす。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013