Flash Memory Pattern Test를 위한 효율적인 알고리즘 연구

김태환,장훈 한국차세대컴퓨팅학회 2016 한국차세대컴퓨팅학회 논문지 Vol.12 No.6

스마트폰, 태블릿 PC, 울트라북등 휴대기기 사용의 증가로 인해 NAND-형 Flash Memory의 수요도 지속적으로 증가하고 있다. 그렇기 때문에 NAND-형 Flash Memory에서 발생할 수 있는 고장을 진단하기 위한 알고리즘 연 구가 매우 중요하다. Flash Memory는 셀 배열구조에 따라서 NOR-형 Flash Memory와 NAND-형 Flash Memory로 구분이 된다. NOR-형 Flash Memory는 다양한 테스트 알고리즘과 BIRA(Built-in Redundancy Analysis)알고리즘, 진단 알고리즘 등 다양한 알고리즘 연구가 진행되어 왔다. 그러나 NOR-형 Flash Memory에 서 연구되었던 이러한 알고리즘들을 이용하여 NAND-형 Flash Memory를 위한 고장을 확인하는 것이 매우 어렵 다. 따라서 본 논문에서는 NAND-형 Flash Memory에서 발생할 수 있는 고장 확인이 가능한 정확하고 효율적인 진단 알고리즘을 제안한다. 그래서 NAND-형 Flash Memory를 위한 고장 진단을 가능하게 한다. The increasing usage of mobile devices such as SmartPhone, TabletPC, and Ultrabook, the demand for NAND-type Flash Memory is also constantly growing. Therefore, high speed and miniaturization able, NAND-type Flash Memory’s research for diagnosis of possible malfunction is very important. The Flash Memory is divided into NOR-type Flash Memory, and NAND-type Flash Memory. A lot of study such as Test Algorithm, BISR(Built-In Self Repair) Algorithm and Diagnostic Algorithm, etc. has been progressed in NOR-type Flash Memory. However, it is very difficult to detect for NAND-type Flash Memory’s fault, with the former studies of algorithms for NOR-type Flash Memory. In this paper, an efficient and accurate problem diagnosable algorithm that can identify, the type of possible failure of the cell in NAND-type Flash Memory, is proposed. So it allows error diagnosing for NAND-type Flash Memory.

향상된 혼합 사상기법을 이용한 효율적인 대블록 플래시 메모리 변환계층 설계 및 구현

박동주(Dong-Joo Park),곽경훈(Kyounghoon Kwak) 한국정보과학회 2009 정보과학회 컴퓨팅의 실제 논문지 Vol.15 No.1

플래시 메모리는 크기가 작고, 적은 전력을 사용하며 충격에 강하기 때문에 MP3 플레이어, 핸드폰, 디지털 카메라와 같은 휴대용 기기에서 저장장치로 널리 사용되고 있다. 플래시 메모리의 많은 장점 때문에 개인용 컴퓨터 및 노트북에서 사용되는 저장장치인 하드디스크를 플래시 메모리로 대체하고자 하는 연구도 진행되고 있다. 플래시 메모리는 덮어쓰기가 허용되지 않으며 읽기/쓰기의 기본 단위와 삭제의 기본 단위가 다르기 때문에 FTL(Flash Translation Layer)라는 플래시 변환 계층을 사용한다. 최근에는 기존의 플래시 메모리와 다른 물리구조와 특성을 갖는 대블록 플래시 메모리가 등장하여 기존의 FTL을 그대로 사용하게 되면 플래시 메모리를 효율적으로 사용할 수 없다. 본 논문에서는 기존의 FTL 중 가장 좋은 성능을 내는 FAST (Fully Associative Sector Translation)을 기반으로 데이타블록 내에서 페이지 단위 사상을 적용하여 대블록 플래시 메모리의 특성에 맞는 FTL 기법을 제안한다. Flash memory is widely used as a storage medium of mobile devices such as MP3 players, cellular phones and digital cameras due to its tiny size, low power consumption and shock resistant characteristics. Currently, there are many studies to replace HDD with flash memory because of its numerous strong points. To use flash memory as a storage medium, FTL (Flash Translation Layer) is required since flash memory has erase-before-write constraints and sizes of read/write unit and erase unit are different from each other. Recently, new type of flash memory called “large block flash memory” is introduced. The large block flash memory has different physical structure and characteristics from previous flash memory. So existing FTLs are not efficiently operated on large block flash memory. In this paper, we propose an efficient FTL for large block flash memory based on FAST (Fully Associative Sector Translation) scheme and page-level mapping on data blocks.

