このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
順序に従った作業
- ほとんどの単純なプログラムは順次処理です。1ステップ実行後、次のステップへ進み、さらに次のステップへと続きます。
- コンピューターはステップ2を開始する前に、ステップ1を完了させます。
- これは理解しやすいですが、大規模なタスクでは遅いことがあります。
English
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
並列計算
- 並列計算は、作業を分割して複数の部分を同時に実行することを指します。
- 現代のコンピューターには、それぞれが独立して作業を行える複数のプロセッサ(コアとも呼ばれる)があります。
- 4人の作業者がそれぞれ1つのタスクを担当する場合、4つのタスクは約1つのタスクの時間しかかかりません。
English
Parallel (four workers at once):
worker 1: task A
worker 2: task B
worker 3: task C
worker 4: task D
|--------|
total time ≈ the longest single task
スピードアップ
- スピードアップとは、並列バージョンがどれほど速いかを示す指標です。
- スピードアップ = (順次処理の時間) / (並列処理の時間)。
- 例:あるタスクが順次処理で8秒、分割処理で2秒かかる場合、スピードアップ = 8 / 2 = 4倍となります。
必ずしもN倍速ではない
- プロセッサを増やすことが、必ずしもN倍速になるわけではありません。
- タスクの一部は分割できません。これらは順次処理で行う必要があります。
- また、作業の分割と結果の統合にも追加の時間がかかります。
English
Job = setup (must be in order) + main work (can split)
setup main work (split over 4)
|-----| |--------------------------------|
|--------| <- this part gets 4x
The setup part stays the same length.
分散計算
- 分散計算は、ネットワークを通じて協力し合う多数の個別のコンピューターを利用します。
- これらのコンピューターは異なる部屋、都市、あるいは国に配置されていることがあります。
- 例:Web(多数のサーバー)、数千台のマシンに分散されたビッグデータ処理、および大規模な科学プロジェクトなどです。
English
Distributed (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
トレードオフ
- 利点: 並列・分散システムは遥かに高速であり、超大規模なタスクに対応できます。
- 難しさ: コードが複雑になり、部分間の調整が必要となり、結果を統合する必要があります。
- 限界: スピードアップは、分割できない部分やコンピューター間のネットワーク遅延によって制限されます。
重要用語
- 順次処理: ステップが順序に従って1つずつ実行されます。
- 並列処理: 複数のプロセッサ上で部分が同時に実行されます。
- スピードアップ: 順次処理時間を並列処理時間で割った値です。
- 分散計算: 多数の個別のコンピューターがネットワークを通じて協力します。
よくあるミス
- 並列スピードアップは、独立した部分に分割可能な作業にのみ有効です。
- プロセッサを追加するごとに、得られる速度向上は次第に減少します。
あなたも試してみよう
- スピードアップの公式を小さな関数として実装してください。
- 固定されたセットアップ部分と分割可能な作業部分组成のタスクをモデル化してください。答えを確認ボタンを押してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
タスクには順次実行しなければならない setup パートと、 workers が同時に共有できる splittable パートがあります。 parallel_time(setup, splittable, workers) を書いて総時間を 返す ようにします: セットアップ時間 + 労働者に割り振られる分割可能な部分の時間。例: parallel_time(2, 8, 4) → 4.0 (2 + 8/4)。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
並列版が何倍速いかを 返す speedup(sequential, parallel) を書きます: 直列時間を並列時間で割ったものです。例: speedup(8, 2) → 4.0 。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
労働者が無限であっても、 setup パートは分割できません。 最も良い スピードアップを 返す max_speedup(setup, splittable) を書いてください: 全体作業時間をセットアップ時間で割ったものです(無限の労働者は分割可能な部分をほぼゼロにし、セットアップ残りのみを残します)。例: max_speedup(2, 6) → 4.0 ((2+6)/2)。
実行ボタンをクリックして出力を確認してください。