[14 SIMULTECH] Analytical Model of SSD Parallelism

0 Abstract

SSD는 IO 성능을 높이기 위해 channel parallelism, way parallelism, plane pallelism과 같은 여러 IO 병렬 메커니즘을 지원한다. 시뮬레이션을 통해 SSD의 성능을 측정하기 위해서 시뮬레이터는 내부 IO 동작을 모델링하여 SSD의 병렬 IO 작업을 지원해야한다. 이 논문에서는 multiple channel 및 multiple way로 설계된 SSD의 IO 대기 시간을 계산하는 분석 모델을 개발하였다. SSD의 IO 유형을 단일 페이지 읽기/쓰기 작업과 다중 페이지 읽기/쓰기 작업의 두 가지 작업으로 분류하여 IO 대기 시간에 대한 공식을 만들었다. IO 대기 시간 모델을 사용하여 실제 SSD인 Intel X25-M의 IO성능을 3.8% 오차로 계산할 수 있었다.

1 Introduction

SSD와 같은 NAND 플래시 기반 스토리지는 스마트폰, TV, PC 및 서버와 같은 유형의 컴퓨팅 장치에서 주 저장 장치로 쓰인다. SSD는 하드웨어 적으로는 ARM micro-controller와 DRAM이나 SRAM의 메모리, SATA나 PCIe 같은 host interface로 구성되어 있으며, 소프트웨어 적으로는 logical address를 physical address로 변환해주고, cell의 수명을 균등하게 해주고, invalid page를 정리해주는 기능을 하는 FTL(Flash Translation Layer)이 있다. SSD는 고려된 channel의 갯수, way의 갯수, physical page size, address translation algorithm, garbage collection algorithm등 여러 요소 간의 상호 작용을 고려하고 SSD의 workload 특성 혹은 사용 사례 또한 고려하여 설계하는 것이 매우 중요하다. SSD의 동작을 예측하기 위해 여러 접근법을 사용한 연구 결과들이 있어왔다.

- analytical formulation (Desnoyers, 2012),

- trace driven simulation (Agrawal et al., 2008), (Kim et al., 2009), (Cho et al., 2012)

- virtual machine based simulation (Yoo et al., 2013)

- FPGA based prototyping (OpenSSD, 2011), (Lee et al., 2010)

그 중 Analytical formulation (Desnoyers, 2012)은 가장 flexible 하지만 SSD의 성능을 예측하기에는 정확도가 매우 낮았다. FPGA based prototyping (OpenSSD, 2011), (Lee et al., 2010)은 가장 소모되는 비용이 많고 유연하지 못한 접근법이다. 하지만 사용자는 주어진 FTL 알고리즘의 실시간 동작과 성능을 면밀히 조사할 수 있었다.

Virtual machine based simulation (Yoo et al., 2013)은 두 방법의 장점을 모두 제공하였다. channel 이나 way의 갯수 그리고 DRAM의 크기와 같은 하드웨어 구성정보들과 address mapping과 garbage collection algorithm과 같은 소프트웨어 알고리즘들을 다양하게 변경하며 사용자가 합리적인 정확도로 host의 성능을 평가할 수 있도록 하였다. 그 결과 VSSIM은 SSD(X-25M)의 real time 성능을 5% 오차 범위 내에서 재구현 할 수 있었다.

기술적으로 중요한 점은 I/O latency를 "algorithmic 방법"으로 적절하게 활용하는 방법이다. SSD가 NAND chips. bus, micro-controller와 같은 수 많은 물리적인 구성요소로 이루어져 있기 때문에 SSD에서 여러 동시 작업을 생성하기 위해 이 구성요소들은 독립적으로(또는 동기화된 방식으로) 작동한다. I/O 요청의 latency는 여러 SSD 구성요소 사이에서 이러한 I/O 요청의 동시 처리가 얼마나 발생하는지에 따라 큰 영향을 받는다. 그러므로 논문에서는 SSD 구성요소의 동시 동작을 모델링하는 방법을 개발하는데 중점을 둔다. NAND flash chip과 같은 개별 구성요소를 thread로 emulate하는 대신 주어진 IO 명령에 대한 latency를 계산하기 위해 정교한 delay model을 개발했다. 그 결과 제안된 delay 모델을 통해 각 구성 요소를 thread로 모델링하지 않고도 SSD 구성요소의 병렬 동작을 emulate할 수 있었다.

개별 구성요소에 thread를 할당하면 동시 동작 및 다른 SSD 구성요소와의 상호 작요을 쉽게 모델링 할 수 있지만 lock contention 및 context switch overhead로 인해 emulator 정확도가 낮아질 수 있다. 예를 들어 10개의 channel과 2개의 way 가 있는 Intel X25-M SSD(Intel, 2009)를 emulate하려면 X25-M의 20개 flash plane과 10개 channel을 모델링하기 위해 총 30개의 thread가 필요할 것이다.

