Digital Library[ Search Result ]
Beyond Traditional Search: SIMD-Optimized Correction for Learned Index
Yeojin Oh, Nakyeong Kim, Jongmoo Choi, Seehwan Yoo
http://doi.org/10.5626/JOK.2025.52.5.363
To address the limitations of traditional indexing techniques, this study examines the search performance of machine learning-based Learned Indexes, focusing on the read-only RMI and the modifiable ALEX We propose a SIMD-based optimization technique to minimize the overhead incurred during the correction phase, which accounts for over 80% of the total search time. Learned Indexes operate in two phases: prediction and correction. In our experiments with RMI, we found that when the error range is large, the SIMD Branchless Binary Search capable of quickly narrowing down the search range outperforms other methods. In contrast. when the error range is small, the model prediction-based SIMD Linear Search demonstrates superior performance. For ALEX, which maintains a relatively constant error range, the straightforward SIMD Linear Search proved to be the most efficient compared to more complex search techniques. These results underscore the importance of choosing the right search algorithm based on the dataset’s error range, index size, and density to achieve optimal performance.
Overcoming a Zone Reclaiming Overhead with Partial-Zone Reclaiming
Inho Song, Wonjin Lee, Jaedong Lee, Seehwan Yoo, Jongmoo Choi
http://doi.org/10.5626/JOK.2024.51.2.115
Solid State Drive (SSD) suffers unpredictable IO latency and space amplification due to the traditional block interface. Zoned Namespace, which is a more flash friendly interface, replaced the block interface bringing reliable IO latency and increasing both the capacity and lifespan of SSDs. The benefit of the zone interface is not free. A Zoned Namespace (ZNS) SSD delegates the garbage collection and data placement responsibility to the host, which requires host-level garbage collection called "zone reclaiming". At the same time, ZNS SSD exposes a larger zone to the host to exploit the device parallelism. The increased number of blocks to a zone gives high parallelism; however, the overhead of the zone reclaiming process becomes high with the increased size of the zone. Eventually, the host neither expects predictable latency nor optimal performance due to the background process. This paper tackles the overhead of the zone reclaiming process by introducing "Partial Zone Reclaiming" method. Partial zone reclaiming delays the ongoing reclaiming process and handles the host request that is on the fly. In our experiment, partial zone reclaiming not only improved the host request latency by up to 8% on average, but also reduced zone reclaiming time by up to 41%.
VirtIO-trace: An Unified Tool for Analyzing I/O Characteristics on NVMe SSD in Virtualized Environments
http://doi.org/10.5626/JOK.2018.45.4.332
Virtualization technology plays a significant-role in diverse computing environments such as cloud computing and data center. CPU manufacturers actively provide hardware-based virtualization techniques for virtualization systems. NIC manufacturers also support virtualization techniques to improve network I/O performance. However, there is a significant performance degradation in storage I/O virtualization, and many studies attempted to overcome this problem. Recently, NVMe(Non-Volatile Memory Express) SSDs(Solid State Drives) have become increasingly popular as storage devices for high-performance virtualized I/O systems. However, such fast storage devices cannot improve I/O performance significantly against one’s expectation. To optimize the storage I/O optimization performance, we need an I/O tracking and analysis tool. In this paper, we propose a novel tool that can monitor I/O behaviors on NVMe SSD in virtualized environments. The tool, which we refer to as VirtIO-trace, basically allows to trace I/O requests and their timing information like the existing blktrace. However, it differs from the traditional tools in that it provides NVMe SSD specific information such as queue status and submission/completion statistics, and virtualization specific information such as I/O processing time in VM/host systems. We implemented the tool in the KVM virtualization system. Experimental results show that the tool can collect I/O information in real time, which can be usefully exploited in analyzing I/O characteristics and exploring a new policy for enhancing performance and fairness on management of NVMe SSD in virtualization systems.
Forgetting based File Cache Management Scheme for Non-Volatile Memory
Non-volatile memory (NVM) supports both byte addressability and non-volatility. These characteristics make it feasible for NVM to be employed at any layer of the memory hierarchy such as cache, memory and disk. An interesting characteristic of NVM is that, even though it supports non-volatility, its retention capability is limited. Furthermore NVM has tradeoff between its retention capability and write latency. In this paper, we propose a novel NVM-based file cache management scheme that makes use of the limited retention capability to improve the cache performance. Experimental results with real-workloads show that our scheme can reduce access latency by up to 31% (24.4% average) compared with the conventional LRU based cache management scheme.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr