|COP5641 Ryan & Jin.tgz||19-Jun-2006 17:01||529K|
Linux Kernel & Device Driver Programming
Cache Optimization for Adaptive Network Memory Engine
COP5641 - 1
Ryan Woodrum & Jin Qian
l Design a cache management policy for anemone pseudo block device
l Improve cache hit rate ( currently hit rate is up to 5% )
We discussed with Dr. Kartik after class about background of anemone project and possibilities to improve the cache management policy.
We had a further discussion about details on how to improve the cache performance. Base on our discussion, we proposed two policies.
1. Logically separate cache into a smaller write buffer and a read cache. Sizes of them are configurable so that we can evaluate for optimum division.
2. Replace the current LRU cache replacement policy using LRW-ended read cache replacement policy which we thought more suitable for network swapped storage.
In addition to above two base improvements, we planed to address the following issue if time allows.
1. Solve page aging problem caused by our new cache replacement policy
2. Dynamically adjust write buffer/read cache size based on workload
3. Combine write buffer/read cache into a unified cache
We planed to start reading code and to mark places we should modify as well as places we should write from scratch.
After some efforts reading anemone code and kernel swap daemon code, we both have questions and new ideas about our project.
On today¡¯s meeting, we begin to finalize design and make programming decisions. We decide to replace current LRU policy to MRW policy and we intend to use workqueue for scheduling network requests from write buffer transfer and for read cache prefetch because we think we need to use sleep for network transfer in these two situations.
We decide to create a circular buffer for write and a cache for read. Particularly, we discussed the implementation of write buffer. There are two ways, array and link list. Considering the memory fragmentation problem caused by frequently allocating/de-allocating pages and the complexity of pointers, we prefer using array to store pages for write. Although this will incur some copy operations from write buffer to read cache, copies will not be frequent because they happen only on initial cache population based on our cache management policy. Another benefit of using circular buffer is locking between reader and writer as show in scullpipe assignment.
Another issue is cache interface. In current implementation, ¡°cache¡± code actually behaves like a page swap manager, which first checks LRU cache. If cache hits, it returns page to upper level, else it issues a network request to fetch page from remote server and send it to upper level. Ideally, cache itself should not care about the network transfer. It just return page if there is one or return null if not so. We are planning to change cache_add and cache_retrieve function into page_put and page_get, inside which they look up cache first and then network and then local disk. And we can focus on cache part and another team (Jian & Kyle) can focus on network and local disk. This requires coordination with them so we may talk with them tomorrow.
We also talk a bit about using time ticking and not swapping cached page to remote server to avoid cache aging problem. We also think about the way to disable swap daemon read ahead (meaning less for anemone because anemone is conceptually a random device so sequential read/write can not gain any benefit).
June 9,2006 -
June 15, 2006
We run the first version with delayed
write which schedule a write requests as soon as page write to buffer. After
trials and errors, we finally build a stable version but the result is
Huge amount of write data occupied the
cache most of time so read hit rate suffers. We changed our algorithm to add
prefetch when swapper requests to read some page in. In addition, we limit
the cache space size used as write buffer.