Tsinghua Yao 학부생들은 10년 만에 가장 큰 발전인 두 작품을 연속으로 출판했습니다. 행렬 곱셈은 이론적 최적에 가깝습니다.
- 王林앞으로
- 2024-03-08 21:52:02887검색
컴퓨터 과학자들은 "숨겨진 비효율성"을 제거하여 이전보다 더 빠르게 대규모 행렬을 곱할 수 있는 새로운 방법을 찾아냈습니다.
많은 GPU 연산자의 기본 연산으로 행렬 곱셈은 고성능 컴퓨팅에서 중요한 역할을 하며 AI와 같은 응용 프로그램의 핵심 구성 요소이기도 합니다. 알고리즘 자체는 상대적으로 간단하지만 더 빠른 속도를 달성하기 위해 수년에 걸쳐 이를 최적화하려는 노력이 이루어져 왔습니다. 그러나 최적화의 범위는 다소 제한되었습니다.
Quantum Magazine 최신호에서 행렬 곱셈의 속도를 높일 수 있는 논문 두 편을 발견했습니다. 이 두 논문의 집필에는 칭화대학교 야오학급 학부생이 적극적으로 참여하여 이 분야의 알고리즘 개선에 대한 새로운 전망을 가져왔습니다.
행렬 곱셈의 개선에 새로운 "특이점"이 나타납니다
컴퓨터 과학자들은 매우 까다로운 사람들입니다. 그들이 추구하는 것은 문제 해결뿐만 아니라 가장 효율적인 방법으로 목표를 달성하는 것입니다.
1812년 프랑스 수학자 자크 필립 마리 비네(Jacques Philippe Marie Binet)는 오늘날에도 여전히 학생들에게 가르쳐지고 있는 일련의 기본 규칙을 제안한 행렬이나 숫자 배열의 곱셈을 예로 들어 보겠습니다. 이 규칙 세트는 널리 사용되지만 최근 몇 년 동안 일부 수학자들은 프로세스를 단순화하고 속도를 높이는 방법을 발견했습니다. 프랑스 수학자 자크 필립 마리 비네.
이 논문은 컴퓨터 과학 분야 최고의 학회인 FOCS 2023에 게재되었습니다.
Paper v1은 2022년 10월, v5는 2023년 11월에 출시될 예정입니다. 논문 주소: https://arxiv.org/abs/2210.10173
그 중 Duan Ran은 칭화 대학교 교차 정보 연구소의 부교수입니다. 그의 주요 연구 방향은 그래프 이론 알고리즘, 데이터 구조 및 컴퓨팅입니다. 이론. 우홍쉰(Hongxun Wu)은 버클리 캘리포니아 대학교에서 박사 과정을 밟고 있는 2년차 학생이자 칭화 대학교 야오 클래스를 졸업했습니다.
Zhou Renfei는 2020년 Tsinghua University Yao Class의 4학년 학부생으로 이론 컴퓨터 공학(TCS)을 전공하고 있습니다. 그는 주로 (간결한) 데이터 구조와 빠른 행렬 곱셈을 연구하고 있으며 스트리밍 알고리즘, 게임 이론, 온라인 알고리즘 등 TCS의 다른 영역에도 폭넓은 관심을 갖고 있습니다.
세 명의 연구원이 작성한 논문은 이미 결실을 맺고 있는 이전에 알려지지 않았거나 아직 개발되지 않은 잠재적인 개선 소스를 보여줍니다. 2024년 1월에 발표된 두 번째 논문(Renfei Zhou 공동 집필)은 이를 기반으로 행렬 곱셈을 더욱 향상시킬 수 있는 방법을 보여줍니다.
논문 주소: https://epubs.siam.org/doi/10.1137/1.9781611977912.134
하버드 대학의 이론 컴퓨터 과학자인 William Kuszmaul은 이것이 10개 이상의 중요한 기술 혁신이라고 말했습니다. 행렬 곱셈에 있어서 우리가 수년간 보아온 가장 큰 개선입니다. 
행렬 곱셈은 모호한 문제처럼 보일 수 있지만 이는 기본적인 계산 연산입니다. 이는 보다 명확한 컴퓨터 그래픽 표시부터 네트워크 이론의 물류 문제 해결에 이르기까지 다양한 작업을 위해 사람들이 매일 사용하는 대부분의 알고리즘에 통합되어 있습니다. 다른 컴퓨팅 영역과 마찬가지로 속도가 핵심입니다. 작은 개선이라도 궁극적으로 필요한 시간, 컴퓨팅 성능 및 비용을 크게 줄일 수 있습니다. 그러나 현재 이론가들은 주로 프로세스가 얼마나 빨리 진행될 수 있는지 알아내는 데 관심이 있습니다.
두 개의 n×n 행렬을 곱하는 전통적인 방법, 즉 첫 번째 행렬의 각 행에 있는 숫자와 두 번째 행렬의 각 열에 있는 숫자를 곱하는 방법에는 n³ 독립적인 곱셈 연산이 필요합니다. 2x2 행렬의 경우 이는 2³ 또는 8번의 곱셈을 의미합니다.
1969년 수학자 Volker Strassen은 단 7개의 곱셈 단계와 18개의 덧셈 단계만으로 2×2 행렬의 곱셈을 완료할 수 있는 더 우아한 방법을 발견했습니다. 2년 후, 컴퓨터 과학자 Shmuel Winograd는 7단계 곱셈이 실제로 2×2 행렬의 절대 최소값임을 보여주었습니다.
Strassen은 동일한 아이디어를 사용하여 모든 더 큰 n×n 행렬을 n3 단계 미만으로 곱할 수도 있음을 보여주었습니다. 이 전략의 핵심 요소에는 분해라는 절차가 포함됩니다. 즉, 큰 행렬을 더 작은 부분행렬로 분해하는 것입니다. 이 부분행렬은 결국 2×2 또는 심지어 1×1(단지 단일 숫자)만큼 작아질 수 있습니다.
거대한 배열을 작은 조각으로 나누는 이유는 매우 간단합니다. MIT의 컴퓨터 과학자인 Virginia Vassilevska Williams는 "큰 행렬(예: 100×100 행렬)의 경우 인간이 생각하기 어렵습니다. 최고의 알고리즘입니다.” 3 by 3 행렬도 아직 완전히 풀리지 않았습니다. "그러나 작은 행렬을 위해 개발된 빠른 알고리즘을 사용하면 더 큰 행렬을 위한 빠른 알고리즘을 얻을 수 있습니다."
연구원들은 속도의 핵심은 곱셈 단계 수를 줄여 n3에서 지수를 이동시키는 것이라고 판단했습니다. 가능한 한 (전통적인 방법) 줄입니다. 가능한 가장 낮은 값 n²은 기본적으로 답을 작성하는 데 걸리는 시간입니다. 컴퓨터 과학자들은 이 지수를 Ω 또는 Ω라고 부릅니다. nΩ는 n이 커짐에 따라 두 개의 n×n 행렬을 성공적으로 곱하는 데 필요한 최소 단계 수입니다. 2024년 1월 논문의 공동 저자이기도 한 Zhou Renfei는 "이 연구의 초점은 2에 얼마나 가까워질 수 있는지, 그리고 그것이 이론적으로 달성될 수 있는지 확인하는 것입니다."라고 말했습니다.
1986년에 Strassen은 또 다른 획기적인 발전을 이루며 행렬 곱셈의 레이저 방법을 도입했습니다. Strassen은 이를 사용하여 2.48의 Ω에 대한 상한 값을 결정했습니다. 이 방법은 대규모 행렬 곱셈의 한 단계일 뿐이지만, 연구자들이 지속적으로 이 방법을 개선하고 있기 때문에 가장 중요한 방법 중 하나입니다.1년 후, Winograd와 Don Coppersmith는 레이저 방식을 완벽하게 보완하는 새로운 알고리즘을 도입했습니다. 이러한 도구 조합은 행렬 곱셈 가속화에 관한 거의 모든 후속 연구에 사용되었습니다.
다음은 이러한 다양한 요소가 어떻게 조화를 이루는지 확인하는 간단한 방법입니다. 두 개의 큰 행렬 A와 B로 시작하여 이를 곱해 보겠습니다. 먼저 이를 청크라고도 하는 여러 개의 작은 하위 행렬로 나눕니다. 다음으로, Coppersmith와 Winograd의 알고리즘을 이러한 블록을 처리하고 궁극적으로 조립하기 위한 가이드로 사용할 수 있습니다. Vassilevska Williams는 "무엇을 곱하고 무엇을 추가해야 하는지, 어떤 요소가 제품 매트릭스 C의 어디에 있는지 알려줍니다"라고 말했습니다. "이것은 A와 B에서 C를 구축하기 위한 '레시피'일 뿐입니다." 그러나 문제가 있습니다. 때때로 공통 요소가 있는 블록이 생성됩니다. 이러한 공통 요소를 유지하는 것은 이러한 요소를 두 번 계산하는 것과 동일하므로 어느 시점에서는 이러한 중복을 제거해야 합니다. 연구원들은 블록이 포함된 블록을 "삭제"하여 이 문제를 해결했습니다. 즉, 해당 구성 요소를 0으로 설정하여 계산에서 제거했습니다. ㅋㅋㅋ Virginia Vassilevska Williams는 다음 팀 중 하나입니다. 행렬 곱셈이라는 새로운 방법을 개량한 멤버들이었고, 현재 가장 빠른 방법을 생각해 냈습니다. 여기서 Strassen의 레이저 방법이 마침내 작동하게 됩니다. "레이저 방법은 일반적으로 매우 효과적이며 종종 겹치는 하위 블록을 제거하는 좋은 방법을 찾습니다."라고 Le Gall은 말했습니다. 레이저가 모든 중복을 제거한 후 최종 제품 매트릭스 C를 구성할 수 있습니다.이러한 다양한 기술을 결합하면 적어도 이론적으로는 총 곱셈을 최대한 적게 하면서 두 행렬을 곱하는 알고리즘이 탄생합니다. 레이저 방법은 실용적인 응용을 위한 것이 아니며 단지 행렬 곱셈에 대한 이상적인 방법일 뿐입니다. Zhou Renfei는 "우리는 이 방법을 컴퓨터에서 실행한 적이 없으며 분석합니다."라고 말했습니다. 10년 이상 동안 Ω의 가장 큰 개선에 기여한 것은 바로 이 분석입니다.
"숨겨진 손실" 발견Duan Ran, Zhou Renfei 및 Hongxun Wu의 첫 번째 논문 "Faster Matrix Multiplication via Asymmetric Hashing"에서 Strassen 알고리즘의 프로세스가 크게 가속화될 수 있음을 보여주었습니다. 이는 모두 '숨겨진 손실'이라는 개념 덕분이다. Zhou Renfei는 이 개념이 이전 분석에서 깊이 숨겨져 있었으며 실수로 너무 많은 블록을 제거한 결과라고 말했습니다.
레이저 방법은 겹치는 블록을 가비지로 표시하고 처리 일정을 예약하는 방식으로 작동하며, 다른 블록은 가치 있는 것으로 간주되어 저장됩니다. 그러나 선택 과정은 다소 무작위입니다. 실제로 쓰레기로 표시된 블록은 결국 유용할 수 있습니다.
전적으로 놀라운 일은 아니지만 Duan Ran의 팀은 많은 무작위 선택을 조사한 결과 레이저 방법이 체계적으로 블록의 가치를 과소평가하므로 더 많은 블록을 저장하고 더 적은 양의 블록을 버려야 한다고 판단했습니다. 그리고 종종 그렇듯이 낭비가 적을수록 효율성이 높아집니다.
Duan Ran 팀의 접근 방식에 대해 Le Gall은 "겹침 없이 더 많은 블록을 유지할 수 있습니다. 이 접근 방식은 더 빠른 행렬 곱셈 알고리즘을 달성합니다."라고 믿습니다.
이 손실의 존재를 증명한 후 Duan Ran 팀은 레이저를 사용하는 방식을 수정했습니다. 방법은 블록을 표시하여 낭비를 크게 줄입니다. 그들은 2.371866 부근에서 Ω에 새로운 상한선을 설정했는데, 이는 2020년 Josh Alman과 Vassilevska Williams가 설정한 2.3728596 상한선보다 향상된 것입니다.
상한을 약 0.001만큼 낮추는 것은 작은 변화처럼 보일 수도 있지만, 이는 2010년 이후 과학자들이 본 가장 큰 개선입니다
. 이에 비해 Vassilevska Williams와 Alman의 2020년 결과는 이전 결과보다 단 0.00001 향상되었습니다.
로 낮췄습니다.
연구원들은 또한 그래프 이론, 기계 학습 및 기타 분야에서 널리 사용되는 직사각형(n×m) 행렬의 곱셈 과정을 개선하기 위해 동일한 방법을 사용했습니다.
이러한 측면에서 추가적인 진전이 거의 확실하지만 한계가 있습니다. 2015년 르 갈(Le Gall)과 두 명의 공동 저자는 현재의 방법, 즉 레이저 방법이 Coppersmith 및 Winograd의 방법과 결합되어 2.3078 이하의 Ω를 얻을 수 없음을 보여주었습니다. Le Gall은 "더 개선하려면 1987년 이후 크게 변하지 않은 Coppersmith와 Winograd의 원래 방법을 개선해야 합니다."라고 말했습니다. 하지만 지금까지 더 나은 방법을 제안한 사람은 없습니다. 어쩌면 전혀 그렇지 않을 수도 있습니다.
Zhou Renfei는 다음과 같이 말했습니다. "Ω를 개선하는 것은 실제로 이 문제를 이해하는 것의 일부입니다. 이 문제를 잘 이해할 수 있다면 더 나은 알고리즘을 설계할 수 있습니다. 그러나 이 고대 문제에 대한 사람들의 이해는 아직 매우 초보적인 수준에 있습니다. 》
원본 링크:https://www.Quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/
위 내용은 Tsinghua Yao 학부생들은 10년 만에 가장 큰 발전인 두 작품을 연속으로 출판했습니다. 행렬 곱셈은 이론적 최적에 가깝습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!