COMP90025의 두 번째 과제에서 MPI로 사전을 여러 프로세스에 나누고, Bloom filter로 통신을 줄였다. BK-tree로 32분 걸리던 작업을 2초 이내로 단축한 과정.
COMP90025는 멜버른 대학교의 병렬 및 멀티코어 컴퓨팅(Parallel and Multicore Computing) 과목이다. 이 과목에는 큰 과제가 두 개 있는데, 둘을 합치면 간단한 병렬 맞춤법 검사기가 된다. 첫 번째 과제에서는 OpenMP로 문서에서 중복 없는 단어를 모았고, 두 번째 과제에서는 MPI로 전환해 그 단어들을 사전과 대조하면서 오타와 수정 후보를 찾는다.
dictionary.txt는 정렬된 사전이고, word_list.txt는 검사할 단어 목록이다. 목록의 각 단어가 사전에 없으면, 문자 하나를 바꾸거나 삭제하거나 추가해서 가능한 후보를 모두 생성해야 한다. 그렇게 만든 새 단어 중 사전에 있는 것들이 올바른 철자 후보가 된다. 대소문자에 관한 규칙도 하나 있다. 첫 글자만 소문자로 바꾼 형태가 사전에 있으면, 그 단어도 사전에 있는 것으로 간주한다.
출력은 오타 하나당 한 줄이며, 뒤에 수정 후보를 나열한다. 예를 들면 다음과 같다.
TEXT
appel: appeal apple rappel
stap: sap snap stab step stop strap tap
출력 순서는 후보 수가 적은 것부터이며, 후보 수가 같으면 사전순으로 정렬한다.
추가 제약도 있었다. 각 프로세스는 사전의 일부만 저장할 수 있고, 프로세스마다 사전 전체를 복제해서는 안 된다. 수업에서 제공한 단일 스레드 참조 구현은 BK-tree를 사용했다. 우리가 만든 프로그램은 학교 HPC 클러스터인 Spartan에서 실행해야 했다. 평가는 코드와 보고서로 나뉘는데, 보고서 배점이 더 높아서 실험과 분석도 대충 넘길 수 없었다.
먼저 알고리즘부터 바꾸기
구현에 들어가기 전에 참조 프로그램부터 실행해 봤다. BK-tree로 사전에서 편집 거리가 1 이하인 단어를 찾는 방식이었다. 가장 큰 데이터셋은 사전에 62만 개가 넘는 단어, 검사 목록에 65만 개가 넘는 단어가 있었는데, 실행에 약 32분이 걸렸다.
내가 택한 방법은 훨씬 단순했다. 편집 거리가 1로 고정되어 있으니, 가능한 후보를 전부 만든 뒤 해시 테이블에서 하나씩 조회하면 된다. 후보를 생성하는 코드도 복잡하지 않다.
C++
std::vector<std::string> GenerateEditDistance1Candidates(const std::string& word) {
std::vector<std::string> out;
const std::string alphabet = "abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";
for (size_t i = 0; i < word.size(); ++i) // 删除
out.push_back(word.substr(0, i) + word.substr(i + 1));
for (size_t i = 0; i < word.size(); ++i) // 替换
for (char c : alphabet)
if (c != word[i]) {
std::string s = word;
s[i] = c;
out.push_back(s);
}
for (size_t i = 0; i <= word.size(); ++i) // 插入
for (char c : alphabet)
out.push_back(word.substr(0, i) + c + word.substr(i));
return out;
}
길이가 L인 단어는 후보를 약 124 × L개 만든다. 따라서 알파벳 여덟아홉 글자로 된 단어라면 후보는 대략 천 개다. 해시 테이블에는 그리 큰 부담이 아니라서, 프로세스 하나로 실행해도 약 20초면 끝났다. 그중 19초는 후보 생성과 조회에 쓰였다.
이 데이터셋에서 오타는 총 30627개였다. 단어마다 후보가 천 개 이상이니, 모두 합치면 삼천만 번이 넘는 조회가 필요했다.
약 백 배 빨라진 이 단계는 사실 병렬화와는 관계가 없다. 알고리즘만 바꿨을 뿐이다. 이제 남은 문제는 이 20초의 작업을 여러 프로세스에 어떻게 나누느냐였다.
첫 번째 버전
첫 버전은 일단 돌아가게 만드는 것을 목표로, 단순하게 작성했다.
각 프로세스가 사전을 읽은 뒤 해시를 기준으로 자기 몫의 샤드만 남겼다. 단어가 사전에 있는지 확인할 때는 단어마다 MPI_Allreduce를 호출해 모든 프로세스가 자신의 샤드를 조회하고, 결과를 논리 OR로 합쳤다.
C++
for (size_t i = 0; i < word_list.size(); ++i) {
bool local_hit = local_dict.Contains(word_list[i]);
bool global_hit = false;
MPI_Allreduce(&local_hit, &global_hit, 1, MPI_C_BOOL, MPI_LOR, MPI_COMM_WORLD);
in_dict[i] = global_hit;
}
후보 검증도 비슷했다. 후보를 모든 프로세스에 보내 각자의 사전을 조회하게 하고, 일치하는 후보를 돌려받았다. 송신과 수신은 모두 블로킹 방식이었다.
아이디어 자체는 문제가 없지만, 단점도 분명했다. 단어가 65만 개면 집단 통신도 65만 번 해야 한다. 후보 하나를 모든 프로세스에 보내므로 통신량도 커진다. 더 큰 문제는 블로킹 송수신이 교착 상태를 일으킨다는 점이었다. 두 프로세스가 동시에 서로에게 큰 데이터를 보내면, 양쪽 모두 전송을 끝내지 못해 프로그램이 멈춰 버렸다.
먼저 교착 상태부터 해결했다. 처음에는 데이터 교환을 MPI_Sendrecv로 바꿨고, 나중에는 검증 절차 전체를 요청·응답 방식으로 고쳤다. 응답을 기다리는 동안 가만히 있어서는 안 된다. 상대도 내 응답을 기다리고 있을 수 있기 때문이다. 그래서 루프를 돌 때마다 MPI_Iprobe로 다른 프로세스의 요청이 도착했는지 확인하고, 있으면 함께 처리했다.
C++
std::vector<int> WaitForResponse(int target, const DistributedDict& dict) {
while (true) {
DrainIncomingRequests(dict); // 等回复的时候，也在帮别人查
int flag = 0;
MPI_Iprobe(target, kResponseHeader, MPI_COMM_WORLD, &flag, MPI_STATUS_IGNORE);
if (flag)
return ReceiveResponse(target);
}
}
이렇게 하면 응답을 기다리면서도 다른 프로세스의 요청을 처리한다. 모두가 응답만 기다리고 요청에는 답하지 않는 교착 상태를 피할 수 있다.
다음은 파일 읽기였다. 과제에서 사전을 분산하도록 요구했으므로 MPI-IO를 사용해 각 프로세스가 자신의 구간만 읽도록 바꿨다. 다만 파일을 바이트 단위로 나누면 경계가 단어 중간에 걸릴 수 있다. 그래서 시작점과 끝점을 모두 파일 끝 방향에 있는 다음 줄바꿈까지 옮겨, 단어 하나가 정확히 한 프로세스에만 속하도록 했다.
위 코드는 개념을 보여 주기 위한 것으로, 버퍼 할당과 EOF, 큰 파일의 카운트 처리는 생략했다. 실제로 줄 경계를 찾을 때는 MPI_File_read로 한 바이트씩 순서대로 읽으며 다음 줄바꿈이 나올 때까지 진행했다.
사전 분할 방식
최종 버전에서는 각 단어를 담당할 프로세스를 정했다. 단어의 해시값을 프로세스 수로 나눈 나머지가 해당 프로세스의 rank다. 사전의 단어는 각 담당 프로세스로 보내고, 그 프로세스가 자신의 해시 테이블에 저장한다.
여기서 작은 주의점이 있다. 첫 글자의 대소문자 규칙 때문에 Apple과 apple은 같은 프로세스가 처리해야 한다. 따라서 해시를 계산하기 전에 첫 글자만 소문자로 바꿨다. 어느 형태로 입력하든 같은 프로세스에 배정된다.
C++
int GetOwnerRank(const std::string& word, int world_size) {
std::string key = word;
if (!key.empty())
key[0] = std::tolower(static_cast<unsigned char>(key[0])); // 首字母统一转小写
return std::hash<std::string>{}(key) % world_size;
}
위 코드는 담당 프로세스를 정하는 규칙만 보여 준다. 보고서에 사용한 구현은 FNV-1a로 해시를 계산한다.
검사할 단어 목록에도 같은 규칙을 적용했다. 각 단어의 담당 프로세스는 사전에 있는지 판단하는 일과, 오타일 때 후보를 생성하는 일을 모두 맡는다. 단어 목록은 각 프로세스에 한 부씩 있으며, 각 프로세스가 인덱스를 기준으로 번갈아 일부를 맡아 해당 단어의 담당 프로세스로 조회를 보낸다. 조회하는 프로세스와 나중에 결과를 사용하는 프로세스가 같으므로, 결과를 다시 브로드캐스트할 필요가 없다. 덧붙이면 기존에 65만 번 수행하던 Allreduce가 여기서는 단 한 번의 Alltoallv로 바뀌었다.
후보 조회 방식
담당 프로세스는 자신에게 배정된 오타의 후보를 생성한 뒤, 후보가 사전에 있는지 조회한다. 그런데 후보의 담당 프로세스는 자신과 다를 수 있다. 로컬에서 담당하는 후보라면 해시 테이블을 바로 조회하면 되고, 다른 프로세스가 담당한다면 요청을 보내야 한다.
이때 필요한 요청 수는 상당히 많다. 64개 프로세스를 사용할 때는 삼천육백만 번이 넘는 후보 조회 중 거의 전부가 다른 프로세스의 몫이다. 하지만 대부분의 후보는 애초에 단어도 아니어서, 불필요한 요청과 응답만 오가게 된다.
그래서 각 프로세스에 Bloom filter를 추가했다. 각 프로세스는 자기 사전으로 Bloom filter를 만들고, MPI_Allgather로 모든 프로세스의 필터를 교환한다. 그러면 각 프로세스가 다른 모든 프로세스의 필터를 갖게 된다. 요청을 보내기 전에 로컬에서 필터를 조회하고, 없다는 결과가 나오면 확실히 없는 것이므로 후보를 전송하지 않아도 된다.
C++
for (const std::string& cand : candidates) {
int owner = GetOwnerRank(cand, world_size);
if (owner == rank) {
if (local_dict.Contains(cand)) verified.insert(cand); // 在本地，直接查
} else if (MayContain(bloom_of[owner], cand)) {
remote[owner].push_back(cand); // 过滤器说可能在，才发出去
} // 说不在的，直接丢掉
}
for (int owner = 0; owner < world_size; ++owner) {
if (remote[owner].empty()) continue;
SendCandidateBatch(owner, word_idx, remote[owner]);
for (int i : WaitForResponse(owner, local_dict))
verified.insert(remote[owner][i]);
}
각 프로세스의 필터는 전체 사전 단어 수의 12배에 해당하는 비트를 사용한다. 750만 비트, 약 940KB이며 해시 함수는 3개다. 프로세스가 64개라면 각 프로세스가 필터 64개를 보관하므로, 합계는 약 60MB가 된다.
효과는 뚜렷했다. 삼천육백만 번이 넘는 후보 조회 중 약 99.7%를 로컬에서 걸러 냈고, 실제로 전송한 것은 93897개뿐이었다. Bloom filter를 끄고 비교해 보니, 64개 프로세스에서 후보 단계가 0.93초 걸렸다. 켜면 0.31초였다.
전체 흐름을 이어 보면 대략 다음과 같다.
실험 방법
참조 구현에는 간단한 테스트가 있었지만 성능을 평가하기에는 부족했다. 그래서 일괄 실행을 위한 Python 스크립트인 batch_srun.py를 직접 만들었다.
프로그램은 각 단계에서 걸린 시간을 기록한 뒤, MPI_Reduce로 평균·최솟값·최댓값을 모아 표준 출력에 표시한다. 프로세스 하나로 실행하면 다음과 같다.
실행이 한 번 끝날 때마다 출력 파일의 MD5를 미리 기록해 둔 정답과 비교한다. 일치하지 않으면 바로 오류를 낸다. 따라서 표의 모든 성능 수치는 결과가 정확한지 확인한 상태에서 측정한 것이다.
데이터셋은 다섯 개다. 사전과 단어 목록을 각각 1만 또는 10만 단어로 구성한 조합들에 가장 큰 데이터셋을 더했다. 각 데이터셋을 1개부터 64개 프로세스까지 실행해 총 320번 측정했다. 모든 프로세스는 Spartan의 동일한 sapphire 컴퓨팅 노드에서 실행했다. 여기서는 MPI 프로세스 수에 따른 결과를 측정했으며, 여러 컴퓨팅 노드 사이의 네트워크를 포함한 확장성은 테스트하지 않았다.
다만 각 조건은 한 번씩만 실행했으므로 곡선에 다소 튀는 값이 있다. 예를 들어 12개 프로세스로 실행한 경우는 인접한 11개, 13개보다 상당히 느렸다.
결과
아래는 사전 62만 단어, 검사 목록 65만 단어인 가장 큰 데이터셋에 Bloom filter를 켠 결과다. 전체 시간은 외부 스크립트로 측정했고, 내부 측정 시간은 프로그램이 출력한 total_mpi를 사용했다. 두 값의 차이에는 시작 비용과 이 측정 구간에 포함되지 않은 I/O 등의 비용도 들어간다.
프로세스 수
전체 시간 (s)
내부 측정 시간 (s)
그중 후보 단계 (s)
1
20.42
19.99
19.17
2
9.09
8.76
8.11
4
4.89
4.42
4.00
8
2.96
2.30
1.90
16
1.99
1.36
0.93
32
1.83
0.89
0.50
64
1.88
1.06
0.31
후보 단계는 매우 잘 확장됐다. 19초에서 0.31초로 줄어, 64개 프로세스에서 약 62배 빨라졌다. 하지만 전체 프로그램이 그만큼 빨라진 것은 아니다. 64개 프로세스의 전체 시간은 1.88초로, 프로세스 하나일 때보다 10.9배 빠른 데 그쳤다.
병목은 다른 곳에 있었다. 후보 단계가 짧아지고 나니, 원래 눈에 띄지 않던 부분의 비중이 갑자기 커졌다.
단어 목록은 모든 프로세스가 각각 파싱해야 한다. 이 단계는 계속 약 0.09초가 걸리며, 프로세스를 늘려도 줄어들지 않는다.
사전 구축은 파일을 읽고 단어를 담당 프로세스로 보내는 순서로 진행된다. 프로세스 수를 1개에서 8개로 늘릴 때는 0.34초에서 0.09초로 실제로 빨라졌다. 하지만 그 이후부터는 다시 늘어나, 64개에서는 0.51초가 됐다. 프로세스가 늘수록 각자가 읽는 구간은 작아지는 반면, 메시지 수는 프로세스 수의 제곱에 비례해 증가하기 때문이다.
내부 측정 구간에 포함되지 않은 시작 비용과 I/O 등의 비용은, 전체 시간이 내부 측정 시간보다 약 0.8초 더 걸리는 데에도 나타난다.
그래서 64개 프로세스에서는 후보 단계가 내부 측정 시간의 30%도 차지하지 않는다. 오히려 사전 구축이 거의 절반을 차지한다.
곡선의 모양도 이로써 설명된다. 약 32개 프로세스 이후에는 곡선이 거의 평평해지고, 전체 시간은 1.3초에서 2초 사이를 오간다. 가장 빠른 경우는 38개 프로세스의 1.35초로, 약 15배 빨랐다. 이후 64개로 늘리면 오히려 32개보다 조금 느려졌다.
다른 프로세스로 전달한 요청에서 실제로 사전에 일치하는 후보의 비율도 프로세스 수에 따라 달라졌다. 각 프로세스의 필터 크기는 고정되어 있으므로, 프로세스가 적으면 각 샤드가 커지고 필터가 더 가득 차서 거짓 양성도 많아진다. 프로세스가 2개일 때는 전달된 후보 중 실제 사전에 있는 비율이 19%뿐이었다. 8개에서는 88%, 16개에서는 98%, 64개에서는 99.96%가 됐다.
마지막으로 처음의 BK-tree와 비교하면, 32분 걸리던 작업이 2초 이내로 줄었다. 그중 약 백 배는 알고리즘을 바꾼 덕분이고, 나머지 열 배에서 열다섯 배는 병렬화 덕분이다.
보고서
과제의 일부로 실험 환경, 결과와 분석을 담은 최종 보고서도 작성했다. 아래에서 원본 PDF를 바로 미리 보거나 다운로드할 수 있다.
COMP90025는 멜버른 대학교의 병렬 및 멀티코어 컴퓨팅(Parallel and Multicore Computing) 과목이다. 이 과목에는 큰 과제가 두 개 있는데, 둘을 합치면 간단한 병렬 맞춤법 검사기가 된다. 첫 번째 과제에서는 OpenMP로 문서에서 중복 없는 단어를 모았고, 두 번째 과제에서는 MPI로 전환해 그 단어들을 사전과 대조하면서 오타와 수정 후보를 찾는다.
두 번째 과제를 마친 뒤에 쓴 글이라, 여기 나오는 코드와 데이터는 모두 최종 제출본을 기준으로 한다. 코드는 xxxbrian/mpi-spell-checker에 올려 두었다.
과제 요구사항
프로그램 사용법은 간단하다.
dictionary.txt는 정렬된 사전이고, word_list.txt는 검사할 단어 목록이다. 목록의 각 단어가 사전에 없으면, 문자 하나를 바꾸거나 삭제하거나 추가해서 가능한 후보를 모두 생성해야 한다. 그렇게 만든 새 단어 중 사전에 있는 것들이 올바른 철자 후보가 된다. 대소문자에 관한 규칙도 하나 있다. 첫 글자만 소문자로 바꾼 형태가 사전에 있으면, 그 단어도 사전에 있는 것으로 간주한다.
출력은 오타 하나당 한 줄이며, 뒤에 수정 후보를 나열한다. 예를 들면 다음과 같다.
출력 순서는 후보 수가 적은 것부터이며, 후보 수가 같으면 사전순으로 정렬한다.
추가 제약도 있었다. 각 프로세스는 사전의 일부만 저장할 수 있고, 프로세스마다 사전 전체를 복제해서는 안 된다. 수업에서 제공한 단일 스레드 참조 구현은 BK-tree를 사용했다. 우리가 만든 프로그램은 학교 HPC 클러스터인 Spartan에서 실행해야 했다. 평가는 코드와 보고서로 나뉘는데, 보고서 배점이 더 높아서 실험과 분석도 대충 넘길 수 없었다.
먼저 알고리즘부터 바꾸기
구현에 들어가기 전에 참조 프로그램부터 실행해 봤다. BK-tree로 사전에서 편집 거리가 1 이하인 단어를 찾는 방식이었다. 가장 큰 데이터셋은 사전에 62만 개가 넘는 단어, 검사 목록에 65만 개가 넘는 단어가 있었는데, 실행에 약 32분이 걸렸다.
내가 택한 방법은 훨씬 단순했다. 편집 거리가 1로 고정되어 있으니, 가능한 후보를 전부 만든 뒤 해시 테이블에서 하나씩 조회하면 된다. 후보를 생성하는 코드도 복잡하지 않다.
길이가 L인 단어는 후보를 약 124 × L개 만든다. 따라서 알파벳 여덟아홉 글자로 된 단어라면 후보는 대략 천 개다. 해시 테이블에는 그리 큰 부담이 아니라서, 프로세스 하나로 실행해도 약 20초면 끝났다. 그중 19초는 후보 생성과 조회에 쓰였다.
이 데이터셋에서 오타는 총 30627개였다. 단어마다 후보가 천 개 이상이니, 모두 합치면 삼천만 번이 넘는 조회가 필요했다.
약 백 배 빨라진 이 단계는 사실 병렬화와는 관계가 없다. 알고리즘만 바꿨을 뿐이다. 이제 남은 문제는 이 20초의 작업을 여러 프로세스에 어떻게 나누느냐였다.
첫 번째 버전
첫 버전은 일단 돌아가게 만드는 것을 목표로, 단순하게 작성했다.
각 프로세스가 사전을 읽은 뒤 해시를 기준으로 자기 몫의 샤드만 남겼다. 단어가 사전에 있는지 확인할 때는 단어마다 MPI_Allreduce를 호출해 모든 프로세스가 자신의 샤드를 조회하고, 결과를 논리 OR로 합쳤다.
후보 검증도 비슷했다. 후보를 모든 프로세스에 보내 각자의 사전을 조회하게 하고, 일치하는 후보를 돌려받았다. 송신과 수신은 모두 블로킹 방식이었다.
아이디어 자체는 문제가 없지만, 단점도 분명했다. 단어가 65만 개면 집단 통신도 65만 번 해야 한다. 후보 하나를 모든 프로세스에 보내므로 통신량도 커진다. 더 큰 문제는 블로킹 송수신이 교착 상태를 일으킨다는 점이었다. 두 프로세스가 동시에 서로에게 큰 데이터를 보내면, 양쪽 모두 전송을 끝내지 못해 프로그램이 멈춰 버렸다.
먼저 교착 상태부터 해결했다. 처음에는 데이터 교환을 MPI_Sendrecv로 바꿨고, 나중에는 검증 절차 전체를 요청·응답 방식으로 고쳤다. 응답을 기다리는 동안 가만히 있어서는 안 된다. 상대도 내 응답을 기다리고 있을 수 있기 때문이다. 그래서 루프를 돌 때마다 MPI_Iprobe로 다른 프로세스의 요청이 도착했는지 확인하고, 있으면 함께 처리했다.
이렇게 하면 응답을 기다리면서도 다른 프로세스의 요청을 처리한다. 모두가 응답만 기다리고 요청에는 답하지 않는 교착 상태를 피할 수 있다.
다음은 파일 읽기였다. 과제에서 사전을 분산하도록 요구했으므로 MPI-IO를 사용해 각 프로세스가 자신의 구간만 읽도록 바꿨다. 다만 파일을 바이트 단위로 나누면 경계가 단어 중간에 걸릴 수 있다. 그래서 시작점과 끝점을 모두 파일 끝 방향에 있는 다음 줄바꿈까지 옮겨, 단어 하나가 정확히 한 프로세스에만 속하도록 했다.
위 코드는 개념을 보여 주기 위한 것으로, 버퍼 할당과 EOF, 큰 파일의 카운트 처리는 생략했다. 실제로 줄 경계를 찾을 때는 MPI_File_read로 한 바이트씩 순서대로 읽으며 다음 줄바꿈이 나올 때까지 진행했다.
사전 분할 방식
최종 버전에서는 각 단어를 담당할 프로세스를 정했다. 단어의 해시값을 프로세스 수로 나눈 나머지가 해당 프로세스의 rank다. 사전의 단어는 각 담당 프로세스로 보내고, 그 프로세스가 자신의 해시 테이블에 저장한다.
여기서 작은 주의점이 있다. 첫 글자의 대소문자 규칙 때문에 Apple과 apple은 같은 프로세스가 처리해야 한다. 따라서 해시를 계산하기 전에 첫 글자만 소문자로 바꿨다. 어느 형태로 입력하든 같은 프로세스에 배정된다.
위 코드는 담당 프로세스를 정하는 규칙만 보여 준다. 보고서에 사용한 구현은 FNV-1a로 해시를 계산한다.
검사할 단어 목록에도 같은 규칙을 적용했다. 각 단어의 담당 프로세스는 사전에 있는지 판단하는 일과, 오타일 때 후보를 생성하는 일을 모두 맡는다. 단어 목록은 각 프로세스에 한 부씩 있으며, 각 프로세스가 인덱스를 기준으로 번갈아 일부를 맡아 해당 단어의 담당 프로세스로 조회를 보낸다. 조회하는 프로세스와 나중에 결과를 사용하는 프로세스가 같으므로, 결과를 다시 브로드캐스트할 필요가 없다. 덧붙이면 기존에 65만 번 수행하던 Allreduce가 여기서는 단 한 번의 Alltoallv로 바뀌었다.
후보 조회 방식
담당 프로세스는 자신에게 배정된 오타의 후보를 생성한 뒤, 후보가 사전에 있는지 조회한다. 그런데 후보의 담당 프로세스는 자신과 다를 수 있다. 로컬에서 담당하는 후보라면 해시 테이블을 바로 조회하면 되고, 다른 프로세스가 담당한다면 요청을 보내야 한다.
이때 필요한 요청 수는 상당히 많다. 64개 프로세스를 사용할 때는 삼천육백만 번이 넘는 후보 조회 중 거의 전부가 다른 프로세스의 몫이다. 하지만 대부분의 후보는 애초에 단어도 아니어서, 불필요한 요청과 응답만 오가게 된다.
그래서 각 프로세스에 Bloom filter를 추가했다. 각 프로세스는 자기 사전으로 Bloom filter를 만들고, MPI_Allgather로 모든 프로세스의 필터를 교환한다. 그러면 각 프로세스가 다른 모든 프로세스의 필터를 갖게 된다. 요청을 보내기 전에 로컬에서 필터를 조회하고, 없다는 결과가 나오면 확실히 없는 것이므로 후보를 전송하지 않아도 된다.
각 프로세스의 필터는 전체 사전 단어 수의 12배에 해당하는 비트를 사용한다. 750만 비트, 약 940KB이며 해시 함수는 3개다. 프로세스가 64개라면 각 프로세스가 필터 64개를 보관하므로, 합계는 약 60MB가 된다.
효과는 뚜렷했다. 삼천육백만 번이 넘는 후보 조회 중 약 99.7%를 로컬에서 걸러 냈고, 실제로 전송한 것은 93897개뿐이었다. Bloom filter를 끄고 비교해 보니, 64개 프로세스에서 후보 단계가 0.93초 걸렸다. 켜면 0.31초였다.
전체 흐름을 이어 보면 대략 다음과 같다.
실험 방법
참조 구현에는 간단한 테스트가 있었지만 성능을 평가하기에는 부족했다. 그래서 일괄 실행을 위한 Python 스크립트인 batch_srun.py를 직접 만들었다.
프로그램은 각 단계에서 걸린 시간을 기록한 뒤, MPI_Reduce로 평균·최솟값·최댓값을 모아 표준 출력에 표시한다. 프로세스 하나로 실행하면 다음과 같다.
스크립트는 srun으로 프로그램을 실행하고, 정규식으로 이 숫자들을 추출해 CSV에 한 줄씩 기록한다.
실행이 한 번 끝날 때마다 출력 파일의 MD5를 미리 기록해 둔 정답과 비교한다. 일치하지 않으면 바로 오류를 낸다. 따라서 표의 모든 성능 수치는 결과가 정확한지 확인한 상태에서 측정한 것이다.
데이터셋은 다섯 개다. 사전과 단어 목록을 각각 1만 또는 10만 단어로 구성한 조합들에 가장 큰 데이터셋을 더했다. 각 데이터셋을 1개부터 64개 프로세스까지 실행해 총 320번 측정했다. 모든 프로세스는 Spartan의 동일한 sapphire 컴퓨팅 노드에서 실행했다. 여기서는 MPI 프로세스 수에 따른 결과를 측정했으며, 여러 컴퓨팅 노드 사이의 네트워크를 포함한 확장성은 테스트하지 않았다.
다만 각 조건은 한 번씩만 실행했으므로 곡선에 다소 튀는 값이 있다. 예를 들어 12개 프로세스로 실행한 경우는 인접한 11개, 13개보다 상당히 느렸다.
결과
아래는 사전 62만 단어, 검사 목록 65만 단어인 가장 큰 데이터셋에 Bloom filter를 켠 결과다. 전체 시간은 외부 스크립트로 측정했고, 내부 측정 시간은 프로그램이 출력한 total_mpi를 사용했다. 두 값의 차이에는 시작 비용과 이 측정 구간에 포함되지 않은 I/O 등의 비용도 들어간다.
프로세스 수
전체 시간 (s)
내부 측정 시간 (s)
그중 후보 단계 (s)
1
20.42
19.99
19.17
2
9.09
8.76
8.11
4
4.89
4.42
4.00
8
2.96
2.30
1.90
16
1.99
1.36
0.93
32
1.83
0.89
0.50
64
1.88
1.06
0.31
후보 단계는 매우 잘 확장됐다. 19초에서 0.31초로 줄어, 64개 프로세스에서 약 62배 빨라졌다. 하지만 전체 프로그램이 그만큼 빨라진 것은 아니다. 64개 프로세스의 전체 시간은 1.88초로, 프로세스 하나일 때보다 10.9배 빠른 데 그쳤다.
병목은 다른 곳에 있었다. 후보 단계가 짧아지고 나니, 원래 눈에 띄지 않던 부분의 비중이 갑자기 커졌다.
그래서 64개 프로세스에서는 후보 단계가 내부 측정 시간의 30%도 차지하지 않는다. 오히려 사전 구축이 거의 절반을 차지한다.
곡선의 모양도 이로써 설명된다. 약 32개 프로세스 이후에는 곡선이 거의 평평해지고, 전체 시간은 1.3초에서 2초 사이를 오간다. 가장 빠른 경우는 38개 프로세스의 1.35초로, 약 15배 빨랐다. 이후 64개로 늘리면 오히려 32개보다 조금 느려졌다.
다른 프로세스로 전달한 요청에서 실제로 사전에 일치하는 후보의 비율도 프로세스 수에 따라 달라졌다. 각 프로세스의 필터 크기는 고정되어 있으므로, 프로세스가 적으면 각 샤드가 커지고 필터가 더 가득 차서 거짓 양성도 많아진다. 프로세스가 2개일 때는 전달된 후보 중 실제 사전에 있는 비율이 19%뿐이었다. 8개에서는 88%, 16개에서는 98%, 64개에서는 99.96%가 됐다.
마지막으로 처음의 BK-tree와 비교하면, 32분 걸리던 작업이 2초 이내로 줄었다. 그중 약 백 배는 알고리즘을 바꾼 덕분이고, 나머지 열 배에서 열다섯 배는 병렬화 덕분이다.
보고서
과제의 일부로 실험 환경, 결과와 분석을 담은 최종 보고서도 작성했다. 아래에서 원본 PDF를 바로 미리 보거나 다운로드할 수 있다.