Road to scalability for efficient graph search on massively parallel neuromorphic hardware

기술 요약: 대규모 병렬 뉴로모픽 하드웨어 상에서의 효율적인 그래프 탐색을 위한 확장성 경로

문제 정의
가중치 그래프에서 최단 경로를 계산하는 것은 경로 계획, 네트워크 라우팅, 로봇 동작 계획, 그리고 비선형 차원 축소(예: Isomap)와 같은 핵심 응용 분야에서 매우 중요한 문제입니다. 다익스트라(Dijkstra) 알고리즘과 같은 기존의 확립된 순차적 알고리즘은 전통적인 하드웨어에서는 효과적이지만, 대규모 그래프나 다중 사용자 환경에 적용될 때 확장성 및 에너지 효율성 측면에서 어려움에 직면합니다. GPU 및 CPU를 위한 기존의 병렬 접근 방식은 종종 비용이 많이 드는 전역 조정 메커니즘에 의존합니다. 뉴로모픽 하드웨어는 계산과 메모리가 국부적으로 결합되어 있고 이벤트 기반 통신을 특징으로 하며, 이는 고유한 강점을 활용하기 위해 전역 동기화를 최소화하는 알고리즘을 필요로 합니다.

방법론: NEURO-MAPP
저자들은 뉴로모픽 시스템을 위해 특별히 설계된 분산 최단 경로 알고리즘인 NEURO-MAPP(Neuromorphic-based Min-Add Parallel Propagation)를 소개합니다. 핵심 개념은 가중치 그래프를 다음과 같은 계산 그래프에 임베딩하는 것입니다:

• 국부 연산(Local Operations): 정점(Vertex)은 들어오는 거리 신호에 대해 국부적인 최소화(minimization)를 수행하여 가장 작은 후보 거리를 선택합니다.
• 에지 연산(Edge Operations): 에지는 연관된 가중치를 들어오는 신호에 더함으로써 거리 업데이트를 전파합니다.
• 역학(Dynamics): 최단 경로는 전역적인 조정 없이 순수하게 국부적이고 병렬적인 업데이트 역학을 통해 나타납니다.

이 알고리즘은 152개의 ARM 코어를 포함하며 각 코어가 전용 SRAM을 보유하고 저지연 네트워크 온 칩(NoC)으로 연결된 대규모 병렬 뉴로모픽 시스템인 SpiNNaker 2 플랫폼에서 구현되었습니다. 주요 구현 전략은 다음과 같습니다:

1. 정점 분할(Vertex Partitioning): 편향된 차수 분포(예: 단백질 네트워크의 "허브")로 인한 부하 불균형을 해결하기 위해, 저자들은 정점의 차수를 고려한 분할 전략을 개발했습니다. 이는 코어당 누적 차수를 최소화하도록 정점을 할당하여 병목 현상을 방지합니다. 다른 유형의 그래프의 경우, 무작위 또는 대역폭 최소화 할당 방식이 사용되었습니다.
2. 메시지 전달 최적화(Message Passing Optimization): 거리 업데이트를 인코딩하는 두 가지 방법을 비교했습니다. 소스 코어에 출력 에지를 직접 저장하고 상수 시간 조회를 수행하는 "선행자 기반(predecessor-based)" 방식이, 이진 탐색을 요구하는 기본 "후속자 기반(successor-based)" 방식보다 훨씬 우수한 성능을 보였으며, 희소(sparse) 및 고연결 그래프에서 검색 시간을 최대 10배까지 단축했습니다.
3. 동적 반복 스케줄링(Dynamic Iteration Scheduling): 코어 간의 가변적인 워크로드로 인한 유휴 시간을 완화하기 위해 경량 전역 코디네이터가 구현되었습니다. 코어는 완료 신호를 스케줄러에 보내고, 스케줄러는 모든 코어가 준비되었을 때만 다음 반복을 트리거하여, 고정되고 낭비적인 타임 스텝 없이 동기화를 보장합니다.

주요 결과
단일 SpiNNaker 2 칩에서의 NEURO-MAPP 성능을 현대적인 CPU(M1 Pro)에서 실행된 다익스트라 알고리즘과 합성 및 실제 그래프 유형에 대해 평가했습니다:

