March 알고리즘, 메모리 셀을 순서대로 읽고 쓰는 이유

아파트 한 동의 모든 집이 무사한지 확인해야 한다고 해 보죠. 101호부터 차례로 문을 두드리고, 꼭대기 층에 닿으면 이번에는 거꾸로 내려오며 다시 두드립니다. 한 집 문을 두드렸을 때 옆집에서 불이 켜지는지, 호수 표시가 엉뚱한 집에 달려 있지는 않은지도 이 순서 덕분에 드러나죠.

메모리 테스트에서 쓰는 March 알고리즘이 바로 이런 방식입니다. 수십억 개의 셀을 정해진 방향으로 훑으며 읽고 쓰기를 반복해, 셀 하나의 고장뿐 아니라 이웃 셀 사이의 간섭과 주소 오류까지 짧은 시간에 잡아내죠. 이 글에서는 메모리 결함 모델부터 March 표기법, 대표 알고리즘인 March C-의 동작까지 차례로 정리합니다.

메모리 테스트가 따로 필요한 이유

메모리는 같은 모양의 셀이 바둑판처럼 촘촘히 늘어선 구조입니다. 셀이 작고 빽빽하다 보니 이웃 셀끼리 영향을 주고받는 결함이 생기기 쉽고, 셀을 찾아가는 주소 해석 회로의 결함도 따로 고려해야 하죠.

그래서 메모리는 로직 회로와 다른 방식으로 시험합니다. 로직 회로가 게이트 단위의 결함을 가정해 패턴을 자동으로 만든다면, 메모리는 셀 배열의 규칙성을 이용해 알고리즘 패턴(Algorithmic Pattern)으로 시험하죠. 셀 수가 N개일 때 연산 횟수가 N에 비례하는지, N²에 비례하는지가 테스트 시간을 좌우합니다.

메모리 결함 모델 네 가지

고착 결함(SAF, Stuck-at Fault)은 셀 값이 0이나 1에 붙어 바뀌지 않는 결함입니다. 전이 결함(TF, Transition Fault)은 0에서 1, 또는 1에서 0 중 한쪽 방향으로만 바뀌지 않는 결함이죠. 둘 다 셀 하나만 보면 찾을 수 있습니다.

결합 결함(CF, Coupling Fault)은 한 셀(공격 셀)에 쓰거나 값이 바뀔 때 다른 셀(피해 셀)의 값이 따라 변하는 결함입니다. 피해 셀 값을 뒤집는 반전형(CFin), 특정 값으로 만들어 버리는 고정형(CFid), 공격 셀이 특정 상태일 때 피해 셀이 영향을 받는 상태형(CFst)으로 나누죠.

주소 디코더 결함(AF, Address Decoder Fault)은 어떤 주소가 아무 셀도 가리키지 않거나, 여러 셀을 동시에 가리키거나, 한 셀이 여러 주소로 접근되는 결함입니다. 흔히 모든 셀에 0과 1을 한 번씩 써 보고 읽으면 메모리 시험은 충분하다고 생각하지만, 이 방법으로는 결합 결함과 주소 디코더 결함을 놓치기 쉽습니다.

March 알고리즘의 표기법

March 알고리즘은 몇 개의 March 요소(March Element)로 이루어집니다. 하나의 요소는 모든 주소를 정해진 방향으로 한 번 훑으면서, 각 주소에서 정해진 읽기와 쓰기를 순서대로 마치고 다음 주소로 넘어가는 동작이죠.

핵심은 한 주소에서 읽기와 쓰기를 묶어 처리한 뒤 다음 주소로 넘어간다는 점입니다. 덕분에 지금 쓰는 셀보다 주소가 큰 셀과 작은 셀이 서로 다른 값을 들고 있는 순간이 생기고, 이 상태가 셀 사이의 간섭을 드러내는 무대가 되죠.

March C- 한 단계씩 따라가기

현장에서 많이 쓰이는 March C-는 다음 여섯 요소로 이루어집니다. 요소마다 셀당 연산 수를 더하면 1+2+2+2+2+1 = 10이므로, 셀이 N개일 때 전체 연산은 10N이죠.

고착 결함은 간단히 잡힙니다. 2단계에서 모든 셀이 0으로 읽히는지, 3단계에서 1로 읽히는지를 보기 때문이죠. 전이 결함도 마찬가지로, 2단계에서 쓴 1(0→1 전이)을 3단계에서 읽고, 3단계에서 쓴 0(1→0 전이)을 4단계에서 읽어 확인합니다.

결합 결함에서 방향이 중요해집니다. 2단계에서 i번 셀에 1을 쓰는 순간, 주소가 더 큰 셀들은 아직 0이고 곧 이 단계에서 읽히죠. 그래서 주소가 작은 공격 셀이 큰 피해 셀을 건드리는 경우는 오름차순 요소에서 드러나고, 반대로 주소가 큰 공격 셀이 작은 피해 셀을 건드리는 경우는 4·5단계의 내림차순 요소에서 드러납니다.

