2020/02/12(水)kv-0.4.50

kvライブラリを0.4.50にアップデートしました。

今回は、卒論修論のシーズンが終わって、学生たちがライブラリを使うことで発見してくれた問題点の解決が主な内容です。利用して下さり、問題点を見つけてくれた学生のみなさまに感謝します。

内容は、
  • dd (double-double)用のfrexpが、入力が2のベキ乗よりも僅かに小さい値のときに正しく動作していなかったバグの修正。
  • interval.hppで、内部型としてfrexpが誤差を含む可能性があるような型を用いていたとき (例えばdd)、logがごく稀に正しい値を返していなかったバグの修正。
  • ddの(精度保証付きでない)sinとcosで、引き戻し処理が雑だったのを修正。
の3点です。特に、2番目は精度保証が破れている可能性があるため、重大な修正です。

ddのfrexpのバグ

frexpは、
    double x, y;
    int i;
    y = frexp(x, &i);
のように呼び出すと、xを入力として 0.5 ≤ |y| < 1, x = y × 2iを満たすようなyとiを計算してくれる関数で、(IEEE754の指数部とは1ずれるが)指数部を取り出してくれる関数としてよく用いられます。ddに対しても、
    kv::dd x, y;
    int i;
    y = frexp(x, &i);
のように同様に使える関数を用意していました。これの実装は、
    friend dd frexp(const dd& x, int* m) {
        double z1, z2;
        z1 = std::frexp(x.a1, m);
        z2 = std::ldexp(x.a2, -(*m));
        return dd(z1, z2);
    }
のようなものでした。しかしこれだと、xが(1, -2-54)のように2のベキ乗よりわずかに小さく、2のベキ乗と小さな負の数の和で表現されている場合、指数部を正しく取り出すことが出来ません。これを、
    friend dd frexp(const dd& x, int* m) {
        double z1, z2;
        z1 = std::frexp(x.a1, m);
        z2 = std::ldexp(x.a2, -(*m));
        if ((z1 == 0.5 && z2 < 0) || (z1 == -0.5 && z2 > 0)) {
            z1 *= 2;
            z2 *= 2;
            (*m)--;
        }
        return dd(z1, z2);
    }
のように修正する必要がありました。完全に作者の見落としであり、これを見つけてくれた学生には感謝しかないです。このバグが発生する確率は非常に低いので、かなりしつこく追い込まないと見つからない種類のバグだと思います。これにより、x = 1-2-54に対して、
x: 0.999999999999999944488848768742172978818416595458984375
y: 0.4999999999999999722444243843710864894092082977294921875
i: 1
のように誤った(0.5 ≤ |y| < 1を満たしていない)値を返していたのに対して、
x: 0.999999999999999944488848768742172978818416595458984375
y: 0.999999999999999944488848768742172978818416595458984375
i: 0
のように正しく計算されるようになりました。

interval<dd>のlogのバグ

前のddのfrexp問題に対処しているうちに、ある問題点に気付きました。それは、例えばx = 1+2-1074みたいな上位と下位の数が非常に離れたdd数に対して、誤差無しでfrexpを実行することが不可能であるという問題です。このxに対するfrexpは、
  • y = 0.5+2-1075
  • i = 1
となるべきですが、2-1075を今のdoubleで表現することは出来ません。よって、必然的に誤差が生じることになります。

frexpなんてあまり使わないし、誤差が生じることを断っておけばいいか、くらいに思ったのですが、ライブラリ内でfrexpを使っている箇所を探していたらありました、数学関数logです。log(x)を計算するのに、x=y×2iのように分解する方法を使っていました。そして、frexpに誤差が発生する可能性を考慮しておらず、frexpの戻り値を信用してそのまま計算していました。実際、doubleやmpfrではfrexpで誤差が発生することは無いのですが、ddだとこれが問題になります。

実際、log(1+2-1074)をinterval<dd>で計算すると、
[0,0]
のように誤った(真値を含まない)値が計算されました。frexpは、返却値のうち仮数部yが問題であり、指数部iは信頼できるので、指数部iのみ使って、yは改めて区間演算するように精度保証付きlogの計算方法を改めることで対処しました。これで、
[0,9.881312916824930883531375857364427447301196052286495288511713650013510145404
17503730599672723271984759593129390891435461853313420711879592797549592021563756
25260142638062280905569163433569796420737743727211399746144610001277481830712996
87746249467945463392302800634307707961482524771311823420533171133735363740791206
21249863890543182984910658610913088802254960259419999083863978818160833126649049
51429573802945356031871047722310026960705298694403875805362142149834066644536895
06671441664863872184765786916736120212023012339619506156684554636658495809965049
46155275185449574931216955640746893939906729403594535543517025132110239826300978
22029020757254763345019116747794671979873296198823284114052741805584855350891304
5817507736501283943653106689453125e-324]
のように正しい値を含む区間が返されるようになりました。

一応表現可能とはいえ、1+2-1074のような上位と下位が大きく離れたdd数が生成されることは稀であり、このバグに遭遇する確率は極めて低そうですが、可能性がゼロでない限り精度保証付き数値計算のライブラリとしては大きな問題と言えます。発見できて幸運でした。

ddのsin,cosの引き戻し問題

こちらは、精度保証付きのsin,cosでなく、sin,cosにintervalでない素のddを入れたときの問題です。元々ddに数学関数は実装されていなかったのですが、近似計算とはいえあれば便利だろうと、後で割と雑に実装したものです。が、sin,cosの引数を0近辺に引き戻すのに、2πを何度も引き算するようなあまりに雑な実装になっていました。多分後で直そうとして忘れていたものと思われます。元々精度保証は何も考えていない部分ですが、これだと大きな引数のときに計算時間が問題になりそうです。ちゃんと割り算するように直しました。

おわりに

ddは本当に鬼門で、何度も予想もしないバグに遭遇します。

精度保証付き数値計算のライブラリは、バグがあれば当然精度保証にならないわけで、プログラムにバグがないことをどうやって保証するのか、という宿命的な問題を抱えています。数学の定理の自動証明や、プログラムの自動検証を行うような研究もなされています。

(将来は分かりませんが)現在のところ、数学の定理が正しいかどうかは、多くの数学者が証明を検証してどうやら正しそうだ、と思えたら正しい、という段階のようです。プログラムも同じことで、大勢の人が使い、またソースコードを見て、どうやら正しそうだと思えたら正しい、とするしかないように思います。そのために、精度保証付き数値計算のプログラムは必ずオープンでなければならないし、また大勢の人に使われなければならないと考えています。

2019/12/20(金)nvidia-dockerインストールメモ

Ubuntu 18.04にnvidia-dockerをインストールしたときのメモです。

機械学習などでCUDAの実行環境が必要になることは多いかと思います。自分は囲碁AIを動かすのに必要となりました。ところが、環境構築がかなり複雑で、また使いたいソフトウェアによってcudaやcudnnの必要なversionが異なることも多く、苦労させられます。VMwareやVirtualBoxなどの仮想化環境を使いたくなりますが、残念ながらそれらの仮想マシンからはGPUは見えません。またWSLからもGPUは見えません。

そこで解決策の一つとして考えられるのが、nvidia-dockerです。dockerはコンテナ型の仮想環境を提供するもので、VMwareなどに比べて例えばメモリ空間を共用できるなど、とても軽いものです。nvidia-dockerはNvidiaのGPUを仮想化して共有することが出来ます。NvidiaのGPUでいろいろなソフトウェアを試したいとき、これはとても便利です。cudaやcudnnがインストールされた状態のイメージも公開されているため、それをダウンロードすればインストールの手間も省けます。元々nvidia-dockerはdockerをNvidiaのGPUを扱えるようにした改造版?でしたが、docker本家がversion 19.03でNvidia GPUに対応したため、19.03以降は普通にdockerを入れた後に追加のパッケージを入れるように変更されました。

以下、Ubuntu 18.04にnvidia-dockerをインストールしたときの様子をメモしておきます。入れたマシンは、
です。ともに普通にUbuntu 18.04を入れたまっさらな状態です。

