Transparent Huge Page

Transparent Huge Page という hugepage が Linux 2.6.37 から使用することができます。

とはいっても、Transparent Huge Page は default で always 設定(すべて hugepage 上に確保)になっているので、CentOS6, Fedora15 あたりの OS を使用している場合、知らず知らずのうちにその恩恵を授かっていると思われます。

本来 Linux は 4KB のページと呼ばれる block でメモリを扱うことになっていますが、この場合 virtual address から 4 段階の変換テーブルを参照して目的の物理メモリにアクセスすることができます。この 4KB ごとの TLB miss を軽減するには、大きなサイズのページ hugepage を採用することが有効です。2MB の hugepage を採用するとメモリアクセスは 1 段減り、TLB miss も約 1/512 となります。その代わり、小さなメモリ要求に対しても 2MB ごとの割り当てになってしまいメモリ量を有効活用できなくなります。

最適化系の数値計算を行う場合、大量のメモリを使用することになるので、hugepage による性能向上の効果は非常に大きいと言えます。最短路問題では 10% ほどの性能向上を確認しました。しかしながら、hugepage の確保は面倒な手順が必要です。Linux では「共有メモリ経由でのメモリ確保」と「hugetlbfs という特殊な file system に対する anonymous memory mapping によるメモリ確保」の 2 種類がありますのが、いずれもソースコードの変更が必要になります。簡単に利用する方法としては「libhugetlbfs ライブラリによる malloc/new 関数の hook」という荒業もありますが、すべての領域が hugepage 上に乗ってしまうので少々使いづらいと言えます。また、いずれの方法でも予め必要なメモリ領域を hugepage 専用として確保しなければなりません。

それに対して Transparent Huge Page では、予め必要な領域を確保する必要がなく、名前の通り透過的に hugepage を扱えるようになる機構です。

◯ Transparent Huge Page で確保したサイズの確認(例:never 設定なのほぼhugepageは0)
% grep Anon /proc/meminfo


◯ node 毎の Transparent Huge Page で確保したサイズの確認(例:never 設定なのでほぼhugepageは0)
% grep Anon /sys/devices/system/node/node*/meminfo


◯ Transparent Huge Page を使用するかどうかの設定
/sys/kernel/mm/transparent_hugepage/enabled

・[always] madvise never
常に THP を使用する設定。

・always [madvise] never
madvise 関数を用いて MAD_HUGEPAGE によって指定された領域のみを Transparent Huge Page に配置させる設定。※ 試していないので推測した情報です。
#include <sys/mman.h>
int madvise(void *addr, size_t length, int advice);

・always madvise [never]
常に THP を全く使用しない使用する設定。



【参考】
Transparent Hugepage Support / Red Hat Inc. @ KVM Forum 2010 Boston
www.linux-kvm.org/wiki/images/9/9e/2010-forum-thp.pdf

記事: より広大なメモリ領域を効率よく利用する -Transparent Hugepage- / Red Hat Inc.
http://www.jp.redhat.com/magazine/jp/201008/rhel.html

Node Interleave 設定

4way Opteron 6174 (magny cours) サーバ上での Node Interleave 設定の ON/OFF による構成の違いを /sys/devices/system 以下の情報に関してまとめる。

この結果から、node interleave を ON にすると、OS からは 48 コアのプロセッサが 1 基あるように見えるようになる。affinity 設定を行っているプログラムだと予想通りに動作しない場合もあるかもしれない。

◯ Node Interleave ON

% ls /sys/devices/system/node/
has_cpu  has_normal_memory  node0/  online  possible

% cat /sys/devices/system/node/node0/cpulist
0-47

% cat /sys/devices/system/node/node0/cpumap
00000000,00000000,00000000,00000000,00000000,00000000,0000ffff,ffffffff

% cat /sys/devices/system/node/node0/distance
10

◯ Node Interleave OFF

% ls /sys/devices/system/node/
has_cpu  has_normal_memory  node0/  node1/  node2/  node3/  node4/  node5/  node6/  node7/  online  possible

% cat /sys/devices/system/node/node?/cpulist
0,4,8,12,16,20
24,28,32,36,40,44
3,7,11,15,19,23
27,31,35,39,43,47
2,6,10,14,18,22
26,30,34,38,42,46
1,5,9,13,17,21
25,29,33,37,41,45

% cat /sys/devices/system/node/node?/cpumap
00000000,00000000,00000000,00000000,00000000,00000000,00000000,00111111
00000000,00000000,00000000,00000000,00000000,00000000,00001111,11000000
00000000,00000000,00000000,00000000,00000000,00000000,00000000,00888888
00000000,00000000,00000000,00000000,00000000,00000000,00008888,88000000
00000000,00000000,00000000,00000000,00000000,00000000,00000000,00444444
00000000,00000000,00000000,00000000,00000000,00000000,00004444,44000000
00000000,00000000,00000000,00000000,00000000,00000000,00000000,00222222
00000000,00000000,00000000,00000000,00000000,00000000,00002222,22000000

% cat /sys/devices/system/node/node?/distance
10 16 16 22 16 22 16 22
16 10 16 22 22 16 22 16
16 16 10 16 16 16 16 22
22 22 16 10 16 16 22 16
16 22 16 16 10 16 16 16
22 16 16 16 16 10 22 22
16 22 16 22 16 22 10 16
22 16 22 16 16 22 16 10

○ magny_cours_48 サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

中心性指標

ここ半年で行ってきたことについて少しずつまとめていく。

まずは中心性計算に関してまとめる。最短路を用いた中心性計算のうち、最短距離による closeness, graph と最短路数による stress, betweenness が有名である。特に betweenness は Web, Communication, Citation, Patents などの座標を持たないネットワークに頻繁に用いられている。

それではそれぞれの特徴をまとめていく。

d(s,t) ... s-t 間の最短路長
sigma_{s,t}(v) ... s-t 間の最短路のうち、vを通る数

1. closeness ... 他点への最短距離の和を指標とする
2. graph ... 他点への最短距離の最大値を指標とする

→ 他点への最短距離に着目している。以下の例のような平面グラフでは非常に分かりやすい結果が得られるものの、座標を持たないグラフに対しての意味付けは難しいかもしれない。graph の最大値は直径(diameter) と一致する。


3. stress ... 最短路上に含まれる回数を指標とする。
4. betweenness ... 最短路上に含まれる割合を指標とする。normalize された stress という解釈も可能

→ 最短路上に含まれる回数や割合を指標としているため、この指標が高い点は何度も最短路に使用される重要な点であることを示している。道路ネットワークであれば渋滞の起こりやすさ等に、ソーシャルネットワークであれば友人関係の活発さ等に関係性があるといえるだろう。※ stress は betweenness に対して最短路数の絶対数を考慮しているため、格子グラフなどの最短路数が非常に多いグラフではオーバーフローしてしまう可能性が高い。


図は、 att532.tsp の近い点間に枝を引いて生成した点数 n=532, 枝数 m=3724 のグラフの中心性の結果である。

ブログ復帰。

ずいぶん長く休んでしまったので実に9ヶ月ぶりの記事となります。
1日1記事ペースは僕には難しいようなので、
少しずつ自分のペースで綴っていければと思います。
これからもどうぞよろしくお願いします。