C++でrestrictと同様の機能を実現する方法

ループのベクトル化や、その他の最適化を促進させることを目的として、C言語のrestrict修飾子を使うことがよくある。

restrict修飾子を指定したポインタは、同じ関数の他のポインタが指すメモリアドレスを指さない。複数のポインタが同じメモリアドレスを指すと、メモリ依存関係によって、ベクトル化ができなくなることが多い。 restrictを使うことで、コンパイラが「メモリ依存が無い」と判定できるようになって、ベクトル化が可能になることがある。

以下のようにするとベクトル化されない。コンパイラはruntimeチェックを入れることで、restrictが無いプログラムもベクトル化してしまうので、-mllvm -pragma-vectorize-memory-check-threshold=0を指定している。

norestrict.c

void test(double *a, double *b, int len) {
  for (int i=1; i<len; i++) {
    a[i] *= b[i] + i;
  }
}

$ clang -O2 -S norestrict.c -fno-unroll-loops -Rpass=loop-vectorize -mavx512f -mllvm -pragma-vectorize-memory-check-threshold=0

以下のようにrestrictを付けるとベクトル化されることがメッセージからわかる。

restrict.c

void test(double *restrict a, double *restrict b, int len) {
  for (int i=1; i<len; i++) {
    a[i] *= b[i] + i;
  }
}

