基本情報のアムダールの法則を処理時間と性能向上比の例題で理解する

基本情報の性能計算で「処理の一部を3倍に高速化した」と書かれていても、全体が3倍速くなるとは限りません。改善していない時間が残るためです。アムダールの法則は、この残る部分を含めて、全体でどれだけ速くなるかを考えるためのものです。

計算の出発点はシンプルです。改善前の時間を「変わらない部分」と「速くなる部分」に分け、速くなる部分だけを倍率で割ります。二つを足した後に、改善前の時間を改善後の時間で割れば、全体の性能向上比を求められます。

この記事では、100秒のうち75秒を改善する独自の例を軸に、並列化、上限、目標性能からの逆算まで確認します。CPUのクロックやMIPS自体の計算とは分けて、部分改善が全体へ与える効果を理解しましょう。

基本情報のアムダールの法則の仕組み

変わらない時間を先に残す

処理全体が100秒かかり、そのうち25秒が準備や逐次処理、75秒が改善対象だとします。改善対象の性能を3倍にするなら、その部分の所要時間は75÷3=25秒です。もともとの25秒は変わらないため、改善後の全体は25＋25=50秒になります。

全体の性能向上比は100÷50=2倍です。改善対象は3倍でも、全体は2倍にとどまります。これが、ある部分を速くしても残りの部分が全体の短縮を制限する、という考え方です。数字を公式に入れる前に、100秒の帯を25秒と75秒へ分けると納得しやすいですね。

ここでの割合は、改善前の全実行時間を基準にしています。改善後の50秒のうち、変わらなかった部分は25秒なので、改善後の比率では50%です。しかし、公式へ入れる元の逐次割合は25%のままです。改善後の比率へ勝手に置き換えると、別の計算になります。

また、「全命令の75%」と「実行時間の75%」も同じとは限りません。命令によって所要時間が違えば、命令数の割合だけから時間の割合は分かりません。問題文が実行時間を与えているのか、命令数を与えているのかを確認します。

Cornell大学のアムダールの法則の解説では、逐次部分と並列化可能部分の時間を分けて計算しています。まず時間へ戻して足す、という方針は、記号の置き方が変わっても使えます。

公式を時間の式から作る

改善前の全体時間をT、改善対象の時間割合をp、その部分の高速化倍率をnとします。変わらない部分の時間はT×(1−p)、速くなる部分の時間はT×p÷nです。したがって、改善後の時間T’は、T×{(1−p)＋p/n}となります。

性能向上比SはT/T’です。共通のTが消えるので、S=1/{(1−p)＋p/n}と表せます。分母は改善後の時間を改善前の時間で割った比です。その逆数を取ると、同じ仕事を何倍の速さで終えられるかになります。

今回の例ではp=0.75、n=3なので、分母は0.25＋0.75/3=0.5です。時間は元の0.5倍、性能は1/0.5=2倍です。0.5を答えるのか2を答えるのかは、設問の「処理時間」「性能向上比」という言葉で決まります。

百分率の75をそのままpへ入れず、0.75へ直す点にも注意しましょう。また、1−pは「全体から改善対象を引いた割合」なので、ここでは0.25です。pを逐次部分の割合と定義する教材なら、式は1/{p＋(1−p)/n}になります。記号だけで暗記しないことが大切です。

公式を忘れたときは、全体を100秒または1と置き、変わらない時間を残して、対象だけを割ってください。割合が見やすい100を使うと、0.75秒といった小数に迷わず計算できます。どちらの置き方でも、最後の比は同じです。

並列化でも逐次部分は残る

並列化の例では、75秒の部分を同じ性能の3プロセッサへ均等に分けられるとします。通信や分担の準備に余分な時間がかからない理想条件なら、75秒の部分は25秒になります。一方、順序が必要な25秒の部分は分けられず、そのまま残ります。

プロセッサ数を6へ増やすと、並列部分は75÷6=12.5秒です。全体は25＋12.5=37.5秒、性能向上比は100÷37.5で約2.67倍になります。3台から6台へ増やしても、全体の処理時間が50秒から25秒へ半減するわけではありません。

「台数が倍」と「全体の性能が倍」は区別します。今回、6台にしたときの性能を、もとの1台に対して比べるなら約2.67倍ですが、直前の3台構成に対して比べるなら50÷37.5で約1.33倍です。比較する基準を省略すると、同じ結果でも倍率が違って見えます。

プロセッサ数	逐次時間	並列部分の時間	全体時間	1台比の性能
1	25秒	75秒	100秒	1倍
2	25秒	37.5秒	62.5秒	1.6倍
3	25秒	25秒	50秒	2倍
6	25秒	12.5秒	37.5秒	約2.67倍
12	25秒	6.25秒	31.25秒	3.2倍

