SDI Seminar

Speaker: Christos Faloutsos

Date: October 9, 1997

Where & When: WeH 8220, Noon

Overlay striping and optimal parallel I/O for modern applications

Abstract Disk array systems are rapidly becoming the secondary-storage media of choice for many emerging applications with large storage and high bandwidth requirements. Striping data across the disks of a disk array introduces significant performance benefits mainly because the effective transfer rate of the secondary storage is increased by a factor equal to the stripe width. However, the choice of the optimal stripe width is an open problem: no general formal analysis has been reported and intuition alone fails to provide good guidelines. As a result one may find occasionally contradictory recommendations in the literature.

With this work we first contribute an analytical calculation of the optimal stripe width. Second, we recognize that the optimal stripe width is sensitive to the multiprogramming level, which is not known a priori and fluctuates with time. Thus, calculations of the optimal stripe width are, by themselves only, of little practical use. For this reason we propose a novel striping technique, called overlay striping, which allows objects to be retrieved using a number of alternative stripe widths. We provide the detailed algorithms for our overlay striping method and we study the associated storage overhead and performance improvements, and we show that we can achieve near optimal performance for very wide ranges of the possible multiprogramming levels, while incurring small storage overheads. At the last part of the talk we also overview related recent work, involving declustering, fractals and data mining.


Biographical note: Christos Faloutsos received the B.Sc. degree in Electrical Engineering (1981) from the National Technical University of Athens, Greece and the M.Sc. and Ph.D. degrees in Computer Science from the University of Toronto, Canada. Since 1985 he has been with the department of Computer Science at University of Maryland, College Park. He is currently visiting Carnegie Mellon University. He has received the Presidential Young Investigator Award by the National Science Foundation (1989), two "best paper" awards (SIGMOD 94, VLDB 97), and three teaching awards. He has published over 70 refereed articles, one monograph, and has filed for three patents. His research interests include physical data base design, searching methods for text, geographic information systems indexing methods for multimedia databases and data mining.