de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Fast Concurrent Access to Parallel Disks

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44368

Egner,  Sebastian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-33AF-3
Zusammenfassung
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}.