NAND Flash Memory Pattern Test를 위한 PMBIST

김태환(Tae-Hwan Kim),장훈(Hoon Chang) 대한전자공학회 2014 전자공학회논문지 Vol.51 No.1

최근 새롭게 보급되는 휴대기기(스마트폰, 울트라북, 태블릿 PC)로 인하여 고용량과 빠른 속도를 원하는 소비자가 증가하고 있다. 이에 따라 Flash Memory의 수요도 지속적으로 증가하고 있다. Flash Memory는 NAND형과 NOR형으로 구분되어 있다. NAND형 Flash Memory는 NOR형 Flash Memory에 비해 속도는 느리지만 가격이 저렴하다. 그렇기 때문에 NAND형 Flash Memory는 Mobile 시장에서 많이 사용되어지고 있다. 그래서 Flash Memory Test를 위한 Fault 검출은 메우 중요하다. 본 논문에서는 Fault 검출 향상을 위한 NAND형 Flash Memory의 Pattern Test를 위한 PMBIST를 제안한다. It has been an increase in consumers who want a high-capacity and fast speed by the newly diffused mobile device(Smart phones, Ultra books, Tablet PC). As a result, the demand for Flash Memory is constantly increasing. Flash Memory is separated by a NAND-type and NOR-type. NAND-type Flash Memory speed is slow, but price is cheaper than the NOR-type Flash Memory. For this reason, NAND-type Flash Memory is widely used in the mobile market. So Fault Detection is very important for Flash Memory Test. In this paper, Proposed PMBIST for Pattern Test of NAND-type Flash Memory improved Fault detection.

NAND 플래시 메모리 저장 장치에서 블록 재활용 기법의 비용 기반 최적화

이종민(Jongmin Lee),김성훈(Sunghoon Kim),안성준(Seongjun Ahn),이동희(Donghee Lee),노삼혁(Sam H. Noh) 한국정보과학회 2007 정보과학회 컴퓨팅의 실제 논문지 Vol.13 No.7

