지난 반세기 동안 집적 회로 산업은 무어의 법칙에 따라 빠르게 발전했으며 알고리즘의 효율성은 대대적으로 개선되었습니다. 2018년 세계에서 가장 빠른 컴퓨터인 IBM Summit은 1945년 세계 최초의 전자 컴퓨터 ENIAC보다 거의 30조 배 더 빨랐습니다.

그러나 무어의 법칙이 물리적 한계에 가까워지면서 칩 개발 및 생산 비용이 급격히 상승했고, 향후 컴퓨팅 성능 향상을 위해 컴퓨팅 파워에 의존할 여지가 제한적이다. 컴퓨터 하드웨어의 성능을 향상시켜 대용량 컴퓨팅 요구 사항을 충족하기가 점점 더 어려워질 수 있으므로 향후 솔루션은 알고리즘의 효율성을 향상시키는 데 있습니다.

이 새로운 MIT 논문은 알고리즘 효율성이 지난 80년 동안 얼마나 빨리 개선되었는지 요약합니다.

알고리즘에 관해서는 컴퓨터의 부모와 약간 비슷하여 컴퓨터에게 정보를 이해하는 방법을 알려주고 컴퓨터는 알고리즘에서 유용한 정보를 얻을 수 있습니다.

알고리즘이 효율적일수록 컴퓨터가 수행해야 하는 작업이 줄어듭니다. 컴퓨터 하드웨어의 모든 기술적 진보와 많은 논란이 되고 있는 무어의 법칙의 수명에도 불구하고 컴퓨터 하드웨어의 성능은 문제의 한 측면일 뿐입니다.

반면에 문제는 하드웨어 외부에 있습니다. 즉, 알고리즘의 효율성입니다. 알고리즘의 효율성이 향상되면 동일한 컴퓨팅 작업에 필요한 컴퓨팅 성능이 감소합니다.

알고리즘 효율성 문제는 그다지 중요하지 않을 수 있지만, 자주 사용하는 검색 엔진이 갑자기 10분의 1 빨라진 반면 대규모 데이터 세트를 이동하는 것이 진흙탕을 헤치고 나아가는 것처럼 느껴진다는 사실을 알고 계셨습니까?

이들은 모두 알고리즘 효율성과 관련이 있습니다.

최근 MIT CSAIL(Computer Science and Artificial Intelligence Laboratory)의 과학자들은 다음과 같은 질문을 했습니다. 알고리즘 효율성이 얼마나 빨리 향상되고 있습니까?

이 질문에 대한 기존 데이터의 대부분은 내러티브이며, 그 중 상당 부분은 특정 알고리즘에 대한 사례 연구이며 이러한 연구 결과는 일반화됩니다.

실증적 연구 데이터가 부족한 상황에서 연구팀은 주로 교과서 57종과 연구 논문 1110여편의 데이터를 활용해 알고리즘 효율 개선 이력을 추적했다.

이 논문 중 일부는 결론에서 새 알고리즘이 얼마나 효율적인지 직접적으로 보여주고, 다른 논문은 작성자가 "의사 코드"(알고리즘의 기본 세부 사항에 대한 간단한 설명)를 사용하여 재구성하도록 요구합니다.

연구원들은 총 113개의 "알고리즘 라인" 또는 컴퓨터 과학 교과서에서 가장 중요한 동일한 문제를 해결하는 알고리즘 모음을 살펴보았습니다. 그들은 각 알고리즘 계열의 역사를 검토하고 문제에 대해 새로운 알고리즘이 제안될 때마다 추적하며 보다 효율적인 알고리즘에 특별한 주의를 기울입니다.

그림 1 알고리즘 발견 및 개선. (a) 10년 동안 발견된 새로운 알고리즘 계열의 수. (b) 알려진 알고리즘 계열의 비율은 10년마다 증가했습니다. (c) 처음 발견되었을 때 알고리즘 계열의 점근적 시간 복잡도 분류. (d) 한 시간 복잡도의 알고리즘에서 다른 시간 복잡도의 알고리즘으로 전환할 평균 연간 확률(알고리즘 시스템의 평균 복잡도 증가 수준 반영). (c)와 (d)에서 ">n3"의 시간 복잡도는 다항식 수준 이상이지만 지수 수준보다는 작음을 의미한다.

가장 초기의 알고리즘 부서는 1940년대로 거슬러 올라갈 수 있으며 각 알고리즘 부서는 평균 8개의 알고리즘을 가지고 있으며 시간순으로 효율성이 점차 향상됩니다. 이 발견을 공유하기 위해 팀은 "Algorithm Wiki" 페이지(Algorithm-Wiki.org)도 만들었습니다.

