Shift-Limited Sort: Optimizing Sorting Performance on Skyrmion Memory-Based Systems

摘要

Modern nonvolatile memories (NVMs) are widely recognized as energy-efficient replacements of classical memory/storage media, such as SRAM, DRAM, and mechanical hard disk. Among the popular NVMs, the skyrmion racetrack memory (SK-RM) is well known for its high storage density and unique supports of insert/delete operations. However, the existing algorithms designed for classical media might experience serious performance degradation when working on the SK-RM, due to the distinct characteristics of SK-RM. Thus, the existing algorithms should be redesigned to adapt to the brand-new memory model based on the SK-RM, so as to fully reveal the potentials of SK-RM. In particular, many existing algorithms tend to access the in-memory data in a random-hopping fashion, which generates many time-consuming shift operations of SK-RM. It is therefore crucial for the existing algorithms to eliminate unnecessary shift operations of SK-RM to boost the performance of the algorithms. In many modern applications, such as multimedia and data analysis, it is a common operation to process two or more arrays/vectors of data to perform certain computation tasks. In the arrays/vectors, an appropriate data placement strategy is critical for avoiding unnecessary shift operations of SK-RM. The observation thus motivates this work in proposing a recursive back-to-back data placement manner to effectively reduces the shift operations of SK-RM. To demonstrate the back-to-back data placement, we take sorting algorithms as a case study, and propose a novel shift-limited sorting algorithm for SK-RM. Analytical studies show that the shift-limited sort effectively enhances the time complexity of classical merge sort from O(dn lg n) to O(n lg n), where d is the bit distance between adjacent access ports on the nanotracks of the SK-RM. After that, the efficacy of the proposed shift-limited sort is then verified by experimental studies, where the results are encouraging.