Categories
近年の微細加工技術の進歩により、数千万トランジスタを1チップに集積したLSIが一般的に使われるようになって来ました。これに伴い、このような大規模なLSIを如何にして短い期間内に設計するかという問題は、いよいよ深刻さを増しています。
LSIの設計はその複雑さゆえに数段階に分けて扱われており、その最終段階が「レイアウト問題」と呼ばれ、これは簡単に言えば、「できるだけ小さい長方形領域の中に指定された様々な大きさの長方形を配置し、その間を指定された通りに配線せよ」という問題であり、非常に難しいパズル問題と考えることができます。
当研究室では、レイアウト問題を「自分で解く」のではなく、この問題を「計算機に解かせる」ためのアルゴリズムに関する研究をやっています。具体的には、レイアウト問題に応用するための「組合せアルゴリズム理論」に関する研究と、理論やアイデアを計算機上にプログラムして実験することによりその実用性を検証するという研究を行ってます。
立体パッキング
多角形パッキング
SADP配線
配置配線パズル