컴퓨터 과학과 공학은 최근 수십년간 엄청난 주목을 받고, 특히 문제를 푸는 알고리즘과 그를 실행하는 하드웨어에서 큰 발전을 이루어내고 있다.

알고리즘쪽은 컴퓨터가 풀 수 있는 “효율적인” 문제가 무엇인지에 대답하기 위해 발전하고, 이 블로그의 글중 많은 부분에서 여러 발전을 소개하고있다.

하드웨어 부분에서는 최근까지도 상수년에 2배의 속도가 빨라진다는 무어의 법칙에 거의 따라가며 발전하고 있고, 이 발전은 많은 뉴스기사를 보거나, 당장 우리가 쓰는 컴퓨터를 실행해 봐도 실감할 수 있다.

---

그렇다면 여기서 질문: 최근의 하드웨어와 알고리즘은 무엇이 더 많이 발전했을까?

물론 일반적으로 두 발전을 비교하는 것은 불가능하다. 특히, 하드웨어는 일반적인 발전정도를 단위연산별로 계측하여 어느정도는 측정할 수 있지만, 알고리즘의 경우에는 어떤 문제를 푸냐에 따라 그 발전정도가 천차만별이다. 심지어 몇몇 문제의 경우는 특수한 경우에 훨씬 잘 풀기도 하고. 지난 글에서 슬쩍 언급했듯이 몇몇 문제는 수십년간 발전이 거의 없는 정도이다.

대신 얼마전 유럽의 연구자들이 Arxiv에 구체적인 문제를 대상으로 비교방식을 제시하는 논문을 포스팅했다. 논문에서는 구체적으로 주어진 식을 만족하는 해가 존재하냐고 묻는 SAT문제를 대상으로 비교를 진행했다. 찾아보니 SAT Competition이 계속 진행되고 있을정도로 활발하게 연구되는 분야이니, 꽤나 괜찮은 대상인듯.

논문의 결과를 간단히 요약하자면 다음과 같다.

여기서 각 항목은 200개의 SAT 인스턴스 중 해결한 인스턴스의 개수를 말하고, 가로축은 서로 다른 SAT-solver 알고리즘들을 뜻하고, 세로축은 1999년과 2019년의 하드웨어, 정확하게는 다음 세팅을 썼다고 한다.

• 1999년: Pentium III processor (467MHz) + 1.5GB RAM
• 2019년: Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM

저자들은 Team SW, Team HW를 나누어 각자 구현했다고 한다. 결과에 따르면 다음과 같이 말할수 있다.

SAT문제에 관해서는 알고리즘의 발전이 하드웨어의 발전보다 약간 더 빠르다!

몇가지 관찰이나 세팅은 아래에 정리해둔다.

• 각 결과들은 200개의 인스턴스중 900초안에 풀리는 인스턴스의 개수를 센 것이다.
• 인스턴스들은 알려진 벤치마크들로 여러가지 만들어진 것으로, 테스트를 위한 적절한 크기/방법을 골랐다고 한다. 아마 Random SAT등으로 고르면 일부 세팅은 거의 전부 푸는데 다른 세팅은 전혀 못푸는 그런 상황이 벌어졌을듯. 특히 set-asp-gauss라는 벤치마크가 가장 적절하여 이용했다고 한다.
• 2019년에 가장 좋은 알고리즘으로 알려진 Maple SAT solver가 1999년 하드웨어를 쓴 경우 다른 알고리즘보다 약간 더 못푸는 경우가 발생했다. 저자들도 정확한 이유를 알지는 못하고, 아마 좋은 알고리즘에서 사용한 특정한 자료구조가 현대 하드웨어에 훨씬 적합한게 아닐까.. 같은 추측을 한다.
• 사실 SAT 알고리즘은 1990년대 후반 등장한 CDCL (Conflict-Driven Clause Learning)이라는 방식을 아직 기반으로 사용하고 있다고 한다. 물론 다양한 발전이 있긴하다! 심지어 CDCL도 DPLL (Davis–Putnam–Logemann–Loveland)이라고 하는 1960년대 알고리즘을 기반으로 발전했다고 한다. 역시 알고리즘의 큰 줄기는 1960년대에 다 나온듯 ㅋㅋㅋ

과거의 알고리즘에 비해 얼마나 좋아졌는지 뭔가 직관적으로 볼 수 있는 결과가 있으면 좋을텐데 좀 아쉽다 ㅋㅋ 여튼 결론은 알고리즘의 연구가 하드웨어연구만큼 중요하다는 것으로 논문은 끝.