• <menu id="s88m8"></menu>
    <nav id="s88m8"></nav><menu id="s88m8"></menu>
  • 首頁 ? 產品技術 ? 數據中心與與計算 ? MIT新研究:過去80年,算法效率提升到底有多快?

    MIT新研究:過去80年,算法效率提升到底有多快?

    作者:  時間:2021-09-23 14:15  來源:

           

    新智元報道

    來源:MIT

    編輯:David

    【新智元導讀】隨著摩爾定律走向終結,靠提升計算機硬件性能可能越發難以滿足海量計算的需要,未來的解決之道在于提升算法的效率。MIT的這篇新論文總結了過去80年來,算法效率的提升究竟有多快。

    提起算法,它有點像計算機的父母,它會告訴計算機如何理解信息,而計算機反過來可以從算法中獲得有用的東西。

    算法的效率越高,計算機要做的工作就越少。對于計算機硬件的所有技術進步,以及備受爭議的摩爾定律的壽命問題來說,計算機硬件的性能只是問題的一方面。

    而問題另一方面則在硬件之外:算法的效率問題。如果算法的效率提升了,對同一計算任務需要的算力就會降低。

    雖然算法效率問題可能不太受關注,但你是否注意到,經常使用的搜索引擎是否突然變快了十分之一,而在大型數據集中活動,就感覺就像在泥濘中跋涉一樣艱難緩慢。

    這些都與算法效率有關。

    近日,麻省理工學院計算機科學與人工智能實驗室 (CSAIL) 的科學家提出疑問:算法效率的提升速度到底有多快?

    關于這個問題,現有數據大部分是敘事性的,其中很大一部分是面向特定算法的案例研究,再把這些研究結果加以推廣。

    面對實證研究數據的不足,研究團隊主要利用了來自 57 部教科書和 1110 多篇研究論文的數據,以追溯算法效率提升的歷史。

    其中有些論文的結論中直接給出了新的算法有多高效,有的論文則需要作者使用“偽代碼”(對算法基本細節的簡單描述)進行重構。

    研究人員總共研究了 113 個“算法系”,即解決計算機科學教科書中最重要的同一問題的算法集。他們對每個算法族的歷史進行了回顧,跟蹤每次針對某一問題提出的新算法,并特別注意更高效的算法。

    圖1 算法發現和改進。(a) 每十年發現的新算法系的數量。(b) 已知算法系的比例每十年都有所提高。(c) 首次發現時算法系的漸近時間復雜度分類。(d) 同一時間復雜度的算法轉換到另一個時間復雜度的每年平均概率(反應算法系復雜度提升的平均水平)。在(c)和(d)中“>n3”的時間復雜度表示超過多項式級,但不到指數級。

    最早的算法系可追溯到上世紀40年代,每個算法系平均有 8 個算法,按時間順序效率逐步提升。為了共享這一發現,團隊還創建了“算法維基”頁面(Algorithm-Wiki.org)。

    研究人員繪制了圖表,標識這些算法族效率提升的速度,重點關注算法分析最多的特征——這些特征往往決定了解決問題的速度有多快(用計算機術語說,就是“最壞情況下的時間復雜度”)。

    圖 2 算法系的相對效率提升,使用漸近時間復雜度的變化計算。參考線是SPECInt 基準性能。(a) 與該系列中的第一個算法(n = 100 萬)相比,四個算法系的歷史改進。(b) 算法改進對“最近鄰搜索”算法系列的輸入大小 (n)的敏感度。為了便于比較算法改進效果隨時間的變化,在圖(b) 中將算法系和硬件基準的起始時間段對齊。

    結果顯示,變數很大,但也發現了關于計算機科學變革性算法效率提升的重要信息。即:

    對于大型計算問題,43% 的算法系的效率提升帶來的收益,不低于摩爾定律帶來的收益。

    在 14% 的問題中,算法效率提升的收益遠超硬件性能提升的收益。

    對于大數據問題,算法效率提升收益特別大,因此近年來,這一效果與摩爾定律相比越來越明顯。

    當算法系從指數復雜度過渡到多項式復雜度時,情況出現了最大的變化。

    所謂指數復雜度算法,就像一個人猜密碼鎖的密碼一樣。如果密碼盤上只有一位數,那么任務很簡單。如果像自行車鎖一樣,表盤是4位數,估計你的自行車很難有人偷得走,但仍然可以一個個試。如果是表盤是50位的,就幾乎不可能破解了,需要的步驟太多了。

    圖3 基于漸近時間復雜度計算的110個算法系效率提升的年平均速度分布,其中問題規模為:(a) n = 1000,(b) n = 100萬,(c) n = 10億。硬件性能提升線表示從 1978 年到 2017 年,SPECInt 基準性能的平均年增長率

    這類問題也是計算機面對的難題,隨著問題的規模越來越大,很快就會超過計算機的處理能力,這個問題光靠摩爾定律是解決不了的。

    解決之道在于找到多項式復雜度的算法。

    研究人員表示,隨著摩爾定律終結這個話題越來越多地被提及,我們需要將未來的解決方案的重點放在算法的效率提升上。

    圖4 前導常數在算法性能提升中的重要性評價

    研究結果表明,從歷史上看,算法效率的提升帶來的收益是巨大的。不過二者之間存在著頻度的差異,摩爾定律帶來的提升是平滑而緩慢的,而算法效率的提升是階梯式的躍進,但出現沒那么頻繁。

    本文通訊作者尼爾·湯普森說:

    這是業界第一篇說明算法效率提升速度的論文。通過我們的分析,可以得出算法改進后,使用同樣的算力可以完成多少任務。

    隨著問題的規模不斷增大,比如達到數十億或數萬億個數據點,算法效率的提升帶來的收益,比硬件性能的提升更重要,而且重要得多。

    在我們開始逐步為算力不足發愁的時代,在摩爾定律越來越顯出疲態的今天,這一發現可能為未來解決超大型計算問題開辟一條新的思路。

    參考鏈接:

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

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

    相關推薦

    MIT新研究:過去80年,算法效率提升到底有多快?

    MIT研究人員利用紅外攝像機和人工智能來預測“沸騰危機”

    機器人該長啥樣 MIT讓計算機“立規矩”

    服務與運營 2020-12-10

    麻省理工學院研發水下自動駕駛車輛

    被男闺蜜摸到了高潮,草蜢在线观看免费WWW,xrk1_3_0ark官网入口
  • <menu id="s88m8"></menu>
    <nav id="s88m8"></nav><menu id="s88m8"></menu>