PREDA：パラレルVMパズルの最後のピース

Written by PREDA Source: chainfeeds 

概要

コンピュータにおける並列性の歴史を通して：並列処理の最初のレベルは、命令レベルの並列処理でした。命令レベルの並列処理は、20 世紀最後の 20 年間でアーキテクチャがパフォーマンスを向上させた主な方法でした。命令レベルの並列処理は、プログラマが特に好む、プログラムのバイナリ互換性を維持しながら性能を向上させます。命令レベル並列性には2つのタイプがある。ひとつは時間的並列処理、すなわち命令パイプライン処理である。命令パイプラインは、自動車を生産する工場の組み立てラインのようなもので、1台の車がロードされるのを待ってから次の車の生産を開始するのではなく、自動車生産工場では複数のパスで同時に複数の車を生産する。空間的並列性のもう1つのタイプは、マルチ発進（スーパースカラ）である。マルチ発進は複数車線のある道路のようなもので、複数車線での追い越しを可能にするのがアウトオブオーダー実行であり、スーパースカラとアウトオブオーダー実行は効率向上のために併用されることが多い。1980年代にRISCが登場した後、命令レベル並列の開発はその後の20年でピークに達し、2010年以降は命令レベル並列をさらに掘り下げる余地はほとんどなくなっていた。

2番目の並列レベルはデータレベル並列で、主に単一命令ストリーム複数データストリーム (SIMD) ベクター構造を指します。最古のデータレベル並列は ENIAC に登場し、1960 年代から 1970 年代にかけて、Cray に代表されるベクトルマシンは Cray-1、Cray-2、そして後の Cray X-MP、Cray Y-MP に至るまで非常に人気がありました。 SIMD は Cray-4 以降しばらく休眠状態にありましたが、現在では活性化し始め、ますます一般的に使用されるようになっています。例えば、X86のAVXマルチメディア命令は、256ビットのパスで4つの64ビット演算または8つの32ビット演算を行うことができます。 SIMDは、命令レベルの並列性を効果的に補完するものとして、ストリーミングメディアで重要な役割を果たしており、初期には主に専用プロセッサで使用されていましたが、現在では汎用プロセッサの標準となっています。

第 3 の並列レベルは タスク レベル並列 です。タスクレベルの並列性は、インターネット アプリケーションに多く存在します。タスクレベルの並列処理は、マルチコア プロセッサやマルチスレッド プロセッサに代表され、現在のコンピュータ アーキテクチャのパフォーマンスを向上させる主な方法です。タスクレベルの並列処理は並列度の粒度が高く、1つのスレッドに数百以上の命令が含まれます。

並列コンピューティングの発展という観点から見ると、今日のブロックチェーンは第1レベルから第2レベルへの変容の過程にあります。主流のブロックチェーンシステムは通常、シングルチェーンかマルチチェーンのいずれかのアーキテクチャを採用している。ビットコインやイーサリアムのようなシングルチェーンシステムは単一のチェーンを持ち、チェーン内の各ノードが全く同じスマートコントラクトトランザクションを実行し、全く同じオンチェーン状態を維持する。各ブロックチェーン・ノード内では、スマート・コントラクト・トランザクションは通常シリアルに実行されるため、システム全体のスループットは低くなります。
最近、シングルチェーンアーキテクチャを使用しながらも、スマートコントラクトトランザクションの並列実行をサポートする高性能なブロックチェーンシステムも登場しています。ブラウン大学とイェール大学のThomas Dickerson氏とMaurice Herlihy氏らは、PODC'17の論文の中で、STM（Software Transactional Memory）アプローチに基づく並列実行モデルを最初に提案しました。このアプローチは、楽観的並列性によって複数のトランザクションを並列実行し、並列実行中にトランザクションが状態アクセスの競合に遭遇した場合、STMを介して状態をロールバックし、競合するトランザクションをシリアルに実行する。このアプローチは、Aptos、Sei、Monadなど、多くの高性能ブロックチェーン・プロジェクトに適用されている。これとは対照的に、別の並列実行モデルは悲観的並列実行に基づいており、トランザクションは並列実行される前に競合する状態アクセスがないかテストされ、競合しないトランザクションのみが並列実行される。このアプローチは通常、スマートコントラクトコードを静的に分析し、有向無サイクルグラフ（DAG）のような状態依存関係を構築するプログラム分析ツールを使用して事前に計算される。同時実行トランザクションがシステムに提出されると、システムはトランザクションがアクセスする必要のあるステートとステート間の依存関係に基づいて、トランザクションを並列実行できるかどうかを判断する。互いに状態依存関係のないトランザクションのみが並列実行される。この種のアプローチは、Zilliqa（CoSplit版）やSuiなどの高性能ブロックチェーン・プロジェクトで使用されている。上記の並列実行モデルはいずれも、システムのスループット率を大幅に向上させることができる。これら2つの方式は、上述の命令レベルの並列実行に相当する。しかし、これらの取り組みは、1）スケーラビリティの問題、2）並列意味表現の問題、という2つの問題に悩まされており、以下に詳しく説明する。

