Parallel Scan 알고리즘을 통한 괄호 매칭 작업의 O(log n) 시간 복잡도 달성

Context

기존의 괄호 매칭 알고리즘은 순차적 Stack 구조에 의존하여 데이터 크기에 비례하는 O(n)의 처리 시간이 소요됨. 대규모 데이터셋 처리 시 단일 스레드의 처리 속도 한계로 인한 병목 현상이 발생함.

Technical Solution

• 데이터를 작은 블록으로 분할하여 독립적으로 처리하는 Parallel Scan 접근 방식 채택
• 각 블록 내의 미매칭 괄호 쌍을 계산하여 요약 정보인 'Net Balance' 추출
• Prefix Sum 기반의 Scan 연산을 적용하여 블록 간의 괄호 상태를 병렬적으로 전파
• 분산된 부분 결과를 최종적으로 병합하여 전체 문자열의 유효성을 검증하는 계층적 구조 설계
• 메모리 접근 최적화를 통해 캐시 미스를 줄이고 SIMD 명령어를 활용한 연산 가속화 구현

Key Takeaway

순차적 의존성이 강한 알고리즘이라도 데이터의 연산 성질을 분석하여 결합 법칙(Associativity)을 찾아내면 병렬 처리가 가능함.