リトル則と待ち行列 ─ レイテンシ・スループット・並列度の関係

なぜ「速いのに遅い」が起きるのか

DRAM や NVMe SSD のスペック表には大きな帯域値が並びますが、要求を1つずつ順番に出すと、その帯域はまるで出ません。理由は単純で、1要求の往復が終わるまで次を出さなければ、デバイスは大半の時間を遊んでいるからです。帯域を使い切るには、飛行中（未処理）の要求を常にある本数だけ抱えておく必要があります。その必要本数を、計測も仮定も最小限で言い当てるのがリトル則です。レイテンシ・スループット・並列度という三者は独立な性能指標ではなく、リトル則という1本の恒等式で結ばれた量だと理解するのが本稿の主眼です。

リトル則 L = λW

定常状態にある任意の系について、次が厳密に成り立ちます。

L = λ × W

  L : 系の中に同時に存在する要求の平均数（在席数・並列度）
  λ : 単位時間あたりに系へ入る（=出る）平均要求数（スループット）
  W : 1要求が系に滞在する平均時間（レイテンシ）

リトル則の強さは、分布にも到着過程にもサービス規律にも依存しない点にあります。ポアソン到着である必要も、FIFO である必要もありません。要請は「系が定常（長期的に入る量と出る量が釣り合い、在席数が発散しない）」ことだけです。直観的には、各要求が滞在時間 W のあいだ系に「面積1×W」を占め、それが率 λ で積み上がるので、時間平均の在席数が λ × W になる、という面積の保存です。

帯域遅延積：帯域を使い切る並列度

スループットを「要求数/秒」ではなく「バイト/秒（帯域 B）」で測り、1要求が運ぶ量を一定とみなすと、リトル則はそのまま**帯域遅延積（Bandwidth-Delay Product, BDP）**になります。

飛行中に必要なデータ量 = 帯域 B × 往復遅延 W

これは「パイプの太さ（B）×長さ（W）＝パイプを満たすのに要る水量」というイメージそのものです。例えばメモリの帯域が 50 GB/s、1回のミスを埋める往復遅延が 80 ns なら、満たすべき量は 50e9 × 80e-9 = 4000 バイト。キャッシュライン 64 バイト換算で 4000 / 64 ≒ 62 本もの未処理ミスを同時に抱えていなければ帯域は飽和しない、と分かります。ネットワークで TCP のウィンドウサイズを BDP 以上に取らないと回線が埋まらないのも、まったく同じ式の別表現です。要求が運ぶ量が均一でなければ、要求数版（L = λW）で本数を数えるほうが正確です。

メモリレベル並列（MLP）と未処理ミス

CPU のメモリ階層では、この「飛行中の要求」が未処理キャッシュミス（outstanding miss）にあたります。1回のミスは数十〜数百サイクルかかりますが、その間に後続のミスを重ねて発行できれば、複数のミスのレイテンシが重なって実効的に隠れます。これが**メモリレベル並列性（Memory-Level Parallelism, MLP）**で、まさにリトル則の L にあたります。

ミスを追跡するハード資源が **MSHR（Miss Status Holding Register）**で、その本数が同時に抱えられる未処理ミスの上限、すなわち L の天井を決めます。MSHR が K 本しかなければ、どれだけ帯域に余裕があっても実効スループットは K / W で頭打ちします。

注意すべきは、L を埋めるには独立した要求が必要な点です。あるロードの結果アドレスを次のロードが使う**依存連鎖（ポインタ追跡）**では、ミスを重ねられず L はほぼ1に張り付き、実効スループットは 1 / W まで落ちます。アウトオブオーダ実行が広い命令窓で独立ロードを先に掘り出すのは、この L を引き上げて遅延を隠すためです。前倒しでミスを起こすプリフェッチ機構も、要求の到着を早めて飛行中の本数を稼ぐ装置と言えます。

飽和点とリトル則の限界

リトル則は恒等式なので常に成り立ちますが、「W が一定のまま λ を上げれば L が伸びる」とは限りません。実際の系ではサービス能力に上限があり、到着率がそれに近づくと待ち行列が伸びて W 自体が急増します（待ち行列理論の W = サービス時間 / (1 − 利用率) が示す通り、利用率が1に近づくと W は発散）。

低負荷域 : Wはほぼ一定。λを上げるとLが線形に増え、帯域に近づく
飽和点近傍 : 待ちが支配しWが急増。λはほぼ頭打ち、Lだけが膨らむ
過負荷 : 利用率1超は定常でなくキューが発散（リトル則の前提が崩れる）

したがって設計の勘所は、飽和点の手前で必要な L を供給しきることにあります。L が足りなければ帯域を使い切れず（並列度律速）、L を過剰に積めば W が伸びてレイテンシ要件を壊す。望ましい動作点は「帯域を飽和させる最小の L」、すなわち BDP ちょうどの並列度です。同じ「並列化しても効果が頭打ちする」現象を計算側から定式化したのがアムダールとグスタフソンの法則で、メモリ側からはルーフラインモデルが演算強度と帯域の境界として同じ天井を描きます。

まとめ

• リトル則 L = λW は、系内の平均要求数・スループット・レイテンシを分布や規律に依らず結ぶ恒等式で、定常であることだけを要請する。
• 帯域を使い切る並列度は帯域遅延積 帯域 × 遅延 で決まり、必要キュー深度や TCP ウィンドウもこの式の別表現である。
• メモリ階層では未処理ミス数（MLP）が L にあたり、上限は MSHR 本数。依存連鎖は L を1に落として遅延支配にする。
• 飽和点に近づくと W が急増して λ は頭打ちするため、設計目標は「帯域を飽和させる最小の L」を遅延要件の範囲で供給することに尽きる。