アルゴリズムのサービスにおける鉄（続き）

コンピューティングの過去、現在、未来に関するボリス・ババヤン

この作業の最初の部分が公開されてからほぼ3か月が経過しました。 この間ずっと、2番目の部分は熟成しており、...最終的に熟成しました！

前の部分と同様に、物語はババヤンに代わって作成されます。 コメントのほとんどをサイドバーまたはWebページへのリンクとして設計しました。


432番目のマシンが故障した後、全世界が高級言語のハードウェアサポートを放棄しました。 彼らは84年目にそれを忘れてしまったが、それを再び覚えていない。 誰もがこれは美しいアイデアであると信じていますが、実用的ではありません。 このアイデアを完全に実装したにもかかわらず、実装は効果的であると考えられています。

しかし、高水準言語はどこで終わったのでしょうか？ 現在のすべての高水準言語は2つのグループに分けることができます。1つはJavaなどの言語を含み、もう1つはCなどです。Javaは厳密な型制御ですが、非常に非効率的です。 そして、スピーカーはいません。 誰もJavaオペレーティングシステムを書くことを考えていません。 私の基準では、これは高度な汎用言語ではありません。 別のグループはCライクな言語です。 一般的な意見は、これらは高級言語ではないということです。 むしろ、アセンブラーバリアントです。

エルブラスの子供たちを除いて、世界中の誰もが高水準言語の本当の利点を知っていないことがわかります。 そして、それはひどいです！

さて、これらの利点を得るには何が必要ですか？ ほんの少し。 簡単です。

まず第一に、言語と機器では、空間と時間の2種類の記述子が導入されます。 空間記述子は、実際にはデータへのポインターです。 たとえば、配列のサイズと配列の先頭のアドレスを含めることができます。 このような記述子を使用した一般的な操作は、インデックス付け（配列の特定の要素へのアクセス）とサブ配列の取得です。 合計で、データへのポインターに対する操作は非常に少数です。

ここで重要な点は、メモリの読み取りおよび書き込み操作のベースアドレスは、そのようなポインタからのみ取得できることです。 彼らの助けを借りて、装置はアレイ境界の出口を制御します。 他の空間記述子が与えるものについては、後で「コンテキスト保護」について話すときに言います。

現在、一時記述子は関数へのポインタであり、何らかのプロシージャを開始する権利です。 関数へのポインターには遷移アドレスが含まれています。 Elbrusの時代には、上位レベルのアドレス指定、つまり静的にネストされたプロシージャが一般的でした。
したがって、関数へのポインタには、この関数が記述されたプロシージャのグローバルデータへの参照も含まれていました。 つまり、プロシージャAがプロシージャB内に記述されている場合、プロシージャAは一般的にプロシージャBで使用可能なすべてのデータにアクセスできます。したがって、関数Aの記述子には、最初に遷移アドレスがあり、次にリンクがあります関数Bのグローバルデータ。さらに、Bの特定のインカネーションのグローバルデータ。これについて説明します。 再帰呼び出しのチェーンの結果として、プロシージャBには複数の化身が同時に存在する可能性があります。 各化身には、独自のグローバルデータがあります。 このため、Bの異なるインカネーション内で生成された関数Aへのポインターは異なるポインターになります。 それらは、カバー手順の異なるコピーに対応するデータを参照します。

ここで、ディスクリプタアプローチの普遍性の観点から一般的な結論を導き出すことができます。オペレーティングシステムには特権モードがありません。 そのような概念は必要ありません。 特権モードがない場合、システムプログラミングの概念はありません。 つまり、オペレーティングシステムは通常のユーザープログラムです。 プロシージャの一部はどのアプリケーションからもアクセス可能であるという意味で、他のアプリケーションにより単純に広く知られています。 このようなシステムで特権モードが必要ない理由を説明します。

プロシージャが開始されると、最初はレジスタのみにアクセスできます。 すべてのレジスタが利用可能です。 しかし、それらに記述子がない場合、これらのレジスタ以外ではプロシージャは機能しません。 メモリの読み取り操作もメモリへの書き込み操作も機能しません（プロシージャで空間ポインタを使用できないため）。 レジスタ上にポインタが1つだけある場合、プロシージャは1つのオブジェクト（ポインタが参照するオブジェクト）のみにアクセスできます。

つまり、各プロシージャにはコンテキストがあります。 私たちはそれを「コンテキスト防御」とさえ呼びました。

ここで、ある時点での手順で新しい配列が必要になったとしましょう。 そして、これは現代のシステムで最も特権的なアクションの1つです。 Elbrusでは、このためにオペレーティングシステムのコンテキストが使用されました。 関数へのポインタが含まれていました。 「新しい配列を与える」関数へのポインタを含める。 バローズのオペレーティングシステムでは、「スペースを取得」と呼ばれていました。

「スペースの取得」などのプロシージャが起動されると、それを呼び出したプロシージャのコンテキストがスタック上で閉じられ、「スペースの取得」自体のコンテキストが開きます。 この文脈では、一般的に言えば、巨大な記述子があります。 すべての仮想メモリへ。 また、ユーザーは、たとえば「スペースを取得」を起動するときに、25ワードの配列を要求しました。 「スペースを取得」には、占有されている場所と空きがある場所を示すテーブルがあります。 彼女は空き領域を見つけて、特権のない操作を実行します。サブアレイを取得します。 その結果、プロシージャが新しい配列に提供するメモリの記述子が取得されます。 さらに、それに応じてテーブルが調整されます。

