텐서화를 통한 진화적 다목적 최적화와
GPU 가속의 연결
Zhenyu Liang,Hao Li,Naiwei Yu, Kebin Sun, and Ran Cheng, Senior Member, IEEE
엔지니어링 설계 및 에너지 관리 등 다양한 분야에서 복잡한 최적화 솔루션에 대한 수요가 지속적으로 증가함에 따라, 진화적 다목적 최적화(EMO) 알고리즘은 다목적 문제를 해결하는 견고한 능력으로 인해 광범위한 주목을 받고 있습니다. 그러나 최적화 작업의 규모와 복잡성이 증가함에 따라, 기존 CPU 기반 EMO 알고리즘은 상당한 성능 병목 현상에 직면하게 됩니다.
이러한 한계를 해결하기 위해, EvoX 팀은 텐서화 방법론을 통해 GPU에서 EMO 알고리즘을 병렬화하는 방안을 제안했습니다. 이 방법을 활용하여 여러 GPU 가속 EMO 알고리즘을 성공적으로 설계하고 구현했습니다. 또한, 팀은 Brax 물리 엔진을 기반으로 한 다목적 로봇 제어 벤치마크 스위트인 **“MoRobtrol”**을 개발하여, GPU 가속 EMO 알고리즘의 성능을 체계적으로 평가하는 것을 목표로 했습니다.
이러한 연구 성과를 바탕으로, EvoX 팀은 고성능 GPU 가속 EMO 알고리즘 라이브러리인 EvoMO를 출시했습니다. 해당 소스 코드는 GitHub에서 공개적으로 이용 가능합니다: https://github.com/EMl-Group/evomo
텐서화 방법론
계산 최적화 분야에서 **텐서(tensor)**는 스칼라, 벡터, 행렬 및 고차 데이터를 표현할 수 있는 다차원 배열 데이터 구조를 의미합니다. **텐서화(Tensorization)**는 알고리즘 내의 데이터 구조와 연산을 텐서 형태로 변환하는 과정으로, 알고리즘이 GPU의 병렬 컴퓨팅 능력을 완전히 활용할 수 있게 합니다.
EMO 알고리즘에서 모든 핵심 데이터 구조는 텐서화된 형식으로 표현할 수 있습니다. 집단의 개체는 해 텐서 X로 표현할 수 있으며, 각 행 벡터는 하나의 개체에 대응합니다. 목적 함수 값은 목적 텐서 F를 형성합니다. 또한, 참조 벡터와 가중치 벡터와 같은 보조 데이터 구조는 각각 텐서 R과 W로 표현할 수 있습니다. 이 통합된 텐서 표현은 표현 수준에서 집단 수준의 연산을 가능하게 하여, 대규모 병렬 연산을 위한 견고한 기반을 마련합니다.
EMO 알고리즘 연산의 텐서화는 계산 효율성을 향상시키는 데 매우 중요하며, 기본 텐서 연산과 제어 흐름 텐서화의 두 계층으로 나눌 수 있습니다. 기본 텐서 연산은 EMO 알고리즘의 텐서화 구현의 핵심을 구성하며, Table I에 자세히 설명되어 있습니다.
Table I: 기본 텐서 연산
제어 흐름 텐서화는 기존의 루프 및 조건 논리를 병렬화 가능한 텐서 연산으로 대체합니다. 예를 들어, for/while 루프는 브로드캐스팅 메커니즘이나 vmap과 같은 고차 함수를 사용하여 배치 연산으로 변환할 수 있습니다. 마찬가지로, if-else 조건문은 마스킹 기법으로 대체할 수 있으며, 논리 조건을 불리언 텐서로 인코딩하여 서로 다른 계산 경로 간의 유연한 전환을 가능하게 합니다.
기존 EMO 알고리즘 구현과 비교하여, 텐서화 접근 방식은 상당한 이점을 제공합니다. 첫째, 다차원 데이터를 자연스럽게 처리하여 더 큰 유연성을 제공하는 반면, 기존 방법은 종종 2차원 행렬 연산에 제한됩니다. 둘째, 텐서화는 병렬 실행을 통해 계산 효율성을 크게 향상시키며, 명시적 루프 및 조건 분기와 관련된 오버헤드를 방지합니다. 마지막으로, 코드 구조를 단순화하여 더 간결하고 유지보수가 용이한 프로그램을 만듭니다.
Fig. 1에서 보듯이, 예를 들어 파레토 지배 검사의 기존 구현은 요소별 비교를 수행하기 위해 중첩 루프에 의존합니다. 반면, 텐서화된 버전은 브로드캐스팅과 마스킹 연산을 통해 동일한 기능을 달성하며, 병렬 평가를 가능하게 합니다. 이는 코드 복잡성을 줄일 뿐만 아니라 실행 시간 성능을 극적으로 향상시킵니다.
Fig.1: 파레토 지배 검출의 기존 구현과 텐서 기반 구현 비교.
더 깊은 관점에서, 텐서화는 GPU 가속에 매우 적합합니다. GPU는 다수의 병렬 코어를 보유하고 있으며, 단일 명령 다중 스레드(SIMT) 아키텍처가 텐서 연산과 자연스럽게 일치하여 특히 행렬 연산에서 뛰어난 성능을 발휘합니다. NVIDIA의 Tensor Cores와 같은 전용 하드웨어는 텐서 연산의 처리량을 더욱 향상시킵니다. 일반적으로 높은 병렬성을 보이고, 독립적인 계산 작업을 포함하며, 조건 분기가 최소인 알고리즘이 텐서화에 더 적합합니다. 순차적 의존성을 포함하는 MOEA/D와 같은 알고리즘의 경우, 내재된 구조가 직접적인 텐서화에 어려움을 줍니다. 그러나 구조적 리팩토링과 핵심 연산의 분리를 통해 효과적인 병렬 가속을 달성하는 것이 여전히 가능합니다.
알고리즘 텐서화의 적용 사례
텐서화된 표현 방법론을 기반으로, EvoX 팀은 지배 기반의 NSGA-III, 분해 기반의 MOEA/D, 지표 기반의 HypE 등 세 가지 고전적인 EMO 알고리즘의 텐서화 버전을 설계하고 구현했습니다. 다음 섹션에서는 MOEA/D를 예로 들어 자세히 설명합니다. NSGA-III와 HypE의 텐서화 구현은 참조 논문에서 확인할 수 있습니다.
Fig. 2에서 보듯이, 기존 MOEA/D는 다목적 문제를 여러 하위 문제로 분해하며, 각 하위 문제는 독립적으로 최적화됩니다. 알고리즘은 교차 및 돌연변이, 적합도 평가, 이상점 업데이트, 이웃 업데이트의 네 가지 핵심 단계로 구성됩니다. 이 단계들은 단일 루프 내에서 각 개체에 대해 순차적으로 실행됩니다. 이러한 순차적 처리는 대규모 집단을 다룰 때 상당한 계산 오버헤드를 초래하며, 각 개체가 모든 단계를 순서대로 완료해야 하므로 GPU 가속의 잠재적 이점이 제한됩니다. 특히 이웃 업데이트는 개체 간의 상호작용에 의존하여 병렬화를 더욱 복잡하게 만듭니다.
Fig.2: MOEA/D의 의사 코드
기존 MOEA/D의 순차적 의존성 문제를 해결하기 위해, 팀은 환경 선택의 내부 루프 내에 텐서화된 표현 방법을 도입했습니다. 교차 및 돌연변이, 적합도 평가, 이상점 업데이트, 이웃 업데이트를 분리하여 독립적인 연산으로 처리함으로써, 모든 개체의 병렬 처리가 가능해졌고, TensorMOEA/D라 불리는 텐서화된 MOEA/D 알고리즘이 구축되었습니다. 이 알고리즘에서 환경 선택은 비교 및 집단 업데이트, 엘리트 해 선택의 두 가지 주요 단계로 나뉩니다. 이 두 단계는 주로 vmap 연산의 두 번 적용을 통해 텐서화됩니다. 자세한 과정은 Fig. 3에 설명되어 있습니다.
Fig.3: TensorMOEA/D 알고리즘의 환경 선택 개요. 왼쪽: 알고리즘의 의사 코드. 오른쪽: 모듈 (1)과 모듈 (2)의 텐서 데이터 흐름. 오른쪽 그림의 상단은 모듈 (1)과 (2)의 전체 텐서 데이터 흐름을 보여주며, 하단은 배치 계산 텐서 데이터 흐름을 나타내며, 왼쪽이 모듈 (1), 오른쪽이 모듈 (2)입니다.
EMO 알고리즘에서 텐서화의 가치를 더 포괄적으로 이해하기 위해, 세 가지 관점에서 요약할 수 있습니다. 첫째, 텐서화는 수학적 공식에서 효율적인 코드로의 직접적인 변환을 가능하게 하여, 알고리즘 설계와 구현 사이의 격차를 좁힙니다. 예를 들어, Fig. 4는 텐서화된 비지배 정렬 절차가 의사 코드에서 Python 코드로 직접 변환될 수 있는 방법을 보여줍니다. 둘째, 텐서화는 집단 수준의 연산을 단일 텐서 표현으로 통합하여 코드 구조를 크게 단순화합니다. 이는 루프와 조건문에 대한 의존성을 줄여 코드의 가독성과 유지보수성을 향상시킵니다. 셋째, 텐서화는 알고리즘의 재현성을 향상시킵니다. 구조화된 표현은 비교 테스트와 결과의 일관된 재현을 용이하게 합니다.
Fig.4: 텐서화된 비지배 정렬의 의사 코드(왼쪽)에서 Python 코드(오른쪽)로의 원활한 변환.
성능 시연
GPU 가속 다목적 최적화 알고리즘의 성능을 평가하기 위해, EvoX 팀은 계산 가속, 수치 최적화 성능, 다목적 로봇 제어 작업에서의 효과에 초점을 맞추어 세 가지 범주의 실험을 체계적으로 수행했습니다.
계산 가속 성능:
Fig.5: 다양한 집단 크기와 문제 차원에서 CPU 및 GPU 플랫폼에서의 NSGA-III, MOEA/D, HypE와 텐서화된 대응 알고리즘의 비교 가속 성능.
실험 결과, TensorNSGA-III, TensorMOEA/D, TensorHypE는 비텐서화된 CPU 기반 대응 알고리즘에 비해 GPU에서 현저히 높은 실행 속도를 달성합니다. 집단 크기와 문제 차원이 증가함에 따라, 관찰된 최대 속도 향상은 1113배에 달합니다. 텐서화된 알고리즘은 대규모 계산 작업을 처리할 때 우수한 확장성과 안정성을 보여주며, 실행 시간은 미미하게만 증가하면서 일관되게 높은 성능을 유지합니다. 이러한 결과는 다목적 최적화에서 GPU 가속을 위한 텐서화의 상당한 이점을 강조합니다.
LSMOP 테스트 스위트에서의 성능:
Table II: LSMOP1—LSMOP9에서 비텐서화 및 텐서화 EMO 알고리즘의 IGD 및 실행 시간(초)의 통계적 결과(평균 및 표준 편차). 모든 실험은 RTX 4090 GPU에서 수행되었으며, 최고 결과가 강조 표시되어 있습니다.
실험 결과, 텐서화된 표현 기반의 GPU 가속 EMO 알고리즘은 원래 대응 알고리즘의 최적화 정확도를 유지하면서, 경우에 따라서는 이를 능가하면서 계산 효율성을 크게 향상시킵니다.
다목적 로봇 제어 작업:
GPU 가속 EMO 알고리즘의 실용적 성능을 종합적으로 평가하기 위해, 팀은 다목적 로봇 제어를 위한 MoRobtrol이라는 벤치마크 스위트를 개발했습니다. 이 스위트에 포함된 작업은 Table III에 나열되어 있습니다.
Table III: 제안된 MoRobtrol 벤치마크 테스트 스위트의 다목적 로봇 제어 문제 개요
Fig.6: 다양한 문제에서 TensorNSGA-III, TensorMOEA/D, TensorHypE, TensorRVEA, 랜덤 탐색(RS)의 비교 성능(HV, EU, 최종 결과 시각화): MoHalfcheetah (390D), MoHopper (243D), MoWalker2d (390D). 참고: 모든 지표에서 높은 값이 더 좋은 성능을 나타냅니다.
Fig.7: 다양한 문제에서 TensorNSGA-III, TensorMOEA/D, TensorHypE, TensorRVEA, 랜덤 탐색(RS)의 비교 성능(HV, EU, 최종 결과 시각화): MoPusher (503D), MoHumanoid (4209D), MoHumanoid-s (4209D). 참고: 모든 지표에서 높은 값이 더 좋은 성능을 나타냅니다.
Fig.8: 다양한 문제에서 TensorNSGA-III, TensorMOEA/D, TensorHypE, TensorRVEA, 랜덤 탐색(RS)의 비교 성능(HV, EU, 최종 결과 시각화): MoSwimmer (178D), MoIDP (161D), MoReacher (226D). 참고: 모든 지표에서 높은 값이 더 좋은 성능을 나타냅니다.
실험에서는 MoRobtrol 벤치마크 내에서 TensorNSGA-III, TensorMOEA/D, TensorHypE, TensorRVEA, 랜덤 탐색(RS)의 성능을 비교했습니다. 결과에 따르면 TensorRVEA가 최고의 전반적 성능을 달성하여, 여러 환경에서 가장 높은 HV 값을 얻고 좋은 해 다양성을 보여주었습니다. TensorMOEA/D는 대규모 작업에서 강한 적응성을 보여주었으며, 특히 해의 선호도 일관성에서 뛰어났습니다. TensorNSGA-III와 TensorHypE는 유사한 성능을 보였으며 여러 작업에서 경쟁력이 있었습니다. 전반적으로, 텐서화된 분해 기반 알고리즘이 대규모 복잡한 문제를 해결하는 데 우수한 이점을 보여주었습니다.
결론 및 향후 연구 본 연구는 기존 CPU 기반 EMO 알고리즘의 계산 효율성 및 확장성 한계를 해결하기 위한 텐서화된 표현 방법론을 제안합니다. 이 접근 방식은 NSGA-III, MOEA/D, HypE를 포함한 여러 대표적인 알고리즘에 적용되어, 해의 품질을 유지하면서 GPU에서 상당한 성능 향상을 달성했습니다. 실용적 적용 가능성을 검증하기 위해, 팀은 물리 시뮬레이션 환경에서의 로봇 제어 작업을 다목적 최적화 문제로 재구성하는 다목적 로봇 제어 벤치마크 스위트인 MoRobtrol도 개발했습니다. 결과는 체화 지능과 같은 계산 집약적 시나리오에서 텐서화된 알고리즘의 잠재력을 보여줍니다. 텐서화 방법이 알고리즘 효율성을 크게 향상시켰지만, 추가적인 개선의 여지가 남아 있습니다. 향후 방향으로는 비지배 정렬과 같은 핵심 연산자의 개선, 다중 GPU 시스템을 위한 새로운 텐서화 연산 설계, 대규모 데이터 및 딥러닝 기법의 통합을 통한 대규모 최적화 문제에서의 성능 향상이 포함됩니다.
오픈소스 코드 / 커뮤니티 리소스
논문:
https://arxiv.org/abs/2503.20286
GitHub:
https://github.com/EMI-Group/evomo
상위 프로젝트 (EvoX):
https://github.com/EMI-Group/evox
QQ 그룹: 297969717
EvoMO는 EvoX 프레임워크를 기반으로 구축되었습니다. EvoX에 대해 더 알고 싶으시다면, WeChat 공식 계정에 게시된 EvoX 1.0에 관한 공식 기사를 확인해 주십시오.
