| 講演抄録／キーワード |
| 講演名 |
2004-12-10 16:00
効率的なRAIDのアクセス順序決定のための完全二部グラフのcluttered orderingの構成法
○足立智子（東邦大） |
| 抄録 |
（和） |
RAIDとは，ディスクの読み込み・書き込みを複数のディスクで並列に行うことにより，処理速度と安全性を高める技術である．プロセッサ速度の進歩によって動画像データや大容量データベース等の大きなファイルを高速に処理することが求められる現在，ネットワーク構築やサーバには欠かせない技術として，重要性を増している．アクセスコストを低減するために，RAIDのinformation diskとcheck diskを完全グラフの辺と頂点に対応させてinformation disk の順序付けを考察するcluttered orderingという概念が，Cohen等(2001)によって導入された．Mueller等(2004)は，二次元のRAIDを完全二部グラフに対応させることで，数理モデル化をおこなった．本稿では，Mueller等の研究をさらに発展させ，効率的なRAIDを構築するために，完全二部グラフのcluttered orderingの構成法について報告する． |
| （英） |
The desire to speed up secondary storage systems has lead to the development of redundant arrays of independent disks (RAID) which incorporate redundancy utilizing erasure codes. To minimize the access cost in RAID, Cohen, Colbourn and Froncek (2001) introduced (d, f)-cluttered orderings of various set system for positive integers d, f. In case of a graph this amounts to an ordering of the edge set such that the number of points contained in any d consecutive edges is bounded by the number f. For the complete graph, Cohen et al. gave some cyclic constructions of cluttered orderings based on wrapped ρ-labellings. Mueller, Adachi and Jimbo (2004) investigated cluttered orderings for the complete bipartite graph. RAID utilizing two-dimensional parity code can be modeled by the complete bipartite graph. Mueller et al. adapted the concept of wrapped Δ-labellings to the bipartite case instead of wrapped ρ-labellings, and gave the explicit construction of several infinite families of wrapped Δ-labellings. Here, we investigate constructions of more generalized infinite families of wrapped Δ-labellings leading to cluttered orderings for the corresponding bipartite graphs. In this paper, we will give constructions of wrapped Δ-labellings for such cases. |
| キーワード |
（和） |
RIAD / Cluttered Ordering / 完全二部グラフ / 数理モデル化 / / / / |
| （英） |
RIAD / Cluttered Ordering / Complete Bipartite Graph / Mathematical Modeling / / / / |
| 文献情報 |
信学技報, vol. 104, no. 501, COMP2004-59, pp. 37-44, 2004年12月. |
| 資料番号 |
COMP2004-59 |
| 発行日 |
2004-12-03 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|