Welcome to Hirata Lab's home page。

レイアウト設計

・配置問題(Placement Problem)

テーマ	「ＬＳＩ／プリント基板の設計・部品配置」
内容	LSIやプリント基板において、部品（またはモジュール）の  情報が与えられた時に、適した配置場所を決定するアルゴリズムを  考える。 ここで、与えられる情報とは、主に部品の大きさ、形状、  また、配線情報などであり、適した配置場所とは、配線長及び全体の  面積がなるべく小さくなるようにすることである。

---

・配線問題(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)を、  ネットと呼ばれる接続要求に従って、クロスバーを用いて  接続しなければなりません。この際、どのネットをどのクロスバーに  割り当てるか考えなければなりません。これがネット割り当て  問題です。このネット割り当て問題を遺伝的アルゴリズムという  手法を用いて解く方法について研究しています。

                                                                                                            

近似アルゴリズム

テーマ	「線形計画法を利用した近似アルゴリズム」
内容	MAX-SAT問題に対していろいろなものが提案されている  数種類の近似アルゴリズムを組み合わせて１つの近似  アルゴリズムを作り、そのパフォーマンスを線 形計画法を  利用して解析すること

テーマ	「半定値計画法を用いた MAX CUT 問題の近似解法に関する研究」
内容	計算機科学の分野において，多項式時間で解けないような  ＮＰ困難問題を解く際に，この問題を多項式時間で解ける別の  問題に緩和して近似解を求めるといった方法があります．  これを一般に近似解法といい，それを解く手順を近似アルゴリズム  と呼びます．緩和した別の問題で得られた解と，もとの問題の解を  比較したときに，その誤差が無視できるとみなせるくらい小さなもの  であったとき，もとの問題を解く操作をこの別の解法で代用させても  差し支えないと言えます．こういったＮＰ困難問題の近似解法に  対しての理論的枠組について実際に計算機実験を通して  調査・研究しています．

テーマ	「グラフの最小Ratio-Cutの近似アルゴリズムに関する研究」
内容	Ratio-Cutとは部分グラフの大きさのバランス及びカットする  辺の最小化の両方を考慮に入れたグラフの分割のことである。  グラフのスペクトルを求め、それに基づきグラフの最小Ratio-Cutを  行なう。スペクトルとはラプラシアンという行列の２番目に  小さい固有値 に対応する固有ベクトルから得られる。  Ratio-Cutの下界（lower bound）はラプラシアンの２番目に  小さい固有値で与えられる。

テーマ	「デマンドバス運行管理問題」
内容	デマンドバスとは、ある定められた地域内における  乗降車依頼に対し、車両基地に配備されている小型バスによる  相乗り方式のサービスを行なうシステムをいう。デマンドバス  運行管理問題とは、乗降車依頼に対する車両の割り当てとバスの  巡回経路とを決める問題である。本研究では、離散最適化問題の  一種であるPickup and Delivery 問題や Dial a Ride 問題を  ベースとしてデマンドバス特有の条件を取り入れモデル化、  定式化を行なう。そのモデルのもとで最適な巡回経路  および運行スケジュールを求める手法について考察する。

テーマ	「MAX SAT における近似アルゴリズムの実験的評価」
内容	最大充足化問題（MAX SAT）とは，重み付きの節の集合が  与えられたときに，充足する節の重みの和を最大にする割当を  求める問題です． MAX SAT問題はNP困難であり，  線形時間で解くアルゴリズムは発見されていません．そのため  MAX SAT を解くさまざまな近似アルゴリズムが  提案されています．しかし，これらのアルゴリズムは  これまで実際問題に適用したとき， 実用になるかどうかは  まだ分かっていません．そこで，実際に計算機上で これらの  アルゴリズムを実現し，計算時間や領域計算量などを評価します．

テーマ	「MAXSATの発見的アルゴリズムに関する研究」
内容	MAXSATとは正の重みの付いたクローズの集合を  与えられたときに、充足するクローズの重みの和を最大にする  割り当てを求める問題です。この問題はNP困難であり  多項式時間で解く事が出来ないことがわかっており、  そのためMAXSATを解く様々な近似アルゴリズムが  提案されています。そこでこの研究では発見的アルゴリズムを  用いた解法を計算機上に実現し、それを評価するのが目的です。

                                                                                                            

VLSI

テーマ	「VLSIのバスデータのコーディングによる低消費電力化」
内容	複数の信号源からの信号をそれぞれ複数の宛先にまとめて  伝送するための信号線をバスと言うが、信号線と地面、信号線と  信号線の間はコンデンサのようになっており、信号の遷移によって  電荷の充放電が起こってしまう。これに対し、いくつかの冗長ビットを  設けて変換した信号を用いることにより、信号の遷移を抑え、  消費電力を低減する。

テーマ	「VLSI設計とチップ試作」
内容	考案されたアーキテクチャを検証するため又は、  アルゴリズムエンジンを作成するためにはVLSI設計を行ない、  所望の機能を有するチップを作成する必要がある。  チップ作成までには、ハードウェア記述言語による機能設計、  論理合成によるゲート回路の生成、マスクパターン作成のための  レイアウト設計など多くの設計工程を踏まなければならない。  そこで本研究ではこの一連の流れを確立し、幾つかのCADツールを  用いてVLSIの設計からチップ試作までを行なう。

