著者

横丸 敏彦 泉 知論 高橋 篤司 梶谷 洋司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM)

巻号頁・発行日

vol.1995, no.72, pp.1-8, 1995-07-20

---

LUTをベースとしたFPGAのテクノロジーマッピングに登場する,2段部分論理回路を最小数のLUTに割り当てる問題は,共通信号線を考慮しない場合,整数ビンパッキング問題となる.整数ビンパッキング問題ではビンの容量を固定した場合,全探索アルゴリズムにより多項式時間で最適解が求まることがよく知られているが,実用性に欠ける.本文では,整数ビンパッキング問題の高速近似アルゴリズムであるFFD法が容量を6以下に固定した時に最適解を求めることを示す.また,入力を制限することにより,容量を7および8に固定した時にFFD法が最適解を与えることを示し,容量を8以下に固定した場合に高速に最適解を求める多項式時間アルゴリズムを提案する.In technology mapping of Look Up Table (LUT) based FPGA, the problem of mapping a two-level subcircuit into LUTs is formulated as the Integer Bin Packing Problem without taking account of the advantage of input signals connected to more than one gate. It is known that Integer Bin Packig Problem can be solved in polynomial time by exhaustive search when the size of bins is fixed, however, which is not practical. In this paper, we show that First Fit Decreasing (FFD) which is a fast approximation algorithm solves Integer Bin Packing Problem when the size of bins is fixed to less than or equal to 6. We show that FFD gives optimal solutions for some class of instances when the size of bins is fixed to 7 or 8, and suggest a polynomial time algorithm which solves fast when the size of bins is fixed to less than or equal to 8.

著者

田中 雄一郎 高橋 篤司

雑誌

DAシンポジウム2014論文集

巻号頁・発行日

vol.2014, pp.221-226, 2014-08-21

---

本稿では,平面基板上の集積回路設計における配線問題と親和性の高いペンシルパズルである,ナンバーリンクの特性について考察し,その解法について述べる.ナンバーリンクは,縦横斜めの周囲 8 マスで隣り合う数字を一塊にして島とすることで,空洞内島配線問題として解くことが可能である.外部配線問題において,CHORD-LAST 法は全ネットが配線可能である時,平面性を失わないネットの配線順序を与える.提案アルゴリズムでは,この順序を利用してナンバーリンクの解を生成する.また,対となる数字が共に外側のマスに位置する時,その数字を結ぶ配線で配線領域を分割することが可能であり,他の数字の組は共に片側の領域に位置する.領域の分割を用いた枝刈りを組み合わせることにより,計算量を削減したアルゴリズムを提案する.

著者

本江 俊幸 高橋 篤司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. SLDM, [システムLSI設計技術] (ISSN:09196072)

巻号頁・発行日

vol.2015, no.3, pp.1-6, 2015-05-07

---

次世代リソグラフイ技術の 1 つである側壁プロセスを 2 回用いる SAQP(Self-Aligned Quadruple Patterning) は微細な配線パターンを実現する有望な技術の 1 つであるが,すべての配線パターンを実現できるわけではない.そこで,SAQP で実現可能な配線パターンを生成するために,特殊な 3 色グリッドを用いる配線パターン生成手法が提案されたその生成手法では,配線は SAQP の製造工程に応じて 3 種類に分類される.最終工程に対応する配線は,分岐は許されず,さらに折れ曲がりが禁止されるグリッドが存在する.そのため,最終工程に対応する配線パターンを生成するために,3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる.本稿では,グラフ上に折れ曲がり制約が与えられたとき,一般に,2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す.

著者

井上 一紀 高橋 渡 高橋 篤司 梶谷 洋司

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術

巻号頁・発行日

vol.97, no.577, pp.79-86, 1998-03-06

被引用文献数

8

---

各レジスタのクロック到達時刻を適切に決定することができれば, クロック周期をレジスタ間の最大遅延時間よりも小さくすることが可能である.本稿では, Elmore遅延モデルを用い, 与えられたクロックスケジュールを実現するクロック木配線アルゴリズムを提案する.本手法は, deferred-merge-embedding(DME)法を採用しており, クロック木のトポロジーの生成と, 中間バッファの挿入及びサイジングを同時に行う.本手法により, ランダムに生成されたクロックスケジュールに対しては, ゼロスキュー配線よりもやや大きな配線長で, なだらかに生成されたクロックスケジュールに対しては, ゼロスキュー配線とほぼ同等の配線長でクロック配線を実現できることを実験により示す.

著者

高橋 篤司

出版者

東京工業大学

雑誌

基盤研究(B)

巻号頁・発行日

2009

---

性能とともに信頼性を従来よりも格段に向上させた集積回路を設計,製造するための設計方法論を確立することを目的とし,回路の遅延分布をできる限り精度を保ちつつ,より高速に得るための遅延分布見積もり手法を開発するとともに,遅延エラー検出回復方式に基づき様々な回路の可変レイテンシ化した場合の性能および性能向上率などを評価することで,高性能高信頼性集積回路を効率良く実現するための指針を得た.

著者

佐々木 将央 高橋 篤司 梶谷 洋司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. 設計自動化研究会報告

巻号頁・発行日

vol.97, no.17, pp.89-96, 1997-02-14

---

接続すべき端子集合(ネット)が多数指定されているメッシュで区切られている配線領域モデルにおいて,1ネットずつ順に経路決定していくことに対する弊害に対しては,従来から予測とか引き剥し再配線手法を含めて様々な対策が考案されてきた.本研究では各ネットの密度への影響を予測しながら,ネットの端点を両側から少しずつ伸ばすようにして経路を決定して行くことで,すべてのネットを同時に配線する新しいアルゴリズム『端点成長法』を提案する.また,ランダムに生成した実験データに対し実験を行ない,その有効性を確認した.