연구원들은 알고리즘의 가장 많이 분석된 특성, 즉 문제를 얼마나 빨리 해결할 수 있는지 결정하는 경향이 있는 특성에 초점을 맞춰 이러한 알고리즘 제품군의 효율성이 얼마나 빨리 개선되었는지 차트로 표시했습니다(컴퓨팅 용어로 "최악의 경우 시간 복잡성"). ).

그림 2 점근적 시간 복잡도 변화를 사용하여 계산된 알고리즘 계열의 상대적 효율성 이득. 기준선은 SPECInt 기준선 성능입니다. (a) 시리즈의 첫 번째 알고리즘(n = 100만)과 비교하여 4개의 알고리즘 제품군에 대한 역사적 개선 사항. (b) 알고리즘의 "최근접 이웃 검색" 계열의 입력 크기(n)에 대한 알고리즘 개선의 감도. 시간 경과에 따른 알고리즘의 개선 효과 비교를 용이하게 하기 위해 그림 (b)에서 알고리즘 시스템과 하드웨어 벤치마크의 초기 기간을 정렬합니다.

결과는 다양한 변수를 보여주지만 컴퓨터 과학에서 변환 알고리즘의 효율성 향상에 대한 중요한 정보도 발견합니다. 지금 바로:

1. 대규모 컴퓨팅 문제의 경우 알고리즘 시스템의 43% 효율성 향상으로 인한 이점은 무어의 법칙에 의한 이점보다 작지 않습니다.

2. 문제의 14%에서 알고리즘 효율성 향상의 이점이 하드웨어 성능 향상의 이점을 훨씬 능가합니다.

3. 빅데이터 문제의 경우 알고리즘 효율성 향상의 이점이 특히 크므로 최근 몇 년 동안 무어의 법칙과 비교하여 이 효과가 더욱 분명해졌습니다.

가장 큰 변화는 알고리즘 시스템이 지수 복잡도에서 다항식 복잡도로 전환될 때 발생합니다.

소위 지수 복잡도 알고리즘은 조합 잠금의 암호를 추측하는 사람과 같습니다. 조합 디스크에 숫자가 하나만 있으면 작업이 쉽습니다. 다이얼이 자전거 자물쇠처럼 4자리면 누군가가 자전거를 훔쳐가기는 어려울 것으로 추정되지만 그래도 하나씩 시도해볼 수는 있다. 다이얼이 50자리이면 크랙이 거의 불가능하고 너무 많은 단계가 필요합니다.

그림 3. 점근적 시간복잡도 계산에 기반한 110개 알고리즘 시스템의 연간 평균 속도 분포. 여기서 문제 크기는 (a) n = 1000, (b) n = 100만, (c) n = 10억입니다. 하드웨어 성능 개선 라인은 1978년부터 2017년까지 SPECInt 벤치마크 성능의 연평균 성장률을 나타냅니다.

이런 문제는 컴퓨터가 직면한 문제이기도 한데, 문제의 규모가 점점 커질수록 곧 컴퓨터의 처리능력을 넘어서게 되는데, 무어의 법칙만으로는 해결할 수 없는 문제이다.

해결책은 다항식 복잡성의 알고리즘을 찾는 데 있습니다.

이미지 설명

그림 4 알고리즘 성능 향상에서 선행 상수의 중요성 평가

연구 결과는 역사적으로 개선된 알고리즘 효율성의 이점이 상당했음을 시사합니다. 그러나 둘 사이에는 빈도의 차이가 있는데, 무어의 법칙에 의한 개선은 부드럽고 느린 반면, 알고리즘 효율성의 개선은 단계적 도약이지만 덜 자주 발생합니다.

교신저자인 Neil Thompson은 다음과 같이 말했습니다.

이것은 알고리즘 효율성이 향상되는 속도를 설명하는 업계 최초의 논문입니다. 분석을 통해 알고리즘이 개선된 후 동일한 컴퓨팅 성능으로 얼마나 많은 작업을 완료할 수 있는지 알 수 있습니다.

문제의 크기가 수십억 또는 수조 개의 데이터 포인트로 커짐에 따라 알고리즘 효율성의 이점이 하드웨어 성능의 이점보다 훨씬 더 큽니다.

참조 링크:

참조 링크:

https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991

에디터: Sue, Interstellar Vision