この表は、同じ100秒分の仕事を固定して比較したものです。プロセッサを増やすのと同時に処理するデータ量も増えるなら、同じ条件の比較ではなくなります。アムダールの法則の基本問題では、仕事量が固定されているという前提を意識します。

改善できない部分が上限になる

プロセッサをどんどん増やすと、75/n秒の部分は小さくなります。しかし、25秒の逐次処理は消えません。したがって全体時間は25秒へ近づき、性能向上比の上限は100/25=4倍です。有限の台数では並列部分の時間も残るので、この例でちょうど4倍へ達することはありません。

一般には、改善対象の割合pが1未満なら、上限は1/(1−p)です。逐次部分が20%なら上限5倍、10%なら上限10倍と計算できます。ただし、上限の値と、指定台数で実現できる性能は違います。4台の計算を問われているのに無限台の上限を答えないようにしましょう。

p=0なら改善できる部分がなく、nを増やしても性能向上比は1です。p=1なら、この単純なモデルでは全体がn倍になります。また、n=1なら改善していないため、どんなpでもS=1です。こうした端の値を式へ入れると、覚えた式の整合性を確認できます。

ローレンス・リバモア国立研究所の並列計算教材でも、並列化できる割合が性能向上を制限する点が説明されています。現実の実測値をすべてこの式だけで決められるという意味ではなく、まず理想条件での限界を知るためのモデルです。

「もっと速いCPUなら残る25秒も短くなるのでは」と考えた場合は、何を改善する設定なのかを確認してください。元の問題は75秒の部分だけを改善する条件です。25秒の部分も改善するなら、前提を変えた新しい計算として、どの時間が何倍になるかを定義し直します。

基本情報のアムダールの法則を例題で解く

時間短縮率と性能比を分ける

独自の学習用例題として、120秒の処理のうち90秒だけを3倍に高速化するとします。対象外は30秒、対象は90/3=30秒なので、改善後の全体は60秒です。時間の比は60/120=0.5、時間短縮率は(120−60)/120=0.5、性能向上比は120/60=2です。

この例では時間の比と短縮率が偶然どちらも50%になりますが、一般には同じではありません。改善後が元の40%の時間なら、時間短縮率は60%、性能向上比は2.5倍です。残った割合、減った割合、逆数の三つを区別します。

「性能が50%向上」と「時間を50%短縮」も異なります。性能が元の1.5倍なら、同じ処理の時間は1/1.5で約66.7%です。時間短縮率は約33.3%になります。一方、時間を50%短縮すれば、性能は2倍です。日常語の「半分速い」などの曖昧な表現へ置き換えず、比を明示しましょう。

選択肢に0.5、1.5、2、3が並んでいたら、まず単位や問いを見ます。時間の比なら0.5、全体の性能比なら2、対象部分だけの性能比なら3です。どの数も計算の途中に現れる可能性があるので、数字を出しただけで選ばず、意味を言葉で確認してください。

CPUそのものの実行時間を求める計算は、基本情報のクロック・MIPS・CPIの計算で整理できます。この記事では、その実行時間を部分に分けた後の改善効果を扱っています。二つの計算の目的を分けると、使う式を選びやすくなります。

目標性能から並列数を逆算する

次は、25%が逐次処理、75%が並列化できる仕事について、全体を3倍以上にしたいという学習用例です。性能向上比が3以上になるには、改善後の時間の比を1/3以下にする必要があります。したがって、0.25＋0.75/n≦1/3と置きます。

両辺から0.25を引くと、0.75/n≦1/12です。nは正なので整理でき、n≧9となります。プロセッサ数は整数のため、理想条件での最小台数は9です。実際に代入すると、0.25＋0.75/9=1/3で、性能比は3になります。

台数を求める問題では、小数を丸める前に条件を確認しましょう。例えば計算上n≧7.2なら、必要な整数台数は8です。四捨五入して7にすると目標を満たしません。最後に候補の台数を元の式へ戻し、目標以上かを確認すると安心です。

同じ構成で目標を5倍にしたい場合はどうでしょうか。逐次部分が25%なので上限は4倍です。並列部分だけの改善では5倍へ到達できず、台数を探す前に不可能と判断できます。4倍ちょうども、有限台数でこのモデルの条件を満たすことはできません。

目標へ届かせるには、逐次部分自体を短くする、手順を変えて並列化できる範囲を広げるなど、別の改善が必要です。台数を増やすことだけを唯一の解にしない点が、この法則を実務的に理解する手掛かりになります。ただし、具体策の効果は実測や追加条件がなければ数値化できません。

