64 ビット Linux での Power Architecture の Time Base Register

PowerPC の追加ハードウェア機能を利用して、効率的かつ正確に時刻を測定する

Power Architecture™ 技術の Time Base Register を使用し、PowerPC® およびCell/B.E. (Cell Broadband Engine™) マイクロプロセッサーで動作する Linux® で、ナノ秒レベルの時刻を測定してください。この精度の高い時刻測定が役に立つアプリケーションとしては、トランザクション(通常は暗号化されるか、またはデジタル署名が付いた 1 回だけ使用されるメッセージ) へのタイムスタンプ付与、コードのプロファイル作成、そして微小時間の正確なソフトウェア遅延の実装などがあります。

Carlos Cavanna, Software Developer, IBM Software Group, Application and Integration Middleware

Carlos Cavanna はIBM Compilers Group のソフトウェア開発者で、PowerPC Architecture 対応の Java JIT (Java Just-In-Time) コンパイルを専門としています。



2007年 4月 04日

通常、アプリケーション・プログラムは何らかの形で時刻を測定するものです (トランザクションのタイムスタンプなど)。そのため POSIX ライブラリーには、アプリケーション・プログラマーが使いやすいインターフェースとして、gettimeofday などの時刻を取得する関数が用意されています。アプリケーションが時刻取得関数を集中的に利用する場合、時刻取得のルーチンをより効率的に実装することで、プログラムの全体的なパフォーマンスを向上させることができます。これは、コードのプロファイル作成やデバイス・ドライバーでの正確な遅延などといった低位レベルのタスク、そしてその他のタイムクリティカルなコードにとって極めて価値のあることです。

Power Architecture プラットフォームでは、gettimeofday によって実現されるパフォーマンスをさらに改善することが可能です。この記事では、UNIX® エポック (1970年1月1日) からの時間を、PowerPCおよび Cell/B.E. PPE プロセッサーで稼動する 64 ビット Linux® オペレーティング・システムで効率的かつ正確に測定する手法を紹介します。この手法は、ミリ秒およびナノ秒の精度を実現します。一部のLinux バージョンでは、この記事で紹介する gettimeofday と同じような実装を提供していますが、精度の点では劣ります。

この手法は AIX オペレーティング・システムでも実装できますが、以下に詳しく説明する例とシステムの詳細は 64 ビット Linux の実装に対応するものです。

Time Base Register

Power Architecture の資料 (「Book II: PowerPC Virtual Environment Architecture」。「参考文献」を参照) で記載している Time Base (TB) と呼ばれるカウント・レジスターは、システム時刻を追跡するために使用されます。TB レジスターは実装に依存した頻度で定期的にインクリメントされますが、この頻度は一定とは限りません。更新頻度が変更されたかどうかを判断し、必要に応じて内部構造を調整するのは、オペレーティング・システム(OS) の役目です。

PowerPC Architecture は、以下のことを規定しています。

  • TB レジスターは 64 ビット長であること。
  • 更新の増分値は 1 であること。
  • オペレーティング・システムが更新頻度を判断できること。
  • TB が最大値に達したら、オーバーフローして 0 から再開すること。TB の再開は明示的に示されることはなく、OS の処理に任されます。
  • OS が電源投入時に TB レジスターを初期化すること。

詳細は、「PowerPC Virtual Environment Architecture」を参照してください (この資料へのリンクをはじめ、この記事で取り上げるその他の資料へのリンクは、このページの終わりにある「参考文献」に記載しています)。Cell/B.E. PPE も同じく、TB レジスターを実装しています。

TB レジスター自体には、時刻を計算するだけの十分な情報は含まれません。Power Architecture の仕様では、TB レジスターの処理はほとんどオペレーティング・システムに任せており、オペレーティング・システムが更新頻度、ブート時にTime Base に設定される値などの追加データを提供することになります。このような計算メカニズム全体は、高速かつ効率的になっています。

Linux オペレーティング・システムの場合、システム・ライブラリーは構造体 systemcfg の以下の情報をエクスポートします。