getスペースから戻った後、それを呼び出したプロシージャのコンテキストが拡張されました。 そして、これには特権アクションは必要ありませんでした。

もちろん、各プロシージャはそのアクションのセマンティクスに責任があることを覚えておく必要があります。 「メモリを割り当てる」手順でメモリの割り当てにエラーがある場合、メモリの割り当ては不十分です。 ただし、これはプロシージャ自体のセマンティクスです。 ただし、ハードウェアレベルでプロシージャのセマンティクスを検証することはできません。

次に参照してください...記述子は変更できないと言われていることからくるようです。 しかし、これは真実ではありません。 必要に応じて記述子を変更できます。 繰り返しますが、特権モードはありません。 方法をご覧ください。 マシンには、記述子を変更できる操作があります。 ただし、これらは特別なプロシージャ内に縫い付けられており、そのコンテキストでは、これらの操作を使用できる特別なパラメータが指定されています。 そのようなプロシージャは非常に少なく、それらへのポインタは少数のシステムプロシージャのコンテキストにのみあります。 記述子の「手動」変更は、他の手順では使用できません！

たとえば、「メモリを与える」プロシージャには、記述子を変更できる関数へのポインタがあります。 事実、実際には、前述の巨大な記述子は使用していません 。 説明のためだけに言及しました。 実際には、大きな記述子は非常に不便です。なぜなら、 大きな仮想アドレスにつながります。 新しく作成された記述子は、多くのスペースを占有します。 さらに、「スペースの取得」は、ハードウェアを介して任意のポインターを発行できます。 彼女はすべてのメモリにアクセスできます。 なぜ彼女に直接記述子を作成させないのですか？

これにより、サイズが小さくなります。 「スペースを取得」して、メモリを割り当て、目的の記述子を描画します。 彼女を除いて、とにかく誰もこれを行うことができません 彼女だけがこれに必要なコンテキストを持っています。

公平には、記述子を変更する操作の使用を許可する特別なパラメーターが実際に特権モードを設定することに注意する必要があります。 しかし、これは純粋に技術的な特権です。 例で仮想メモリ全体の巨大な記述子で示したように、哲学的にはそのような特権は必要ありません。

次に、コンテキスト保護が提供するものを確認します。 デバッグは非常に簡単です。 エラーがないことがわかっている巨大なプログラムがあるとします。 これが理論的に証明されていると仮定します。 ここで誇張できますが、言いましょう。 ここで、プログラムが絶対に正しいことを知らないユーザーに、デバッグされていない新しい手順を追加してみましょう。 この手順では正しい結果が得られますが、同時に他の人のデータが損なわれます。 ユーザーにとって、これは巨大なプログラム全体のエラーのように見えます。 さらに、彼が追加した手順は正しい結果を与えるため、ユーザーはおそらく、エラーが自分の手順ではなくメインプログラムにあると判断するでしょう。 彼はすでにデバッグされたコードをデバッグする準備ができているはずです。 そして、これは現代のすべてのアーキテクチャに当てはまります。 この状況は、拡張可能なコードが巨大になる可能性があり、それを書いた人々が長い間終了する可能性があるという事実によってさらに悪化します。 そのようなシステムをデバッグしてください... Elbrusでは、これは単純に不可能でした。 Elbrusでは、単にプログラムを実行し、デバッグされたプロシージャのすべての出口で停止を設定します。 次に、出口で彼女の仕事の結果を確認します。 彼らがあなたを満足させるなら、あなたはデバッグされた手順を忘れることができます。 彼女はあなたに害を与えません。 これにより、プログラミングが大幅に簡素化されます。

すべてがメモリに入力されるため、デバッグはメモリダンプをチェックするだけで実行できます。 Elbrusの2号車を引き渡すと、SRCETのプロジェクトマネージャーであるLenya Raikovが出席しました。 また、NICEVTはIBMマシンをコピーした組織です。 次に、オペレーティングシステムを作成しました。 多くの場合、100台の端末が機能します。 多くの場合、何らかのエラーがあります。 私たちはメモリダンプを取りました。 それは構造化され、タイプがあります。 プログラマーは2時間座って、オペレーティングシステムを修正しました。 レーニャ・ライコフはinした！ なぜなら、IBMオペレーティングシステムでエラーが検出された場合、数か月間このエラーに到達する必要があるからです。

マシンで記述子のサポートを提供するために必要なものを見てみましょう。 ここで最も難しいことは、64ビットごとにタグに1ビットを追加で割り当てることです。ECCコードがメモリに実装されている場合、それは簡単です。 Elbrus-3にはECCコードがあるため、問題はありませんでした。 しかし現在、多くのマシンにはECCコードはありません。 次に、何かを考え出す必要があります。 もちろん、記述子のサポートをそれらに結び付けたくない限り。