実行時間の測定結果から、並列化できる割合を逆算する問題も考えられます。4台で2.5倍という条件なら、1/2.5=0.4が改善後の時間比です。0.4=(1−p)＋p/4=1−0.75pと置くと、0.75p=0.6なので、p=0.8と求まります。この理想モデルでは並列化できる部分が80%、逐次部分が20%です。

ただし、測定値へオーバーヘッドや負荷の偏りが含まれているなら、この逆算だけで実際の逐次割合を断定できません。同じ速度低下でも、分割できない仕事が多い場合と、分配や待ち時間が増えた場合があるためです。試験では指定されたモデルに従い、実務では測定対象と追加時間の内訳を確認します。

並列化効率という観点なら、1台比の性能向上比を台数で割ります。3台で2倍なら2/3で約66.7%です。これは理想的に3倍となる場合に対する速度向上の比率で、CPU使用率の実測値そのものではありません。効率、速度、使用率という異なる指標を混ぜないことも、性能問題を読むうえで役立ちます。

オーバーヘッドを足す場合

並列処理では、仕事の分配、データの受け渡し、結果の集約、同期待ちなどに時間がかかる場合があります。これらをオーバーヘッドと呼びます。基本の式は、こうした追加時間を無視でき、仕事が均等に分かれる理想条件を扱います。

元の100秒の例で、3プロセッサ化により25＋75/3=50秒となる一方、分配と集約に合計3秒かかると指定されたなら、改善後は53秒です。性能向上比は100/53で約1.89倍です。理想値2倍と実際の条件を入れた値を、別々に示せます。

この3秒は、この記事で計算のために置いた仮定であり、一般的な装置の実測値ではありません。また、台数を6へ増やしたときも3秒のままとは限りません。オーバーヘッドが一定か、台数とともに増えるかは、問題の条件や測定結果から判断します。

Oracleの並列化の説明では、仕事の分散や通信に必要な時間が速度向上へ影響することが整理されています。基本の式による理想値は、現実の所要時間を保証する値ではありません。

問題文に「オーバーヘッドは無視できる」とあれば、勝手に余分な時間を足しません。逆に、通信や準備の時間が与えられている場合は無視しないようにします。固定仕事量、均等分割、追加コストの有無を、計算前の確認欄として書いておくと取りこぼしを減らせます。

改善案を同じ基準で比べる

別の独自例題を考えます。100秒の仕事が処理Aに60秒、処理Bに30秒、その他に10秒で構成されるとします。案Aは処理Aを2倍、案Bは処理Bを5倍にする条件です。Aの改善後は30＋30＋10=70秒、Bの改善後は60＋6＋10=76秒です。

対象部分だけなら案Bの5倍が大きいですが、全体時間は案Aの方が短くなります。案Aは30秒を削減し、案Bは24秒を削減するためです。部分の倍率が最も大きい案を、そのまま全体でも最良と考えないことが重要です。

両方を同時に行えると明示されたなら、改善後は30＋6＋10=46秒です。全体性能は100/46で約2.17倍になります。AとBの全体性能比を掛け合わせる計算ではありません。互いに別の時間部分を改善するなら、それぞれを短縮してから足し合わせます。

この例で、案Aの適用後に処理Aが占める割合は30/70です。改善前の60%のままではありません。次の改善を、新しい測定結果の割合から評価する場合は基準を更新します。一方、元の割合を使う式なら、元の100秒を基準に統一して計算します。異なる基準の割合を混ぜないようにしましょう。

性能に加えて費用や運用負荷を比べる場面では、台数、費用、処理時間などを同じ条件でそろえる必要があります。必要能力の見積もりとの関係は、基本情報のキャパシティプランニングも参考になります。ただし、この例には価格条件がないので、費用対効果まで優劣を断定することはできません。

基本情報のアムダールの法則のまとめ

計算では「改善対象外を残す」「対象の時間だけを倍率で割る」「足してから性能比を求める」の順に進めます。改善前の実行時間の割合を使い、記号が何を表すかを確かめれば、式の形が少し違っていても対応できます。

見直しでは、求めた改善後時間が対象外の時間より短くなっていないか、全体性能が部分の倍率を超えていないか、n=1なら元と同じになるかを確認してください。ここで扱った基本モデルでは、こうした端の値が計算ミスを見つける手掛かりになります。

まず100秒を25秒と75秒へ分け、3台、6台、上限の三つを自力で求めてみましょう。答えが50秒・37.5秒・上限4倍とつながれば、逐次部分が残る意味をつかめています。追加演習には基本情報の過去問アプリを使えますが、この独自例題やアムダールの法則の問題が必ず収録されているという案内ではありません。