Input/output (I/O) systems are a critical performance limitation for many data-intensive applications (e.g. data mining, satellite data processing). In an attempt to meet the bandwidth requirements of these applications, storage architectures often decluster file data over multiple drives or disk arrays. This added file system complexity makes I/O systems extremely sensitive to I/O access patterns; sequential file access is harder to achieve. In existing systems, the application programmer is forced to either program to the idiosyncrasies of the storage subsystem, or suffer the consequences of poor performance. As systems become more complicated and heterogeneous, with increasing processing power at the storage, understanding system performance is more difficult and this approach fails. My research goal is to develop new I/O interfaces to exploit high bandwidth and increased processing power at the storage layer, coupled with automatic techniques for characterizing performance and adapting to expected workloads.

My Ph. D research, conducted with Daniel Reed at the University of Illinois at Urbana-Champaign, demonstrates that it is possible to automatically recognize and classify certain access patterns from the application-level file access stream. These classifications can be used to select adaptive caching and prefetching algorithms, improving performance by as much as an order of magnitude. This is an important step toward designing higher-level application programming interfaces (APIs) that are easy to use and deliver good performance; the application developer does not need to supply information that can be detected automatically.

I am currently continuing my efforts in automatic access pattern classification, in collaboration with Christos Faloutsos. I/O subsystems in large systems often have collectively more processing power than the processors, presenting an opportunity to give disks the ability self-monitor and tune themselves. Higher-level object interfaces (e.g., as proposed for network-attached storage) that allow applications to access variable length objects as opposed to fixed length blocks give drives control over placement of related file blocks. Thus, one can imagine plugging a smart drive into a Windows NT workstation, or into a large commercial database system with terabytes of storage, and expecting it to characterize the incoming traffic and adapt its data layout, caching, and prefetching strategies accordingly. We are examining linear and fractal characterizations of general I/O workloads at multiple levels of abstraction, based on techniques for data mining. Such characterizations can be used to understand and predict future I/O requirements, and have direct application to performance visualization, capacity planning, and design of more intelligent disk drives.

Unfortunately, certain access pattern information necessary for high performance  cannot be automatically detected, and must be supplied. For example, reordering of requests is a crucial factor in improving I/O performance. Applications that request data in a particular order because the API enforces it (such as UNIX stdio file access) not because the data processing algorithm demands it, limit their I/O parallelism artificially. Many APIs have been proposed to expose I/O parallelism, with different advantages and performance characteristics, including informed prefetching, scatter-gather I/O, collective I/O, and dynamic sets. To exploit the intelligence and performance features that storage systems designers want to add to devices, applications must describe their actual I/O requirements as specifically as possible, letting the system optimize where appropriate.

To explore these interfaces, and their applicability to parallel I/O, I continued my research with Garth Gibson at Carnegie Mellon University. Our immediate focus was collective I/O, an important access pattern for scientific applications, where multiple processors simultaneously access disjoint portions of a parallel file.  Depending on the mappings of file data to drives and processors, throughput can be orders of magnitude poorer than the optimal case. For example, consider a matrix striped in row-major order across several drives that is accessed in column-major by the processors: individual I/Os will be small and noncontiguous. Research in this area has suggested that a specialized collective I/O interface, allowing the file system to reorder the requests within the collective (i.e., to batch them), is crucial for improving performance. In contrast, I proposed and analyzed a general method of optimizing collective access patterns using informed prefetching. I proved that under certain reasonable assumptions, the number of prefetch buffers required at each client to obtain optimal I/O throughput is equal to the number of drives. This method requires no system-level support beyond asynchronous I/O facilities, and can flexibly use additional memory to improve performance (collective I/O implementations cannot).

Although informed prefetching exposes some I/O parallelism, traditional sequential byte stream or record-based interfaces ultimately limit full expression of the inherent parallelism of application I/O requirements. For this reason, I am investigating a new interface for parallel I/O called {\it collective sets}, to support applications that can process disjoint portions of data without regard for order. The ability to reorder these I/O requests is a basic principle behind improving performance. The application programming interface must be able to specify subfiles within a collective set, giving the parallel file system control over request ordering, and allowing the application to implement a distributed task queue scheduling model. At the block I/O level, this application programming interface enables smarter disk scheduling, and I/O performance degrades gracefully in the presence of competing workloads. At the job scheduling level, the work associated with the I/O can be automatically moved to the location of the data, potentially reducing network bandwidth, and transparently adapting to changing storage configurations.