余分なビットが唯一の難しさです。 残りは簡単です。 2種類の記述子を導入する必要があります-これは基本です。 記述子を使用した操作はパフォーマンスに影響しません。 めったに実行されません。 このような操作の実装は簡単です。 ここで最も重要なことは、メモリの書き込みおよび読み取り操作に必要なチェックを追加することです。

このすべての後、メモリクリーニングを追加します。 次に、それが何であるかを説明します。

プログラマが何らかの種類のメモリを使用して解放したとします。 解放されたメモリには古い記述子が含まれている可能性があるため、クリーンアップする必要があります。 メモリが消去されない場合、これらの記述子は新しい手にある可能性があります。そして、これは保護違反になります。 したがって、メモリをクリーニングする必要があります。 しかし、それはシンプルであり、オペレーティングシステムであり、今すぐ実行できます。

クリーンなメモリへのポインタを処理することはより困難です。 メモリが解放された後、メモリへのすべてのポインタを見つけて破棄する必要があります。 それ以外の場合、解放されたメモリが再び再利用された後、これらのポインターを使用して、他の人のオブジェクトにアクセスできます。

この問題をどのように解決しましたか？ ごみの男性を紹介しませんでした 私たちのオペレーティングシステムは、常に発生ベースでメモリを分散し、再利用しません。 メモリが不足すると、オペレーティングシステムはメモリの穴を収集します。 これは、バックグラウンドでメモリ全体の単一パスで実行されますが、ユーザーアプリケーションは停止しません。 このパッセージ中に、ある記述子が穴を見ていることが発見された場合、それは殺されます。 それだけです！ さらに、すべてのメモリは単純に圧縮され、記述子のアドレスは必要に応じて変更されます。

以前は、プログラムがすべてのメモリを使用することはまれであったため、実際には圧縮はほとんど発生しませんでした。 おそらく現代のシステムではこれは当てはまらないでしょう。

ここで説明したアルゴリズムは、ヒープアルゴリズムです。 スタック上では、ハングしたポインターのクリーンアップは少し難しくなります。 スタックではメモリを積極的に再利用するため、スタックで同じことを行うことはできません。 しかし、小さなハードウェアデバイスの助けを借りて、スタックをクリーニングすることもできます。 最初、2番目のElbrusでは、プログラムでクリーニングしましたが、今ではそうではなく、機器の助けを借りて効率的に必要になりました。 そして、あなたもこれを行うことはできません。 言語レベルで困難な状況を単純に禁止できます。 次に説明します。

単一の問題のために、複雑なスタッククリーニングメカニズムを導入する必要があります。ローカルプロシージャデータを参照する記述子をグローバルに書き込むことができるためです。 これは非常に悪いプログラミングスタイルですが、時々発見されます。 たとえば、オペレーティングシステムを開発する場合。 良い方法では、そのような状況は禁止されなければなりません。 その後、機器に不必要な問題はありません。

それだけです！ 私が説明した困難に加えて、困難はありません。 つまり、オブジェクトのサポートに費用はかかりません！ しかし、これはまだどの車にもありません！ただの災害です、分かりますか？ 高レベルのプログラミングなどのプロパティはまだ存在しません。

上で話したことはすべて、空間コンポーネントにほぼ完全に関連していました。

次に、一時的なコンポーネントを見てみましょう。 私が言ったように、それはすべてビットシリアルマシンから始まりました。 その後、機器は徐々に拡大し、拡大しました。 まあ、彼らが最初にしたことは、ビット演算をワード演算に置き換えることでした。 私がITMiVTに来たとき、そして私はPhysics and Technology Instituteで勉強しましたが、議論がありました。 Sergey Alekseevich Lebedevが開始しました。 車は平行であるべきだと主張されました。 次に、算術演算内で並列性が考慮されました。 オペレーションを並列に並列に実行できるとはまだ誰も考えていませんでした。 そのため、オペレーション内に並列性が導入されました。 その後、算術の実装の背後にあるロジックを加速するだけで、アーキテクチャを改善することができました。 他は与えられなかった。 プログラムの実行時間は、プログラムに含まれる算術演算の実行時間の合計で構成されていたためです。

そして、演算を加速する作業が始まりました。 自慢できること：私の最初の科学研究-物理学と技術の4年目である54年目に、これはキャリーセーブ演算の導入です。 今、算術に従事している人はこれをよく知っています。 これは、乗算、除算、および桁を転送しない平方根です。 かなり明白でシンプルなこと。 それはすべての重要な操作の基礎です。 2つの基本的なアルゴリズムがあります。 そのうちの1つをPhysTech会議で55年目に発表しました。 同じトピックに関する最初の西洋の公開出版物は、56年目に出版されました。 ナドラー出版。つまり、1年前にこのことを公開しました。 しかし、残念ながら、私の仕事の結果に基づく記事は、1958年にMIPT会議の議事録の最初の号でのみ公開されました。

算術の2番目の基本的なキャリーセーブアルゴリズムは、2より大きい基数を持つ数体系で最初のアルゴリズムのアクションを実行する方法を示します。 たとえば、4進数または8進数で。 マルチビット演算の導入により、操作の総数が削減されます。 このアイデアとその実装は、ロバートソンに属します。58年目に彼はモスクワに来て、私たちは彼とよく話しました。

これまでに説明した2つのアルゴリズムは、機械演算の基礎を形成しています。 並列化の闘いは彼らから始まりました。

