容量を固定した整数ビンパッキング問題のFFD法による解法
スポンサーリンク
概要
- 論文の詳細を見る
LUTをベースとしたFPGAのテクノロジーマッピングに登場する,2段部分論理回路を最小数のLUTに割り当てる問題は,共通信号線を考慮しない場合,整数ビンパッキング問題となる.整数ビンパッキング問題ではビンの容量を固定した場合,全探索アルゴリズムにより多項式時間で最適解が求まることがよく知られているが,実用性に欠ける.本文では,整数ビンパッキング問題の高速近似アルゴリズムであるFFD法が容量を6以下に固定した時に最適解を求めることを示す.また,入力を制限することにより,容量を7および8に固定した時にFFD法が最適解を与えることを示し,容量を8以下に固定した場合に高速に最適解を求める多項式時間アルゴリズムを提案する.
- 一般社団法人情報処理学会の論文
- 1995-07-20
著者
-
梶谷 洋司
東京工業大学工学部電気・電子工学科
-
泉 知論
立命館大学 理工学部電子情報デザイン学科
-
泉 知論
京都大学 大学院 情報学研究科
-
高橋 篤司
東京工業大学大学院理工学研究科集積システム専攻
-
高橋 篤司
東京工業大学
-
梶谷 洋司
東京工業大学 大学院 理工学研究科 集積システム専攻
-
横丸 敏彦
東京工業大学工学部電気・電子工学科
-
泉 知論
東京工業大学工学部電気・電子工学科
関連論文
- 2層BGAパッケージにおける配線混雑度低減のための詳細ビア配置手法(物理設計技術,物理設計及び一般)
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- 高位合成を有効活用するか?活用をあきらめるか?(システム設計及び一般)
- 高位合成を有効活用するか?活用をあきらめるか?(パネル討論,システム設計及び一般)
- Flipにより自己変換するスタイナ木とそのVLSI最適配線への応用(電子システムの設計技術と設計自動化)
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Elip
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 動的再構成可能デバイスの耐故障化に関する検討
- 最近傍ビア配置に基づく2層BGAパッケージ自動配線手法(配置配線,物理設計及び一般)
- プリント基板のための45度線による混雑度緩和を利用した配線手法(信号処理,LSI及び一般)
- 動的再構成可能なシステムのための計算資源割り当てスケジューリング手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 動的再構成可能なシステムのための計算資源割り当てスケジューリング手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 2層BGAパッケージのための詳細ビア配置手法の評価(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- 入力べクトルと回路の内部状態を考慮したピーク電力高速見積もり手法(低電力設計と回路設計技術,システムオンシリコンを支える設計技術)
- PCB配線設計のための一層複線指定長自動配線手法(システム設計と高位・論理設計,物理設計及び一般)
- 最小総変位配置実現問題のための高速位相変更手法(物理設計,物理設計及び一般)
- A-4-27 コンフィギュラブルプロセッサを用いたJPEG2000符号器の設計
- A-4-11 組込み向けJPEG2000適応型レート制御方式
- A-4-39 JPEG2000スケーラブル符方化器の構成法
- VISI回路の階層設計をサポートする階層化BSGフロアプラン
- 確率的探索手法に基づく凸多角形パッキング手法の提案
- 抽象データ構造による高密度3次元パッキング手法
- 複数ネットの非交差配線における探索的最適化手法の提案
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 最小総変位配置実現問題における高速最適化手法(レイアウト,システムオンシリコンを支える設計技術)
- 単層プリント基板配線のための効率的な高混雑度領域特定および45度線による混雑度緩和法(回路最適化技術,システム設計及び一般)
- エラー検出回復方式における加算器の性能評価(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 一般同期方式における消費電力を抑えたクロック木構成のためのクラスタ分割法(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- 1層複線配線問題における幹配線を生成するための壁生成法(物理設計技術,物理設計及び一般)
- A-3-9 障害物を含む1層配線領域のための領域分割によるリバー配線手法(A-3. VLSI設計技術,一般セッション)
- プリント基板のための45度線による混雑度緩和を利用した配線手法(信号処理,LSI及び一般)
- プリント基板のための45度線による混雑度緩和を利用した配線手法(信号処理,LSI及び一般)
- パス長制約付き点集合に対する矩形スタイナー木構成手法(物理設計,システム設計及び一般)
- EDAツールを用いた低コスト一般同期クロックツリー合成手法(レイアウト,システムオンシリコンを支える設計技術)
- 動的再構成可能なシステムのための計算資源割り当てスケジューリング手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 動的再構成可能なシステムのための計算資源割り当てスケジューリング手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- クロック木構成を考慮したクラスタ分割による高速クロックスケジューリング手法
- クロック木構成を考慮したクラスタ分割による高速クロックスケジューリング手法
- クロック木構成を考慮したクラスタ分割による高速クロックスケジューリング手法
- スケジュール可能範囲を考慮したクロック木合成手法
- 遅延変動を考慮したクロック木レイアウトの評価
- 遅延変動を考慮したクロック木レイアウトの評価
- 遅延変動を考慮したクロック木レイアウトの評価
- 最短パス木修正アルゴリズムの設計とその性能評価
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式におけるクロック配線駆動配置
- 準同期式におけるクロック配線駆動配置
- A-3-1 一般同期方式におけるクラスタ分割に基づくクロック木の性能評価(A-3.VLSI設計技術,一般セッション)
- 2層BGAパッケージにおけるメッキ引き出し線配線手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- 2層BGAパッケージにおけるメッキ引き出し線配線手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- ピーク電力削減のためのクロックスケジュール手法
- ピーク電力削減のためのクロックスケジュール手法
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 回路分割のためのビンパッキングアルゴリズムFFDとその拡張
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 容量を固定した整数ビンパッキング問題のFFD法による解法
- Computational Complexity Map of the Set Bin-Packing Problem
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- 二つのグラフの共通木グラフについて(グラフ理論とその応用)
- プラスティックセルアーキテクチャへのアレイ型論理マッピング手法
- 枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- A-3-4 局所方向性を持つFPGAの経由スイッチ数最小化配置アルゴリズム
- BDDサイズに着目したPCA-Chip2のための変数順序決定手法
- フロアプランの部屋間チャネル隣接を表現するHalf-State Sequence(H-Seq)
- A-3-1 近接度に着目した入出力ピン配置アルゴリズム
- COMP2000-17 壁と部屋に関する位相方形分割のReduct-Seqによる数え上げ
- Reduct-Seq表現による高速な一般構造フロアプラニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプランニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプラニング
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- SA-1-4 PCA-Chip2におけるパイプライン通信機構の多チャネル化
- プラスティックセルアーキテクチャへの回路実装密度に関する一考察