SIMDによる将棋Bitboard計算の高速化 - すぎゃーんメモ
自作Rust製将棋合法手生成ライブラリ、計算の高速化のためBitboardの128bit計算をSIMDで行うようx86_64のAVX2、AArch64のNEON、wasm32のsimd128で動くようにそれぞれ実装して 各環境で多少速く探索できるようになった。https://t.co/h7Dz3X6BhT— すぎゃーん💯 (@sugyan) July 2, 2022 ということでSIMDでの高速化のメモ。 SIMDとは 実装 x86_64 基本演算 飛び利き計算 AArch64 同値判定、ゼロ値判定 飛び利き計算 Iterator WebAssembly Benchmark x86_64 AArch64 WebAssembly 感想 SIMDとは ja.wikipedia.org の通り、複数のデータを1命令で同時に演算する、というもの。 将棋Bitboardは81マスのデータを表現する
x86/x64最適化勉強会8 レポート - Cybozu Inside Out | サイボウズエンジニアのブログ
サイボウズ・ラボの光成です。 今回は2月17日に開催された「x86/x64最適化勉強会8」の模様についてお伝えします。 第7回からなんと約3年振りです。 今回の発表内容はAVX-512周りの話が2件、命令の正確なレイテンシの話、年明けから世間を騒がせているMeltdownとSpectreの話が2件でした。 以下、それぞれの発表内容について簡単に解説します。 AVX-512関係 私の発表は「AVX-512（フォーマット）詳解」でした。 AVX-512はまだSkylake-Xなどの一部のCPUにしか搭載されていませんが、今後徐々に採用が増えるでしょう。 （注意）21ページの「3値論理」は「3項論理」の方が適切です。 AVX-512のレジスタ構成や基本的な命令セットを説明した後、AVX2までにはなかったマスクレジスタ、静的丸めモード、ブロードキャストなどの解説をしました。 マスクレジスタは便利に
MKL-DNNで学ぶIntel CPUの最適化手法 - Cybozu Inside Out | サイボウズエンジニアのブログ
初めに サイボウズ・ラボの光成です。 DNN（deep neural network : 深層学習）といえばGPUや専用プロセッサを使うのが主流です。 しかしIntelはCPUで高速にDNNをするためのライブラリ MKL-DNN を提供しています。 MKL-DNNはIntelの最新CPUに対応したオープンソースソフトウェアなのでコードを見ると勉強になります。 ここではMKL-DNNで使われているテクニックをいくつか紹介します。 概要 MKL-DNNの紹介 Xbyakの紹介 呼び出し規約 圧縮displacement ReLU exp 内積 vpdpbusd キャッシュコントロール 想定読者 C++11とx64 CPUのアセンブリ言語の知識をある程度仮定します。 機械学習についてはその知識がなくても最適化手法が理解できるよう、最小限の説明をします。 MKL-DNNの特長 まずMKL-DNNの
WebAssembly's post-MVP future: A cartoon skill tree - Mozilla Hacks - the Web developer blog
People have a misconception about WebAssembly. They think that the WebAssembly that landed in browsers back in 2017—which we called the minimum viable product (or MVP) of WebAssembly—is the final version of WebAssembly. I can understand where that misconception comes from. The WebAssembly community group is really committed to backwards compatibility. This means that the WebAssembly that you creat
C++でSIMDを書くときのオススメライブラリ libsimdpp
概要 C++でSIMDを書く人向けの良いライブラリを見つけました。 https://github.com/p12tic/libsimdpp SIMDをtemplateで扱うことができるので、SSE、AVXなどの異なった命令セットや、float, doubleなどの異なった型を同じコードで扱うことができます。 メリット 命令セットを簡単に切り替えられる 型を簡単に切り替えられる ヘッダーオンリーで導入が楽 アセンブラや組み込み関数を使うくらいならlibsimdppを使った方が良いと思います。 デメリット GPUと横断の抽象化(OpenCLなど)はできない 最新の命令に追従しないかもしれない OpenCLとどちらを選ぶかは吟味する必要がありそうです。 OpenCLだとCPU向けのカリカリチューニングはできないかもしれないので、カリカリチューニングをする必要があるなら、libsimdppが良いと
過去に開発した、高難易度案件の技術概要 - Qiita
自分語りすみません。自己紹介ついでです 自己紹介 学生の頃ふと図書館においてあった古いゲーム雑誌に 「ゲーム業界では服装も髪も自由だ。黒髪でリクルートスーツ着ている人より、金髪でラフな服装をしている人のほうが きっとエンタテイメントな人生をおくってるに違いない。ゲーム業界では独創的な人は大歓迎だ」 といったリクルート記事をみて 一瞬でゲームプログラマに決めました 学生時代は勉強は出来たけど、集団生活や 授業を聞くことが出来ず常に授業中走り回ってました 大学も3ヶ月で教師と喧嘩して辞めて 東京に出て フリーでビジネスプログラミングをしました 高校時代に ゲームを逆アセンブルして、グラフィックローダや音楽ドライバ等を高速化して 会社に送りつけたりしてたので、すんなり仕事はできました そこからは お金がほしい時はビジネスプログラム、夢がほしい時はゲームプログラムと 業界を行ったり来たりし、ソーシ
Rustでソートアルゴリズム (7)バイトニックソート (SIMDで高速化) - Qiita
概要 並列化が容易なため、GPGPU等で有用であるバイトニックソートを実装する。 Wikipediaでの説明(英語) ナイーブな実装 前提条件 前回と同様にRustのバージョンは1.19.0とします。 fn sort<T: PartialOrd>(&self, source: &mut [T]) { let source_size = source.len(); let size = source_size.next_power_of_two(); if source_size != size { return; } let half_size = size >> 1; let mut i = 2; while i <= size { let mut j = i >> 1; while j > 0 { let ml = j - 1; // 下位ビットマスク let mh = !ml; //
HotSpot JavaVM の SIMD 最適化を効かせる方法 - Qiita
HotSpot JavaVM のベクトル化変換 最近の HotSpot JavaVM はスカラー演算の繰り返し処理をベクトル化し SIMD 命令に変換する最適化を行っています (SIMD とは何ぞやという話は後半参照)。実際に最適化が効くコードで試してみたところ 1.5～2.8 倍程度の速度向上が見られたので、大量の演算処理を行う (GPGPU に頼らない) Java ライブラリでうまく使うことが出来れば有効な最適化手段になるかもしれません。 HotSpot の SIMD 最適化は Superword-Level Parallelism (SLP) に基づいています (以降この最適化は SLP と呼びます)。元々この論文は時代を反映して SIMD 未対応の画像・音声処理をコンパイラやランタイムのレイヤーで SIMD を利用する命令に変換することを目的としていましたが、これは SIMD 命令
SIMD型について - JS.next
概要 新しいプリミティブ型であるSIMD型及びAPIがV8で実装されてきている。 SIMDとは、複数の数値を並べて１つの値としたようなデータ型である。 これはCPUによって効率良くサポートされているデータ型であり、 1 + 2 -> 3 をするように [ 1, 2, 3, 4 ] + [ 2, 3, 4, 5 ] -> [ 3, 5, 7, 9 ] を1回の演算ですることができる。 つまり、沢山の数値を扱う場面でSIMD型を利用することで、何倍ものパフォーマンス向上が期待できる。 （※WASMに入ることとなり、ESからは一旦取り除かれました。） 実装される型 float32x4 32bit浮動小数点型を4つ並べた128bitのデータ型 float32はJSの通常のnumberであるところのfloat64より精度が低い int32x4 32bit符号付き整数型を4つ並べた128bitのデータ
Writing x86 SIMD using x86inc.asm | Ronald S. Bultje
In multimedia, we often write vector assembly (SIMD) implementations of computationally expensive functions to make our software faster. At a high level, there are three basic approaches to write assembly optimizations (for any architecture): intrinsics; inline assembly; hand-written assembly. Inline assembly is typically disliked because of its poor readability and portability. Intrinsics hide co
EmscriptenからSSEとかpthreadを使って爆速にする
Webでとにかく高速に計算したい やまだです。Webでとにかく高速な計算を行うために人生の何％かを使っています。 前回はJavaScriptから直接SIMD.jsを呼びましたが今回はEmscriptenを使用し、C言語からSIMD命令を呼び出してみます。 題材としては定番ですがマンデルブロ集合を使用します。 マンデルブロ集合は以下の漸化式で計算が可能でしばしば並列演算の課題としてとりあげられます。 z は複素数なので実部と虚部をXY平面に表すと以下のようになります。 Emscriptenを使う 今回はWebでということでC言語のコードをJavaScriptコードにコンパイルするEmscriptenを使用します。 Emscriptenを使用するとasm.jsを利用した最適化をかけることができるため単純にJavaScriptで実装した時よりも高速になることがあります。 Emscriptenでは
emscripten で SIMD.js を使う - Qiita
コンパイル時とリンク時に emcc -s SIMD する。 SIMD.js が使われるケースは3種類ある。 clang デフォルトの LLVM autovectorization が働いて自動的に SIMD 化する GCC 拡張の SIMD Vector Extensions で明示的に使う x86 の Streaming SIMD Extensions 命令を使う。詳細は 大本営 を読むべし opencv など sse サポートしているものをを asm.js にする場合は 3 が使えそう SIMD.js が有効なブラウザを用意する -s SIMD で JS 出力すると SIMD.js の polyfill が付いてくる。 これをそのまま使うと遅くなる。 2017年上半期現在標準で SIMD が有効なブラウザはない。 chrome の場合起動フラグでV8の起動フラグを渡せば有効になる。 c
どれだけ速く文字列からスペースを削除できるのか | POSTD
時によってプログラマは文字列から不要な文字を取り除きたい場合があります。例えば、テキストの一部からすべての行の末尾文字を削除したいとします。 その時、全スペース(‘ ‘)や改行コード(‘\n’および‘\r’)を削除する問題を考えてみましょう。 効率的に実行するにはどのような方法がいいのでしょうか。 size_t despace(char * bytes, size_t howmany) { size_t pos = 0; for(size_t i = 0; i < howmany; i++) { char c = bytes[i]; if (c == '\r' || c == '\n' || c == ' ') { continue; } bytes[pos++] = c; } return pos; } 上記のコードはUTF-8でエンコードされた文字列で動作します。UTF-8がASCII
SIMDの組み込み関数のことはじめ - koturnの日記
はじめに 現代のCPUではSIMD(Single Instruction Multiple Data)命令を利用することができる． SIMD命令とはその名の通り，ひとつの命令で複数のデータを処理するものである． Intel系のCPUでは，MMX/SSE/AVX/AVX-512といったSIMD命令が利用可能であり，ARM CPUではNEONというSIMD命令が用意されている． 各SIMDとSIMD用のレジスタの対応関係は以下のようになる． 項目 利用可能レジスタ MMX 64bit のMMレジスタ SSE 128bit のXMMレジスタ AVX 256bit のYMMレジシタ AVX-512 512bit のZMMレジシタ ARM NEON 64bitのD(Double-Word)レジスタおよび128bitのQ(Quad-Word)レジスタ これらのレジスタを用いて，例えば4つのint型を一
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - minio/md5-simd: Accelerate aggregated MD5 hashing performance up to 8x for AVX512 and 4x for AVX2. Useful for server applications that need to compute many MD5 sums in parallel.
GitHub - kaityo256/sevendayshpc: 一週間でなれる！スパコンプログラマ
高速化チューニングとその関連技術２
GitHub - AdamNiederer/faster: SIMD for humans
SIMD / GPU Friendly Branchless Binary Search
Reddit - Dive into anything