リスト 1. Time Base 固有のシステム情報
struct systemcfg {
...
__u64 tb_orig_stamp;            /* Time Base at boot       */
__u64 tb_ticks_per_sec;         /* Time Base ticks / sec    */
__u64 tb_to_xs;                 /* Inverse of TB to 2^20  */
__u64 stamp_xsec;
__u64 tb_update_count;          /* Time Base atomicity ctr */
...
};

上記に含まれる情報は、以下のとおりです。

  • tb_orig_stamp: ブート時の TB レジスターの値です。
  • tb_ticks_per_sec: 1 秒あたりの TB レジスターのティック数です (以下の計算では使用されません)。
  • tb_to_xs: TB ティック数を x秒数に変換するために使用します。
  • stamp_xsec: x秒単位でのブート時の時刻です。
  • tb_update_count: tb 更新時にカウントとして使用します。

この構造体にアクセスするには、以下のヘッダー・ファイルをインクルードします。

#include <asm/systemcfg.h>


アセンブリー言語でレジスターを読み出す方法

TB レジスターの値を汎用レジスターに転送するには、mftb ニーモニックを使用します。その文法は以下のとおりです。

mftb rx

「PowerPC Virtual Environment Architecture [1]」に、このニーモニックの技術的詳細、そしてアセンブリー言語でgettimeofday を計算するためのアルゴリズムについての説明が記載されています。

一部の Linux ディストリビューションには、TB レジスターの値を返す get_tb() というライブラリー関数が用意されています。この関数は、単一の mftb アセンブリー命令として実装されます。


gettimeofday を使用する方法

gettimeofday を使用したナノ秒計算は、以下のように実装します。

リスト 2. ナノ秒精度での現在時刻の取得
U64 gtod_nano()
{
struct timeval t;
gettimeofday(&t,NULL);
return t.tv_usec * 1000 + t.tv_sec * 1000000000;
}

ナノ秒精度での時刻計算

ナノ秒精度でのエポックからの経過時間は、TB レジスターと systemcfg 構造体で公開された値を使用して以下のように計算できます。

リスト 3. 時間値から絶対時刻への変換
nanoseconds_since_epoch =
((( (<TB value> - tb_orig_stamp) * tb_to_xs)
+ stamp_xsec) * <nanoseconds per second>)
/ <xseconds per second>

上記の前提は、以下のとおりです。

  • 1 秒に相当するナノ秒 = 1 000 000 000
  • 1 秒に相当する x秒 = 2^20

上記の計算をさらに詳しく説明すると、以下のように分けることができます。

  1. ブート時以降の Time Base Register のティック数を計算するため、TB レジスターの現行値から tb_orig_stamp の値を引きます。

    elapsed_ticks_since_boot = <TB value> - tb_orig_stamp

  1. ブートからの経過 x秒数を計算するため、tb_to_xs を使ってブート時以降のティック数 (1) を x秒数に変換します。

    elapsed_xseconds_since_boot = elapsed_ticks_since_boot * tb_to_xs

  1. エポックからの x秒数を計算するため、ブートからの経過 x秒数 (2) を stamp_xsec に保存されたブート時の時刻 (x秒単位) に加えます。

    xseconds_since_epoch = elapsed_xseconds_since_boot + stamp_xsec

  1. エポックからの x秒数の値 (3) をナノ秒に変換するため、値を 1 秒あたりの x秒数で割って、1 秒あたりのナノ秒数を掛けます。

    nanoseconds_since_epoch = (xseconds_since_epoch * <nanoseconds per second>)/ <xseconds per second>

ミリ秒精度での時刻も上記の考え方に沿って計算しますが、中間結果を 1 秒あたりのミリ秒数で変換するという点が違います。

リスト 4. ミリ秒精度への変換
nanoseconds_since_epoch =
((( (<TB value> - tb_orig_stamp) * tb_to_xs)
+ stamp_xsec) * <nanoseconds per second>)
/ <xseconds per second>

この記事では、ナノ秒の計算についてのみ詳しく説明します。

完全なアルゴリズム

以下に、ナノ秒精度で時刻を計算する C 言語の完全なアルゴリズムを記載します。

リスト 5. ナノ秒精度での時刻の取得
#define U64 __u64