さらに、もちろん、Crayはコンベアを導入しました。 コンベアモジュールは1つだけですが、それでも平行度です。 非常に深刻な一歩が踏み出されました。

これも面倒をみました。 キャリーセーブ演算を導入した後、特殊な乗算器、特殊な除数、加算器、ロジックを取得しました。 すべての異なるデバイス。 車には約10個のデバイスがあり、考えてみました：スティックツリー、それらは並行して実行できるはずです。 そして、コマンドシステムは一貫しています。 さらに、高級言語をサポートするには単純なコンパイラが必要であるという誤った考えがありました。 したがって、逆ポーランドエントリがありました。 スタックベースの非アドレスコマンドシステム。 最初に、データがスタックの最上部にダウンロードされ、次にアドレスなしの操作が実行され、結果が再びスタックの最上部にありました...すべてがスタックを通過しました。 たとえば、3アドレスコマンドシステムと比較して、多くの操作が取得されました。 したがって、これらのすべての操作を並行して実行できると便利です。 もちろん、これにより、3アドレスのマシンに追いついて追い越すことができます。これは、ポーランドの肥大化したレコードのために多くを失いました。 しかし、主な動機は異なっていました。 私たちは全体的なパフォーマンスについて考え、すでに持っている多くのコンピューティングデバイスをどのように占有するかについて考えました。 72歳でした。

78年までに、私たちは世界初の異常なスーパースカラーを作成しました。確かに、彼はたった2つのコンベアを持っていました。現在、スーパースカラーは6つのコンベアに成長しています。 Power 8には10があります。しかし、これはRISCです。多数のコンベヤーをそこに作成する方が簡単です。

Intelは95年目に故障したマシンを作りました。非常に大きな距離が得られます。 78年目と95年目。 17歳！ホラー！

これが並列処理の闘争でした。

今日のスーパースカラーの問題は、単一の命令ストリーム、単一の命令ポインタがまだあることです。最初のスーパースカラーでは、このストリームを処理するのにそれほど多くの機器は必要なかったため、これは耐えられました。

次に、現在のスーパースカラーマイクロプロセッサを見てください。これはすごいことです。ひどいこと。最初に、コンパイラは最初の並列アルゴリズムをルーラーに変換します。次に、スーパースカラーマシンはこのルーラーから再び並列性を抽出します。そして、言語が連続しているという事実のために、リタイアメントユニットは再び並列に実行された命令を一列に並べます。ここにそのようなジグザグがあります！まあ、これは許容できますか？これはひどいです。しかし、人々は苦しみます。

私の概念によると、スーパースカラーマシンは非常に不完全です（一度は非常に便利でしたが）。私の同僚と私は、スーパースカラーには限界があることに長い間気づいていました...なぜ限界があるのですか？シリアルからパラレルへのこの変換には制限があるためです。最新のIntelスーパースカラーのデコーダーは、クロックサイクルごとに4つまたは6つの解読されたコマンドを発行する必要があります。そして、読みは一貫しています。したがって、各サイクルで6つの操作をデコードするのはそれほど簡単ではありません。 x86デコーダーは非常に複雑です。

RISCでは、もちろんコマンドの長さが固定されているため、デコーダははるかに単純です。ただし、名前の変更では、次の順序の制限に引き続き従います。。名前の変更は、さまざまな操作の引数と結果を相互に接続します。実際には、チェーン内で操作を次々に処理するため、もちろん並列化が制限されます。ただし、名前の変更の制限を何らかの方法で克服したとしても、バイパスロジックの遅延が前面に出てきます。しかし、これに対処したとしても、最終的にはすべてが分岐予測子に依存します。分岐のネストのレベルが上がると、分岐予測の精度が急激に低下します。

したがって、スーパースカラーには制限、パフォーマンス制限があります。これは、エルブラス2の後のスーパースカラーの第2世代の後に実現しました。 2回目のエルブラススーパースカラーの時点では良い考えでしたが。 EC-1060を作成したNICEVTの競合他社であるIBM System / 360（スーパースカラではない3033プロセッサを搭載）の競合他社を倒したという意味で、IBMを倒しました。

私たちはそれらを二度打ちました。しかし、これはNICEVTとの競争ではなく、IBMとの競争でした。NICEVTは、アメリカのマシンの時計の正確なコピーを作成したからです。そして、彼らのソフトウェアはすべてIBMに移行していました。そして、私たち自身のすべてを持っています。

ただし、スーパースカラーのアイデアがどれほど美しいものであっても、限界があることに気付きました。見返りに何かを考え出す必要があります。次に、Volodya Volkonskyでこのトピックについて多くのことを考え、同じコア内で実行の並列スレッドである「トレイン」を思いつきました。私たちは考えました：まあ、32の列車を作るために-そして、我々は本当の並列性を持っているでしょう！しかし、その後、私は間違いを犯しました。それは非常に難しいと思いましたが、より単純なアプローチがあります-幅広いチームのアプローチです。さて、私たちはそれを試してみることにしました。結局のところ、この広いチームのマイナス面を知りませんでした...

