2020-08-09

RISC-Vのビット操作系拡張（B拡張）のまとめ（その5）

ブール環（ $\mathbb{F}_2$ 、 $\mathbb{Z}/2\mathbb{Z}$ 、“足し算”がxorで“掛け算”がandであるような演算体系、“2で割ったあまり”）に関係する命令群です。

`clmul`, `clmulh`, `clmulr`

繰上りなしの掛け算です。ビット列の畳み込みと考えることもできます。

clmulは掛け算の結果の下32/64ビットを返します。 clmulhは掛け算の結果の上32/64ビット（下から32～63/64～127ビット目）を返します。ここで、繰上りがないため、clmulhの最上位ビットは常に0です。

clmulrはその再上位ビットを除いた上32/64ビット（下から31～62/63～126ビット目）を返します。名前のrは、reverseに由来します。clmulrの結果は、ビット順序逆転した結果同士のclmulの結果のビット順序逆転と同じになるからです。

巡回冗長検査（Cyclic Redundancy Check, CRC）やハッシュ関数の実装などに有用だそうです。自分自身とのclmul/clmulhを使うと、0を00に、1を01に変換する（32/64ビットのビット列の各ビットの間に0を挿入して64/128ビットのビット列にする）操作を実現します。また、-1とのclmulはprefix sum（ここで言うsumはxor）を求めるのに使えます（グレイコードのデコードに使えます）。

`crc32`, `crc32c`

巡回冗長検査（CRC）をまさにそのまま計算する命令です。

`bmatxor`, `bmator`, `bmatflip`

64bitのレジスタを、8×8のビット行列だとみなして、行列演算を行う命令です。

bmatxorは、“足し算”がxorであるような行列乗算、bmatorは“足し算”がorであるような凝結乗算、bmatflipは行列転置です。

bmatflipは、zip三回分に相当します。

2020-08-08

RISC-Vのビット操作系拡張（B拡張）のまとめ（その4）

ビットフィールドやビットベクトルの操作系命令をまとめます。

`bfp`

rs1のoffビット目からlenビットをrs2の下lenビットに置き換えます。ここで、offとlenは（オペランド数の都合上）rs2の上位ビットを使って指定します。

offは、RV32であればrs2の16ビット目から20ビット目、RV64であればrs2の32ビット目から37ビット目または48ビット目から53ビット目を使います。 lenは、RV32であればrs2の24ビット目から27ビット目、RV64であればrs2の40ビット目から44ビット目または56ビット目から60ビット目を使います。

「または」と書いてある部分は、rs2の62ビット目から63ビット目が2であれば後者を、そうでなければ前者を使います。

lenは1から16/32になるはずです。そこで、4/5bitのフィールドは、すべてが0の時に16/32と解釈する工夫がなされます。

offやlenを指定する定数をrs2の上位ビットに送り込むには、pack命令が有用です。 RV32の場合、addiで作った12ビットの定数をpack命令で上位ビットに送り込めば、任意のlenとoffを実現できます。 RV64の場合、luiで作った32ビットの定数をpack命令で上位ビットに送り込めば、任意のlenとoffを実現できます（「または」と書いてある部分を後者で使うモードを利用します）。

`bext`, `bdep`

bext命令は、rs1のうち、rs2の中で1がたっているビットの部分だけを下位ビットに集約します。 bdep命令は、その逆操作を行います。つまり、rs2の中で1がたっているビットの位置に、rs1の各ビットを展開します。

bext命令を使うと、Magic Bitboardみたいなことが簡単にできます。

また、bdep命令を使うと簡潔データ構造で用いられるようなselect1(rank)演算が実現可能です。先頭から10ビット目の1の位置を知りたい場合、bdep a0, 1ull<<10, a0; ctz a0, a0のようにすることで求まります。

2020-07-26

Visual Studio 2019でllvmがビルドできない問題とその対処

例によって「Visual Studioでclangを使う」話ではなく、「Visual Studioでllvm自体をビルドする」話です。

