Cache-miss-initiated prefetch in mobile environments

Prefetching has been widely used to improve system performance in mobile environments. Since prefetching consumes system resources, such as bandwidth and power, it is important to consider the system overhead when designing prefetching schemes. In this paper, we propose a cache-miss-initiated prefetch (CMIP) scheme to address this issue. The CMIP scheme relies on two prefetch sets: the always-prefetch set and the miss-prefetch set. The always-prefetch set consists of the data that should always be prefetched if it is possible. The miss-prefetch set consists of the data that are closely related to the cache-missed data item. When a cache miss happens, instead of sending an uplink request to only ask for the cache-missed data item, the client requests several data items, which are within the miss-prefetch set, to reduce future cache misses. Note that the client can ask for more than one data item by an uplink request with very little additional cost. Thus, prefetching several data items in one uplink request can save additional uplink requests. We propose novel algorithms to mine the association rules and use them to construct the prefetch sets. Detailed experiments are used to evaluate the performance of the proposed scheme. Compared to the UIR scheme [G. Cao, A scalable low-latency cache invalidation strategy for mobile environments, IEEE Transactions on Knowledge and Data Engineering 15(5) (2003)] and the UIR scheme without prefetch, our CMIP scheme can greatly improve the system performance in terms of cache hit ratio, reduced uplink requests and additional traffic.