結果として、広いチームを作りました。ただし、Itaniumとは異なります。Itaniumは、いわば完全な誤解でもあります。幅がスーパースカラーと同じであるため：6チーム。そして同時に、静的計画を使用します。なぜそれはスーパースカラーよりも速くなければならないのですか？わかりません。

Elbrus 3では、クラスターアプローチを適用しています。ワイドチームにはシリアルからパラレルへの動的な変換がないため、単一の命令ポインターのメンテナンスは無駄になりません。

当社の各チームには、最大22のオペレーションを含めることができます。つまり、22のエグゼクティブデバイスがありました。

私たちはこれに取り組み、静的計画が使用されているため、これも素晴らしいことではないことに気付きました。

このように、私たちの人生では、非常に動的な計画を試みましたが、2つのパイプラインを使用した狭いものと、2つのクラスターを使用した非常に静的なものでした。両方とも悪いことがわかりました。

その後、すでにIntelで、両方のアプローチの制限から逃れることができるプロジェクトを作成し始めました。

だから今回に来ました。彼は時間の変化と空間の変化を教えてくれました。ここで、現在を詳しく見てみましょう。

何を変更する必要がありますか？なぜすべてが悪いのですか？さて、最初に、スーパースカラーは非常に複雑であるとすでに述べました。しかし、最悪の部分は、パフォーマンスの制限があることです。その制限-6コンベア-はもはや不可能です。Power 8には10個ありますが、これはRISCです。そこでは、x86でより簡単に-より複雑になります。しかし、この「より複雑な」ことは、Intelチームの高い資格によって相殺される以上です。この問題の資格は非常に重要です。

次に、この制限が何につながったかを見てください。彼らは、マシンを拡張する方法、論理速度を上げる方法を考え始めます。さて、どうすればこれを行うことができますか？頻度の増加は現在制限されています。したがって、ベクトル演算が導入されます。

これはひどいです。かつて、クレイはベクターを発明しました。クレイは素晴らしい男だった。その後、彼はただ一つの浮遊装置を持っていました。彼はベクトルレジスタを導入しました。そして、1つのデバイスを介して、各クロックサイクルが異なるレジスタで同じ動作を開始しました。つまりそのベクターは、現在のようにデバイスを「横切る」のではなく、「沿って」行きました。彼にはコンベアが1つしかありませんでした。彼の記事を読みました。彼は速いスカラー速度に愛されていると言い、ベクトルは無料です。

次に、ベクトル演算を見てみましょう。ワオ無料！巨大なベクトルデバイス！そこの記憶では、これから地獄が起こっています。ベクトルの使用はごくわずかです。条件付き遷移がベクトル化可能なサイクルで発生する場合、これはひどいです。マスクを入力し、実際にサイクル全体を2回実行する必要があるためです。

この状況では、反復並列処理が自然になります。また、ベクターでは使用できません。

ベクトルは機器の複雑さであり、この複雑さは多くの場合使用されません。あまり人気がありません。

論理速度を上げるために考えられる2番目のことは、マルチスレッドです。しかし、これは悪いことでもあります。タスクが1つある場合、手動でスレッドに分割する必要があるからです。グラフィックを扱ったとき、私たちはそれをよく感じました。 Intelは当時Larrabeeに取り組んでいました。ララビーは巨大な目標-プログラマブルグラフィックスを設定しました。しかし、大きな間違いがありました。彼らは、明示的な同時実行性がサポートされていないx86でこのプログラマブルグラフィックスを作成することにしました。ラスタライズ

がどのように行われるかを見てみましょう。。ラスタライズは、非常に小さな計算部分であり、互いに非常に平行です。これがオブジェクトです。平面に投影します。典型的な作業は次のとおりです。次のオブジェクトが取得され、次にピクセルごとに表示されます。何かがすでに投影されていますか？投影された場合、以前に投影されたオブジェクトは現在のオブジェクトを覆いますか？その場合、ピクセル値は上書きされます。現在のオブジェクトがより近い計画に進まない場合、無視されます。

このようなアルゴリズムを並列化するには、同期が必要です。多くのオブジェクトが特定のピクセルに並行して投影しようとするためです。しかし、多くのオブジェクトが存在する可能性があり、同期には許容できないほど長い時間がかかります。メモリを介した同期が行われるためです。原則として、セマフォは共有メモリから取得されます。

これが、ララビープロジェクトが失敗した理由の1つでした。

そして、グラフィックスに理想的に必要なものは何ですか？明示的な並列処理を実装するには、適切な機器が必要です。

つまり、明示的な並行性-それは何ですか？信じられないほどの繰り返しのサイクルを考えてみましょう。明示的な並列処理がサポートされている場合、このループの反復は任意の順序で実行できます。そして、それらはたくさんあります。ここで同期について説明します。メモリ要求が行われます。

明らかな並列性がない場合-たとえば、ララビー-同期を待機しているスレッド-ちなみに200クロックサイクルを必要とする-は、この間何もせず、同時にリソースを消費します！
本当に必要なのは、実行可能な別のスレッドに現在同期しているスレッドのリソースを提供することです。このようなストリームは、大量の反復処理のため常に検出されます。確かに、あるスレッドから別のスレッドにリソースを効率的に転送する方法が必要です。しかし、我々はすでにそれを行う方法を知っています。

