Ubuntu 14.04 メモ

HDD交換する用があったので、ついでに入れ直した。
幾つか困ったので、メモ。

1. UEFIブートで、WindowsとUbuntuのデュアルブート
   Ubuntuインストーラから、先にUEFIでインストールしたWindowsが見えない。普通にOther Optionを選んで、空き領域に必要なパーティションを作って、ブートローダのインストール先を/dev/sdaから/dev/sda2(efi領域)にして、インストールすれば大丈夫
2. sshdのインストール
   GUIから見つからない
     $ sudo apt-get install openssh-server
   で大丈夫だった。
3. mozc(日本語入力)のインストール
   GUIからibus用のmozcが見つからない
   GUIからmozcの設定プログラムか何かをインストールして、
     $ sudo apt-get install ibus-mozc
   で大丈夫だった。ログアウトしてログインして、Text Entry Setting
4. ALT+backtick(`)が効かない
   治ってなかった。先日の投稿の通りやったら大丈夫
5. NFSクライアントの設定
   デフォルトだとインストールされていない
     $ sudo apt-get install nfs-common
   で大丈夫

バス幅、バスの周波数、転送レート、帯域幅、Bandwidth

最近、数字がよく分からなくなってきてたので復習。

メモリの場合は、
バス幅: 64bitとか、256bitとか
バスの周波数: 666MHzとか、800MHzとか
転送レート: 1333MT/sとか、1600MT/sとか
帯域幅: 10.6GB/sとか、51.2GB/sとか

単純にいうと、バス幅×周波数×1サイクル当たりの転送回数＝帯域幅。
また、バス周波数×1サイクル当たりの転送回数＝転送レート。

1サイクル当たり1回転送のSDRメモリだと、64×666MHz×1÷8＝5.3GB/s。
今の主流のDDRメモリだと、1サイクル当たり2回転送するので倍の、10.6GB/s。

Sandy Bridgeになってバス幅が192bitから256bitに拡張された。
64bitを1チャネルとするので、4チャンネルということになる。
1333MT/ｓで4チャネルを同時に駆動すると、256×1333MT/s÷8＝42.6GB/s。


QPIの場合は、
レーン数: 20
リンク当たりのデータ幅: 16/20
周波数: 3.2GHzとか、4.0GHzとか
1サイクル当たりの転送回数: 2
転送レート: 7.2GT/sとか、8GT/sとか
同時転送方向数: 2
QPIリンク数: 2とか、4とか

最近は転送レートしかデータシートに出てこない。
なので計算は、データ幅×転送レート×同時転送方向数×QPIリンク数＝最大帯域幅。
データ幅と同時転送方向数が固定なので、転送レート×32×QPIリンク数でいい。

7.2GT/sで、2リンク同時に駆動すると、7.2GT/s×32×2÷8＝57.6GB/s。


ただ、この計算ででてくるMHｚやMT/sはSI接頭辞で1000のべき乗倍なんだよな。
通常GBとか計算するときは1024のべき乗倍なので注意が必要。


以下参考
Doube data rate
Multi-channel memory architecture
Intel QuickPath Interconnect

使ってはいけないＰＡＵＳＥ命令

仕事でmanycoreのスケーラビリティなんかを調査する必要がでてきた。

で、いろいろ調べて適当なベンチマークを使ってたんだけど、2008年頃に作られたベンチマークでspinlockの中でアセンブラのpause命令を多用してた。

google先生に聞くと、spinlockでpauseを使って性能アップ！みたいなiSUSの記事が出てくるんで、そのままにしてたんだけど、よくよく考えると、pause命令ってパイプラインに空命令を流し込むような処理をしてるんだよね。

当時は1スレッドでパイプライン埋めれなかったとかで問題ないんだろうけど、今だと1スレッドでパイプライン埋めれるので、無駄に空命令流し込むと、ＳＭＴ使ってると性能ガタ落ちのはず。ちょｗｗｗ

明日修正して再度計測するわ。


で、修正してみたんだけど、並列に同時に処理してばっと終わるようなコードではあまり影響が出なかった。マルチスレッドで順々にデータを渡すような処理で、空き時間をＰＡＵＳＥで待ってると、結構影響があった。Ｘｅｏｎ Ｐｈｉを使ってたので、_mm_delay(1)とに置き換えて試した。

Bamboo Paper

最近、メモ取ったり落書きしたりするのに、iPad使ってる。

iPadで、Bamboo Paper (無料)とスタイラスC1 (410円)を使ってる。Bamboo Paperが書き味抜群で、書いてるだけで楽しい。ペン先の見えるちゃんとしたスタイラスがどんどん欲しくなってきてるとこ。で、静電パネルだけだと限界があるのが分かって、Wacomのデジタイザチップが付いてるタブレットが欲しくなってきた……。

これ以外は、Note Anytime (200円期間限定)も買って使ってみてる。ペンがボールペンオンリーという感じで、書き味はいまいちだけど、メモ書きツールとしての基本機能はしっかりしてると感じる。でも、Bamboo Paperが書いてるだけで楽しいので、ついついそっち使ってしまう。

そういえば、Android用のBamboo Paperもタブレットで使えるようになってましたので、こちらもお薦め。

簡潔データ構造 (succinct data structure) 修正版

先日書いた簡潔データ構造の説明に色々勘違いが混ざってたので修正版

最近、簡潔データ構造が気になってる。

きっかけは、2年位前の国立情報学研究所(NII)のオープンハウスに行って、定兼さんの透過的データ圧縮の話を聞いてからだ。すぐにでもOSSとしてライブラリをリリースするという話だったが、2年経っても公開されていない。

なので、ぼちぼちと自分で調べたことや理解したことなどメモしていってみようと思う。


まず、透過的データ圧縮で使う簡潔データ構造とは何か？
G. Jacobson, "Space-efficient Static Trees and Graphs", IEEE 1989が元ネタ。
簡単に言うと、新しいデータ構造。

データ構造には大きく分けて以下の3つがある。
簡潔データ構造 on Wiki

データTがあり、それを表現するのに必要なビット数をZとおく。

• Z+O(1)を必要とするデータ構造をimplicit data structureと呼ぶ
  データそのものに対し、追加でO(1)～O(lg Z)のデータを必要とするデータ構造
  例えばHeapがこの一種。具体的には、以下の図の通り
• Z+o(Z)を必要とするデータ構造をsuccinct data strcuture (簡潔データ構造)と呼ぶ
  データそのものに対し、追加でO(lg Z)～O(Z)のデータを必要とするデータ構造
  例えば、上記論文(Jacob, 1989)に出てくるlevel-ordered bitmapがこの一種
• O(Z)を必要とするデータ構造をcompact data structure (コンパクトデータ構造)と呼ぶ
  これが何を指しているかが、wikiでは明確でない
  例えば、suffix arrayがこの一種 (と理解している。suffix arrayは、理論的にはO(Z)だが実際はO(Z lg Z)ビット必要)

一言でいうと、これまでのデータ構造はビット数まで考えると、サイズがO(n lg n)、計算量がO(lg n)だった。それに対し、サイズをO(n)に抑え、計算量もO(lg n)を保ったデータ構造を考えたという話。次の世代のデータ構造として、非常に有効だと思うので勉強していきたい。

また、透過的データ圧縮では、LZ78の辞書をsuccient data structureに置き換え、かつrank/select用のテーブルに相当するデータを用意することで、圧縮データのどこからでも定数時間内で展開する方法を提案するという感じ。詳細は、まだ勉強中。