조건문의 선택되지 않은 경로를 기다리면 생기는 일
조건문의 두 경로를 회로로 만들어 놓았는데 결과가 영원히 나오지 않는다. 양쪽 계산기는 멀쩡하고 각 계산의 답도 맞는다. 원인은 결과를 모으는 지점이 선택되지 않은 경로까지 기다리는 데 있을 수 있다. Handshake IR을 읽을 때 값의 계산식만 보면 놓치는 문제다. 어떤 경로에 데이터가 실제 도착하는지까지 프로그램의 의미에 포함되어 있다.
Handshake IR은 데이터 흐름을 연산과 채널로 표현한다. 값이 전송되었다는 사건을 토큰이라고 생각하면 편하다. 숫자 0을 가진 토큰도 정상적인 데이터이며, 토큰이 없다는 상태와 구분된다. 제어만 전하는 토큰은 수치 계산에 쓰이지 않더라도 어떤 작업을 실행해도 되는지 결정한다. 이 차이가 조건문을 회로로 바꿀 때 특히 중요해진다.
다음 식을 생각해 보자. 입력 범위는 작은 정수로 제한해 오버플로 문제를 제외하고, 우선 한 입력의 처리가 끝난 다음 다음 입력을 받는다고 하자.
if x > 0: y = x + 1
else: y = 2*x
x=10이면 양수 경로로 10이 전달되어 11이 나온다. 음수 경로에 계산용 10을 보낼 이유는 없다. x=-3이면 반대로 음수 경로에서 -6이 나온다. CIRCT의 handshake.cond_br는 조건에 따라 데이터 입력을 두 출력 중 하나로 전달한다. 조건이 거짓인 쪽에 값 0을 보내라는 뜻은 아니다. CIRCT Handshake, handshake.cond_br
이제 두 경로를 다시 모으는 회로를 고른다. 모든 입력이 도착해야 출력하는 join을 붙이면, 위의 단일 입력 처리에서는 문제가 생긴다. 10의 실행은 양수 경로에만 토큰을 보냈으므로 음수 경로의 토큰은 끝내 오지 않는다. 두 토큰을 모두 기다리는 규칙을 쓰면 조건문의 결과가 아니라 병렬 작업 두 개의 완료를 기다리게 된다.
CIRCT에서 join은 모든 입력의 가용성을 기다리는 제어 동기화 연산이고, merge는 입력 중 하나를 전달하는 합류 연산이다. 둘은 선의 개수만 비슷할 뿐 도착에 대한 조건이 다르다. 분기에서 하나를 골랐다면 합류에서도 그 실행이 보낸 하나의 결과로 완료할 수 있어야 한다. CIRCT Handshake, handshake.join·handshake.merge
다만 merge만 붙이면 모든 조건문 문제가 끝난다고 생각할 수는 없다. 여러 입력의 실행을 겹치면 서로 다른 경로의 결과가 동시에 존재할 수 있기 때문이다. 가상으로 양수 경로의 계산 지연을 3, 음수 경로의 지연을 1이라는 시간 단위로 정해 보자. A의 x=10은 시간 0에 시작해 3에 11을 만든다. B의 x=-3은 시간 1에 시작해 2에 -6을 만든다. 먼저 들어온 A보다 B의 결과가 먼저 도착한다.
아무 준비된 입력이나 받을 수 있는 합류 지점은 -6, 11 순서로 내보낼 수 있다. 시스템이 입력 순서대로 11, -6을 요구한다면 값 두 개가 모두 맞아도 계약을 어긴다. 이 예제의 시간은 특정 Handshake 합성 결과가 아니라, 경로 지연과 출력 순서가 별개의 조건임을 드러내는 가정이다. 실제 변환은 원래 프로그램의 제어 순서와 실행 간 상관관계를 보존해야 한다.
CIRCT의 control_merge는 전달한 입력과 함께 그 입력의 번호를 내보낸다. 같은 블록의 mux는 이 번호에 맞는 데이터 입력을 선택한다. 이 연결은 제어가 고른 선행 블록과 값이 온 선행 블록을 맞추기 위한 장치다. 일반 merge의 비결정적인 선택과 구별해서 읽어야 한다. 또한 그 입력 번호 하나가 시스템 전체의 모든 실행 순서를 자동으로 복구하는 것은 아니다. 실행을 얼마나 겹칠지와 외부에서 어떤 순서를 요구하는지는 별도 계약이다. CIRCT Handshake, handshake.control_merge·handshake.mux
한 입력 값을 여러 연산에서 쓰는 경우도 같은 관점이 필요하다. 분기는 한 경로를 고르지만, 복제는 여러 사용처에 같은 실행의 값을 전달해야 한다. x를 조건 검사와 산술 계산에 함께 쓴다고 해서 한 사용처가 값을 읽은 뒤 다른 사용처 몫까지 사라지면 안 된다. 반대로 복제된 토큰들을 조건문의 두 결과로 오해하면 선택되지 않은 계산까지 실행시키는 구조를 만들 수 있다.
채널이 잠시 막히는 것도 오류와 구별해야 한다. 아래쪽이 결과를 받지 못하면 앞쪽에서 전송을 기다릴 수 있다. 이것이 정상적인 backpressure인지, 서로 없는 토큰을 기다리는 교착인지 알려면 각 실행의 토큰을 따라가야 한다. invalid 상태에서 데이터 선에 보이는 숫자만으로 이미 계산이 도착했다고 판단할 수는 없다.
Handshake IR에서 조건문을 이해하는 핵심은 질문을 두 번 하는 데 있다. 이 실행은 어느 경로에 토큰을 보냈는가? 그 결과를 받을 연산은 어떤 토큰을 요구하는가? 여기에 실행 간 순서까지 붙이면, 산술식은 맞는데 회로가 멈추거나 결과가 뒤바뀌는 이유를 찾을 수 있다. 제어 흐름을 데이터 흐름으로 옮기는 일은 선을 잇는 작업과 함께 도착 조건을 정하는 작업이다.