読者です 読者をやめる 読者になる 読者になる

分散システム 7章「フォールトトレラント性」

部分的な障害の発生は単体システムでは起こらない分散システムの問題である

フォールトトレラント性の導入

基本概念

高信頼性とは:

  • 可用性 (availability)・・・ある瞬間に正常に稼働している確率
  • 信頼性 (reliability)・・・障害を起こすことなくジョブが走り続けられる確率
  • 安全性 (safety)
  • 保守性 (maintainability)

1時間に1ミリ秒ダウンするシステムは可用性は高いが信頼性は低い。1年に2週間メンテナンスするシステムは前の例より可用性は低いが信頼性は高い。

障害の種類:

  • 過渡障害 (transient fault)・・・1度だけ起こるが消滅する
  • 間欠障害 (intermittent fault)・・・一時的に障害が現れることが繰り返す
  • 永久障害 (permanent fault)

障害モデル

  • クラッシュ障害
  • 欠落障害(受信欠落・送信欠落)
  • タイミング障害・・・指定時間内に応答できない
  • 応答障害(値障害、状態遷移障害)
  • 任意障害(ビザンチン障害)・・・最も深刻な障害

冗長性による障害の隠蔽

冗長性の種類:

  • 情報的冗長性・・・誤り訂正符号など
  • 時間的冗長性・・・リトライ
  • 物理的冗長性・・・余分な装置の付加

三重モジュール (TMR; Triple Modular Redundacy) による冗長性・・・電子回路を 3 重化しゲートの直後に毎回多数決を取る。

プロセスのレジリエンス

レジリエンス=いくつかのプロセスが故障した場合に、システムの残りの部分に大きなダメージを与えないようにするための技術

設計問題

プロセスグループ・・・同じ役割を担う複数のプロセスを作っておく

  • 平坦なグループ・・・全プロセスの役割が同じ
  • 階層的なグループ・・・調整プロセスと実行プロセス

障害隠蔽とレプリケーション

Kフォールトトレラント性・・・K個のコンポーネントが故障しても動作する

  • 停止するだけなら、K+1個あれば十分
  • ビザンチン障害を保つ場合、最低でも2K+1個必要

障害システムにおける同意

  • 2 つの軍隊問題・・・5000の軍隊を持つ赤軍が谷に野営。谷を見下ろす位置に3000+3000で2つの青軍が野営。赤軍に勝てるか?→障害のないプロセスしか考えないとしても信頼性のない通信を仮定すると、2つのプロセス間で合意形成はできない。
  • ビザンチン将軍問題・・・通信は完全だがプロセスは完全でない場合。mプロセスが裏切りに対して2m+1の正しく動作するプロセスが存在すると正しく動作できるアルゴリズム

TODO:6章(レプリケーション)を読む

高信頼クライアント・サーバ間通信

  • TCPのような高信頼転送プロトコルを用いる
  • クラッシュ時には再接続するしかない

TODO: 障害がある場合の遠隔手続き呼び出し

高信頼グループ間通信

  • 高信頼マルチキャストの基本手法・・・いくつかの仮定を踏まえた簡単なシステム:受信したらACKを送り、喪失に気づいたら再要求をする
  • アトミックマルチキャスト・・・全プロセスに送信されるか、全く送信されないかのどちらか
  • 仮想同期 (virtually synchronous)・・・アトミックマルチキャストであって、メッセージが送信されないのは送信者がクラッシュした場合のみ

TODO: 高信頼マルチキャストにおけるスケーラビリティ

分散コミット

分散コミット・・・あるオペレーションはグループ内の全てのメンバによって行われるか全く行われないかのいずれか(アトミックマルチキャストは分散コミットの1例)

1相コミット (one-phase commit) ・・・コーディネーターが実行するかどうかを通知する。参加者の1つが行うことができなくなった場合に、コーディネータに伝えることができなくなって困る。

2相コミット

  1. コーディネータ:VOTEをマルチキャスト
  2. 参加者:可否をコーディネータに報告
  3. コーディネータ:全員が可能ならCOMMITをマルチキャスト
  4. 参加者:COMMITを受信したら実行

いくつかのケースでブロッキングしてしまう問題がある。解決策の1つは3相コミットである。

回復

  • 後向きエラー回復・・・エラー状態から以前の正しい状態(チェックポイント)へシステムを巻き戻す。
  • 前向きエラー回復・・・実行を継続できる新しい状態に戦意させる。発生する可能性のあるエラーを事前に知っておく必要がある。

チェックポイントづくり

  • 回復ライン (recovery line) ・・・各プロセスのチェックポイントの組み合わせであって一貫性があるもの
  • 独立チェックポイントづくり・・独立にローカルな状態を記録し続ける
  • 協調チェックポイントづくり

