exFAT은 FAT과 다른점이 몇가지가 있는데 그중에 대표적인것이 free cluster bitmap의 존재이다. 1bit은 곧 1cluster를 의미하기 때문에 1byte에 8개의 cluster할당 정보를 담을 수 있다.  따라서 FAT table보다는 많은 정보를 압축하여 저장할 수 있다.

그러나, cluster bitmap을 탐색하고 수정하는 것은 많은 비용을 발생시킨다. 이 논문은 이 비용 중에서도 연속된 free cluster bitmap을 효과적으로 탐색하는 알고리즘을 소개하고 있다. 

gap-search라는 방법이 그것인데, 논문에서는 이 알고리즘과 일반적인 순차탐색을 비교하면서 gap-search 알고리즘의 우수성을 증명하고 있다. 

하지만, 비교의 대상이 왜 순차탐색이냐 하는데는 의문을 갖는다. 분명 gap-search방법이 순차 탐색보다는 월등한 성능을 가져 오는 것은 사실이나, 순차탐색 보다 더 안좋은 탐색 방법이 없다는 것도 사실이기 때문이다.

free cluster를 찾는 방법은 list를 활용하는 방법도 있고, tree를 이용하는 방법도 있다. 이렇게 bitmap을 다른 자료구조로 추상화한뒤 검색하는 방법과 비교를 했더라면 하는 아쉬움이 든다.

탐색 시간을 고려 해봤을 때는 tree나 list를 이용하는 방법이 bitmap을 사용한 방법보다 우월할 것이 자명하나, 메모리 사용량이나 bitmap을 추상화하는 비용도 만만치 않기 때문에 bitmap을 그대로 사용하는 gap-search 알고리즘이 더 효과적일 수 있기 때문이다. 

아쉬움도 있었지만, gap-search 알고리즘은 정말 단순하면서도 놀라울 정도로 성능이 좋다.  정말 좋은 논문이다.


저작자 표시 비영리 변경 금지
신고
Write your message and submit

C 언어 펀더멘털

Posted 2009.06.08 09:23

문자열 상수를 정의할 때  L keyword를 스트링의 앞에 붙이면 한 문자를 wchar_t형(2byte)으로 메모리상에 잡게 된다.

sizeof("1234567890" ) = 11byte
sizeof(L"1234567890") = 22byte

그러나 L keyword는 선택적으로 붙여야 할 때가 많으므로 이를 편하게 사용하기 위해 _T 매크로를 사용한다.
_T 매크로는다음과 정의되어 있다.

#define _T(x)       __T(x)
#define __T(x)      L ## x


_T("1234567890") 라고 사용하면  L"1234567890" 로 되기를 기대하는 것이다.

하지만, 이상한 점이 있다. _T가 L ## x 로 바로 매크로로 정의하지 않고 _T는 __T로  __T는 다시 L ## x로 재정의 한다.

실제로 매크로 _T를 __T를 거치지 않고 _T를 L ## x로 바로 정의하여 사용하면 컴파일 에러가 발생한다.

왜 이런 현상이 일어나는 것일까? 

이러한 궁금증을 속 시원히 설명하는 C언어 책이 있던가?


C언어 펀더멘털은 이럴 때 필요한 책이다.

수 년간 C언어 표준만을 연구해 온 저자의 치열하고 정확한 설명을 들을 수 있다. 다소 딱딱한 주제이고, 책의 만만치 않은 무게가 약간 거부감을 주지만, 일단 펼치면 마치 소설속에 빠져 들듯이, 재미있는 C언어 표준의 세계로 들어가게 된다.

지식 노동자에게는 새로운 지식은 유희 그 자체이다. 

이런 책이 있다는 것은 이땅의 개발들에게 축복이다.

ps. 이 책은 C언어 입문자들에게는 적합하지 않습니다. 시작도 해보기 전에 좌절을 안겨줄수도 있습니다. ㅎㅎ 
저작자 표시 비영리 변경 금지
신고
Write your message and submit


MP3나 디지털 카메라, 캠코더와 같이 대용량 file을 single thread로 write하는 응용에서 좋은 선택이 될 수 있는 논문이다.

논문의 요지는

  • FAT file system의 meta data update를 어떻게 하면 file write 도중에 하지 않을 수 있을까?
  • FTL merge를 write 도중에 하지 않을 수 있을까?


에 대한 고민과 해답이다.

단, 앞서 언급했듯이 대용량 single thread라는 것을 집고 넘어가자.