Flash memory based storage has been used in various mobile systems and now is to be used in Laptop computers in the name of Solid State Disk. The Flash memory has not only merits in terms of weight, shock resistance, and power consumption but also limitations like erasebefore-write property. To overcome these limitations, Flash memory based storage requires special address mapping software called FTL(Flash-memory Translation Layer), which often performs merge operation for block recycling. In order to reduce block recycling cost in NAND Flash memory based storage, we introduce another block recycling scheme which we call migration. As a result, the FTL can select either merge or migration depending on their costs for each block recycling. Experimental results with Postmark benchmark and embedded system workload show that this cost-based selection of migration/merge operation improves the performance of Flash memory based storage. Also, we present a solution of macroscopic optimal migration/merge sequence that minimizes a block recycling cost for each migration/merge combination period. Experimental results show that the performance of Flash memory based storage can be more improved by the macroscopic optimization than the simple cost-based selection. 이동기기의 저장 장치로 사용되는 플래시 메모리는 이제 SSD(Solid State Disk) 형태로 노트북 컴퓨터까지 그 적용 범위가 확대되고 있다. 이러한 플래시 메모리는 무게, 내충격성, 전력 소비량 면에서 장점을 가지고 있지만, erase-before-write 속성과 같은 단점도 가진다. 이러한 단점을 극복하기 위하여 플래시 메모리 기반 저장 장치는 FTL(Flash-memory Translation Layer)이라는 특별한 주소 사상소프트웨어를 필요로 하며, FTL은 종종 블록을 재활용하기 위하여 병합 연산을 수행해야 한다. NAND 플래시 메모리 기반 저장 장치에서 블록 재활용 비용을 줄이기 위해 본 논문에서는 이주 연산이라는 또 다른 블록 재활용 기법을 도입하였으며, FTL은 블록 재활용시 이주와 병합 연산 중에서 비용이 적게 드는 연산을 선택하도록 하였다. Postmark 벤치마크와 임베디드 시스템 워크로드를 사용한 실험 결과는 이러한 비용 기반 선택이 플래시 메모리 기반 저장 장치의 성능을 향상시킬 수 있음을 보여준다. 아울러 이주/병합 연산이 조합된 각 주기마다 블록 재활용 비용을 최소화하는 이주/병합 순서의 거시적 최적화의 해를 발견하였으며, 실험 결과는 거시적 최적화가 단순 비용 기반 선택보다 플래시 메모리 기반 저장 장치의 성능을 더욱 향상시킬 수 있음을 보여준다.

A Crash Recovery Scheme for Log-Based File System over Flash Memory Using Shadow Paging

Dileep Kumar,Yeonseung Ryu,Minho Shin 보안공학연구지원센터(IJSEIA) 2016 International Journal of Software Engineering and Vol.10 No.1

Nowadays, NAND flash memory has become major storage in building portable information devices because of its non-volatility, shock-resistance, energy-friendly, and robust access time for read operations. One drawback of the flash memory file system is how to provide efficient roll back or crash recovery. This type of observation motivates our research on the investigation of crash recovery of flash-memory file systems. In this paper, we introduced a concept of shadow paging and presented a crash recovery scheme for log-based file systems over flash memory using shadow paging. In this paper a scheme is proposed for the crash recovery for log-based file systems over flash memory using shadow paging. We have also described the initialization and mounting of flash memory and we have given brief background on flash memory management like wear leveling, flash translation layer (FTL) and flash file system such as FAT/FAT32, ExFAT, JFFS2, LogFS and YAFFS. In addition, we have improved the Wear-Levelling of Garbage Collection Algorithms such as CATA, Greedy, and Cost Benefit by improving the flash memory device information.

패턴 테스트 가능한 NAND-형 플래시 메모리 내장 자체 테스트

황필주(Phil-Joo Hwang),김태환(Tae-Hwan Kim),김진완(Jin-Wan Kim),장훈(Hoon Chang) 대한전자공학회 2013 전자공학회논문지 Vol.50 No.6

