0

次のコードスニペットを検討してください

double *x, *id;
int i, n; // = vector size

// allocate and zero x
// set id to 0:n-1

for(i=0; i<n; i++) {  
  long iid = (long)id[i];
  if(iid>=0 && iid<n && (double)iid==id[i]){
    x[iid] = 1;
  } else break;
}

このコードはid、typeのvectorの値をvectorへのdoubleインデックスとして使用しますx。インデックスが有効であるためには、インデックスが0以上、ベクトルサイズn未満であり、に格納されているdoubleidが実際には整数であることを確認します。この例idでは、1からnまでの整数を格納するため、すべてのベクトルに線形にアクセスし、ifステートメントの分岐予測が常に機能するはずです。

コードの場合n=1e8、私のコンピューターでは0.21秒かかります。計算上軽量なループのように思われるので、メモリ帯域幅に制限があると思います。ベンチマークされたメモリ帯域幅に基づいて、0.15秒で実行されると予想しています。idメモリフットプリントは、値ごとに8バイト、値ごとに16バイトとして計算しxます（SSEストリーミングは使用されていないと想定しているため、書き込みとメモリからの読み取りの両方が必要です）。したがって、ベクトルエントリごとに合計24バイトです。

質問：

  • このコードはメモリ帯域幅を制限する必要があり、改善できると言っているのは間違っていますか？
  • そうでない場合は、メモリの速度で動作するようにパフォーマンスを向上させる方法を知っていますか？
  • それとも、すべてが正常で、並行して実行する以外に簡単に改善することはできませんか？

のタイプを変更することはオプションでidはありません-それはオプションでなければなりませんdouble。また、一般的なケースidでは、xサイズが異なり、別々の配列として保持する必要があります。これらは、プログラムのさまざまな部分から取得されます。要するに、境界チェックと型キャスト/整数検証をより効率的な方法で書くことが可能かどうか疑問に思います。

便宜上、コード全体は次のとおりです。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static struct timeval tb, te;

void tic()
{
  gettimeofday(&tb, NULL);
}

void toc(const char *idtxt)
{
  long s,u;
  gettimeofday(&te, NULL);
  s=te.tv_sec-tb.tv_sec;
  u=te.tv_usec-tb.tv_usec;
  printf("%-30s%10li.%.6li\n", idtxt, 
     (s*1000000+u)/1000000, (s*1000000+u)%1000000);
}

int main(int argc, char *argv[])
{
  double *x  = NULL;
  double *id = NULL;
  int i, n;

  // vector size is a command line parameter
  n = atoi(argv[1]);
  printf("x size %i\n", n);

  // not included in timing in MATLAB
  x = calloc(sizeof(double),n);
  memset(x, 0, sizeof(double)*n);

  // create index vector
  tic();
  id  = malloc(sizeof(double)*n);
  for(i=0; i<n; i++) id[i] = i;
  toc("id = 1:n");

  // use id to index x and set all entries to 4
  tic();
  for(i=0; i<n; i++) {  
    long iid = (long)id[i];
    if(iid>=0 && iid<n && (double)iid==id[i]){
      x[iid] = 1;
    } else break;
  }
  toc("x(id) = 1");
}
4

2 に答える 2

1

編集:配列を分割できない場合は無視してください!

一般的なキャッシュの概念を利用することで改善できると思います。時間または場所のどちらかでデータ アクセスを近づけることができます。タイトな for ループを使用すると、データ構造を for ループのように整形することで、データのヒット率を向上させることができます。この場合、2 つの異なる配列にアクセスし、通常は各配列の同じインデックスにアクセスします。あなたのマシンは、そのループを反復するたびに両方の配列のチャンクをロードしています。各ロードの使用を増やすには、各配列の要素を保持する構造体を作成し、その構造体で単一の配列を作成します。

struct my_arrays
{
    double x;
    int id;
};

struct my_arrays* arr = malloc(sizeof(my_arrays)*n);

これで、データをキャッシュにロードするたびに、配列が互いに接近しているため、ロードしたすべてのものにヒットします。

編集:あなたの意図は整数値をチェックすることであり、値が十分に小さく、精度を損なうことなく double で正確に表現できるという明示的な仮定をしているので、比較は問題ないと思います。

私の以前の回答には、暗黙的なキャスト後に大きな double を比較することに注意するための参照が ありました。

于 2012-11-26T12:45:23.120 に答える
0

double型表現の検討を検討する価値があるかもしれません。

たとえば、次のコードは、double1 より大きい数値を 999と比較する方法を示しています。

bool check(double x)
{
    union
    {
        double d;
        uint32_t y[2];
    };
    d = x;
    bool answer;
    uint32_t exp = (y[1] >> 20) & 0x3ff;
    uint32_t fraction1 = y[1] << (13 + exp); // upper bits of fractiona part
    uint32_t fraction2 = y[0]; // lower 32 bits of fractional part
    if (fraction2 != 0 || fraction1 != 0)
        answer = false;
    else if (exp > 8)
        answer = false;
    else if (exp == 8)
        answer = (y[1] < 0x408f3800); // this is the representation of 999
    else
        answer = true;
    return answer;
}

これは多くのコードのように見えますが、(SSE などを使用して) 簡単にベクトル化できます。また、境界が 2 のべき乗である場合は、コードがさらに単純化される可能性があります。

于 2012-11-26T17:28:42.157 に答える