研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

研究集会「最適化とその応用」

2010-07-31 16:31:57 | Weblog
筑波大の山本先生の還暦シンポジウムに参加。うちの父も半年前に還暦を迎えたので、勝手に親近感が出てきてしまった。実は父の方が1つ上のようだった。

シンポジウムも失礼ながらパーティも参加してしまった。ご家族を大切にされていることが良く伝わる本当に素敵なパーティだった。このようににぎやかに還暦を迎えることが出来る人ってそうそういるものではない。自分の30年後どのようになっているのだろう。そんなことを考えてみる。

Gurobi 教えてもらう

2010-07-30 03:07:43 | Weblog
オクトーバー・スカイの方を研究室にお呼びしてセミナーを行ってもらった。普段、自分のソフトウェアの設計等を気にすることが多いので、単に Gurobi の使い方を教えてもらう以上に勉強になった。 TeX で書くと「5x_{2}」となるような変数は「5 x2」と書く。ここでハマったところを見ているので、メモしておこう。

Gurobi(MacOSX) install

2010-07-29 02:44:27 | Weblog
MacOSX 用の Install メモ。 1. Gurobi Install CD から Install を行う 2. ライセンスファイル(gurobi.lic とする)の設定 2.1. gurobi.sh の実体がどこにあるか探す
$shell> which gurobi.sh
/usr/local/bin/gurobi.sh

$shell> ls -l /usr/local/bin/gurobi.sh
lrwxr-xr-x  1 root  39  7 28 14:05 /usr/local/bin/gurobi.sh@ -> //Library/gurobi301/mac64/bin/gurobi.sh
2.2. gurobi.lic を配置する
# cp gurobi.lic /Library/gurobi301/mac64/
2.3. パスを通す
# chmod +w /etc/bashrc
# emacs -nw /etc/bashrc
export GUROBI_HOME=/Library/gurobi301/mac64
export PATH="${PATH}:${GUROBI_HOME}/bin"
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${GUROBI_HOME}/lib"
export GRB_LICENSE_FILE=${GUROBI_HOME}/gurobi.lic
# chmod -w /etc/bashrc
# source /etc/bashrc

CPUID : キャッシュメモリの大きさ

2010-07-28 19:56:42 | Weblog
L2キャッシュメモリとキャッシュラインサイズを取得する。
#include <stdio.h>

void cpuid(int op, int *eax, int *ebx, int *ecx, int *edx){
  __asm__ __volatile__ ("cpuid" : "=a" (*eax), "=b" (*ebx), "=c" (*ecx), "=d" (*edx) : "a" (op) : "cc");
}

unsigned long get_cache_size(void) {
  int eax, ebx, ecx, edx;
  int size = 0;  
  cpuid(0x80000000, &eax, &ebx, &ecx, &edx);
  if ((unsigned int)eax >= 0x80000006) {
    cpuid(0x80000006, &eax, &ebx, &ecx, &edx);
    size = (ecx >> 16) & 0xffff;
  }
  return size * 1024;
}

unsigned long get_cache_linesize(void) {
  int eax, ebx, ecx, edx;
  int linesize = 0;
  cpuid(0x80000000, &eax, &ebx, &ecx, &edx); if ((unsigned int)eax >= 0x80000006) { cpuid(0x80000006, &eax, &ebx, &ecx, &edx); linesize = (ecx >> 0) & 0xff; } return linesize; } int main(void) { printf("L2 cache\t: %ld KB\n", get_cache_size() / 1024); printf("L2 line cache\t: %ld B\n", get_cache_linesize()); return 0; }

CPUID : コア数の取得

2010-07-27 19:55:55 | Weblog
プロセッサのコア数を取得する。
#include <stdio.h>

void cpuid(int op, int *eax, int *ebx, int *ecx, int *edx){
__asm__ __volatile__ ("cpuid" : "=a" (*eax), "=b" (*ebx), "=c" (*ecx), "=d" (*edx) : "a" (op) : "cc");
}

int get_cpu_cores(void) {
int cores = 1, eax, ebx, ecx, edx;
cpuid(0x00000000, &eax, &ebx, &ecx, &edx);
if ( eax >= 0x01 ) {
cpuid(0x01, &eax, &ebx, &ecx, &edx);
cores = (ebx >> 16) & 0xff;
}
return cores;
}

