I/O prefetching for recursive data structures.
Published: 2004
Language: eng
Number of pages: 100
Description: Out-of-core applications that manipulate data too large to fit entirely in memory, tend to waste a large percentage of their execution times waiting for disk requests to complete. We can hide disk latency from these applications by taking advantage of under-utilized I/O resources to perform prefetching. However, while I/O prefetching has proven to be quite successful in array-based numeric codes; its applicability in pointer-based codes has not been explored.In this thesis, we explore the potential of applying the concepts of cache prefetching for pointer-based applications to prefetch items from the disk to memory. We also propose a new data structure for prefetching the elements of linked lists that can effectively reduce the run-time at the expense of some extra space when there are frequent updates to the list. Experimental results demonstrate that our technique is able to outperform previous techniques when there are significant changes to the list.
Notes: Adviser:  Angela Demke Brown.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 43-03, page: 0874.

MICR copy on microfiche (2 microfiches).