症状

Building Attributes.inc...
llvm-tblgen.exe: Unknown command line argument '-gen-attrs'. Try: '..\..\..\Debug\bin\llvm-tblgen.exe -help'
llvm-tblgen.exe: Did you mean '-stats'?
llvm\include\llvm/IR/Attributes.h(74,14): fatal error C1083: include ファイルを開けません。'llvm/IR/Attributes.inc':No such file or directory

などのエラーメッセージが出てビルドできません。

確かにllvm/IR/Attributes.incは存在しません。これは自動生成されるファイルなのですが、生成するllvm-tblgen.exeというプログラムが、（ビルドできているにもかかわらず）正しく動作しないことが原因です。

原因究明

「'llvm/IR/Attributes.inc'」などとググっても原因はよくわかりません（単に依存関係を間違えている事例ばかり出てきます）。

「llvm-tblgen msvc」とググったところ、以下の手掛かりを得ました（二つ目のサイトは一つ目のサイトにリンクがありました）。

原因

最新のmsvcではヘッダが更新されC++20の機能が追加されました。この機能はC++11/14/17でコンパイルする際は（マクロ等で）適切に無効にされる必要がありますが、そうなっていないというmsvcのバグが原因です。

アトミック変数の初期化周りの仕様がC++20から変更されますが、どうやらこれが破壊的変更になっていて、コンパイルは素通りするものの動作が変わってしまっているようです。

解決法

コンパイラを変更する方法

問題のあるヘッダファイルが使われるのは16.6以降のバージョンです。

したがって、Visual Studio 2019 のビルド番号とリリース日 | Microsoft Docs から16.6以前のバージョン（例えば16.5.5）をインストールすれば、問題は発生しません。

ソースコードを変更する方法

この問題へのワークアラウンドがコミットされている（[ManagedStatic] Fix build errors with clang-tblgen in Debug mode usin… · llvm/llvm-project@28a6713 · GitHub）ため、このコミット以降であれば問題は発生しません。

先日リリースされたllvm10.0.1には、このコミットが含まれています。

2020-07-19

RISC-Vのビット操作系拡張（B拡張）のまとめ（その3）

`gorc`, `gorci`

gorc命令では、「入力の両方が0なら出力の両方が0、それ以外なら出力の両方が1」というバタフライ演算を、FFTのように適用します。 $log_2 XLEN$ 段のバタフライネットワークのうち、どこを有効にし、どこを無効（入力を素通し）にするかをrs2/immで指定します。

XLEN'(1,2,4,8,16,32,64)ビット毎に、「X(1,2,4,8,16,32)ビット飛ばしのXLEN/Xビットすべてが0ならそれらを0のままに、そうでないならそれらをすべて1に変更」を行うというSIMD命令が実現可能です。

8ビット毎に、「その8ビット全てが0なら0のまま、そうでないならそれらをすべて1に変更」というSIMD命令orc.bは、文字列検索に有用です。

2020-07-18

RISC-Vのビット操作系拡張（B拡張）のまとめ（その2）

レジスタ中のビット列の順序を入れ替える命令についてまとめます。

rsレジスタの中身が[tex: \Sum{i=0}^{XLEN-1}2ⁱ\dot a_i]だった時、rdレジスタに[tex: \Sum{i=0}^{XLEN-1}2ⁱ\dot a_{f(i)}]を書き込みます。ここで、 $i → f(i)$ は、[0, X_LEN-1]から[0, X_LEN-1]への全単射です。XLENは、レジスタの幅で、32とか64です。

`rol`, `ror`, `rori`

循環シフト（ローテート）です。入れ替えの計算式は、循環シフト幅を $k$ として $f(i) = (i+k) \mod XLEN$ （左ローテートの場合）、 $f(i) = (i-k) \mod XLEN$ です。

循環シフト幅が定数の命令は、roriのみです。これは、左ローテートでできることと右ローテートでできることは同一だからです。実際、左kビットローテートは、右(XLEN-k)ビットローテートと同値です。

