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

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

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

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

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

4 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

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

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

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

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

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

10 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 1234320 1237431 1240431 1250431 10

11 특징 – 전체 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 1235431 1236431 1237431 Compression Chunk 1235 1236 1237 … … Flash Memory 하나의 compression chunk 11

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

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

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

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

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

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

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

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

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

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

22 평가 방법 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

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