Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

현대 컴퓨팅의 광활한 풍경 속에는, 단 하나의 최적의 해답을 찾는 것이 발걸음을 옮길 때마다 크기가 두 배로 커지는 사막에서 특정 모래알 하나를 찾는 것처럼 느껴질 정도로 복잡한 문제들이 존재합니다. 이러한 것들은 최적화 도전 과제들로, 종종 상호작용하는 부분들의 네트워크로 모델링되며, 목표는 가능한 낮은 에너지 상태나 비용에 도달하도록 조각들을 배치하는 것입니다. 과학자와 엔지니어들은 이 모델들을 사용하여 원자 수준에서 물질이 어떻게 행동하는지부터 교통량을 조절하거나 금융 포트폴리오를 관리하는 방법까지 모든 것을 이해합니다. 수십 년 동안 이 퍼즐을 푸는 가장 신뢰할 수 있는 방법은 가능한 모든 배치를 일일이 확인하는 것이었으며, 이를 전수 조사(exhaustive search)라고 합니다. 그러나 조각의 수가 늘어남에 따라 가능한 배치의 수는 너무나 빠르게 폭발적으로 증가하여, 세계에서 가장 강력한 슈퍼컴퓨터조차도 인간의 수명 내에 작업을 끝낼 수 없습니다. 이는 결정적인 격차를 만듭니다. 즉, 절대적인 최선의 답을 찾을 방법이 없다면, 연구자들은 "충분히 좋은" 답을 찾기 위해 사용하는 영리한 지름길들이 실제로 진리에 얼마나 근접해 있는지 확신할 수 없습니다.

폴란드의 연구팀은 이제 이러한 특정 범위의 어려운 문제들을 위해 이 격차를 메우도록 설계된 새로운 도구를 구축했습니다. 그들은 고성능 컴퓨터에서 게임이나 영상용으로 쓰이는 일반적인 그래픽 카드를 60개의 조각까지 모든 가능한 배치를 확인할 수 있는 기계로 변모시키는 소프트웨어 업데이트를 만들어냈습니다. 이러한 원시적인 확인 능력과 여러 대의 컴퓨터에 걸쳐 작업을 분할하는 시스템을 결합함으로써, 그들은 이전에는 완전히 해결하기에 너무 컸던 문제들에 대해 완벽한 해답을 찾아내는 데 성공했습니다. 이 성과는 다른 더 빠른 컴퓨터 프로그램들이 테스트될 수 있는 "골드 스탠다드(표준)" 답변을 제공하며, 이를 통해 과학자들이 자신들의 지름길이 정말로 작동하고 있는지, 아니면 최선의 해답을 놓치고 있는지를 검증할 수 있게 해줍니다.

이 작업의 핵심은 Omnisolver-bruteforce라는 소프트웨어 플러그인으로, 이는 서로 다른 유형의 컴퓨터 솔버들을 위한 범용 번역기 역할을 합니다. 이것을 다양한 도구들을 동일한 문제에 투입할 수 있게 해주는 마스터 키라고 생각하십시오. 연구진은 단일 그래픽 카드에서 모든 가능성을 확인할 수 있는 기존 도구를 가져와, 여덟 개의 강력한 그래픽 카드가 동시에 작동하도록 업그레이드했습니다. 그들은 거대한 탐색 공간을 작고 독립적인 덩어리들로 나누는 방식을 통해 이를 달성했습니다. 도서관에서 특정 책을 찾아야 하는 상황을 상상해 보십시오. 한 사람이 모든 선반을 확인하는 대신, 작업을 나누어 여덟 명의 사람이 동시에 서로 다른 구역을 확인하고, 목표를 찾았을 때만 보고하는 방식입니다. 이 경우, "도서관"은 문제의 모든 가능한 배치 집합이며, "탐색자"는 병렬로 작동하는 그래픽 카드들입니다.

