Software-based Out-of-order Scheduling Technique for High-Performance SSDs

Abstract

We propose an efficient software-based out-of-order scheduling technique for high-performance NAND flash-based SSDs. Unlike an existing hardware-based out-of-order scheduling technique in SSDs (which is implemented in a physical address space), our proposed software-based solution, SOST, can make more efficient out-of-order scheduling decisions, taking advantage of both logical address information and physical address information of multiple I/O requests simultaneously without a significant implementation cost. By exploiting various mapping information and I/O access characteristics available from the flash translation layer (FTL) software, SOST can avoid unnecessary hardware-level operations and manage inter- and intra-queue request rearrangements more efficiently, thus maximizing multichip parallelism of SSDs. Furthermore, SOST can easily support user- or OS-specified I/O request priorities which are important in time-sensitive real-time applications. Experimental results on a prototype SSD show that SOST is effective in improving the overall SSD performance, lowering the average I/O response time by up to 43% over the out-of-order flash controller.