아날로그 솔버, NP-하드 최적화 문제에서 디지털 컴퓨터 능가

오늘날 디지털 컴퓨터는 대부분의 작업을 잘 수행합니다. 특정 계산, 워드 프로세싱, 웹 서핑, 그래픽 아트에 완벽합니다. 하지만 이진 코드(0과 1)에 의존하므로 모든 문제를 푸는 데 이상적이지는 않습니다.

디지털 컴퓨팅은 거의 최대 잠재력에 도달했고, 그래서 일부 수학자들은 아날로그 컴퓨팅 부활에 관심을 갖기 시작했습니다. 이는 디지털 프레임워크를 넘어 계산을 발전시키는 데 도움이 될 수 있습니다.

최근 노트르담 대학과 루마니아 바베시-볼야이 대학 연구자들이 NP-하드 문제의 최적 해를 평가할 수 있는 새로운 아날로그 솔버를 개발했습니다.

NP-하드 문제란 다항식 시간에 문제를 풀 수 있는 알고리즘이 없는 것을 의미합니다. 해에 도달하는 데 필요한 시간은 문제 크기에 따라 기하급수적으로 증가합니다. 보통 이 문제들은 의료 영상, 바이오인포매틱스, 단백질 접힘, 스케줄링과 관련됩니다.

연구자들은 광범위한 NP-하드 문제에 아날로그 솔버를 테스트했고, 이 새로운 방법이 더 적은 시간에 더 나은 해로 이어질 잠재력이 있음을 발견했습니다.

아날로그 컴퓨터는 20세기 중반에 매우 인기 있었습니다. 역학 문제와 관련된 모든 큰 행정기관과 회사에는 거대한 아날로그 컴퓨팅 센터가 있었습니다. 로켓을 우주로 발사하고, 전함의 무기를 유도하고, 항공기 역학을 시뮬레이션하는 데 사용되었습니다.

디지털 컴퓨터와 달리 아날로그 컴퓨터는 전압, 무게, 속도, 온도, 압력 같은 비이산 데이터를 사용합니다. 연속값을 사용하므로 양자화 노이즈에 면역입니다.

아날로그 컴퓨터는 다양한 문제를 풀도록 설계될 수 있습니다. 직접 수학 연산을 수행할 수 있습니다. 예를 들어 3에서 8을 빼려면 아날로그 컴퓨터는 해당 값에 대응하는 전압을 빼고 즉시 정확한 출력을 제공합니다.

실시간 연산과 동시 계산에 사용될 수 있습니다. 아날로그 문제 발생 시 문제와 오류에 대한 통찰을 제공할 수 있습니다. 양자화가 필요 없으므로 신호 변조/복조와 고속 모터 제어에 완벽합니다.

참조: Nature Communications | doi:10.1038/s41467-018-07327-2 | 노트르담 대학

그러나 디지털 컴퓨터가 1980년대에 시장을 장악했습니다. 일반적인 작업 수행에 충분히 유연하고 빠르며 더 정확했습니다. 효율적 알고리즘이 등장하면서 성능은 더 좋아졌습니다.

빈티지 아날로그 AMF665D 컴퓨터 | 이미지 출처: Francis Massen / YouTube

하지만 디지털 컴퓨터(현대 포함)는 큰 변수를 가진 NP-하드 문제를 풀 수 없습니다. 대부분의 최적화 문제의 어려움은 해가 최적인지 판단할 수 없다는 것입니다. 더 나은 해가 없는지 확인하는 것이 문제 자체만큼이나 어렵습니다.

새로운 연속시간 역학 시스템은 퀸테센셜 이산 최적화 문제인 MaxSAT을 풀 수 있습니다. 이 방법은 결정론적 상미분방정식 세트와 아날로그 시간 t까지 최적 해가 평가되었을 가능성을 예측하는 휴리스틱 기법에 의존합니다.

아날로그 회로에서 폰 노이만 병목현상이 제거됩니다: 회로 자체가 프로세서이자 메모리 역할을 합니다. 반면 디지털 컴퓨터에서 이 접근법을 구현하려면 연속시간 방정식을 이산화하고 단계별로 풀면서 오류를 처리하는 상미분방정식 적분 알고리즘을 사용해야 합니다.

디지털 형태에서는 역학이 수천 개의 결합된 상미분방정식을 진화시키므로 시간이 많이 소요되는 적분 과정 때문에 솔버가 효율적으로 작동하지 않습니다.

참고: 양자 컴퓨터에 대한 가장 흥미로운 사실들

이 접근법이 일반적인 특성을 사용하므로 다른 최적화 문제로도 확장될 수 있습니다. 연구자들은 이 새로운 접근법을 기반으로 장치를 설계하고 구축할 계획입니다.

산업기술