Cache-oblivious algorithms are well understood when the cache size remains constant. Recently variable cache sizes have been considered. We are motivated by programs running in pseudo-parallel and competing for a single cache. This thesis studies the underlying cache model and gives a generalization of two models considered in the literature. We give a new cache model called the "depth model" where pages are accessed by page depths in an LRU cache instead of their ad- dresses. This model allows us to construct cache-oblivious algorithms that cause a certain number of cache misses prescribed by an arbitrary function computable without causing a cache miss. Finally we prove that two algorithms satisfying the regularity property running in pseudo-parallel cause asymptotically the same number of cache misses as their serial computations provided that the cache is satisfying the tall-cache assumption.

Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our technique's performance, we also examine its practical performance on the problem of matrix transposition.

In Utah all water, both on or below the ground surface, is considered public property. The right to use water is obtained by fellowing certain subsiding procedures of appropriation through the office of the State Engineer. Any right to the use of water may be changed to some other beneficial use with the approval of the State Engineer; however, there must be no interference with other rights, unless proper compensation has been made. Agriculture still uses most of the available water in Utah; However, farmers' needs for water are not exactly the same. When allocation per acre is the same among farmers, water soon comes to have different values. Unless some mechanism arises to permit transfer of water, misallocation results. the Cache Valley area was chosen to illustrate the Misallocation problem. Input-output data which the Bureau of Reclamation used in their feasibility report on the Cache County area of the Oneida project were analyzed to determine the value of residual water. All factors of production except water, such as land, capital, seed, fertilizer, fuel, labor, and repairs were calculated at their market prices. These were subtracted form the value of a unit of product and the residual value was then imputed to water as one estimate of its value. Varying farm sizes and different cropping practices were studied to show the effect these variables had on water values. Agricultural water users on the Logan River distribution system were interviewed to find the value of water rentals and water-right sales. The water-right prices quoted by farmers and irrigation company officials were stated in terms of dollars per share. Since a share delivers varying quantities of water along the complete river system the "right" values were converted to vale per acre-foot. local customs, existing water laws and past court decisions were examined to ascertain their role in water transfer. The principle of equal marginal value was applied to Logan River water supplies. Marginal value in use reflects the amount in dollars which consumers would be willing to pay for the last unit of water consumed. In a perfectly competitive rental market the price of water reflects the value of the marginal product. A brief historical sketch of the Bear Lake system and the irrigation companies making up the Logan River distribution system is given. The water rights of the individual companies are listed and a brief resumé of water-right laws and administration is supplied. legal decrees and litigations relative to irrigation supplies, power requirements and urban use, vis. The Call and Kimball and Logan City vs Water Users (1963) decrees are discussed. The effect these decisions have on water use in Cache Valley is noted.

No description available.