메모리반도체산업이 성장함에 따라 수요와 공급이 큰 폭으로 증가하고 있다. 그 중 플래시 메모리가 스마트폰, 테블릿PC, SoC(System on Chip)산업에 많이 사용되고 있다. 플래시 메모리는 NOR-형 플래시 메모리와 NAND-형 플래시 메모리로 나뉜다. NOR-형 플래시 메모리는 BIST(Built-In Self Test), BISR(Built-In Self Repair), BIRA(Built-In Redundancy Analysis)등 많은 연구가 진행되었지만 NAND-형 플래시 메모리 BIST는 연구가 진행되지 않았다. 현재 NAND-형 플래시 메모리 패턴테스트는 고가의 외부 테스트 장비를 사용하여 테스트를 수행하고 있다. NAND-형 플래시 메모리에서는 블록단위로 소거, 페이지 단위로 읽기, 쓰기 동작이 가능하기 때문에 자체 내장 테스트가 존재하지 않고 외부장비에 의존하고 있다. 고가의 외부패턴 테스트 장비에 의존해서 테스트를 수행하던 NAND-형 플래시 메모리를 외부 패턴 테스트 장비 없이 패턴 테스트를 수행할 수 있도록 두 가지의 유한 상태 머신 기반 구조를 갖고 있는 BIST를 제안한다. The demand and the supply are increasing sharply in accordance with the growth of the Memory Semiconductor Industry. The Flash Memory above all is being utilized substantially in the Industry of smart phone, the tablet PC and the System on Chip (SoC). The Flash Memory is divided into the NOR-type Flash Memory and the NAND-type Flash Memory. A lot of study such as the Built-In Self Test (BIST), the Built-In Self Repair (BISR) and the Built-In Redundancy Analysis (BIRA), etc. has been progressed in the NOR-type fash Memory, the study for the Built-In Self Test of the NAND-type Flash Memory has not been progressed. At present, the pattern test of the NAND-type Flash Memory is being carried out using the outside test equipment of high price. The NAND-type Flash Memory is being depended on the outside equipment as there is no Built-In Self Test since the erasure of block unit, the reading and writing of page unit are possible in the NAND-type Flash Memory. The Built-In Self Test equipped with 2 kinds of finite state machine based structure is proposed, so as to carry out the pattern test without the outside pattern test equipment from the NAND-type Flash Memory which carried out the test dependant on the outside pattern test equipment of high price.

NAND 플래시 메모리에서 쓰기/지우기 연산을 줄이기위한 버퍼 관리 시스템

정보성(Bo-Sung Jung),이정훈(Jung-Hoon Lee) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.10

NAND 플래시 메모리는 저전력, 저렴한 가격, 그리고 대용량임에도 불구하고 페이지 단위의 쓰기 및 블록 단위의 지우기 연산은 큰 문제점을 가지고 있다. 특히 NAND 플래시 메모리 특성상 덮어쓰기가 불가능하므로 쓰기동작 후 수반되는 지우기 동작은 전체 성능저하의 원인이 된다. 기존의 NAND 플래시 메모리를 위한 SRAM 버퍼는 간단하면서도 NAND 플래시 메모리의 쓰기 동작을 효과적으로 줄여줄 수 있을 뿐 아니라 빠른 접근 시간을 보장 할 수 있다. 본 논문에서는 작은 용량의 SRAM을 이용하여 NAND 플래시 메모리의 가장 큰 오버헤드인 지우기/쓰기 동작을 효과적으로 줄일 수 있는 버퍼 관리 시스템을 제안한다. 제안된 버퍼는 큰 페칭 크기를 가지는 공간적 버퍼와 작은 페칭 크기를 가지는 시간적 버퍼인 완전연관 버퍼로 구성된다. 시간적 버퍼는 공간적 버퍼에서 참조된작은 페칭을 가지며, NAND 플래시 메모리에서 쓰기 및 지우기 수행시 시간적 버퍼내에 존재하는 같은 페이지 혹은 블록에 포함된 페칭 블록을 찾아 동시에 처리한다. 따라서 NAND 플래시 메모리에서 쓰기 및 지우기 동작을 획기적으로 줄였다. 시뮬레이션 결과에 따르면 제안된 NAND 플래시 메모리 버퍼 시스템은 2배 크기의 완전연관 버퍼에 비해 접근 실패율 관점에서는 높았지만, 쓰기 동작과 지우기 동작은 평균적으로 각각 58%, 83% 정도를 줄였으며, 결론적으로 평균 플래시 메모리 접근 시간은 약 84%의 성능 향상을 이루었다. There are the large overhead of block erase and page write operations in NAND flash memory, though it has low power consumption, cheap prices and a large storage. Due to the physical characteristics of NAND flash memory, overwrite operations are not permitted at the same location, so rewriting operation require after erase operation. it cause performance decrease of NAND flash memory. Using SRAM buffer in traditional NAND flash memory, it can not only reduce effective write operation but also guarantee fast memory access time. In this paper, we proposed the small SRAM buffer management system for reducing overhead of NAND flash memory, that is, erase and write operations. The proposed buffer system in a NAND flash memory consists of two parts, i.e., a fully associative temporal buffer with the small fetching block size and a fully associative spatial buffer with the large fetching block size. The temporal buffer have small fetching blocks that referenced from spatial buffer. When it happen write operations or erase operations in NAND flash memory, the related fetching blocks in temporal buffer include a page or a block are written in NAND flash memory at the same time. The writing and erasing counts in NAND flash memory can be reduced. According to the simulation results, although we have high miss ratios, write and erase operations can be reduced approximatively 58% and 83% respectively. Also the average memory access times are improved about 84% compared with the fully associative buffer with two sizes.

