2014年12月31日

ソフトウェアパイプラインの手書きをDRYで行う

投稿者：koto、投稿日時：2014年12月31日18時26分

ソフトウェアパイプライン (SWPL) を、Don’t Repeat Yourself で書くというお話です。

サンプルとして次のプログラムを考えます。

#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;
}

#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;

}

// 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');

}

}

// 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 のどれを行ったかを表すチャートが出力されます。

SWPL化の準備として、i==0 の時の実行だけ、ループの外に出しましょう。
同じ処理を２回書くのはいやなので、マクロにしてしまいます。
ついでに、Load, Calc, Store のどのパートを実行するか、マクロの引数で切り替えられるようにしましました（今回は1行を1つのパートにに分けましたが、実戦的には、複数行を1つのパートにしたり、パート数も3とは限らず必要に応じて設定したりします）。

    // 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_
    }

// 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しましょう。マクロの定義は変わりません。

        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>
        }

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*/

BODY(i-1, 0, 0, 1); /*S=1*/

BODY(i, 0, 1, 0); /*C=1*/

}

BODY(i-1, 0, 0, 1); /*S=1*/

}

S=1 の行を移動させました。移動後の文脈ではiの値が増えているので、-1しています。なお、i==0の時のL=1, C=1は、２行に分ける必要がないのでまとめまています。
TRACEの結果は…