[논문]SSD FTL의 캐시 메커니즘에 대한 심층 분석 및 개선

이형봉; 정태윤

doi:10.14372/iemek.2020.15.1.9

Abstract ▼ AI-Helper

Recently, the capacity of SSD has been increasing rapidly due to the improvement of flash memory density. To take full advantage of these SSDs, first of all, FTL's prompt adaptation is necessary. The FTL is a translation layer existing in SSDs to overcome the drawback of the SSD that cannot be modif...

Recently, the capacity of SSD has been increasing rapidly due to the improvement of flash memory density. To take full advantage of these SSDs, first of all, FTL's prompt adaptation is necessary. The FTL is a translation layer existing in SSDs to overcome the drawback of the SSD that cannot be modified in place, and has garbage collection and caching functions in addition to the map table management function. In this study, we focus on caching function, compare and analyze the cache implementation methodologies, and propose improved methods. Typical cache implementations divide the cache into groups, manage and retrieve the caches in the group as a linked list. Thus, searches are made in the order of the linked list. In contrast, we propose a method of sequential searching using the search area group of a cache registered in the map table regardless of the linked list and cache group. Experimental results show that the proposed method has a 2.5 times improvement over the conventional method.

주제어

표/그림 (16)

그림 그림 1. FTL 읽기/쓰기 프로시저 Fig. 1 FTL read/write Procedure
그림 그림 2. 해싱 그룹에 의한 캐시 구조 Fig. 2 Cache Architecture using Hashing Group
표 표 1. 실험 플랫폼 Table 1. Experimental Platform
그림 그림 3. LM/ML 캐시 검색 알고리즘 Fig. 3 LM/ML Cache Search Algorithm
그림 그림 4. LM/ML 알고리즘 비교 Fig. 4 Comparison of LM/ML Algorithm
그림 그림 5. SQ 캐시 검색 알고리즘 Fig. 5 Search Algorithm for SQ Cache
표 표 2. LM/ML 알고리즘 검색시간 (초) Table 2. Search Time of LM/ML Algorithm (sec)
표 표 3. ML/SQ 알고리즘 검색시간 (초) Table 3. Search Time of ML/SQ Algorithm (sec)
그림 그림 6. ML/SQ 알고리즘 비교 Fig. 6 Comparison of ML/SQ Algorithm
그림 그림 7. SG 캐시 검색 알고리즘 Fig. 7 SG Cache Search Algorithm
그림 그림 8. SQ/SG 알고리즘 비교 Fig. 8 Comparison of SQ/SG Algorithm
표 표 4. SQ/SG 알고리즘 검색시간 (초) Table 4. Search Time of SQ/SG Algorithm (sec)
그림 그림 9. ML/SQ 알고리즘 비교 Fig. 9 Comparison of ML/SQ Algorithm
그림 그림 10. SG/BT 알고리즘 비교 Fig. 10 Comparison of SG/BT Algorithm
표 표 5. SG/BT 알고리즘 검색시간 (초) Table 5. Search Time of SG/BT Algorithm (sec)
표 표 6. ML/SQ/SG 알고리즘 비교 (배) Table 6. Comparison of ML/SQ/SG Algorithm (times)

AI 본문요약
AI-Helper

문제 정의

제자리 수정하기가 불가능한 SSD의 근본적 특성을 해결하기 위한 FTL은 논리 페이지와 물리 페이지 번호 사이의 변환, 쓰인 후 초기화를 기다리는 가비지 수집, 물리 페이지 입‧출력을 최소화하기 위한 캐싱 등 세 가지 핵심 기능을 담당한다. 이 논문에서는 FTL의 캐싱 기능에 집중하여 캐시 구현 방안들을 분석하고 개선 방안을 제시하였다. 개선 방안 중, LRU 캐시 그룹과 독립적인 검색 구간을 설정하고 할당 캐시가 속한 검색 구간을 맵 테이블에 표시하는 캐시 구간 순차 검색 방법은 LRU 캐시 그룹을 연결 리스트로 검색하는 일반적인 방법보다 평균 1.

제안 방법

