三か月ぐらいブログをサボっていました。お久しぶりです。 以前Pythonを使う必要があったのですが、組込みのハッシュ関数が弱すぎ、大変悲惨な目にあったので、その記録です。 Pythonの組込みのハッシュ関数では、hash(-2)とhash(-1)がどちらも-2となります*…
GitHub Actionsは、GitHub上のリポジトリに何らかのイベント（pushされた、pull requestが行われた……など）が発生したときに、自動的にプログラムを実行してくれる仕組みです。 pushのたびにテストをして壊れていないかをチェックする、pushするたびにウェブ…
浮動小数点数同士の足し算や引き算の結果は、浮動小数点数で正確に表せるとは限りません。 そういった場合、近い値を持つ浮動小数点数に丸められます。 どういった場合に結果が浮動小数点数で正確に表せるか、という問題に対しては、以下のシンプルな結果が…
リオーダーバッファは、アウトオブオーダー実行をするプロセッサにおいて、その投機的な状態を保存するバッファです。 リオーダーバッファのサイズは、命令ウィンドウ（実行順序を並べ替える範囲）の大きさの上限を決めます。 命令ウィンドウに含まれる、依…
概要 RISC-Vでは、jalr t0という命令には特別な意味が割り当てられているので、関数ポインタを用いた関数呼び出しのために使うと一部のプロセッサで性能低下を引き起こします。 t0以外のレジスタを使う場合は問題なく動作するので、関数ポインタの格納にはt0…
glibcのexp関数は、倍精度浮動小数点数の指数関数をソフトウェアで計算するものです。 glibcの実装（IBM Accurate Mathematical Libraryの実装を用いたもの）は、おそらく完全精度を達成しています。 完全精度とは、入力がどんな値であっても真の値に最も近…
On the definition of ulp(x) という論文を読んだメモです。 浮動小数点数の誤差を議論するとき、最終桁の重み (Unit of Last Place, ULP) が単位として使われます。 例えば、以下のような使い方をします。 最近接丸めをした場合、その丸め誤差は0.5ULP以下…
新年になりました。今年もよろしくお願いします。 Value prediction（値予測）の世界的な大会、Second Championship Value Prediction @ HPCA'21というのが開催されているそうです。 値予測というのは投機的実行の一種で、レジスタに書き込まれる値を予測す…
なんだか指数関数の実装ばかり見ているような気がしますが、GPGPU向けの実装はどうなっているんだろうなと思ったので見てみました。 Programming Guide :: CUDA Toolkit Documentationによれば、最大誤差1ULPを保証する実装になっているようです。 ULPの定義…
近年のほとんどのプロセッサには分岐予測機構が搭載されています。 分岐予測機構は、この命令は分岐命令か否か、分岐命令だとしたらとび先はどこか、条件分岐ならそれが成立するかしないか、などを予測します。 予測が外れていた場合、正しい命令のフェッチ…
[1204.4221] Magic-state distillation with the four-qubit codeという論文のFig. 1(c)でやっていることを手計算で試して理解しました。 マジック状態とは 量子コンピュータの勉強をやると、Xゲート・Zゲート・Hゲート・CNOTゲート、などが出てきますが、こ…
Intel CPUで高速に動く、数学関数のSIMD実装に Intel Math Kernel Library というものがあります。 それに含まれる指数関数実装を読んでみました。 AVX-512（512bitレジスタがあるので、doubleを最大で八並列で演算できる）用の実装は、以下のようになってい…
なんだか分岐予測器で当てれそうなところを当ててくれなかったことがあったので、Intel CPUの分岐予測器はどんな時に分岐予測を当てることができるのかを調べてみました。 実際に調べてみると、ループのような単純な場合であっても非常に複雑怪奇な挙動を示…
先週、浮動小数点数を足していくプログラムについて、Juliaで書いた場合とC言語で書いた場合とで速度を比較しました（浮動小数点数を足すだけのプログラムがC言語よりJuliaのほうが速い、について - よーる）。 この記事について、黒木玄さん（黒木玄 Gen Ku…
なんかすごく前に話題になっていたので、確かめてみました。 数値計算に強いプログラミング言語と言えば従来FortranとC言語でしたが、近年Pythonのように書けて実用上十分な速度を達成できるJuliaが人気を集めているようです*1。 Juliaは動的言語ですが、(1)…
同時に修理に出していたもう一つのパソコンの修理が終わったようです。戻ってくるときも同じとはちょっと不思議です。
ここ一か月ほどパソコンが壊れていて修理していたのですが、修理が終わって戻ってきたのでいろいろやっていきます。
授業で知ったのですが特に証明がなかったので考えました。 仮定 構造によらずバンドの上端・下端は同じ 構造によらずバンドに入る電子数も同じ（が一定） 構造によらず電子がバンドに全部入った時のエネルギーも同じ（が一定） 状態密度として上下対称なもの…
二つの浮動小数点数を比較する演算は、C言語の演算子としては6種類（<、<=、>、>=、==、!=）ありますが、NaNの取り扱いを考えるともっとあります。 一般的なのは、以下の四状況に関してそれぞれtrueとfalseがどうなるかを考えた14種類（24=16のうち、2種類は…
二次元データを可視化する方法に、標高線を描くという方法があります。 図1: 標高線を使った可視化 また、ヒートマップを使う方法もあります。 図2: ヒートマップを使った可視化 標高線通りにヒートマップを作ってほしいのですが、gnuplotが標高線を描画する…
前に完全精度expf関数を作った（高速な完全精度 expf 関数の作り方 - よーる）ので、今度は完全精度sincosf関数を作っていきます。 作戦 まず、引数の絶対値が小さい時のsin関数とcos関数を（taylor展開などを利用して）作ります。 引数の絶対値が大きい場合…
ブール環（、、“足し算”がxorで“掛け算”がandであるような演算体系、“2で割ったあまり”）に関係する命令群です。 clmul, clmulh, clmulr 繰上りなしの掛け算です。ビット列の畳み込みと考えることもできます。 clmulは掛け算の結果の下32/64ビットを返します…
ビットフィールドやビットベクトルの操作系命令をまとめます。 bfp rs1のoffビット目からlenビットをrs2の下lenビットに置き換えます。 ここで、offとlenは（オペランド数の都合上）rs2の上位ビットを使って指定します。 offは、RV32であればrs2の16ビット目…
例によって「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…
gorc, gorci gorc命令では、「入力の両方が0なら出力の両方が0、それ以外なら出力の両方が1」というバタフライ演算を、FFTのように適用します。段のバタフライネットワークのうち、どこを有効にし、どこを無効（入力を素通し）にするかをrs2/immで指定します…
レジスタ中のビット列の順序を入れ替える命令についてまとめます。 rsレジスタの中身が[tex: \Sum{i=0}^{XLEN-1}2i\dot a_i]だった時、rdレジスタに[tex: \Sum{i=0}^{XLEN-1}2i\dot a_{f(i)}]を書き込みます。 ここで、は、[0, X_LEN-1]から[0, X_LEN-1]への…
ビット操作系の命令は多くのCPUにあり、各種のアルゴリズムを高速化することに役立っています。 オープンな命令セットのRISC-Vにもビット操作系の命令を拡張命令として導入しようという機運があり、どういった命令を追加するべきか議論されているようです。 …
ChampSimというコンピュータアーキテクチャの研究でよく使われている（？）シミュレータがあります。 他のシミュレータと比べてソースコードが簡潔なのはいい点ですが、シミュレーションの正確性はかなり怪しいです。 ソースコードを全部読んで見つけた変な…
ポラードのロー法（Pollard's rho algorithm）は、与えられた数nの非自明な因数を一つ見つける乱択アルゴリズムです。この手法が答えを返した場合、解は常に正しいことが保証されます。ただし、このアルゴリズムは「失敗」を返して終了することもあります*1…
5/29～6/4に行われたコンピューターアーキテクチャの国際会議、ISCA 2020 で開催されたワークショップ「CARRV」で発表されていた、Sonic BOOMの論文をながめて思ったことを書いておきます。 Figure 1 について この手の図ってWikiChipでよく見る（例えば、 S…