U64 tb_nano()
{
#define NANOSECS_PER_SEC 1000000000

U64 tbr;
U64 elapsed_ticks_since_boot;
U64 elapsed_xseconds_since_boot_hi;
U64 elapsed_xseconds_since_boot_lo;
U64 xseconds_since_epoch;
U64 nanoseconds_per_second = NANOSECS_PER_SEC;
U64 nps_temp_hi;
U64 nps_temp_lo;
U64 nanoseconds_since_epoch_hi;
U64 nanoseconds_since_epoch_lo;
U64 nanoseconds_since_epoch;

U64 count_start;
U64 count_end;
do {
count_start = cfg->tb_update_count;

__asm__ __volatile__("mftb %[tbr]" : [tbr] "=r" (tbr):);

elapsed_ticks_since_boot = tbr - cfg->tb_orig_stamp;

multiply(elapsed_ticks_since_boot, cfg->tb_to_xs,
&elapsed_xseconds_since_boot_hi,
&elapsed_xseconds_since_boot_lo);

xseconds_since_epoch =
cfg->stamp_xsec + elapsed_xseconds_since_boot_hi;

count_end = cfg->tb_update_count;

} while (count_start != count_end && count_start & 0x1 != 0);

multiply(xseconds_since_epoch, nanoseconds_per_second,
&nps_temp_hi,
&nps_temp_lo);

nanoseconds_since_epoch_lo = nps_temp_lo >> 20;
nanoseconds_since_epoch_hi = nps_temp_hi << (64 ? 20);

nanoseconds_since_epoch =
nanoseconds_since_epoch_hi | nanoseconds_since_epoch_lo;

return nanoseconds_since_epoch;
}

詳しい内容は以下のとおりです。

  1. TB レジスターの値を 64 ビット変数の tbr に読み込みます。C 言語にはこのレジスターにアクセスするためのメカニズムがないため、アセンブリー言語を使用する必要があります。

    __asm__ __volatile__ ("mftb %[tbr]" : [tbr] "=r" (tbr):);

  1. TB レジスターから tb_orig_stamp を引いて、elapsed_ticks_since_boot を計算します。

    elapsed_ticks_since_boot = tbr - cfg->tb_orig_stamp;

  1. elapsed_ticks_since_boottb_to_xs を掛けて、elapsed_xseconds_since_boot を計算します。

    multiply(elapsed_ticks_since_boot, cfg->tb_to_xs, &elapsed_xseconds_since_boot_hi, &elapsed_xseconds_since_boot_lo);

    注意しなければならない点は、ヘルパー乗算関数を使用する必要があることです。elapsed_ticks_since_bootcfg->tb_to_xs はどちらも 64 ビット長のオペランドなので、その乗算結果は 128 ビットの数値になります。これほど大きい数値は単一の C 変数では表現できません。そのため、ヘルパー乗算関数を使って値を2 つの部分に分割します。この例ではこれに相当するのは、 elapsed_xseconds_since_boot_hielapsed_xseconds_since_boot_lo です。乗算アルゴリズムについては、「サポート関数としての乗算」で詳しく説明します。

  1. elapsed_xseconds_since_boot_histamp_xsec を加算して、xseconds_since_epoch を計算します。

    xseconds_since_epoch = cfg->stamp_xsec + elapsed_xseconds_since_boot_hi;

  1. xseconds_since_epochxseconds_per_second (20 ビット右シフト) で割って秒数に変換し、その結果に nanoseconds_per_second を掛けてナノ秒に変換することによって、nanoseconds_since_epoch を計算します。このアルゴリズムはまず乗算してから除算 (シフト) を行うことに注意してください。これにより、精度がさらに高くなります。
    multiply(xseconds_since_epoch, nanoseconds_per_second,
                  &nps_temp_hi,
                  &nps_temp_lo);
    
    nanoseconds_since_epoch_lo = nps_temp_lo >> 20;
    nanoseconds_since_epoch_hi = nps_temp_hi << (64 ? 20);
    
    nanoseconds_since_epoch =
              nanoseconds_since_epoch_hi | nanoseconds_since_epoch_lo;