논문에서는 multi-channel/multi-way를 가지는 SSD의 IO delay를 계산하는 analytical model을 개발하였다. 제안된 delay model은 read나 write 요청의 latency를 정확하게 계산한다. 이 모델을 사용하면 하나의 thread를 사용하여 SSD 구성요소의 병렬 동작을 emulate할 수 있다. 예를 들어 IO 요청을 수신할 때 thread는 IO latency를 계산하고 busy wait을 사용하여 적절한 delay를 부여하는 방식이다. IO latency model의 결과를 실제 SSD인 Intel X25-M과 비교했을 때 3.8% 미만의 오차 범위가 나타났다.

2 Background

Figure 1은 4개의 channel과 2개의 way를 가진 SSD의 internal block diagram을 보여준다. SATA, PCIe와 같은 host interface를 통해 SSD는 IO 명령어를 수신한다. IO command에는 시작 sector 번호 (512Byte per a sector)와 sector의 길이 정보가 포함되어 있다. Host에서 오는 IO 요청은 command queue에 쌓이고 그에 따른 데이터가 device buffer에 쌓인다. 이 device buffer는 write buffer라고도 불린다(Kim and Ahn, 2008). SSD의 펌웨어는 IO 요청이 전달되는 NAND flash block을 찾고 각 NAND controller에 IO command를 보낸다.

 

Flash Memory Read and Write: Figure 2는 Samsung NAND flash memory의 내부 구조를 보여준다. Flash memory는 여러 페이지로 구성되어 있으며 각 페이지는 2~8 KByte의 크기를 가진다. Flash memory는 여러 페이지로 구성되어 있는 block 단위로 erase 동작을 수행한다. 동일한 레지스터를 사용하여 데이터를 전송하는 block의 집합을 plane이라고 한다. Write 동작에서 flash controller는 레지스터에 데이터를 쓴다. 레지스터에 데이터 쓰기가 끝나고 나면, 레지스터에 있던 데이터는 flash memory의 빈 공간에 program(write)된다. Read 동작은 write 동작의 반대로 동작한다. Read 동작일 때는 flash memory가 flash page에서 데이터를 읽어서 레지스터에 기록한다. 이러한 동작이 완료되면 flash controller가 channel을 통해 데이터를 가져온다.

SSD는 I/O 성능을 높이고 flash write 및 read 작업의 대기 시간을 줄이기 위해 plane parallelism, channel parallelism, and way parallelism과 같은 여러 계층에서 IO 병렬 처리를 활용한다.

Plane Parallelism: Flash memory의 내부 IO 동작은 여러 레지스터를 동시에 사용함으로써 병렬 동작을 구현한다. Figure 2에서 flash memory는 2개의 page IO를 병렬적으로 수행한다. Plane 0이 레지스터에 데이터를 보낸 후, flash controller가 Plane1에 레지스터를 전송한다. 레지스터가 동일한 channel을 공유하기 때문에 flash controller는 두 레지스터에 동시에 access할 수 없다. Flash controller에서 각 레지스터로 데이터 전송이 완료된 후, 각 plane은 빈 페이지에 데이터를 기록한다. Figure 3에서와 같이 flash controller와 레지스터 사이의 데이터 전송 시간(82usec for Samsung NAND flash)은 flash page의 기록 시간(900usec)보다 훨씬 짧기 때문에 두 page 프로그래밍 작업을 병렬로 수행할 수 있다. 이러한 병렬성을 "plane parallelism"이라고 한다. Plane parallelism은 read 동작에서도 적용될 수 있다.

 

Channel Parallelism:

Way Parallelism:

3 Modeling The Latency

이번 장에서는 multi channel과 multi way를 가진 SSD의 IO latency model을 구현한 방법을 설명한다. 이때 SSD의 동시 IO processing을 고려해야한다. 그러므로 먼저 single page IO latency model을 설명한 다음, multiple page IO latency model에 대해서 설명한다. IO latency라는 용어를 host에서 device로 IO command가 도착한 후 I/O 장치가 IO 명령의 완료를 알리는 IO 인터럽트를 보내는 시간 사이로 정의한다. 그리고 IO latency model에서 사용된 용어들은 Table 1에 정리해두었다.

3.1 Modeling Single Page Write/Read

Write 동작에서 IO latency는 장치가 완료 인터럽트를 보내는 시기에 따라 크게 달라진다. Device는 ①device의 write buffer에 데이터가 기록되거나 ②NAND flash에 데이터가 저장될 때 완료 interrupt를 보낼 수 있다. 전자의 경우 write latency는 interface의 속도와 데이터의 크기에 따라 결정된다. 논문에서는 host가 "O_DIRECT" 옵션을 적용한 것과 같이 스토리지에 데이터를 직접 기록하도록 요청한 후자의 경우에 더 집중을 한다. single page write latency는 Eq.1 과 같이 표현될 수 있다. 

