著者

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

出版者

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

雑誌

情報処理学会研究報告システム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.

著者

梶谷 洋司

出版者

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

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)

巻号頁・発行日

vol.106, no.548, pp.61-66, 2007-03-01

被引用文献数

8

---

平面配線領域を信号ピンを点とするグラフでシミュレートし、点に仮想ポテンシャルを与えて電界を生成し、付随する等ポテンシャル線をポテンシャル勾配を表す枝で制御して配線経路として使う新しい配線パラダイムを提供する。本文の前半では、このモデルをグラフ理論的に解明する。後半ではこのグラフが配線を一意に決める枠組みを提案する。等ポテンシャル線は「存在する、切れない、交わらない」ので配線は等ポテンシャル線の選択作業である。また配線の切断や制限が考察の対象である奇体な配線アルゴリズムである。無限の配線多様性を備えたField-Unprogrammable-Pin-Array(FUPA)と呼べるアーキテクチャーである。また配線の本質的困難と考えられている配線順序依存性から脱却している。

著者

久保 ゆき子 高島 康裕 中武 繁寿 梶谷 洋司

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.4, pp.881-888, 2000-04-15

参考文献数

10

被引用文献数

8

---

平面配線領域上に指定された複数の点を相互に結ぶスタイナ木を別のスタイナ木へ変換するアルゴリズムFlipを提案する.これは,現スタイナ木の1枝をそれを含む面上のパスで迂回させる操作である.Flipは高速で働き,また任意のスタイナ木から任意のスタイナ木へ多項式回の適用で到達できることが証明できるので,VLSI配線における複雑な評価に対する有効なアルゴリズムになる.Flipは,2層HV配線領域のスタイナ木にも適用できるよう拡張される.例として採用した総配線長,クロストーク,スキュー,VIA数などの複合評価関数に対応する実験では,従来の構成的手法では達成できない特徴を有する結果を得ることができた.また,類似の手法であるrip-up and reroute手法との差異を付録で論ずる.Given a Steiner tree thatconnects designated terminals on a plane routing area, the Flip isdefind as a procedure that makes a current Steiner tree change itsconfiguration.It is to replace one of the edges of the Steiner treewith a detour on an adjacent face.Since the procedure runs quickly, and the reachability is proved, theidea can be a useful routing algorithm if it is implemeted bysimulated annealng.The idea is enhanced to the 2-layer HV routing.The performance of the algorithm was experimented for multipleobjectives.Some unique and satisfiable results were observed.The difference from the rip-up and reroute strategy is discussed in Appendix.

著者

村田 洋 梶谷 洋司

出版者

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

雑誌

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

巻号頁・発行日

vol.1993, no.55, pp.85-92, 1993-06-25

被引用文献数

1

---

単層アナログレイアウトの設計ツールとして,設計者が指定するひとつの部品の連続移動に対応して周囲の配線を連続移動させるレイアウト連続移動エディタが求められているが,その有効性は処理の早さにかかっている.筆者らは,連続移動を位相的に処理する段階(位相配線処理)とそれに続く配線の物理的実現の段階(物理配線処理)とに分けることで高速化をはかるエディタを開発中である.本稿では,全体の概要と位相配線処理部分について記述する.部品の配置に応じて領域を三角形分割し,位相配線はそれが通過する三角形の系列で表現する,というデータ構造において部品の連続移動を多角形の変形の連続で捉え,それぞれはデータ構造の部分変更で対応するワームクリープ法を提案する.実験のために仮の物理配線処理を組み込んでエディタを試作したところ,実時間エディタとして設計者が満足できる早さで動作させることができた.As an interactive design tool for analog circuit layout, a layout editor is useful if wires are transformed continuously with a continuous move of a module which is instructed by a designer. To realize this function with a quick response time, the editor we are developing divides the continuous move into topological move phase (topological wiring process) and physical realization phase (physical wiring process). In this paper, after the overview of the whole system, topological phase is studied. Using the triangulation data structure of the wiring space, topological wires are expressed as a sequence of passing triangles. The proposed algorithm named Worm Creep Method moves one polygonal object by a sequence of local data modifications which is a polygon deformation with surrounding space. With a test version of physical phase algorithm, a prototype editor is developed and demonstrated to response quick enough for interactive use.

著者

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

出版者

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

雑誌

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

巻号頁・発行日

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

被引用文献数

8

---

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

著者

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

出版者

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

雑誌

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

巻号頁・発行日

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

---

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