한상욱, 이성진 (shanehahn, 고급 내장형 시스템 Lab3: Compression-Aware FTL 서울대학교 컴퓨터공학부 임베디드 시스템 연구실

본 실습의 목표 본 실습에서는 플래시 저장장치서 데이터 압축 (data compression) 기능의 구현을 목표함 –(1) 내구성 측면에서의 이득 확인 –(2) 플래시 변환 계층에서의 설계상의 이슈 –(3) 소프트웨어 단계에서의 최적화 이슈 Mini Project: Compression-Aware FTL2

Data Compression 소개 Data Compression 의 장점 – 성능 향상 : 데이터의 크기를 줄임으로써, 저장장치에 직접 읽고 쓰는 양이 줄어들게 됨 – 수명 개선 : 데이터의 크기를 줄임으로써, 저장장치에 쓰는 양이 적어지므로, 쓰고 지우는 과정이 줄어들게 됨 Data Compression 의 단점 –Compression cost : Data compression 을 위한 부가적인 비용이 들게 됨 –Hardware-accelerate compression 기능을 활용하여 계산 비용을 줄일 수 있음 ( 본 실습에서는 software 기반의 compression 만 고 려함 ) Mini Project: Compression-Aware FTL3

Data Compression Overview Mini Project: Compression-Aware FTL Compressor Module Data Compression 기능 Data Decompression 기능 BlueFTL - 압축된 데이터를 고려한 주소 사 상 기능 필요 - 압축된 데이터를 고려한 가비지 컬렉션 기능 필요 - 데이터 버퍼링 기능 필요 - 기타 최적화 기능 필요 BlueSSD (Emulation) block … Flash chip block … Flash chip block … Flash chip block … Flash chip block … Flash chip block … Flash chip Flash bus Host 4

Data Compression 단위 (1) 페이지 단위 압축의 문제점 – 플래시의 기본적인 읽기 / 쓰기 연산의 단위는 페이지임 – 페이지 단위로 데이터를 압축할 데이터의 량은 감소하지만 실제 쓰기 연산 횟수는 감소 시키지 못함 – 내부 단편화 (Internal Fragmentation) 문제 Mini Project: Compression-Aware FTL 1301 request Physical Flash memory Compressor BlueFTL Internal Fragment 5

Data Compression 단위 (2) 다수의 페이지를 하나의 compression chunk 로 묶어서 기 록 – 다수의 논리 페이지를 하나의 덩어리로 묶어 더 적은 개수의 물리 페이지에 기록함 ( 이러한 데이터 덩어리를 compression chunk 라 함 ) – 기록 요청된 페이지의 개수 대비 실제 쓰여지는 페이지의 개수를 감소시킬 수 있음 Mini Project: Compression-Aware FTL 1301 Internal Fragment Compression Chunk 6 Physical Flash memory Compressor BlueFTL Write Buffer

Data Compression 단위 (3) 다수의 페이지를 묶어서 기록할 경우 아래와 같은 기술적 이슈가 발생함 – 쓰기 시 요청된 페이지 데이터를 임시로 보관할 쓰기 버퍼가 필요함 – 읽기 시 compression chunk 내 페이지를 항상 모두 읽어야 함 Mini Project: Compression-Aware FTL 7 Compressor BlueFTL Physical Flash memory 1301 Compression chunk Read ( 여기서는 2 page) Compressor BlueFTL Physical Flash memory Write Buffer

비효율적 Data Compression Compression 이 효과적이지 않을 수 있음 –Compression 이 이루어 져도, 크기가 줄지 않을 수 있음 – 메타 데이터 (Head information) 으로 인해 크기가 더 커질 수 있음 –Compression 을 하지 않는 것이 최적화 방법 ! Mini Project: Compression-Aware FTL Physical Flash memory Compressor BlueFTL Write Buffer Physical Flash memory Compressor BlueFTL Write Buffer 메타 데이터

쓰기 버퍼 (Write Buffer) 쓰기 버퍼 (write buffer) 의 기능 –4 개의 페이지를 한번에 flush 하여 플래시 메모리에 저장하기 위함 –Flush 시에는 header information 과 함께 데이터를 보냄 Mini Project: Compression-Aware FTL request Compression Chunk 9 Compression Algorithm (LZRW3) Write Buffer

Chunk Table (1) 기능 –Compression Chunk 들의 관리를 위해 필요함 구성 : 3 가지 정보 유지 –Valid page counter : compression chunk 에 유효한 logical 페이지 수 –Number of physical pages: compression chunk 에 할당된 물리 페이 지 수 –Compression indicator : 데이터의 compression 여부를 나타냄 (compression 된 경우 ‘1’, 아닌 경우 ‘0’ 으로 표기 ) Mini Project: Compression-Aware FTL Data Chunk Table Physical page address Valid page counter Number of physical pages Compression indicator

특징 – 전체 entry 는 물리적 페이지의 주소 개수 만큼 유지해야 함 – 하나의 compression chunk 가 여러 페이지에 걸쳐있는 경우, 각 entry 는 동일한 값을 가짐 Chunk Table (2) Mini Project: Compression-Aware FTL Data Chunk Table Physical page address Valid page counter Number of physical pages Compression indicator Compression Chunk … … Flash Memory 하나의 compression chunk 11

Write operation : 모두 새로운 데이터 쓰기 요청일 경우 Compression 동작 과정 (1) Mini Project: Compression-Aware FTL Compression algorithm (LZRW3) 쓰기 버퍼에 4 개의 페이지를 모은 후, 쓰기버퍼에 모인 데이터 전체를 compress lpappa ppa Valid page counter No. of physical pages Compressi on indicator … … … … … … … … Compression Chunk … … Flash Memory Mapping Table Data Chunk Table Write Buffer 12

lpappa Compression 동작 과정 (2) Mini Project: Compression-Aware FTL Compression algorithm (LZRW3) 쓰기 버퍼에 4 개의 페이지를 모은 후, 쓰기버퍼에 모인 데이터 전체를 compress ppa Valid page counter No. of physical pages Compressi on indicator … … … … Flash Memory … … … … … … Mapping Table Data Chunk Table … Compression Chunk update updat e 2 Write operation : 데이터를 update 하는 요청이 있는 경우 Write Buffer 13

lpappa Compression 동작 과정 (2) Mini Project: Compression-Aware FTL Compression algorithm (LZRW3) 쓰기 버퍼에 4 개의 페이지를 모은 후, 쓰기버퍼에 모인 데이터 전체를 compress ppa Valid page counter No. of physical pages Compressi on indicator … … … … Flash Memory … … … … … … Mapping Table Data Chunk Table … Compression Chunk update updat e 2 Write operation : data compression 을 하지 않는 경우 Write Buffer 14

Read operation : LBN 302 번 읽기 요청일 경우 Decompression 동작 과정 Mini Project: Compression-Aware FTL Compression algorithm (LZRW3) Compression chunk 전체 decompress 후, 요청이 들어온 페이지만 host 에게 전달 lbnppa ppa Valid page counter No. of physical pages Compressi on indicator … … … … … ………… … … … … … Flash Memory Mapping Table Data Chunk Table Compression Chunk

가비지 컬렉션 사용된 블록 중 다음 블록을 교체 대상으로 선정 –(1) 빈 블록이 아닌 블록 –(2) Compression chunk 내 유효 페이지 수가 가장 적 은 블록 페이지 이주에 따른 부하가 상대적으로 적은 블록 페이지 기반 FTL 의 greedy 정책과 유사한 방식임 Mini Project: Compression-Aware FTL16

교체할 블록 선정 예 Mini Project: Compression-Aware FTL17 Block 1Block 2Block 3 플래시 페이지 무효한 압축된 페이지 유효한 압축된 페이지 이주 비용 측면에서 가장 저렴한 블록임 Compression Chunk 1 Compression Chunk 2

페이지 이주 ( 블록 합병 ) 과정 선택된 교체 블록 내의 유효한 페이지를 빈 블록에 복사 –(1) Compression chunk 를 압축 해제하여 유효 한 데이터만 임시로 버퍼에 저장함 –(2) 압축 해제된 페이지 4 개를 다시 압축하여 새로운 compression chunk 를 생성함 –(3) 새로 만든 compression chunk 를 빈 블록에 기록 –(4) 일반적인 쓰기 연산과 동일하게 페이지 사 상 테이블과 chunk table 을 알맞게 갱신함 Mini Project: Compression-Aware FTL18

페이지 이주 ( 블록 합병 ) 과정 예 Block 1, Block 2, Block 3 이 순차적으로 Victim 으 로 선택되어 합병된다고 가정함 Mini Project: Compression-Aware FTL19 Block 1Block 2Block 3 Free Block (1) 압축 해제 후 임시 버퍼에 저장 (2) 재압축 (3) 기록 삭제

참고자료 세부적인 설명은 다음 논문을 참고 –“Improving Performance and Lifetime of Solid- State Drives Using Hardware-Accelerated Compression,” IEEE Transactions on Consumer Electronics, Vol. 57, Issue 4, pp , December Mini Project: Compression-Aware FTL20

관련코드 개선된 코드를 다운 받은 후 사용 –Data compression 을 위해 새로 수정된 코드를 ftp 에 올려놓았음 압축 알고리즘 –LZRW3 알고리즘 사용하여 관련 코드는 제공 함 lzrw3.c / lzrw3.h 홈페이지의 공지 확인 Mini Project: Compression-Aware FTL21

평가 방법 STEP1: FTL 초기화 확인 – 파일 시스템 초기화가 정상적으로 이루어지는지 확인 mkfs 및 mount 과정이 정상적으로 수행되는지 확인 STEP2: FTL 데이터 기록 확인 – 대량의 압축된 데이터 기록 후 압축이 정상적으로 해제 되는지 확인 페이지 캐시의 영향이 없도록 평가 전 페이지 캐시를 비움 –sudo –c “echo 3 > /proc/sys/vm/drop_caches” STEP3: FTL 동작 및 성능 평가 –bonnie++.sh, run_postmark.sh, run_tiobench.sh: 성능 평가 /home/ssd/blueftl_lab1/benchmark 디렉터리 참고 Mini Project: Compression-Aware FTL22

과제 제출 제출 자료 – 구현한 소스 코드와 결과 보고서 제출 제출 방법 – 다음 이메일 주소로 제출 : 한상욱 / – 기타 문의 사항 : 이성진 / 제출 시간 –2013 년 6 월 14 일 ( 금 ) 오후 11 시 59 분까지 Mini Project: Compression-Aware FTL23