BLAS, LINPACK, LAPACK

BLAS とは

ベクトルと行列に関する積や和などの基本的な操作を提供するライブラリのことっぽい。機能はレベルに分類されるらしい。

  • Level 1:ベクトル演算
  • Level 2:行列ベクトル演算
  • Level 3:行列同士の演算

有名な操作として GEMM (ジェム)がある。GEMM とは General Matrix Multiplication のことで、C = αAB + βC を計算する。

精度を頭につけて識別する。例えば SGEMM は 32bit float、DGEMM は 64bit float。

LINPACK, LAPACK とは

線形方程式や固有値問題などを解くための線形代数のライブラリ。BLAS を利用している。LAPACK は LINPACK の後継。両方 Fortran で書かれている。

BLAS と同様の命名規則が採用されているようだ。 DGESV は double (D) の一般行列 (GE) の方程式の求解 (SV) である。

BLAS の実装

ありがたい情報を貰いました……感謝!!

MKL は BLAS のみならず LAPACK や FFTW と互換性のある関数群も含んでいるらしいです。

CUDA の BLAS には NVIDIA 公式の cuBLAS がある。CUDA の LAPACK には CULA と MAGMA というものがあるようだ(どちらも公式ではなさそう)。

BLAS, LAPACK の間接的な利用

C++ を Python から呼ぶ方法まとめ

空のプロジェクトを PyPI に登録するまで

プロジェクトの名前を決めたらまずは PyPI で名前を予約しましょう。

PyPI にユーザ登録する

TestPyPI というお試しサイトにも登録しよう。

~/.pypirc を作る

パスワードを書かないでおくと実行時に聞いてもらえる。

[distutils]
index-servers =
  pypi
  pypitest

[pypi]
repository=https://pypi.python.org/pypi
username=<ユーザ名>

[pypitest]
repository=https://testpypi.python.org/pypi
username=<ユーザ名>

setup.py を作る

空のディレクトリに以下の内容で setup.py を置く。

from setuptools import find_packages
from setuptools import setup

setup(
    name='<パッケージ名>',
    version='0.0.1',
    description='<せつめい>',
    author='<名前>',
    author_email='<メールアドレス>',
    packages=find_packages(),
)

アップロード

$ python setup.py sdist upload -r pypitest  # お試し
$ python setup.py sdist upload  # ガチ

apt パッケージ探偵をするときに使うコマンド

会社のバイアリアン(?)の人の問題解決が僕の10倍ぐらい速い。僕も少しずつでもコマンドを覚えていきたい。

apt-cache show cuda-drivers
apt-cache depends cuda-drivers

dpkg -l | grep nvidia
dpkg -l | grep cuda

apt-get changelog cuda-8-0
apt-get download cuda-8-0

ar xv cuda-repo-ubuntu1404_8.0.44-1_amd64.deb

CNN による画像分類で使われる前処理・テスト時処理まとめ

機械学習

とりあえず ImageNet 系の論文で、目に入ったものから順々にまとめていきます。情報・ツッコミ歓迎。

前処理・Data Augmentation

Mean Subtraction

入力画像から平均を引く。[103.939, 116.779, 123.68] を各ピクセルから引く。VGG はこれ。

Per-pixel Mean Subtraction

入力画像から平均を引く。ピクセル・チャンネルごとに計算された平均を引く。即ち、224x224x3 個の値について個別に平均を計算し用いる。AlexNet 論文から使われており、ResNet もこれ

Random Crop

256x256 ピクセルに画像をリサイズし、そこから 224x224 のパッチをランダムに取り出す。AlexNet 論文で使われていた。ちなみに Chainer の ImageNet サンプルはこれと Horizontal Flip をやっている(これしかやっていないので相応の精度しか出ない)。

Horizontal Flip

画像をランダムにフリップする。ImageNet では縦方向はなく水平方向の flip のみが使われるようであり、AlexNet 論文以降必ず使われているようだ。

Scale Augmentation

まず画像をリサイズする。[256, 480] からランダムに短辺の長さを選ぶ。次に、224x224 のパッチをそこからランダムサンプルする。

VGG 論文から使われており、ResNet 本家論文でも使われる。

Aspect Ratio Augmentation

上の Scale Augmentation に加え画像のアスペクト比を [3/4, 4/3] で変換する・・・ぽい?(論文の記述が短くわかりにくい)

GoogLeNet の論文で使われている。FAIR の ResNet 再現記事でも使われており、本家から 1.2% の精度向上に寄与したらしい。

Color Augmentation

