分散共有メモリに対するオンラインアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1993-05-28
• タイトル: 分散共有メモリに対するオンラインアルゴリズム
• タイトル / 言語: en
• タイトル: On - line Algorithms for Distributed Shared Memory
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学理学部情報科学科今井研究室
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, University of Tokyo
• 著者名: 古賀, 久志
• 著者名(英): Hisashi, Koga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ローカルメモリを持った複数のプロセッサーからなる分散共有メモリシステムにおいては、各ページはメモリアクセス要求列に対してコストが低くなるように、適宜移動または複写されて適当なプロセッサーに配置される必要がある。本研究では、こうした低いコストのページ配置を実現するオンラインアルゴリズムをコンペティティブ比（最適オフラインアルゴリズムとのコスト比）の面から考える。特に本研究では、ページ移動問題に対しての確率的アルゴリズムをページ複写問題用に改良して木やリングのネットワークに対して既存の決定的アルゴリズムよりコンペティティブ比の面で強い結果が得た。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In distributed shared memory system consisting of multiple processor s, each of which has its own local memory, each page needs to be located at a proper processor by migration or replication so at to make the total cost for memory-access lower. In this paper, on-line algorithms attempting to implement this low-cost locating are considered in terms of competitiveness, the ratio of the cost of the on-line algorithms to that of the off-line optimal algorithm. Especially in this paper, we show that the application of algorithms base on randomized algorithms for page migration problem to page replication problem can acquire more powerful result than existing deterministic algorithms about competitive ratio.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 48(1993-AL-033), p. 49-55, 発行日 1993-05-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会