概要 アルゴ式が公開している素因数分解するアルゴリズム（と称しているもの）は、特定の入力に対して正しく動作しません（無限ループします）。 ポラードのロー法が失敗した場合、疑似乱数生成器のシードのみを変更するのではなく、疑似乱数生成器自体を変…
先々週の記事（SRT除算について - よーる）で取り扱ったように、SRT法は除算をするアルゴリズムですが、少しだけ変形すると平方根を求めることにも使えます。 まずは、長除法（割り算を筆算で計算する手順）と開平法（平方根を筆算で計算する手順）の類似性…
SRT除算は、回復法や非回復法と同様、商を上の桁から求めていくタイプの除算アルゴリズムです。 この時、回復法や非回復法と違い、商を冗長表現で求める点が特徴です。 商を冗長表現で求めることは、各桁の商の選択に多少の自由度を生み、これが回路的なメリ…
CORDICアルゴリズムという、乗算なしにsin/cos/sinh/coshを求めるアルゴリズムがあります。 乗算器すらないような非常に小規模なプロセッサでsinやcosが必要になった場合などに有用です。 sin/cosを求める場合 戦略 加法定理を思い出します。 を因数としてく…
浮動小数点数同士を足したり引いたりする場合、その数学的な結果は浮動小数点数で表せるとは限りません。 そのため、結果を適当に浮動小数点数に戻す、丸めが行われます。 丸めを行うためには、最終的な結果に使われる桁数より少し多く情報を保持しておく必…
C言語標準ライブラリに含まれるqsortは、配列のソートを行ってくれる関数です。 第一引数にソート対象の配列、第二引数に配列の要素数、第三引数一要素のサイズ、第四引数に比較関数、のように渡すことで、ソートを行ってくれます。 ここで、第四引数に渡す…
gcc12から、RISC-VのB拡張命令を使ったコンパイルが可能になりました。 B拡張には、ビット演算を取り扱う命令が含まれています。 したがって、B拡張に対応したCPUでは、gcc12でコンパイルすることによりプログラムが高速化することが期待できます。 RISC-Vの…
前回に引き続き、Zen2の方向分岐予測器の仕組みを明らかにしていきます。 分岐履歴の仕組み gselect(GAs)のような単純な分岐予測器は、分岐履歴をそのまま分岐予測テーブルのインデクスの一部として利用します。 gshareのような分岐予測器であっても、分岐履…
前回に引き続き、Zen2の方向分岐予測器の仕組みを明らかにしていきます。 分岐履歴に使われる情報 分岐元アドレス 前回と同様のアセンブリを用いて、分岐命令のアドレスのみを変化させていき、パターン長1～48の予測を当てることができるかを調べていきます…
最初はGolden Coveの方向分岐予測器を調べていたのですが、規則的な分岐履歴系列を与えても正答率が100%に張り付かないなど、あまりにもアナログで複雑な挙動を示すのであきらめました。 それと比べてZen2の方向分岐予測器は、正答率が0%や100%に張り付く非…
第12世代インテル® Core™ プロセッサーのEコア（高効率コア）はGracemontというマイクロアーキテクチャでできています。 このコアで命令を実行したときのレイテンシを調べたものにuops.info - Tableがありますが、測定方法がよくなくて正しい値になっていま…
第12世代インテル® Core™ プロセッサーのPコア（高性能コア）はGolden Coveというマイクロアーキテクチャでできていますが、Golden CoveにはFADD演算器が新規搭載されました。 FADD演算器は、浮動小数点数加算を高速に行う演算器であり、そのレイテンシは2 c…
以下の問題で時間を溶かしたので、メモを残しておきます。 概略 おかしなusing宣言がコンパイラを混乱させ、壊れたバイナリの生成を引き起こすことがあります。 static_castするとポインタの値が変わるような継承構造を持つクラス*1では、基底クラス由来のメ…
この記事は C++ Advent Calendar 2021の5日目の記事です。 2021年ももうすぐ終わりそうですが、みなさんはC++20を使っているでしょうか？ C++20では、符号付き整数型のビット表現が二の補数であると規定されました。 また、ビット表現を保ったまま別の型に変…
またちょっと違う世界に行っていました（前回とは違う世界です）。 そこの住人は、やはり親切でした。 お客様だから親切にしてくれたという可能性もありますが、住人同士もそんな感じだったので、本質的にそうなのでしょう。 私に親切にする理由は特になさそ…
三か月ぐらいブログをサボっていました。お久しぶりです。 以前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)…
