by shigemk2

当面は技術的なことしか書かない

筑波大学のスーパーコンピュータを利用していろいろした話 #kernelvm

勉強会

@n_IMRC

案

  • initスクリプトを書いてRaspberryPiのOSをUSB HDDから起動した話
  • framebufferをpngやjpeに変換するプログラムを書きmjpg streamer経由でストリーミング出来るようにした話

→n次魔方陣のプログラムを書いて並列化した話

並列計算

  • 複数のCPUやスレッドで分散して処理
  • 実行時間の短縮が目的

1台のコンピュータを複数台で処理することで実行時間を短縮

環境

  • 数値計算ではMPI OpenMP pthreadなど高レベルライブラリ
  • XcalableMPを開発中

スーパーコンピュータ

  • 多少高性能なコンピュータの集まり

  • HA-PACSとCOMAを運用(T2K-Tsukubaが運用されていたのが去年)

  • quad-core AMD Opteron

  • NVIDA M2090(Fermi)
  • Intel Xeon Phi

学際共同利用

  • 申請に通れば1年間無料でスパコンを使える
  • 5TBのディスクスペース
  • リモートで使うにはすごく高スペック
  • 研究員、大学生、高専、センター長が認めた者

学際共同利用での成果

  • n次魔方陣全解数え上げプログラムの並列化と性能解析
  • 数え上げプログラムのメニーコア化

n次魔方陣全解数え上げプログラムの並列化と性能解析

整数問題 n次魔方陣全解数え上げ を超並列処理で行う

縦n横nマス

魔方陣 - Wikipedia

|:--|:--|:--|:--|:--| |1|7|13|19|25| |18|24|5|6|12| |10|1|17|23|4| |22|3|9|15|16| |14|20|21|2|8|

6次魔方陣の総数 1.8*1019

1クロック

  • nの増大に伴い、階乗的に増加する探索空間を絞る
  • n=6は困難なので、n=5に修正

計算環境

  • 32ノード上で512スレッド
  • 最大連続実行時間は24時間

アルゴリズムの改良

鏡像性(裏返しても結果は同じ) 途中解(n=5のとき、4つの数が決まれば最後の数も決まる)

から計算量を絞る

  • 5次魔方陣の場合、入る最大数は25
  • 部分解からの探索の計算量は事前に求められない→動的タスクスケジューリング
  • master-worker型並列処理が有効

http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0

並列処理 ポイント

  • 25マス中D個まで埋まった状態でworkerに分配
  • worker数が大きいとmasterの分配処理が大きくなり小さいとmasterはidleになりやすい

これらを踏まえて、worker数とDの関係の最適値を計算

  • masterはD番目のマスまで総当りし、1つの暇なworkerに渡す
  • workerは次のパターン配布を待つ

D=3は処理時間が長く、4 5 6 7とがくんと下がった

D=3とD=6の比較

  • D=3では実行時間にばらつきが多すぎて、配る問題の粒度が粗すぎる
  • D=6 D=8だと実行時間が一定している

6次魔方陣への拡張

今回のアルゴリズムをそのまま使うと実行に150兆年かかってしまう

数え上げプログラムのメニーコア化

Intel Xeon Phi

  • x86のISAと互換性がある
  • Linux動く
  • 60コア以上

x86と互換性あるから今までのアプリケーションをそのままオフロードできるね 1コアあたりの性能はXeon

アプリケーションは100スレッドオーダーでスケールすること(えっ)

  • 1コアあたりの性能はXeonより低い
  • 倍精度のベクトル演算ではない

まとめ

  • 整数問題なのでベクトル演算は含まない
  • XeonPhiは整数問題に向いていない

追記

総当りARM64 #kernelvm

勉強会

@7shi

ARM64

  • 64bit ARMは最後発のISA
  • ISAはややこしいので以後ARM64とする
  • 実用性と美しさを兼ね備えているらしい

計画

  • 逆アセンブラは入手可能 binutilsを--target=aarch64-elfでビルド
  • ARM64の命令は4バイト固定長(43億通り)

調査

  • 00000000-FFFFFFFFのバイナリを作って逆アセンブル
  • 逆アセンブル結果は200GB
  • バイナリ16GB
  • Athlonなので遅い

データを削る

  • 逆アセ結果からデータを削る
  • 約7割が未定義なので削る
  • 未定義データを削ると35GBに縮小

