English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Fast Concurrent Access to Parallel Disks

Sanders, P., Egner, S., & Korst, J. (2000). Fast Concurrent Access to Parallel Disks. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00) (pp. 849-858). New York, USA: ACM Press.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33AF-3 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33B0-E
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sanders, Peter1, Author           
Egner, Sebastian1, Author           
Korst, Jan, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: High performance applications involving large data sets require the efficient and flexible use of multiple disks. In an external memory machine with $D$ parallel, independent disks, only one block can be accessed on each disk in one I/O step. This restriction leads to a load balancing problem that is perhaps the main inhibitor for adapting single-disk external memory algorithms to multiple disks. This paper shows that this problem can be solved efficiently using a combination of randomized placement, redundancy and an optimal scheduling algorithm. A buffer of $\Ohh{D}$ blocks suffices to support efficient writing of arbitrary blocks if blocks are distributed uniformly at random to the disks (e.g., by hashing). If two randomly allocated copies of each block exist, $N$ arbitrary blocks can be read within $\ceil{N/D}+1$ I/O steps with high probability. In addition, the redundancy can be reduced from $2$ to $1+1/r$ for any integer $r$. %Using appropriate codes even multiple disk %failures can be tolerated with low redundancy. These results can be used to emulate the simple and powerful ``single-disk multi-head'' model of external computing \cite{AggVit88} on the physically more realistic independent disk model \cite{VitShr94} with small constant overhead. This is faster than a lower bound for deterministic emulation \cite{Arm96}.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM Press
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518110
Other: Local-ID: C1256428004B93B8-F6D0E56540A5201BC12569DD006CA6DB-SanEgnKor2000
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: San Francisco, USA
Start-/End Date: 2000

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 849 - 858 Identifier: ISBN: 0-89871-453-2