딥러닝 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. 신경망 구조를 DAG(Directed Acyclic Graph)로 표현하고 연산 순서를 결정하는 토폴로지컬 정렬을 구현해야 합니다. 특히 ResNet이나 DenseNet처럼 skip connection이 많은 복잡한 네트워크에서 메모리 효율적인 연산 스케줄링을 위해 어떤 알고리즘 접근법을 사용하시겠습니까? Kahn 알고리즘과 DFS 기반 접근의 차이점과 각각의 시간복잡도, 그리고 중간 텐서의 생명주기 관리를 위한 최적화 전략을 설명해주세요.
연산 그래프의 위상 정렬 알고리즘과 메모리 재사용을 위한 참조 카운팅을 함께 고려해보세요.
Kahn 알고리즘은 진입 차수(in-degree)를 활용한 BFS 기반으로 O(V+E) 시간복잡도를 가지며, 큐를 사용해 레벨별 병렬 실행 가능한 노드를 식별하기 용이합니다. DFS 기반 접근은 재귀 스택을 활용하며 역순으로 정렬 결과를 얻고, 구현이 간결하지만 스택 오버플로우 위험이 있습니다. 메모리 효율적인 스케줄링을 위해서는 각 노드의 참조 카운트를 추적하여 더 이상 필요 없는 중간 텐서를 즉시 해제하는 전략이 필요합니다. Skip connection이 많은 경우 Kahn 알고리즘에서 우선순위 큐를 사용해 메모리 압력이 낮은 순서대로 노드를 선택하는 휴리스틱을 적용할 수 있습니다. 실무에서는 gradient checkpointing과 결합하여 forward pass에서 일부 중간 결과만 저장하고 backward에서 재계산하는 방식으로 메모리-연산 트레이드오프를 조절합니다.
- • Kahn 알고리즘(BFS)과 DFS 기반 토폴로지컬 정렬의 시간복잡도 O(V+E)
- • 참조 카운팅을 통한 중간 텐서 생명주기 관리
- • 우선순위 큐를 활용한 메모리 효율적 스케줄링 휴리스틱
- • Gradient checkpointing과의 결합을 통한 메모리-연산 트레이드오프
PyTorch나 TensorFlow의 autograd 엔진에서 연산 그래프를 구성하고 역전파 순서를 결정할 때 핵심적으로 사용됩니다.
동적으로 구조가 변하는 Dynamic Computation Graph(PyTorch 스타일)에서는 정적 그래프(TensorFlow 1.x 스타일) 대비 어떤 추가적인 오버헤드가 발생하며, 이를 최소화하기 위한 JIT 컴파일 전략은 무엇인가요?
Q. Transformer 모델의 Self-Attention 메커니즘에서 시퀀스 길이 N에 대해 O(N^2)의 메모리와 연산 복잡도가 발생합니다. Long sequence를 처리하기 위해 Sparse Attention이나 Sliding Window Attention을 구현할 때, 어떤 알고리즘 패턴과 자료구조를 사용하여 복잡도를 O(N*sqrt(N)) 또는 O(N*log(N))으로 줄일 수 있는지 설명해주세요. 특히 Dynamic Programming을 활용한 최적화 방법과 캐싱 전략을 포함해서 답변해주세요.
Attention 패턴의 희소성(sparsity)을 활용한 블록 단위 처리와 중간 결과 재사용을 고려해보세요.
Sparse Attention에서는 전체 N×N 행렬 대신 특정 패턴(strided, fixed, local)만 계산하여 복잡도를 줄입니다. Sliding Window 방식은 각 토큰이 반경 k 이내의 토큰만 참조하여 O(N*k)로 선형화할 수 있으며, 이때 희소 행렬 자료구조(CSR, COO)를 사용합니다. Longformer나 BigBird 스타일의 블록 단위 Attention은 sqrt(N) 크기의 블록으로 나누고 블록 내부와 global token만 계산하여 O(N*sqrt(N))을 달성합니다. Dynamic Programming 관점에서는 이전 레이어나 시간 스텝의 attention score를 캐싱하고 incremental하게 업데이트하는 KV-cache 전략을 사용하며, 이는 특히 autoregressive 생성에서 중복 계산을 제거합니다. Flash Attention처럼 타일링 기법으로 블록을 SRAM에 올려 처리하고 중간 결과를 재사용하면 IO 복잡도도 크게 개선됩니다.
- • Sparse Attention 패턴을 통한 O(N^2)에서 O(N*k) 또는 O(N*sqrt(N))으로 복잡도 감소
- • 희소 행렬 자료구조(CSR, COO) 활용
- • KV-cache를 통한 incremental computation과 중복 계산 제거
- • 타일링과 블록 단위 처리로 메모리 계층 최적화
GPT, BERT 등 대규모 언어모델에서 긴 문서나 컨텍스트를 처리할 때 메모리 제약을 극복하기 위해 필수적으로 적용됩니다.
Multi-Head Attention에서 여러 헤드를 병렬 처리할 때 GPU 메모리 대역폭과 연산 유닛 활용률을 최대화하기 위한 커널 퓨전(kernel fusion) 전략은 무엇인가요?
Q. 대규모 임베딩 테이블(수억 개의 벡터)에서 Nearest Neighbor Search를 수행하는 추천 시스템을 구축할 때, Brute Force O(N*d) 대신 사용할 수 있는 근사 알고리즘들(LSH, HNSW, IVF)의 원리와 시간복잡도를 비교 설명해주세요. 각 알고리즘의 Recall-Latency 트레이드오프와 인덱스 구축 비용, 그리고 실시간 업데이트가 필요한 상황에서의 적합성을 논해주세요.
공간 분할, 그래프 기반 탐색, 해시 기반 버킷팅의 세 가지 접근법을 각각 생각해보세요.
LSH(Locality Sensitive Hashing)는 유사한 벡터를 같은 해시 버킷에 매핑하여 O(d) 해시 계산 후 버킷 내 O(k) 비교로 검색하며, 인덱스 구축이 빠르고 실시간 업데이트가 용이하지만 고차원에서 recall이 낮습니다. HNSW(Hierarchical Navigable Small World)는 계층적 그래프 구조로 O(log(N))의 탐색 복잡도를 가지며 높은 recall과 낮은 latency를 제공하지만, 그래프 구축에 O(N*log(N)*d) 비용이 들고 업데이트 시 그래프 재구성이 필요합니다. IVF(Inverted File Index)는 k-means로 공간을 분할하여 O(sqrt(N))개 클러스터 중 일부만 탐색하며, 클러스터 수와 probe 수로 recall-latency를 조절할 수 있고 Product Quantization과 결합하여 메모리를 크게 절약할 수 있습니다. 실시간 업데이트가 빈번하면 LSH나 온라인 클러스터링이 가능한 IVF를, 정적 데이터에서 최고 성능이 필요하면 HNSW를 선택합니다.
- • LSH는 O(d+k) 검색으로 빠른 업데이트 지원하나 고차원에서 recall 저하
- • HNSW는 O(log(N)) 탐색과 높은 recall 제공하나 구축 비용과 업데이트 복잡도 높음
- • IVF는 공간 분할로 O(sqrt(N)) 복잡도, PQ와 결합하여 메모리 효율적
- • Recall-Latency-Update 트레이드오프에 따른 알고리즘 선택
YouTube 추천, Pinterest 이미지 검색, Spotify 음악 추천 등에서 수억 개의 아이템 중 사용자 쿼리와 유사한 항목을 밀리초 내에 찾을 때 사용됩니다.
벡터 차원이 수천 차원일 때 발생하는 Curse of Dimensionality 문제를 완화하기 위해 검색 전에 적용할 수 있는 차원 축소 기법과 그 영향은 무엇인가요?
Q. 대규모 배치 학습에서 Batch Normalization의 통계량(평균, 분산)을 계산할 때, 단일 GPU에서는 O(N)으로 간단하지만 여러 GPU에 데이터가 분산된 경우 효율적인 병렬 알고리즘이 필요합니다. Welford's online algorithm과 parallel reduction을 결합하여 수치 안정성을 유지하면서 O(log(P)) 통신 복잡도로 구현하는 방법을 설명해주세요. 특히 분산 환경에서 floating point 오차 누적을 최소화하는 전략을 포함해주세요.
각 GPU에서 로컬 통계량을 먼저 계산한 후 트리 구조로 병합하는 과정에서 수치 안정성을 고려해야 합니다.
Welford's online algorithm은 데이터를 한 번에 하나씩 처리하면서 평균과 분산을 수치 안정적으로 업데이트하는 O(N) 알고리즘으로, (현재 평균 - 새 값)의 작은 차이만 누적하여 catastrophic cancellation을 방지합니다. 분산 환경에서는 각 GPU가 로컬 배치에 대해 Welford 알고리즘으로 (count, mean, M2)를 계산한 후, 이를 binary tree 구조로 병합하여 O(log(P)) 통신 라운드에 글로벌 통계량을 얻습니다. 병합 시에는 Chan의 parallel variance formula를 사용하여 두 파티션의 통계량을 결합하는데, delta = mean_B - mean_A를 계산하고 가중 평균으로 새 평균을, M2_AB = M2_A + M2_B + delta^2 * n_A * n_B / (n_A + n_B)로 새 분산을 구합니다. Floating point 오차를 최소화하기 위해 Kahan summation을 적용하거나, 더 높은 정밀도(FP64)로 통계량을 누적한 후 FP32로 변환하는 mixed precision 전략을 사용합니다. AllReduce 연산을 커스터마이즈하여 단순 합 대신 통계량 병합 연산을 직접 구현하면 통신 오버헤드를 줄일 수 있습니다.
- • Welford's algorithm으로 O(N) 단일 패스에서 수치 안정적인 평균/분산 계산
- • Chan의 parallel variance formula로 파티션 통계량을 O(log(P)) 트리 병합
- • Kahan summation이나 mixed precision으로 floating point 오차 최소화
- • 커스텀 AllReduce 연산으로 통신 효율성 개선
ImageNet 같은 대규모 데이터셋을 수십 개 GPU로 학습할 때 배치 정규화의 통계량을 정확하고 빠르게 계산하는 데 필수적입니다.
Synchronized Batch Normalization 대신 Group Normalization이나 Layer Normalization을 사용하면 분산 학습에서 어떤 통신 오버헤드를 줄일 수 있으며, 모델 성능에는 어떤 영향을 주나요?
Q. Neural Architecture Search(NAS)에서 수천 개의 후보 아키텍처 중 최적을 찾을 때, 전체 학습 없이 성능을 예측하는 early stopping 전략이 필요합니다. Successive Halving과 Hyperband 알고리즘의 원리를 설명하고, 각각의 시간복잡도와 리소스 할당 전략을 비교해주세요. 특히 exploration-exploitation 트레이드오프와 비동기 병렬 실행 시 고려사항을 포함해서 답변해주세요.
제한된 리소스를 여러 후보에 분배하면서 유망하지 않은 후보를 조기에 제거하는 bandit 알고리즘의 관점에서 접근해보세요.
Successive Halving은 n개 후보를 동일 리소스(에폭)로 학습 후 상위 절반만 남기고 리소스를 배로 늘려 반복하는 방식으로, log(n) 라운드에 총 O(n*R) 리소스를 사용하며 R은 최대 리소스입니다. 초기에 많은 후보를 빠르게 평가(exploration)하지만, 초기 리소스 설정이 부적절하면 좋은 후보를 조기에 제거할 위험(exploitation 부족)이 있습니다. Hyperband는 여러 Successive Halving 브래킷을 다른 초기 리소스와 후보 수로 병렬 실행하여 이 문제를 완화하며, 총 리소스는 O(log(n)^2 * R)로 약간 증가하지만 더 robust합니다. 비동기 병렬 실행 시에는 ASHA(Asynchronous Successive Halving)처럼 워커가 유휴 상태일 때 즉시 새 후보를 할당하고, promotion 결정을 현재까지 완료된 결과만으로 동적으로 수행하여 GPU 활용률을 높입니다. Exploration-exploitation 밸런스는 초기 리소스 비율과 survival rate로 조절하며, early stopping의 신뢰도를 높이기 위해 learning curve extrapolation이나 proxy task를 함께 사용합니다.
- • Successive Halving은 log(n) 라운드로 O(n*R) 리소스에 후보 탐색
- • Hyperband는 다중 브래킷으로 초기 설정 민감도를 완화하며 O(log(n)^2 * R) 복잡도
- • ASHA로 비동기 병렬 실행 시 GPU 활용률 극대화
- • Exploration-exploitation 트레이드오프를 survival rate와 초기 리소스로 조절
AutoML 플랫폼에서 제한된 시간과 컴퓨팅 예산 내에서 최적의 모델 아키텍처를 찾을 때 핵심 알고리즘으로 사용됩니다.
NAS에서 아키텍처 후보 생성 자체를 최적화하는 gradient-based NAS(DARTS)와 evolutionary algorithm 기반 접근의 장단점과 계산 복잡도는 어떻게 다른가요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!