int main(void) {
printf("CPU cores\t: %d\n", get_cpu_cores());
return 0;
}

CPUID : CPU 名

2010-07-26 19:55:03 | Weblog
プロセッサ名取得を行う。
#include <stdio.h> 

void cpuid(int op, int *eax, int *ebx, int *ecx, int *edx){
  __asm__ __volatile__ ("cpuid"
: "=a" (*eax), "=b" (*ebx), "=c" (*ecx), "=d" (*edx)
 : "a" (op) : "cc"); } char *get_cpu_name(void) { int eax, ebx, ecx, edx; static int name[12] = {0};
cpuid(0x80000000, &eax, &ebx, &ecx, &edx); if ( (eax & 0xffff) >= 4 ) { cpuid(0x80000002, &name[0], &name[1], &name[ 2], &name[ 3]); cpuid(0x80000003, &name[4], &name[5], &name[ 6], &name[ 7]); cpuid(0x80000004, &name[8], &name[9], &name[10], &name[11]); } return (char *)name; } int main(void) { printf("CPU name\t: %s\n", get_cpu_name()); return 0; }

オープンキャンパス2010 - その1

2010-07-25 02:42:16 | Weblog
今年もこの季節がやってきた。今年度からなぜか3回実施で、3回とも参加せよとのこと。

教員免許を持ってるくらいなので、高校生との話するのは嫌いではない。最近の高校生の特徴なのか、オープンキャンパスに来るようなやる気のある生徒であっても「俺なんて…」と諦め気味なことを口にするようだ。真面目にやって落ちたりしたら格好悪いので、そのための保険と思っているのだろうか。

RIMS2010

2010-07-22 02:41:13 | Weblog
2年連続での参加となった。しかも去年も同じ時間帯(2日目の1つ目という定位置)を頂けた。

今回は最短路ソルバと大規模避難経路に関することをお話ししたが、やはり色々試した最短路ソルバに関することよりも、これから詰めていこうしている大規模避難経路を主に突っ込まれた。仕方ないだろう。

メモリ階層構造を考慮して汎用的に高速化を行うことに関してはある程度のノウハウの蓄積が出来てきていると感じるが、さらにアルゴリズムに対する実装後の性能を見積もり評価することができればと考えている。

K大

2010-07-21 02:40:39 | Weblog
2年ぶりに関西大へ。文理が1つのキャンパスで学んでいるのは活気があるし、非常に羨ましい。学祭など理系だけではどうしても盛り上がりに欠けるところがある(怒られそうだが)。テニスコートからはソフトテニスの乱打の音を久しぶり聞く事ができて、うきうきしてしまった。

時間計測ルーチンの種類

2010-07-20 19:35:18 | Weblog
時間計測のためのルーチンはいくつか存在する。

例えば Linux 環境では、
1. gettimeofday
2. rpcc
3. performance counter
4. getrusage
が有名である。

1. 現在の UNIX 時間を取得する方法
現在の UNIX 時間(1970年1月1日0時0分0秒からの経過時間)を取得する。実行前後での差を取る事で計測する。非常に精度が高い計測方法なので、一般的にはこれを用いる。実装によっては 2 の rpcc() を内部で用いている。

2. cycle counter を用いる方法
最近のプロセッサはマルチコアであるため、各コア上にあると別々の計測となってしまうため、メモリコントローラに配置されているそうだ。そのためメモリコントローラへアクセスするためのコストを含んでしまう。また Intel 系の turbo burst など周波数が変化してしまう状況では、計測が困難となる。

3. プロセッサの performance counter を取得する方法
コア上に配置されている performance counter 非常に精度の高い計測を行う事ができる。oprofile などのソフトウェアを使用する。

4 消費したリソースを取得する方法
スレッド並列実行でもプロセスの合計となってしまうため、実行時間計測に適さない。


例えば VM のようなプロセッサの周波数が安定しない場合などでは 3 が使用不可であり、1 や 2 のカウンターもうまく動かないため、計測結果が正しくないということが考えられる。

例えば以前紹介した記事(Link)での、VM(AmazonEC2) での結果が出来すぎている。

Google

2010-07-17 19:24:26 | Weblog
Google Japan へ行ってきた。最短路に関するお話をしたのですが、そこそこ興味を持ってもらったようだ。帰りに紙袋で Google Goods を頂いた。個人的にはレジャーシートがお気に入り。