`grev`, `grevi`

ビット列順序逆転の一般化です。入れ替えの計算式は、パラメータ値を $k$ として $f(i) = i XOR k$ です。 $k = XLEN-1$ の時、ビット列順序逆転になります。それ以外のパラメータのうち、二進法で表した時010*のようにあらわせるパラメータ値では、より幅の短いXLEN'(1, 2, 4, 8, 16, 32)に対するXLEN''(1,2,4,8,16,32)ビット毎のブロックの列順序逆転のSIMD命令とみなせます。さらにそれ以外のパラメータ値の場合は、解釈の難しい動作をすることになります。

`shfl`, `unshfl`, `shfli`

ビット列のアウトシャッフルの一般化です。入れ替えの計算式を書き下すことは難しいですが、 $f(i) = iのビット列の順序を変更したもの$ になっています。パラメータ値がXLEN-1の時、アウトシャッフルになります。

2020-07-05

RISC-Vのビット操作系拡張（B拡張）のまとめ（その1）

ビット操作系の命令は多くのCPUにあり、各種のアルゴリズムを高速化することに役立っています。

オープンな命令セットのRISC-Vにもビット操作系の命令を拡張命令として導入しようという機運があり、どういった命令を追加するべきか議論されているようです。

とりあえずVersion 0.92版のpdfを見てまとめていきます。

riscv-bitmanip/bitmanip-0.92.pdf at master · riscv/riscv-bitmanip · GitHub

ビットカウント系命令

`clz`

count leading zeros です。二進数としてあらわした時、上位ビットから何ビット0が続くかを数えます。

`ctz`

count trailing zeros です。二進数としてあらわした時、下位ビットから何ビット0が続くかを数えます。「その数が2^kの倍数である」が成り立つ最大のkを求めることになります。

`pcnt`

pop count です。二進数としてあらわした時の1の数を数えます。三オペランド命令（二引数命令）にし、第二引数がゼロレジスタであるときの挙動がpop countと一致するような命令にしたほうが便利との提案が出されています。 github.com

ビット毎論理演算命令

`andn`

rs1 & ~rs2を計算します。

`orn`

rs1 | ~rs2を計算します。

`xnor`

rs1 ^ ~rs2を計算します。

パック命令

`pack`

二つのレジスタの下位半分を連結した値を計算します。 0xffff0000ffff0000のような数を二命令で生成することができます。また、16bit/32bitのローテート操作の実現に利用可能です。さらに、ゼロ拡張にも使えます。

f:id:lpha_z:20200706001707p:plain — pack命令の動作（32bitの場合）

`packu`

二つのレジスタの上位半分を連結した値を計算します。

f:id:lpha_z:20200706001759p:plain — packu命令の動作（32bitの場合）

`packh`

二つのレジスタの下位八ビットを連結した十六ビット値を計算します。

f:id:lpha_z:20200706001740p:plain — packh命令の動作

最大・最小を求める命令

`min`/`max`

rs1とrs2を符号付き整数として解釈した時、両者のうち大きくないほう/小さくないほうの値を計算します。 maxは絶対値を求めるのにも使えます。また、飽和演算にも役立てられます。

`minu`/`maxu`

rs1とrs2を符号無し整数として解釈した時、両者のうち大きくないほう/小さくないほうの値を計算します。

サブワード符号拡張命令

`sext.b`

下位八ビットの内容を符号拡張した数を計算します。

`sext.h`

下位十六ビットの内容を符号拡張した数を計算します。

その他

zext.bはandi rd, rs, 255で実現可能です。
zext.hは32bitの場合はpack rd, rs, zero、64bitの場合はpackw rd, rs, zeroで実現可能です。
zext.wはpack rd, rs, zeroで実現可能です（64bitの場合のみ利用価値があるため、64bitの場合を前提としています）。
sext.wはaddiw rd, rs, 0で実現可能です。