Dynamic Log Page Allocation Method for Flash Memory

송석일,길기정 한국정보기술학회 2011 JOURNAL OF ADVANCED INFORMATION TECHNOLOGY AND CON Vol.1 No.1

Due to advantages of NAND flash memory such as non-volatility, low access latency, low energy consumption, light weight, small size and shock resistance, it has become a better alternative over traditional magnetic disk drives, and has been widely used. Traditional DBMSs including mobile DBMSs may run on flash memory without any modification by using Flash Translation Layer (FTL), which emulates a random access block device to hide the characteristics of flash memory such as “erase-before-update”. However, most existing FTLs are optimized for file systems, not for DBMSs, and traditional DBMSs are not aware of them. Also, traditional DBMSs do not consider the characteristics of flash memory. In this paper, we propose a flash-conscious storage system for DBMSs that utilizes flash memory as a main storage medium, and carefully put the characteristics of flash memory into considerations. The proposed flash-conscious storage system exploits log records to avoid costly update operations. It is shown that the proposed storage system outperforms the state of the art flash-conscious DBMSs through the simulation.

낸드 플래시 메모리 상에서 쓰기 패턴 변환을 통한 효율적인 B-트리 관리

박동주(Dong-Joo Park),최해기(Haegi Choi) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.6

플래시 메모리는 하드디스크와 다른 물리적 특성을 가진다. 대표적으로 읽기연산과 쓰기연산의 비용이 다르고, 덮어쓰기(overwrite)가 불가능하여 소거연산(erase)이 선행되어야 한다. 이러한 물리적 제약을 소프트웨어적으로 보완해주기 위해서, 플래시 메모리를 사용하는 시스템은 대부분 플래시 변환 계층(Flash Translation Layer)을 사용한다. 현재까지 효율적인 FTL 기법들이 제안되었으며, 이들은 임의쓰기(random writes) 패턴보다 순차쓰기(sequential writes) 패턴에 훨씬 더 효율적으로 동작한다. 본 논문에서는 플래시 메모리 상에서 B-트리 인덱스를 효율적으로 생성, 유지하기 위한 새로운 기법을 제안한다. B-트리에 키의 삽입, 삭제, 수정 등의 연산을 수행하면 FTL에 비효율적인 임의쓰기 패턴을 많이 발생시키며, 결국 B-트리 인덱스 유지 비용이 커지게 된다. 제안하는 기법에서는 B-트리에서 발생되는 임의쓰기 패턴을 먼저 플래시 메모리의 쓰기 버퍼에 추가쓰기(append writes) 패턴으로 변환하여 저장하고, 추후이를 FTL에 효율적인 순차쓰기 패턴으로 FTL에 전달한다. 다양한 실험을 통해 제안하는 기법이 기존의 기법보다 플래시 메모리 I/O 비용 측면에서 우수하다는 것을 보인다. Flash memory has physical characteristics different from hard disk where two costs of a read and write operations differ each other and an overwrite on flash memory is impossible to be done. In order to solve these restrictions with software, storage systems equipped with flash memory deploy FTL(Flash Translation Layer) software. Several FTL algorithms have been suggested so far and most of them prefer sequential write pattern to random write pattern. In this paper, we provide a new technique to efficiently store and maintain the B-tree index on flash memory. The operations like inserts, deletes, updates of keys for the B-tree generate random writes rather than sequential writes on flash memory, leading to inefficiency to the B-tree maintenance. In our technique, we convert random writes generated by the B-tree into sequential writes and then store them to the write-buffer on flash memory. If the buffer is full later, some sequential writes in the buffer will be issued to FTL. Our diverse experimental results show that our technique outperforms the existing ones with respect to the I/O cost of flash memory.