テーマ	「三角形分割変換アルゴリズムの視覚的表現」
内容	VLSIの設計のなかで、チップ間の配線を行う段階がある。  三角形分割変換アルゴリズムは、この配線をする段階で使われる  アルゴリズムである。この研究では、この三角形分割変換  アルゴリズムをアニメーションなどを使って目に見て  わかりやすい形で表現する。

                                                                                                            

暗号理論

テーマ	「楕円曲線上の公開鍵暗号における計算の効率に関する研究」
内容	公開鍵暗号は、一般的に有限体上の乗法群において  構成されている。これは通常の四則演算を用いているために  便利ではあるが、安全性を確保するために長大な鍵を必要と  していた。1985年にKoblitzとMillerが示した楕円曲線上における  公開鍵暗号は、その後の研究で有限体上の乗法群における  場合の1/4程度の長さの鍵で同等の安全性が確保できる事が  示され、既存の公開鍵暗号方式が楕円曲線上で構成されるように  なった。しかし楕円曲線上においては計算が複雑なために  鍵の長さほど処理時間が高速化できないという問題点があるため、  計算の効率化が求められている。この研究では楕円曲線上での  公開鍵暗号における計算の効率化を目指した研究を行なっている。

                                                                                                            

画像処理アルゴリズム

テーマ	「高速 Morphology 演算アルゴリズム」
内容	画像処理の基本的演算にMorphology演算というものがある。  フィルターを用いて画像の特徴抽出やノイズ除去などの処理を  行なうものであるが、入力画像やフィルターのサイズにその処理速度は  大きく依存する。そこで距離変換を利用した高速演算アルゴリズムを  研究し、さらに画像処理の並列 アルゴリズムへの適用なども  考えています。

                                                                                                            

並列アルゴリズム

テーマ

「画像処理を行う並列アルゴリズムに関する研究」

内容

「画像処理」というと非常に広い範囲になってしまうが、  僕は白黒２値画像を対象としている。距離変換アルゴリズム  （各画素の再近接前景画素までの距離を求める）を中心に  現在は考えているが、それに類するような画像情報を扱う  アルゴリズムについて、効率の良い並列化について研究する。  並列モデルにはＰＲＡＭモデルを代表として、多くの種類があるが、  そのなかのどのモデルを扱うというようには、まだ限定していない。  単純に距離といっても、実は多くの距離関数が存在する。  一般に２点間の距離と言った場合にはユークリッド距離を表すが、  他にも、縦に何マス、横に何マスという数えかたをするCityblock  距離や、斜め移動を含んで、何回の移動で到達できるかという  Chessboard距離などもある。 並列アルゴリズムとは、通常の  逐次アルゴリズムに対応するタームで、複数個のプロセッサを  同時に制御して素早く処理を行うことを目的とする。 この時、  各プロセッサ間のネットワーク構造や、メモリ領域の扱いなどに  よって、並列モデルというものが考えられてくる。  ＰＲＡＭモデルとは、複数のプロセッサが共通大域メモリを  扱うモデルで、並列アルゴリズムのモデルとしては、最も一般的で  ある。ＰＲＡＭモデルは、メモリの同一番地への同時読み込みや  同時書き込みを許すかどうかで、さらに細かく分類される。  通常、逐次アルゴリズムの評価はその実行時間によってなされる。  それに対して、並列アルゴリズムの場合は、実行時間と  プロセッサ数の２つによって評価される。実行時間×プロセッサ数が  逐次アルゴリズムの最適実行時間に等しければ、  その並列アルゴリズムは仕事量最適だと言われる。

                                                                                                            

グラフアルゴリズム

テーマ	「最短経路アルゴリズムに関する研究」
内容	グラフ理論における古典的問題である最短経路問題について、  効率のよいアル ゴリズムを求めて研究しております。

テーマ	「ハイパーグラフの頂点被覆の近似解法」
内容	ハイパーグラフの頂点被覆を求める問題はNP困難のため、  直接求めることは難しい。そのため近似解を求め、  最適解との近似比について考える。

テーマ	「ペトリネット発火系列問題に関する研究」
内容	ペトリネット発火系列問題は一般的にはNP困難であるが、  きわめて簡単な問題に関しては多項式時間で解ける問題もある。  この問題について研究する。

                                                                                                            

組合せ最適化問題

テーマ	「Dial-a-Rideシステムにおける経路探索とスケジューリングに関する研究」
内容	Dial-a-Rideシステムとは、利用者の乗降要求に応じて  走行ルートや運行スケジュールを柔軟に変更出来る乗合バスに  よる乗客輸送システムである。本研究では、実際のシステムに  適用するための高速かつ柔軟な経路探索とスケジューリングの  手法を提案することを目的としている。

テーマ	「チャネル割り当て問題について」
内容	移動体通信において、各基地局には複数のチャネルが  割り当てられる。その有効な割り当てを求める問題を、  チャネル割り当て問題という。 本研究では、この問題を  近似的解法や発見的手法によって求める方法を提案し、  比較、検討を行なう。

                                                                                                            

量子計算

テーマ	「量子計算のシミュレート」
内容	現在、既存の計算機とは全く違う理論で動作する  量子計算機が話題になっている。本研究では、量子計算機の  ためのアルゴリズムを既存の計算機上でシミュレートし、  その動作の検証を行なう。