この頃よくきっぷを買っています。 オンラインで予約を取って電子的なきっぷを買ってもいいのですが、紙のきっぷが好きでよく買っています。 きっぷは、「どこからどこまで」だけではなく、「どこを通るか」も指定して買う必要があります（「新宿→150円」み…
倍精度浮動小数点数よりも高い精度で計算したいときに便利なアルゴリズムに、TwoSumというものがあります。 TITAN VというNVIDIAのGPGPU上でこれを高速化したので紹介します。 TwoSum TwoSumは、二つの浮動小数点数（aとb）を入力とし、以下の二つを返すアル…
近年の深層学習の隆盛により、IEEE 754以外の数値表現の利用が広まっています。 そのような数値表現をまとめてみました。 深層学習で利用された数値表現の軽い歴史 機械学習には詳しくないので、エポックメイキングなイベントについて的を外しているかもしれ…
（ロビンソン）算術の超準モデルの話です。 第一不完全性定理によれば、一定条件を満たす公理系には、証明も反証もできない命題が存在します。 ここで、「一定条件」とは次のことを言います。 ロビンソン算術を含む（等号付きの一階述語論理で、足し算と掛け…
PentiumのFDIVバグという有名な設計ミスがあります。 これは、PentiumプロセッサのFDIV命令（浮動小数点数除算命令）が正しくない値*1を返すという問題で、回路設計の誤りが原因です。 ブルン定数（双子素数の逆数の和の極限で、収束することが知られている…
NVIDIAが開発している、cutlassというライブラリがあります。 github.com cutlassは、GPUで線形代数演算をしたいときに役立つ外枠のライブラリです。 どう役に立つのか、もっとも単純な行列積を例にとって説明します。 行列積プログラムを書くことは非常に簡…
以前の記事（行列乗算の最適化入門（コンシューマー向けGPU編） - よーる）で、RTX 4090向けの単精度行列積コードを作成しました。 その後の記事（行列乗算のさらなる最適化（コンシューマー向けGPU編） - よーる）ではそれを改良し、cuBLASを超える60.0 TFL…
以前の記事（行列乗算の最適化入門（コンシューマー向けGPU編） - よーる）で、RTX 4090向けの単精度行列積コードを作成し、cuBLASの98.4%である58.3 TFLOPSの性能を達成しました。 そのコードを更に最適化した結果、cuBLASを超える60.0 TFLOPSの性能を出せ…
Gandalfという、AIチャットゲームがあります。 このゲームの目的は、AIとチャットを繰り返し、AIが隠しているパスワードを聞き出すことです。 つまり、適切なプロンプトインジェクションを行うことで、AIに言ってはいけないことを言わせるゲームということで…
不定積分を求めようとすると少しめんどくさいのような三角関数の有理式について、不定積分を求める技巧的な方法を前からまとめようと思っていたので、書き出しました。 究極的には での置換が万能ですが、とにかくめんどくさいので、それを避ける方法を書き…
カットなしの二階算術は、自身の無矛盾性を示せる体系です。 つまり、第二不完全性定理が成り立たないわけですが、どういう仕組みになっているか、詳しく書きたいと思います。 元ネタ：自分自身の無矛盾性が証明できる強い自然数の理論体系 – Depressive Dia…
C言語やC++では、コンパイラが気を利かせてFMA命令にコンパイルすることがあります。 具体的には、次のように書いた場合、浮動小数点数乗算命令と浮動小数点数加算命令が使われるのではなく、浮動小数点数融合積和演算命令（以下FMA命令）が使われることがあ…
最近浮動小数点数演算器を作っているので、作るときのポイントを忘れないようにメモしておきたいと思います。 以下の全4回で書いていく予定です。 最近接丸めの浮動小数点数加算器の作り方（今回） 最近接丸めの浮動小数点数乗算器の作り方 RISC-Vの規格に従…
FizzBuzz - MN-Core Challenge というコードゴルフに挑戦した記録です。 スコアはぴったり100になりました。 ただのFizzBuzzですが、SIMDプロセッサであるMN-Coreでこの手の処理をするのはかなり面倒です。 以下、順を追って説明していきます。 最初に作った…
コンシューマー向けGPUは、倍精度演算性能こそ高くないものの、単精度でよければ驚異的な演算性能を持っています。 例えば、NVIDIA社のGeForce RTX 4090は、カタログスペックで82 TFLOPSもの性能があります。 カタログスペックに近い性能を出すことは困難で…
今まで3回にわたって、行列サイズがコンパイル時にわかる場合の正方行列乗算の最適化を取り扱ってきました（行列乗算の最適化入門 - よーる、行列乗算の最適化入門（マルチコア編） - よーる、行列乗算の最適化入門（GPGPU編） - よーる）。 行列サイズがコ…
前回の記事（行列乗算の最適化入門（マルチコア編） - よーる）では、CPU上でマルチスレッドの理論性能の89%以上（1.1 TFLOPS）を出せる簡単なコードを紹介しました。 今回はさらに高速化するため、GPGPUを使ってみます。 GPGPUとしては、前回セットアップし…
この前Ubuntu 24.04 LTSがリリースされたので、これの上でTITAN VというGPUを動かせるようにしていきます。 TITAN V について TITAN Vは、2018年にNVIDIA社が発売した非常に高価なコンシューマー向けGPUです。 国内代理店の菱洋(りょうよう)エレクトロからの…
前回の記事（行列乗算の最適化入門 - よーる）では、L3キャッシュに乗りきる程度のサイズ（だいたい1000×1000くらい）の行列積について、シングルスレッドの理論性能の84%以上を出すことができるコードを紹介しました。 4000×4000くらいのもう少し大きな行列…
以前の記事（Yosysを使ってみる（その1） - よーる）でYosysというオープンソースの論理合成ツールを紹介しました。 今回は、乗算器を複数の作り方で作ってみて、その回路面積を比較してみようと思います。 全加算器セルのような複数出力のセルを使いたいの…
そんなに大きくない行列乗算をそこそこの速度にする必要が生じたので、そのメモです。 L3キャッシュに乗るくらいのサイズの行列乗算において、シングルスレッドの理論性能の80%以上を出すことができました。 実験環境 Intel Core i9 12900Kを用いました。 共…
x86やRISC-Vなどの多くの機械語命令セットには、64ビット整数同士の積（128ビット整数になる）の上位64ビットを求める命令が存在します。 しかし、C言語やC++の言語標準には128ビット整数が存在しないため、これを簡単に得ることができません。 gccなどのコ…
与えられた整数に対し、以下の素数の数を数えるアルゴリズムを理解します。 Library Checkerで高速な実装を調べてみると、提出107115が最速ですが、このソースコードは未定義動作を含んでいます（ランキング上位を見てみると、62015, 107115, 147826, 150290…
今週の水曜日にMN-Core勉強会があり、そこでMN-Core 2のエミュレータが公開されたようです。 そこで、MN-Core 2の機械語（アセンブリ言語がvsmと呼ばれているらしい？）のコードゴルフをやってみます。 MN-Core 2の機械語なんて書いたことないので、丁寧に勉…
Library CheckerのFactorizeという問題でfastestを取ったので、そのコードの解説です（速度ランキング）。 Factorizeは、までの整数が高々100個与えられ、それらを素因数分解せよ、という問題です。 概要 上位陣（13ms～15ms）の解法では、ECM（楕円曲線を用…
最近久しぶりにUnityでゲーム作りをしています。 共同で開発するためにgitを使うのですが、gitコマンドをWSL2から使用するといまいちな感じになったので、何とかする方法のメモです。 プロジェクトはWSL2の外に作る UnityプロジェクトをWSL2の中（/home/lpha…
新年になりました。 タイトルに関してですが、なんだか話があったので軽くまとめておきます。 要点としては、 投資の期待値が標準偏差に比して大きい（インデクスファンドなどはこの条件を満たす）投資商品がある場合、 余剰資金があるなら、 何も考えずにそ…
この記事は自作CPU Advent Calendar 2023の24日目の記事です。 みなさんが使っているパソコンのCPUは、そのほとんどがアウトオブオーダー実行をしているはずです。 しかし、アウトオブオーダーCPUの作り方が書かれた教科書はあまりないような気がします。 ト…
浮動小数点数を扱う時に注意しなければいけない例として、0.1 + 0.2が0.3にならない、というものがあります。 具体的には、0.1 + 0.2が0.30000000000000004になってしまい、0.3にならないプログラミング言語が多数存在します。 この問題について、以下の記事…
アセンブリプログラムを書いていたら、遭遇したのでメモです。 さすがにプログラム全てをアセンブリ言語で書くのは大変なので、性能上重要ではないところはコンパイラのコード生成に任せて、性能上重要なところだけアセンブリプログラムで書くということはあ…
