異世界とか(その2)

またちょっと違う世界に行っていました(前回とは違う世界です)。 そこの住人は、やはり親切でした。 お客様だから親切にしてくれたという可能性もありますが、住人同士もそんな感じだったので、本質的にそうなのでしょう。 私に親切にする理由は特になさそ…

Pythonの弱いhashがたくさん衝突する例

三か月ぐらいブログをサボっていました。お久しぶりです。 以前Pythonを使う必要があったのですが、組込みのハッシュ関数が弱すぎ、大変悲惨な目にあったので、その記録です。 Pythonの組込みのハッシュ関数では、hash(-2)とhash(-1)がどちらも-2となります*…

GitHub Actionsで自動テストできるようにしたメモ

GitHub Actionsは、GitHub上のリポジトリに何らかのイベント(pushされた、pull requestが行われた……など)が発生したときに、自動的にプログラムを実行してくれる仕組みです。 pushのたびにテストをして壊れていないかをチェックする、pushするたびにウェブ…

二進浮動小数点数の加減算の結果が正確に表せる場合について

浮動小数点数同士の足し算や引き算の結果は、浮動小数点数で正確に表せるとは限りません。 そういった場合、近い値を持つ浮動小数点数に丸められます。 どういった場合に結果が浮動小数点数で正確に表せるか、という問題に対しては、以下のシンプルな結果が…

リオーダーバッファのサイズを測ってみた

リオーダーバッファは、アウトオブオーダー実行をするプロセッサにおいて、その投機的な状態を保存するバッファです。 リオーダーバッファのサイズは、命令ウィンドウ(実行順序を並べ替える範囲)の大きさの上限を決めます。 命令ウィンドウに含まれる、依…

RISC-Vで関数ポインタ呼び出しにjalr t0を使ってはいけない

概要 RISC-Vでは、jalr t0という命令には特別な意味が割り当てられているので、関数ポインタを用いた関数呼び出しのために使うと一部のプロセッサで性能低下を引き起こします。 t0以外のレジスタを使う場合は問題なく動作するので、関数ポインタの格納にはt0…

glibcのexp(x)をいじめる

glibcのexp関数は、倍精度浮動小数点数の指数関数をソフトウェアで計算するものです。 glibcの実装(IBM Accurate Mathematical Libraryの実装を用いたもの)は、おそらく完全精度を達成しています。 完全精度とは、入力がどんな値であっても真の値に最も近…

Unit of Last Place (ULP) の定義について

On the definition of ulp(x) という論文を読んだメモです。 浮動小数点数の誤差を議論するとき、最終桁の重み (Unit of Last Place, ULP) が単位として使われます。 例えば、以下のような使い方をします。 最近接丸めをした場合、その丸め誤差は0.5ULP以下…

CVPシミュレータを解読したメモ

新年になりました。今年もよろしくお願いします。 Value prediction(値予測)の世界的な大会、Second Championship Value Prediction @ HPCA'21というのが開催されているそうです。 値予測というのは投機的実行の一種で、レジスタに書き込まれる値を予測す…

CUDA libraryのexp(x)を読んだ

なんだか指数関数の実装ばかり見ているような気がしますが、GPGPU向けの実装はどうなっているんだろうなと思ったので見てみました。 Programming Guide :: CUDA Toolkit Documentationによれば、最大誤差1ULPを保証する実装になっているようです。 ULPの定義…

分岐予測ミスペナルティを測ってみた

近年のほとんどのプロセッサには分岐予測機構が搭載されています。 分岐予測機構は、この命令は分岐命令か否か、分岐命令だとしたらとび先はどこか、条件分岐ならそれが成立するかしないか、などを予測します。 予測が外れていた場合、正しい命令のフェッチ…

量子コンピュータの勉強(その1)

[1204.4221] Magic-state distillation with the four-qubit codeという論文のFig. 1(c)でやっていることを手計算で試して理解しました。 マジック状態とは 量子コンピュータの勉強をやると、Xゲート・Zゲート・Hゲート・CNOTゲート、などが出てきますが、こ…

Intel MKLのSIMD exp関数を読んだ

Intel CPUで高速に動く、数学関数のSIMD実装に Intel Math Kernel Library というものがあります。 それに含まれる指数関数実装を読んでみました。 AVX-512(512bitレジスタがあるので、doubleを最大で八並列で演算できる)用の実装は、以下のようになってい…

Intel CPU の分岐予測器を調べてみた(ループの場合だけ)