まず、Nvidia GPUのためのドライバを入れます。これだけはホストマシンに入れる必要があります。まず、
ubuntu-drivers devices
として使用可能なドライバを検索します。ここで、GTX-1060デスクトップの方は、
== /sys/devices/pci0000:00/0000:00:01.0/0000:01:00.0 ==
modalias : pci:v000010DEd00001C20sv00001458sd0000D005bc03sc00i00
vendor   : NVIDIA Corporation
model    : GP106M [GeForce GTX 1060 Mobile]
driver   : nvidia-driver-430 - distro non-free
driver   : nvidia-driver-390 - distro non-free
driver   : nvidia-driver-435 - distro non-free recommended
driver   : xserver-xorg-video-nouveau - distro free builtin
のように情報が表示されました (2019年12月)。GTX-1050ノートの方は何も見えなかった(2019年6月)ので、
sudo add-apt-repository ppa:graphics-drivers/ppa
sudo apt update
のようにPPAの追加が必要でした。これが、ハードの違いによるものか、実行した時期の違いによるものかは検証していません。PPA追加後は、
== /sys/devices/pci0000:00/0000:00:1c.4/0000:03:00.0 ==
modalias : pci:v000010DEd00001C92sv00001462sd00001245bc03sc02i00
vendor   : NVIDIA Corporation
driver   : nvidia-driver-418 - third-party free
driver   : nvidia-driver-415 - third-party free
driver   : nvidia-driver-430 - third-party free recommended
driver   : nvidia-driver-410 - third-party free
driver   : xserver-xorg-video-nouveau - distro free builtin
のように表示されるようになりました。なお、現在(2019年12月)に ubuntu-drivers devices を実行すると
== /sys/devices/pci0000:00/0000:00:1c.4/0000:03:00.0 ==
modalias : pci:v000010DEd00001C92sv00001462sd00001245bc03sc02i00
vendor   : NVIDIA Corporation
driver   : nvidia-driver-410 - third-party free
driver   : nvidia-driver-430 - third-party free
driver   : nvidia-driver-415 - third-party free
driver   : nvidia-driver-440 - third-party free recommended
driver   : nvidia-driver-435 - distro non-free
driver   : xserver-xorg-video-nouveau - distro free builtin
となったので、実行する時期によって内容は異なるようです。これらを見て、"recommended"なドライバをインストールしました。
(GTX1050, 2019年6月)
sudo apt install nvidia-driver-430
(GTX1060, 2019年12月)
sudo apt install nvidia-driver-435
いったん再起動し、動作確認は、nvidia-smiを実行します。
Thu Dec 12 03:20:08 2019       
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 435.21       Driver Version: 435.21       CUDA Version: 10.1     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  GeForce GTX 1060    Off  | 00000000:01:00.0  On |                  N/A |
| N/A   47C    P8     4W /  N/A |    254MiB /  6075MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
                                                                               
+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
|    0      1082      G   /usr/lib/xorg/Xorg                            18MiB |
|    0      1132      G   /usr/bin/gnome-shell                          48MiB |
|    0      1393      G   /usr/lib/xorg/Xorg                           114MiB |
|    0      1527      G   /usr/bin/gnome-shell                          69MiB |
+-----------------------------------------------------------------------------+
のように表示されれば正常に動作しています。

次に、dockerをインストールします。19.03以降でないとnvidia-docker化はできないので、本家から最新のものを入れます。ほぼ本家のページに従いました。
sudo apt update
sudo apt install apt-transport-https ca-certificates curl gnupg-agent software-properties-common
curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add -
sudo apt-key fingerprint 0EBFCD88
sudo add-apt-repository "deb [arch=amd64] https://download.docker.com/linux/ubuntu $(lsb_release -cs) stable"
sudo apt update
sudo apt install docker-ce docker-ce-cli containerd.io
動作確認は、
sudo docker run hello-world
として、
Unable to find image 'hello-world:latest' locally
latest: Pulling from library/hello-world
1b930d010525: Pull complete 
Digest: sha256:4fe721ccc2e8dc7362278a29dc660d833570ec2682f4e4194f4ee23e415e1064
Status: Downloaded newer image for hello-world:latest

Hello from Docker!
This message shows that your installation appears to be working correctly.

To generate this message, Docker took the following steps:
 1. The Docker client contacted the Docker daemon.
 2. The Docker daemon pulled the "hello-world" image from the Docker Hub.
    (amd64)
 3. The Docker daemon created a new container from that image which runs the
    executable that produces the output you are currently reading.
 4. The Docker daemon streamed that output to the Docker client, which sent it
    to your terminal.

To try something more ambitious, you can run an Ubuntu container with:
 $ docker run -it ubuntu bash

Share images, automate workflows, and more with a free Docker ID:
 https://hub.docker.com/

For more examples and ideas, visit:
 https://docs.docker.com/get-started/
のようなメッセージが表示されれば成功です。

次に、nvidia-docker化を行います。これも、本家のページの通りです。
distribution=$(. /etc/os-release;echo $ID$VERSION_ID)
curl -s -L https://nvidia.github.io/nvidia-docker/gpgkey | sudo apt-key add -
curl -s -L https://nvidia.github.io/nvidia-docker/$distribution/nvidia-docker.list | sudo tee /etc/apt/sources.list.d/nvidia-docker.list
sudo apt update
sudo apt install -y nvidia-container-toolkit
sudo systemctl restart docker
動作確認は、コンテナの中でnvidia-smiを実行してみましょう。
sudo docker run --gpus all --rm nvidia/cuda nvidia-smi
として、
Unable to find image 'nvidia/cuda:latest' locally
latest: Pulling from nvidia/cuda
7ddbc47eeb70: Pull complete 
c1bbdc448b72: Pull complete 
8c3b70e39044: Pull complete 
45d437916d57: Pull complete 
d8f1569ddae6: Pull complete 
85386706b020: Pull complete 
ee9b457b77d0: Pull complete 
be4f3343ecd3: Pull complete 
30b4effda4fd: Pull complete 
Digest: sha256:31e2a1ca7b0e1f678fb1dd0c985b4223273f7c0f3dbde60053b371e2a1aee2cd
Status: Downloaded newer image for nvidia/cuda:latest
Wed Dec 11 18:34:37 2019       
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 435.21       Driver Version: 435.21       CUDA Version: 10.1     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  GeForce GTX 1060    Off  | 00000000:01:00.0  On |                  N/A |
| N/A   38C    P8     4W /  N/A |    253MiB /  6075MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
                                                                               