주소 디코더 결함은 오름차순에서 ⇑(r0,…,w1), 내림차순에서 ⇓(r1,…,w0) 형태의 요소가 함께 있을 때 잡힌다고 알려져 있고, March C-에는 2단계와 5단계가 이 조건을 채웁니다. 두 주소가 한 셀을 가리키면 한쪽에서 쓴 값이 다른 쪽에서 예상과 다르게 읽히기 때문이죠. 이렇게 March C-는 10N이라는 짧은 연산으로 SAF, TF, AF와 주요 결합 결함을 함께 다룹니다.

체커보드, 워킹, 갤로핑 패턴

체커보드(Checkerboard) 패턴은 바둑판처럼 이웃 셀에 0과 1을 엇갈려 쓰고 읽습니다. 연산이 4N 정도로 가볍고, 이웃 셀 사이의 누설이나 단락을 보기에 좋지만, 주소 디코더 결함은 잘 잡지 못하죠.

워킹(Walking) 1/0은 배경을 0으로 채운 뒤 1 하나를 셀마다 옮겨 가며 나머지 셀을 모두 읽고, 갤로핑(Galloping, GALPAT)은 기준 셀과 다른 셀을 번갈아 읽어 셀 쌍 사이의 영향을 촘촘히 봅니다. 결함 검출력은 뛰어나지만 연산이 N²에 비례하죠.

N²가 왜 문제인지는 숫자로 보면 분명합니다. 셀이 2³⁰개(약 10억 7천만 개)인 메모리에 연산 하나당 1 ns를 가정하면, 10N은 약 11초지만 N²는 약 1.15×10⁹초, 그러니까 30년이 넘는 시간이 걸리죠. 그래서 대용량 메모리의 양산 테스트는 March 알고리즘처럼 N에 비례하는 패턴을 중심으로 짜고, N² 패턴은 작은 영역이나 불량 분석에만 제한적으로 씁니다.

현장에서 March 알고리즘이 쓰이는 곳

메모리 전용 테스트 장비에는 주소와 데이터를 규칙에 따라 만들어 내는 APG(Algorithmic Pattern Generator)가 들어 있어, March 같은 알고리즘을 저장된 패턴 없이 실시간으로 생성합니다. SoC 안에 들어간 SRAM처럼 바깥에서 직접 접근하기 어려운 메모리는 칩 내부의 MBIST 회로가 March 알고리즘을 직접 실행하죠.

테스트 결과는 수율과 바로 연결됩니다. 어느 행과 열에서 실패가 났는지 기록한 실패 지도를 바탕으로, 불량 셀이 있는 행이나 열을 예비 셀로 바꾸는 리페어(Repair)를 하기 때문이죠. 또 실제 DRAM 테스트는 March 패턴에 데이터 유지 시간, 리프레시, 인접 행 간섭 같은 제품 특유의 조건을 더해 구성합니다.

메모리 테스트 패턴 비교 표

구분	연산 수	잘 잡는 결함	한계
체커보드	약 4N	이웃 셀 단락, 누설	주소 디코더 결함에 약함
MATS+	5N	SAF, AF	결합 결함 검출이 제한적
March C-	10N	SAF, TF, AF, 주요 결합 결함	패턴 의존 결함 일부는 놓침
워킹 1/0	N²에 비례	셀 간 간섭 전반	대용량에서 시간이 비현실적
갤로핑(GALPAT)	N²에 비례	셀 쌍 사이의 영향 전반	대용량에서 시간이 비현실적

핵심 정리

메모리는 셀 하나의 고착·전이 결함뿐 아니라 셀 사이의 결합 결함과 주소 디코더 결함을 함께 시험해야 합니다. March 알고리즘은 주소를 정해진 방향으로 훑으며 주소마다 읽기와 쓰기를 묶어 처리하는 방식으로, 대표 알고리즘인 March C-는 10N 연산으로 이 결함들을 폭넓게 잡아내죠. 연산이 N²에 비례하는 패턴은 검출력이 높아도 대용량 양산 테스트에는 맞지 않습니다.

아파트를 한 번은 올라가며, 한 번은 내려가며 두드려야 위층과 아래층의 반응을 모두 볼 수 있듯, 방향을 바꾸는 데에는 분명한 이유가 있습니다. 새로운 March 변형을 만나면 요소마다 무엇을 읽고 무엇을 바꾸는지, 그때 앞뒤 주소의 셀은 어떤 값을 들고 있는지를 따져 보면 그 알고리즘이 노리는 결함이 보입니다.

면접 대비 질문