연구진은 대용량 메모리를 갖춘 8개의 고성능 그래픽 카드 클러스터에서 이 새로운 시스템을 테스트했습니다. 그들은 이 최적화 문제들의 무작위 버전을 해결하도록 시스템을 설정하고, 문제의 크기를 40개에서 60개까지 점진적으로 늘렸습니다. 결과는 놀라웠습니다. 60개의 조각이 있는 문제에 대해, 시스템은 모든 가능성을 확인하고 최선의 답을 확정하는 데 약 3일이 걸렸습니다. 이것이 길게 느껴질 수도 있지만, 이 새로운 방법이 없었다면 이 작업은 합리적인 시간 내에 완료하는 것이 불가능했을 것입니다. 연구진은 문제에 조각이 하나씩 추가될 때마다 해결에 필요한 시간이 대략 두 배로 증가하는 현상을 관찰했으며, 이 패턴은 모든 테스트에서 동일하게 나타났습니다. 이 예측 가능한 동작은 그들의 시스템이 이러한 유형의 전수 조사에 따른 물리 법칙과 수학적 법칙에 따라 정확하게 작동하고 있음을 확인시켜 주었습니다.

이 혁신의 중요한 부분은 컴퓨터가 이토록 방대한 양의 작업을 수행하는 동안 작은 실수를 저지르지 않도록 보장하는 것이었습니다. 그래픽 카드는 극도의 정밀함보다는 속도에 치중하도록 설계되어 있어, 시간이 흐르면서 누적될 수 있는 미세한 오류가 발생할 수 있습니다. 연구진은 이러한 미세한 오류가 발생하는 즉시 자동으로 수정하는 방법을 개발하여, 최종 결과가 수학적으로 정확하도록 보장했습니다. 그들은 더 작은 문제들에 대해 알려진 완벽한 해답과 비교함으로써 이를 검증했으며, 마지막 자리 숫자까지 일치하는 결과를 얻었습니다. 이러한 신뢰 수준은 이 도구가 기업을 위한 일상적인 문제를 해결하기 위한 것이 아니라, 참조점 역할을 하기 위해 만들어졌다는 점에서 매우 중요합니다. 이는 과학자들이 양자 물리학이나 생물학적 시스템에서 영감을 받은 새로운, 더 빠른 알고리즘들이 정말로 최선의 해답을 찾고 있는지, 아니면 그저 추측하고 있는 것인지를 테스트할 수 있는 척도를 제공합니다.

연구는 또한 더 큰 컴퓨터 클러스터를 사용한다면 무엇이 가능할지에 대해서도 살펴보았습니다. 연구진은 만약 216개의 그래픽 카드를 연결할 수 있다면, 60개의 조각이 있는 문제를 단 33초 만에 해결할 수 있다고 계산했습니다. 나아가, 이 정도 규모의 거대한 네트워크를 갖춘다면 이론적으로 76개의 조각까지 있는 문제를 한 달 이내에 해결할 수 있다고 추정했습니다. 그러나 그들은 이것이 현재의 데이터를 바탕으로 한 투영치이며, 컴퓨터 간의 통신 지연과 같은 실제 환경 요인들이 정확한 수치를 바꿀 수 있다는 점을 주의 깊게 언급했습니다. 현재 시스템은 소프트웨어가 배치를 계산하는 방식 때문에 64개의 조각까지로 제한되어 있지만, 이 한도 내에서는 확정적인 답을 제공합니다.

이 작업은 모든 최적화 문제를 해결했다고 주장하거나, 전수 조사가 일상적인 용도의 더 빠르고 근사적인 방법들을 대체할 것이라고 제안하는 것이 아닙니다. 대신, 그것은 그러한 더 빠른 방법들의 품질을 인증하는 방법을 제시합니다. 특정 크기의 문제에 대해 보장된 정답을 제공함으로써, 연구진은 과학계에 새로운 기술의 정확도를 측정할 수 있는 자를 건네주었습니다. 컴퓨팅 분야가 더 복잡한 과제들을 향해 나아감에 따라, "이것이 가능한 최선의 답이다"라고 단정적으로 말할 수 있는 도구를 갖는 것은 필수적인 벤치마크가 됩니다. 연구진은 자신들의 소프트웨어를 공개하여, 커뮤니티가 이 새로운 능력을 사용하여 자신들의 발견을 검증하고 컴퓨팅이 가능한 한계를 넓혀갈 수 있도록 초대했습니다.