64bits

linux で 64 ビット環境を構築。そして64ビットマルチプロセス対応プログラムを作る - 志を立てるのに、遅すぎることはない -- by ピカソ河

このまま記事を入力し[投稿する]ボタンを押せば当サイトに送信されます。 以下の文章は注意書きです。

名前はかならず記入してください。ハンドルネームでも構いません。 またパスワードを入力することをお勧めします。 その場合他人による *なりすまし* と区別出来るかもしれません。 さらにブラウザでクッキーを有効に設定してある場合あなたの記事は後で修正可能になります。

コメントスパム防止のため記事の内容を機械的にモデレート (スパムである確率を計算) する処理を通します。 どのような投稿であれ、たまたま計算誤差によりスパムとみなされ 秘密の場所 に収納される可能性があります。 その場合、管理人が手作業で正規の場所に移動しますのでお待ちください。

51  owa  2008/04/29 15:32 id: mJs8kxp1Zus  prob: 0.0%

AMD CPU エラッタ
http://pc.nikkeibp.co.jp/article/news/20080428/1001503/
B2 Stepping でのバグ
Phenom 9500/9600/9600 Black Edition、同X3 8400/8600、同X4 9100e
B3 Stepping では解消されているらしい
Phenom X4 9550/9650/9750/9850 Black Edition、同X3 8450/8650/8750

50  owa  2008/03/11 21:41 id: mJs8kxp1Zus  prob: 0.4%

C128クラスの更新
http://owa.as.wakwak.ne.jp/zope/docs/C/C128
getofs() - 追加: ビット位置を整数で返すメソッド
getbit() - 追加: 最下位ビットを返すメソッド。そのたび最下位ビットを0にする。
getlsb() - 更新: 高速化 (10%)

49  owa  2007/11/11 23:27 id: mJs8kxp1Zus  prob: 2.4%

C128クラスにLSB,MSB関数を追加
http://owa.as.wakwak.ne.jp/zope/docs/C/C128
上記128ビット型クラスに getlsb(), getmsb() を追加しました。

C128 C128::getlsb() const
{
    ULong x = -hi;
    if (lo)
        --x;
    return C128(lo & (-lo), hi & x);
}

C128 C128::getmsb() const
{
    ULong x = (hi)? hi: lo;
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    x &= ~(x >> 1);
    return (hi)? C128(0, x): C128(x);
}

48  owa  2007/11/09 23:30 id: mJs8kxp1Zus  prob: 1.3%

nasm 0.99 サンプルコード
sse レジスタにコピーして左に 8bits シフトするだけです。
64 ビット境界を越えてシフトされません。
----------------------------
bits 64
    section .text   
    global bitshift128
bitshift128
    movupd xmm0, [rdi]
    psllq xmm0, 8       ; shift left 8bits
    movq rax, xmm0
    psrldq xmm0, 8      ; shift right 8bytes
    movq rdx, xmm0
    ret
---------------------------

呼び出し側
void test3()
{
    struct U128 {unsigned long long lo, hi;} src;
    src.lo = 0x4444444488888888LL;
    src.hi = 0x1111111122222222LL;
    fprintf(stderr, "src=0x%016llx%016llx\n", src.hi, src.lo);
    U128 dst = bitshift128(&src);
    fprintf(stderr, "dst=0x%016llx%016llx\n", dst.hi, dst.lo);
}

実行結果
src=0x11111111222222224444444488888888
dst=0x11111122222222004444448888888800

参考サイト
http://www.cs.uaf.edu/2007/fall/cs301/support/x86_64/index.h...

47  owa  2007/11/09 22:50 id: mJs8kxp1Zus  prob: 0.1%

SSE の利用は難しい;;
ビット移動を伴う命令が 64bit までしか対応していないのかな (paddq, psubq, psllq, psrlq)。
バイト単位のシフトは pslldq, psrldq があるけど、ビットシフトを作るのは少し大変。
あまり汎用ロジック向けには作ってないってことでしょうか。

ただメモリ対128ビットレジスタ間のコピーは movupd, movntdq でダイレクトにできるようだし、
XOR, OR, AND, NOT は pxor, por, pand 使えばできることが解った。
いつか役に立つ日が来るかもしれない。

46  owa  2007/11/07 21:58 id: mJs8kxp1Zus  prob: 0.0%

SSE にはビットシフト命令が無い;;
http://web.mit.edu/nasm_v0.98/doc/nasm/html/nasmdoc0.html
あるのはバイト単位のシフト演算のみ。

とりあえず SSE 128bit レジスタに入れて出すだけのコード。(信用しないで!)
void test2()
{
    typedef struct {ULong lo; ULong hi;} U128;
    U128 m, n;
    m.hi = 0x1111111111111111;
    m.lo = 0x2222222222222222;
    n.hi = 0;
    n.lo = 0;
    __asm__ __volatile__ (
        "movq %2, %%xmm0;"
        "movq %3, %%xmm1;"
        "pslldq $8, %%xmm0;"
        "orps %%xmm0, %%xmm1;"
        "movq %%xmm1, %1;"
        "psrldq $8, %%xmm1;"
        "movq %%xmm1, %0;"
        : "=m"(n.hi), "=m"(n.lo)    // n is output operand (%0, %1)
        : "m"(m.hi), "m"(m.lo)      // m is input operand (%2, %3)
        : "%xmm0", "%xmm1"          // clobbered register
        );
    fprintf(stderr, "m=0x%016llx%016llx, n=0x%016llx%016llx\n", m.hi, m.lo, n.hi, n.lo);
}
実行結果は
m=0x11111111111111112222222222222222, n=0x11111111111111112222222222222222