このアプローチでは、算術の使用-チャートでは、主に浮動算術-が100％になります！マシンの所定の幅では、単純に高速化することはできません。これは、完全な同時実行性のためです。

つまり、実際には何が必要でしたか？明示的な並列処理が必要でした。メモリ内および時間内の両方でのこのプログラムの一貫した提示は負担になっています。線形空間のため、オブジェクトのサポートがないため、タイプセーフがありません。すべてはスペースで注文されます。

そして、時間内の注文は何につながりますか？さらに、言語も整然と作られています。一般に、言語開発者は明示的な同時実行が重要であることを理解し、並列言語を導入しました。これはアルゴル68、これはエイダです。反復には明確な並列性があります。明示的な並列処理-これは同期が必要であることを意味します。そのため、開発者は独自の言語、同期を備えた並列言語を作成しました。そして、コンパイラはそれをシリアルマシンに変換します。並列言語を使用してもメリットはありません。プログラマにとっては頭痛だけ。言語に明確な並列性がある場合、デッドロックが発生することがあるためです。したがって、そのような言語は定着しませんでした。そして今、彼らは非常に重要です！

繰り返しになりますが、ロジックをトレースすると、最新のスーパースカラーは非常に複雑であり、速度制限もあります。この制限を克服するために、ベクトル化とマルチスレッドが導入されています。そして、本当に必要なのは明確な並列性です。

今、現代のコンピューター技術のもう1つの不幸...最初のマシンが登場したとき、プログラマーまたはコンパイラーは特定のマシン用に設計されたプログラムを作成しました。そして、プログラムはそれぞれ最適化されました。確かに、シーケンシャルマシン用に最適化する必要は特にありませんでした。しかし、後でキャッシュが表示されたときに、トランスレーターは各マシンに対して独自の最適化を行いました。

この状況は、IBMの360番目のマシンが登場するまで続きました。 IBMは360度の到来により、実際に次のように述べています。「まあ、以前は、各マシンに独自のプログラムを作成していました。チームの新しいシステム-新しい世代、新しいプログラム。多くのモデルで、360番目に同じコマンドシステムを持たせましょう。速いモデルと遅いモデルがありますが、コンパイラーはコードを1回だけ変換し、このコードはすべてのモデルで実行できます。これが今あるものです。

以前は、このアプローチは良さそうでした。しかし、今彼はひどいです！ほら、ここでどんなトラブルが起きているのか。コンパイラーはプログラムを翻訳し、最適化します。つまりこのアルゴリズムでのリソースの使用を最適化します。最適化を適切に実行するには、コンパイラは2つのことを知る必要があります。まず、アルゴリズムをよく知っている必要があります。彼は徹底的に知っておく必要があります：その構造、どのような並列性があるか...コンパイラが知っておくべき2番目のことは、リソースです：キャッシュレベルの数、それらの配置、レジスタの数...

今、物事がどのようになっているかを確認してください。コンパイラはアルゴリズムを適切に認識していません。言語は古い車に甘やかされているからです。それらはすべて一貫しています。アルゴリズムに並列性がある場合、ユーザー自身が言語で線形化することを余儀なくされます。さらに、最適化された方法で線形化されません。あるモデルでは線形化する必要があり、別のモデルでは異なる方法で線形化する必要があります。そのため、プログラマはすでにプログラムを台無しにしています。まあ、彼は台無しにした後、コンパイラは何らかの理由でそれをハードウェアに変換します。彼は、どのモデルでプログラムが実行されるかを知りません。ここで、状況を少し単純化します。なぜなら、 （少なくとも理論的には）コンパイルオプションを使用すると、ハードウェア機能に最適化されたコードを取得できます。ただし、特定のモデル用にコードを特化する慣行は一般的に受け入れられていません。したがって、コンパイラーは、古いモデル、最新モデル、および将来に向けてプログラムを適切にコンパイルする必要があります。彼ができないこと。したがって、無計画にコンパイルされます。今日、スーパースカラーのコンパイルはシャーマニズムです。一般的に、最適化コンパイラーはどのように開発されますか？彼らの仕事に感心します。場所で何かを並べ替えます-そして突然、すべてがより速く動作し始めます。

しかし、たとえば、このアプローチでは不可能であることに注意してください。コードの交換などの単純な最適化はできません。このVolodya Pentkovskyは私に説明した。彼は事前ページングを実装したチームで働いていました。

このスワップが特定のモデルでデバッグされると、プログラムはより高速に実行されます。 2、3年後、他のモデルが表示されます。同じプログラムでも、古いマシンよりもゆっくりと動作します。ある同僚が私に話をした：彼は、プログラムの実行が遅いユーザーに行く必要があるとき、主にソフトウェアのページングをオフにした。通常、プログラムはより速く起動しました。これは、スワッピングがモデルに依存するためです。コンパイラはそれを効率的に行うことができません。

では、何がありますか？コンパイラーはアルゴリズムをよく知らず、ハードウェアもまったく知りません。したがって、機器自体は外に出なければなりません。特に、キャッシュ操作はその中にプログラムされています。しかし、この作業はどのようにプログラムされていますか？Ironはプリフェッチを実行できません;コードをダウンロードするのは、振り返るだけです。最も最近使用されたタイプ別。これらはすべて、アルゴリズムによるデータの使用方法に反する可能性があります。

