なんだか指数関数の実装ばかり見ているような気がしますが、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…

親指シフトなどかな入力系を使っている場合は以下が参考になります（本稿も当該記事を参考にしています。ありがとうございます）。 Windows 10 May 2020 Update とDvorakJ での親指シフト入力の問題を解消する 症状 Dvorak配列にしてローマ字入力をすると、[…

前回のコードを最適化していきます。 主要なループ*1のうち、最も時間がかかるのはctz部分（3サイクルレイテンシのBSF命令にコンパイルされます）です。 これを少しでも早く実行開始できれば、さらに高速に動作するはずです。 ここで、二の補数表現の特徴か…

なんだか最近最大公約数を高速に求めたい読者（競技プログラマ？）が多いようなので、書いておきます。 最大公約数を求める改良版アルゴリズムとして、Stein's algorithm（Binary GCD）というものがあります。 ナイーブな実装では、普通の互除法よりも遅いで…

ウィンナ・チューバ - Wikipediaを見ていて、どういう仕組みになっているのか面白いと思ったので、メモです。 私は金管楽器を*1演奏したことが一切ないので、以下に書かれていることは、あくまで物理的な計算に基づいた憶測です。 Wikipediaによれば、ウィン…

毎週末に何かしらの締め切りがあって、インプットもアウトプットもできない日々が続きます…… あまりこういう癖をつけないように、来週からは何か少しずつでも始めましょう。

今までは以下のように作っていましたが、 template<std::size_t... Indeces> constexpr auto make_iota_impl( std::index_sequence<Indeces...> ) { return std::array { Indeces... }; } template<std::size_t N> constexpr auto make_iota() { return make_iota_impl( std::make_index_sequence<N>() ); } C++20で</n></std::size_t></indeces...></std::size_t...>…

An Alternative TAGE-like Conditional Branch Predictor https://hal.inria.fr/hal-01799442/document という論文に載っていて、 TAGE分岐予測器は、PPM-like分岐予測器と異なり、 * グローバル分岐履歴の最長一致で予測を立てるのではなく、二番目に長く一…

世界から人間が消えた気がする