2014年12月31日
ソフトウェアパイプラインの手書きをDRYで行う
ソフトウェアパイプライン (SWPL) を、Don’t Repeat Yourself で書くというお話です。
サンプルとして次のプログラムを考えます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define NUM_DATA 8 #define TRACE(i, c) trace(i, c) void trace(int i, char c) { for (int j = 0; j < 2*i; ++j) putchar(' '); putchar(c); putchar('\n'); } int main(int argc, char** argv) { int input[NUM_DATA]; int output[NUM_DATA]; // Initialize for (int i = 0; i < NUM_DATA; ++i) { input[i] = i; } <span style="color: red;"> <span style="color: blue;">// Target Loop { int r1, r2; for (int i = 0; i < NUM_DATA; ++i) { r1 = input[i]; TRACE(i, 'L'); r2 = r1 + r1; TRACE(i, 'C'); output[i] = r2; TRACE(i, 'S'); } }</span></span> // Test for (int i = 0; i < NUM_DATA; ++i) { int v = 2 * input[i]; if (output[i] != v) { fprintf(stderr, "Error: i=%d: %d != %d\n", i, output[i], v); return 1; } } return 0; } |
入力を2倍して出力するだけのプログラムです。
Target Loop の部分を変更して、SWPLを実装します。
実行順がわかりやすいように、TRACE でログを出力しています。
次のように、行で実行順、桁でループのiの値、文字で Load, Calc, Store のどれを行ったかを表すチャートが出力されます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
L C S L C S L C S L C S L C S L C S L C S L C S |
SWPL化の準備として、i==0 の時の実行だけ、ループの外に出しましょう。
同じ処理を2回書くのはいやなので、マクロにしてしまいます。
ついでに、Load, Calc, Store のどのパートを実行するか、マクロの引数で切り替えられるようにしましました(今回は1行を1つのパートにに分けましたが、実戦的には、複数行を1つのパートにしたり、パート数も3とは限らず必要に応じて設定したりします)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Target Loop { #define BODY(i, L, C, S) BODY_((i), (L), (C), (S)) #define BODY_(i, L, C, S) \ if (L) { \ r1 = input[i]; TRACE(i, 'L'); \ } \ if (C) { \ r2 = r1 + r1; TRACE(i, 'C'); \ } \ if (S) { \ output[i] = r2; TRACE(i, 'S'); \ } \ /* end of macro */ int r1, r2; int i = 0; if (i < NUM_DATA) { BODY(i, 1, 0, 0); /*L=1*/ BODY(i, 0, 1, 0); /*C=1*/ BODY(i, 0, 0, 1); /*S=1*/ for (++i; i < NUM_DATA; ++i) { BODY(i, 1, 0, 0); /*L=1*/ BODY(i, 0, 1, 0); /*C=1*/ BODY(i, 0, 0, 1); /*S=1*/ } } #undef BODY #undef BODY_ } |
i==0 の処理をループの外に出しただけなので、実行しても TRACE の出力結果は変わっていません。
それでは、
各iのStore処理を、i+1のLoad処理の後ろに移動してSWPLしましょう。マクロの定義は変わりません。
1 2 3 4 5 6 7 8 9 10 11 |
int r1, r2; int i = 0; if (i < NUM_DATA) { BODY(i, 1, 1, 0); /*L=1, C=1*/ for (++i; i < NUM_DATA; ++i) { BODY(i, 1, 0, 0); /*L=1*/ <span style="color: blue;">BODY(i-1, 0, 0, 1); /*S=1*/</span> BODY(i, 0, 1, 0); /*C=1*/ } <span style="color: blue;">BODY(i-1, 0, 0, 1); /*S=1*/</span> } |
S=1 の行を移動させました。移動後の文脈ではiの値が増えているので、-1しています。なお、i==0の時のL=1, C=1は、2行に分ける必要がないのでまとめまています。
TRACEの結果は…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
L C L S C L S C L S C L S C L S C L S C L S C S |
きれいにSWPL化されました。