Wikipediaのdumpからinfoboxの内容や文章を取ってくる方法

こんにちは!

Link-Uの町屋敷です。

今回はWikipediaの本文を収集する方法と特定のInfoboxを収集する方法を書いていきます。

Wikipediaから文章を取ってくる

Wikipediaの文章を取ってくる方法は主に以下の2つです。

  1. MediaWikiのAPIを使う
  2. 同じくMediaWikiが提供しているXML形式のダンプファイルを使う。

APIを使う方法のほうが簡単ですが、Wikipediaはクロールが禁止されているので、データセットの作成には方法2を使わざるを得ません。チャットボットとかなら1で良いでしょう。

Wikipedia Extractorを使う

今回はWikipediaExtracctorを使って本文を取得します。

まず、最新のMediaWikiが提供しているXML形式のダンプファイルの中から、

jawiki-latest-pages-articles.xml.bz2

をダウンロード

次に適当なフォルダに移動して

git clone git@github.com:attardi/wikiextractor.git
cd wikiextractor
python python setup.py install

でwikiextractorをインストール出来ます。

自分はminicondaの仮想環境に入ってからやりました。

早速本文を抽出してみましょう。

WikiExtractor.py --json --keep_tables -s --lists -o ../whole_data/ ~/Downloads/jawiki-latest-pages-articles.xml

コマンド説明
--json        : 出力をjsonにする
--keep_tables : 文章内の表を出力するようにする
-s            : セクション情報も出力するようにする
--list        : 文章内のリストを出力するようにする
-o            : 出力ファルダ名

最後のパスがさっきダウンロードしたxmlの入力ファイルです。

このフォイルはダウンロード時bz2という謎の形式で圧縮されています。

wikiextractorで使う分には圧縮されたままで良いのですが、後で中身を見る必要が出てくるので先に解凍しちゃいましょう。linuxなら

bzip2 -d jawiki-latest-pages-articles.xml.bz2 

で解凍できます。

Windowsの場合はLhaplusを使うと良いでしょう。(なぜか7zipだと失敗した)

少し話がそれましたが、先程のスクリプトを実行するとわらわらとファイルが生成されて、

中を見ると文章が取得できているのでめでたしめでたし。

と、思いきやよく見るInfoboxが取得できていない。

Infoboxとはなんぞやと言う事ですが、要はWikipedia見てると右側にわりといる情報が書かれた表です。

これ機械学習だと正解ラベルになるようなかなり重要なこと書かれてるのになんで無いの?

最初–keep_tablesのオプション使っていなくて絶対コレじゃんと思ってやってみたが増えたのは文章の途中に出てくる表だけだった。残念。

XMLから特定のInfoboxの情報を取得する

Infoboxの情報がどうしてもほしいのでネットで色々検索したが、出てくるのはAPIを使ったものばかり。

WikipediaのXMLをJSONに変換するツールなども試してみたがうまく動かず、

そんなこんなで1日くらいあがいても良いライブラリは見つからなかった。

こうなったら自分で作るしか無い

というわけで、XMLから特定のInfoboxの情報を取得してjsonで保存するスクリプトをPython3で作成した。

通常の文章はさっきほど抽出したものがあるので、必要なInfoboxが存在する項目だけタイトルとタイトルIDとセットで保存して、使うときに結合させるようにする。

どうせやるなら一緒に本文も保存したら良いじゃないかってなりそうだが、xml本文中にはいらないものが大量に含まれていて、消す作業が面倒だったので保留。

幸いあがいてる途中に参考になるサイトを見つけたので、大体はこれに沿ってやります。

プログラム全文はページの一番下。特に特別なパッケージは必要ない

大事なところだけ解説すると、

PythonでXMLからタグを取ってくる方法は、普通は

import xml.etree.ElementTree as ET
tree = ET.parse('country_data.xml')
root = tree.getroot()

こんな感じだが、今回はxmlファイルが馬鹿でかいのでこれを行うとメモリが死ぬ可能性がある。

なので、イテレータを用いて処理する。

for event, elem in etree.iterparse(pathWikiXML, events=('start', 'end')): 

処理は上のタグから一つずつ進行していく、例えば

<a>
    <b>0</b>
    <c>
      <d>70334050</d>
    </c>
</a>

このようなタグが来た時は、elem.tagにはa->b->b->c->d->d->c->aの順番でデータが入り、

開きタグなのか閉じタグなのかは,eventを見て判断する。

elem.textにそのタグに囲まれた部分の文章がひるようだ、

ここで、実際のxmlがどんな形式ななっているか確認しましょう。

less ~/Downloads/jawiki-latest-pages-articles.xml

巨大なファイルなので通常のテキストエディタでは開きません。

どうやら<page>~</page>でwikipediaの各ページが表現されていて、

<title>にタイトル

<id>にページ番号

<text>にメインの文章が書かれているようだ。

ただ、Infoboxは少々面倒で、特定のタグに囲われているわけでもなく、<text></text>の中に