AlexNet 論文で行われた方法は以下である。各ピクセルの RGB を 3 次元のベクトルの集合だと考え PCA をかける。ガウス分布でノイズを生成し、固有ベクトル方向にノイズを加える。乱数は各ピクセルではなくパッチ全体に対して共通。論文によると AlexNet の精度への寄与は 1% 程度。ResNet 本家論文でも使われている。PCA した結果はここにあったり。

"Some Improvements on Deep Convolutional Neural Network Based Image Classification" 論文で行われた方法は以下である。contrast, brightness, color を、[0.5, 1.5] の間でランダムに変更する。変更の順番もランダムに選択する。(ご丁寧に、Python image library (PIL) を使ったと書いてある。)その後で、AlexNet 論文と同様の操作を行う。FAIR の ResNet 再現記事ではこれを利用したと書いてあったが、精度への寄与はとても小さかったらしい。

テスト時

Ensemble

複数のモデルを独立に学習し、それらの予測を平均する。

GoogLeNet 論文では、ネットワークは同じだが入力の処理法を変えた 7 つのモデルをアンサンブルしているらしい。GoogLeNet の論文は全体的に詳細が濁されているのでよくわからない。single crop だと top-5 error が 2% 弱程度向上。

ResNet 本家論文では、34B, 34C, 50, 101, 152×2 の 6 モデルをアンサンブルしている。fully-convolutional-form で top-5 error に 1% 弱程度向上。

10-crop Testing

テスト画像 1 つから data augmentation と類似した手順で 10 個のパッチを切り出し、それぞれに対する予測を平均して答える。

AlexNet 論文では、(4 スミ+中央)×(反転の有無)で 10 個のパッチを切り出している。GoogLeNet は 144 パッチも試してる。

GoogLeNet 論文では、crop 数の精度への影響が載っている。top-5 error で、10 crops で約 1% 弱向上、144 crops で 2% 強向上(下表は GoogLeNet 論文より引用)。

f:id:iwiwi:20161231213228p:plain

Fully-convolutional-form Testing

まず、全結合層たちを畳み込み層とみなす。例えば、直前の画像サイズが s×s であれば、最初の全結合層は s×s → 1×1 の畳み込み層であるとみなす。すると、ネットワークは fully convolutional (全レイヤーが畳み込み)となる。fully convolutional なネットワークの利点は、入力の画像サイズが変化しても適用することができることである(ただし、出力サイズも変化する)。

テスト画像をリサイズする。この時の画像サイズは、学習で使っている画像サイズと一致しているとは限らないし、正方形とも限らない。例えば、短辺を 480 にする。ネットワークをこの画像に適用する。出力を average pooling してそれを予測とする。

さらに、テスト画像のサイズを複数試し、その結果の平均を用いる。例えば、ResNet 本家論文では短辺を 224, 256, 384, 480, 640 になるようにリサイズしている。また、horizontal flip も試して平均を取る。

VGG から使われている。ResNet 本家論文を見るところ、10-crop Testing と比べて、大体 2% 程度精度に寄与している。

Chainer で全結合層を畳み込み層にするコードの例を mitmul さんから貰ったので貼っておきます。

def linear2conv(model, name, feature_size=1):
    """Convert Linear layer to 1x1 Convolution Layer
    args:
        model (chainer.Chain): The input model
        name (str): Name of a Linear link that will be converted to 1x1 conv
            ex. '/predictor/trunk/fc6'
        feature_size (int): The feature map size of convolution layer
    """
    target = model
    lnames = [n for n in name.split('/') if len(n) > 0]
    for l in lnames[:-1]:
        target = target.__dict__[l]
    t = target.__dict__[lnames[-1]]
    assert ('Linear' in str(t.__class__))
    out_dim, in_dim = t.W.data.shape
    in_dim = in_dim // (feature_size ** 2)
    conv = L.Convolution2D(in_dim, out_dim, feature_size)
    W = t.W.data.reshape((out_dim, in_dim, feature_size, feature_size))
    conv.W.data, conv.b.data = W, t.b.data
    target.__dict__[lnames[-1]] = conv
    return model

参考文献

謝辞

  • 宮戸さん (PFN)
  • mitmul さん

スヌープモードを設定して QPI を爆速で超える

スヌープモードの影響

マルチ CPU のマシンでメモリ帯域を測ると、別ソケット側のメモリとの帯域が死ぬほど遅いという現象がある。これは、CPU のスヌープモードがデフォルトの「Early Snoop」になっているからである。BIOS からこれを「Home Snoop」に変更することによって、帯域は大きく向上する。

software.intel.com

この記事によると、Early Snoop では 6GB/s 程度であったのが、Home Snoop では 25GB/s 程度になっている。