なんだか分岐予測器で当てれそうなところを当ててくれなかったことがあったので、Intel CPUの分岐予測器はどんな時に分岐予測を当てることができるのかを調べてみました。 実際に調べてみると、ループのような単純な場合であっても非常に複雑怪奇な挙動を示…

「単純和」プログラムの速度をJuliaとC言語で比較した

先週、浮動小数点数を足していくプログラムについて、Juliaで書いた場合とC言語で書いた場合とで速度を比較しました(浮動小数点数を足すだけのプログラムがC言語よりJuliaのほうが速い、について - よーる)。 この記事について、黒木玄さん(黒木玄 Gen Ku…

浮動小数点数を足すだけのプログラムがC言語よりJuliaのほうが速い、について

なんかすごく前に話題になっていたので、確かめてみました。 数値計算に強いプログラミング言語と言えば従来FortranとC言語でしたが、近年Pythonのように書けて実用上十分な速度を達成できるJuliaが人気を集めているようです*1。 Juliaは動的言語ですが、(1)…

パソコンの修理がおわった(二日連続・二回目)

同時に修理に出していたもう一つのパソコンの修理が終わったようです。戻ってくるときも同じとはちょっと不思議です。

パソコンの修理がおわった

ここ一か月ほどパソコンが壊れていて修理していたのですが、修理が終わって戻ってきたのでいろいろやっていきます。

バンド端付近にフェルミエネルギーが来る場合、そこの状態密度が高い構造が選ばれる、について

授業で知ったのですが特に証明がなかったので考えました。 仮定 構造によらずバンドの上端・下端は同じ 構造によらずバンドに入る電子数も同じ(が一定) 構造によらず電子がバンドに全部入った時のエネルギーも同じ(が一定) 状態密度として上下対称なもの…

浮動小数点数の比較演算に関するメモ

二つの浮動小数点数を比較する演算は、C言語の演算子としては6種類(<、<=、>、>=、==、!=)ありますが、NaNの取り扱いを考えるともっとあります。 一般的なのは、以下の四状況に関してそれぞれtrueとfalseがどうなるかを考えた14種類(24=16のうち、2種類は…

gnuplotの等高線でヒートマップを描きたい

二次元データを可視化する方法に、標高線を描くという方法があります。 図1: 標高線を使った可視化 また、ヒートマップを使う方法もあります。 図2: ヒートマップを使った可視化 標高線通りにヒートマップを作ってほしいのですが、gnuplotが標高線を描画する…

完全精度sincosf関数の作り方(その1)

前に完全精度expf関数を作った(高速な完全精度 expf 関数の作り方 - よーる)ので、今度は完全精度sincosf関数を作っていきます。 作戦 まず、引数の絶対値が小さい時のsin関数とcos関数を(taylor展開などを利用して)作ります。 引数の絶対値が大きい場合…

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

ブール環(、、“足し算”がxorで“掛け算”がandであるような演算体系、“2で割ったあまり”)に関係する命令群です。 clmul, clmulh, clmulr 繰上りなしの掛け算です。ビット列の畳み込みと考えることもできます。 clmulは掛け算の結果の下32/64ビットを返します…

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

ビットフィールドやビットベクトルの操作系命令をまとめます。 bfp rs1のoffビット目からlenビットをrs2の下lenビットに置き換えます。 ここで、offとlenは(オペランド数の都合上)rs2の上位ビットを使って指定します。 offは、RV32であればrs2の16ビット目…

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…

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

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

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

レジスタ中のビット列の順序を入れ替える命令についてまとめます。 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]への…

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

ビット操作系の命令は多くのCPUにあり、各種のアルゴリズムを高速化することに役立っています。 オープンな命令セットのRISC-Vにもビット操作系の命令を拡張命令として導入しようという機運があり、どういった命令を追加するべきか議論されているようです。 …

ChampSimの変な点についてメモ

ChampSimというコンピュータアーキテクチャの研究でよく使われている(?)シミュレータがあります。 他のシミュレータと比べてソースコードが簡潔なのはいい点ですが、シミュレーションの正確性はかなり怪しいです。 ソースコードを全部読んで見つけた変な…

ポラードのロー法で64bit符号なし整数を素因数分解する

ポラードのロー法(Pollard's rho algorithm)は、与えられた数nの非自明な因数を一つ見つける乱択アルゴリズムです。この手法が答えを返した場合、解は常に正しいことが保証されます。ただし、このアルゴリズムは「失敗」を返して終了することもあります*1…