並列設計

典型的なSolana、Monadプロジェクトの技術的ソリューションの例を用いて、並列分類を含む並列アーキテクチャ設計を分解します。これには、並列化の分類、データ依存性、および並列性とTPSに影響するその他の重要なメトリクスが含まれます。

ソラーナ

高いレベルで言えば、ソラーナの設計哲学は、ブロックチェーンのイノベーションはハードウェアの進歩に合わせて進化すべきだということです。ムーアの法則に従ってハードウェアが改良され続ける中、ソラーナはより高いパフォーマンスとスケーラビリティの恩恵を受けることを目指している。 Solanaの共同設立者であるAnatoly Yakovenkoは、5年以上前にSolanaの並列化アーキテクチャを設計しており、今日、並列化はブロックチェーンの設計理念として急速に広まっている。

Solanaは決定論的並列化を使用しています。これは、開発者が通常すべての状態を事前に宣言する、アナトリーの組み込みシステムでの過去の経験に由来する。これにより、CPUはすべての依存関係を認識し、メモリの必要な部分をプリフェッチすることができる。その結果、システムの実行は最適化されるが、やはり開発者側には余分な作業が必要になる。Solanaでは、プログラムのすべてのメモリ依存関係が必要とされ、構築されたトランザクション（すなわち、アクセスリスト）で説明されるため、ランタイムは複数のトランザクションを効率的にスケジューリングし、並列実行することができます。
Solanaアーキテクチャの次の主要コンポーネントは、 Sealevel VMであり、バリデータが所有するコア数に基づいて、複数のコントラクトとトランザクションの並列処理をサポートする。ブロックチェーンにおけるバリデータは、トランザクションの検証と妥当性確認、新しいブロックの提案、ブロックチェーンの整合性とセキュリティの維持を担うネットワーク参加者である。トランザクションは、どのアカウントが読み取りと書き込みのロックを必要とするかを事前に宣言するため、Solanaスケジューラーはどのトランザクションが同時に実行できるかを決定することができる。このため、検証時に「ブロックプロデューサー」またはリーダーは、保留中の何千ものトランザクションを選別し、重複しないトランザクションを並行してスケジュールすることができる。

モナド

モナドはチューリング完全並列EVMのレイヤー1を構築しています。 Monadは並列化エンジンだけでなく、バックグラウンドで構築される最適化エンジンもユニークです。

Seiと同様に、Monadブロックチェーンは楽観的並行性を使用しています。strong>「楽観的同時実行制御（Optimistic Concurrency Control：OCC）」を使用してトランザクションを実行します。同時実行トランザクション処理は、複数のトランザクションが同時にシステム内に存在する場合に発生する。このトランザクション方式には、実行と検証の2つの段階がある。

実行フェーズでは、トランザクションは楽観的に処理され、すべての読み取り/書き込みはトランザクション固有のストレージに一時的に格納される。その後、各トランザクションは、一時記憶操作の情報が前のトランザクションによって行われた状態変更と照合される検証フェーズに入る。トランザクションは独立していれば並行して実行される。あるトランザクションが他のトランザクションによって変更されたデータを読むと、衝突が生じる。

モナドの設計における重要な革新の1つは、わずかなオフセットを持つパイプラインです。このオフセットにより、複数のインスタンスを同時に実行することで、より多くのプロセスを並列化することができます。その結果、パイプラインは、ステート・アクセス・パイプライン、トランザクション実行パイプライン、コンセンサスと実行のパイプライン、コンセンサス・メカニズム自体のパイプラインなど、多くの機能を最適化するために使用される。

Monadでは、トランザクションはブロック内で線形に順序付けられますが、並列実行を活用することで、より速く最終状態に到達することが目標です。 Monadは楽観的並列化アルゴリズムを使って実行エンジンを設計している。 Monadのエンジンはトランザクションを同時に処理し、それらを分析することで、トランザクションを次々に実行しても結果が同じになるようにする。衝突があれば、再実行する必要がある。ここでの並列実行は比較的単純なアルゴリズムだが、Monadの他の主要な革新技術と組み合わせることで、このアプローチが斬新なものになる。ここで注意すべき点は、再実行が発生したとしても、無効なトランザクションに必要な入力はほとんど常にキャッシュに保持されているため、通常は単純なキャッシュ検索で済むということである。ブロック内の前のトランザクションをすでに実行しているので、再実行は間違いなく成功する。