パターン抽出

  • ニーモニックごとにパターンを抽出
  • ニーモニック単位のビット部はなさそう
  • 逆アセンブラを作るのは難しそう

パターン抽出

(分岐)

分岐はARM32で最上位にあった条件ビットと同じパターンが最下位にある

b.eq b.ne b.cs b.cc b.le b.al b.nv

(オペランド)

(スクリプトはF#で)

適当に書いたらあまり高速化しなかった

組み合わせ爆発！

31番レジスタあたりにアタリをつけてみる

31番レジスタは状況に応じて別物になる アドレッシングでは必ず[sp] spは以下の10命令にしか現れない

add adds and cmn cmp eor mov orr sub subs

PowerPCにも似た仕様がある

31番レジスタ

ゼロレジスタがデフォルトで、一部の命令に限ってspが出てくる

どこかに判別ビットがあるはずだが、統一ルールみたいなのはない

付加的な操作

ARMの伝統で一部の命令はオペランドに対してシフトや拡張の操作ができる

これと31番レジスタとの合わせ技が組み合わせ爆発の原因

課題

Live Migration by BitVisor #kernelvm

勉強会

http://www.atmarkit.co.jp/news/201209/27/bitvisor.html

PCI-Passthroughしつつライブマイグレーションを実現 OSによるライブマイグレーション

コンテナによるライブマイグレーション

BitVisorのアーキテクチャ

ほとんどのI/Oはパススルー

高い性能をインスタンスへ提供 インスタンス上で動作するOSに特別な制約を課さない

物理ハードウェアの状態を取得して復元

書き込み専用の状態を取得 OSがWOに"20"を書き込む

読み出し専用の状態を復元

VMMがデバイスを操作して間接的に状態を復元 デバイスの仕様にもとづいて操作

実装

I/Oデバイスについてだけ話す

PIC PIT

PIOをフック

REALTEK(問題児)

カニさんのディスクリプタポインタ

どっかのレジスタにポインタを格納したレジスタがあるよね…？

なかった

ポインタはレジスタとして存在しない

内部ポインタはどこにいるのか

Rxディスクリプタ

Rxの内部ポインタの取得

Txは送信依頼前にスキャン

NICの送信ポインタの復元

送信ポインタ=次に送るべきバッファを指すオフセット パケットを1つ送るごとにインクリメントする

性能評価

スループットはベアメタルと同じ レイテンシーはベアメタル+60us ダウンタイムは2.5sくらい

BitVisorでライブマイグレーションするとそれなりに性能が出そう

ラップトップ電磁リレー #kernelvm

勉強会

電磁リレーの人 KOBA789

経緯

シミュレーターをやったので実機つくろう

  1. 実機
  2. 妥協 GUIエディタ シミュレータ
  3. 既存エディタ GUIシミュレータ
  4. 既存エディタ CLIシミュレータ
  5. 未完成

学び

Eeschema

  • KiCadについてる回路図エディタ
  • 操作感が謎
  • オープンソース
  • クロスプラットフォーム(大嘘)
  • 残像が残るなどMacだとポンコツ
  • 謎仕様

詳解Eeschemaファイルフォーマット

  • Schemeのソースコードではない
  • 行ベースの構造化も中途半端
  • パーサは実装
  • 最新版のバイナリが吐くやつはVersion1なのに、Version2の記述がどこにもないEnglish Wikipedia

libファイル

  • パーツライブラリ

schファイルの糞なところ

結線情報は直線の交点を幾何学的計算でもとめるしかない

ネットリスト

  • 部品のピンの結線をあらわすデータ
  • 回路図の構造は持っていない
  • 最小のデータしか出力出来ない

出力

  • 出力すると、中間形式はXMLなのに、S式
  • プラグインの実態は標準入出力するコマンド
  • catでXMLが取れる
  • Windowsだとcatがなかった

OSb: OSv on BitVisor #kernelvm

勉強会

BitVisor(VMM)

薄いVMMで、物理デバイスがぶら下がっている OSvも、薄い

OSv on BitVisor

カバーガラスとスライドガラス

OSv code readingをやってみて、ブートプロセスを見る

/scripts/run.py

Pythonスクリプト

このスクリプトを動かすと、VMMの上でOSvが動く

/scripts/run.py→Image Update→PXE Boot→IPMI→NetworkBoot

ACPI workaround

物理マシンが遅いので起動が2分かかる

パフォーマンスOSb vs OSv

OSb 20.75 OSv 21

NIC埋め込み

  • ちょっとごまかしてVirtioNICに見せかけることをやる
  • Faking IDs

Faking BARs

PRO/1000 IO spaceに入れる

NICを偽装する capabilityを偽装する

まとめ

  • OSv on BitVisorでブート
  • NICを偽装

ALSA=仮想マシン #kernelvm

勉強会
  • Ubuntu Japanese Team

  • ミラクル・リナックス

  • ALSAのドライバこみったになった

  • 420パッチを投稿していた

  • 前半

  • ALSA
  • 後半

  • 進捗

  • Advanced Linux Sound Architecture

  • Linuxのサウンドサブシステム(音声入出力のための周辺デバイス

  • 接続バス PCI

  • デバイスはこんな感じ。
  • MIDI入出力などをカバー
  1. 低レベルの機能にまつわる負担からプログラマを解放
  2. ハードウェアの抽象化
  3. サウンドデバイスというリソースの管理

コンセプト

扱うデータ

  • PCMで標本化した音声データ
  • MIDI
  • デバイスコントロール情報

入出力

  • ほとんどの入出力をioctlでやる

  • フレームを入出力の単位とする

  • I/Oコントロールの直接実装は苦痛であるため、プラグインで機能を付与

  • デバイスに付与する特徴をランタイムに設定

ALSAのカーネルランド

  • ALSA Core
  • ALSA Drivers
  • Linux Subsystems

自分のコミット領域

  • IEEE1394接続(FireWireなど 入力40チャネル 出力40チャネル)

  • プロトコルスタック概要

  • FFADOというもの

  • 構造的な問題があって、ALSAから使えない(開発動機)

ドライバの設計と終わった作業

  • スタック実装を拡張
  • ドライバの実装

これからの作業

  • snd-dice
  • snd-oxfw
  • ALSAのユーザースペース(DSPを制御するアプリケーションの実装)

つらみ

  • プロトコルスタックを開発しているのは自分だけ
  • 4ドライバで計150デバイスをサポート
  • 問い合わせ
  • PulseAudioやる気でない

http://en.wikipedia.org/wiki/FFADO http://ja.wikipedia.org/wiki/%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB%E3%82%B7%E3%82%B0%E3%83%8A%E3%83%AB%E3%83%97%E3%83%AD%E3%82%BB%E3%83%83%E3%82%B5

進捗どうですか

neovim = VM #kernelvm

勉強会

neovimの話をしよう

意見が合わずにforkしたvim=neovim

軽量な仮想化=neovim

Vim ScriptとLuaで拡張可能 Device Driver=Vim Script

Emacsはシェルと通信する機能が充実→これをvimで実装したらEmacsの利点は薄れていくのでは？

neovimの開発者が足りないのが弱点→XEmacsと同じ道を辿らないようにしたい

Vimのアップストリームでの変更をどれだけマージできるか

めっちゃ安いARMボードたくさん輸入してみた #kernelvm

勉強会

イバラキスタン労働党

ARM9 大量購入

マイコンボードFX

まとめ CMakeはクソ

GPIO

課題

  • もっといじる
  • microSDをゼリーに入れて食べる
  • QEMUとか使えばいいんじゃねーの

Robot言語と末尾再帰インタープリタ #kernelvm

勉強会

last update 1998

Brainfuckみたいなやつで、一文字実装

インタプリタは大変 末尾再帰インタプリタ 不要なスタックを消費しない 実行のために明らかに不要な情報を記憶しない。

一文字ずつ解析して…みたいなやつ。

ルールベースの人工知能を開発中

Lispプログラマ Prologプログラマ募集

追記

タイトル変えました。

追記その２

Robot Language and a Tail Recursive Interpreter

OSv噺 #kernelvm

勉強会

OSvをつくってる SD連載

OSvの設計

  • 複数のメモリ空間を持たない
  • カーネルとユーザープロセス間で権限の切り替えをやらない

構造

  • OpenJDK
  • Node.js
  • RESTAPI

アプリケーション

  • 100％の互換ではないが互換性はある
  • マルチスレッド対応
  • Rubyなど対応

  • MySQLなど対応

  • mruby=14MB

  • Ruby=48MB

ブート時間は1秒

ネットワーク経由でリモートからOSの挙動を処理、操作できる。プログラムから。

シェルスクリプトで自動化、など。

LuaCLI

  • 簡易的なシェル機能を提供
  • リモートシェルっぽく使える

OSvGUI

  • WebベースのGUI
  • OSの負荷、JVMのリソース情報などの統計情報などが表示

ゆーざふれんどりぃ！

  • 手軽なコマンド群をLuaCLIで
  • MentionをLuaCUIに流しこもう

どんな実装でTwitterにつなぐのか

  • CLIがLuaだからLua?→サンプルコード少ない
  • JavaやCRuby向け？→ランタイムで別のアプリを動かすのが面倒で避けたい
  • C/C++→これが現実解っぽい

既存実装

  • Twitter4C ツイート投稿だけ
  • twitcurl いちおう動くけどmentionのURLを間違えている JSONのパーサどこだよ UserStreamがない

→Userstreamがほしい

ひとばんくっきんぐ

LuaCLIから実装

感想

  • コマンド出力つぶやきたい
  • 送信元ユーザ制限しないとあぶない

加速器と素粒子物理での超?低レイヤー (3時間で作った手抜き^h^h^hイントロ版)

勉強会

加速器

KernelVMといえば低レイヤー

量子力学(第一原理計算 分子状態を計算)

量子力学の例 * トランジスタの動作をちゃんと計算で求める * フラッシュメモリの原理はトンネル効果を利用している * トンネル効果は量子力学で説明できる

量子力学は低レイヤーなのか？→時代は素粒子！

分子 原子 素粒子

原子核のまわりに電子

原子核は陽子と中性子に別れる

http://ja.wikipedia.org/wiki/%E9%99%BD%E5%AD%90

http://ja.wikipedia.org/wiki/%E4%B8%AD%E6%80%A7%E5%AD%90

http://ja.wikipedia.org/wiki/%E7%B4%A0%E7%B2%92%E5%AD%90

ワインバーグサラムの電弱理論

http://ja.wikipedia.org/wiki/%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%90%E3%83%BC%E3%82%B0%EF%BC%9D%E3%82%B5%E3%83%A9%E3%83%A0%E7%90%86%E8%AB%96

http://ja.wikipedia.org/wiki/%E5%A4%A7%E5%9E%8B%E3%83%8F%E3%83%89%E3%83%AD%E3%83%B3%E8%A1%9D%E7%AA%81%E5%9E%8B%E5%8A%A0%E9%80%9F%E5%99%A8

超電導磁石

http://ja.wikipedia.org/wiki/%E5%8D%8A%E5%B0%8E%E4%BD%93%E6%A4%9C%E5%87%BA%E5%99%A8#.E3.82.B7.E3.83.AA.E3.82.B3.E3.83.B3.E5.8D.8A.E5.B0.8E.E4.BD.93.E6.A4.9C.E5.87.BA.E5.99.A8

http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%83%E3%82%B0%E3%82%B9%E7%B2%92%E5%AD%90

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%B3%E3%83%9E%E3%83%B3%E3%83%BB%E3%83%80%E3%82%A4%E3%82%A2%E3%82%B0%E3%83%A9%E3%83%A0

まとめ

  • 素粒子物理は究極の低レイヤー
  • 巨大な実験装置で究極の理論を探す山師的な一面
  • 測定データはビックデータ
  • シュミレータの計算は１事象５、６分
  • 数万CPUを同時に動かしてスループットを上げる

小さいLinux環境の作り方 #kernelvm

勉強会

フロッピーでブートするディストリビューション

カーネルとユーザランドで1440KiBくらいにおさまればいいんじゃないのか

１３年前のLinuxをフロッピーでブートしようとする config_expert カーネルの基本的な機能を無効に出来る

いろいろな機能を切れば、カーネルのファイルサイズを極限まで小さくすることが出来る→948KiB ブートローダ→カーネル→initramfs→rootfs

glibcを使うのは無理そう→Linux libcを使うことを検討(1998にglibcへの移行するように言われている)

BusyboxとDropbearを使う

でもフロッピーでのブートは終了しているので諦めてブートローダを使う。 でもdmesgは使えん

linux-2.6がEOLになってもコードを修正したら動く。

ストレージが絶望的に小さくても戦える。