이 연구에서 구현한 LRU 캐시 교체 알고리즘은 그림 1과 같이 최초 쓰기의 경우 일단 데이터를 캐시에만 보관할 뿐 곧바로 물리 페이지를 할당하지 않고, 이후에 교체 대상으로 선정되었을 때 비로소 물리 페이지에 플러시한다. 따라서, 최선의 경우 물리 페이지는 할당되지 않은 채 최종적으로 삭제와 함께 마무리될 수도 있다.
이러한 차이점에도 불구하고 청결 캐시 우선(CFLRU: Clear First LRU) [11], 정적 청결 캐시 우선(CCFLRU: Cold Clean First LRU) [12] 등 LRU에 NUR 알고리즘을 부가적으로 적용하여 제한적 환경에서 페이지 쓰기 회수를 줄이려는 연구들이 있다. 이 연구에서는 LRU 페이지 교체 알고리즘을 기반으로 몇 가지 캐시 구현 방법론을 비교‧분석하고 개선안을 제시한다.

대상 데이터

FTL에 적용할 부하 워크로드로, 200MB 크기의 각 파일에 대하여 랜덤하게 설정한 8KB 안팎의 레코드를 15,000번 순차 쓰기 하는 스레드 4개, 순차 읽기 하는 스레드 4개, 랜덤 위치 (offset)에서 읽기 하는 스레드 4개, 랜덤 위치에서 쓰기 하는 스레드 4개, 랜덤 위치에서 읽고 덮어쓰는 스레드 4개 등 대표적인 입‧출력 패턴 다섯 가지 유형을 포괄하는총 20개의 스레드를 사용한다.

이론/모형

일반적인 캐시 구현은 그림 2와 같이 캐시들을 그룹으로 분할하고 논리 페이지 번호 (lpn)에 대한 해시 값으로 할당 그룹을 결정한다. 이 연구에서는 ‘lpn mod NGRP’ 형태의 해시 함수를 적용한다. 희생 캐시는 CLRU (Cache Least Recently Used)에서 할당되고 읽기나 쓰기가 이루어진 캐시는 CMRU (Cache Most Recently Used)로 이동한다.

성능/효과

이 논문에서는 FTL의 캐싱 기능에 집중하여 캐시 구현 방안들을 분석하고 개선 방안을 제시하였다. 개선 방안 중, LRU 캐시 그룹과 독립적인 검색 구간을 설정하고 할당 캐시가 속한 검색 구간을 맵 테이블에 표시하는 캐시 구간 순차 검색 방법은 LRU 캐시 그룹을 연결 리스트로 검색하는 일반적인 방법보다 평균 1.5~2.5배 우수함을 확인하였다. B tree 검색 방법은 캐시 그룹핑에 관한 어떠한 영향도 받지 않고 안정적인 최고 성능을 보이지만 약 5KB 정도의 추가 메모리를 소모하는 단점이 있다.

후속연구

이 연구의 결과는 FTL 시뮬레이션 과정에서 캐시를 어떻게 구현해야 할 것인가에 대한 시행착오 예방에 기여할 것이며, 이를 바탕으로 가비지 수집에 효과적인 캐시 교체 전략에 대한 연구가 계속 이어질 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	SSD의 시간적 성능저하가 없는 이유는 무엇인가?	이 중에서도 특히 빠른 접근속도는 일반 사무용 PC의 부팅과정에서 쉽게 실감할 수 있다. 기존의 하드 디스크가 데이터의 흩어짐 정도에 따라 기계적 탐색시간이 크게 늘어나는 반면, SSD는 저장 위치가 전자적으로 탐색되므로 시간적 성능 저하가 전혀 없다. 이에 따라 최근 출시되는 대부분의 PC는 시스템 디스크용으로 SSD를 탑재하고 있다 [1].
	SSD의 장점은 무엇인가?	플래시 메모리에 기반한 SSD (Solid State Disk)는 널리 알려진 바와 같이 빠른 접근속도, 낮은 전력소모, 높은 내충격성, 가벼운 무게 등의 장점으로 기존의 하드 디스크를 빠르게 대체하고 있다. 이 중에서도 특히 빠른 접근속도는 일반 사무용 PC의 부팅과정에서 쉽게 실감할 수 있다.
	Solid State Disk의 단점은 무엇인가?	이러한 장점에도 불구하고 초기화 없이 제자리 쓰기가 불가능하고, 초기화 회수가 한정되어 있다는 단점은 SSD의 효율적 이용에 대한 장애요인이다. 여기에 더해 읽기‧쓰기 단위인 페이지 크기와 초기화 단위인 블록의 크기가 다르고, 각 연산에 소모되는 전력이 각각 다르다는 점은 SSD의 보편적 최적화는 거의 불가능함을 의미한다 [2].