実行を遅らせることに加えて、Monadはまた、SolanaやSeiと同様に、実行とコンセンサスを分離することでパフォーマンスを向上させます。コンセンサスが完了したときに実行を完了するという条件を緩和すれば、2つを並行して実行することができ、それによって両方に余分な時間をもたらすということだ。もちろん、Monadはこの状況を処理するために決定論的アルゴリズムを使用して、一方が追いつくために先行しすぎないようにしている。

楽観的並列実行であろうと悲観的並列実行であろうと、上述のシステムは基礎となるデータモデルの抽象化として共有メモリーを使用しています。異なる並列実行ユニットが直接アクセスできる（つまり、すべてのオンチェーンデータを並列実行ユニットが直接読み書きできる）。基礎となるデータモデルとして共有メモリを使用するブロックチェーンシステムは、通常、その並行性が単一の物理ノード（Solana）に制限され、各物理ノードの並行性は、ノードの計算能力、すなわち物理スレッド数（各スレッドが仮想マシンをサポートすると仮定）によって制限されます。

このノード内並列性は、スマートコントラクト実行レイヤーのアーキテクチャを変更するだけでよく、システムコンセンサスレイヤーのロジックを変更する必要はありません。その結果、データストレージのシャーディングがないため、ブロックチェーンネットワークの各ノードは、すべてのトランザクションを実行し、すべての状態を保存する必要があります。一方、分散スケーリングにより適したシェアードナッシング・アーキテクチャと比較すると、基盤となるデータモデルの抽象化として共有メモリを使用するこれらのシステムは、処理能力の点で水平方向にスケールすることができません。つまり、システムの状態ストレージの拡張だけでなく、実行能力の拡張を達成するために物理マシンの数を増やすことができるため、ブロックチェーンの根本的なスケーラビリティに対処することができません。問題は、ブロックチェーンがスケーラブルではないということだ。

では、既製の解決策はあるのでしょうか？

並列プログラミングモデル

PREDAを紹介する前に、当然の質問をしたいと思います。並列プログラミングを使うのか？1970年代、1980年代、そして1990年代の一部でさえ、私たちはシングルスレッド・プログラミング（あるいはシリアル・プログラミングと呼ばれていました）にとても満足していました。あるタスクを実行するプログラムを書くことができた。実行が終わると結果が返ってくる。タスクは完了し、誰もがハッピーになる！
2004年以前、CPUメーカーのIBM、Intel、AMDは、より高速なプロセッサを提供することができました。プロセッサーのクロックは、16MHz、20MHz、66MHz、100MHz、200MHz、333MHz、466MHz......と、どんどん速くなり、つまり、どんどん良くなっていくように見えた。しかし2004年になると、技術的な限界からCPUの高速化は維持できないことが明らかになった。CPUメーカーの解決策は、1つのCPUの中に2つのCPUを搭載することであった。たとえ両方のCPUが1つのCPUよりも低速で動作したとしても、である。たとえば、200MHzで動作する2つのCPU（メーカーはこれをコアと呼ぶ）を一緒に使えば、300MHzで動作するシングルコアCPUよりも1秒間に多くの計算（つまり、1秒間に多くの演算）を行うことができる。たとえば、200MHzで動作する2つのCPU（メーカーはコアと呼ぶ）を一緒に使えば、300MHzで動作する1つのCPUよりも1秒間に多くの計算を行うことができる（つまり、直感的には2×200 >300）。
「シングルCPU、メニーコア」という夢のような話が現実のものとなり、プログラマーは両方のコアを活用するための並列プログラミング手法を学ばなければならなくなった。もし1つのCPUで2つのプログラムを同時に実行できるのであれば、プログラマーは両方のプログラムを書かなければならない。しかし、これはプログラムを2倍速く実行することにつながるのだろうか？そうでないなら、2 x 200 >300のアイデアには欠陥がある。一方のコアが十分な仕事を得られない場合はどうなるのか？つまり、1つのコアだけが本当に忙しく、もう1つのコアは何もしていない場合だ。その場合は、300MHzのコアを1つ使う方がいいだろう。マルチコアの導入により、多くの似たような問題が非常に顕著になり、これらのコアを効率的に使用する唯一の方法はプログラミングです。

下の画像では、ボブとアリスを2人の金鉱夫と想像しています。paddingleft-2">