負荷分散問題に対するオンライン・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
オンラインに逐次発生するジョブをネットワーク上のどの資源に割り当てると効率良い処理が行えるかを考える負荷分散問題であるオンラインスケジューリング問題について考察する。Aspnesらにより8-competitive ratioをもつオンラインアルゴリズムSLOWFITが提案されている。理論的にはSLOWFITは効率の良い手法であるが、実験的には貪欲法GREEDYが良質な解を得ている。本稿ではSLOWFITに導入されているステージの概念とダブリング・トリックに注目して、新しい2つのオンラインスケジューリングアルゴリズムを提案する。シミュレーション実験により、提案手法の有効性を検証する。
- 社団法人電子情報通信学会の論文
- 2000-03-22
著者
-
大谷 純
富士通ビジネスシステム株式会社
-
吉田 典可
広島市立大学情報科学部情報工学科
-
上土井 陽子
広島市立大学 情報科学部 情報工学科
-
齊藤 忠志
株式会社松下ソフトリサーチ
-
齋藤 忠志
広島市立大学情報科学部
-
大谷 純
広島市立大学情報科学部
-
吉田 典可
広島市立大学情報科学部
-
吉田 典可
広島市立大学大学院 情報科学研究科
-
吉田 典可
広島市立大学大学院情報科学研究科情報工学専攻
関連論文
- マルチレートフィルタと帯域制限補間を用いたウェーブレット変換による楽音モーフィング
- マルチレートフィルタを用いたウェーブレット変換による感性情報処理 : 民族音楽と生理指標解析のための一手法
- 2H-10 データ駆動型ノイマンマシン(DDNM)の構築 : 各プログラムモジュールのクリティカルパスでの処理速度を目指して
- 2H-9 データ駆動型ノイマンマシン(DDNM)におけるスケジューリング : SPECint95ベンチマークテストの試み
- システムのインテリジェント化を支えるディジタル設計教育(新しい知能化へ向けたLSIシステム技術)
- ウェーヴレット変換を用いた心拍データの解析 : 音楽鑑賞によるリラクセーションを求めて
- ノイマン型コンピュータのデータ駆動型マシン技術を用いた高速化 : モジュールフェッチを前提とするループ・アンローリングのハードウエアによる実現
- ウェーヴレット変換のためのスケーラブルなデータ駆動型マシンの一構成法
- 完全なインターロックを行なうパイプラインCISC/RISCの設計教育 : マイクロコンピュータ設計教育環境City-1の2年目
- 完全なインターロックを行なうパイプラインCISC/RISCの設計教育 : マイクロコンピュータ設計教育環境City-1の2年目
- マイクロコンピュータ設計教育環境City-1 : FPGAコンピュータの自由な設計と製作
- マルチプロセッサ用スケジュール支援ハードウェアの提案とシミュレーション評価
- 2000-ARC-139-21 マルチプロセッサ・システムに於けるスケジューリング支援ハードウェアのシミュレーション評価
- 非公開データベース間における機密性の高い情報共有の検討
- コールアドミッションアルゴリズムに適した経路探索法の提案
- A-1-30 コールアドミッションに適した効率的な経路探索法の提案(A-1.回路とシステム,一般講演)
- 分散処理環境でのオンラインルーティング・スケジューリング手法の実験的考察
- 分散処理環境でのオンラインルーティング・スケジューリング手法の実験的考察
- 負荷分散問題に対するオンライン・アルゴリズム
- 分散処理環境での負荷分散問題に対するオンラインスケジューリング手法の実験的考察
- C-6 再構成型アーキテクチャPARSにおけるプログラムのマッピング : 条件判断を伴うプログラムのマッピング(LSI設計,C.アーキテクチャ・ハードウェア)
- PARSアーキテクチャの詳細設計に関する一考察
- PARSプログラミングモデルとPARSアーキテクチャの提案
- 投機的データプリフェッチを行うキャッシュの一考察
- クラスタリング結果の特徴抽出を用いる高次元データの対話的クラスタリング
- FlexDice: 高次元な大規模データセットに対する高速クラスタリング手法
- 最小コストκ分割を全て求めるアルゴリズム
- 多次元データ空間に対する高速クラスタリングと実験的評価
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- A-31 演算の対象となるデータに注目したアルゴリズム実行中の消費電力削減手法(計算モデル,A.アルゴリズム・基礎)
- A-26 データの事前圧縮によるソートアルゴリズムの高速化に関する考察(離散アルゴリズム(3),A.アルゴリズム・基礎)
- M-22 入力系列パターンに着目したコールアドミッションアルゴリズムの実験的性能解析(サービス・資源管理と応用(2),M.ネットワーク・モバイルコンピューティング)
- D-39 不均一サイズセルを用いた階層的クラスタリングの高速化(データマイニング,D.データベース)
- 共有オブジェクト上での競合低減を目的とする非同期分散合意手法の提案
- 6. 地域ネットワークのNPO法人化 : 組織運営の新しい可能性 (地域ネットワークの新しい展開)
- 大規模論理回路分割に関する一手法
- 大規模論理回路分割に関する一手法
- 中国地域における情報通信 : 展望
- コンピュ-タ援用による最適化設計問題の解法
- グラフの最小コストk分割問題に関する一解法
- 共有変数へのアクセス競合の回避を目的とする同時実行可能で拡張可能なハッシュアルゴリズムの改良
- スタンダードセルレイアウト設計における最適ピン割当て
- 匿名データ収集におけるプロトコルからの逸脱防止法の効率化(一般(ストリーム・匿名性・省電力),e-ScienceとData Intensive Science及び一般)
- グラフの最小コスト部分分割について
- 共有情報を用いた同時実行可能なゼロ知識識認証について(セッション1)
- 中国地域における情報通信 : 展望
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- タイミング制約を考慮した並列スタンダードセル配置手法
- 大規模回路の最小コスト分割のための分散遺伝的アルゴリズム
- LSIレイアウト設計における移動可能な端子を考慮したピン割当て手法
- 生態ピラミッドの概念を取り入れた遺伝的アルゴリズムの提案(アルゴリズムと計算量理論)
- 論理回路分割と線形計画法に基づく階層的スタンダードセル配置手法