참고문헌 (14)

D.H. Gouk, M.R. Kwon, M.S. Jung, "Practical Analysis and Characterization Methods of Moders SSD using Full-System Integrated SimpleSSD," Journal of Communications of the Korean Institute of Information Scientists and Engineers, Vol. 36, No. 6, pp. 37-55, 2018 (in Korean).
V. Mohan, T. Bunker, L. Grupp, S. Gurumurthi, M.R. Stan, S. Swanson, "Modeling Power Consumption of NAND Flash Memories Using FlashPower," Journal of IEEE Transactions on Computer-Aided Design of Integrated Circuit and Stsrems, Vol. 32, No. 7, pp. 1031-1044, 2013.

상세보기
Y.S. Kim, "A Compact Representation of Translation Pages for Flash Translation Layers of Solid State Drives," Journal of the Korea Society of Computer and Information, Vol. 24, No. 2, pp. 1-7, 2019 (in Korean).

원문보기 상세보기
Samsung Electronics, "Samsung SSD 850 Pro Data Sheet Rev. 3," 2017 (available on : http://downloadcenter.samsung.com/content/UM /201711/20171115103115156/Samsung_SSD_850_PRO_Data_Sheet_Rev_3.pdf).
H.J. Kim, D.K. Shin, "Increasing-Order Page-Level Mapping FTL for Memory-constraint Flash Storage Systems," Proceedings of Korea Computer Congress, pp. 1181-1183, 2016 (in Korean).
S.H. Kim, Garbage Collection Technique for Balanced Wear-out and Durability Enhancement with Solid State Drive on Storage Systems," Journal of the Korea Society of Computer and Information, Vol. 22, NO 4, pp. 25-32, 2017 (in Korean).

원문보기 상세보기
J.K. Park, J.H. Kim, "Flash Storage System, A Method for Reducing Garbage Collection Overhead of SSD Using Machine Learning Algorithms", Proceedings of International Conference on Information and Communication Technology Convergence (ICTC), pp. 775-777, 2017.
N. Shahidi, M.T. Kandemir, "CachedGC:Cache-Assisted Garbage Collection in Modern Solid State Drives," Conference of IEEE 26th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pp. 79-85, 2018.
A. Silberschatz, P.B. Galvin, G. Gagne, "Operating Ssystem Concepts-ninth Edition," Wiley Press, pp. 604-607, 2013.
H.B. Lee, T.Y. Chung, "A Comparative Analysis on Page Caching Strategies Affecting Energy Consumption in the NAND Flash Translation Layer," IEMEK J. Embed. Sys. Appl., Vol. 13, No. 3, pp. 109-116, 2018 (in Korean).

원문보기 상세보기
S.Y. Park, D.W. Jung, J.U. Kang, J.S. Kim, J.W. Lee, "CFLRU: A Replacement Algorithm for Flash Memory," Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'06), pp. 234-241, 2006.
Z. Li. P. Jin, X. Su, K. Cui, L. Yue, "CCF-LRU: A New Buffer Replacement Algorithm for Flash Memory," Journal of IEEE Transactions on Consumer Electronics, Vol. 55, No. 3, pp. 1351-1359, 2009.

상세보기
J.S. Bucy, J. Schindler, S.W. Schlosser, G.R. Ganger, The DiskSim Simulation Environment Version 4.0 Reference Manual, Technical Report CMU-PDL-08-101, 2008.
Cygwin, Avaliable on : https://www.cygwin.com/

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

SSD FTL의 캐시 메커니즘에 대한 심층 분석 및 개선
An In-Depth Analysis and Improvement on Cache Mechanisms of SSD FTL 원문보기

Abstract ▼ AI-Helper

주제어

표/그림 (16)

표/그림 (16)

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

SSD FTL의 캐시 메커니즘에 대한 심층 분석 및 개선 An In-Depth Analysis and Improvement on Cache Mechanisms of SSD FTL 원문보기

Abstract ▼ AI-Helper

주제어

표/그림 (16) 모든 표/그림 보기

표/그림 (16) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

이형봉 (25) 정태윤 (14)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

SSD FTL의 캐시 메커니즘에 대한 심층 분석 및 개선
An In-Depth Analysis and Improvement on Cache Mechanisms of SSD FTL 원문보기

표/그림 (16)

표/그림 (16)

AI 본문요약
AI-Helper