---
title: "0을 같은 비율로 건너뛰어도 PE가 기다리는 시간은 다르다"
author: "브레이브브라우저쓰자"
published_at: "2026-11-01T06:27:03.665Z"
updated_at: "2026-10-06T03:42:12.534Z"
tags: ["sparse load balancing"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/0%EC%9D%84-%EA%B0%99%EC%9D%80-%EB%B9%84%EC%9C%A8%EB%A1%9C-%EA%B1%B4%EB%84%88%EB%9B%B0%EC%96%B4%EB%8F%84-pe%EA%B0%80-%EA%B8%B0%EB%8B%A4%EB%A6%AC%EB%8A%94-%EC%8B%9C%EA%B0%84%EC%9D%80-%EB%8B%A4%EB%A5%B4%EB%8B%A4"
ai_assisted: true
---

# 0을 같은 비율로 건너뛰어도 PE가 기다리는 시간은 다르다

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/0%EC%9D%84-%EA%B0%99%EC%9D%80-%EB%B9%84%EC%9C%A8%EB%A1%9C-%EA%B1%B4%EB%84%88%EB%9B%B0%EC%96%B4%EB%8F%84-pe%EA%B0%80-%EA%B8%B0%EB%8B%A4%EB%A6%AC%EB%8A%94-%EC%8B%9C%EA%B0%84%EC%9D%80-%EB%8B%A4%EB%A5%B4%EB%8B%A4)

두 희소 작업의 0 비율이 모두 50%인데 하나는 네 cycle, 다른 하나는 여덟 cycle이 걸린다. 0을 제대로 건너뛰었어도 이런 차이가 생긴다. sparse load balancing은 남은 유효 작업이 어느 PE에 몰렸는지, 먼저 끝난 PE가 언제 다음 작업을 받을 수 있는지에 관한 문제다. 전체 비영 원소 수만으로는 끝나는 시점을 정할 수 없다.

## 다음 단계는 가장 늦은 PE를 기다릴 수 있다

가상의 PE 네 개가 각각 최대 여덟 개의 후보 곱을 맡고 있다고 하자. 각 PE는 비영 곱 하나를 한 cycle에 계산하며 0은 이미 decoding 단계에서 제거됐다고 정한다. 이번 모델에는 공급 지연이나 누산 충돌이 없다. 다음 단계는 네 PE가 현재 작업을 모두 마친 뒤 시작한다.

작업 A에서 각 PE의 유효 곱 수는 [4,4,4,4]다. 총 16개이고 모두 네 cycle에 끝난다. 작업 B는 [8,8,0,0]이다. 역시 총 16개지만 앞의 두 PE가 여덟 cycle까지 계산한다. 뒤의 두 PE는 처음부터 기다린다. 원래 후보가 총 32개이므로 두 작업의 0 비율은 똑같이 50%다.

유효 연산 자리를 시간까지 포함해 세면 A는 16/(4PE×4cycle)=100%, B는 16/(4PE×8cycle)=50%다. 0을 건너뛰는 데 성공한 양과 PE들의 진행 속도가 맞는 정도는 서로 다른 비율이다. 이 숫자는 가상 계산이며 compressed format의 실제 overhead까지 넣은 측정값은 아니다.

일반적으로 이 조건의 완료 시간은 PE별 작업 수 ni의 평균보다 `max(ni)`에 가깝다. 총량을 PE 수로 나눈 값은 균형 있게 나눌 수 있고 추가 제약이 없을 때의 하한이다. 기다리는 PE가 다른 독립 작업을 받을 수 있다면 이 barrier 모델의 결과도 달라진다.

SCNN의 원 논문은 output-channel group 경계에서 PE들이 동기화하며, 먼저 끝난 PE가 늦은 PE를 기다리는 load imbalance를 설명한다. PE 내부의 multiplier 묶음이 덜 채워지는 fragmentation도 별개의 손실로 다룬다. 이번 네 PE 예는 그 두 효과 가운데 PE 사이 대기만 분리한 것이다. [SCNN 논문, 11쪽 그림 9–10 주변 설명](https://research.nvidia.com/sites/default/files/publications/ISCA_2017_SCNN.pdf)

## 남은 작업을 나누는 데에는 출력의 소유권이 붙는다

작업 B의 16개 곱을 모든 PE가 가져갈 수 있는 큐에 넣으면, 이상적으로 네 개씩 나누어 네 cycle에 끝낼 수 있다. 그러나 각 곱이 어떤 output에 더해져야 하는지 함께 전달해야 한다. 값만 옮기고 좌표를 잃으면 빠르게 계산한 다른 답을 만든다.

한 output의 누산값을 한 PE만 소유한다면 다른 PE가 계산한 partial sum을 그곳으로 보내야 한다. 여러 PE가 같은 output을 동시에 수정한다면 합산 충돌을 처리해야 한다. bank가 같거나 같은 주소에 두 업데이트가 겹쳐 한 번에 처리하지 못하면, 균형을 개선하며 새로운 병목을 만들 수 있다.

SCNN의 compressed dataflow도 nonzero 값과 함께 좌표를 decoding하고, 곱의 결과를 대응 output 좌표의 accumulator bank로 분산한다. sparse 곱은 dense loop의 다음 순서만으로 목적지를 정할 수 없기 때문이다. 좌표 처리와 누산 경로를 포함해야 실제로 재배치 가능한 일의 단위를 정의할 수 있다. [SCNN 논문, 6쪽 3.2절](https://research.nvidia.com/sites/default/files/publications/ISCA_2017_SCNN.pdf)

## 균형의 이득에서 재분배 비용을 뺀다

앞의 큐를 만드는 데 가상 두 cycle이 추가되고, 그동안 계산과 겹치지 않는다고 정하자. B는 여덟 cycle에서 2+4=6cycle로 줄어든다. 반면 이미 균형적인 A도 같은 재분배를 거치면 네 cycle에서 여섯 cycle으로 늘어난다.

두 cycle은 특정 scheduler의 실제 비용이 아니다. 작업의 이동, index decoding과 partial sum 전달이 무료라는 가정을 드러내려는 값이다. 실제 비용이 input 준비와 겹칠 수 있으면 단순 합도 바뀐다. 조밀한 작업에서 큐 경로를 bypass하는 선택 역시 지원 여부를 확인해야 한다.

균형화 단위를 작게 하면 늦은 PE의 꼬리를 나누기 쉽지만 좌표와 큐 관리가 잦아진다. 큰 block으로 옮기면 관리가 단순해도 내부에 0이 몰린 분포를 그대로 가져갈 수 있다. block의 개수가 같다는 조건과 block 안의 유효 곱 수가 같다는 조건을 구분한다.

평균 sparsity만 기록한 benchmark는 이런 차이를 숨길 수 있다. PE별 유효 작업 수, decoding과 누산 대기, barrier에서 빈 시간을 따로 기록하면 실제 실행 시간을 설명할 수 있다. weight와 activation의 희소성이 동시에 있는 경우에도 두 0 비율만 곱해 특정 output·PE의 분포까지 확정하지 않는다.

희소 계산의 이득은 제거한 0의 개수에서 시작한다. 완료 시간을 판단하려면 남은 일을 누가 끝내는지까지 가야 한다. 작업 배분과 output 누산 계약을 함께 지키고 재분배 비용을 포함할 때, 같은 50% sparsity가 서로 다른 시간으로 나타난 이유와 균형화가 이득인 조건이 보인다.