ただし、Home Snoop にすると、代償として同一 NUMA ノード内でのレイテンシが 10% 程度悪くなってしまう。

スヌープとは

キャッシュメモリ - Wikipedia

キャッシュコヒーレンシを保つ方法の 1 つがスヌープ方式(スヌープキャッシュ)である。各キャッシュメモリが、自身とよそのキャッシュラインの状況を管理し、メッセージにより情報交換を行う方式である。この情報交換の方式に、MESI プロトコル等が含まれる。

スヌープ方式以外のアプローチは、ディレクトリ方式、共有キャッシュなどである。

スヌープモードとは

software.intel.com

技術的詳細は分からないが、スヌープモードを変更すると、このスヌープのアルゴリズムが切り替わると思われる。ちなみに、上述の Early Snoop, Home Snoop の他に Cluster on Die (COD) モードというのがある。これは、他の NUMA ノードへのアクセスがかなり少ない仮定を置いたモードのようで、仮想マシンを扱う場合などを想定しているようだ。

数列の和を計算するアルゴリズム

数列の和の計算にアルゴリズムなんて考える余地はあるのか?と思ったが、誤差についても考える場合、単純な方法以外にも複数のアルゴリズムが存在し使われているということを教えてもらった。

Kahan summation はより高い精度を達成できるが、pairwise summation のほうが高速である。NumPy の sum では pairwise summation algorithm が使われているようだ。

ちなみに、分散を計算する際には専用のアルゴリズムもある。

Cython の落とし穴

Python

ポインタを使ってあれこれしたいときの落とし穴を会社で教えてもらった。

numpy の ndarray.data の挙動が型を指定するかによって変わる

tutorials NumpyPointerToC · cython/cython Wiki · GitHub

ここに書かれた方法2でポインタを取り出したい時、引数の型の指定を取り除くと、挙動が変わってしまう。コンパイルエラーも起きず、実行もできるが、ndarray の中が書き換わらないというかなり不思議な状態になる。

これは Cython (cimport) 側の numpy と Python (import) 側の numpy の両方で data が定義されており、Cython 側の定義が優先され上書きされるからである。

void* に Python の int を代入しようとすると意図しない挙動になる

a が Python object の int でありメモリアドレスを表現しているとする(例えば、cupy の ndarray.data.ptr)。から void* に直接キャストしようとすると、Python object のポインタをとってきてしまうようだ。正解は、size_t に一度キャストして、void* にキャストするということである。つまり、以下の2つのコードの挙動は異なる。

<void*>a
<void*><size_t>a

Regularized Greedy Forest (RGF) のロス関数をカスタマイズする

機械学習

Regularized greedy forest (RGF) in C++

RGF の公式実装のロス関数をカスタマイズするには、C++ のコードを直接書き換えることになる。とはいえそんなに難しくない。以下の方法がお手軽。

  • src/comm/AzLoss.cpp を開く
  • AzLoss::getLosses 関数に loss_type == AzLoss_Xtemp という場合分けを追加
  • o._loss1 にロス関数の 1 階微分を代入する
  • o.loss2 にロス関数の 2 階微分を代入する
  • 使用時には loss に 'Xtemp' を指定する

getLoss の方には追加せずとも動いた。getLoss と getLosses とか、_loss1 と loss2 とか、命名が滅茶苦茶すぎてヤバい……。

malloc にわざと失敗させる

#define _GNU_SOURCE

#include <dlfcn.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef void* (*malloc_t)(size_t);

static malloc_t libc_malloc = NULL;
static unsigned long malloc_max_called = 1000 * 1000;

void initialize() {
  libc_malloc = (malloc_t)dlsym(RTLD_NEXT, "malloc");
  if (libc_malloc == NULL) {
    perror("dlsym");
    exit(1);
  }

  char const* const s = getenv("MALLOC_MAX_CALLED");
  if (s == NULL) return;

  sscanf(s, "%lu", &malloc_max_called);
}

unsigned long count = 0;

void* malloc(size_t n) {
  if (libc_malloc == NULL) initialize();
  if (count >= malloc_max_called) return NULL;

  count++;
  return libc_malloc(n);
}
% gcc -Wall -g -fPIC -shared failing_malloc.c -o failing_malloc.so -ldl
% MALLOC_MAX_CALLED=1000 LD_PRELOAD=./failing_malloc.so ./a.out

機械学習アルゴリズムの直感を養えるデモ・記事

発見次第更新予定

デモ

Neural Network

Gradient Boosting

t-SNE

リンク集

記事

NIPS のヤバいプロモーションビデオ

機械学習

www.youtube.com

音を出して観るべき。

Python の処理系

Python


  • Pysco
  • Pyjion
  • Nuitka
  • Skulpt