$ clang -O2 -S restrict.c -fno-unroll-loops -Rpass=loop-vectorize -mavx512f -mllvm -pragma-vectorize-memory-check-threshold=0
restrict.c:2:3: remark: vectorized loop (vectorization width: 8, interleaved count: 1) [-Rpass=loop-vectorize]
  for (int i=1; i<len; i++) {
  ^

一方、C++の場合は、以下のように構造体のメンバとすることでベクトル化できるようになる。これは、「別のタグ名を持つ構造体への2つのポインタは別名ではない」というルールを使っている。

a.cpp

struct A {
  double v;
};

struct B {
  double v;
};

void test(struct A *as, struct B *bs, int len) {
  for (int i=1; i<len; i++) {
    as[i].v *= bs[i].v + i;
  }
}

$ clang++ -O2 -S a.cpp -fno-unroll-loops -Rpass=loop-vectorize -mavx512f -mllvm -pragma-vectorize-memory-check-threshold=0
a.cpp:10:3: remark: vectorized loop (vectorization width: 8, interleaved count: 1) [-Rpass=loop-vectorize]
  for (int i=1; i<len; i++) {
  ^

上は、-fno-strict-aliasingを指定すると、ベクトル化されなくなる。

$ clang++ -O2 -S a.cpp -fno-unroll-loops -Rpass=loop-vectorize -mavx512f -mllvm -pragma-vectorize-memory-check-threshold=0 -fno-strict-aliasing

また、C++では、コンパイラの独自拡張である__restrict__や__restrictが使える様子。

restrict.cpp

void test(double *__restrict__ a, double *__restrict__ b, int len) {
  for (int i=1; i<len; i++) {
    a[i] *= b[i] + i;
  }
}

 clang++ -O2 -S restrict.cpp -fno-unroll-loops -Rpass=loop-vectorize -mavx512f -mllvm -pragma-vectorize-memory-check-threshold=0 
restrict.cpp:2:3: remark: vectorized loop (vectorization width: 8, interleaved count: 1) [-Rpass=loop-vectorize]
  for (int i=1; i<len; i++) {
  ^

低レベルプログラミング | Igor Zhirkov, 吉川邦夫, 吉川邦夫 |本 | 通販 | Amazonのp.351 「14.6 厳密な別名のルール」を参考にした。

2020-08-12

Linux無線LAN設定

Ubuntu Server 20.04.1 LTS で無線LANの設定を行いました。以下、メモです。

マザーボードに無線LANユニットが無かったので、　IODATA WN-G300UA をUSB2.0ポートに接続し、以下の手順で無線LANの設定をしました。

まず、以下のように設定ファイルを編集します。

/etc/netplan/50-clowd-init.yaml

network:
        version: 2
        renderer: NetworkManager
        ethernets:
                enp5s0:
                        addresses:
                                - 192.168.3.10/24
                        dhcp4: false
                        gateway4: 192.168.3.1 
                        nameservers:
                                addresses:
                                        - 8.8.4.4
                                        - 8.8.8.8
                                search:
                                        - domain.local
        wifis:
                wlx3476c5f2c85f:
                        addresses:
                                - 192.168.3.10/24
                        dhcp4: false
                        gateway4: 192.168.3.1 
                        access-points:
                                SSIDXXXXX:
                                        password: "PASSXXXXX"
                        nameservers:
                                addresses:
                                        - 8.8.4.4
                                        - 8.8.8.8
                                search:
                                        - domain.local

無線LANの設定は、wifisから下です。SSIDXXXXXやPASSXXXXXには、適切なSSIDとパスワードを設定します。 enp5s0やwlx3476c5f2c85fは私のアダプタの名前なので適切な名前を設定します。

次に以下のコマンドを実行します。

設定コマンド

$ sudo apt install network-manager
$ sudo netplan apply

接続先のSSIDなどは、以下のように確認します。

$ nmcli dev wifi list

2020-07-25

浮動小数点数とビット表現の変換

浮動小数点数をビット表現に変換したり、ビット表現を浮動小数点数に変換したりすることが多いので、コンバータを作ってみました。

github.com

bfloat16以外の浮動小数点数なら、pythonでも以下のように変換できます。

 $ python3
Python 3.8.2 (default, Jul 16 2020, 14:00:26) 
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import struct
>>> hex(struct.unpack('Q', struct.pack('d', 1.0))[0])
'0x3ff0000000000000'
>>> hex(struct.unpack('I', struct.pack('f', 1.0))[0])
'0x3f800000'
>>> hex(struct.unpack('H', struct.pack('e', 1.0))[0])
'0x3c00'
>>> struct.unpack('d', struct.pack('Q', 0x3ff0000000000000))[0]
1.0
>>> struct.unpack('f', struct.pack('I', 0x3f800000))[0]
1.0
>>> struct.unpack('e', struct.pack('H', 0x3c00))[0]
1.0

上から順番に

fp64->hex
fp32->hex
fp16->hex
hex->fp64
hex->fp32
hex->fp16

です。

2019-11-04

ハイティング代数の勉強

J. ヨスト著, 清水勇二訳現代数学の基本概念上を読んでいて、p.35 の練習問題が難しかったので、この問題について書いておく。

p.35の練習問題とは、ハイティング代数において以下を示すことだ。

$t \Rightarrow (s \Rightarrow u) = t \land s \Rightarrow u$

ハイティング代数は0と1を持つ束で冪対象 $u^{s} = s \Rightarrow u$ を持つ。

冪対象の記法で書くと示したいことは以下になる。

$(u^{s})^{t} = u^{t \land s}$

$x$ を任意の元として、次の①と②, ②と③は一対一に対応する。ここで $\to$ は $\le$ を表す。

① $x \land t \land s \to u$

② $x \land t \to u^{s}$

③ $x \to (u^{s})^{t}$

また、 $y$ を任意の元として、次の④と⑤は一対一対応する。

④ $y \land t \land s \to u$

⑤ $y \to u^{t \land s}$

もし①で $x$ を $u^{t \land s}$ とした射があるならば、③の $x$ に $u^{t \land s}$ を代入して、射

$u^{t \land s} \to (u^{s})^{t}$

が存在する。すなわち以下が成り立つ。

$u^{t \land s} \le (u^{s})^{t}$

一方、もし④で $y$ を $(u^{s})^{t}$ とした射があるならば、⑤の $y$ に $(u^{s})^{t}$ を代入して、射

$(u^{s})^{t} \to u^{t \land s}$

が存在する。すなわち以下が成り立つ。

$(u^{s})^{t} \le u^{t \land s}$

したがって、 $u^{t \land s} \le (u^{s})^{t}$ , $(u^{s})^{t} \le u^{t \land s}$ , 反対称律より

$(u^{s})^{t} = u^{t \land s}$

となる。

あとは、 $u^{t \land s} \land t \land s \le u$ と $(u^{s})^{t} \land t \land s \le u$ を示せばよい。

まず、 $u^{t \land s} \land t \land s \le u$ は、 $u^{t \land s} \le u^{t \land s}$ から成り立つことがわかる。

次に、 $(u^{s})^{t} \land t \land s \le u$ は、次のように示す。

$(u^{s})^{t} \le (u^{s})^{t} \Leftrightarrow (u^{s})^{t} \land t \le u^{s} \Leftrightarrow (u^{s})^{t} \land t \land s \le u$

2019-10-14

Kleisli圏の単位律と結合律

西郷甲矢人 (著), 能美十三 (著) 圏論の道案内 ~矢印でえがく数学の世界~ (数学への招待シリーズ) の「第9章モナド」で、モナドから随伴を作るときにKleisli圏という圏が登場した。

この記事では、Kleisli圏の単位律と結合律についてまとめてみる。

まず、圏 $C$ 上のモナド $T$ とは、組 $\langle T, \eta, \mu \rangle$ であり、以下の図式を可換にするものである。

f:id:yabaniyatun:20191014195735p:plain

ここで、 $T, \eta, \mu$ は、関手 $T: C \to C$ , 自然変換 $\eta: id_C \Rightarrow T$ , 自然変換 $\mu: TT \Rightarrow T$ 。

Kleisli圏はモナドに関連して考えられる圏である。モナド $T$ に関するKleisli圏 $C_{T}$ の対象 $X_{T}$ は、圏 $C$ の対象 $X$ と同じであり、圏 $C_{T}$ の射 $f_{T}: X_{T} \to Y_{T}$ は、圏 $C$ の射 $f: X \to T(Y)$ に対応する。

対象 $X_{T}$ の恒等射 $1_{X_{T}}: X_{T} \to X_{T}$ は、圏 $C$ の射 $\eta_{X}: X \to T(X)$ に対応する。

$f_{T}: X_{T} \to Y_{T}$ と $g_{T}: Y_{T} \to Z_{T}$ の合成 $g_{T} \circ_{T} f_{T}: X_{T} \to Z_{T}$ は、圏 $C$ の射 $\mu_{Z} \circ T(g) \circ f: X \to T(Z)$ に対応する。

ここで、このように定義した恒等射が単位律を満たすこと、それから、このように定義した射および射の合成が結合律を満たすことを示したい。

まずは、恒等射が単位律を満たすこと、すなわち、任意の $f_{T}: X_{T} \to Y_{T}$ に対して、

$f_{T} \circ_{T} 1_{X_{T}} = 1_{Y_{T}} \circ_{T} f_{T} = f_{T}$

が成り立つことを示す。

圏 $C$ において、

$\mu_{Y} \circ T(f) \circ \eta_{X} = \mu_{Y} \circ T(\eta_{Y}) \circ f = f$

が成り立つことを示せばよい。

$\eta$ の自然性を表す図式とモナド $T$ の定義に使った2番目の可換図式を組み合わせた以下の図式が可換であることから、上の式が成り立つことがわかる。

f:id:yabaniyatun:20191014203533p:plain

よって、恒等射が単位律を満たすことが示せた。

次に、射および射の合成が結合律を満たすこと、すなわち

$f_{T}: X_{T} \to Y_{T}, g_{T}: Y_{T} \to Z_{T}, h_{T}: Z_{T} \to W_{T}$

に対して、

$(h_{T} \circ_{T} g_{T}) \circ_{T} f_{T} = h_{T} \circ_{T} (g_{T} \circ_{T} f_{T})$

が成り立つことを示す。

圏 $C$ において、

$\mu_{W} \circ T(\mu_{W} \circ T(h) \circ g) \circ f = \mu_{W} \circ T(h) \circ (\mu_{Z} \circ T(g) \circ f)$

が成り立つことを示せばよい。

$\mu_{W} \circ T(\mu_{W} \circ T(h) \circ g) \circ f = \mu_{W} \circ T(\mu_{W}) \circ TT(h) \circ T(g) \circ f$

ここで、モナド $T$ の定義の1番目の可換図式から、以下の図式が可換であることがわかる。

f:id:yabaniyatun:20191014205033p:plain

よって、上の式は以下になる。

$\mu_{W} \circ \mu_{T(W)} \circ TT(h) \circ T(g) \circ f$

$\mu$ の自然性を表す以下の可換図式が書けるので、

f:id:yabaniyatun:20191014205629p:plain

上の式は以下になる。

$\mu_{W} \circ T(h) \circ \mu_{Z} \circ T(g) \circ f = \mu_{W} \circ T(h) \circ (\mu_{Z} \circ T(g) \circ f)$

射および射の合成が結合律を満たすことが示せた。

図式を書くのに使ったTexソース

\documentclass[12pt]{ujarticle}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amscd}
\usepackage[all]{xy}
\def\objectstyle{\displaystyle}
\begin{document}
\[
\xymatrix{
  TTT \ar@{=>}[r]^{T\mu} \ar@{=>}[d]_{\mu T} & TT \ar@{=>}[d]^{\mu} \\
  TT \ar@{=>}[r]_{\mu} & T
}
\]
\[
\xymatrix{
  T \ar@{=>}[r]^{T\eta} \ar@{=>}[rd]_{1_T} & TT \ar@{=>}[d]^{\mu} & T \ar@{=>}[l]_{\eta T} \ar@{=>}[ld]^{1_T} \\
  & T &
}
\]
\[
\xymatrix{
  X \ar[r]^{f} \ar[d]_{\eta_X} & T(Y) \ar[d]^{T(\eta_Y)} \ar[rd]^{1_{T(Y)}} \\
  T(X) \ar[r]_{T(f)} & TT(Y) \ar[r]_{\mu_Y} & T(Y)
}
\]
\[
\xymatrix{
  TTT(W) \ar[r]^{T(\mu_W)} \ar[d]_{\mu_{T(W)}} & TT(W) \ar[d]^{\mu_W} \\
  TT(W) \ar[r]_{\mu_W} & T(W)
}
\]
\[
\xymatrix{
  TT(Z) \ar[r]^{TT(h)} \ar[d]_{\mu_Z} & TTT(W) \ar[d]^{\mu_{T(W)}} \\
  T(Z) \ar[r]_{T(h)} & TT(W)
}
\]
\end{document}

2019-10-12

C言語で浮動小数点数をビットパターンに変換する方法

1.0の64bit浮動小数点数、32bit浮動小数点数、16bit浮動小数点数でのビットパターンを求めます。

a.c

#include <stdio.h>
#include <stdint.h>


int main() {
  union A {
    double d;
    float f;
    _Float16 f16;
    uint64_t i64;
  };

  union A a;
  a.d = 1.0;

  printf("64bit 0x%lx\n", a.i64 & 0xFFFFFFFFFFFFFFFF);
  a.f = 1.0;
  printf("32bit 0x%lx\n", a.i64 & 0xFFFFFFFF);
  a.f16 = 1.0;
  printf("16bit 0x%lx\n", a.i64 & 0xFFFF);

}

コンパイルして、実行すると以下になります。

$ clang a.c
$ ./a.out 
64bit 0x3ff0000000000000
32bit 0x3f800000
16bit 0x3c00

2019-07-27

Pythonで浮動小数点数をビットパターンに変換する方法

64bit浮動小数点数(1.0の例)

>>> import struct
>>> hex(struct.unpack('<Q', struct.pack('<d', 1.0))[0])
'0x3ff0000000000000'

32bit浮動小数点数(1.0の例)

>>> import struct
>>> hex(struct.unpack('<I', struct.pack('<f', 1.0))[0])
'0x3f800000'

16bit浮動小数点数(1.0の例) Python3.6以上で動く

>>> import struct
>>> hex(struct.unpack('<H', struct.pack('<e', 1.0))[0])
'0x3c00'