適切に最適化するには、アルゴリズムを知る必要があります。もちろん、これは機器では利用できません。

しかし、状況を修正するには今何をする必要がありますか？コンパイラーをモデル依存にする必要があります。彼を機器にまっすぐにドラッグします。これが最初です。次に、アルゴリズムからコンパイラに送られる情報を作成する必要があります。これは、アルゴリズムとまったく同じです。

次に、もう1つの非常に重要なことを見てみましょう。最初の車はタイヤ付きでした。そして、メモリが共有されました。何かが書き込まれている場合、メモリシステムに直接書き込まれます。ローカルキャッシュはありませんでした。異なるプロセッサからのメモリアクセスに違いはありませんでした。はい、メモリへのアクセスは算術演算よりも高速でした。

共有メモリへのアクセスには200サイクルかかり、これはどの操作の実行時間よりも大幅に長くなります。 したがって、キャッシュがあります。 ある意味で、キャッシュはローカルなものです。 また、バスがモデル化されているという事実により、キャッシュの操作は、ある意味で共有メモリの操作を再現します。 結果として、複雑なキャッシュ相互作用アルゴリズムがあります。 特定のキャッシュにレコードがある場合、ラインなどの所有権を取得する必要があります。

ここでの簡単なアプローチは、キャ​​ッシュの代わりにローカルメモリを入力することです。 そうすれば、キャッシュにミスがほとんどなくなります。 ローカルメモリは特定のコアのみに使用する必要があります。

しかし、今ではどのように行われていますか？ プログラムがあり、何らかのカーネルが機能しています。 ある種のメモリで動作します。 そして、それは知られていない：同じメモリで他のコアに並列操作があるかどうか。 念のため、そのような作業が進行中であると想定する必要があります。 メモリモデルに耐えなければなりません。 これにより、車の速度が大幅に低下します。 これはばかです！

明確な並列性があれば、すべてをより効率的に行うことができます。 明示的な並列化の言語のプログラマーが、計算の特定の部分で共有メモリ上で並列に動作する人はいないと言った場合、カーネルは外部に移動できません。 直接アドレス指定されたローカルメモリで動作します。 現在のキャッシュは、古いものへのワイルドな賛辞です。 この技術はかなり前に変更されましたが、それでもバス構造を模倣しています。

私は非常に慎重にローカルメモリを提案する予約をします。 私はまだこのアイデアを解決していません。 しかし、私はそれができると思います。

別の古風なもの-退職を見てみましょう。 明示的な並列化の導入により、削除する必要があります。 一連の命令は不要です。 完全な線形化により、効率を達成することは非常に困難になります。 もちろん、どういうわけかメモリからの読み取りとメモリへの書き込みの関係を解決する必要がありますが、これは別の問題です。 そのような依存関係はプログラマーによって明示的に指定されるべきであり、それらの効果的な開発は既にコンパイラーとハードウェアの問題です。 特に、依存関係がアルゴリズムのクリティカルパスにない場合、特別な操作は必要ありません。 依存する操作は、依存する操作の実行を待つだけです。 クリティカルパスが通過する依存関係により、事態はもう少し複雑になります。 ここですべての依存操作を注文すると、パフォーマンスが大幅に低下する可能性があります。 したがって、データ投機と有能な計画を使用する必要があります。これにより、依存する操作を互いに可能な限り遠くまで広げようとします。

今...現代の車の欠点に気付いたとき、私は怖がっていました！ 長い間、すでに機器は完全に異なっています。 そして同時に、最初の車がモデル化されています。 そして、誰もこれが愚かであると考えさえしません。 誰もが恐れています。

私はすでにたくさん言いました。 しかし、最終的に、私の将来の最も進歩的なマシンの顔は何ですか？

ここを見て。 アルゴリズムがあります。 プログラムの空間的および時間的コンポーネントがアルゴリズムと完全に同等であることを確認する必要があります。 このために、明示的な並列化の言語が導入されています。 私たちはそれに取り組む必要があります。 この言語では、タイプセーフが必ず存在します。 これが最初です。

次に、シンプルなトランスコーダーが導入されます。 この段階での最適化は禁じられています。 これはコンパイラータスクであり、トランスコーダーはプログラムをバイナリ表現に変換するだけです。

第三に、トランスコーダーによって作成されたディストリビューションは、ハードウェアに移動されたコンパイラーに直接送られます。 他のコンパイラオプションは必要ありません。 アルゴリズムをコンパイラから隠すだけなので、ハードウェアに移動します。 先ほど述べたようにすべてが完了すると、この単一のコンパイラーはアルゴリズムとハードウェアの両方を完全に認識します。

次に、キャッシュの問題を解決する必要があります。

これは最も難しい場所です。 最小探索。 いくつかの注意を払って、いくつかの予測で、私は単にキャッシュを捨てる必要があると断言します。 ケシは昔ながらの人へのオマージュです。 直接アドレス可能なメモリを入力する必要があります。

それから退職はまた投げ出される必要があります。

