File assignment in parallel I/O systems with minimal variance of service time

Lin Wen Lee, Peter Scheuermann, Radek Vingralek

Research output: Contribution to journalArticlepeer-review

92 Scopus citations

Abstract

We address the problem of assigning nonpartitioned files in a parallel I/O system where the file accesses exhibit Poisson arrival rates and fixed service times. We present two new file assignment algorithms based on open queuing networks which aim at minimizing simultaneously the load balance across all disks, as well as the variance of the service time at each disk. We first present an off-line algorithm, Sort Partition, which assigns to each disk files with similar access time. Next, we show that, assuming that a perfectly balanced file assignment can be found for a given set of files, Sort Partition will find the one with minimal mean response time. We then present an on-line algorithm, Hybrid Partition, that assigns groups of files with similar service times in successive intervals while guaranteeing that the load imbalance at any point does not exceed a certain threshold. We report on synthetic experiments which exhibit skew in file accesses and sizes and we compare the performance of our new algorithms with the vanilla greedy file allocation algorithm.

Original languageEnglish (US)
Pages (from-to)127-140
Number of pages14
JournalIEEE Transactions on Computers
Volume49
Issue number2
DOIs
StatePublished - 2000

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'File assignment in parallel I/O systems with minimal variance of service time'. Together they form a unique fingerprint.

Cite this