Memory allocation for computer systems

29 Aug 2016. NUS mathematicians have formulated an equation for designing efficient memory allocation techniques for computer systems.

Current computer systems require four fundamental resources: computational power, memory space, disk storage and network bandwidth. Hardware is so powerful now that one machine can run hundreds of jobs simultaneously, with each job contained in a virtual machine (VM). The resources are allocated to these VMs in such a way so as to maximise performance and ensure fairness. Prof TAY Yong Chiang and his research assistant Vimalraj VENKATESAN from the Mathematics Department in NUS, in collaboration with Dr WEI Qingsong from the Data Storage Institute, A*Star have found a way to control the memory allocation using a “Cache Miss Equation”.

VMs tend to acquire lots of memory but leave them idle. Such resource wastage can be avoided by having them request memory from a pool called “cleancache”. This pool is used to hold data from disks, in case the VMs need the data again. However, some VMs can make heavy use of the pool, and displace the data kept there for other VMs; when the latter fail to get their data from the pool, there is a cache miss, causing them to re-read their data from the disks, thus suffering a delay. This raises an issue: How should the pooled memory be fairly allocated to the VMs?

The impact of memory allocation on cache misses depends on the interaction between job behaviour and the memory manager. The job may be a web browser, a phone call, a scientific calculation, etc. The memory manager differs for Microsoft’s Windows, Google’s Android and Apple’s iOS. Previous analyses of this interaction relied on unrealistic assumptions. In contrast, the “Cache Miss Equation” adopts a different approach that is based on weak assumptions, and relies on dynamic measurements of the interactions. Experiments have shown that this equation is accurate, and can be used to optimise a fair allocation of memory to VMs.

There is now considerable churn in memory technology, which calls for new memory management techniques. Current web traffic, which is dominated by videos, leads to vast networks of memories for storing such data. These trends suggest new applications for the equation, to design management techniques for new memory devices and memory networks. However, a more exciting application lies in a different direction: each job behaviour is a mix of memory patterns, and each management technique that tries to cater to these patterns must pick a tradeoff. The next step in Prof Tay’s research lies in using the equation as a powerful tool to study this tradeoff in a scientific manner.

Figure shows that the “Cache Miss Equation” can accurately model the probability of a cache miss for different memory allocations.

References

V. Venkatesan, Y.C. Tay and Q. Wei. “Sizing cleancache allocation for virtual machines’ transcendent memory”. IEEE Transactions on Computers 65, 6 (2016), 1949-1963.

V. Venkatesan, Y.C. Tay, Y. Zhang and Q. Wei. “A 3-level cache miss model for a nonvolatile extension to transcendent memory”. Proceedings of IEEE 6th International Conference on Cloud Computing, Technology and Science, Singapore (2014), 218-225.