+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
+-----------------------------------------------------------------------------+
のようにcuda入りイメージのダウンロード後、コンテナの中でnvidia-smiが実行できたら成功です。なお、このように"--gpus all"を付ければnvidia-dockerとして、付けなければただのdockerとして振る舞うようです。

ご参考になれば幸いです。

後はおまけ。dockerの使い方はまるで分かってなくて適当に検索しながら使ってるので、備忘録として。
なお、囲碁AIの一つであるKataGoを動かしたときは、KataGoはCUDA 10.1とCUDNN 7を必要とするので、
docker run -dit --gpus all --name katago nvidia/cuda:10.1-cudnn7-devel
のようにしてコンテナをバックグラウンドで立ち上げ、
docker exec -it katago bash
としてその中に入って作業を行いました。Dockerfileとかを使わない、ダメな使い方だと思いますが、これで十分役に立っています。

2019/11/21(木)kv-0.4.49

久しぶりに、kvライブラリを0.4.49にアップデートしました。

今回は、以前から溜めていた、
  • 辺に特異性を持つ2変数関数の二重積分
  • 一点に特異性を持つ2変数関数の二重積分
を精度保証付きで行う機能を追加しました。

言葉で書くと簡単そうですが苦労しています。数値積分のページの第5,6節とか、辺及び一点にベキ型特異性を持つ2変数関数の二重積分を見て下さい。

2019/04/10(水)kv-0.4.48

kvライブラリを0.4.48にアップデートしました。

今回は、区間演算の非常に基本的な部分の更新を含んでいます。

kvライブラリの区間演算は、端点に無限大を含む、 [0,\infty]のような半無限区間や、 [-\infty,\infty]のような無限区間を表現することが出来るように設計されています。これらは、区間が無限大という数?を含むという意味ではなく、 [0,\infty]ならば 0 \le x < \inftyのような、 [-\infty,\infty]なら -\infty < x < \inftyのような範囲を意味します。

このように端点に \inftyを許す区間演算を実装する場合、特に乗算で 0 \times \inftyに注意する必要があります。この計算はIEEE 754 Std.ではNaNになることになっていますが、区間演算の結果としてNaNはふさわしくありません。加算、減算、除算では適切に場合分けを行っていればNaNの危険はありませんが、乗算だけはきちんと考慮する必要があります。で、0.4.47以前では、片方が [0,0]でもう片方が無限大を含む区間だった場合の乗算で、何を考えていたのか、
\begin{eqnarray*} [0,0] \times [-\infty,\infty] &=& [-\infty, \infty] \\ [0,0] \times [c,\infty] &=& [-\infty, \infty] \\ [0,0] \times [-\infty,c] &=& [-\infty, \infty] \\ \end{eqnarray*}
のような計算をしていました。これらは、無限大を含む区間の意味を考えれば、当然 [0,0]になるべきものです。今回の0.4.48でこれを修正しました。福井大学の石井大輔先生のご指摘によります。大変ありがとうございました。

また、使ってる人がいるかどうか分からない、C++で気軽にリアルタイムグラフ表示 (matplotlib.hpp)の記事で書いたmatplotlib.hppですが、長方形を描画する関数rectにバグがあって正しい位置に描画されていなかったのを直しました。

2018/12/26(水)三部会連携 応用数理セミナー

応用数理学会の、三部会連携 応用数理セミナーで講演してきました。年末恒例のセミナーですが、9月に行った「精度保証付き数値計算の基礎」チュートリアルの続編という意味合いもあります。9月の第4章のチュートリアルに続いて、第7章のチュートリアルでした。

そこでつかったスライドを上げておきます。

40分では少し駆け足になってしまったのが反省点。また、Affine Arithmeticは常微分方程式の精度保証でかなり重要な役割を果たしているにもかかわらず、教科書のどこにも説明がないのが大きな問題点だなあと感じました。
OK キャンセル 確認 その他