文献

J-GLOBAL ID：201202214197647946   整理番号：12A1518284

重みつきページングに関する主双対ランダマイズドアルゴリズム

A Primal-Dual Randomized Algorithm for Weighted Paging

著者 (3件)： BANSAL Nikhil (Eindhoven Univ. Technol.) ,  BUCHBINDER Niv (Open Univ. Israel) ,  NAOR Joseph (Technion)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 59  号： 4  ページ： 19:1-19:24  発行年： 2012年08月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： キャッシングは計算システムの性能を加速するための効果的技法である。各ページをキャッシュにフェッチするための重み(コスト)が存在する,オンラインページング問題の重みつきバージョンを研究した。オンライン主双対法に基づいて,ランダマイズドO(log k)-競合アルゴリズムを提示した。続けてこれらのアイデアを拡張し,ページが任意の重みとキャッシュサイズを持つ一般的事例に関する,多対数競合アルゴリズムを獲得した。提案解法は2段階方式で,O(log k)-競合分数アルゴリズムを得た後,分数解をキャッシュ状態の確率分布に丸めることによってランダマイズドアルゴリズムを得る。また,計量タスクシステム問題(MTS)に関するオンライン主双対ランダマイズドO(log k)-競合アルゴリズムを提示した。

シソーラス用語： *重みづけ ,  *ページング ,  *計算機アルゴリズム ,  *ランダム処理 ,  オンライン処理 ,  記憶管理 ,  データ読取 ,  双対性 ,  キャッシュメモリ ,  対数
準シソーラス用語： ランダマイズドアルゴリズム ,  キャッシング ,  フェッチ

分類 (2件)： 計算理論  (JB02000A) ,  オペレーティングシステム  (JD03020J)

タイトルに関連する用語 (2件)： ページング ,  ランダマイズドアルゴリズム