by Vincent, Kwan Chi Wai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 123-127). / Abstract --- p.i / Acknowledgement --- p.ii / List of Tables --- p.vii / List of Figures --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- I/O System --- p.2 / Chapter 1.2 --- Disk Cache --- p.4 / Chapter 1.3 --- Dissertation Outline --- p.5 / Chapter 2 --- Related Work --- p.7 / Chapter 2.1 --- Prefetching --- p.7 / Chapter 2.2 --- Cache Partitioning --- p.9 / Chapter 2.2.1 --- Hardware Assisted Mechanism --- p.9 / Chapter 2.2.2 --- Software Assisted Mechanism --- p.10 / Chapter 2.3 --- Replacement Policy --- p.12 / Chapter 2.4 --- Caching Write Operation --- p.13 / Chapter 2.5 --- Others --- p.14 / Chapter 2.6 --- Summary --- p.15 / Chapter 3 --- Methodology and Models --- p.17 / Chapter 3.1 --- Performance Measurement --- p.17 / Chapter 3.1.1 --- Partial Hit --- p.17 / Chapter 3.1.2 --- Time Model --- p.17 / Chapter 3.2 --- Terminology --- p.19 / Chapter 3.2.1 --- Transfer Block --- p.19 / Chapter 3.2.2 --- Multiple-sector Request --- p.19 / Chapter 3.2.3 --- "Dynamic Block, Heading Sectors and Content Sectors" --- p.20 / Chapter 3.2.4 --- Heading Reuse and Non-heading Reuse --- p.22 / Chapter 3.3 --- New Models --- p.23 / Chapter 3.3.1 --- Unified Cache with Always Prefetch --- p.24 / Chapter 3.3.2 --- Partitioned Cache: Branch Target Cache and Prefetch Buffer --- p.25 / Chapter 3.3.3 --- BTC + PB with Alternative Storing Sector Technique --- p.29 / Chapter 3.3.4 --- BTC + PB with ASST Applying to Dynamic Block --- p.34 / Chapter 3.3.5 --- BTC + PB with Storing Enough Head Technique --- p.35 / Chapter 3.4 --- Impact of Block Size --- p.38 / Chapter 4 --- Trace Driven Simulation --- p.41 / Chapter 4.1 --- Simulation Environment --- p.41 / Chapter 4.2 --- Two Kinds Of Disk --- p.43 / Chapter 4.3 --- Control Models --- p.43 / Chapter 4.3.1 --- Model 1: No Cache --- p.43 / Chapter 4.3.2 --- Model 2: Unified Cache without Prefetch --- p.44 / Chapter 4.3.3 --- Model 3: Unified Cache with Prefetch on Miss --- p.44 / Chapter 4.4 --- Two Comparison Standards --- p.45 / Chapter 4.5 --- Trace Properties --- p.46 / Chapter 5 --- Performance Evaluation of Common Disk --- p.54 / Chapter 5.1 --- The Effect Of Cache Size --- p.54 / Chapter 5.1.1 --- Trends of Absolute Reduction in Time --- p.55 / Chapter 5.1.2 --- Trends of Relative Reduction in Time --- p.55 / Chapter 5.2 --- The Effect Of Block Size --- p.68 / Chapter 5.2.1 --- Trends of Absolute Reduction in Time --- p.68 / Chapter 5.2.2 --- Trends of Relative Reduction in Time --- p.73 / Chapter 5.3 --- The Effect Of Set Associativity --- p.77 / Chapter 5.3.1 --- Trends of Absolute Reduction in Time --- p.77 / Chapter 5.4 --- The Effect Of Start-up Time C1 --- p.79 / Chapter 5.4.1 --- Trends of Absolute Reduction in Time --- p.80 / Chapter 5.4.2 --- Trends of Relative Reduction in Time --- p.80 / Chapter 5.5 --- The Effect Of Transfer Time C2 --- p.83 / Chapter 5.5.1 --- Trends of Absolute Reduction in Time --- p.83 / Chapter 5.5.2 --- Trends of Relative Reduction in Time --- p.83 / Chapter 5.5.3 --- Impact of C2=0.5 on Cache Size --- p.86 / Chapter 5.5.4 --- Impact of C2=0.5 on Block Size --- p.87 / Chapter 5.6 --- The Effect Of Prefetch Buffer Size --- p.90 / Chapter 5.7 --- Others --- p.93 / Chapter 5.7.1 --- In The Case of Very Small Cache with Large Block Size --- p.93 / Chapter 5.7.2 --- Comparing Performance of Model 6 and Model 7 --- p.94 / Chapter 5.8 --- Conclusion --- p.95 / Chapter 5.8.1 --- The Number of Actual Sectors Transferred between Disk and Cache . --- p.95 / Chapter 5.8.2 --- The Efficiency of Our Models on Common Disk --- p.96 / Chapter 6 --- Performance Evaluation of High Performance Disk --- p.98 / Chapter 6.1 --- Difference Between Common Disk And High Performance Disk --- p.98 / Chapter 6.2 --- The Effect Of Cache Size --- p.99 / Chapter 6.2.1 --- Trends of Absolute Reduction in Time --- p.99 / Chapter 6.2.2 --- Trends of Relative Reduction in Time --- p.99 / Chapter 6.3 --- The Effect Of Block Size --- p.103 / Chapter 6.3.1 --- Trends of Absolute Reduction in Time --- p.105 / Chapter 6.3.2 --- Trends of Relative Reduction in Time --- p.105 / Chapter 6.4 --- The Effect Of Start-up Time C1 --- p.110 / Chapter 6.4.1 --- Trends of Relative Reduction in Time --- p.110 / Chapter 6.5 --- The Effect Of Transfer Time C2 --- p.110 / Chapter 6.5.1 --- Trends of Relative Reduction in Time --- p.112 / Chapter 6.5.2 --- Impact of C2=0.5 on Cache Size --- p.112 / Chapter 6.5.3 --- Impact of C2=0.5 on Block Size --- p.116 / Chapter 6.6 --- Conclusion --- p.117 / Chapter 7 --- Conclusions and Future Work --- p.119 / Chapter 7.1 --- Conclusions --- p.119 / Chapter 7.2 --- Future Work --- p.122 / Bibliography --- p.123

No description available.

The methods of improving the cache performance are multiform and advanced of nowadays. We are concerned about the cache and TLB utility. To reduce the context switch cost on system, we utilize an address-space switching hardware of ARMS3C2410 processor to realize the fast address switching mechanism. The Fast Context Switch can help to improve cache and TLB utility and performance. Fast Context Switch is a method that can help to improve the cache performance. The key feature of Fast Context Switch is without any cache and TLB flush on process context switching. To implement Fast Context Switch, we address the different processes to different address space by process ID. When context switch occurs, we can just change the working space without the cache and TLB flush. This thesis emphasizes on the performance measure for improvement on the cache and TLB. We use a high dependable microkernel architecture for message passing between processes, this microkernel called MinixARM. Rely on the microkernel, we can more easily understand and analyze the system performance and additional cost of the cache scheme. We provide more complete performance tests by benchmarks, fast context switch can increase the system performance about 65% at most.

Thesis (Ph. D.)--College of Computing, Georgia Institute of Technology, 2004. Directed by Ken MacKenzie. / Vita. Includes bibliographical references (leaves 135-146).

Not available / text

We consider cache replacement algorithms at a shared cache in a multicore system which receives an arbitrary interleaving of requests from processes that have full knowledge about their individual request sequences. We establish tight bounds on the competitive ratio of deterministic and randomized cache replacement strategies when processes share memory blocks. Our main result for this case is a deterministic algorithm called GLOBAL-MAXIMA which is optimum up to a constant factor when processes share memory blocks. Our framework is a generalization of the application controlled caching framework in which processes access disjoint sets of memory blocks. We also present a deterministic algorithm called RR-PROC-MARK which exactly matches the lower bound on the competitive ratio of deterministic cache replacement algorithms when processes access disjoint sets of memory blocks. We extend our results to multiple levels of caches and prove that an exclusive cache is better than both inclusive and non-inclusive caches; this validates the experimental findings in the literature. Our results could be applied to shared caches in multicore systems in which processes work together on multithreaded computations like Gaussian elimination paradigm, fast Fourier transform, matrix multiplication, etc. In these computations, processes have full knowledge about their individual request sequences and can share memory blocks. / text