인터랙션 넷의 지역성, 병렬성, 선형성이 하드웨어 아키텍처 설계의 어려운 문제들을 어떻게 극복하는지 설명합니다.
우리의 새로운 범용 아키텍처의 잠재력을 이해하려면, 그 기반이 되는 계산 모델인 인터랙션 넷을 이해해야 합니다. 그래서 인터랙션 넷과 그 고유한 성질들(특히 지역성, 병렬성, 선형성), 그리고 이것들이 하드웨어 아키텍처 설계에서 가장 어려운 몇 가지 과제를 어떻게 극복하는 데 도움이 되는지를 소개하겠습니다.
인터랙션 넷은 그래프 기반의 계산 모델입니다. 인터랙션 넷은 각 노드가 하나의 주 포트와, 노드 유형에 따라 0개 이상의 보조 포트를 가지는 구조로 이루어집니다. 다음은 A 유형의 노드로, 하나의 주 포트(위쪽)와 두 개의 보조 포트(아래쪽)를 갖습니다.
인터랙션 넷은 여러 노드로 구성되며, 이들의 포트는 와이어로 연결됩니다.
두 개의 주 포트를 연결하는 와이어는 활성 쌍을 형성합니다. 그러면 그 두 노드는 서로 상호작용하여 어떤 계산을 수행합니다. 이를 위해 인터랙션 넷 시스템은 특정 유형의 두 노드가 서로 어떻게 상호작용하는지에 대한 규칙을 정의합니다.
더 큰 넷 안의 활성 쌍에 규칙을 적용하면, 활성 쌍의 두 노드는 규칙의 오른쪽 항으로 대체됩니다.
이것은 인터랙션 넷의 첫 번째 중요한 성질로 이어집니다: 지역성. 계산의 한 단계는 그래프의 아주 국소적인 부분만 바꾸며 전역적인 영향을 주지 않습니다.
지금은 인터랙션 넷이 어떻게 계산을 수행하는지 감을 잡기 위해 매우 단순한 계산에 집중해 보겠습니다. 먼저, 단항 수를 위한 노드를 도입하겠습니다. 주 포트 하나와 보조 포트가 없는 0 노드, 그리고 주 포트 하나와 보조 포트 하나를 가진 +1 노드를 사용하겠습니다.
숫자 0, 1, 2는 다음과 같이 표현하겠습니다:
덧셈부터 시작하여, 두 수를 더하기 위한 + 노드를 도입합니다.
계산을 하기 전에, + 노드가 우리의 수 노드들과 어떻게 상호작용하는지 정의해야 합니다. 이 규칙들은 산술 규칙 와 를 나타냅니다.
이 시스템을 사용하면 이제 를 계산할 수 있습니다.
결과는 예상대로 입니다.
다음으로, 와 라는 동치를 이용해 곱셈을 정의하겠습니다. 다만 첫 번째 경우에는 가 오른쪽 항에 전혀 나타나지 않고, 두 번째 경우에는 두 번 나타난다는 점에 주목하세요. 이를 모델링하려면 수를 삭제하고 복제하는 두 가지 추가 노드 유형이 필요합니다.
이제 곱셈 노드에 대한 규칙을 지정할 수 있습니다.
이것으로 를 계산할 수 있습니다.
첫 번째 상호작용 이후, 흥미로운 일이 일어납니다. 이제 인터랙션 넷 안에 두 개의 활성 쌍이 생깁니다. 게다가 이 두 활성 쌍은 서로 겹치지 않습니다. 실제로 이것은 항상 성립합니다. 노드는 주 포트를 하나만 가지므로, 단 하나의 활성 쌍에만 속할 수 있습니다. 즉, 모든 활성 쌍은 완전히 독립적이며, 어떤 순서로든 실행할 수 있고, 더 흥미롭게는 병렬로 실행할 수 있습니다.
이 두 활성 쌍을 실행한 뒤에는 세 개가 더 생기며, 이들 역시 병렬로 실행할 수 있습니다.
예상한 결과인 을 얻습니다.
이 계산들을 종이 위에서 할 때는 그래프에서 활성 쌍을 직접 찾으면 됐습니다. 하지만 인터랙션 넷을 소프트웨어나 하드웨어로 구현할 때는 그래프를 저장하고 활성 쌍을 찾는 작업이 매우 느립니다. 그래서 우리는 인터랙션 넷을 트리들로 분해합니다. 이를 위해 두 보조 포트를 연결하는 모든 링크를 끊고, 양 끝을 라벨로 대체합니다. 예시로, 곱셈 계산의 중간 단계 넷 가운데 하나에 대해 이를 해보겠습니다.
남는 것은 트리의 쌍들입니다. 인터랙션 넷의 모든 활성 쌍은 정확히 두 트리의 루트가 만나는 곳에 있습니다. 즉, 인터랙션 넷을 메모리에 트리로 효율적으로 저장할 수 있고, 동시에 넷 안의 모든 활성 쌍에도 즉시 접근할 수 있습니다.
효율적인 구현을 갖추는 것은 한 가지 문제이고, 순수한 인터랙션 넷 자체로 프로그래밍하는 것은 사실상 실용적이지 않습니다. 이를 위해 아직 언급하지 않은 세 번째 성질, 즉 선형성을 이야기해 보겠습니다. 이 성질은 어떤 것이 정확히 한 번씩만 사용된다는 사실을 가리킵니다. 실제로 우리는 수를 명시적으로 삭제하고 복제하는 전용 노드를 정의할 때 이미 이 성질이 작동하는 모습을 보았습니다. 이 성질이 흥미로운 이유는, 선형 타입 시스템을 가진 일반적인 프로그래밍 언어가 인터랙션 넷과 같은 선형 계산 모델로 완벽하게 컴파일될 수 있기 때문입니다. 특히 Rust는 소유권 개념을 통해 한 종류의 선형 타입 시스템을 대중화했습니다.
왜 정확히 Rust는 인터랙션 넷으로 쉽게 컴파일될 수 없는지에 대한 몇 가지 큰 제약은 있지만, 우리는 Rust와 유사하면서도 인터랙션 넷으로 직접 컴파일되는 언어(Vine)를 만들 수 있습니다.
이 더 나은 도구를 갖춘 상태에서, 더 큰 문제인 최장 공통 부분수열 문제를 풀어보겠습니다.
리스트의 부분수열이란 리스트에서 항목들을 골라낸 것인데, 반드시 연속적일 필요는 없습니다. 최장 공통 부분수열 문제에서는 두 개의 리스트가 입력으로 주어지고, 두 리스트가 공통으로 가지는 부분수열 중 가장 긴 것의 길이를 구하는 것이 목표입니다. 예를 들어, "Tendrils"와 "edits" 사이의 최장 공통 부분수열은 "edis"이며 길이는 4입니다.
이 문제는 동적 계획법 해법을 갖는 것으로 잘 알려져 있습니다. 첫 번째 리스트의 처음 개 원소와 두 번째 리스트의 처음 개 원소 사이의 최장 공통 부분수열의 길이를 라고 정의하면, 다음 성질을 얻습니다:
이를 통해 Vine에서 알고리즘을 구현할 수 있습니다. 우리는 병렬 계산에 관심이 있지만, 우선 두 개의 중첩 루프를 사용하는 가장 직관적인 구현부터 시작해 봅시다.
Tendrils let row = [];
for a_elem in a {
let prev_row_entry = 0;
let prev_new_entry = 0;
let new_row = [];
for b_elem in b {
let row_entry = row.pop_front().or_use(0);
let new_entry = if a_elem == b_elem {
prev_row_entry + 1
} else {
row_entry.max(prev_new_entry)
};
prev_row_entry = row_entry;
prev_new_entry = new_entry;
new_row.push_back(new_entry);
}
row = new_row;
}
row.get(b.len() - 1).or_use(0)
}```
다음으로 이 함수를 길이 200의 두 무작위 리스트에 대해 실행해 보겠습니다.
> vine run lcs.vi --breadth-first
Interactions
Total 2_993_893
Depth 10_920
Breadth 274
보시다시피 이 프로그램은 총 2,993,893번의 상호작용을 수행합니다(즉, 명령어 수입니다).
더 흥미로운 점은, 우리가 `--breadth-first` 플래그를 사용해 프로그램을 실행했다는 것입니다. 이 모드는 무한히 병렬적인 컴퓨터가 있다고 가정하고, 각 단계마다 넷 안의 모든 활성 쌍을 실행합니다. 앞서 우리가 했던 방식과 같습니다. 이것은 병렬 머신에서 얻을 수 있는 속도 향상의 매우 낙관적인 상한입니다. 이때 계산의 깊이는 프로그램이 필요로 하는 병렬 단계 수이며, 임계 경로라고도 부릅니다.
보시다시피 이것은 총 상호작용 수보다 훨씬 작습니다. 또한 총 상호작용 수를 계산 깊이로 나누면 breadth, 즉 각 단계에서 실행할 수 있는 평균 상호작용 수를 얻습니다. 이것은 프로그램이 포함하는 병렬 작업량이 얼마나 되는지에 대한 추정치입니다.
breadth가 274라는 점에 주목하세요. 즉, 각 단계에서 평균 274개의 상호작용을 병렬로 수행할 수 있다는 뜻입니다. 따라서 먼저 가장 직관적인 버전을 구현하려고 했지만, 이것이 이미 병렬 구현이었던 셈입니다!
이 병렬성이 어디서 오는지 보려면, DP 테이블의 의존 관계를 그려보겠습니다.
특히 대각선 방향의 한 단면을 따라 있는 모든 항목은 서로 독립적이므로 동시에 계산할 수 있습니다.
이를 더 확인하기 위해 입력 리스트의 길이를 2000으로 늘렸을 때 어떤 일이 일어나는지 살펴볼 수 있습니다.
Interactions
Total 296_223_905
Depth 108_142
Breadth 2_739
이 알고리즘의 전체 실행 시간이 이므로, 총 상호작용 수는 약 100배 증가합니다. 하지만 계산의 깊이는 이전 결과의 약 10배에 불과합니다. 그 이유는 DP 테이블의 주대각선에 해당하는 임계 경로가 입력 크기에 선형적으로 비례하기 때문입니다.
중요하게도 계산의 breadth는 약 10배 증가했습니다. 이는 입력 크기가 커질수록 병렬 작업량이 훨씬 많아진다는 뜻입니다.
Vine 컴파일러가 이것을 가능하게 하는 방식은 프로그램에서 병렬성을 마법처럼 추출하는 것이 아닙니다. 단지 의존 관계 정보를 하드웨어 수준(혹은 이 경우 런타임)까지 그대로 보존할 뿐입니다. 예를 들어 [옵션 가격 책정 알고리즘](https://github.com/nilscrm/quant-vi)에서도 매우 유사한 병렬성 패턴을 찾을 수 있습니다.
일반적인 컴파일러도 이미 내부적으로 이런 의존 관계를 추적하고, 최적화에 활용합니다. 하지만 그런 정보는 이후 버려지고, 전체 프로그램은 선형적인 명령어 시퀀스로 평탄화됩니다. 아이러니하게도 현대 CPU는 그다음 순서 바꿈 버퍼와 슈퍼스칼라 실행을 통해 실리콘 안에서 이 병렬성을 제한적으로 다시 추출하려고 합니다. 인터랙션 넷을 사용하면 대신 이 정보를 가장 낮은 수준까지 유지하고 활용할 수 있습니다.
### 인터랙션 넷 하드웨어
앞서 우리는 인터랙션 넷의 성질들이 하드웨어 아키텍처 설계에서 가장 어려운 문제들 일부를 극복하는 데 도움이 된다고 주장했습니다. 왜 그런지 보기 위해, 현대 아키텍처 설계의 몇 가지 과제를 살펴봅시다.
CPU의 핵심 설계 선택 중 하나는 하나의 통합 메모리 공간을 갖는 것입니다. 이것은 최근 몇 년 사이 문제가 되었습니다. 2000년대 초반 이후 단일 코어 CPU 성능이 정체되었기 때문입니다. 그 결과 멀티코어 CPU가 크게 증가했지만, 모든 프로세서가 하나의 메모리 공간에서 작업하면 모든 load 및 store 명령은 기술적으로 전역 연산이 됩니다. 물론 현대적인 캐시는 이 문제의 대부분을 숨기지만, 그 대가가 캐시 일관성 프로토콜입니다. 이런 프로토콜은 보통 확장성이 좋지 않고 코어 수를 제한합니다. 인터랙션 넷에서는 연산이 지역적이므로 코어가 관련 데이터를 로컬 SRAM에 저장할 수 있고, 이는 어떤 캐시 일관성도 필요로 하지 않습니다. 더 나아가 Rust의 타입 시스템이 가비지 컬렉터 없이 자동 메모리 관리를 가능하게 하는 것과 같은 이유로, 인터랙션 넷의 선형성은 칩 위에서의 메모리 관리도 가능하게 만듭니다. 이러한 성질 덕분에 우리는 수천 개의 코어까지 확장할 수 있습니다.
멀티코어 CPU의 또 다른 문제는 프로그래밍의 어려움입니다. 디버깅 가능성은 큰 문제이며, 경쟁 상태와 같은 완전히 새로운 부류의 문제가 발생합니다. 하지만 인터랙션 넷에서는 모든 활성 쌍이 독립적이므로 실제로 어떤 순서로든 실행될 수 있습니다. 이 성질은 합류성이라고 불리며, 어떤 순서로 실행하더라도 결과가 같다는 뜻입니다. 이는 디버깅을 단순하게 만들고 경쟁 상태 같은 문제를 제거합니다. 덕분에 Vine은 기본적으로 병렬적입니다. 프로그래머는 병렬 실행을 얻기 위해 스레드, 프로세스, CUDA 커널 등에 대해 특별히 할 일이 없습니다.
물론 CPU는 병렬성을 여러 코어에서만 얻는 것이 아닙니다. 단일 코어 내부에도 명령어 수준 병렬성이 있습니다. 그러나 CPU는 근본적으로 선형적인 명령어 시퀀스를 실행합니다. 명령어 수준 병렬성을 활용하려면 CPU는 런타임에 그 병렬성을 분석하고 추출하기 위해 상당한 전력과 다이 면적을 사용해야 합니다. 특히 더 깊은 순서 바꿈 윈도와 더 넓은 실행 파이프라인은 큰 비용을 수반하기 때문에, 이는 금방 수확 체감에 부딪힙니다. 그래서 보통 사이클당 실행 가능한 명령어 수는 최대 몇 개 수준에 그칩니다. 하드웨어가 정말로 모든 병렬성을 추출할 수 있다면, 어떤 프로그램도 여러 스레드를 필요로 하지 않을 것입니다. 단일 스레드만으로도 같은 양의 병렬성을 가질 테니까요. 인터랙션 넷은 그래프 구조로 모든 의존 관계를 직접 부호화하므로, 하드웨어는 그 병렬성을 추출하기 위해 아무 작업도 할 필요가 없습니다. 그것은 이미 바로 이용 가능한 형태로 존재합니다. 이는 코어 내부의 엄청난 복잡성과 전력 소모를 제거합니다.
더 나아가 인터랙션 넷은 모든 수준의 병렬성을 포착하는 반면, CPU는 단일 코어 내부의 매우 미세한 병렬성과, 스레드/코어를 통한 매우 거친 병렬성만 포착합니다. 그리고 후자의 경우에는 이를 관리하는 큰 비용과 코어 간 통신 및 동기화의 높은 오버헤드를 상쇄할 만큼의 이득이 있어야 합니다.
마이크로아키텍처, 메모리 시스템, 칩 인터커넥트, 컴파일 과정이 어떤 모습인지에 대한 더 자세한 내용을 알고 싶다면, [문의해 주세요](mailto:hello@tendrils.co). 그리고 [현재 채용 중인 포지션](https://tendrils.co/jobs)에도 지원해 보시기 바랍니다.