このすべての後、車は非常にシンプルになります。 そのようなシステムでは、投機性を導入する必要があります：データ投機と制御投機の両方。 次は、スーパースカラーよりもはるかに単純な非常に単純なスケジューラーです。 条件付きジャンプとプロシージャ入力を正しく実行するには、何かを追加する必要があります。 さて、アクチュエータが必要になります。 そして、他に何も必要ありません。

次に、このようなマシンの汎用性について少し説明します。 しかし、私はこれを少し不安に思って言います...最近、クアルコムのスマートフォンの結晶構造を見ました。 約11の正方形があります。 正方形の1つは汎用プロセッサであり、面積の15％しか占有していません。 次はグラフィックです。 現代の言語や機械ではできません。 これはわかっています。 また、明示的な並列処理がサポートされているマシンでは、基本的なものです。 したがって、グラフィックのある正方形は、ユニバーサルスクエアに入ります。 次に、DSPが表示されます。 DSPはサイクルであり、最も難しいものではありません。 ユニバーサルマシンでは、簡単に実行できます。 残りの正方形については、それらが意図されているアルゴリズムを本当に知りません。 しかし、私は人々にそれぞれに対処するように頼みました。 さらに、スマートフォンを使用している米国の人に連絡し、これらのボックスで実行されるタスクに関する情報を彼に尋ねました。

この男が私に言ったことを知っていますか？ 以前は、各正方形はシンプルで小さな専用のデバイスでした。 さらに、これらのデバイスはより複雑になり始め、プログラマブルコントローラーになりました。 つまり すべてのスマートフォン開発者は現在、12を超える自家製のプログラマブルプロセッサを製造しています。 これは、スマートフォン開発者を競争させるものです。 ほぼ同じ汎用プロセッサがあり、水晶の15％しか占有せず、他のデバイスと競合します。

私のアイデアはこれです...離散算術とサイクルを除いて、これらの正方形には何がありますか？ ほとんどありません。 しかし、どうやら、明らかに、ユニバーサルプロセッサはこれらすべてのデバイスを置き換えることができます。 今日存在するユニバーサルプロセッサはこれを行うことができません。 特殊なタスクには非常に効果がありません。 ただし、明示的な同時実行性をサポートするプロセッサは可能です。 もちろん、これは保証することはできません、私たちはちょうどそれに取り組み始めています。

ただし、そうだとすれば、スマートフォン開発者の生活はずっと楽になります。

現在、彼らは多数の複雑なデバイスを使用して自分で作業することを余儀なくされています。 彼らの競争は非常に激しくなっています。

このようなさまざまなデバイスをすべて単一のユニバーサルプロセッサに置き換えることが可能であれば、すべての競合がプログラムに参加します。 現在、ハードウェアの専用ハードウェアに実装されているこれらのアルゴリズムは、プログラムで記述してユニバーサルマシンで実行できるためです。

この考えは、私がサムスンで働いていた昔に起こりました。 冷蔵庫用の特別なチップを作ったら。 そして、コントローラーをプログラム可能にすれば、多くの製品で1つのデバイスを使用できると考えました。 だから今、私は考えている：あなたが1つのユニバーサルスマートフォンに切り替える場合-それはちょうど素晴らしいだろう！

私は今何が起こっているかを再び強調します。 コンピューター技術の現状は、すべてが線形であったときに元のものからあまり取り除かれていません。

互換性は、シーケンシャルタイム、シーケンシャルスペースのすべてを支配します。 そして、タイヤはまだモデル化されています。 今、私が今言っているように、これがすべて削除されて完了したら、スーパースカラーの制限は削除され、アルゴリズムの自然な制限に近づいています。

そして、この制限はいくつかの点で改善できません。 ここで彼らは私に言うことができます：おそらく、あなたの頭に何かが間違っています。 unimprovableはどういう意味ですか？ 進行が止まった、または何？

まあ、それは起こります。 現在、スーパースカラーが開発中にほとんど停止していることを誰もが認めています。 機械は究極の教育です。 これが最終的な機器である場合、もちろん、少なくとも理論的には、異なるプロセッサの数。 この有限セットの中で、いくつかは最高です。 そのため、原則として、改善不可能です。 Intel開発者の天才は、実際にこの改善不可能性を達成したという事実にあります。 それらは理論的にはありませんが、実際にはそれを達成しました。 次に、これをステップオーバーする必要があります-明示的な並列処理を導入します。 その後、アルゴリズムが制限になります。 アルゴリズムに並列性がある場合、それ以上ジャンプすることはできません。 誰かが言うなら：そして私はアルゴリズムを修正することができ、それはより速くなる-私は言う：はい、さあ、修正しなさい、この修正されたアルゴリズムを取り、最良の方法でそれを実行する。 どうぞ、すべて順調です。

まあ、おそらく、私が言いたかったことすべて。 あなたについては知りませんが、これは私に非常に大きな印象を与えます。

著者は、資料の準備に協力してくれたAlexander OstanevichとSergey Shishlovに感謝します。

親愛なる読者の皆さんにも、リクエストをお願いします。 ソビエトとロシアのコンピューター技術の歴史（そして現在）をカバーし続けることに興味があります。 そのため、創業者の父親（BESMマシン、セトゥンなど）のための手段があれば、私に連絡してください。 機械とその作成者の歴史には、埋めておくと良い白い点がたくさんあると思います。

よろしくお願いします！