順不同に格納されたエントリの順番を保持するAge Matrix回路について

とある事情でAge Matrix回路について調べていた。存在は何となく知っていたし、エントリのLiveness管理に必要だという理解はあったものの、どういう回路で動いているのか全く理解していなかったのでこの際頑張って勉強してみることにした。

そもそもの目的は、例えばCPUのInstruction Issue Queueは複数の命令を保持しておくためのQueueであるが、依存関係の解決した命令から順番に発行することができる。ただし何も考えずに依存関係の解決したもの順に出せばよいということではなく、「同時に複数発行できる命令が存在している場合、先に入ってきたエントリから順番に発行してほしい」ということになる。例えば条件的にエントリAとエントリBが同時に発行可能になったとしても、Aの方が先にエントリに格納された(古い命令)である場合、Aを優先的に発行したい。エントリは空いている場所にとりあえず命令を格納するので、エントリ番号的にA>Bである場合単純にエントリ順に発行するとBが先に発行されてしまう。これを解決するのがAge Matrixという訳だ。

Age Matrixの説明はいくつかの場所で載っているが、ググってそれっぽい解説が無いので別の呼び名が通例なのだろうか？とりあえず以下の論文が出てくる。

Matrix Scheduler Reloaded

https://dl.acm.org/doi/10.1145/1250662.1250704

ちょうどMatrix Reloadedが公開された年代に近いので、タイトルは駄洒落っぽい。いつかMatrix Scheduler Revolutionsを出して欲しい。

以下のような図が載っていて、なるほど何となくその意味は理解できるような気がする。

Nエントリが用意されている場合、Inserterは空いている場所ならどこにでも値を格納できるものとする。まあ回路設計の場合は単純なLSB抽出器でもっと番号の小さい、空いている場所へ格納することだろう。この際、 $N \times N$ のマトリックスを用意しておき、マトリックスの $i$ 行目は、「エントリ $i$ 」が格納される前までに格納されていたエントリ」の情報が格納されている。つまり、自分よりも古いエントリが誰なのかが、マトリックスの行をサーチすることで分かるようになる。「エントリ $i$ がエントリ内でもっと古い」場合、 $i$ 行をサーチすると自分を示すビット( $i$ ビット目)のみが1になっているというように理解すれば良かろう。

エントリを挿入するときは上記の通りで、エントリを削除する際は自分のエントリに相当するマトリックスの横の行と、縦の行もすべて0に設定する。これにより、自分の次に古いエントリは自分の情報が削除され、最も古いエントリとしてみなされるようになる。

説明を書いても意味不明なので、 $6\times 6$ のAge Matrixを作って実際にシミュレーションしてみる。

初期状態は何も格納されていないとする。

これに対して、エントリ0から順番にエントリに値が格納されていったものとする。Age Matrixは以下のようになる。エントリのインデックスは右から左に昇順に並んでいるものとする([6:0][6:0]のイメージ)。

Age Matrixにおいて1が付いているのは、「自分か、自分よりも前に格納されたエントリの場所」を意味している。エントリ2はエントリ1とエントリ0の後に格納されたので、Age Matrixの2行目はビット0とビット1(と自分を示すビット2)が1に設定されている。さらに、エントリ1はエントリ0の次に格納されたので、Age Matrixの1行目はビット0(と自分を示すビット1)が1に設定されている。

ここで、すべてのエントリがReady信号を出したものとする。ArbitrationにてGrantを出せるのは1つのエントリのみなのだが、Grantを出せるのは、「自分を示すビットのみが1に設定されているエントリのみ」とする。この例だとエントリ0が相当する。エントリ0は自分を示すビット0のみが1に設定されており、それ以外は0となっている。一方でエントリ0以外は、自分を示すビット以外のビット(エントリ0を示すビット0はすべて)が1になっており、Grantは得られない。

ここでエントリ3が削除されたものとする。エントリ3は自分のAge Matrixの行を0に設定するとともに、自分に相当する列ビット(3ビット目)もすべて0に設定する。エントリ0がGrantを得られ続けていることは変わらない。

次にエントリ0が削除されたものとする。Age Matrixの0行目が0に設定されるとともに、列ビット0もすべて0に設定される。これにより、次にGrantが得られるのは自分自身を示すビットのみが1となっている、エントリ1になる。

さらにエントリ1を削除する。エントリ2が次にGrantを得られるようになる。

ここでエントリ2が削除され、さらにエントリ1に新しい値が挿入されたらどうなるか。エントリ1は生き残っている「エントリ4」と「エントリ5」のビットを引き継いでAge Matrixの1行目に対して1，4，5ビット目を1に設定する。この状態ではエントリ1にGrant権限は得られず、エントリ4がGrant権限を取得する。