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

ソフトウェアパイプライン (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;
    }

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

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 の時の実行だけ、ループの外に出しましょう。
同じ処理を２回書くのはいやなので、マクロにしてしまいます。
ついでに、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_
    }

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*/
                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の結果は…

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化されました。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。