レイアウト設計

配線問題 (Routing Problem)

テーマ	「ＶＬＳＩ／プリント基板における配線問題」
内容	配線問題とは基板、部品位置情報、及びネット情報が与えられた時、 配線禁止領域を通ることなく、配線領域内で配線経路を決定する問題である。 現在は配線領域をチャネル分割、概略配線経路探索、チャネル配線、配線割当という 手順を使って、この問題に取り組んでいる。

テーマ	「制約論理プログラミングによるチャネルルーティング問題へのアプローチ」
内容	本研究室の研究テーマの一つであるVLSI設計の中から、チャネルルーティング 問題に着目します。チャネルルーティング問題とは、２本の平行線（レイヤー） からなるチャネルについて、そのレイヤー上の点（ターミナル）を線で結ぶとき、 すべての線の長さを最小にするような配線（ルーティング）のしかたをみつける 問題です。この問題を制約論理プログラミングを用いて効率良く解く研究をして います。

テーマ	「ビア数最小化問題に関する研究」
内容	現在のVLSI設計やプリント基板レイアウト設計において多層配線は不可欠である。 一本の配線が異なる配線層を通る際にはビアを通じて結線される。 ビアの増加は生産コストや配線領域の増大、抵抗増加や遅延問題による 性能低下などの問題が生じる。よってビアの総数が少ないレイアウト設計が要求 される。この問題をビア数最小化問題という。 そこで本研究では負の重みを持つ辺を正の重みを持つ辺へ変換する手法及び、 ２層配線問題の制約つきビア数最小化問題の近似解法を提案し、 その有用性を実験をもって示す。

設計自動化 (Design Automation)

ＦＰＧＡ

テーマ	「論理エミュレータにおけるネット割り当てに関する研究」
内容	論理エミュレータはFPGAというチップからなっている。エミュレータの利用時にはFPGAを互いに接続する(どのFPGAを接続するかという情報をネットという)必要がある。相互接続は専用のチップにより行なう。どのチップを用いて相互接続をおこなうか(ネットをどのチップに割り当てるか）を求めるアルゴリズムについて考える。
詳細はこちら

テーマ	「FPGA 設計に関する研究」
内容	FPGA(Field Programmable Gate Array)とは、ユーザーがその場で目的に 合わせてプログラムできる LSI である。FPGA は１チップで実現できる回路の 大きさに制限があるため、効率良く FPGA の内部を配置配線する必要がある。 本研究では設計時に生じる問題点を挙げ、それらを解決するアルゴリズムを 考える。

テーマ	「CSPによるネット割り当てアルゴリズムに関する研究」
内容	近年、FPGA上に回路を実現し、高速に論理検証をおこなう論理エミュレータが 利用されるようになってきている。FPGA間の接続にはクロスバが用いられるが、 接続要求(ネット)をどのクロスバを用いて実現するかを決定する必要がある。 これがネット割り当て問題である。この問題はネットが接続するFPGAの数が 3以上であるときNP完全問題であるため、これを実用的な時間で解くための heuristicなアルゴリズムが幾つか提案されている。ネット割り当て問題を 制約充足問題(Constraint satisfactionProblem,CSP)ととらえ、この観点から heuristicなアルゴリズムについて考察し、性能の改善を試みている。

テーマ	「遺伝的アルゴリズムを用いたネット割り当て問題に関する研究」
内容	CPU等を設計するに当たって、設計した回路が期待通りの動作をしているか どうかを確かめる、論理検証という過程は必要不可欠な過程です。この 論理検証の手法の1つとして論理エミュレータを用いる方法があります。 この論理エミュレータを用いる際に、FPGA(Field programmable gate array)を、 ネットと呼ばれる接続要求に従って、クロスバーを用いて接続しなければ なりません。この際、どのネットをどのクロスバーに割り当てるか考えなければ なりません。これがネット割り当て問題です。このネット割り当て問題を 遺伝的アルゴリズムという手法を用いて解く方法について研究しています。

平田研 研究紹介 Home Pageへ
平田研 Home Pageへ