一ビット操作命令

`sbset`/`sbseti`

rs1のrs2/immビット目を1にした数を計算します。

`sbclr`/`sbclri`

rs1のrs2/immビット目を0にした数を計算します。

`sbinv`/`sbinvi`

rs1のrs2/immビット目を反転した数を計算します。

`sbext`/`sbexti`

rs1のrs2/immビット目を計算します。計算される値は、0か1のどちらかです。

一のシフト系命令

（うまい訳語がないので「一のシフト」としました）

`slo`/`sloi`

左シフトですが、下位ビットは1で埋められます。 ~(~rs1 << (rs2 & XLEN-1))と書けます。 0xffffffみたいな数を一命令で生成することができます。

`sro`/`sroi`

右シフトですが、上位ビットは1で埋められます。 ~(~rs1 >> (rs2 & XLEN-1))と書けます。

条件分岐内蔵命令

2020-06-28

ChampSimの変な点についてメモ

ChampSimというコンピュータアーキテクチャの研究でよく使われている（？）シミュレータがあります。他のシミュレータと比べてソースコードが簡潔なのはいい点ですが、シミュレーションの正確性はかなり怪しいです。ソースコードを全部読んで見つけた変な点をメモしておきます（大半は先週今週あたりに直りました）。

ソースコードの問題点

デコード幅がおかしい

不等号を間違えていてデコード幅が1多くなっています。今は直っています。

デコーダーがパイプライン化されていない

このサイクルにデコードした命令数ではなく、デコードステージにあるすべての命令数がデコード幅以下になるようなコードになっています。今は直っています。

何回もフェッチされる

フェッチ完了後に同じキャッシュラインにある命令がフェッチ開始されると、フェッチ中状態に戻ってしまいます。developブランチでは直っています。

命令のスケジューリングがおかしい1

[ROB.head, ROB.size)の範囲のみをスケジューリングしていたため、[0, ROB.head)の範囲の命令はROB.headが一巡するまでスケジューリングされなくなっています。developブランチでは直っています。

SPPというプリフェッチャが間違っている

配列外アクセスをしている部分があります。DPC3に参加したSPP+PPFというプリフェッチャもバグっているらしいです（2020 ISCA p.125）。

キャッシュのレイテンシ設定がおかしい

L2キャッシュでヒットした場合、そのレイテンシはL1D_LATENCY+L2C_LATENCY+L1D_LATENCYになります。意図したものとは思いづらいです。

分岐命令が全て方向分岐予測器にかけられる

無条件分岐命令であっても、分岐方向予測器がnot-takenだと言えば分岐予測ミスになります。逆に、間接分岐命令であっても、分岐方向予測器がtakenだと言えば分岐予測成功になります。 BTBが欠如しているため、こういうことになるようです。

x86トレースにおける問題点

pop命令のレイテンシが長すぎる

pop命令はRSPレジスタとなんらかのメモリをソースとし、RSPレジスタと他のレジスタをデスティネーションとする命令です。RSPレジスタの値は、RSPレジスタの値足す8になるのですが、見た目上、メモリから読み出した内容に依存してRSPが決まるようにも見えるため、そのような依存の連鎖でシミュレーションされています。シミュレーション対象プログラムの実行速度はほとんどこれに支配されています。DPC3の性能向上値はこの点で怪しいです。

A64トレースにおける問題点

命令のスケジューリングがおかしい2

命令間の依存関係を推定する部分にヒューリスティクスが導入されましたが、A64トレースでは完全におかしくなります。

条件分岐命令が即実行される

条件分岐命令のソースレジスタがEIPレジスタだけになってしまっているため、本当はほかのレジスタに依存しているであろう条件命令が即実行されてしまいます。これはシミュレーション対象プログラムを不当に高速化しています。IPC1の性能向上値はこの点で怪しいです。

clmul, clmulh, clmulr

crc32, crc32c

bmatxor, bmator, bmatflip

bfp

bext, bdep

症状