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…

SonicBOOM (BOOMv3) の論文をながめて思ったこと

5/29~6/4に行われたコンピューターアーキテクチャの国際会議、ISCA 2020 で開催されたワークショップ「CARRV」で発表されていた、Sonic BOOMの論文をながめて思ったことを書いておきます。 Figure 1 について この手の図ってWikiChipでよく見る(例えば、 S…

Windows 10 May 2020 Update 後に DvorakJ を使う

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

最大公約数をもっと高速に求める番外編(その2)

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

最大公約数をもっと高速に求める番外編(その1)

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

ウィンナ・チューバの仕組みの予想

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

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

0からN-1までの数が入った配列

今までは以下のように作っていましたが、 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...>…

PPM-like分岐予測器とTAGE分岐予測器の違い

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

いそがしい一週間の終わり

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

あまりしゃべらないと調子よくない気がする ちゃんと調整していきたいです

make_index_sequenceを短く書いた(C++11用)

std::make_index_sequence<N>は、std::index_sequence<0, 1, 2, ..., N-1>に展開される、メタプログラミングを行う場合や最適化に便利なエイリアステンプレートです。 しかし、以下の問題点があります。 C++14で追加されたため、C++11環境では使えない*1 多くの</n>…

バーチャルっていろいろときれいなのがいいね

リングバッファを作るときstd::dequeを使うのはちょっと楽でちょっと損

容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。 しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。 C++の場合、std::deque*1を…

gshare分岐予測器について、の補足

gshare分岐予測器について - よーるの補足です。 分岐命令の上位アドレスとグローバル分岐履歴をxor、について 吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Ve…

gshare分岐予測器について

gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。 このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。 この記事には、以下のものが含ま…

いつも通りの日々の連続?

クイックソートのピボットは中央値でなく四分位数を選択したほうが高速

概要 クイックソートは一般に高速なソートアルゴリズムとして知られています。 アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。 しかし、最近の高性能プロセッサ…

sshでログインできなくなった問題と解決策

リモートマシンにsshログインしようとしたところ、パスフレーズの入力後に何も反応しなくなることがありました。 正しくない公開鍵を使った場合や、正しくないパスフレーズを入力した場合はログインできないと応答が返ってくるので、リモートマシンの側の問…

近況

輻輳が発生しています……

64bit符号なし整数を素因数分解するのにかかる時間

64bit符号なし整数を素因数分解するため、事前に32bit符号なし整数で表せる素数をリストアップしておくとします。 方法1: 素数のリストをビットベクトルで保持し、試し割り 32bit符号なし整数で表せる奇数が素数であるかを、0, 1で表した列(ビットベクトル…

ABC152のE問題 Flatten を遅い方法で解いた

以下にはABC152のE問題 Flatten のネタバレが含まれます。 この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。 foldr …

Karatsuba乗算の最適化をした

Karatsuba乗算、あるいはToom–Cook2乗算とは、入力a0、a1、b0、b1が与えられたとき、a0*b0、a0*b1+a1*b0、a1*b1の三つを出力する際、必要な乗算を四回から三回に減らせるアルゴリズムです。ただし、減算ができることを要求します。 長乗法(筆算と同様の手順…

64bit版RISC-Vで即値を生成するときの罠

RISC系の命令セットでは、一命令でレジスタに書き込める即値と、一命令では書き込めない即値が存在する設計になっています。 一命令では書き込めない即値の場合、二命令以上かけて即値を生成することになるわけですが、そこに存在する罠に引っかかった記録で…

新年になりました

今年もよろしくお願いします。 2020ってちょっと不思議な感じのする数字です。 今年は、きっかけを待つのではなくて、自分で行動を起こせる年にしたいです。 あと、お酒飲むのやめます。心身の健康に悪いので……。