André Seznec氏はOGEHL分岐予測器を、Pierre Michaud氏はPPM-like分岐予測器を、それぞれ提出しました。
OGEHL分岐予測器は、GEHLパーセプトロン分岐予測器(hashed perceptron分岐予測器)の改良です。
GEHLは、GEometric History Length(幾何級数的履歴長)の略です。
PPM-like分岐予測器は、予測アルゴリズムがTAGE分岐予測器とほぼ同じで、学習アルゴリズムが微妙に異なるものです。
OGEHL分岐予測器は2位、PPM-like分岐予測器は5位でした。
André Seznec氏はTAGE-LSC分岐予測器を提案しました(2011/12/5, 44th MICRO)。
ここで、"LSC"はLocal history Statistical Corrector予測器で、短めのローカル分岐履歴を使うGEHL(LGEHL)パーセプトロン分岐予測器です。※禁忌です
よく読んでいませんが、あとは大体ISL-TAGEと同じだと思います。
cbp4(2014/6/14, 41th ISCA併設ワークショップ)
André Seznec氏は現実的部門と非現実部門にTAGE-SC-L分岐予測器を提出しました。
また、Pierre Michaud氏は非現実的部門にFive poTAGEs and a COLT分岐予測器を提出しました。
さらに、André Seznec氏とPierre Michaud氏は共著で非現実的部門にMulti-poTAGE+SC分岐予測器を提出しました。
なお、Jorge Albericio氏、Joshua San Miguel氏、Natalie Enright Jerger氏、Andreas Moshovos氏は共著で現実的部門と非現実部門にWormhole予測器を提出しました(正確には、提出したのはISL-TAGE + Wormholeです。Wormhole予測器は、Loop予測器と同様に、TAGEの出力を上書きするタイプの予測器です)。
Five poTAGEs and COLT分岐予測器は、普通のグローバル履歴を使うTAGEで作られたpoTAGEと、グローバル履歴以外の不思議な履歴を使うTAGEで作られた4つのpoTAGE、あわせて5つのpoTAGEの出力をCOLT予測器に入れて最終的な分岐予測を行います。
Multi-poTAGE+SC分岐予測器は、Five poTAGEs and COLT分岐予測器の後ろに"SC"をつけたものです。
cbp4の後
André Seznec氏、Joshua San Miguel氏、Jorge Albericio氏は共著で、TAGE-GSC-IMLI分岐予測器を提案しました(2015/12/8, 48th MICRO)。
TAGE-GSC-IMLI分岐予測器は、TAGE分岐予測器に"GSC"と"IMLI"を加えたものです。
ここで、"GSC"はグローバル履歴しか使わないStatistical Corrector予測器、"IMLI"はInner Most Loop Iterationカウンタを用いた予測器です。
Leading Zero Anticipatory (LZA)は、二進法で表されたNビット符号つき整数A, Bを受け取り、A+Bを直に計算することなしにA+B+1の上位に0が何ビット並ぶか(Leading Zero Count, LZC)を(多少の誤差の範囲で)予測することです。
以前の記事(Leading Zero Anticipation (LZA) の勉強 - よーる)では、適宜左右オペランドを交換することでA+Bが常に非負となることを仮定する方式を紹介しました。
この方式の欠点は、Aの絶対値とBの絶対値の大小比較というΘ(log N)段の回路の出力を待つ必要がある点です。
#include <iostream>#include <cassert>intget_estimate( int i, int j ) {
int P = i ^ j;
int X = ~P;
int G = i & j;
int N = ~G;
int O = i | j;
int Z = ~O;
int n = N | N<<1;
int o = O | O<<1;
int L = X>>1 & n & o
| P>>1 & G & O<<1
| P>>1 & Z & N<<1 ;
return L & 0x1fffe | 1;
}
longlong count[2];
voidcheck( int i, int j ) {
int abs = std::abs(i + j + 1);
int est = get_estimate(i, j);
int diff = __builtin_clzll(abs) - __builtin_clzll(est);
assert( 0 <= diff && diff <= 1 );
++count[diff];
}
intmain() {
for( int i = 0; i < 65536; ++i ) {
for( int j = 0; j < 65536; ++j ) {
check(i,j);
check(i,-j);
check(-i,-j);
}
}
std::cout << "LZA == LZC " << count[0] << std::endl;
std::cout << "LZA == LZC-1 " << count[1] << std::endl;
}
一方で、新しい拡張として取り入れられたmin/maxはこの方針を踏襲していません。
min/maxは100/110というfunct3を、minu/maxuは101/111というfunct3を持ちます。
つまり、符号の有無をfunct3[0]で、条件の反転をfunct3[1]で、それぞれ区別しており、標準的な命令のエンコーディングと異なります。
どうやらslt/sltuの対立(符号の有無をfunct3[0]で区別している)に合わせてしまったらしいです(Regularize MIN vs. MINU encoding to match SLT vs. SLTU by aswaterman · Pull Request #88 · riscv/riscv-bitmanip · GitHub)。
一応、div/divuなどの対立もfunct3[0]で区別しているため、一見合理性があるように見えます。
しかし、slt/sltu、div/divu、rem/remuはいずれも条件が反転した命令を持たない命令であり、そうでない命令と同列に扱うべきではありません。
min/max/minu/maxuのエンコーディングはblt/bge/bltu/bgeuやamomin/amomax/amominu/amomaxuのエンコーディングに合わせるべきでした。
czero.eqz/czero.nez命令のエンコーディングは、この失敗を上塗りするものとなっています。
RISC-V Integer Conditional (Zicond) operations extension Version 1.0(RISC-V International)
RISC-V Bit-Manipulation ISA-extensions Version 1.0.0(著作権者不明。RISC-V(暗黙にRISC-V Internationalを意味する可能性もあり)またはJacob Bachmeyer, Allen Baum, Ari Ben, Alex Bradbury, Steven Braeger, Rogier Brussee, Michael Clark, Ken Dockser, Paul Donahue, Dennis Ferguson, Fabian Giesen, John Hauser, Robert Henry, Bruce Hoult, Po-wei Huang, Ben Marshall, Rex McCrary, Lee Moore, Jiří Moravec, Samuel Neves, Markus Oberhumer, Christopher Olson, Nils Pipenbrinck, Joseph Rahmeh, Xue Saw, Tommy Thorn, Philipp Tomsich, Avishai Tvila, Andrew Waterman, Thomas Wicki, and Claire Wolf)
RISC-V Bitmanip Extension Document Version 0.93(Jacob Bachmeyer, Allen Baum, Ari Ben, Alex Bradbury, Steven Braeger, Rogier Brussee, Michael Clark, Ken Dockser, Paul Donahue, Dennis Ferguson, Fabian Giesen, John Hauser, Robert Henry, Bruce Hoult, Po-wei Huang, Ben Marshall, Rex McCrary, Lee Moore, Jiří Moravec, Samuel Neves, Markus Oberhumer, Christopher Olson, Nils Pipenbrinck, Joseph Rahmeh, Xue Saw, Tommy Thorn, Avishai Tvila, Andrew Waterman, Thomas Wicki, and Claire Wolf)
The RISC-V Instruction Set Manual Volume I: Unprivileged ISA Document Version 20191213(Arvind, Krste Asanović, Rimas Avižienis, Jacob Bachmeyer, Christopher F. Batten, Allen J. Baum, Alex Bradbury, Scott Beamer, Preston Briggs, Christopher Celio, Chuanhua Chang, David Chisnall, Paul Clayton, Palmer Dabbelt, Ken Dockser, Roger Espasa, Shaked Flur, Stefan Freudenberger, Marc Gauthier, Andy Glew, Jan Gray, Michael Hamburg, John Hauser, David Horner, Bruce Hoult, Bill Huffman, Alexandre Joannou, Olof Johansson, Ben Keller, David Kruckemyer, Yunsup Lee, Paul Loewenstein, Daniel Lustig, Yatin Manerkar, Luc Maranget, Margaret Martonosi, Joseph Myers, Vijayanand Nagarajan, Rishiyur Nikhil, Jonas Oberhauser, Stefan O’Rear, Albert Ou, John Ousterhout, David Patterson, Christopher Pulte, Jose Renau, Josh Scheid, Colin Schmidt, Peter Sewell, Susmit Sarkar, Michael Taylor, Wesley Terpstra, Matt Thomas, Tommy Thorn, Caroline Trippel, Ray VanDeWalker, Muralidaran Vijayaraghavan, Megan Wachs, Andrew Waterman, Robert Watson, Derek Williams, Andrew Wright, Reinoud Zandijk, and Sizhuo Zhang)
*5:What's new for RISC-V in LLVM 16 - Muxupに"the previously proposed but now abandoned Zbt extension (part of the earlier bitmanip spec)"と書かれています。ただし、出典が明記されていないため、RISC-Vの公式の見解であるとは確認できませんでした。