2013年5月15日水曜日

[Code reading] time command

[Motivation]
FORTRANで記述されコンパイラで自動並列化した数値解析のプログラムの実行時間を下記環境でtimeコマンドを使って測定したら下記の様な結果になった。


-実行環境-
OS: Cent OS
CPU: Intel Xeon Processor L5640 x 2

-並列数-
OMP_NUM_THREAD=12

-time コマンド結果-

real 84m23.521s
user 1010m2.767s
sys 0m7.199s


[reasoning]
user時間は、各コアのuser時間の合計となるためスレッド並列化して実行したコマンドでは、real時間よりも長くなることがある?

[research]


適当なミラーサイトからソースを取ってくる。
後、linuxカーネル(2.6.34)のソースも取ってくる。

まずは、タイムコマンドのmain関数
-time.c: main
632 main (argc, argv)
633      int argc;
634      char **argv;
635 {
636   const char **command_line;
637   RESUSE res;

640   run_command (command_line, &res);
641   summarize (outfp, output_format, command_line, &res);

run_commandという関数を見てみる
-time.c: run_command
597 static void
598 run_command (cmd, resp)
599      char *const *cmd;
600      RESUSE *resp;
601 {

605   resuse_start (resp);

614       execvp (cmd[0], cmd);

623   if (resuse_end (pid, resp) == 0)

timeコマンドで指定したコマンドをexecvp関数で実行している.
execvp関数の前後で呼んでいるresuseで始まる関数を次に見てみる

-resuse.c: resuse_start
 46 void
 47 resuse_start (resp) //resuseは、resource use startの略と思われる。
 48      RESUSE *resp;
 49 {
 50 #if HAVE_WAIT3
 51   gettimeofday (&resp->start, (struct timezone *) 0);
 52 #else
 53   long value;
 54   struct tms tms;
 55
 56   value = times (&tms); // man によると返り値は過去のある時点からのtick
 57   resp->start.tv_sec = value / HZ; // HZ は、CPUクロックか? 確証は得られてない
 58   resp->start.tv_usec = value % HZ * (1000000 / HZ);
 59 #endif
 60 }
現在のクロックカウント(と言っていいのか?)をHZで割って時刻をresp->start.tvに保持する

-resuse.c: resuse_end
117   resp->elapsed.tv_sec -= resp->start.tv_sec; // real time (sec)?
124   resp->elapsed.tv_usec -= resp->start.tv_usec; // real time (micro sec)?
コマンド実行後に省略したが同様にCPU時刻を取得して実行前の時刻を引いている。=> 正味実行にかかった時間(real time)を算出。


struct tmsとは何か?
struct tms -> linux/times.h
 6 struct tms {
  7         __kernel_clock_t tms_utime; // user time
  8         __kernel_clock_t tms_stime; // system time
  9         __kernel_clock_t tms_cutime; // child process user time
 10         __kernel_clock_t tms_cstime; // child process system time
 11 };

__kernel_clock_t -> linux/types.h
 79 typedef __kernel_clock_t        clock_t;


-time.c : summarize
320 static void
321 summarize (fp, fmt, command, resp)
322      FILE *fp;
323      const char *fmt;
324      const char **command;
325      RESUSE *resp;
326 {


-kernel/sys.c 912 void do_sys_times(struct tms *tms)
 921         tms->tms_utime = cputime_to_clock_t(tgutime);
 922         tms->tms_stime = cputime_to_clock_t(tgstime);
 923         tms->tms_cutime = cputime_to_clock_t(cutime);
 924         tms->tms_cstime = cputime_to_clock_t(cstime);


thread_group_timesとは
kernel/sched.c

3398 void thread_group_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
3399 {
3400         struct task_cputime cputime;
3401        
3402         thread_group_cputime(p, &cputime);
3403
3404         *ut = cputime.utime;
3405         *st = cputime.stime;
3406 }


kernel/posix_cpu_timers.c

234 void thread_group_cputime(struct task_struct *tsk, struct task_cputime *times)
 235 {
 236         struct sighand_struct *sighand;
 237         struct signal_struct *sig;
 238         struct task_struct *t;
 239
 240         *times = INIT_CPUTIME;
 241
 242         rcu_read_lock();
 243         sighand = rcu_dereference(tsk->sighand);
 244         if (!sighand)
 245                 goto out;
 246
 247         sig = tsk->signal;
 248
 249         t = tsk;
 250         do {
 251                 times->utime = cputime_add(times->utime, t->utime);
 252                 times->stime = cputime_add(times->stime, t->stime);
 253                 times->sum_exec_runtime += t->se.sum_exec_runtime;
 254
 255                 t = next_thread(t);
 256         } while (t != tsk);
 257
 258         times->utime = cputime_add(times->utime, sig->utime);
 259         times->stime = cputime_add(times->stime, sig->stime);
 260         times->sum_exec_runtime += sig->sum_sched_runtime;
 261 out:
 262         rcu_read_unlock();
 263 }


include/asm-generic/cputime.h
12 #define cputime_add(__a, __b)           ((__a) +  (__b))

next_thread(t);とは
include/linux/sched.h

2177 static inline struct task_struct *next_thread(const struct task_struct *p)
2178 {              
2179         return list_entry_rcu(p->thread_group.next,
2180                               struct task_struct, thread_group);
2181 }

thread_group.nextとは、
include/linux/sched.hのtask_structのメンバー
1285         struct list_head thread_group;

list_headとは、
include/linux/list.h

 41 struct list_head {
 42         struct list_head *next, *prev;          
 43 };


list_entry_rcuとは?
include/linux/rculist.h

210 #define list_entry_rcu(ptr, type, member) \
211         container_of(rcu_dereference_raw(ptr), type, member)




spin_lock_irq のirqとは?
include/linux/spinlock.h

307 static inline void spin_lock_irq(spinlock_t *lock)
308 {      
309         raw_spin_lock_irq(&lock->rlock);
310 }
include/linux/spinlock.h
220 #define raw_spin_lock_irq(lock)         _raw_spin_lock_irq(lock)
include/linux/spinlock-api_up.h
59 #define _raw_spin_lock_irq(lock)                __LOCK_IRQ(lock)


spin_local_irqに渡しているcurrent_sighand_siglockとは?


[conclusion]
utimeとstimeは、とりあえず全てのスレッド分足してそうだというとこまでは行ったがかなり消化不足気味

[気になるキーワード]
Hyper Threading
SMT (Simultaneous Multi Threading) 同時マルチスレッディング
SMP (Symmetric Multi Processing) 対象型マルチプロセシング

0 件のコメント:

コメントを投稿