caligue’s blog

■[programming][assembly language][C]サポートしているSIMD拡張を調べるプログラム

Intel AVX について勉強しているが、使っているCPUがどのSIMD拡張をサポートしているのかを知りたくなった。なので色々調べてインラインアセンブラを使ったコードを書いてみた。Sandy Bridge (Core i7 2600K)でAVXが使えることは確認できた。

// sup_ext.c
#include <stdio.h>

int main()
{
    int REG_edx, REG_ecx, REG_eax=-1;
    __asm__("mov eax, 1\n\t"
            "cpuid\n\t"
            "mov %0, edx\n\t"
            "mov %1, ecx\n\t"
            : "=r" (REG_edx), "=r" (REG_ecx)
           );
    if(REG_edx && 0x800000) printf("MMX ");         // EDX bit 23
    if(REG_edx && 0x2000000) printf("SSE ");        // EDX bit 25
    if(REG_edx && 0x4000000) printf("SSE2 ");       // EDX bit 26
    if(REG_ecx && 0x00000001) printf("SSE3 ");      // ECX bit 0
    if(REG_ecx && 0x00000200) printf("SSSE3 ");     // ECX bit 9
    if(REG_ecx && 0x00080000) printf("SSE4.1 ");    // ECX bit 19
    if(REG_ecx && 0x00100000) printf("SSE4.2 ");    // ECX bit 20
    if(REG_ecx && 0x00200000) printf("AESNI ");     // ECX bit 25
    if(REG_ecx && 0x00000002) printf("PCLMULQDQ "); // ECX bit 1

    __asm__("mov eax, 1\n\t"
            "cpuid\n\t"
            "and ecx, 402653184\n\t" // 0x01800000 = 402653184
            "cmp ecx, 402653184\n\t"
            "jne not_supported\n\t"
            "mov ecx, 0\n\t"
            "xgetbv\n\t"
            "and eax, 6\n\t"
            "cmp eax, 6\n\t"
            "mov %0, eax\n"
            "not_supported:\n\t"
            : "=r" (REG_eax)
           );
    if (REG_eax == 0x6)
        printf("AVX "); // EAX bit 1&2
    printf("\n");

    return 0;
}

コンパイル・コマンド

gcc -masm=intel sup_ext.c

参照

1. Introduction to Intel® Advanced Vector Extensions - Intel® Software Network
2. コンパイラー最適化入門： 第1回 SIMD 命令とプロセッサーの関係 | iSUS
3. GCCのインラインアセンブラの書き方 for x86 - OSのようなもの

Permalink | コメント(0) | トラックバック(0) | 15:04

■[algorithm]最短経路の距離行列から経路行列を構築するアルゴリズム

全点対最短経路問題(All-Pairs Shortest Paths Problem)において、Floyd-Warshall法などで最短経路の距離行列が求められている場合に、その最短距離行列から対応する経路行列を構築するアルゴリズムについてのメモ。アルゴリズムはO(n^3)のアルゴリズムで単純な実装ではFloyd-Warshall法と同程度の計算処理時間がかかる。以下はCによる実装例。

void construct_aps_path(const int n, const int **A, const int **D, int **P)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (D[i][j] == D[i][k]+A[k][j]) {
                    P[i*n+j] = k;
                    break;
                }
                if (k != n-1) {
                    P[i*n+j] = NIL;
                }
            }
        }
    }
}

nが問題サイズ、Aが入力距離行列、Dが最短経路の距離行列、Pは求める最短経路のpredecessor行列。初期条件等はCLRSの"Introduction to Algorithms"の"Constructing a shortest path"の項を参照(この問題はCLRSの演習問題にもなっている)。入力グラフによっては、Floyd-Warshall法の計算途上で経路行列も記録させた場合と結果が違うものになることもある。

Permalink | コメント(0) | トラックバック(0) | 08:05

■Google Site の Quick LaTeX ガジェットのテスト

Quick LaTeX ガジェットをサイト内に設置し、そのガジェットで数式を生成し、それをコピー＆ペーストすることで、Google Site で数式を使うことはできる。

テスト結果

Permalink | コメント(1) | トラックバック(0) | 20:10

■[Programming][C] Sun Ultra24 Workstation での GSL の CBLAS の SGEMM の性能

Sun Ultra 24 Workstation (プロセッサは Intel Core2Duo E8600 (3.3GHz)) で GSL (GNU Scientific Library) の CBLAS の SGEMM の性能を測った。

結果は以下図(行列サイズは16の倍数)。僕が実装したスカラーとブロックの行列乗算アルゴリズムと比較した(ブロックのは、8x8でブロック化)。時間があったら他のBLASも試す。

Permalink | コメント(0) | トラックバック(0) | 11:08

■[Ruby][Algorithm][SPOJ] 中置記法を後置記法に変換するプログラム

Sphere Online Judge (SPOJ) - Problem ONPを解くために書いたRubyのコードを、後々使えそうだからポストする。

$priority = [[['+',0],['-',1],['*',2],['/',3],['^',4]]]

def recur(s, idx)
  op_stack = Array.new
  p = idx
  while p < s.length
    c = s[p].chr
    case c
    when 'a'..'z'
      print c
    when '('
      p = recur(s, p+1)
    when ')'
      until op_stack.empty?
        print op_stack.pop
      end
      return p
    else
      while !op_stack.empty? && $priority[op_stack.last] > $priority[c]
        print op_stack.pop
      end
      op_stack.push c
    end
    p += 1
  end
  until op_stack.empty?
    print op_stack.pop
  end
end

T = gets.to_i
T.times do
  s = gets.chomp
  recur(s, 0)
  puts
end

Permalink | コメント(0) | トラックバック(0) | 20:20