注目すべき点は、計算のほとんどの部分で、count_start および count_end 変数に保存される tb_update_count の値が変更されたことによる影響を受けないようにされていることです。これによって、tb_to_xs 変数と stamp_xsec 変数から読み出した値の一貫性が保証されます。これらの変数の値は、オペレーティング・システムが更新頻度の変更を検出した場合、あるいはオペレーティング・システムが頻度の変更を開始した場合に変わるためです。

Linux libc ライブラリーでは、tb_update_count の更新方法、そしてその値の解釈方法について、以下のように説明しています。

これらの変数を更新するコードは、まず tb_update_count をインクリメントしてから両方の変数を更新し、その後もう一度 tb_update_count をインクリメントします。つまり、このコードは tb_update_count を読み出し、次に 2 つの変数を読み出し、それから tb_update_count をもう一度読み出すということです。コードはこの動作を、tb_update_count の 2 回の読み出し値が同じ偶数値になるまで繰り返します。これにより、2 つの変数の一貫性が確実になります (引用については、「参考文献」を参照)。

さらに、tb_update_count は TBレジスターのオーバーフローを検出するためにも使用されます。オーバーフローが発生した場合は、同じプロトコルに従います。つまり、tb_update_count が更新される一方、残りの変数に必要な変更が反映されます。このようなシナリオを検出するのは、オペレーティング・システムの役目です。

最後に興味深い点として触れておきますが、64 ビットのナノ秒値は、約 585 年分の経過時間を表現できます。


サポート関数としての乗算

上記の Time Base 計算の実装では、アルゴリズムがヘルパー乗算関数を使用します。乗算のオペランドは 64 ビットの値なので、乗算結果は128 ビットの数値になります。この結果は C 言語では単一の変数で表現できません。そのため、この乗数関数は結果を 2 つの異なる出力パラメーターで返します。

この関数は、以下のように実装されます。

