Physically Addressed Queueing (PAQ): Improving Parallelism

NAND flash storage has proven to be a competitive alter-native to traditional disk for its properties of high random-access speeds, low-power and its presumed efficacy for random-reads. Ironically, we demonstrate that when pack-aged in SSD format, there arise many barriers to reaching full parallelism in reads, resulting in random writes out-performing them. Motivated by this, we propose Physically Addressed Queuing (PAQ), a request scheduler that avoids resource contention resultant from shared SSD resources. PAQ makes the following major contributions: First, it ex-poses the physical addresses of requests to the scheduler. Second, I/O clumping is utilized to select groups of op-erations that can be simultaneously executed without ma-jor resource conflict. Third, inter-request NAND transac-tion packing empowers multi-plane-mode operations. We implement PAQ in a cycle-accurate simulator and demon-strate bandwidth and IOPS improvements greater than 62% and latency decreases as much as 41.6 % for random reads, without degrading performance of other access types. 1