Vector LoadとElement Ordering
スカラーのOut-of-Order実行では、同一アドレスに対する後続loadを先に実行すること自体は許される。
ただし、後続loadが先行loadより古い値へ戻るCoRR違反はcommitできない。
では、1命令が複数のメモリアクセスを発生させるRISC-V Vector Extensionでは、このルールをどのように考えればよいのだろうか。
ベクトルでは、次の2つを分けて考える必要がある。
- 異なるvector memory instruction間の順序
- 1つのvector memory instruction内部のelement order
異なるVector命令間の順序
次の2つのvector loadを考える。
V1: vle64.v v1, (a0) V2: vle64.v v2, (a0)
V1とV2はprogram order上、この順番で並んでいる。
V1 → V2
RISC-V Vector Extensionでは、vector memory instructionは命令レベルでRVWMOに従う。
したがって、異なるvector load命令が同じアドレスを読む場合、スカラーloadと同様にCoRRとの整合性を満たす必要がある。
たとえば、ある要素について、別hartが途中で値AからBへ更新したとする。
許される代表例は次のとおりである。
V1[i] = A V2[i] = A
V1[i] = A V2[i] = B
V1[i] = B V2[i] = B
一方、次の結果は問題になる。
V1[i] = B V2[i] = A
後続のvector load命令が、先行命令より古いmemory versionへ戻っているためである。
したがって、ベクトル実装でも、異なる命令間の同一アドレスアクセスについて、必要に応じてordering validationやreplayを行わなければならない。
ベクトルでは要素単位で実行が重なる
ベクトル命令は複数のelement operationを発生させるため、実装では次のような状態が起こり得る。
V1 element 0: completed V1 element 1: stalled V1 element 2: pending V2 element 0: completed V2 element 1: completed speculatively V2 element 2: pending
つまり、先行vector命令の一部要素が未完了である一方、後続vector命令の対応要素が先に実行されることがある。
その間に、別hartからstoreやinvalidationが到着すると、対応要素間でCoRR違反が発生する可能性がある。
V2 element 1がAを読む
↓
別hartがBをstore
↓
V1 element 1がBを読む
この結果をそのままcommitすると、
V1[1] = B V2[1] = A
となり、後続命令が古い値へ戻ってしまう。
Vector命令内のElement Orderは別問題
ここで注意が必要なのは、異なるvector命令間の順序と、単一vector命令内の要素順序は同じではないことである。
通常のvector memory instructionでは、命令内のelement operationは原則としてunorderedである。
たとえば、4要素のvector loadがあったとしても、
element 0 element 1 element 2 element 3
の順番でメモリアクセスする保証はない。
内部的には次の順番でもよい。
element 2 → element 0 → element 3 → element 1
これは、ベクトル実装が複数laneや複数memory portを使って並列に処理することを許すためである。
Ordered Indexed Access
要素順序を保証する必要がある場合、RISC-V Vector Extensionにはindexed-ordered memory instructionが用意されている。
代表例は次の命令である。
vloxei64.v v1, (a0), vindex vsoxei64.v v1, (a0), vindex
indexed-ordered命令では、element operationがelement orderに従ってRVWMO上で順序付けられる。
概念的には、
element 0 → element 1 → element 2 → element 3
という順序が要求される。
一方、unordered indexed命令では、要素順序は保証されない。
vluxei64.v v1, (a0), vindex vsuxei64.v v1, (a0), vindex
同じアドレスを複数要素が参照する場合
indexed memory operationでは、複数の要素が同じアドレスを参照する可能性がある。
たとえば、
index[0] = 0 index[1] = 0
であれば、element 0とelement 1は同じメモリアドレスへアクセスする。
unordered indexed loadの場合、どちらの要素が先にアクセスするかは保証されない。
element 1 → element 0
となることもあり得る。
その間に別hartのstoreが入れば、要素ごとに異なる値を読む可能性もある。
一方、indexed-ordered loadではelement orderが適用されるため、要素間の順序を前提にした処理が可能になる。
Vector実装に必要な管理
ベクトルでは、CoRR違反への対処粒度も複数考えられる。
命令全体をReplayする
最も単純な方法は、違反が見つかったvector命令全体を再実行することである。
1 elementで違反
↓
vector instruction全体をreplay
制御は単純だが、VLが大きい場合には再実行コストが高い。
対象要素だけReplayする
より細かい実装では、違反した要素だけを再実行する。
element 5だけ違反
↓
element 5のみreplay
性能面では有利だが、要素単位の完了状態、例外状態、依存関係を管理する必要がある。
Cache Line単位でReplayする
同じcache lineに属する要素群をまとめてreplayする方法も考えられる。
line Xでinvalidation
↓
line Xを参照した要素をreplay
要素単位と命令単位の中間的な粒度になる。
保守的に直列化する
実装を簡単にするため、重複アドレスの可能性が高い命令やordered indexed命令を保守的に直列化する方法もある。
Precise Trapとの関係
ベクトル命令では、途中の要素で例外が発生し、vstartを使って再開することがある。
そのため、memory ordering violationによるreplayと、architectural exceptionによる再開を区別する必要がある。
マイクロアーキテクチャ内部でreplayを行う場合は、通常、ソフトウェアから見えるvstartや例外状態を変更せずに処理する。
一方、architectural trapが発生した場合は、仕様に従って完了済み要素と未完了要素を管理しなければならない。
この点でも、ベクトルのmemory ordering implementationはスカラーより複雑になる。
順序規則の整理
ベクトルメモリアクセスの順序は、次のように整理できる。
| 対象 | 順序規則 |
|---|---|
| 異なるvector memory instruction間 | 命令レベルでRVWMOに従う |
| 通常のvector命令内部の要素 | 原則unordered |
| unordered indexed命令内部の要素 | unordered |
| indexed-ordered命令内部の要素 | element orderで順序付けられる |
したがって、
vector命令だから全要素がprogram orderで処理される
という理解は正しくない。
命令間のorderingと、命令内のelement orderingは別の規則である。
まとめ
RISC-V Vector Extensionでも、異なるvector memory instruction間ではRVWMOに従う必要がある。
したがって、同一アドレスを読む2つのvector load命令について、
先行命令の要素 = 新しい値 後続命令の要素 = 古い値
というCoRR違反をcommitしてはならない。
ただし、単一vector命令内のelement operationは原則としてunorderedである。
element orderが必要な場合は、indexed-ordered memory instructionを使用する。
ベクトル実装では、複数要素が並行して実行されるため、CoRR違反の検出とreplayはスカラーより複雑になる。
設計上は、次の粒度を選択することになる。
命令単位 要素単位 cache line単位
仕様が要求するのは、最終的なarchitectural behaviorがRVWMOとVector Extensionのordering ruleを満たすことであり、どの粒度で検証・replayするかは実装に委ねられている。