RAID 기반 플래시 저장장치를 위한 수명 인지 신뢰성 향상 기법

이세환(Sehwan Lee),이빛나(Bitna Lee),고건(Kern Koh),반효경(Hyokyung Bahn) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.4

플래시 메모리 기반 저장 장치는 저전력 고성능의 장점과 더불어 용량이 점차 증가하면서, 서버 시스템에 이르기까지 채용될 것으로 전망되고 있다. 그와 함께 플래시 메모리의 신뢰성 문제 역시 점차 중요해지고 있다. 각 플래시 블록에 허용된 쓰기/삭제 횟수는 제한되어 있으며, 특히 MLC 플래시 메모리의 경우는 그 횟수가 10,000회 이하이다. 또한 플래시 메모리의 쓰기/삭제 횟수가 증가함에 따라 비트에러 발생률이 급격하게 증가한다. 이러한 문제를 해결하기 위해, 본 논문에서는 RAID 기반의 플래시 저장장치를 위한 수명 기반 신뢰성 관리 기법을 제안한다. 첫째, 제안하는 기법은 쓰기/삭제 횟수 증가에 따라 플래시 메모리의 에러 발생률이 함께 증가하는 문제를 해결하기 위하여 스트라이핑 그룹의 크기를 동적으로 관리한다. 둘째, 제안하는 기법은 플래시 메모리의 특성을 고려한 로그 블록 FTL 기법을 이용한다. 이것은 데이터 영역과 로그 영역이 서로 다른 쓰기 패턴을 갖는 특징을 활용하여 각 영역에 대하여 서로 다른 신뢰성 정책을 적용하는 것이다. 셋째, 제안하는 기법은 임시로 패리티 블록을 저장하는 소량의 SCM을 사용한다. 이는 빈번한 패리티 업데이트가 즉시 플래시 메모리에 적용되지 않도록 함으로써 플래시 메모리의 수명을 연장시킨다. 실험 결과에서 제안하는 기법은 기존의 RAID-5에 비해 적은 공간 오버헤드와 높은 신뢰성을 보이면서 입출력 성능은 패리티 블록을 사용하지 않는 RAID-0과 대등한 성능을 보였다. Due to the ever-growing capacity of flash memory along with its good properties such as low-power consumption and high performance, flash-based SSDs (solid state disks) are anticipated to be used in the storage of high-end server systems. However, the reliability problem of flash devices is becoming increasingly serious. The number of P/E (program/erase) cycles allowed to each flash block is too small, especially less than 10,000 for MLC (multi-level cell) flash memory. Furthermore, the bit error rate of flash memory becomes rapidly high as the number of P/E cycles increases. To relieve these problems, we present a lifespan-aware reliability scheme, which adopts RAID technologies together with ECCs (error correction codes). First, our scheme dynamically manages the size of striping group to cope with the increasing error rates of flash memory as the number of P/E cycles increases. Second, we use a device-aware log block mapping scheme, which uses different reliability policies for data blocks and log blocks by taking advantage of the characteristics of each block type. Third, we use small amount of storage class memory (SCM) to save parity blocks temporarily. By absorbing frequent updates of parity into SCM, we can extend the lifespan of flash memory. Simulation experiments show that our scheme obtains high reliability with minimum space overhead as well as improved I/O performances compared to traditional RAID-5.