{{東京都の特別区
|画像 = [[File:Sensoji 2012.JPG|200px]]
|画像の説明 = [[浅草寺]]境内
|区旗 = [[File:Flag of Taito, Tokyo.svg|100px]]
|区旗の説明 = 台東[[市町村旗|区旗]]&lt;div style=&quot;font-size:smaller&quot;&gt;[[1965年]][[6月4日]]制定
|区章 = [[File:東京都台東区区章.svg|75px]]
|区章の説明 = 台東[[市町村章|区章]]&lt;div style=&quot;font-size:smaller&quot;&gt;[[1951年]][[4月18日]]制定&lt;ref&gt;「東京都台東区紋章制定について」昭和26年4月18日台東区告示第47号&lt;/ref&gt;
|自治体名 = 台東区
|コード = 13106-7
|隣接自治体 = [[千代田区]]、[[中央区 (東京都)|中央区]]、[[文京区]]、[[墨田区]]、[[荒川区]]
|木 = [[サクラ]]
|花 = [[アサガオ]]
|郵便番号 = 110-8615
|所在地 = 台東区[[東上野]]四丁目5番6号&lt;br /&gt;&lt;small&gt;{{ウィキ座標度分秒|35|42|45.4|N|139|46|47.9|E|region:JP-13_type:adm3rd|display=inline,title}}&lt;/small&gt;&lt;br /&gt;[[File:Taito Ward Office.JPG|250px|台東区役所庁舎(東上野四丁目)]]
|外部リンク = [http://www.city.taito.lg.jp/ 台東区]
|位置画像 = {{基礎自治体位置図|13|106}}
|特記事項 =}}

突然現れるだけで文章からの抽出が必要。

どうやら<text>中で{{}}で表されているものは複数あるらしく、単純に{{}}に囲われた部分を抽出してもうまく行かない。

そこでInfoboxの名前を使う。名前は{{のすぐ後に書いているやつで、lessでそのInfoboxが使われている項目を検索して直接確認するか、Wikipediaの基本情報テンプレートに書いてあるTemplate:Infobox ~ の項目を確認する。

                    elem.text = re.sub('{{[F|f]lagicon.*?}}', '', elem.text)
                    infobox = re.findall('{{{0}n.*?|.*?}}'.format(INFOBOX_SEARCH_WORD), elem.text, re.MULTILINE | re.DOTALL)

ここがその抽出部分で、INFOBOX_SEARCH_WORDにInfoboxの名前を入れるとその名前に対応するInfoboxを抽出できる。ただし、{{}}が入れ子になっているとバグるので、re.subで事前にいらないものを消している。

reの代わりにregexを使うと入れ子でも処理できるようだが、今回選んだInfoboxではこれで大丈夫だったので保留。

試しに上のWikipedia画面のキャプチャで囲んでいた漫画のInfobox(Infobox名 animanga/Manga)で試してみた結果がこちら。

ちゃんと取得できていることが確認できた。

参考サイト

https://www.heatonresearch.com/2017/03/03/python-basic-wikipedia-parsing.html

プログラム全文

import xml.etree.ElementTree as etree
import time
import os
import json
import re
import collections as cl

PATH_WIKI_XML = '/home/machiyahiki/Downloads/'
FILENAME_WIKI = 'jawiki-latest-pages-articles.xml'
JSON_SAVE_DIR = '.'
INFOBOX_SEARCH_WORD = 'Infobox animanga/Manga'

ENCODING = "utf-8"

def strip_tag_name(t):
    idx = t.rfind("}")
    if idx != -1:
        t = t[idx + 1:]
    return t

pathWikiXML = os.path.join(PATH_WIKI_XML, FILENAME_WIKI)

totalCount = 0
articleCount = 0
redirectCount = 0
templateCount = 0
title = None
start_time = time.time()
dict_array = []

with open('{0}//wiki_infobox_{1}.json'.format(JSON_SAVE_DIR, re.sub('[ |//]', '_',  INFOBOX_SEARCH_WORD)),'w', encoding='utf_8') as jf:
    for event, elem in etree.iterparse(pathWikiXML, events=('start', 'end')):
        tname = strip_tag_name(elem.tag)
    
        if event == 'start':
            if tname == 'page':
                inrevision = False
                findinfobox = False
                data_dict = cl.OrderedDict()
            elif tname == 'revision':
                # Do not pick up on revision id's
                inrevision = True
            if tname == 'title':
                data_dict['title'] = elem.text
            elif tname == 'id' and not inrevision:
                data_dict['id'] = elem.text
        else:
            if tname == 'text':
                if elem.text:
                    elem.text = re.sub('{{[U|u]nicode.*?}}', '', elem.text)
                    elem.text = re.sub('{{[F|f]lagicon.*?}}', '', elem.text)
                    infobox = re.findall('{{{0}n.*?|.*?}}'.format(INFOBOX_SEARCH_WORD), elem.text, re.MULTILINE | re.DOTALL)
                    if infobox:
                        findinfobox = True
                        data_dict['infobox'] = infobox
            if tname == 'page':
                if findinfobox:
                    if data_dict['title']: #タイトル名に{{Unicode}}があるとnullが入る、後で修可
                        if 'プロジェクト:' in data_dict['title']: #プロジェクト:から始まる項目は無視
                            continue
                        if 'Template:Infobox' in data_dict['title']: #Template:Infoboxから始まる項目も無視
                            continue
                    dict_array.append(data_dict)
                    
                
        if len(dict_array) > 1 and (len(dict_array) % 10000) == 0:
            print("{:,}".format(len(dict_array)))

        
        elem.clear()
    json.dump(dict_array, jf, ensure_ascii=False)
    
    
elapsed_time = time.time() - start_time

print("Total pages: {:,}".format(len(dict_array)))
print("Elapsed Time: {:,}".format(elapsed_time))   
                
    

GPUを使って無線LANを(略) 番外編 GPUなしでCUDAは動かせるのか?

紅葉への切り替わり中です。秋って感じですね。

でも町を歩いていると、8月末くらいには紅葉のポスターが貼られだして、ハロウィン一色になったなぁ、と思ったら、今はもうクリスマス一色です。町から紅葉の絵はなくなり、雪の結晶やクリスマスツリーの絵ばかり。気が早えぇなぁ、人間。

わたしは最近こういう「イメージ」も「拡張現実」の一種なんじゃ無いかと感じています。ARゴーグルだけが「拡張現実」では、ないんじゃない?

みなさんはどう思います?

…と聞いてみるにもコメント欄ないんだったわ、このブログ。トラックバックもない。…時代は変わってしまったなぁ。

GPUサーバがない!

というわけで、前回山の上で瞑想して考えた「ぼくの考えた最強のベンチマーク・ルール」にしたがってガンガンPyritを書き換えていきたいところ…なのですが、なんと今回はオトナの事情により、GPUサーバは使えないらしいのです。かなしい。

しかし、案ずることなかれ。

こんな事もあろうかと、もう2枚ほどGeForce 1080を用意しておきました。

これをどこのご家庭にもある、PCI-Express用の電源ポートがなぜか10個あってPCI-Express x16のスロットがなぜか4つあるデスクトップパソコンに刺してPyritの改造をしていきましょう。

がっちゃん(GPUを突き刺す音)

カチッ(電源を押す音)

ブワー(電源がつきファンが回る音)

ピカピカピカ(1680万色に光るゲーミングマザーボードのLED)

…(しかしモノリスのように真っ黒なまま沈黙するモニタ)

…(その前でなす術もなく立ち尽して一緒に沈黙する筆者)

…(なす術もなく立ち尽くす筆者)

……(立ち尽くす筆者)

…………

……………はぁ〜〜〜〜〜〜〜

なんで画面が出ないんだよ〜〜〜〜〜〜〜〜

グラフィック・ボード」じゃなかったのかよ〜〜〜〜〜〜〜

…嘆いていてもしょうがないので、GPUなしでなんとかする方法を考えましょう。

遅くてよいので、CPUだけでCUDAのコードを動かせないものか…。

原理的には可能なはずですよね。CUDAはただ計算が早くなったり(ならなかったり)するだけの技術ですから。同じPCIeの拡張カードでも、真の乱数発生ボードと違って、原理的にはエミュレーションできる事は明らかです。原理的には、だけどね。

わたくし結構macでノマドもするので、できればLinuxだけじゃなくてmacでも動いて欲しいなぁ(欲を出しておく)。

あーそうそう、画面が出ない理由ですが、Radeonと一緒に刺すとダメみたいです。グラボのバグなのか、Linuxのバグなのか、その辺は、よくわからない。

代案を調べる

代案 その1:gpuocelot

gpuocelot公式サイトより引用

gpuocelotは、CUDAの実行ファイルであるPTXをnVidiaのGPUだけでなく、AMDのGPUやCPUで直接実行したり、エミュレーションしたり、ネットワーク経由で他のマシンのGPU(やCPU)で実行したりできるようにするぜ!というそのものズバリわたしが求めていたソフトウェアです。

が、公式サイトいわく「The GPU Ocelot project is no longer actively maintained.」ということで開発終了。まぁ大学製ソフトなので、資金が尽きたのか論文書き尽くしたのか、まぁ、そんな所でしょうか。しかも最後の論文が2014年なのであまり期待はできなさそうです。

あと個人的なプログラマ、あるいは大学院生しての直感が告げているのですが、こんな野心的なソフト、本当に安定して動くのかな…論文書くための機能が一応動いてるだけじゃないかな…という疑念が正直あります。

はい次。

代案 その2: MCUDA

The MCUDA translation framework is a linux-based tool designed to effectively compile the CUDA programming model to a CPU architecture.

IMPACT: MCUDA Toolset

こちらも大学製。何か書くにも、一切ドキュメントがない。

はい次。

代案 その3:CUDA Waste

GPUocelotはLinux専用らしく(gpuocelotのページにはそんな事書いてなかったけどな!)、そのためにWindows用に同じようなソフトウェアを開発したのがこちらだそうです。こちらもだいぶ前から更新がないので実用は難しそう。あとわたしWindows持ってない。

はい次。

代案その4: CU2CL

CUDAのソースコードをOpenCLのソースコードに変換するというソフトウェア。今までのソフトウェアに比べると大分「現実的」な落とし所なような気はします。

が、実際にこれを使おうとすると、CUDAを実行していた部分をOpenCLを実行するためのコードにモリモリ書き換えないといけませんし、そもそもPyritにはOpenCLのコードは最初から入っています。

悪くは無いんだけど、今回の場合は色々な意味で本末転倒。

はい次。

代案その5: NVEmulate

これはなんとNVIDIA公式。古いGPUのマシンでも、新しいGPUを要求するソフトウェアを動かせるようにするためのソフトウェアだそうです。しかし2014年から更新がなく、ついでに言えばWindows専用。よしんばWindowsを持っていたとして、CUDAが動くかどうかは怪しいです。ゲーム開発者のデバッグ用っぽい。

「非常に低速」であることには違いないが,例えば,GeForce FXシリーズのマシンでGeForce 6800のデモであるNaluやTimburyが動いてしまうという素晴らしいツールだ(普通の人用には,これ以外の用途を思いつかないのが残念だが)。
手持ちのGeForce FX 5900搭載マシンでは,Naluが0.1fps程度で動いている。

4Gamer.net ― 君のマシンでNaluが動く! GPUエミュレータNVemulate公開

はい次。

代案その6: nvcc -deviceemu

nvcc –deviceemu <filename>.cu

  • デバイスエミュレーションモードでビルド
  • デバッグシンボルなし、CPUですべてのコードを実行

NVIDIA – CUDA実践エクササイズ

こちらも公式。CUDAコンパイラであるnvccが、CUDAソースコードのうち、GPUで走るはずの部分も全部CPUで走るようにコンパイルしてくれるんだそうな。

これはかなり理想的かつ現実的なアプローチに思えます。PyritのCUDAモジュールをコンパイルする時にこのオプションをつけておくだけでいいのでラクチンですし、mac用のnvccもあるのでノマドワーカーにも優しい。そしてPTXを動的に変換するような大道芸はしない、安定したアプローチ。

しかし

 % cd /Developer/NVIDIA/CUDA-9.2/bin
 % ./nvcc --help | grep deviceemu
 %

とっくの昔にそんなものは無くなっていたのであった。

CUDA Emulation Modeというのもあった(GPUの代わりにCPUのエミュレータが出てくる)というのも昔はあったようなのですが、これも今はもうなさそう。

NVIDIAからの「GPU買ってね!」という熱いメッセージだと思っていいのかな…。でもそれ以前に動かないんだけど。

gpuocelotを試す

現実的に使えそうなものはgpuocelotぐらいなので、これちょっと試してみましょう。Instlationページによると、WindowsはExperimental(もう二度とExperimentalが外れることはなさそうだけど)で、macは最初から言及すらないので、ノマドは諦めてLinuxでやりましょう。

Ubuntu 18.04でやる事にします。

ビルド・インストラクションに沿って(かつGCC4.8では動かないなどの諸々の注意書きを見なかった事にして)やってみると:

ocelot/ir/implementation/Module.cpp:712:46: error: enum constant in boolean context [-Werror=int-in-bool-context]
     if (prototypeState == PS_ReturnParams || PS_Params) {
                                              ^~~~~~~~~
cc1plus: all warnings being treated as errors
scons: *** [.release_build/ocelot/ir/implementation/Module.os] Error 1
Build failed...
Build failed

「PS_Paramsはenumなのでboolの値としては使えないんだけど…!」という、もっともなエラー。しかしどう直せばいいのか。||の前を見る限り、”prototypeState == “を忘れたんですかね?

…これ…コンパイルエラーじゃなかったら、常に”true”になるif文としてコンパイルされてたんじゃないかな…。それでいいのかな…この世はコワイネ。

とりあえず追加してビルド再開。

In file included from ./ocelot/parser/interface/PTXLexer.h:11:0,
                 from ./ocelot/parser/interface/PTXParser.h:16,
                 from ocelot/ir/implementation/Module.cpp:10:
.release_build/ptxgrammar.hpp:354:22: error: 'PTXLexer' is not a member of 'parser'
 int yyparse (parser::PTXLexer& lexer, parser::PTXParser::State& state);
                      ^~~~~~~~
...(略)...
.release_build/ptxgrammar.hpp:354:47: error: 'parser::PTXParser' has not been declared
 int yyparse (parser::PTXLexer& lexer, parser::PTXParser::State& state);
                                               ^~~~~~~~~
...(略)...

scons: *** [.release_build/ocelot/ir/implementation/Module.os] Error 1
Build failed...
Build failed

parser::PTXLexerや、parser::PTXParser::Stateを宣言していないのに、yyparse関数のパラメータとして使ってるぞ!という、これまたもっともなコンパイルエラー。

ptxgrammar.hppはyaccから生成されるファイルで、NVIDIAのGPUの命令セット、PTXのパーサーのようです。で、このパーサーがparse::PTXParser::Stateを利用すると。

で、PTXParserを見ると次のようになっていて、プログラムの他の部分から使うための外面の実装のようです。そのため、ptxgrammar.hppにガッツリ依存しております。

namespace parser
{
	/*! brief An implementation of the Parser interface for PTX */
	class PTXParser : public Parser
	{
		public:
			class State
			{
				public:
					class OperandWrapper
...(略)...

必然的に、循環参照が発生しています。

PTXParserはyaccの生成したコードに依存していて、yaccの生成したコードはPTXParser::Stateに依存している。

で、コンパイラは、どちらを先に読み込んだとしても、知らないクラスや知らない定数がいきなり出てくるので、よくわかんなくなって、困ってしまう、と。

こういうシチュエーションはC++ではよくあることで、そのためにクラスの前方宣言という機能が用意されております:

namespace hoge{
class Fuga; // これが前方宣言。
}

// ポインタ、もしくは参照としてなら使える
int foo(hoge::Fuga& fuga);

namespace hoge {
// 実際の宣言
class Fuga {
...(略)...
}
}

こんな感じで最初に「hogeというネームスペースの中にFugaというクラスがあるぞ!」とコンパイラに教えておいてあげると、foo関数の定義を見たコンパイラは、「よくわかんないけど、そういうクラスがあるんやな」となんとなく察してコンパイルを続行することが出来ます(逆に、前方宣言をしないと「hoge::Fugaって何?」とエラーを吐いて止まってしまいます)。ただ、あくまで「なんとなく」なので、ポインタか参照としてでしか使えません(もっと詳しくはコンパイラの本かC++の本を読んでね)。

じゃあ今回もそうするか…と言いたいところなのですが、parser::PTXLexerはともかく、parser::PTXParser::Stateクラスはふつうのクラスではありません。上で見たとおり、Parserクラスの中に存在するクラス、「インナークラス」です。C++では、残念ながらインナークラスの前方宣言は出来ません。もしできれば万事解決しそうなのですが、C++の仕様上できないので仕方がない(どうしてそういう仕様なのかは、謎)。

まぁ、このインナークラスが前方宣言できなくて困るシチュエーションも、C++ではよくあることです。じゃあ、そういう時はどうするのかというと、普通に設計を見直してリファクターします

…はぁ…。まぁ、「動かない」ってことで、いいか…。でも、なんで今までこれでコンパイル通ってたんだろう?

今回のまとめと次回のPyrit

GPUなしでCUDAの実行をするのは、現実的にはどうやら難しいらしいことがわかりました。

CUDA用の純正コンパイラ「nvcc」に、CPUでエミュレートするためのコンパイルフラグが、過去には存在していたようですが、現在は跡形もなく無くなってしまいました。CUDAの使えるGPUが非常に限られていた時代ならいざしらず、NVIDIAのカードならどれでもCUDAが使える昨今ではあんまり需要は無くなったからなのか、…それともCUDAがGPGPUとしての覇権を取ったから、傲慢になったのか。その辺はわかりませんが。

ちなみにTensorFlowとかCaffeはCPU用とGPU用のコードが両方ともゴリゴリ書いてあったと記憶しております。大変だねぇ。資本を上げて人月で殴れ!

次回の月刊Pyritの頃にはGPUサーバが使えるようになるはずなので、素直にGPU使って開発しようと思います。

Numbaを使ってpyhonコードを高速化する方法

こんにちは、Link-Uの町屋敷です。

今回は、機械学習を行う際にほぼ必ず行わなければならない前処理を、
GPUを使ってやったら早く終わったので、メモがてらに書いていきます。
今回はpythonでの話です。

pythonでcudaを使ったGPU演算をする方法として、
NVIDIAの公式でも紹介されているnumbaを使いたいと思います。

@Vectorizeを使った方法

pipでも入るそうですが、anacondaでもインストールできるのでcondaを使用します。

Anaconda,Minicondaのインストール方法はバックナンバーで、

conda install accelerate

このコマンドを使うとnamba以外にも必要なパッケージが入るので楽です。

早速試してみましょう。

先程の公式ページの動画内に書かれていたコードを使っててみます。

import numpy as np

from timeit import default_timer as timer
from numba import vectorize
from numba import cuda, float32

@vectorize(['float32(float32, float32)'], target='cpu')
def VectorAdd(a,b):
    return a + b

@vectorize(['float32(float32, float32)'], target='cuda')
def GpuAdd(a,b):
    return a + b

def NormalAdd(a,b,c):
    for i, _ in enumerate(a):
        c[i] = b[i] + a[i]    

def main():
    
    for N in [1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8]:
        vec_a = np.ones(int(N), dtype=np.float32)
        vec_b = np.ones(int(N), dtype=np.float32)
        vec_c = np.zeros(int(N), dtype=np.float32)
        
        start = timer()
        NormalAdd(vec_a, vec_b, vec_c)
        normal_time = timer() - start
        
        print('When [{0}] vector, NormalAdd took {1} seconds'.format(N, normal_time))
        
        vec_c = np.zeros(int(N), dtype=np.float32)
        
        start = timer()
        vec_c = VectorAdd(vec_a, vec_b)
        cpu_time = timer() - start
        #print(C)
        
        print('When [{0}] vector, CpuAdd took {1} seconds'.format(N, cpu_time))
        
        start = timer()
        vec_c = GpuAdd(vec_a, vec_b)
        gpu_time = timer() - start
        
        print('When [{0}] vector, GpuAdd took {1} seconds'.format(N, gpu_time))
        print('Normal speed / CPU speed = {0}'.format(normal_time/cpu_time))       
        print('Normal speed / GPU speed = {0}'.format(normal_time/gpu_time))    
        print('CPU speed / GPU speed = {0}'.format(cpu_time/gpu_time))

numbaでは高速化を行いたい関数にデコレータを付けます。

この例では@vectorize([‘float32(float32, float32)’], target=’cuda’)の部分が該当します。

@vectorizeの第一引数には、C言語の関数の宣言ように返り値と引数の型を記述します。

第二引数はをcudaにするとGPUをcpuにするとcpuを使って最適化します。

GPUサーバーで動かした結果はこの通り。

何もしていないときと比べて遥かに早くなりました。

ただ、GPUを使用し始めるのに3.5秒ほど準備期間が必要な模様で、最初の処理に時間がかかっています。

また、CPUのほうが早いという結果に。

桁数がもう少し増えれば逆転しそうだがあまり降らしすぎるとメモリーエラーになります。

公式の動画でtarget=cpuをやっていないのはそういうことがややこしいからなのか……

このままではCPUのほうが良いんじゃないか説が出てきてしまうので、少し処理を追加した関数でやってみましょう。

@vectorize(['float32(float32)'], target='cuda')
def RadToDegGpu(a):
    return (360 + 180 * a / np.pi) % 360

@vectorize(['float32(float32)'], target='cpu')
def RadToDegCpu(a):
    return (360 + 180 * a / np.pi) % 360

def main():
    
    for N in [1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8]:
        A = np.ones(int(N), dtype=np.float32) * np.pi
        B = np.zeros(int(N), dtype=np.float32)
        
        start = timer()
        B = RadToDegCpu(A)
        cpu_time = timer() - start
        
        print('When [{0}] vector, RadToDegCpu took {1} seconds'.format(N, cpu_time))
        
        start = timer()
        B = RadToDegGpu(A)
        gpu_time = timer() - start
         
        print('When [{0}] vector, RadToDegGpu took {1} seconds'.format(N, gpu_time))
        print('x{0} speed'.format(cpu_time/gpu_time))

ラジアンを°に変える簡単な関数です。

nambaはnumpyに最適化されているため関数を使う時は極力numpyを使いましょう(この例だと使ってるのはただの定数だけど)。

引数の数が変わっているので、@vectorizeの第一引数も変わっています。

x~speedの~が1以上だとgpuのほうが早いです。

桁数が小さい時はまだCPUのほうが早いですが、大きくなってくるとGPUを使ったほうが約3倍早くなっています。

ただし最初の準備期間3.5秒は一律でかかるので、この処理単体だけをやるとGPUのほうが遅くなります。

1回の実行では使う関数が変わっても1回しか準備期間はないようなので、封数の処理を一気にやると良いでしょう。

@cuda.jitを使った方法

次に行列を使った計算を高速化する方法をここを参考にして書いていきます。

例としてデータの前処理によく使う各行に対して平滑化を行うプログラムを作ります。

まず、普通の実装

def NormalSmooth(inputMat, outputMat):
    for i, row in enumerate(inputMat):
        for j, v in enumerate(row):
            if j == 0:
                outputMat[i, j] = (inputMat[i, j] + inputMat[i, j] + inputMat[i, j + 1])/3
            elif j == outputMat.shape[1] - 1:
                outputMat[i, j] = (inputMat[i, j - 1] + inputMat[i, j] + inputMat[i, j])/3
            else:
                outputMat[i, j] = (inputMat[i, j - 1] + inputMat[i, j] + inputMat[i, j + 1])/3

そして、@cuda.jitを使った実装

@cuda.jit
def GpuSmooth(inputMat, outputMat):
    row, col = cuda.grid(2)
    if row < outputMat.shape[0] and col < outputMat.shape[1]:
        if col == 0:
            outputMat[row, col] = (inputMat[row, col] + inputMat[row, col] + inputMat[row, col + 1])/3
        elif col == outputMat.shape[1] - 1:
            outputMat[row, col] = (inputMat[row, col - 1] + inputMat[row, col] + inputMat[row, col])/3
        else:
            outputMat[row, col] = (inputMat[row, col - 1] + inputMat[row, col] + inputMat[row, col + 1])/3

cuda.grid(2)を使うことで簡単に2重のfor文の処理を書き換えることが出来ます、

cuda.grid(2)が返す値はx,yともに正の値ですが、上限が行列の形と違うのでif文を使って行列の外になった場合処理をしないことが必要になります。

def main(): 
     
    for R in [10,100,1000,10000]:
        for C in [10,100,1000,10000]:
    
            A = np.ones((R, C))
            B = np.ones((R, C))
            
            start = timer()
            NormalSmooth(B, A)
            normal_time = timer() - start
            
            print('When [{0}, {1}] matrix, NormalSmooth took {2} seconds'.format(R, C, normal_time))
            
            start = timer()
            GpuSmooth(B, A)
            gpu_time = timer() - start
            
            print('When [{0}, {1}] matrix, GpuSmooth took {2} seconds'.format(R, C, gpu_time))
            print('x{0} speed'.format(normal_time/gpu_time))

こちらも行列が小さい時はCPUのほうが優位ですが大きくなってくると最大で129倍と圧倒的にGPUのほうが早くなります。

ちなみに手元のノートパソコンの結果が[10000, 10000]のとき121.75秒かかっていたので100倍以上高速化されたことになります。

まとめ

numbaを使うことでpytonスクリプトを高速化する手法を書いた

大きいデータを扱う時はかなり高速化されるので積極的に使っていきたい。

AIを端末側で処理するチップ達

以前NVIDIAの新しいGPUを紹介しましたが、NVIDIAのGPUはPCで主に利用されると思います。

しかし、恐らくAI(正確には機械学習の推論)を行う回数で言うと圧倒的にスマートフォンの方が多いと思います。

今回はスマートフォン等に搭載されるチップがAIをどう処理するかを紹介していきましょう。今回はどのチップもPVがあったので全編PV付きでお送りします。

Snapdragon 845

スマホ用チップの雄、QUALCOMMの最上位チップです。Androidのハイエンド機は一部の例外を除いてほぼこのチップを使っていると言っても過言ではないかと。

ただし、最近のチップの中では比較的AI系の性能は控えめで、どちらかというと従来からのCPUやGPUといった部分の強い正統派のチップです。

AIに対する対応はCPU+GPU+DSPで行い専用回路は持ちません。

この対応だと、AI用の回路がない分、チップに余裕ができるので、CPUやGPUといった汎用的な回路を強化できる利点があります。

一方特にCPUなどは汎用的な処理ができる分、大量のAI向け演算などは処理量の点でも、電力効率の点でも苦手と言えます。

このあたりAIに関連する処理が、全スマホ利用時間のうちどの程度を占めるか、メーカーによる考え方の違いとなって表れてきます。

QUALCOMMとしては音声認識など局所的にAIを使うことはあっても、全利用時間に占める割合はさほど高くないと踏んでいるのではないでしょうか。

とはいえ、AI性能は全世代のSnapdragon 835比で3倍をうたっていますので、CPUやGPUの性能が30%程度の向上であることを加味すると力を入れてきているなというのはあります。

ところでSnapdragon 845にはWiFiの接続が16倍高速になるという機能向上もあり、性能面で言うとそちらが一番の底上げであったり。

そちらも個人的には気になります。

Kirin 980

最近登場した中国Huawei製のチップ。恐らくHuawei製の端末以外採用されていない・・・はず。

QUALCOMMとは真逆で積極的にAI系の機能を盛り込んでくるメーカーで、昨年のKirin 970からAI系の回路を盛り込んできています。

Kirin 980では回路規模を倍増させており、AI系の性能はKirin 970の2倍以上になっていると思われます。

とはいえ、CPU性能も75%向上したらしく、AI系の性能を特別に向上させた、というよりは全般的に2倍程度になるようにチップを設計したようです。

中国メーカーの技術力の伸びを示すような、かなりアグレッシブな性能のあげ方です。

Apple A12 Bionic

日本で一番普及しているiPhoneの最新版に搭載されているチップ。

Appleは他の会社と違ってちゃんと素の演算回数を公表してくれており毎秒5超回の演算ができます。

全世代からAI系の機能をチップに入れてきていますが、前世代と比較して9倍の性能になっています。

こうして他のチップと比較してみるとAppleが全力でAI系を増強してきていることがわかります。

実はAppleは自社生産かつ大量生産なので、他の会社よりもチップにお金をかけることができます。

なので、チップに他社より多くの機能を入れることができ、AI系の機能を強化する余裕があるのかもしれません。

Movidius NCS

IntelがAIチップベンチャーを買収して作ったUSBデバイス。1Wで100GFlopsです。

専用設計で100GFlopsというのは若干微妙な気もしないではないですが、USBインターフェイスとかも入っていることも考えるとこんなものでしょうか。

このデバイス、USBで刺すと使えるので後付けできるのが最大の魅力です。しかも複数台刺して性能向上なんてこともできるようです。

Raspberry Piに刺して使えるなどD.I.Yでデバイスが作れそうな予感が大変します。

というかIntelもCPUにそういう系の機能つければいいのにと思わなくもないです。

まとめ

各メーカーで取り組み方に差はみられるものの、基本的にどのチップメーカーもAI強化に舵を切っていることがわかります。

現在はカメラ、音声認識などでの利用が多いようですが、AIを使えば便利になるシーンは多いと思います。

Pythonで次元圧縮する方法

こんにちは、Link-Uの町屋敷です。

今回は次元圧縮について書いていこうと思います。

データの次元数が多いとどうなるのか

次元の呪いという単語を機械学習では度々目にします。
入力するデータの次元数が多いとモデルに対して与えられる点が相対的に少なくなっていろいろ不都合が出るとか、単純に計算量が多くなってやばいといったもので、
計算が終わらないから次元圧縮するという流れになるんですが。
そもそも使用する頻度の高いSVMなどの学習機で実際どのくらい終わらなくなるのか計測したことがなかったので、
次元圧縮の話の前にまずやってみました。

今回使用するデータは生成データで2クラス分類問題を行います。

DIMENTION_MAX = 2000
SEED = 12345
np.random.seed(SEED)

n_features = 1000
label = []

#ラベルの生成
for i in range(int(n_features/2)):
    label.append(0)
    label.append(1)
    
label = np.array(label)

dim = 100
#次元数がMAXを超えるまでループ
while dim < DIMENTION_MAX:
    feature = []
    x_axis.append("{0}".format(dim))
    
    for i in range(dim):
        #データ生成用の変数を作る
        mu_a = np.random.normal(0,1)
        omega_a = np.random.rand()
        
        mu_b = np.random.normal(0,1)
        omega_b = np.random.rand()
        
        for j in range(int(n_features/2)):
            #上がラベル0、下がラベル1
            feature.append(np.random.normal(mu_a,omega_a) + np.random.normal(0,10*dim/DIMENTION_MAX))
            feature.append(np.random.normal(mu_b,omega_b) + np.random.normal(0,10*dim/DIMENTION_MAX))
            
    #特徴量を要素数*次元数の形に変換        
    feature = np.reshape(feature, (dim, n_features))
    feature = feature.T

具体的には上コードで正規分布を使って作ったデータです。

最初と最後の特徴量だけ取ってきてラベルごとに色を変えてプロットするとこんな感じ。

実データを使うとデータごとに違った結果にまずなりますので今回の結果はあくまで参考です。
次元数は100から始めて2000まで100ずつ増加させてそれぞれ1000個ずつデータを作ります。

次に各次元で生成した特徴量を学習データとテストデータに分割するんですが、

sklearn.model_selection.train_test_split

をそのまま使うと分割したデータのラベルの数が偏ってしまうので、今回はここから関数を拝借してきて使ってます。

それをSVM,ロジスティック回帰、ランダムフォレスト、ニューラルネットで学習して、次元数ごとに学習にかかった時間と学習器の良さを計るF1値をノートパソコンとサーバーで計測しました。

ただし、scikit-learnがGPUに対応していないので、ニューラルネットのみGPUを使っています。

結果は以下の通りで左側のy軸が計算にかかった時間、右側のy軸がF1の値でx軸は次元数です。

このように次元数が増えると時間がかかるだけでなく、精度も落ちてしまうアルゴリズムが出てきてしまいます。

特にSVMは学習に使うデータ量より多い次元を分類しようとすると精度が絶望的になります。

このような問題を回避するためには、データ量を増やす他に、次元を削減したり、データのすべての次元を使うのではなく有用だろうと思われるものを選んで学習に使う必要があります。

次元圧縮

今回は次元を圧縮する方法として、主成分分析(PCA)線形判別分析(LDA)を使います。

タスクが簡単なので線形な変換をするやつだけ。

文章トピック分類に用いるLDAではないので注意。

PCAには教師データが必要ありませんが、LDAには必要です。

LDAは教師データを使って最もよくクラスタを分類するように新しい軸を検索します。

一方でPCAには教師データが必要ありません。

PCAとLDAの違いはここがわかりやすい(英語)

PCA,LDAともにskikit-learnに実装されているので簡単に行うことが出来ます。

from sklearn.decomposition import PCA
    
    dcp = PCA(n_components=10) #n_componentsで削減する次元数を指定
    dcp_data = dcp.fit_transform(data)
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
    dcp = LinearDiscriminantAnalysis(n_components=10) #n_componentsで削減する次元数を指定
    dcp_data = dcp.fit_transform(data, label) #教師データとしてlabelを渡す

上に載せてあるデータにPCAをかけて2次元に圧縮すると結果はこんな感じになります。

LDAをかけて1次元に圧縮する(カラスが2つなので1次元になる)とこんな感じ。

PCAを使って圧縮時間も含めて処理時間とF1値を計算した結果がこちら。

比較用に圧縮してないときの結果も載せた。

F1は1が最高ですべてのテストデータを正解したことを示す。

全体的に処理速度が早くなり、F1の値が向上している。

ニューラルネットだけ時間が伸び気味なのは何故だろうか…

まとめ

今回は次元の圧縮で処理が早くなり、精度も向上することを示したが、

実データじゃない簡単タスクだからかもしれない。

isomapとかの非線形の次元圧縮方法や、t-sne、オートエンコーダも紹介していないので、

もっと難しいデータでいつか紹介したい。

使用したソースコード

#Python3系じゃないとバグります

import time
from matplotlib import pyplot as plt
import numpy as np
from sklearn.decomposition import PCA, FastICA
from sklearn.linear_model import LogisticRegression
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.mixture import GaussianMixture
from sklearn.svm import SVC
from sklearn.model_selection import StratifiedShuffleSplit
from sklearn.metrics import confusion_matrix, f1_score
from sklearn.manifold import TSNE

import keras
from keras.models import Sequential
from keras.layers import Dense, Dropout, Flatten

import joblib

#Quoted from https://stackoverflow.com/questions/35472712/how-to-split-data-on-balanced-training-set-and-test-set-on-sklearn
def get_safe_balanced_split(target, trainSize=0.8, getTestIndexes=True, shuffle=False, seed=None):
    classes, counts = np.unique(target, return_counts=True)
    nPerClass = float(len(target))*float(trainSize)/float(len(classes))
    if nPerClass > np.min(counts):
        print("Insufficient data to produce a balanced training data split.")
        print("Classes found %s"%classes)
        print("Classes count %s"%counts)
        ts = float(trainSize*np.min(counts)*len(classes)) / float(len(target))
        print("trainSize is reset from %s to %s"%(trainSize, ts))
        trainSize = ts
        nPerClass = float(len(target))*float(trainSize)/float(len(classes))
    # get number of classes
    nPerClass = int(nPerClass)
    print("Data splitting on %i classes and returning %i per class"%(len(classes),nPerClass ))
    # get indexes
    trainIndexes = []
    for c in classes:
        if seed is not None:
            np.random.seed(seed)
        cIdxs = np.where(target==c)[0]
        cIdxs = np.random.choice(cIdxs, nPerClass, replace=False)
        trainIndexes.extend(cIdxs)
    # get test indexes
    testIndexes = None
    if getTestIndexes:
        testIndexes = list(set(range(len(target))) - set(trainIndexes))
    # shuffle
    if shuffle:
        np.random.shuffle(trainIndexes)
        if testIndexes is not None:
            np.random.shuffle(testIndexes)
    # return indexes
    return trainIndexes, testIndexes
#Quote end

DIMENTION_MAX = 2000
SEED = 12345
np.random.seed(SEED)

n_features = 1000
label = []

#ラベルの生成
for i in range(int(n_features/2)):
    label.append(0)
    label.append(1)
durations = []
f1_values = []
label = np.array(label)
for clf_name in ['SVM', 'LogisticRegression', 'RandomForest', 'NeuralNet']:

    x_axis = []
    for decomp_name in ['LDA']:#['LDA', 'ICA']:
        dim = 1000
        #次元数がMAXを超えるまでループ
        while dim < DIMENTION_MAX:
            feature = []
            x_axis.append("{0}".format(dim))
            
            for i in range(dim):
                #データ生成用の変数を作る
                mu_a = np.random.normal(0,1)
                omega_a = np.random.rand()
                
                mu_b = np.random.normal(0,1)
                omega_b = np.random.rand()
                
                for j in range(int(n_features/2)):
                    #上がラベル0、下がラベル1
                    feature.append(np.random.normal(mu_a,omega_a) + np.random.normal(0,10*dim/DIMENTION_MAX))
                    feature.append(np.random.normal(mu_b,omega_b) + np.random.normal(0,10*dim/DIMENTION_MAX))
            
                    
            #特徴量を要素数*次元数の形に変換        
            feature = np.reshape(feature, (dim, n_features))
            feature = feature.T

            
            #バランス良く訓練データとテストデータに分割
            train_index, test_index = get_safe_balanced_split(label, trainSize=0.8, getTestIndexes=True, shuffle=True, seed=SEED)
           
            train_feature, test_feature = feature[train_index], feature[test_index]
            train_label, test_label = label[train_index], label[test_index]
            
            #学習器の選択
            if clf_name == 'SVM':
                clf = SVC(C = 1, gamma = 0.01)
            elif clf_name == 'LogisticRegression':
                clf = LogisticRegression(C = 1e5)
            elif clf_name == 'RandomForest':
                clf = ExtraTreesClassifier(n_estimators=1000,random_state=0)
            
            start = time.time()
            
            #次元圧縮法の選択
            if decomp_name == 'PCA':
                dec = PCA(n_components = 2)
                train_feature = dec.fit_transform(train_feature)    
                test_feature  = dec.transform(test_feature)
            elif decomp_name == 'LDA':
                dec = LinearDiscriminantAnalysis(n_components=1)
                train_feature = dec.fit_transform(train_feature, train_label)
                test_feature  = dec.transform(test_feature)
            elif decomp_name == 'ICA':
                dec = FastICA(n_components = 2)
                train_feature = dec.fit_transform(train_feature)
                test_feature  = dec.transform(test_feature)
            elif decomp_name == 'TSNE':
                dec = TSNE(n_components=2, perplexity=30)
                train_feature = dec.fit_transform(feature)
            
            if clf_name == 'NeuralNet':
                clf = Sequential()
                clf.add(Dense(64, activation='relu', input_shape=(len(train_feature[0]),)))
                clf.add(Dense(1, activation='sigmoid'))
                
                clf.compile(loss='binary_crossentropy',
                            optimizer=keras.optimizers.Adadelta(),
                            metrics=['accuracy'])
                
                clf.fit(train_feature, train_label,
                          batch_size=128,
                          epochs=100,
                          verbose=0)
                predict = np.round(clf.predict(test_feature))
            else:
                clf.fit(train_feature, train_label)
                predict = clf.predict(test_feature)
            
            
            
            duration = time.time() - start
            
            print("Dim {0}, Time: {1}".format(dim, duration))
            print(confusion_matrix(test_label, predict, [0,1]))
            
            f1_values.append(f1_score(test_label, predict, [0,1]))
            durations.append(duration)
            dim += 100
            
        #データの保存、保存したデータはjoblib.loadでロードできる 
        joblib.dump(durations, '{0}_{1}_Note_durations.pkl'.format(clf_name, decomp_name))
        joblib.dump(f1_values, '{0}_{1}_Note_f1values.pkl'.format(clf_name, decomp_name))

GPUを使って無線LANをクラックする話:Pyritの考古学/倫理学

拝啓。

自販機にたまにホット飲料を見かける季節となりましたが皆さまいかがおすごしでしょうか。

秋ですね。気まぐれと勢い 旅行で行った九州では彼岸花が咲いておりました。

今回は咲きかけギリギリのヒガンバナくんの写真です。

これぐらいのをお散歩中に見つけたら、だいたい翌日か翌々日ぐらいには咲きますので、翌日もぜひ見に行ってあげてくだせぇ。ヒガンバナくんは、写真で見るより実物のほうが絶対いいです。雨が降ってない事を祈ります。

あーでも。毒性があるので持ち帰って食べたりしちゃダメですよ。持ち帰るのは思い出だけ。山と一緒かな。

前回までのPyrit

じゃーまた、WiFiのパスワードでも、クラックしてきますか。

前回わかった事は、最初取ったベンチマークで「GPUはCPUより速くてすごーい!!」とか喜んでたけど、実はGPUは10%も使っていないし、CPUも全部は使いきってはいなかった…というなかなか衝撃的な事実でした。さらに言えば、そのベンチはGPUの分と称してCPUも使っている、公平かどうかは正直怪しいと言わざるを得ないものでありました。

言うなれば我々は…ただの幻を見て一喜一憂していたのです。

どうしてこうなった(AA略)

うーん。悲しい。

実際に何か手を動かす前に、どうしてこんなことになってしまったのか想像してみましょう。Pyritのクラスターを組んでいたみなさんは、実はほとんど寝てるだけのGPUを前に、ドヤっていたのか。まさか、そんな。

Pyritの考古学

Pyritが活発に開発されていたのは2009〜2010年ごろです。DeepLearningブームが始まったのが2012年とかなのでそれよりも前だし、その頃に生まれた子供は、今小学校で九九を覚えてる頃。それぐらい大昔です。そんな古代のソフトウェアを今動かそうというのですから、歴史を踏まえなければ、目の前の状況を理解することはできないでしょう。

まず、GPUをなんでこんなに遊ばせてしまっているのか。

ひょっとすると、前回使ったVisual Profilerが実はその頃なかったのかもしれません。だから使い切ってない事に誰も気づかなかったとか。が、しかし、NVIDIAの公式ページによると2008年から作ってるとの事なので(頑張ってるなNVIDIA)、この線は無い…と思いたい。つまり、「昔はGPUを全部使い切ってたけど、時間が経ったら状況が変わった」可能性が高い。

あの頃のGPU:GTX480が出た頃(買えたとは言ってない)

2010年といえば、GPUならGeForce GTX 295(2009年6月)とか、GTX 480(2010年3月)の頃です。…もう何も覚えてない…。まーとりあえず表でも書いてみますか。CUDAとは直接は関係ないですが、参考程度にPassMarkのベンチマークの数値も貼っときます。グラフィクスを描く時もCUDAコアが走るそうなので、無関係ではあるまい。

GPU発売時期CUDAコアクロックCUDAコア数PassMarkベンチ
GTX 2952009/061242MHz240×21052
GTX 4802010/031401MHz4804358
GTX 1080 Ti2017/021480MHz358414057

GTX480ではGPGPUへの最適化も進んだそうで、一気に性能が上がっていますが、曰く

最初のロットの歩留まりは、嘘か真かは不明だが2%ほどだったという。その後もステッピングを重ねてできる範囲での改良を施したものの、最終的に2010年3月のGeForce GTX 480発表時点で出荷可能な枚数は全世界を合わせて数千枚程でしかなかった。

ロードマップでわかる!当世プロセッサー事情 ― 第146回
GPU黒歴史 DX11への遅れが生んだ駄作 GeForce GTX 480

だそうで、2010年のゲーマーたちはだいたいGTX295を使っていたんじゃないかと思います。つまり、今の1080 Tiは当時に比べて10倍以上、逆に言えば、GTX295は今に比べたら1/10以下の文字通り「桁違い」の性能だったと思われます。…ところで、10%弱しか走ってなかったんですよね?

あの頃のCPU: Core i7が初めて出た頃

じゃあ一方CPUはどうなんだ。2010年にPCパーツショップに並んでいたのは、Core iシリーズの最初、Nehalem世代です。これももう覚えてないですねぇ。せいぜい登場時に「3と5と7って何?Core i7には7コア載ってるのか?」と思ったのを覚えている程度です(答え:載ってない)。

同じように表を書いてみましょう。

GPU発売時期クロック(ターボ)コア数(スレッド数)PassMarkベンチ(マルチ/シングル)
Core i7 9602009/103.2GHz(3.46GHz)4(8)5828/1389
Core i7 8700K2017/103.7GHz(4.7GHz)6(12)15969/2704
Xeon Silver
4116
2017/022.1GHz(3.0GHz)12(24)15131/1599

ターボクロックはカッコの中に一応書いてはいますが、ターボブーストは「一時的に加速できる」という機能ですので、ずっと負荷を掛け続けるベンチマークではベースクロックの方が重要です。

ベンチに使ってるサーバに乗ってるのが最後のXeon Silver 4116です。PassMarkのベンチマーク的にはなんとシングルコア性能自体は2009年のCPUである960と大して変わらないという結果になってます。もちろん周波数は960よりかなり低いので、「周波数あたりの性能は上がってる」と言えるのは間違いなく事実なんですけどね。

最近のサーバ用CPUトレンドはこのようにそこまでの性能ではない低い 周波数のコアをたくさん束ねて全体としての性能を確保する戦略らしく、結果としてCPU全体では10年前のCPUの三倍ぐらいの性能は出るようになっています。という所は観察できました。

時を経ても変わらないもの―Pythonはシングルスレッド

GPUもCPUも速くなってはいるけれど、一つだけ変わらない事があります。

それは、Pythonはシングルスレッドでしか動かないという事実です。PythonにはGIL(Global Interpreter Lock)という仕組みがあるので、いくらthreading.Thread()してスレッドを作っても、同時に動くPythonのスレッドはたった1つだけです。100コア積んでも5000兆コア積んでも1つだけ。

ちょっと待て。じゃあなんでPythonで書かれてるはずのPyritはマルチコア対応してるんだ?もっというとDeepLearningはみんなPythonでやってるんじゃ無いのか?シングルスレッドなのか?

もちろんそんな事あるわけなくて、PythonからC言語の拡張を呼んだ時は、C言語で処理しつつPythonの他のスレッドを起こす事ができます。その時はPy_BEGIN_ALLOW_THREADS;Py_END_ALLOW_THREADS;で囲めばマクロがよしなにスレッドの面倒を見てくれます。

実際にPyritでCPUでクラックする時もこんな感じになってます:

    Py_DECREF(passwd_seq);

    if (arraysize > 0)
    {
        Py_BEGIN_ALLOW_THREADS;
        i = 0;
        do
            i += finalize_pmk(&pmk_buffer[i]);
        while (i < arraysize);
        Py_END_ALLOW_THREADS;

        result = PyTuple_New(arraysize);
        for (i = 0; i < arraysize; i++)
            PyTuple_SetItem(result, i, PyString_FromStringAndSize((char*)pmk_buffer[i].e1, 32));
    } else {
        result = PyTuple_New(0);
    }

    PyMem_Free(pmk_buffer);

    return result;
}

これを使う事で1つ以上のCPUコアを使う事が可能になっていますが、しかし、他の部分は全部シングルスレッドでしか動かないことは記しておく価値があると思います。C言語のコードでも、PythonのオブジェクトからCの値に変換したり、その逆をしたりするところはシングルスレッドでやらないといけません。

CPUを全コア使いきれていない理由は、前回書いた通り、ここだと思います。パスワードを生成する部分がPythonで書かれているので、そこがボトルネックになっているんだと思います。

Pyritの倫理学:「公平なベンチマーク」ってなんじゃらほい

まぁ、だいたい状況は掴めました。次にルールを考えましょう。

「ベンチマーク」という「勝負」のルールを、です。

現在のPyritのbenchmarkコマンドのルールでは、「CPU」と「GPU」の勝負のはずが、「GPUのために準備するCPUのコード」も同時に別々のCPUのスレッドで走っています。

CPUのスレッドはランダムなタイミングで割り込まれる可能性がありますから、CPUがクラックしているコード上の「行間」でGPUの為に準備するスレッドのコードが実行されて、CPUの性能が見かけ上悪くなってる可能性はかなり高いです。わたしはこんなんじゃあ、公平なベンチマークとは到底言えない思います。

「公平」とはなんじゃらほい??

ほう、「公平」ねぇ。ところで、「公平」ってなんでしょう?試しに「公平な社会」とか書いて見ると、これがいかにも政治家さんや官僚さんの口から出てきそうな単語な事からも分かるように、「公平」とは人によって意見が別れうる、一筋縄ではいかない手強い単語なわけです。

まぁ、「公平な社会」が何なのかは置いておいて(わたしにはわからん)、今回は「公平なPyritのベンチマーク」とは何なのかのわたしなりの意見を書いておきます。

CPUとGPUは明らかに対等な立場ではありません。というのも、CPUだけでパスワードのクラックはできるけれど、GPUだけではできないからです。CPUがGPUの処理しやすい問題の形式に整えてから、GPUが一気に処理をする。そういう、協力関係で計算を進めるのがGPGPUです。 こういうのを一般的かつかっちょいい言葉では「ヘテロジニアス・コンピューティング」といいます。

そういう意味では、同じ勝負でも「サッカー」とはだいぶ雰囲気が違います。サッカーみたいに、お互いが対称なルール、例えば「GPUめ、CPUに頼らずクラックしてみろ。CPUもお前には頼らないから平等だよな?」みたいなルールでは、単にGPUが何もできなくて降参して終わりです。

そもそも勝負のルールってどうして必要なんだ?

サッカーという勝負のルールは、選手や観客が楽しく、かつ安全に遊ぶためのルールですが(たぶん)、じゃあ、Pyritのベンチマークという勝負のルールは何の為のルールでしょう?

まぁ結局は同じ、「面白いかどうか」が基準でいいと思うんですが、それをもうちょっと具体的に言えば、「GPUとCPU同士の本気の勝負が見たい」に尽きると思います。もうちょっと大人じみた言葉で言えば、「GPUの得意な処理をCPUからGPUにオフロードした時に、そこがCPUと比べてどれぐらい速くなるか?」の限界が見たい。

もちろん、一部だけ高速化できても全体で速くなるとは限りません。全体の10%がGPUで10倍速くなっても、1.1倍ぐらいしか速くなりません(アムダールの法則)。例えば、GPUがCPUに比べてそこまで得意ではない処理もGPUに持って言って「並列化」する事で、その部分はそこまで高速化しなくとも、システム全体としては高速化する可能性はあります。…が、個人的にそこはあんまり面白くないなぁ…GPUの最高性能、つまり「ガチ」が見たいなぁ…と思ったので独断により今後はこの上に書いた方針で行きたいと思います。Pyrit全体よりも局所的な情報の方が、他のシステムについて見積もる時に便利そうだし。まぁこのいかにもな理由の方は後付けなんですが。

流石にこれだけではGPUに甘々な感じがするので、今邪魔されているCPUにも救いの手を差し伸べましょう。CPUが邪魔されている原因は、結局CPUとGPUを同時に走らせてクラックしていることです。これは単にベンチマークをとる時に、別々に走らせれば邪魔されずにすみます。

ベンチマークのルールは与えられるものじゃない、考えるものだ

というわけで考えた「面白い勝負」のためのルールをまとめると:

  • GPUの一番得意な処理をCPUからGPUにオフロードする
    • そこが全く同じ処理をするCPUと比べ、どれぐらい速くなるかを測定
  • CPUとGPUは別々に走らせて、お互いに邪魔しあう事を防ぐ

そろそろ長くなってきたので、もっと具体的な話は次回で。

本当に今のルールは「公平」ではないのか?

一応擁護しておくと、今のPyritのベンチマークのルールも「公平」だと言えなくもありません。

というのも、今のPyritのベンチマークは会社でよくある「成果主義」そのものだ、と捉えることも出来るからです。会社というのも協力関係がお互いにあるわけですが、「成果主義」の会社ではお給料を決めたりする時はその上で「そいつが、会社の利益に、どれくらい貢献したか?」みたいなのを(定量的にじゃないにしても)測ります。Pyritの今のベンチマークは、それと似たような事を測っている、と捉えることは可能だと思います。

で、この「成果主義」をどう思うか、具体的にどうするか、色々意見があることと、上でわたしがベンチマークのルールをどうするか悩んでいるのと、対応がつくわけです。もちろん、人とコンピュータの世界では前提が色々違うので全く同じというわけではありませんが、「一筋縄ではいかないねぇ〜」「意見が別れるだろうね〜」という点では全く同じです。

まとめ

Pyritが想像以上に大昔のソフトウェアだったので、歴史を調べました。

Pyritが盛んに開発されていた頃のGPUはCUDAへの最適化が進む一歩手前で今とは桁違いの性能差がありそうなこと。

シングルコア性能は今のサーバのXeonは昔のハイエンドCore i7と同じぐらいの性能だけれどマルチコアにすることで性能を稼いでいること、Pythonは相変わらずシングルスレッドなこと。そんなことがわかりました。

そして、わたしの興味に応じた「ぼくのかんがえたベンチマークのルール」も考えました。意外と人の仔の世界とも通じるものが有るんじゃのぅ。

さ〜て次回のPyritは?

このルールに応じてPyritを書き換えて、測定しなおしましょう!

山の上の石に日が暮れるまで座って色々考えてると今回みたいな記事になりまして。
まぁ、たまにはこういうのをじっくり考えるのも大事なんじゃないかなぁ、って最近思うんですよ。

TuringアーキテクチャのGPUが発表されました

NVIDIAが新しいGPUシリーズ、Turingシリーズを発表しました。

弊社にあるGPU、GeForce 1080TiはPascalアーキテクチャ、Tesla V100はVoltaアーキテクチャです。

VoltaもTuringもPascalの進化系ではあるのですが、VoltaはGPGPUなどのコンピューティング系、Turingはグラフィックス系です。

GPUの使われ方が二極化してきたので設計を分けたのでしょうか。

まずは性能を比較してみましょう

とりあえず、CPUメーカーの長たるIntelの最上位モデルとNVIDIAのゲーム向け、サーバー向けの現行最上位モデル、そしてTuringのゲーム向け最高峰の浮動小数点演算能力を比較してみましょう。

 Xeon Platinum 8180GeForce GTX 1080TiTesla V100GeForce RTX 2080Ti
倍精度(64bit)1.12 TFLOPS0.33TFLOPS6.38TFLOPS0.37TFLOPS
単精度(32bit)2.24 TFLOPS10.61TFLOPS12.75TFLOPS11.75TFLOPS
半精度(16bit)2.24 TFLOPS10.61TFLOPS25.5TFLOPS11.75TFLOPS
消費電力205W250W250W250W
お値段$10009$699$8000~$9000$999

* Turingは未発売のGPUであるため、実際のスペックは異なる可能性があります。
* 定格の能力で比較しています。実際には温度等の環境によって性能が上下します。

これだけを見ると、10~20%しか性能が向上していないのに、しれっと価格は40%増しになっています。

これしか違いがないかというと、さすがにそんな馬鹿なことはなくて、追加の機能としてレイトレーシング向けのRTコアとTensorコアの搭載があります。

逆に、この2つの新機能が必要ないのであれば、発売から時間もたって価格も手ごろなPascal系のGPUを買うのが正解ではないかと思います。

Tensorコアとは?

Tensor:テンソル、とは何でしょうか?Wikipedia先生に聞いてみたところ、

テンソル: tensor, : Tensor)とは、線形的なまたは線形的な幾何概念を一般化したもので、基底を選べば、多次元の配列として表現できるようなものである。

全くをもって意味不明ですね。

要は行列なんですが、行列演算は機械学習の学習/推論の両方で多用されます。

そこで、普通に演算器を大量に積むのではなく、行列演算用のアクセラレータを用意した、そのアクセラレータがTensorコアという感じです。

実はTensorコア自体はVoltaにも入っています。VoltaとTuringのTensorコアを比較してみます。

 Tesla V100GeForce RTX 2080Ti
半精度(16bit)101.99T Tensor FLOPS99.53T Tensor FLOPS
消費電力250W250W
お値段$8000~$9000$999

* Turingは未発売のGPUであるため、実際のスペックは異なる可能性があります。
* 定格の能力で比較しています。実際には温度等の環境によって性能が上下します。

何故半精度だけで比較しているかというと、どうもVoltaのTensorコアは学習よりで、TuringのTensorコアは推論寄りっぽいので、どちらでも使うFP16しか被らないっぽいのです。

自信がなくてすいません、間違っていたら弊社お問い合わせフォームよりご指摘くださいませ。

比較してみて

エンタープライズとゲーム向けという差はあれど、Turingのゲーム向けGPUの圧倒的なコスパの良さが光ります。

残念ながら利用規約によりデータセンターでは使えないものの、データセンター以外で使うならTuringでいいんじゃないかな。。。

単精度演算はVoltaのみのサポートのようですが、機械学習の学習もFP16でやってもそこまで問題があるわけではないですし・・・。

RTコアについて

一応紹介したので、今回初登場のRTコアについてご説明します。

RTコアとは一言で言うと「レイトレーシングアクセラレーター」です。

Nvidiaのデモを見ていただけるとよくわかると思うのですが、今まで難しかった光の反射のリアルタイム描画を可能にする光線処理のアクセラレーターになります。

機械学習に興味がなくても、これだけでも買い替える価値があるやもしれませんし、逆にこの機能にも興味がないとなると、大して性能が違わないので前世代のGeForceでもいいかもしれません。

C#で強化学習 その1 -Q-learning(Q学習)で簡単なゲームAIを作ってみる-

こんにちはLInk-Uの町屋敷です。

今回は強化学習をやっていきたいと思います。

主にQ-learningの具体的な実装の方法を書いて、Q-learning自体の証明とかには触れません。

強化学習は今までやってきたニューラルネットやSVMなどの学習方法と毛色が異なります。

何をやるかをざっくりいうと
ある問題を解きたいときにある状況になったときにこういうことをしたらこうなったという経験を蓄積して、
その経験を元に次に同じ状況になったとき最適な行動を選択するようにAIを訓練します。

Q-learningを行う準備

強化学習を行うアルゴリズムはたくさんあるのですが、今回はQ-learningという手法をC#で一から実装していきます。
いつものPythonだと一から実装すると重くてやってられなくなるかもしれないから回避。
C#には今回使わなかったけどUnityもあるしね。

早速実装して行きましょう。
今回のタスクはRPGでよくある1対1の戦闘で相手モンスターを倒すことです。
プレイヤーは状況に応じて攻撃や回復を行います。

強化学習ではプレイヤーに何回も戦闘を行ってその結果によってAIを賢くしていきます。
なので、Q-learningどうこうのまえに自動で戦闘を行うプログラムを先に書く必要があります。

まずプレイヤーや相手モンスターを扱う親クラスCharacterを作りましょう。

public abstract class Character
    {
        private string name;
        private int id;
        private int maxHp;
        private int maxMp;
        private int hp;
        private int mp;
        private Dictionary<int, Action> actions;
        private Dictionary<string, double> weeknesses;

        public Character()
        {
            this.Init();
        }

        private void Init()
        {
            this.name = this.SetName();
            this.id = this.SetId();
            this.maxHp = this.SetMaxHp();
            this.maxMp = this.SetMaxMp();
            this.hp = this.maxHp;
            this.mp = this.maxMp;
            this.actions = this.SetActions();
            this.weeknesses = this.SetWeekness();
        }

        private string SetName()
        {
            return this.GetType().Name;
        }

        public abstract int SetId();
        public abstract int SetMaxHp();
        public abstract int SetMaxMp();

        public void SetHp(int hp)
        {
            this.hp = hp;
        }

        public void SetMp(int mp)
        {
            this.mp = mp;
        }

        public abstract Dictionary<int, Action> SetActions();
        public abstract Dictionary<string, double> SetWeekness();

        public string GetName()
        {
            return this.name;
        }

        public int GetId()
        {
            return this.id;
        }

        public int GetHp()
        {
            return this.hp;
        }

        public int GetMp()
        {
            return this.mp;
        }


        public int GetMaxHp()
        {
            return this.maxHp;
        }

        public int GetMaxMp()
        {
            return this.maxMp;
        }

        public Dictionary<int, Action> GetActions()
        {
            return this.actions;
        }

        public Dictionary<string, double> GetWeekness()
        {
            return this.weeknesses;
        }

        public void RestoreHp()
        {
            this.hp = this.maxHp;
        }

        public void RestoreMp()
        {
            this.mp = this.maxMp;
        }

    }

攻撃力とか防御力とかはなくて、HPとMPだけです、ダメージ量とかは技で固定で、攻撃の属性に対する相性をweeknessesで設定するモデルです。

カードゲームによくある仕組み。

次に、キャラクターごとにデータを作っていきます。

public class Player : Character
    {
        public Player() : base()
        {

        }

        public override int SetId()
        {
            return 0;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 100;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

SetWeeknessはさっき書いた属性に対する耐性です。今回属性は「物理」と「魔法」があります。

SetActions関数でそのキャラクターが選択できる行動を定義します。

CharacterクラスとPlayerクラスのように親クラスとしてActionクラスを作り、

行動の内容はActionTableクラスに定義されています。

    public class Action
    {
        public int id;
        public int hpDamage;
        public int hpHeal;
        public int mpCost;
        public string attribute;

        public Action(int id, int hpDamage, int hpHeal, int mpCost, string attribute, ref int count)
        {
            this.id = id;
            this.hpDamage = hpDamage;
            this.hpHeal = hpHeal;
            this.mpCost = mpCost;
            this.attribute = attribute;
            ++count;
        }
    }

    static class ActionTable
    {
        public static int count;
        public static Action normalAttack;
        public static Action magicAttack;
        public static Action heal;
        public static Action strongAttack;

        static ActionTable()
        {
            count = 0;
            normalAttack = new Action(count, 10, 0, 0, "physical", ref count);
            magicAttack = new Action(count, 15, 0, 10, "magic", ref count);
            heal = new Action(count, 0, 40, 10, "magic", ref count);
            strongAttack = new Action(count, 30, 0, 0, "physical", ref count);
        }
    }

Playerクラスでプレイヤーの情報を設定しました。

同じことを敵モンスターでも行います。今回はゴブリン、ウィッチ、グリズリーの3種類の敵を作りました。

それぞれの特徴は後で書きます。

さて、これでデータは揃ったのであとは戦闘部分を書けばいいのですが、Q-learningの説明を先にしてから説明します。

Q-learningを実装する

強化学習は、ある状況になったときにこういうことをしたらこうなったという経験を蓄積して、
その経験を元に次に同じ状況になったとき最適な行動を選択するようにAIを訓練するものでした。

よってまずどんな状況を考慮するかを決めてあげなくてはなりません。

RPGの一対一の戦闘で考えられうる状況のうち今回は以下の4つを考えます。

  1. 何と戦っているか
  2. 自分の残りHPはどのくらいか
  3. 自分の残りMPはどのくらいか
  4. 戦闘に勝利、敗北した

1は今回ゴブリン、ウィッチ、グリズリーの3パターンです。

残りHPや残りMPは単なる数字なのでその値一つ一つを異なる状況と考えてしまうと

連続値を扱えないQ-learningだと状況の数がかなり増えて計算に時間がかかってしまうので、ざっくり離散化します。

HPでは、残りHPが半分以上、残りHPが1/4以上、残りHPが1/4未満の3パターン。

MPでは、残りMPが半分以上ある、残りMPが半分未満だが0ではない、残りMP0の3パターンです。

1,2,3が戦闘中に考えられる状況です。

1,2,3それぞれ3パターンずつあって4が2パターンあるので今回考えられる状況は3*3*3+2=29通り存在します。

それぞれの状況でプレイヤーは選択できる行動を行います。つまりMPが切れていない状況では、

Playerクラスの関数SetActionsで追加した、通常攻撃、魔法攻撃、HP回復のうちどれかを実行することになります。

通常攻撃は相手に10ダメージ、魔法攻撃はMP10を使って相手に15ダメージ、回復はMP10を使って自分のHPを40回復します。

回復だけやけに数値が大きいのは、はじめ10でやってたんですけどQ-learningの結果全く使われない産廃と化していたので上げました。

次に報酬について説明します。

強化学習では、行った行動がいい行動だったのか悪い行動だったのかを判別する基準として報酬を用います。

つまり、行動の結果に点数を付けてあげます。

今回はRPGの戦闘なので、敵を倒したら1000点、負けたら-1000点といった超単純なものです。

HP,Mpがたくさんあって敵がゴブリンのときに通常攻撃して敵を倒せたらその組み合わせにプラスの評価がされるというわけです。

しかし、毎回行動を行った直後に効果が現れるとは限らないので、ある行動の評価を行うときはある程度未来までみてその間に得た報酬を参考にします。

つまり、HP,Mpがたくさんあって敵がゴブリンのときに通常攻撃を2回行ってから魔法攻撃をして敵を倒した場合、最後の魔法攻撃だけにいい評価を与えるのではなく、最初の通常攻撃にも意味があるだろうという考えです。

ある程度未来までみてその間に得た報酬のことを収益と言ってその期待値を行動価値Qといいます。

このへんは本や他のサイトのほうが詳しいので、それを見ることをあ勧めします。

Qは収益の期待値を表すので、ある状況、行動を行ったときのQの値がわかっていれば、選択できる行動の中でQの一番大きい行動を選んでおけば良いということがわかります。

そしてこのQを経験から計算するのがQ-learningです。

C#ではこんな感じ。

        public void updateQ(int situationNo, int nextSituation, int actionNo, double reward, List<int> unselectableActions = null, List<int> nextUnselectableActions = null)
        {
            int maxIndex = -1;
            double maxQ = -10000000;

            this.qValues[situationNo, actionNo] = (1 - this.alpha) * this.qValues[situationNo, actionNo]
                + this.alpha * (reward + this.gamma * serachMaxAndArgmax(nextSituation, ref maxIndex, ref maxQ, nextUnselectableActions));
        }

Qの値は状況、行動ごとに変わるので1度に更新するのは配列 this.qValues[situationNo, actionNo]の値1つです。

1回の戦闘で報酬が得られるタイミングは1回だけなので何回も何回も戦闘を行います。

1回の戦闘のことを1エピソードと呼びます。

        public override int MainProcess(int nEpisodes)
        {
            this.player = new Player();
            this.SetEneyList();

            var q = new QLearning(
                this.GetSituationSize(),
                this.GetActionSize(),
                0
            );
            int situationNo;
            int nextSituationNo;
            int e = 0;
            while (e < nEpisodes)
            {
                //this.enemy = this.SelectRandomEnemy();
                this.enemy = this.enemyList[e % 3];
                player.RestoreHp();
                player.RestoreMp();
                enemy.RestoreHp();
                enemy.RestoreMp();
                do
                {
                    situationNo = this.GetSituationNo();
                    nextSituationNo = -1;
                    var unselectable = this.GetUnselectableActions(situationNo);
                    int actionNo = q.SelectActionByEGreedy(0.05, situationNo, unselectable);

                    double reward = this.CalcActionResult(situationNo, ref nextSituationNo, actionNo);
                    var nextUnselectable = this.GetUnselectableActions(nextSituationNo);
                    q.updateQ(situationNo, nextSituationNo, actionNo, reward, unselectable, nextUnselectable);

                } while (nextSituationNo != ENEMY_DEATH && nextSituationNo != PLAYER_DEATH);

				if (e % 1000 == 0)
				{
					Console.WriteLine();
                    Console.Write(String.Format("Progress {0:f4}%", (double) 100 * e / nEpisodes));
					Console.WriteLine();
					this.PrintQValuesWithParams(q);
				}
				e++;
            }

            Console.WriteLine();
            this.PrintQValuesWithParams(q);

            return 0;
        }

while (e < nEpisodes)の中が1回の戦闘で、do-while文の中がプレイヤーと敵の攻撃の1ターンになります。

this.GetSituationNo()で現在の状況を確認し、q.SelectActionByEGreedyで状況とQをもとに行動を選択しています。

ここで、常に一番大きなQをもつ行動を選択するようにしてしまうと、たまたま良い結果が出たものを集中的に行って本当に良い行動を見落としてしまう可能性があるため小さい確率で一番大きなQをもつ行動以外を選択するようにします。

CalcActionResultで戦闘の処理と報酬の付与を行っています。

        public override double CalcActionResult(int situationNo, ref int nextSituation, int actionNo)
        {

            if (situationNo == PLAYER_DEATH)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            if (situationNo == ENEMY_DEATH)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }

            int playerHp = this.player.GetHp();
            int playerMp = this.player.GetMp();
			int playerMpOrg = playerMp;
            int enemyHp = this.enemy.GetHp();
            int enemyMp = this.enemy.GetMp();

            Action playerAction = this.player.GetActions()[actionNo];
            string playerAttackAttribute = playerAction.attribute;
            enemyHp -= (int)(playerAction.hpDamage * this.enemy.GetWeekness()[playerAttackAttribute]);
            playerHp += this.player.GetActions()[actionNo].hpHeal;
            if (playerHp > this.player.GetMaxHp())
                playerHp = this.player.GetMaxHp();
            playerMp -= this.player.GetActions()[actionNo].mpCost;
            if (enemyHp <= 0)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }
            Action enemyAction = this.SelectRandomAction(enemy);
            string enemyAttackAttribute = enemyAction.attribute;
            playerHp -= (int)(enemyAction.hpDamage * this.player.GetWeekness()[enemyAttackAttribute]);
            enemyHp += enemyAction.hpHeal;
            if (enemyHp > this.enemy.GetMaxHp())
                enemyHp = this.enemy.GetMaxHp();
            enemyMp -= enemyAction.mpCost;
            if (playerHp <= 0)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            this.player.SetHp(playerHp);
            this.player.SetMp(playerMp);
            this.enemy.SetHp(enemyHp);
            this.enemy.SetMp(enemyMp);


            nextSituation = this.GetSituationNo();

			return (playerMp - playerMpOrg) * MP_CONSUMPTION_REWARD_RATE;
        }

プレイヤーとモンスターのHP,MPを足したり引いたりしてHPが0になったら死亡判定してるだけです。

どちらかが死亡するとエピソードが終了します。

エピソードを行う数は予め決まっていてそれをすべて実行し終えると終了です。

Q-learningの実行結果

各モンスターに対して100万回戦闘しました。

普通にやったら何ヶ月かかるのかわからない処理ですがPCさんなら6分17秒でやってくれます。

対戦相手がゴブリンのときの結果がこれ。

ゴブリンは通常攻撃、魔法攻撃ともに等倍のダメージを受け、毎ターン通常攻撃しか行わないただの雑魚です。

少し見にくいが2行で1つのデータで、1行目は左から「対戦相手」、「HP状態」、[MP状態]を表す。、「HP状態」は0のとき半分以上1のとき1/4以上、2のときが1/4以下を表し、「MP状態」は0のとき半分以上1のとき0以上、2のときが0です。2行目は各行動の行動価値を表していて左から通常攻撃、魔法攻撃、回復です。

だから、上から2行目までは対戦相手がゴブリンのときでHP,MPが十分ある時は3つの行動のうち一番値の大きい魔法攻撃をするのが良いことになります。

BlogRainForest.Gobrin 2 0の行をみるとHPがかなり少なくてMPが十分ある時は回復するのが良いということがわかります。

次にウイッチの場合、ウイッチは裏で通常攻撃を効きやすく(2倍)、魔法攻撃を効きにくく(半分)しています。

結果では通常攻撃の行動価値が魔法攻撃の行動価値よりも常に大きくなっているのでウィッチ相手には通常攻撃と回復しか選択しないようなAIを作ることが出来ました。

まとめ

Q-learningを用いることで、簡単なゲームAIを作ることが出来ました。

Q-learningでは状態は離散値でしたが状況や行動を連続した値で表して計算を行う方法も存在するので、機会があったら解説しようと思います。

使用したプログラム

using System;
using System.Collections.Generic;


namespace BlogRainForest
{
    class Program
    {
        static void Main(string[] args)
		{
			var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            //var ql = new QLearning();
            var rb = new RpgBattle();
            rb.MainProcess(3000000);
			sw.Stop();
			TimeSpan ts = sw.Elapsed;
            Console.WriteLine($" {sw.ElapsedMilliseconds}ms");
            Console.Write("nEndn");
            Console.Read();
        }
    }


    public class QLearning
    {
        public double[,] qValues;
        public double alpha;
        public double gamma;

        public QLearning(int sSize, int aSize, int fillValue, double alpha = 0.01, double gamma = 0.8)
        {
            this.alpha = alpha;
            this.gamma = gamma;
            this.qValues = new double[sSize, aSize];
            for (int i = 0; i < sSize; i++)
            {
                for (int j = 0; j < aSize; j++)
                {
                    this.qValues[i, j] = fillValue;
                }
            }
        }

        public void updateQ(int situationNo, int nextSituation, int actionNo, double reward, List<int> unselectableActions = null, List<int> nextUnselectableActions = null)
        {
            int maxIndex = -1;
            double maxQ = -10000000;

            this.qValues[situationNo, actionNo] = (1 - this.alpha) * this.qValues[situationNo, actionNo]
                + this.alpha * (reward + this.gamma * serachMaxAndArgmax(nextSituation, ref maxIndex, ref maxQ, nextUnselectableActions));
        }

        public int SelectActionByGreedy(int situationNo, List<int> unselectableActions = null)
        {
            unselectableActions = unselectableActions ?? new List<int>();
            int maxIndex = -1;
            double maxQ = -10000000;
            this.serachMaxAndArgmax(situationNo, ref maxIndex, ref maxQ, unselectableActions);
            return maxIndex;
        }

        public int SelectActionByEGreedy(double epsilon, int situationNo, List<int> unselectableActions = null)
        {
            Random r = new Random();
            if (r.NextDouble() < epsilon)
            {
				int action = -1;
				do
				{
					action = r.Next(this.qValues.GetLength(1));
				} while (unselectableActions.Contains(action));
				return action;
            }
            else
            {
                return this.SelectActionByGreedy(situationNo, unselectableActions);
            }
        }

        private double serachMaxAndArgmax(int situationNo, ref int maxIndex, ref double maxQ, List<int> unselectableActions = null)
		{
            unselectableActions = unselectableActions ?? new List<int>();
            for (int j = 0; j < this.qValues.GetLength(1); j++)
            {
				
				if (unselectableActions.Contains(j))
				{
					continue;
				}
                if (this.qValues[situationNo, j] > maxQ)
                {
                    maxIndex = j;
                    maxQ = this.qValues[situationNo, j];
                }
            }
            
            return maxQ;
        }

        public void PrintQValues()
        {
            var rowCount = this.qValues.GetLength(0);
            var colCount = this.qValues.GetLength(1);
            for (int row = 0; row < rowCount; row++)
            {
                for (int col = 0; col < colCount; col++)
                    Console.Write(String.Format("{0}t", this.qValues[row, col]));
                Console.WriteLine();
            }
        }
    }


    public abstract class Task
    {
        public abstract int MainProcess(int nEpisodes);
        public abstract int GetSituationSize();
        public abstract int GetActionSize();
        public abstract List<int> GetUnselectableActions(int situation);
        public abstract double CalcActionResult(int situationNo, ref int nextSituation, int actionNo);
    }

    public class RpgBattle : Task
    {
        public const int PLAYER_DEATH = 27;
        public const int ENEMY_DEATH = 28;

        public const double PLAYER_DEATH_REWARD = -1000;
        public const double ENEMY_DEATH_REWARD = 1000;
		public const double MP_CONSUMPTION_REWARD_RATE = 0;

        public Character player;
        public Character enemy;
        public List<Character> enemyList;


        public override int MainProcess(int nEpisodes)
        {
            this.player = new Player();
            this.SetEneyList();

            var q = new QLearning(
                this.GetSituationSize(),
                this.GetActionSize(),
                0
            );
            int situationNo;
            int nextSituationNo;
            int e = 0;
            while (e < nEpisodes)
            {
                //this.enemy = this.SelectRandomEnemy();
                this.enemy = this.enemyList[e % 3];
                player.RestoreHp();
                player.RestoreMp();
                enemy.RestoreHp();
                enemy.RestoreMp();
                do
                {
                    situationNo = this.GetSituationNo();
                    nextSituationNo = -1;
                    var unselectable = this.GetUnselectableActions(situationNo);
                    int actionNo = q.SelectActionByEGreedy(0.05, situationNo, unselectable);

                    double reward = this.CalcActionResult(situationNo, ref nextSituationNo, actionNo);
                    var nextUnselectable = this.GetUnselectableActions(nextSituationNo);
                    q.updateQ(situationNo, nextSituationNo, actionNo, reward, unselectable, nextUnselectable);

                } while (nextSituationNo != ENEMY_DEATH && nextSituationNo != PLAYER_DEATH);

				if (e % 1000 == 0)
				{
					Console.WriteLine();
                    Console.Write(String.Format("Progress {0:f4}%", (double) 100 * e / nEpisodes));
					Console.WriteLine();
					this.PrintQValuesWithParams(q);
				}
				e++;
            }

            Console.WriteLine();
            this.PrintQValuesWithParams(q);

            return 0;
        }

        public void PrintQValuesWithParams(QLearning q)
        {
            var rowCount = q.qValues.GetLength(0);
            var colCount = q.qValues.GetLength(1);

            int charaId = -1;
            int hpSituation = -1;
            int mpSituation = -1;

            for (int row = 0; row < rowCount; row++)
            {
                if (row >= PLAYER_DEATH)
                    continue;
                this.GetParamsBySituationIndex(row, ref charaId, ref hpSituation, ref mpSituation);
                Console.Write(String.Format("{0}t{1}t{2}", this.enemyList[charaId - 1], hpSituation, mpSituation));
                Console.WriteLine();
                for (int col = 0; col < colCount; col++)
                    Console.Write(String.Format("{0}t", q.qValues[row, col]));
                Console.WriteLine();
            }
        }

        public override int GetSituationSize()
        {
            int enemyKindCount = 3;
            int hpSituationCount = 3;
            int mpSituationCount = 3;
            //自分死亡(PLAYER_DEATH)と相手死亡(ENEMY_DEATH)状態も足す
            return enemyKindCount * hpSituationCount * mpSituationCount + 2;
        }

        public int GetSituationNo()
        {
            return 9 * (this.enemy.GetId() - 1) + 3 * this.GetHpSituation() + this.GetMpSituation();
        }

        private int GetSituationIndexByParams(int charactterId, int hpSituation, int mpSituation)
        {
            return 9 * (charactterId - 1) + 3 * hpSituation + mpSituation;
        }

        private void GetParamsBySituationIndex(int situationId, ref int characterId, ref int hpSituation, ref int mpSituation)
        {
            characterId = situationId / 9;
            hpSituation = (situationId - 9 * characterId) / 3;
            mpSituation = situationId - 9 * characterId - 3 * hpSituation;
            ++characterId;
        }

        public override int GetActionSize()
        {
            return this.player.GetActions().Count;
        }

        public override List<int> GetUnselectableActions(int situation)
        {
            if (situation == PLAYER_DEATH)
				return new List<int>();
            if (situation == ENEMY_DEATH)
				return new List<int>();
            List<int> unselectableActions = new List<int>();

            foreach (KeyValuePair<int, Action> a in this.player.GetActions())
            {
                if (a.Value.mpCost > this.player.GetMp())
                    unselectableActions.Add(a.Value.id);
            }

            return unselectableActions;
        }

        public override double CalcActionResult(int situationNo, ref int nextSituation, int actionNo)
        {

            if (situationNo == PLAYER_DEATH)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            if (situationNo == ENEMY_DEATH)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }

            int playerHp = this.player.GetHp();
            int playerMp = this.player.GetMp();
			int playerMpOrg = playerMp;
            int enemyHp = this.enemy.GetHp();
            int enemyMp = this.enemy.GetMp();

            Action playerAction = this.player.GetActions()[actionNo];
            string playerAttackAttribute = playerAction.attribute;
            enemyHp -= (int)(playerAction.hpDamage * this.enemy.GetWeekness()[playerAttackAttribute]);
            playerHp += this.player.GetActions()[actionNo].hpHeal;
            if (playerHp > this.player.GetMaxHp())
                playerHp = this.player.GetMaxHp();
            playerMp -= this.player.GetActions()[actionNo].mpCost;
            if (enemyHp <= 0)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }
            Action enemyAction = this.SelectRandomAction(enemy);
            string enemyAttackAttribute = enemyAction.attribute;
            playerHp -= (int)(enemyAction.hpDamage * this.player.GetWeekness()[enemyAttackAttribute]);
            enemyHp += enemyAction.hpHeal;
            if (enemyHp > this.enemy.GetMaxHp())
                enemyHp = this.enemy.GetMaxHp();
            enemyMp -= enemyAction.mpCost;
            if (playerHp <= 0)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            this.player.SetHp(playerHp);
            this.player.SetMp(playerMp);
            this.enemy.SetHp(enemyHp);
            this.enemy.SetMp(enemyMp);


            nextSituation = this.GetSituationNo();

			return (playerMp - playerMpOrg) * MP_CONSUMPTION_REWARD_RATE;
        }

        public void SetEneyList()
        {
            this.enemyList = new List<Character>();
            this.enemyList.Add(new Goblin());
            this.enemyList.Add(new Witch());
            this.enemyList.Add(new Grizzly());
        }

        private Character SelectRandomEnemy()
        {
            Random rnd = new Random();
            int ri = rnd.Next(this.enemyList.Count);
            return this.enemyList[ri];
        }

        private Action SelectRandomAction(Character character)
        {
            Random rnd = new Random();
            List<int> KeyList = new List<int>(character.GetActions().Keys);
            int ri = rnd.Next(KeyList.Count);
            return character.GetActions()[KeyList[ri]];
        }

        private int GetHpSituation()
        {
            if (this.player.GetMaxHp() / 2 < this.player.GetHp())
            {
                return 0;
            }
            else if (this.player.GetMaxHp() / 4 < this.player.GetHp())
            {
                return 1;
            }
            else
            {
                return 2;
            }
        }

        private int GetMpSituation()
        {
            if (this.player.GetMaxMp() / 2 < this.player.GetMp())
            {
                return 0;
            }
            else if (10 <= this.player.GetMp())
            //else if (this.player.GetMaxMp() / 4 < this.player.GetMp())
            {
                return 1;
            }
            else
            {
                return 2;
            }
        }
    }


    public abstract class Character
    {
        private string name;
        private int id;
        private int maxHp;
        private int maxMp;
        private int hp;
        private int mp;
        private Dictionary<int, Action> actions;
        private Dictionary<string, double> weeknesses;

        public Character()
        {
            this.Init();
        }

        private void Init()
        {
            this.name = this.SetName();
            this.id = this.SetId();
            this.maxHp = this.SetMaxHp();
            this.maxMp = this.SetMaxMp();
            this.hp = this.maxHp;
            this.mp = this.maxMp;
            this.actions = this.SetActions();
            this.weeknesses = this.SetWeekness();
        }

        private string SetName()
        {
            return this.GetType().Name;
        }

        public abstract int SetId();
        public abstract int SetMaxHp();
        public abstract int SetMaxMp();

        public void SetHp(int hp)
        {
            this.hp = hp;
        }

        public void SetMp(int mp)
        {
            this.mp = mp;
        }

        public abstract Dictionary<int, Action> SetActions();
        public abstract Dictionary<string, double> SetWeekness();

        public string GetName()
        {
            return this.name;
        }

        public int GetId()
        {
            return this.id;
        }

        public int GetHp()
        {
            return this.hp;
        }

        public int GetMp()
        {
            return this.mp;
        }


        public int GetMaxHp()
        {
            return this.maxHp;
        }

        public int GetMaxMp()
        {
            return this.maxMp;
        }

        public Dictionary<int, Action> GetActions()
        {
            return this.actions;
        }

        public Dictionary<string, double> GetWeekness()
        {
            return this.weeknesses;
        }

        public void RestoreHp()
        {
            this.hp = this.maxHp;
        }

        public void RestoreMp()
        {
            this.mp = this.maxMp;
        }

    }

    public class Player : Character
    {
        public Player() : base()
        {

        }

        public override int SetId()
        {
            return 0;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 100;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

    public class Goblin : Character
    {
        public Goblin() : base()
        {

        }

        public override int SetId()
        {
            return 1;
        }

        public override int SetMaxHp()
        {
            return 140;
        }

        public override int SetMaxMp()
        {
            return 0;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

    public class Witch : Character
    {
        public Witch() : base()
        {

        }

        public override int SetId()
        {
            return 2;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 200;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 2.0);
            weeknesses.Add("magic", 0.5);
            return weeknesses;
        }
    }

    public class Grizzly : Character
    {
        public Grizzly() : base()
        {

        }

        public override int SetId()
        {
            return 3;
        }

        public override int SetMaxHp()
        {
            return 240;
        }

        public override int SetMaxMp()
        {
            return 0;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.strongAttack.id, ActionTable.strongAttack);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 2.0);
            return weeknesses;
        }
    }

    public class Action
    {
        public int id;
        public int hpDamage;
        public int hpHeal;
        public int mpCost;
        public string attribute;

        public Action(int id, int hpDamage, int hpHeal, int mpCost, string attribute, ref int count)
        {
            this.id = id;
            this.hpDamage = hpDamage;
            this.hpHeal = hpHeal;
            this.mpCost = mpCost;
            this.attribute = attribute;
            ++count;
        }
    }

    static class ActionTable
    {
        public static int count;
        public static Action normalAttack;
        public static Action magicAttack;
        public static Action heal;
        public static Action strongAttack;

        static ActionTable()
        {
            count = 0;
            normalAttack = new Action(count, 10, 0, 0, "physical", ref count);
            magicAttack = new Action(count, 15, 0, 10, "magic", ref count);
            heal = new Action(count, 0, 40, 10, "magic", ref count);
            strongAttack = new Action(count, 30, 0, 0, "physical", ref count);
        }
    }
}

GPUを使って無線LANをクラックする話・ボトルネック発見編

データセンターで偶然出会った、キーボード・No.1さんです。ナンバーワンですって。

まさか、こんなところでキーボード界の頂点に出会えるとは。偶然てのは、すごいですね。

キーボードを見る目のないわたしには、この方を見てもその凄さ−《王者の風格》、とでも言うべきものでしょうか−そういったものは、感じ取れませんでした。「能ある鷹は爪を隠す」ってやつなんでしょうか。いやぁ、御見逸れ致しました。わたくしにはキーボードの才能が無いのでしょう。わたしはせいぜい、指でキーボードぺちぺちする身で一生甘んじていようと思います。

キーボードのNo.1ってどうやって決めるんだろうとか、次の世界大会はいつなのかとか、聞けば良かったな。サインももらえば良かったかも。

…えー、もちろん嘘で、ただの通し番号です。データセンターにはたくさん共用のキーボードがあって空いてるものを番号の小さいものから貸してもらえるんですが、同時に作業する人は居ないのでいつもだいたいこのキーボードを貸してもらって作業しています。でも不思議かな、みんなこのキーボードばっかり使ってるはずなのに、「キーボードNo.10」とかの方がボロボロな感じがします。…もしかして、やっぱ世界1位《ザ・トップ・オブ・キーボード》だったのか?

いや…まさかね。

前回までのPyritなのですよ

えー、何の話でしたっけ。あーそうそう。無線LANのパスワード認証方式WPA2-PSKをPyritでクラックしてたんだけど、WPA2の仕様書が読めないから諦めて直接Pyritのソースを読んでいたんでしたね。

えー、何の話でしたっけ。あーそうそう。無線LANのパスワード認証方式WPA2-PSKをPyritでクラックしてたんだけど、WPA2の仕様書が読めないから諦めて直接Pyritのソースを読んでいたんでしたね。

簡単におさらいです:

  • IteratorCrackerというのがいて
  • 辞書ファイルから読んだパスワードのリストを、Iteratorがresultsにして
  • Crackerがresultsを検証して「そのパスワード、あたりっ!」「はずれっ!」と判定する
  • CUDAを使っているのはIteratorだけ。CrackerはCPUでしか動かない。

というのを前回ソース読んで確認したんでした。

そもそも何を測っているのかを把握するのですよ

太古の昔に書いた最初の記事では、Pyritの「benchmark」というコマンドを実行してCPUと比較してみたり、GPU同士で比較して「Tesla V100はGTX1080よりめっちゃ高くて性能いいはずなのに大差ない…」とか嘆いていたわけですが、そもそもこれは何を測っていたのでしょうか。前回多少なりともソースコードを読んだ事により、このような多少深まった疑問が生まれるわけですな。前回見た限り、Crackerも二種類あって、データやコマンドラインフラグによって変わるんですよね。その辺の条件は?

…というわけで、早速読んでみましょう。pyritコマンドのサブコマンドの実装は全部ルートにあるpyrit_cli.pyに置いてありまして、コマンド名と関数名はすべて一致しています。つまり、benchmarkコマンドもbenchmark関数に置いてあります。大変わかりやすい。

ちょっと長いですが、多少はしょりつつ載せます:

    def benchmark(self, timeout=45, calibrate=10):
# ... 略 ...
# ダミーの仕事をなげまくる仕事
            t = time.time()
            perfcounter = cpyrit.util.PerformanceCounter(timeout + 5)
            while time.time() - t < timeout:
                pws = ["barbarbar%s" % random.random() for i in xrange(bsize)]
                cp.enqueue('foo', pws)
                r = cp.dequeue(block=False)
# ... 略 ...
# CPUの結果を表示する
            for i, core in enumerate(cp.cores):
                if core.compTime > 0:
                    perf = core.resCount / core.compTime
                else:
                    perf = 0
                if core.callCount > 0 and perf > 0:
                    rtt = (core.resCount / core.callCount) / perf
                else:
                    rtt = 0
                self.tell("#%i: '%s': %.1f PMKs/s (RTT %.1f)" % \
                            (i + 1, core.name, perf, rtt))
# ... 略 ...
# GPUの結果を表示する
            for i, CD in enumerate(cp.CUDAs):
                if CD.compTime > 0:
                    perf = CD.resCount / CD.compTime
                else:
                    perf = 0
                if CD.callCount > 0 and perf > 0:
                    rtt = (CD.resCount / CD.callCount) / perf
                else:
                    rtt = 0
                self.tell("#%i: '%s': %.1f PMKs/s (RTT %.1f)" % \
                          (i + 1, CD.name, perf, rtt))
# ... 略 ...

cpyrit.cpyrit.CPyrit() as cp というのはIteratorが依存している、パスワードを入れるとresultsというリストが出て来るモジュールでした(で、これをCrackerがチェックする)。

すぐに気がつくのは、CPUやCUDAごとにベンチマークしてるわけではないことです。cp.enqueueとして「パスワード計算してくれや」とお願いすると、cpくんが代理店となって、実際にCPU、CUDA(、OpenCL)のどれで計算するかを決めるようになっています。で、あとで集計するときにcpくんに「ところでTesla使ったのってどれくらい?」って聞いて、その結果をベンチの結果としてまとめる、と。

うーん。APIとしてはバックエンドが隠蔽されてて、いい感じだと思います。でも、これで本当に「公平」にベンチマークできているのかは、若干怪しい感じがするんですが…。

とりあえず。前回、「CPUだけで走るCrackerがボトルネックとなってbenchmarkでTeslaがあんまり速くなかったのでは?」という仮説を立てましたが、それは否定されました。だって、見ての通り、Crackerは走らないからです。もちろん、「このbenchmarkでは」であって、実際にパスワードを検索する時はCrackerも走らせて正しいパスワードかどうかチェックするので、Crackerがボトルネックとなる可能性は残ります。

綺麗なCUDAプロファイラーでも眺めるのですよ

なんか手詰まり感があるので、ここで一旦ソースコードの調査を打ち切ってプロファイラーで遊んでみましょう。

というのも。

ベンチマーク取ってる間、nvidia-smiコマンドを打つとこんな感じで消費電力が見れるわけですが:

+-----------------------------------------------------------------------------+
| NVIDIA-SMI 390.30                 Driver Version: 390.30                    |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  Tesla V100-PCIE...  Off  | 00000000:3D:00.0 Off |                    0 |
| N/A   55C    P0    43W / 250W |      0MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   1  Tesla V100-PCIE...  Off  | 00000000:3E:00.0 Off |                    0 |
| N/A   57C    P0    45W / 250W |      0MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   2  GeForce GTX 108...  Off  | 00000000:B1:00.0 Off |                  N/A |
| 28%   50C    P0    60W / 250W |      0MiB / 11178MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   3  GeForce GTX 108...  Off  | 00000000:B2:00.0 Off |                  N/A |
| 32%   56C    P0    57W / 250W |      0MiB / 11178MiB |      2%      Default |
+-------------------------------+----------------------+----------------------+

+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
|  No running processes found                                                 |
+-----------------------------------------------------------------------------+

pyrit benchmarkを実行している間も、このアイドル時の画面と正直消費電力があんまり変わらなくて、ごくごくたまにGPUのどれか1つがちょっと電気を使うようになって、また戻る…そんな感じなんですよ。

+-----------------------------------------------------------------------------+
| NVIDIA-SMI 390.30                 Driver Version: 390.30                    |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  Tesla V100-PCIE...  Off  | 00000000:3D:00.0 Off |                    0 |
| N/A   54C    P0    48W / 250W |    427MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   1  Tesla V100-PCIE...  Off  | 00000000:3E:00.0 Off |                    0 |
| N/A   56C    P0    51W / 250W |    427MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   2  GeForce GTX 108...  Off  | 00000000:B1:00.0 Off |                  N/A |
| 44%   74C    P2   198W / 250W |    167MiB / 11178MiB |     36%      Default | ←一時的に使用率が上がった(でもたった36%??)
+-------------------------------+----------------------+----------------------+
|   3  GeForce GTX 108...  Off  | 00000000:B2:00.0 Off |                  N/A |
| 48%   79C    P2    85W / 250W |    161MiB / 11178MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+

+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
|    0     96620      C   /home/psi/src/Pyrit/.env/bin/python          416MiB |
|    1     96620      C   /home/psi/src/Pyrit/.env/bin/python          416MiB |
|    2     96620      C   /home/psi/src/Pyrit/.env/bin/python          157MiB |
|    3     96620      C   /home/psi/src/Pyrit/.env/bin/python          151MiB |
+-----------------------------------------------------------------------------+

CPU(htop)もこんな感じで全コア使い切ってない感が否めない…。

でも、それっておかしいですよねぇ?上で読んだように、CPUやGPUごとじゃあなくて、全部に対して仕事を投げまくってるので、理想的な状況としては全GPUと全CPUがTDPギリギリに張り付いてないとおかしいはずなんです。で、せっかく静かにしたファンが全力で回るようになると。ちなみにわたくしリモートで勤務するバーチャル実在する架空のプログラマですので、音のほうは確かめられません。フヒヒ。

というわけで、まずは本当にGPUが遊んでいるのかどうか、プロファイラーで調べられないか試してみます。

PythonとC言語とCUDAが組み合わさった現代のバベルの塔としか言いようがないこの複雑極まりないシステムですが、DeepLearningで非常によくある組み合わせだからかツール自体はかなり整備されておりまして(そしてDeepLearningの場合はさらに統計的機械学習の難しい理論や巨大なデータがその塔の上に積み上がっていく)、こんな感じで非常に簡単にプロファイルできるようになっています:

# nvidia-profilerは別パッケージらしい
sudo apt install nvidia-profiler

# 測定したいコマンドの前にnvprof -o <出力>.nvvpをつけるだけ。すっごいかんたん!
nvprof -o profile.nvvp pyrit benchmark_long

しかもこのprofile.nvpの結果を見るためのVisual Profilerは、なんとmacでも動きます!リモートのLinuxでももちろん動きます!GPUがあってもなくても!…資本主義ってこえぇなぁ。

nVIDIAのサイトからCUDAのmac版をインストールして、DriverとToolkitとSampleのうち、Toolkitだけインストールします。DriverもインストールできるってことはGeForce積んでるmacもあるんだな…。

で、/Developer/NVIDIA/CUDA-9.2/bin/nvvp (macの場合。CUDAバージョンによって違う)を実行して、openからscpか何かで持ってきたprofile.nvvpを開きます。結果はこんな感じになりましたとさ:

めっちゃスカスカやんけー!

この茶色とか青い棒が出てるところが「計算したで」「CPUとGPUの間でデータのやりとりしたで」を表しているので、このスカスカ具合は、…要するに「GPU全然使えてません」ということになります。つまり、nvidia-smiから雑に考えた仮説は正しかったってこと。

もうすこし拡大して見て行くと、だいたい1秒に一回ぐらいGPUが叩き起こされて、0.06〜0.08秒だけ起こされてまた寝てます。正直ちょっと羨ましい!…いや、そんな頻繁にちょっとだけ起こされるのもやだな。

最初、GPUとCPUの間でパスワードのデータをやりとりするところがボトルネックになるのかなぁ、と予想したりもしていましたが、それは否定されました。計算している80ミリ秒とかに対して、データの転送は0.1ミリ秒程度です。誤差。

ベンチというのは分母と分子が大事なのですよ

まだあわてるような時間じゃない

仮にほとんどGPUを使っていないとしても、ベンチマークの値の信憑性にただちに影響があるわけではありません。

元のソースコードに戻りましょう:

            for i, CD in enumerate(cp.CUDAs):
                if CD.compTime > 0:
                    perf = CD.resCount / CD.compTime
                else:
                    perf = 0

「ベンチマーク」と英語で横文字を使ってみるとなんとなく知的でイケてる感じですが、要するに「仕事率」を測っておるわけです。「やった仕事」を「掛かった時間」で割ってるだけ。

この「掛かった時間」が実際にはどこからどこまでなのかが問題なわけです。

仮に、GPUが1秒間に80ミリ秒しか仕事してないとしても、「掛かった時間」も80ミリ秒なら、その「ベンチマーク」は「GPUの計算の仕事率」を測れていることになります。もし仮にそうなら、GTX1080とTeslaはパスワードクラックという仕事では、そんなに実力に差がないという事になるでしょうね。Pyritに対しては「もっとGPUに仕事割り当ててあげて」と言う事になります。

じゃあ、そうじゃなかったら?…それは、GPUを働かせるために必要な他の仕事の方にばかり時間を取られていて、GPUをうまく動かせていない、という結論が出てきます。例えていうなら、30分の大学院のミーティングに出るために2時間電車乗ってるような。…はぁ…。もし仮にそうなら、ベンチマークの結果はGPUそのものの性能差はあまり反映できていない、という事になるでしょうね。もっといえば、その「余分な仕事」はCPUを使ってるはずなので、このCPUとGPUを同時に走らせるベンチマークは、公平でないことになります。

ソースコードをちょっと書き換えて、この分母であるCD.compTime も表示するようにしましょう。

した結果がこんな感じ:

#1: 'CPU-Core (SSE2/AES)': 528.7 PMKs/s (RTT 2.7) compTime=24
#2: 'CPU-Core (SSE2/AES)': 585.8 PMKs/s (RTT 2.8) compTime=31
#3: 'CPU-Core (SSE2/AES)': 559.6 PMKs/s (RTT 2.9) compTime=35
#4: 'CPU-Core (SSE2/AES)': 537.1 PMKs/s (RTT 2.7) compTime=32
#5: 'CPU-Core (SSE2/AES)': 566.9 PMKs/s (RTT 3.0) compTime=27
#6: 'CPU-Core (SSE2/AES)': 488.4 PMKs/s (RTT 3.0) compTime=33
#7: 'CPU-Core (SSE2/AES)': 569.0 PMKs/s (RTT 3.1) compTime=31
#8: 'CPU-Core (SSE2/AES)': 506.9 PMKs/s (RTT 2.9) compTime=29
#9: 'CPU-Core (SSE2/AES)': 520.3 PMKs/s (RTT 2.8) compTime=19
#10: 'CPU-Core (SSE2/AES)': 579.7 PMKs/s (RTT 2.8) compTime=28
#11: 'CPU-Core (SSE2/AES)': 543.4 PMKs/s (RTT 3.1) compTime=31
#12: 'CPU-Core (SSE2/AES)': 580.9 PMKs/s (RTT 3.0) compTime=33
#13: 'CPU-Core (SSE2/AES)': 569.9 PMKs/s (RTT 2.9) compTime=37
#14: 'CPU-Core (SSE2/AES)': 496.3 PMKs/s (RTT 2.9) compTime=23
#15: 'CPU-Core (SSE2/AES)': 546.1 PMKs/s (RTT 2.8) compTime=34
#16: 'CPU-Core (SSE2/AES)': 564.5 PMKs/s (RTT 2.8) compTime=36
#17: 'CPU-Core (SSE2/AES)': 538.7 PMKs/s (RTT 2.9) compTime=31
#18: 'CPU-Core (SSE2/AES)': 621.0 PMKs/s (RTT 2.8) compTime=25
#19: 'CPU-Core (SSE2/AES)': 527.8 PMKs/s (RTT 2.8) compTime=31
#20: 'CPU-Core (SSE2/AES)': 492.7 PMKs/s (RTT 2.8) compTime=34
#21: 'CPU-Core (SSE2/AES)': 532.0 PMKs/s (RTT 2.8) compTime=28
#22: 'CPU-Core (SSE2/AES)': 558.4 PMKs/s (RTT 2.9) compTime=29
#23: 'CPU-Core (SSE2/AES)': 548.8 PMKs/s (RTT 2.8) compTime=31
#24: 'CPU-Core (SSE2/AES)': 528.6 PMKs/s (RTT 2.9) compTime=32
#25: 'CPU-Core (SSE2/AES)': 594.7 PMKs/s (RTT 2.8) compTime=28
#26: 'CPU-Core (SSE2/AES)': 508.1 PMKs/s (RTT 2.8) compTime=33
#27: 'CPU-Core (SSE2/AES)': 534.2 PMKs/s (RTT 2.9) compTime=32
#28: 'CPU-Core (SSE2/AES)': 545.9 PMKs/s (RTT 3.1) compTime=31
#29: 'CPU-Core (SSE2/AES)': 543.0 PMKs/s (RTT 3.0) compTime=39
#30: 'CPU-Core (SSE2/AES)': 550.1 PMKs/s (RTT 2.6) compTime=29
#31: 'CPU-Core (SSE2/AES)': 595.8 PMKs/s (RTT 3.1) compTime=31
#32: 'CPU-Core (SSE2/AES)': 581.9 PMKs/s (RTT 2.7) compTime=30
#33: 'CPU-Core (SSE2/AES)': 537.9 PMKs/s (RTT 2.9) compTime=29
#34: 'CPU-Core (SSE2/AES)': 566.2 PMKs/s (RTT 3.0) compTime=30
#35: 'CPU-Core (SSE2/AES)': 563.1 PMKs/s (RTT 2.6) compTime=24
#36: 'CPU-Core (SSE2/AES)': 590.0 PMKs/s (RTT 2.7) compTime=32
#37: 'CPU-Core (SSE2/AES)': 581.8 PMKs/s (RTT 2.7) compTime=27
#38: 'CPU-Core (SSE2/AES)': 566.3 PMKs/s (RTT 2.7) compTime=33
#39: 'CPU-Core (SSE2/AES)': 516.1 PMKs/s (RTT 3.2) compTime=28
#40: 'CPU-Core (SSE2/AES)': 561.8 PMKs/s (RTT 2.9) compTime=35
#41: 'CPU-Core (SSE2/AES)': 542.7 PMKs/s (RTT 2.9) compTime=29
#42: 'CPU-Core (SSE2/AES)': 577.9 PMKs/s (RTT 2.9) compTime=29
#43: 'CPU-Core (SSE2/AES)': 586.3 PMKs/s (RTT 3.0) compTime=33
#44: 'CPU-Core (SSE2/AES)': 523.4 PMKs/s (RTT 3.0) compTime=30
#45: 'CPU-Core (SSE2/AES)': 526.7 PMKs/s (RTT 2.9) compTime=32
#46: 'CPU-Core (SSE2/AES)': 505.5 PMKs/s (RTT 2.9) compTime=32
#47: 'CPU-Core (SSE2/AES)': 567.8 PMKs/s (RTT 2.7) compTime=24
#48: 'CPU-Core (SSE2/AES)': 521.5 PMKs/s (RTT 2.9) compTime=32
CUDA:
#1: 'CUDA-Device #1 'Tesla V100-PCIE-16GB'': 113061.9 PMKs/s (RTT 0.4) compTime=11.3
#2: 'CUDA-Device #2 'Tesla V100-PCIE-16GB'': 120956.8 PMKs/s (RTT 0.4) compTime=13.1
#3: 'CUDA-Device #3 'GeForce GTX 1080 Ti'': 94154.2 PMKs/s (RTT 0.4) compTime=13.3
#4: 'CUDA-Device #4 'GeForce GTX 1080 Ti'': 96664.7 PMKs/s (RTT 0.5) compTime=16.4

45秒のベンチに対して、10秒程度。たしかにCPUに比べてかなり短いですが、1秒中80ミリ秒、つまり8%しか使ってないことを考えるとあまりに長いです。Pyritくんが口ではGPUで実行している!といいつつ、実はそうでない部分がかなり占めていて、GPUを全然使い切れていない可能性はやはりかなり高い、と考えてよいでしょう。

もう一つ。CPUもGPUも、どっちも45秒のベンチマークのうち、けっこうの部分遊んでいます。htopであんまりコアを使い切ってない気がしたのもここで説明がつきました。これはどう解釈すればいいのかといえば…たぶん、ダミーのパスワードの生成が、追いついてないんじゃないでしょうか。CPUやGPUがすぐパスワードを処理して「もっとくれや!」って言うけれど、

["barbarbar%s" % random.random() for i in xrange(bsize)]
としてパスワードをどんどん作る処理が追いついてない。

月刊Pyrit、今月のまとめなのですよ

  • benchmarkはパスワードクラックの一部の処理しか測ってない
  • GPUもCPUも遊びまくっている
  • nVIDIAのプロファイラきれい(明らかにEclipse製)

さぁて、来月の月刊Pyritは何なのですよ?

いきあたりばったりで書いてるのでどうなるかはわかんないんですけど、このボトルネックたちと遊んでいきましょう。いいっすね、なんかやっと技術ブログっぽくなってきた。…台風の低気圧で今日はテンションがひくいのですよ。みなさまも強い風に飛ばされないように気をつけて〜。

そう言えば先月書いた正解のパスワード、検閲されちゃいましたね。「xxxxxxxxxxx」ですって、いったいどんな文字列だったんでしょう、前後の文脈から想像をかき立てられちゃいますねぇ。「えっちなことば」って昔こんな感じで生まれたのかな。フヒヒ。

GPUサーバーを静かにする話

はじめに

弊社にテスト用のGPUマシンがいらっしゃったわけですが、この評判がすこぶる・・・悪い。

とてーもお高いサーバーであるはずなのに、とても評判が悪い。

このサーバーはNVIDIAさんのライセンスのおかげでデータセンターに置けずオフィスに置いてあるのです。

があまりにもうるさすぎて、執務スペースを追い出されて廊下というか玄関?に置いてあります。

今回はGPUサーバーをどうにかしてみんなに受け入れてもらった話をしましょう。

現状把握をしよう

騒音を計測してみましょう。

1.起動した瞬間

BAKUON!

起動時はファンが前回になるため一番うるさいです。にしても100デシベルと言えば、自動車のクランクション等に相当し、聴覚機能に異常をきたすレベルだそうな。起動後落ち着いた状態(アイドル時)

2. 起動後落ち着いた状態(アイドル時)

騒々しい街頭や掃除機に相当するレベルだそうな。

3. 起動後落ち着いた状態@会議室

扉を1枚隔てた会議室での測定結果。会議室も会議ができないほどではないですが、余裕で音が聞こえます。

4. 執務スペースの社長の机

執務スペースは扉1枚隔てているものの、余裕で聞こえる、というかうるさい。社長の席がGPUサーバーに一番近いので、私の席だともう少し静か。60デシベルで、時速40kmで走行する車の車内に相当する騒音だそうな。

5. 起動後落ち着いた状態@オフィスの外の廊下

外でも余裕で聞こえる。これはそのうちビルの管理会社に怒られそう。

6. 起動後落ち着いた状態@オフィスの外のエレベーターホール

エレベーターホールまで行けばあまり気にならない。

が相変わらず聞こえる。

やはりなんとかせねば。

サーバーの設定を見直して静かにしよう

ところがこのサーバー、BIOSやUEFIにFANに関する設定がないんだなー。

じゃあどうするんだというとIPMIから設定する感じ。

サーバーらしく、大量のセンサーが存在。これらのセンサー値とファンを連動させることができます。

初期設定は最初から50%ぐらいの力でファンが回っていて、負荷がかかるとすぐに75%ぐらいまで上がるように設定されています。

が、廃棄はかなり涼しく、正直過剰冷却感否めず。

そこで以下のように変更してみます。

ある瞬間までは頑張って耐えますが、温度が上がってくると突然ファンを全開にして温度を下げる方針です。

本当はもう少し緩やかにファン回転数を上げて言ってもいいんですが、熱で壊れたりしたら嫌なのでコンサバに行きます。

さて結果はどうなりましたでしょうか。

結果発表

起動した瞬間はどちらも全力で動くので割愛します。

起動後落ち着いた状態

おおお、劇的に静かになりました。

起動後落ち着いた状態@会議室

ここまで来るとほぼ聞こえません。

起動後落ち着いた状態@オフィス街の廊下

こちらもほとんど聞こえません。というかサーバー自体より騒音値が上なので、廊下自体の騒音の方がうるさい感じです。

エレベーターホールは聞こえなかったのと、執務室は空気清浄機の音の方が支配的だったので割愛します。

番外編

弊社のデータセンターにも同じ機種のGPUがないものがあったので、ファンのチューニングをしてみました。

騒音はデータセンター自体元々うるさいので測定していませんが、アイドル時の消費電力が420W→160Wに減少しました。。。この機種の初期設定がひどすぎる説・・・。

結論

サーバーも設定次第で静かにすることが可能です。諦めずにチューニングしましょう。