Eq.1은 총 페이지 쓰기 시간(Wpage)은 channel switching delay(Wch), 플래시 컨트롤러와 플래시 메모리 레지스터 간의 데이터 전송 delay(Wreg), 데이터 프로그래밍 delay(Wcell)의 합으로 표현되어 있다.

Read 동작에 대한 latency도 host에서 보낸 command부터 IO 완료 interrupt가 발생할 때까지로 정의하며, 읽기 대기 시간(Rpage)은 channel switching delay(Rch), NAND 페이지 읽기 delay(Rcell) 및 레지스터 읽기 delay(Rreg)을 합산한 식으로 표현된다.

3.2 Write Operations

호스트 요청에는 둘 이상의 페이지 I/O 요청이 포함될 수 있다. 예를 들어, 512KByte SATA write 명령이 수신되면 4KByte page 크기의 SSD는 128 page write를 수행해야 한다. Multiple page write 요청이 수신되면 multi-channel/multi-way SSD가 IO 병렬 처리를 활용하여 작업을 동시에 처리한다. Figure 7은 multiple page 쓰기 요청을 처리할 때의 각 flash memory 동작의 timing diagram을 보여준다.

SSD가 channel parallelism, way parallelism, plane parallelism을 사용할 때 병렬로 처리할 수 있는 최대 페이지 수를 ρ로 표시한다. 이는 SSD는 한 사이클에서 ρ개의 page write를 처리할 수 있다는 의미이다. 각 사이클에서 1~ρ page IO를 처리하는 flash memory는 FM1 ~ FMρ로 표시한다. 먼저 flash controller는 FM1에 page 쓰기 요청을 보내고 channel switching delay(Wch) 단계로 들어선다. 그 후, 레지스터 쓰기 delay(Wreg)이 발생하고 NAND 페이지 쓰기 delay(Wcell)가 발생한다. 이러한 동작 시간의 합은 SSD에서 한 페이지를 쓰는데 드는 시간이며 Wpage로 표시한다. FM1에 대한 channel switching delay가 발생한 후 flash controller가 FM2에 다른 페이지 쓰기 요청을 보내는 동안 FM1의 레지스터에 데이터를 기록한다. FM2에서도 데이터를 쓰기 전에 channel switching delay이 발생한다. 이는 FM1과 FM2가 서로 다른 channel을 사용하기 때문이다. 같은 방법으로 FM2에 channel swtiching delay가 발생한 후, flash controller는 다른 페이지 쓰기 요청을 다음 flash memory에 보낸다. Flash controller는 페이지 쓰기 요청을 FMρ에 보낼 때까지 이 프로세스를 반복한다. Figure 7은 첫번째 cycle이 완료된 후 두번째 cycle의 시작 부분을 보여준다. FM1에서 두번째 cycle의 첫번째 작업을 시작하려면 FM1의 작업이 완료되어야 한다. 첫번째 페이지 쓰기 작업을 시작하기 전 두번째 cycle의 대기 시간은 t_wait으로 표현되며 이는 다음 Eq.3에서 나타나있다.

만약 single page writing time(Wpage)가 충분히 짧다면, t_wait는 0이되고 두번째 cycle은 대기시간 없이 첫번째 페이지 쓰기 작업을 시작할 수 있다.

한 cycle의 처리 시간은 첫 번째 페이지 쓰기 시작부터 다음 cycle의 첫 번째 페이지 쓰기를 시작하기까지 이다. 이는 t_cycle로 표시되며 Eq.4 로 계산할 수 있다.

Figure 8은 마지막 cycle에 대한 timing diagram을 보여준다. 경우에 따라 마지막 cycle에서 수행된 IO의 수는 ρ보다 작을 수 있으며, 이는 N_remain으로 표시된다. Figure 8에서 마지막 cycle의 처리 시간을 아래의 방법을 통해 쉽게 얻을 수 있다.

Eq.5를 사용하여 호스트에서 요청한 write의 처리 시간을 의미하는 t_record를 계산할 수 있다. 쓰기 요청의 경우 SSD가 반복해야 하는 주기 수를 N_cycle로 표시한다. 그런 다음 t_record는 다음과 같이 계산된다.

"ρ×(N_cycle −1)+N_remain"이 record에서 사용한 전체 페이지의 개수(N_page)와 같기 때문에, t_record에 대한 write latency model을 다음과 같이 얻을 수 있다.

3.3 Read Operation

