文献

J-GLOBAL ID：201702267370797021   整理番号：17A0414273

通信遅延を考慮した計算タスクオフローディングのための準オンライン・アルゴリズム【Powered by NICT】

Semi-Online Algorithms for Computational Task Offloading with Communication Delay

著者 (2件)： Champati Jaya Prakash (Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON, Canada) ,  Liang Ben (Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON, Canada)
資料名： IEEE Transactions on Parallel and Distributed Systems  (IEEE Transactions on Parallel and Distributed Systems)
巻： 28  号： 4  ページ： 1189-1201  発行年： 2017年 
JST資料番号： T0882A  ISSN： 1045-9219  CODEN： ITDSEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 一つの局所プロセッサ上の計算タスクと通信遅延を持つ1遠隔プロセッサのスケジューリングを検討した。この問題は,クラウドコンピューティングにおける重要な用途がある。タスクを伝送する通信時間はタスクと伝送帯域幅の既知のデータサイズから推論できるが,タスクの処理時間は一般的には知られていない,完了に加工される。未知処理時間を持つ独立なタスクの集合が与えられた時,著者らの目的は,メイクスパンを最小化することである。二つのシナリオの下で問題を研究1)リモートプロセッサに対するタスクの通信時間は遠隔プロセッサ上でのそれらの対応する処理時間よりも小さく,2)リモートプロセッサに対するタスクの通信時間は遠隔プロセッサ上でのそれらの対応する処理時間よりも大きかった。最初のシナリオのために,半オンライン分割と通信(SPaC)アルゴリズムを提案し,第二のシナリオでは,SPaC再開(SPaC R)アルゴリズムを提案した。既知処理時間を持つ,この問題のオフライン版はNP困難であるが,提案した半オンラインアルゴリズムは,意図したシナリオのためのO(1)競合比を達成することを示した。もより一般的な通信時間の両アルゴリズムの競合比を提供した。シミュレーションSPaCとSPaC Rはオンラインリストスケジューリングを凌ぎ,しかも,最も良く知られたオフラインヒューリスティックスを用いた比較的良好に動作することを実証した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： スケジューリング ,  加工時間 ,  *アルゴリズム ,  NP困難 ,  *通信 ,  演算プロセッサ ,  帯域幅
準シソーラス用語： 競合比 ,  オンラインアルゴリズム ,  オフライン ,  メイクスパン ,  通信時間 ,  クラウドコンピューティング ,  *オンライン ,  *通信遅れ , 【Automatic Indexing@JST】

分類 (1件)： ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (6件)： 通信遅延 ,  計算 ,  タスク ,  オフローディング ,  オンライン ,  アルゴリズム