1. 번에 대한 대안으로 ACPA(All Cluster Pre-Allocation) 이라는 이름으로 file create시 cluster를 미리 할당하는 것을 제시한다. 미리 FAT을 써 넣으면 write도중 meta update가 발생하지 않을테니 빠르다는 것이다.
--> ACPA 거창하게 이름까지 붙였으나,, 보통 file create후 write전에 큰용량으로 truncate하는 것은 이미 흔히 사용하는 기법이다.
2. 번에 대한 대안으로 FTL에서 Sector Reservation method라는 것을 언급하는데 이것은 지금 NAND에서는 사용될 수 없는 방법이다. 지금 생산되고 있는 NAND는 모두 large block 인데 out of place page write를 금지하고 있다. 알고리즘의 좋고 나쁘고를 떠나서 잘못된 방법이다.

써 놓은 글을 보니 이 논문에 대해 혹평을 한것 같이 보이지만, 사실 이논문은 훌륭한 논문이다.

이 논문이 던지는 시사점은


real time latency 의 중요성을 알려주었다. : 캠코더의 예를 들면 write도중 NAND에서 merge가 일어나 cache 가 flush하기 전에 다 차버렸다면 심각한 결과를 초래 할 수 있다. 하지만, merge를 유발 시킬 수 있는 operation을 미리 함으로써 어능정도 latency를 보장하려는 의도는 좋다.
FTL 과 filesystem의 상호고려한 알고리즘을 제시하였다. : 지금까지의 FTL논문이나 filesystem논문은 서로의 영향은 고려하지 못했다. 왜냐하면 filesystem은 FTL에 대해 block device이상으로 내무 알고리즘까지 고려하려는 시도가 없었다. 하지만, 이 논문은 그런 시도를 했다는 것에 대해 좋은 점수를 주고 싶다.
대용량에 특화되었다. : 보통 filesystem은 generic하게 개발한다. 왜냐하면 어떤 응용이 올지 모르기 때문이다. 하지만, 디지털 카메라나 캠코더에 한정하였다. 한정된 응용에 특화되어 최고의 성능을 낸다는 의도는 좋았다.


NAND flash가 SLC 를 넘어 2bit, 3bit 까지 영역을 넓이고 있다. 하지만, 용량 증가 대비 성능은 계속 해서 나빠지고 있다.
이러한 시도를 통해 대용량 응용에서 성능향상 시도를 해볼 수 있을 것이다.


 

신고
Write your message and submit

NAND flash는 rewrite를 하기전에는 반드시 erase를 해주어야 하고 write와 erase의 단위가 다르다는 태생적인 제약 사항이 있다.
이러한 제약사항이 FTL (Flash Translation Layer)을 만들게한 출발점이다.

이논문은 FAST FTL에서 block의 page align이 맞는 상태에서는 block안에 valid한 page가 많을 수록 cache안에서 victim으로 선정되는 것이 좋다고 판단한다.

하지만, cache의 크기가 충분히 크다는 점(8MB 이상) read/write되는 file의 크기가 대용량(block보다 큰) 이라는 전제를 붙이고 있다.

PMP와 같은 응용처럼 위 전제를 만족하는 경우 FAB은 효과가 있다. 사실 큰 file이 순서대로 write되고 update가 잘일어나지 않는 경우는 LRU는 의미가 없기 때문이다.(이때는 cache가 아예 없는 것이 최상일것이다.)

거의 대부분의 disk cache관련 논문들은 victim선정 알고리즘으로 LRU의 대안을 찾는다. 기본은 LRU이지만, 어떤 상황에서는 가중치를 부여한다던가, LRU와 다른 알고리즘을 섞는 형태가 주류인데.

이것을 뒤집어 생각해 보면 LRU는 보편적으로 가장 우수하다고 검증된 방법이고, 특정 behavior에서는 다른 알고리즘이 좋을 때도 있다는 것이다.

FAB도 마찬가지이다. PMP가 아닌 phone에서는 어떨까? 이 방법이 효과가 있을까?

cache의 알고리즘은 사용자 응용에 의존적인 알고리즘으로 분화되고 있다. 새로운 알고리즘은 요즘 NAND flash기반의 사용자 응용이 어떻게 변화하고 있느냐가 가장 중요한 key factor이다.

그렇다면 사용자 응용패턴을 어떻게 정형화 할 수 있냐는 재미있는 질문이 생긴다. 또한, 추출된 패턴이 얼마나 대표성을 갖게 되느냐도 매우 중요하다.

결국 확률의 문제이다.

신고
Write your message and submit