アルゴリズム遅延

アルゴリズム遅延（テンプレート:Lang-en-short）はアルゴリズムに内在する待ち時間である。

概要

プログラムはアルゴリズムからなり、アルゴリズムが計算機によって処理されることで実行される。計算処理には当然時間がかかるため、プログラムの開始から実行完了には遅延（レイテンシ）が発生する。しかし無限の能力をもつ計算機（=処理遅延0秒）を仮定してもレイテンシが発生する、すなわちアルゴリズムそのものに由来してレイテンシが発生する場合がある。このアルゴリズムに内在する遅延をアルゴリズム遅延という。

例えば2つの音声加工アルゴリズム「A: 音量倍増」と「B: ノイズ除去」を考える。Aの音量倍増では時刻 $t$ の入力信号を2倍にして即返せばよいので、無限の計算能力があれば即座に出力できる。Bのノイズ除去の場合、時刻 $t$ の入力信号が $x_t=0.5$ のとき、この1点だけを見てもどの程度ノイズが乗っているかは判別できない。ノイズ検出にはある程度の時間区間（ブロック）を見る必要があり、そのために信号を一定時間貯める必要がある。つまりBでは処理そのものに追加してアルゴリズムのための信号蓄積が必要であり、たとえ無限の処理能力があっても信号が貯まるまでの待ち時間がかかる。ゆえにBのアルゴリズムはブロック長分の遅延を必ずもつ、すなわちアルゴリズム遅延をもつことになる。

アルゴリズム遅延はリアルタイム情報処理において重要である。例えばボイスチャットではリアルタイムに自分の音声を圧縮、ネットワーク転送し、相手方で伸展して音を届ける。経験的に知られているように、遅いマシンやネットワークを利用すると相手の声が遅れて聞こえ、コミュニケーションを阻害してしまう。しかし超高性能のマシンとネットワークを利用したとしても、圧縮伸展アルゴリズムが大きなアルゴリズム遅延をもっていると音が遅れて聞こえてしまう。なぜならアルゴリズム遅延は処理能力に依存しない、それ以上下げることのできない遅延だからである。音声圧縮伸展アルゴリズムすなわち音声コーデックの分野ではこのような低遅延リアルタイム用途を意識してアルゴリズム遅延を最小化できるコーデックが多数発表されている（例: Opus）。

アルゴリズム遅延はアルゴリズムが規定する入力形式に強く依存する。入力形式には時間に依存するストリームや時間に依存しないバッチなどがある。例えば上記アルゴリズムBはリアルタイム処理用のストリーム入力を前提としているため、ストリームからブロック長分貯めるためのアルゴリズム遅延が発生している。一方、ブロック単位のノイズ除去をオフライン用のバッチ入力に適用するとする。その場合、全ての入力が既に揃っている、すなわち全ての信号が「既に貯まっている」状態で処理を開始できる。ゆえに信号蓄積にかかる遅延が0になってアルゴリズム遅延が0になる。このような背景から、通話などのリアルタイム用途ではアルゴリズム遅延が重視され、保存用圧縮などの非リアルタイム用途では相対的に重視されない傾向がある。

アルゴリズムの実処理（実行）にかかる遅延は処理遅延と呼ばれる。処理遅延は計算機の性能や実装の質により左右される。

要因

アルゴリズム遅延は様々な要因（手法）により決定される。以下はその一例である。

先読み

アルゴリズム遅延の要因の1つが先読み/前方参照（テンプレート:Lang-en-short）である。時刻 $t$ の入力信号 $x_t$ を処理する際、時刻 $t+N$ の情報を利用することでより良い $x_t$ の処理をできる場合がある。この先データアクセスが先読みである。先読みをおこなう場合、$x_t$ を処理するために $x_{t+N}$ までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、$N$ サンプルの先読みは $N$ のアルゴリズム遅延をもたらすことになる。アルゴリズムを設計する際には、先読みで得られる出力の質向上と遅延増大のトレードオフを理解する必要がある。

時刻 $t-N$ すなわち過去の信号を後読み（テンプレート:Lang-en-short）することは一般にアルゴリズム遅延へは影響しない。なぜならストリーム入力であっても過去の入力は既に手元にあるからである。$N$ を大きくすることはむしろ処理量の増大による処理遅延と質の兼ね合いになる。

ブロック処理

アルゴリズム遅延の要因の1つがブロック処理である。ブロック処理では時刻 $t$ の入力信号 $x_t$ を逐次処理するのではなく、$x_t$ ~ $x_{t+N}$ を1かたまりとしこの単位で一括処理する。次の処理では時刻を $h$ 進めた $x_{t+h}$ ~ $x_{t+h+N}$ を同様に一括処理する。処理単位はブロック、フレーム、ウィンドウなどと、間隔 $h$ はホップ長（テンプレート:Lang-en-short）やストライド（テンプレート:Lang-en-short）と呼ばれる。ブロック長 $N$ とホップ長 $h$ は必ずしも一致しない。

$N=h$ のブロック処理では、ブロック先頭 $x_t$ を処理するためにブロック末端 $x_{t+h}$ までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、ホップ長 $h$ のブロック処理は入力 $x_{t+a}$ に「最大で」 $h$ のアルゴリズム遅延をもたらす。「最大」なのはサンプル位置によりアルゴリズム遅延が異なるからである。ブロック末端 $x_{t+h}$ の視点でみると取り込まれた瞬間に処理されるためブロック処理のアルゴリズム遅延は0である。ブロック単位でみた遅延は最大値たる $h$ になる。

$N>h$ の場合、ブロック処理を出力の視点でみると、ホップ長 $h$ 分の出力を一括で出力している。$N>h$ で出力長以上の入力を取りこんでいるということは、ブロック内での先読み/後読みをおこなっていることになる。つまり $t$ ~ $(t+h)$ を出力するために $(t-b)$ ~ $(t+h+a)$ を入力している（$N:=b+h+a$） 。アルゴリズム遅延に影響するのは先読みであるため、ブロック単位でみたアルゴリズム遅延は $h+a$ になる。

またブロック処理と先読みを組み合わせ、ブロック $k$ の処理にブロック $k+M$ を必要とさせることもできる。その場合は $h$ 単位で必要な入力が増えていくため、アルゴリズム遅延が $h+a+M*h$ になる。

関連項目

• レイテンシ
• アルゴリズム
• 計算機科学