Read latency model은 write latency model과 같은 방법으로 Eq.7을 얻을 수 있다. Figure 9와 같은 경우에는 모델이 더 간단해질 수도 있다. 이 경우 중요한 점은 cycle이 변할때의 t_wait가 없다는 것이다. 이는 NAND read 동작이 write보다 훨씬 빠르기 때문에 나타난 결과이다 (50usec for a read operation, 900usec for a write operation in Samsung NAND flash). 이 경우 t_wait는 0이 되고 "t_record = Rch ×(Npage-1)+Rpage" 로 표현될 수 있다.

4 Experiment

In this section, we validate the accuracy of the IO latency models with a real SSD, Intel X25-M. Using analytical models, we calculated the IO performance of an SSD that is configured the same way as X25-M under various workloads. Then, we measured the IO performance of X25-M performing the same workloads and compared both results. Next, we compared the theoretical performance with VSSIM SSD simulator (Yoo et al., 2013). From this experiment, we are assured that the IO latency models can be used in VSSIM as an IO emulator module.

4.1 Validation with X25-M

4.2 Validation with VSSIM

5 Related Work

Analytic modeling of write performance (Desnoyers, 2012) provides block cleaning performance in terms of the Write Amplification Factor (WAF): the ratio between the number of page writes from the host to the number of page writes that happen in an SSD. Although this work provides a precise closed-form solution for the block cleaning performance for LRU and greedy collection algorithm, it cannot be used to predict the IO latency of SSDs.

There has been much research on simulating the performance of SSDs or flash memory. One of the SSD simulators is NANDFlashSim (Jung et al., 2012). NANDFlashSim simulates a single flash memory and can configure a page size, IO latency, the number of dies in a flash memory, and the number of planes. It supports various IO modes such as cache mode, internal data move mode, multi-plane mode, and interleaved mode. NANDFlashSim uses local clock domain, and all flash memories are synchronized with it. At every clock, NANDFlashSim checks the progress of each flash memory and changes its state. Because NANDFlashSim only simulates flash memory, it cannot measure the performance of SSDs using channel, way, and plane parallelism.

CPS-SIM (Lee et al., 2009) can simulate SSDs that use channel parallelism. Similar to NANDFlashSim, CPS-SIM is a clock-driven simulator, which synchronizes its state machine with local clock. For IO processing, each flash memory is managed by a finite state machine. CPS-SIM checks each flash memory for the completion of IOs and changes its state. For higher accuracy of the simulation result, clock-driven simulators have to use higher clock frequency. At the same time, clock driven simulators need enough clock intervals to check and change the state of every flash memory. These conflicting needs make it difficult for clock-driven simulators to guarantee the accuracy of their simulation results.

There are simulators that provide a virtual flash device in a main memory, such as NANDSim (NANDSim, 2008) and Flash Disk Simulator (El Maghraoui et al., 2010). A host uses virtual devices as a primitive flash memory or as a block device. This enables us to check the performance of the host, which operates on top of the virtual devices. However, the simulators only simulate a flash memory. Thus, we cannot get IO performance of an SSD, which utilizes multi-channel and multi-way parallelism. Flash-DBSim (Jin et al., 2009) also provides a virtual flash device to upper layer. Flash-DBSim creates a virtual flash disk in memory which is managed by MTD (Memory Technology Device) module. MTD Module supports interfaces for Flash Translation Layer (FTL) to manipulate the virtual flash disk. Unlike NANDSim, Flash-DBSim uses a trace as workload. Because Flash-DBSim only simulates a flash memory, it cannot test various IO parallelism supported in an SSD.

Trace driven SSD simulator is also widely used to examine the internal behavior of SSDs. DISKSim SSD Extension (Agrawal et al., 2008) and Flashsim (Kim et al., 2009) are developed to simulate an SSD based on DiskSim (Bucy et al., 2008). With these simulators, users can configure the number of flash memories, the number of planes per flash memory, the page read/write latency, a page size, a block size, etc. However, these simulators calculate the SSD performance without imposing IO processing delay, which means that they cannot be used to observe the host IO performance in real time.

6 Conclusion

SSD의 동시 IO 처리를 고려한 IO 대기 시간을 계산하는 분석 모델을 개발

SSD인 Intel X25-M의 성능과 비교했을 때 레이턴시 모델은 다양한 워크로드에서 4% 미만의 오차

VSSIM으로 결과를 검증하여 IO 대기 시간 모델을 SSD 시뮬레이터에서 0.8%~7.6% 오차로 사용할 수 있음을 입증

IO 대기 시간 모델을 사용하여 SSD 시뮬레이터는 IO 요청에 대해 IO 대기 시간을 계산할 수 있음

다중 스레드 방법을 사용하지 않고 다중 채널 및 다중 방향 SSD의 IO 성능을 시뮬레이션 하였다는 장점이 있음