bitmap table

우리는 흔히 bitmap table과 같이 특정한 범위의 값을 bit string으로 표현합니다. 너무나 흔히 쓰이는 것이기 때문에 좀 지루하시긴 하겠지만 일단 퀴즈가 나가기 전에 이 퀴즈의 쓰임새부터 설명 하는 것이 맞을 것이라 생각하여 간단하게 bitmap table 또는 bit string의 표현예를 아래 그림과 같이 들었습니다.
이러한 bit string들은 많은 곳에서 유용하게 쓰입니다. 가장 흔한 방법은 0과 1로써 유효성을 표현하여 큰 사이즈의 데이터를 작게 표현하는 방법입니다. 예를 들어서 캐시나 스토리지등에서 현재 DRAM또는 레지스터에 있는 정보가 유효한지를 나타내기 쓰입니다. 4Byte짜리 값은 총 32개의 Entry 정보 유효성을 표시 할 수 있습니다.

위의 그림에서는 유효한 Entry가 앞에서 6번째부터 3개입니다. 이러한 예제 말고도 우리는 이러한 bit string을 프로토콜을 표현할 때도 사용합니다. 스토리지등에서 한개의 기본 연산 Entry가 512 byte이므로 4byte짜리 unsigned int타입의 변수 하나는 16 KByte 크기의 스냅샷을 생성 할 수 있습니다. 우리가 일반적으로 128GByte의 하드를 쓰고 있지요? 그러면 이 하드에 대한 스냅샷은 8Mbyte 사이즈를 가지는 배열, 즉 unsigned int타입의 2만개면 충분한 것이지요.
 8Mbyte 사이즈의 배열 하나로 128GByte를 관리 하지만 실제 특정 섹터에 값이 존재 하는지 아닌지를 파악하기 위해서는 bit 하나 하나를 다 뒤져야 합니다. 당연히 알고리즘에 따라 상당한 속도 차이를 가지게 되겠지요.

Bit string을 쓰면서 흔하게 겪게 되는 몇 가지 연산

그러면 이러한 bit string을 분석할 때는 어떠한 방법을 쓰겠습니까? 대부분 처음부터 loop를 돌면서 하나씩 정보들을 찾아가게 됩니다. 4byte로 구성된 bit를 모두 loop하기 위해서는 32번의 iteration이 필요하겠지요. 그런데 이런 bit string을 쓰면서 우리는 몇 가지 흔한 문제를 접하게 됩니다. 아래는 unsigned int 타입의 변수 하나를 기준으로 그 안에서의 동작을 의미합니다. 예를 들어 1번의 경우는 unsigned int 타입의 변수 안에서 값이 1인 bit인 총 갯수를 이야기 하는 것이지요.

1. 1 bit의 총 개수
2. 0bit의 총 개수
3. MSB 부터 처음 1이 나타 날 때 까지의 0의 총 개수
4. LSB부터 MSB로 가면서 처음 1이 나타낼 때 까지의 0의 총 개수.

1,2번의 경우 32번 루프를 돌면서 1일 때를 찾으면 몇 개의 1이 있는지 알 수 있겠죠. 하지만 좀 더 효율적으로 하기 위해서 실제 32Byte에서 1의 개수가 존재 하는 만큼만 비교 연산(time complexity of basic unit)을 하는 방법은 어떤 것이 있을까요. 이것이 첫 번째 Quiz입니다. 매번 루프를 도는 것이 결국 O(n) 수준 이기 때문에 별 것 아닐 것이라 생각 할 수 있지만 캐시와 같은 모듈이 매번 자신이 가지고 있는 캐시 중 유효한 메모리 세그먼트의 개수를 파악해야 한다면 그 오버헤드는 정말 존재하는 크기때문에 1의 개수만큼 Iteration만큼 도는 것이 유리할 것입니다.

Leading Zero Counter and Tailing Zero Counter

정말 내고 싶은 Quiz는 3번과 4번입니다. 우리는 일반적으로 3번을 하나의 Instruction으로 해결 할 수 있습니다. 대부분의 MCU들은 LZC와 같은 Leading Zero Counter 인스트럭션을 제공합니다. IBM계열의 경우도 cntlzd라는 이름으로 double word까지 3번의 경우에 대한 0을 인스럭션 한번에 개수를 return해줍니다. 이 것은 inline으로 선언하여 어셈블러상에서 O(1) 시간 안에 해결하게 해줍니다.
 그런데 4번과 같이 Tailing Zero Counter의 경우는 어떻게 해야 할까요. 이 또한 루프를 32번 돌지 않고 몇 개의 인스트럭션 만으로 해결 하고 싶은데 대부분 LZC만 제공하고 4번의 경우는 제공을 하지 않습니다. 이것이 두 번째 Quiz입니다.

Quiz 정리

1. Bit string에서 특정 비트의 값이 몇 개나 존재 하는지를 알아내는 데 있어서 O(n)이 아니라 O(m)의 시간 안에 찾아내는 방법을 설명하세요(단 m은 특정한 값을 가진 bit수)
2. Tailing Zero Counter를 LZC를 사용하여 O(1)에 가깝게 구현하세요.

두 개는 모두 실무작업 때 자주 사용할 수 있는 간단한 연산입니다. 해답을 찾으신 후배님들은 덧글 달아주세요. 기간은 9월 말까지. 해답을 찾으신 후배님들은 제가 저녁 식사 및 술을 Treat합니다.(메모리사업부 제외)

부연 설명