128ビット空間を自由に使えるものだと思ってた。馬鹿ですね。
シフト演算はたし算 (とバイト単位のシフトも使う?) に置き換えればできるけど、どうなんだろう?
C/C++ の 64ビットx2 のデータではシフト演算のロジックが汚くなるので SSE まで逃げてきたんだけど、
GPU と連立組むのもアイディアのうちか。

参考サイト:
Optimizing MILC Math Routines with SSE
http://lqcd.fnal.gov/sse/
SSE2を用いたRC5-64クライアントの最適化に関する考察
http://www.katto.comm.waseda.ac.jp/~matsui/rc5/index.html
続 GeForce8800GTX と SM4.0 の整数演算
http://wlog.flatlib.jp/item/911/catid/6
NVIDIA CUDA Homepage
http://developer.nvidia.com/object/cuda.html

45  owa  2007/11/06 22:44 id: mJs8kxp1Zus  prob: 0.0%

インラインアセンブラの勉強
GCC Inline Assembler
http://caspar.hazymoon.jp/OpenBSD/annex/gcc_inline_asm.html
http://caspar.hazymoon.jp/OpenBSD/annex/gas.html
http://www.mars.sannet.ne.jp/sci10/on_gcc_asm.html

void test1()
{
    typedef unsigned long long ULong;
    ULong m = 0x1000100010001000;
    ULong n = 0x0111011101110111;
    ULong out = 0;
    __asm__ __volatile__ (
        "movq %1, %%rax;"
        "addq %2, %%rax;"
        "movq %%rax, %0;"
        : "=r"(out)         // 出力 (%0)
        : "r"(m), "r"(n)    // 入力 (%1, %2)
        : "%rax"            // 破壊されるレジスタ
        );
    fprintf(stderr, "m=0x%016llx, n=0x%016llx, out=0x%016llx\n", m, n, out);
}

コンパイル (gcc -m64) 後の実行結果は
m=0x1000100010001000, n=0x0111011101110111, out=0x1111111111111111

44  owa  2007/11/03 22:44 id: mJs8kxp1Zus  prob: 0.4%

ビット位置の計算
0.0065秒/100万 (gcc -O3 Athlon64x2 3800+ x86_64 vine seed) 
0.0146秒/100万 (gcc -O3 Athlon64x2 3800+ i386 vine 4.1) 

ただ1ビットだけ立ってる場合のオフセットを求める方法。
---
int offset_of_onebit1(unsigned long long x)
{
    int n = 0;
    if (x & 0xffffffff00000000LL) {
        n += 32;
        x >>= 32;
    }
    if (x & 0xffff0000) n += 16;
    if (x & 0xff00ff00) n += 8;
    if (x & 0xf0f0f0f0) n += 4;
    if (x & 0xcccccccc) n += 2;
    if (x & 0xaaaaaaaa) n += 1;
    return n;
}
---
n += 16 は n |= 16 でも同じ。むしろ若干遅くなる。
また以下のように if 文を無くしても処理速度は変わらない
---
int offset_of_onebit2(ULong x)
{
    int n = 0;
    (x & 0xffffffff00000000LL) && (n += 32) && (x >>= 32);
    (x & 0xffff0000) && (n += 16);
    (x & 0xff00ff00) && (n += 8);
    (x & 0xf0f0f0f0) && (n += 4);
    (x & 0xcccccccc) && (n += 2);
    (x & 0xaaaaaaaa) && (n++);
    return n;
}
---
環境によって違いはあるかも。

43  owa  2007/10/29 22:37 id: mJs8kxp1Zus  prob: 1.5%

ビットの連続抽出
0.230秒/100万 (gcc -O3 Athlon64x2 3800+ x86_64 vine seed)
0.513秒/100万 (gcc -O3 Athlon64x2 3800+ i386 vine 4.1)

ビット位置を一個ずつ取り出すイテレータ。
肝は bits & (-bits) で LSB (Least Significant Bit) が求められること。
---
#if defined(__x86_64__)
typedef unsigned long ULong;
#elif defined(__i386__)
typedef unsigned long long ULong;
#endif

class CBitPos {
    ULong bits;
public:
    CBitPos(ULong x) : bits(x) {}
    ULong next() {
        ULong x = bits & (-bits);
        bits &= ~x;
        return x;
    }
};
---

一回あたり44ビットONのデータで測定。つまり一個のイテレータで44回ループ処理した。
for (long i = 0; i < 1000000L; i++) {
    CBitPos a(0x7777777777773333LL);
    int pos = a.next();
    while (pos)
        pos = a.next();
}

ちなみに MSB (Most Significant Bit) を求める方法を用いると三倍くらい遅くなる。
---
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    x &= ~(x >> 1);
---

42  owa  2007/10/29 22:18 id: mJs8kxp1Zus  prob: 12.4%

ビット数のカウント
0.0085秒/100万 (gcc -O3 Athlon64x2 3800+ x86_64 vine seed)
0.0251秒/100万 (gcc -O3 Athlon64x2 3800+ i386 vine 4.1)

立ってるビットを数えるには隣同士の和を求めることを繰り返す。
---
int bitcount(unsigned long long x)
{
    x -= ((x >> 1) & 0x5555555555555555LL);
    x = (((x >> 2) & 0x3333333333333333LL) + (x & 0x3333333333333333LL));
    x = (((x >> 4) + x) & 0x0f0f0f0f0f0f0f0fLL);
    x += (x >> 8);
    x += (x >> 16);
    x += (x >> 32);
    return x & 0x0000007f;
}
---
参考サイト:
http://www.nminoru.jp/~nminoru/programming/bitcount.html
http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit
http://graphics.stanford.edu/~seander/bithacks.html