リスト 6. 最適化された 64 ビットの乗算関数
void multiply (U64 val1, U64 val2, U64 *res_hi, U64 *res_lo)
{
U64 half1, half2;

/* Even though we use 32 bits here, the compiler needs 64-bit
registers */
U64 half1_lo, half1_hi;

/* Higher bits of val 1 */
U64 val1_hi = (val1 >> 32) & 0xFFFFFFFF;

/* Lower bits of val 1 */
U64 val1_lo = val1 & 0xFFFFFFFF;

/* Higher bits of val 2*/
U64 val2_hi = (val2 >> 32) & 0xFFFFFFFF;

/* Lower bits of val 2*/
U64 val2_lo = val2 & 0xFFFFFFFF;

U64 mult1          = val1_lo * val2_lo;
U64 mult1_overflow = ((mult1 >> 32) & 0xFFFFFFFF);
U64 mult2          =
val1_hi * val2_lo + val2_hi * val1_lo + mult1_overflow;
U64 mult2_overflow = ((mult2 >> 32) & 0xFFFFFFFF);

half1_lo = (mult1 & 0xFFFFFFFF);
half1_hi = (mult2 & 0xFFFFFFFF);

half1    = (half1_hi << 32) | half1_lo;
half2    = val1_hi * val2_hi + mult2_overflow;

*res_hi = half2;
*res_lo = half1;

関数は、val1val2 という 2 つの 64 ビット入力値を受け取ります。この 2 つの値はさらに hi と low に二分され、その結果、val1_hival1_loval2_hi、および val2_lo という値になります。乗算は以下のように行われます。

表 1
Xval1_hival1_lo
val2_hival2_lo
val1_hi x val2_hi + mult2_overflowval1_hi x val2_lo + val2_hi x val1_lo + mult1_overflowval1_lo x val2_lo
half 2mult2mult1
half1

考え方としては、10 進数の乗算アルゴリズムと同じです。

積の下半分の下の部分は、val1_loval2_lo を掛けた結果で、これは mult1 と呼ばれます。下半分の上の部分は mult2 で、これは val1_hival2_lo の積に val2_hival1_lo の積を加えた値です。また、mult2 には mult1 乗算からのオーバーフローも加算されます。

mult2 mult1 の値を連結すると、結果の下半分の 64 ビット、つまり half1 になります。

上半分の half2 は、val1_h1val2_hi を掛けた結果で、この積には mult2 からのオーバーフローが加算されます。

この他に、乗算 アセンブリー命令を使用するという方法もあります。

リスト 7. multiply 関数のアセンブリー言語バージョン
void multiply (U64 val1, U64 val2, U64 *high, U64 *low)
{
U64 h;
U64 l;
__asm__ __volatile__("mulhdu %[h],%[val1],%[val2]" :
[h] "=r" (h) : [val1] "g" (val1), [val2] "g" (val2));
__asm__ __volatile__("mulld %[l],%[val1],%[val2]" :
[l] "=r" (l) : [val1] "g" (val1), [val2] "g" (val2));

*high = h;
*low = l;
}

ただし、上記のアルゴリズムによってもたらされるパフォーマンスは、純粋な C 言語でのパフォーマンスには及びません。IBM XL C コンパイラーは非常に優れたオプティマイザーであるため、C言語アルゴリズムは結果的に、最適化されていない単純なアセンブリー言語の実装よりも優れたパフォーマンスを実現します。

アセンブリー言語で可能なバリエーションは他にもありますが (乗算命令の代わりにシフトと加算を使用するなど)、この記事の適用範囲ではありません。


Time Base 手法の利点

Time Base Register を使用したナノ秒計算の実装には、以下の 2 つの利点があります。

  • パフォーマンス次のセクションに記載する実験結果からわかるように、この記事で説明した手法では、単純に gettimeofday を呼び出す場合に比べて大幅に速度が向上します。
  • 精度: gettimeofday の精度はマイクロ秒に固定されています。結果をナノ秒で表現するには、1000 を掛ける必要があるため、精度が損なわれてしまいます。一方、TimeBase の実装では、結果はすでにナノ秒になっています。いずれの実装にしても、適切な除算演算を使えばミリ秒精度を簡単にサポートすることができます。

実験的評価

このセクションでは、3 種類のアルゴリズムでのパフォーマンスの結果を紹介します。すべてのテストは IBM XL C コンパイラーを使って最適化レベル-O3 でコンパイルし、p630 POWER4+™ マイクロプロセッサーで稼働中の RHEL Linux で実行しました。

比較したアルゴリズムは以下のとおりです。

  • tb: 上記で説明したナノ秒計算の実装です。
  • tb_libc: TB レジスターを使用した gettimeofday の libc 実装です。ただし、スタンドアロン・プログラムに再コンパイルされています (一部の Linux 実装は、このアルゴリズムを使用します)。
  • gtod: gettimeofday の呼び出しです。

図 1 で、実行時間 (マイクロ秒単位) と呼び出し回数を比較します。

図 1. 実行時間 (マイクロ秒単位) と呼び出し回数
図 1. 実行時間 (マイクロ秒単位) と呼び出し回数

上記のグラフを見るとわかるように、この記事で紹介した実装の処理時間が最も早く、再コンパイルした libc 実装と同じように増加しています。

tb アルゴリズムでの速度は tb_libc と比べると 20% 改善され、gtod と比べると 300% も改善されています。

gettimeofday インターフェースを使用すると、かなりのパフォーマンス・ヒットが生じ、スケーラビリティーも大幅に低くなります。この劣化の原因の 1 つとしては、Linuxlibc ライブラリーが適切な最適化レベルでコンパイルされていないことが考えられます。


まとめ

要約すると、PowerPC コア (Cell/B.E. のバリエーションも含め) は、高い精度で、しかも素早くスケーラブルに経過時間を測定するのに有益なハードウェア機能を提供します。この類のコードが活躍するアプリケーションの例としては、個別のイベントのタイムスタンプを取る必要がある高負荷トランザクション・サーバーや、メッセージ・データに時刻を組み込んで時刻に対する依存性をデータにもたせる暗号化アプリケーションが挙げられます。

参考文献

学ぶために

製品や技術を入手するために

  • alphaWorksCell Broadband Engine ダウンロードにアクセスしてください。IBM の完全システム・シミュレーター、サポート・ライブラリー、ツール・チェーン、ライブラリーのソース・コード、そしてサンプルが用意されています。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=245798
ArticleTitle=64 ビット Linux での Power Architecture の Time Base Register
publish-date=04042007