• 확장성 및 실행 시간:

  • 무작위 및 좁은 세상(Small-World) 그래프: NEURO-MAPP은 우수한 확장성을 보여주었습니다. 다익스트라 알고리즘이 작은 그래프에서는 더 나은 성능을 보였으나, NEURO-MAPP의 실행 시간은 그래프 크기에 따라 로그 함수적으로 증가하여, 약 30,000~38,000개의 정점을 초과하는 그래프에서 다익스트라를 능가했습니다.
  • 그리드 그래프: 3D 그리드 그래프의 경우, 더 많은 반복을 요구하는 그래프의 큰 직경 때문에 다익스트라 알고리즘이 여전히 더 빨랐습니다. 그러나 고차원 그리드(예: 5D)의 경우, NEURO-MAPP은 약 20%의 실행 시간 이점을 보였습니다.
  • 실제 응용 분야: 3D 항공 항법(맨해튼 도심 환경)에서 NEURO-MAPP은 다익스트라의 6.8 ms에 비해 6.1 ms 만에 문제를 해결했습니다. 반대로, 도로 네트워크 항법(독일 지역)의 경우, 특정 토폴로지와 테스트된 네트워크 규모로 인해 현재는 NEURO-MAPP이 (한 자릿수 차이로) 더 느렸으나, 저자들은 더 큰 규모에서 다익스트라를 추월할 것이라고 전망합니다.
  • 단백질 상호작작용 네트워크: 현재 네트워크 크기에서는 실행 시간이 더 길었음에도 불구하고, NEURO-MAPP은 유사한 토폴로지를 가진 더 큰 네트워크에 대해 유리한 추세를 보였습니다.

• 에너지 효율성:

  • 테스트된 모든 그래프 유형에 대해, NEURO-MAPP은 CPU 구현보다 최단 경로 쿼리당 현저히 적은 에너지를 소비했습니다.
  • SpiNNaker 2 칩은 실행 중 500 mW 미만을 소비한 반면, CPU는 약 4 W를 소비했습니다. NEURO-MAPP의 실행 시간이 더 긴 경우에도, 낮은 전력 소모 덕분에 총 에너지 소비량이 낮았습니다(예: 항공 항법 작업의 경우 2.4 mJ 대 25.5 mJ).

• Isomap과의 통합:

  • 저자들은 모든 쌍 최단 경로(APSP) 행렬을 계산하기 위해 NEURO-MAPP을 Isomap 차원 축소 프레임워크에 통합했습니다. NEURO-MAPP은 더 큰 데이터셋과 더 많은 근접 이웃($k$)에 대해 우수한 성능을 입증하여, 더 큰 알고리즘 파이프라인의 구성 요소로서의 유용성을 검증했습니다.

의의 및 주장
본 논문은 NEURO-MAPP이 희소한 스파이크 기반 통신을 특징으로 하는 뉴로모픽 하드웨어가 그래프 탐색을 위한 확장 가능하고 에너지 효율적인 플랫폼이 될 수 있음을 입증한다고 주장합니다. 저자들은 단일 코어 순차 알고리즘과 대규모 병렬 시스템을 비교하는 것이 불공평해 보일 수 있다는 점을 인지하고 있으나, 관심 지표는 과업을 완료하는 데 필요한 총 실행 시간과 에너지임을 강조합니다.

주요 클레임은 다음과 같습니다:

1. 에너지 효율성: 뉴로모픽 하드웨어는 병렬 알고리즘이 아직 모든 그래프 크기에서 절대적인 실행 속도 면에서 가장 빠르지 않더라도, 기존 CPU보다 훨씬 적은 에너지 소비로 최단 경로 문제를 해결할 수 있습니다.
2. 확장성: 알고리즘은 낮은 직경을 가진 그래프 패밀리(무작위, 좁은 세상, 고차원 그리드)에 대해 유리하게 확장되며, 이는 다중 칩 뉴로모픽 시스템이 현재 에너지 제약이 있는 애플리케이션에서 다루기 힘든 문제들을 해결할 수 있음을 시사합니다.
3. 하드웨어 불가지론(Hardware Agnosticism): SpiNNaker 2에서 구현되었지만, 저자들은 이 알고리즘이 충분한 독립적 병렬 유닛, 국부 메모리 및 저지연 통신을 갖춘 Loihi 2나 Graphcore IPU와 같은 다른 뉴로모픽 플랫폼을 포함한 모든 시스템에 적용 가능하다고 언급합니다.

저자들은 현재의 한계에 대해 겸허한 태도를 유지하며, 특정 유형의 그래프(예: 2D 도로 네트워크)나 현재의 단일 칩 제약 조건 하에서는 다익스트라 알고리즘이 여전히 더 빠르다는 점을 인정합니다. 그러나 에너지 이점과 로그 스케일링 추세는 더 큰 규모의 다중 칩 뉴로모픽 시스템에서 탁월한 성능을 낼 수 있는 명확한 경로를 제시한다고 주장합니다.