私は10,000の要素を600,000回追加するループ(宿題として)を最適化しています。最適化が行われない時間は23.34秒〜、私の目標はBの場合は7秒未満、Aの場合は5秒未満に達することです。ループ分割はコードを遅くします
このように、最初に最適化を開始しました。
これにより、実行時間が約6.4秒に短縮されます(さらに展開すると約6になります)。
私は、読み書きの依存関係の時間を節約するために、サブサムの追加と最終的な合計を試してみることにしました。このようなコードが思いつきました。
int j;
for (j = 0; j < ARRAY_SIZE; j += 8) {
sum0 += array[j] + array[j+1];
sum1 += array[j+2] + array[j+3];
sum2 += array[j+4] + array[j+5];
sum3 += array[j+6] + array[j+7];
は、しかし約6.8秒
にこの増加ランタイムは、私は、ポインタを使用して、同様の手法を試してみましたが、私は何ができる最高は約15秒でした。
これは私が稼働しているマシン(学校が購入したサービスなので)は、Red Hatを実行していると思われる32ビットのリモートIntelベースのLinux仮想サーバーです。
私はコードを高速化するために考えられるすべての手法を試しましたが、それらはすべて逆の効果を持つようです。誰かが私が間違っていることを詳しく説明できますか?または、ランタイムを低下させるために使用できる別のテクニックですか?先生ができる最高のものは約4.8秒でした。
追加の条件として、完成したプロジェクトに50行以上のコードを入れることはできません。そのため、複雑な作業は不可能です。ここで
が
#include <stdio.h>
#include <stdlib.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
// double sum0 = 0;
// double sum1 = 0;
// double sum2 = 0;
// double sum3 = 0;
// ... and this one.
// Please change 'your name' to your actual name.
printf("CS201 - Asgmt 4 - ACTUAL NAME\n");
for (i = 0; i < N_TIMES; i++) {
// You can change anything between this comment ...
int j;
for (j = 0; j < ARRAY_SIZE; j += 8) {
sum += array[j] + array[j+1] + array[j+2] + array[j+3] + array[j+4] + array[j+5] + array[j+6] + array[j+7];
}
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
}
// You can add some final code between this comment ...
// sum = sum0 + sum1 + sum2 + sum3;
// ... and this one.
return 0;
}
両方のソースの完全なコピーである砕きコード
#include <stdio.h>
#include <stdlib.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
double sum0 = 0;
double sum1 = 0;
double sum2 = 0;
double sum3 = 0;
// ... and this one.
// Please change 'your name' to your actual name.
printf("CS201 - Asgmt 4 - ACTUAL NAME\n");
for (i = 0; i < N_TIMES; i++) {
// You can change anything between this comment ...
int j;
for (j = 0; j < ARRAY_SIZE; j += 8) {
sum0 += array[j] + array[j+1];
sum1 += array[j+2] + array[j+3];
sum2 += array[j+4] + array[j+5];
sum3 += array[j+6] + array[j+7];
}
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
}
// You can add some final code between this comment ...
sum = sum0 + sum1 + sum2 + sum3;
// ... and this one.
return 0;
}
答えは、我々はグレードを判断するために使用する「時間」アプリケーションが少しありますビットオフ。私ができる最善のことは、ループを50回展開し、TomKarzesの基本フォーマットを使って以下のようにグループ化することで4.9〜でした。
int j;
for (j = 0; j < ARRAY_SIZE; j += 50) {
sum +=(((((((array[j] + array[j+1]) + (array[j+2] + array[j+3])) +
((array[j+4] + array[j+5]) + (array[j+6] + array[j+7]))) +
(((array[j+8] + array[j+9]) + (array[j+10] + array[j+11])) +
((array[j+12] + array[j+13]) + (array[j+14] + array[j+15])))) +
((((array[j+16] + array[j+17]) + (array[j+18] + array[j+19]))))) +
(((((array[j+20] + array[j+21]) + (array[j+22] + array[j+23])) +
((array[j+24] + array[j+25]) + (array[j+26] + array[j+27]))) +
(((array[j+28] + array[j+29]) + (array[j+30] + array[j+31])) +
((array[j+32] + array[j+33]) + (array[j+34] + array[j+35])))) +
((((array[j+36] + array[j+37]) + (array[j+38] + array[j+39])))))) +
((((array[j+40] + array[j+41]) + (array[j+42] + array[j+43])) +
((array[j+44] + array[j+45]) + (array[j+46] + array[j+47]))) +
(array[j+48] + array[j+49])));
}
「B」と「A」とは何ですか? – pvg
これは意味をなさない。パフォーマンスに影響を与えてもそれほど劇的ではないだろう。 –
これは、現代のCPUがベクトル操作を最適化する方法に起因する可能性があります。 – Will