過去半世紀にわたり、集積回路産業はムーアの法則の導きの下で急速に発展し、アルゴリズムの効率は大幅な向上を維持してきました。 2018 年、世界最速のコンピューターである IBM Summit は、1945 年の世界初の電子コンピューター ENIAC よりも約 30 兆倍高速でした。

しかし、ムーアの法則が物理的な限界に近づいているため、チップの開発と生産のコストが大幅に上昇しており、将来的にコンピューティング性能を向上させるためにコンピューティングパワーに依存する余地は限られています。コンピュータハードウェアの性能向上によって大規模コンピューティングのニーズを満たすことはますます困難になる可能性があり、将来の解決策はアルゴリズムの効率を向上させることにあります。

この新しい MIT 論文は、過去 80 年間でアルゴリズムの効率がいかに急速に向上したかを要約しています。

アルゴリズムに関しては、アルゴリズムはコンピューターの親のようなもので、情報を理解する方法をコンピューターに伝え、コンピューターはアルゴリズムから有用なものを得ることができます。

アルゴリズムが効率的であればあるほど、コンピューターが実行する作業が少なくなります。コンピューター ハードウェアにおける技術の進歩と、よく議論されているムーアの法則の寿命にもかかわらず、コンピューター ハードウェアのパフォーマンスは問題の 1 つの側面にすぎません。

一方、問題はハードウェアの外側、つまりアルゴリズムの効率にあります。アルゴリズムの効率が向上すると、同じ計算タスクに必要な計算能力が削減されます。

アルゴリズムの効率性の問題はそれほど問題ではないかもしれませんが、頻繁に使用する検索エンジンが突然 10 分の 1 速くなり、大規模なデータセットを移動するのが泥の中を歩いているように感じられることに気づいたことがありますか?

これらはすべてアルゴリズムの効率に関係しています。

最近、MIT のコンピューター サイエンスおよび人工知能研究所 (CSAIL) の科学者たちは、「アルゴリズムの効率はどれくらいの速さで向上しているのでしょうか?」と尋ねました。

この問題に関する既存のデータの多くは物語的なものであり、その大部分は特定のアルゴリズムのケーススタディであり、これらの研究の結果は一般化されています。

実証的な研究データの不足に直面し、研究チームは主に57冊の教科書と1110件以上の研究論文のデータを使用して、アルゴリズムの効率向上の歴史を追跡した。

これらの論文の中には、結論の中で新しいアルゴリズムがどれほど効率的であるかを直接示しているものもあれば、著者が「疑似コード」（アルゴリズムの基本的な詳細の簡単な説明）を使用してアルゴリズムを再構築する必要があるものもあります。

研究者らは合計 113 の「アルゴリズム ライン」、つまりコンピューター サイエンスの教科書で最も重要な同じ問題を解決するアルゴリズムのコレクションを調査しました。彼らは各アルゴリズム ファミリの歴史をレビューし、問題に対して新しいアルゴリズムが提案されるたびに追跡し、より効率的なアルゴリズムに特に注意を払います。

図 1 アルゴリズムの発見と改善。 (a) 10 年ごとに発見された新しいアルゴリズム ファミリの数。 (b) 既知のアルゴリズム ファミリの割合は 10 年ごとに増加しています。 (c) 最初に発見されたときのアルゴリズム族の漸近時間計算量の分類。 (d) ある時間の複雑さのアルゴリズムから別の時間の複雑さのアルゴリズムに切り替わる平均年間確率 (アルゴリズム システムの複雑さの平均増加レベルを反映)。 (c) と (d) の「">n3」の時間計算量は、多項式レベル以上、指数関数レベル未満を意味します。

最も初期のアルゴリズム部門は 1940 年代にまで遡り、各アルゴリズム部門には平均 8 個のアルゴリズムがあり、時系列に沿って徐々に効率が向上していきました。この発見を共有するために、チームは「アルゴリズム Wiki」ページ (Algorithm-Wiki.org) も作成しました。

研究者らは、最もよく分析されているアルゴリズムの特性、つまり問題をどれだけ早く解決できるかを決定する傾向にある特性に焦点を当て、これらのアルゴリズム群の効率がどの程度早く向上したかをグラフ化した(コンピューティング用語では「最悪の場合の複雑さ」)。 ）。

図 2 漸近的な時間計算量の変化を使用して計算された、アルゴリズム ファミリの相対効率ゲイン。基準線は SPECInt のベースライン パフォーマンスです。 (a) シリーズの最初のアルゴリズムと比較した 4 つのアルゴリズム ファミリの歴史的改善 (n = 100 万)。 (b) 「最近傍検索」ファミリーのアルゴリズムの入力サイズ (n) に対するアルゴリズムの改善の感度。時間の経過に伴うアルゴリズムの改善効果の比較を容易にするために、図 (b) では、アルゴリズム システムとハードウェア ベンチマークの初期期間を揃えています。

結果は、さまざまな変数を示していますが、コンピューター サイエンスにおける変革的アルゴリズムの効率向上に関する重要な情報も明らかにしています。今すぐ：

1. 大規模なコンピューティング問題の場合、アルゴリズム システムの 43% の効率向上によってもたらされる利点は、ムーアの法則によってもたらされる利点に劣りません。

2. 問題の 14% では、アルゴリズムの効率を向上させるメリットが、ハードウェアのパフォーマンスを向上させるメリットをはるかに上回っています。

3. ビッグデータ問題では、アルゴリズムの効率化による効果が特に大きく、近年ではその効果がムーアの法則に比べて顕著になってきています。

最大の変化は、アルゴリズム システムが指数関数的な複雑さから多項式の複雑さに移行するときに発生します。

いわゆる指数関数的複雑さのアルゴリズムは、人がダイヤル錠のパスワードを推測するようなものです。組み合わせディスクに 1 桁しかない場合、作業は簡単です。自転車の鍵のようにダイヤルが 4 桁の場合、誰かが自転車を盗むのは難しいと推定されますが、1 つずつ試すことはできます。ダイヤルが 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

編集者: スー、Interstellar Vision