MIT证明:解决超大规模问题,算法比硬件更有用
本文经AI新媒体量子位(公众号ID:QbitAI)授权转载,转载请联系出处。
软件算法对计算速度的提升有多大?
MIT最新研究说:超过4成算法对性能的改进,已经超过了硬件的摩尔定律。
对于中等规模的问题,30%-43%的算法的改进比硬件进步更能提升性能。
当问题数据增加到数亿规模时,算法改进变得比硬件改进/摩尔定律更重要。
这就是MIT的两位科学家对来自57本教科书,超过1137篇研究论文的数据进行分析后得到的结论。
![MIT证明:解决超大规模问题,算法比硬件更有用](https://s6.51cto.com/oss/202109/23/8983e403e3408e953c7243cc253807cd.jpg)
不仅如此,他们还全面叙述了现有以及历史上的算法何时被发现、如何改进、以及改进的规模。
14%的算法改进率超过1000%
研究者通过分析QS排名中前20的计算机名校所用的课件,总结出11个算法子领域:
组合学、统计学/机器学习、密码学、数值分析、数据库、操作系统、计算机网络、机器人学、信号处理、计算机图形/图像处理、生物信息学。
通过分析子领域中的算法教材、学术期刊、已发表论文等信息,研究者划分出了113个算法家族,平均每个家族8个算法。
他们首先统计了从1940年到现在,各种算法的最初提出时间:
![MIT证明:解决超大规模问题,算法比硬件更有用](https://s4.51cto.com/oss/202109/23/833be9a4c29af2c8ce9e1b1594fdc7ae.jpg)
并且根据这些算法最初被提出时的时间复杂度进行了归纳。可以看到,其中31%的算法属于指数复杂度类别:
![MIT证明:解决超大规模问题,算法比硬件更有用](https://s2.51cto.com/oss/202109/23/f3d4550250b3e121389482d4752514aa.jpg)
在时间复杂度的改进上,对于n=100万的问题规模,一些算法比硬件或摩尔定律的改进率更高:
△算法改进对四个算法家族的影响
将这一分析拓展到110个算法家族上时,可以看到,对于中等规模(n=1000)的问题来说,只有18%的算法改进率快于硬件。
但当问题规模来到了百万、亿、甚至万亿级别时,算法的改进速度就超过了硬件性能。
甚至有14%的算法家族的改进率超过1000%,远超硬件改进所带来的性能提升。
△a:n=一千 b:n=一百万 c:n=一亿
作者介绍
论文一作Yash Sherry本科毕业于印度德里大学计算机科学专业,现在是MIT斯隆商学院的一位研究员,工作重点是跟踪算法的改进及其对IT公司经济的影响。
![MIT证明:解决超大规模问题,算法比硬件更有用](https://s2.51cto.com/oss/202109/23/86fa754798acb7cd80c0c50738b88d5d.jpg)
另一位Neil Thompson是麻省理工大学CSAIL(计算机科学和人工智能实验室)的科学家,也是哈佛大学创新科学实验室的客座教授。
![MIT证明:解决超大规模问题,算法比硬件更有用](https://s2.51cto.com/oss/202109/23/77a81e0825004d8b31e6372fa4139b6b.jpg)
论文:
https://ieeexplore.ieee.org/document/9540991
相关文章
- Kubernetes+.NET Core 在非著名互联网公司的落地实践
- AttributeError:module 'keras.engine.topology' has no attribute 'load_weights_from_hdf5_group_by_name
- AttributeError:module ‘keras.engine.topology‘ has no attribute ‘load_weights_from_hdf5_group_by_name
- 不可或缺的IT领导者的七大特质
- Kubernetes + .NET Core 的落地实践
- 人脸检测互动游戏-源码
- 网页自动提交
- 用自洽性提升大模型推理能力,谷歌解答基准中75%数学问题,比GPT-3提升20%
- 新机遇:大厂裁员背后的周期律
- 女神也用的约会决策:决策树算法实践
- 谈谈网站的面包屑
- Linux为指定ip开放/关闭端口
- 强化学习如何做数据分析?新加坡国立等TKDE 2022综述论文
- 解决一个C#中定时任务被阻塞问题
- 斯坦福学生攻破约会软件!用GAN模型女扮男装骗过人脸识别系统
- Rockley Photonics的血糖监测硅光芯片(续)
- 教你查看 jupyter notebook 每个单元格运行时间
- 牛津大学最新调研:AI面临基准危机,NLP集中“攻关”推理测试
- 相关性矩阵图绘制方法大汇总!!
- 一文带你了解机器人是如何通过视觉实现目标跟踪的