HP 35s でプログラミング - 3

前回 RTA に必要な ceil() が実装出来たので、RTA 本体を実装してみようと思う。
RTA に関する詳細な説明は
https://dspace.jaist.ac.jp/dspace/bitstream/10119/13748/5/paper.pdf
の定義1, 例2に譲るとして、ここでは最低限 RTA の定義とアルゴリズムを簡単に説明するに留める。
RTA は以下で定義される:

C_i, T_j はタスクの実行時間と周期で、予め与えられる。R_i が応答時間であるが、右辺と左辺両方に出てくるので式が成り立つまで R_i の値を変えて試す必要がある(C_i, または C_i + R_i-1 から始め、1づつインクリメントすれば良い)。RTA は NP 困難のクラスに属することが証明されているが、疑似多項式時間で計算可能で非力な HP 35s でもそこそこ動いてくれると信じたいところ。

まずは前述の式を C 言語で実装してみる。

int
rta( int i, int Ri )
{
    int r;
    int j;

    r = C[i];
    for ( j = 0; j <= (i - 1); j++ ) {
        r += ceil( Ri / (T[j] + 0.0) ) * C[j];
    }
    if ( r == Ri ) {
        return Ri;
    } else {
        return rta( i, Ri + 1 );
    }
}

C, Tグローバル変数である。
こいつを

    C[0] = 1; T[0] = 5;     // タスク 0 の実行時間 = 1, 周期= 5
    C[1] = 2; T[1] = 8;     // タスク 1 の実行時間 = 2, 周期= 8
    C[2] = 3; T[2] = 10;    // タスク 2 の実行時間 = 3, 周期= 10

    R[0] = rta( 0, C[0] );
    R[1] = rta( 1, C[1] );
    R[2] = rta( 2, C[2] );

のようなコードで呼び出すと、R[0] = 1, R[1] = 3, R[2] = 7 が得られる。
次に、このコードを HP 35s での実装を意識して、多少変えてみる。再帰を使っているのをループ展開にし、さらに i, j といった HP 35s で特別な意味を持つ変数の使用をやめ、それぞれ y と l に置き換える。Ri は R で使うので、小文字 r は x に置き換えた。

int
rta( int y, int Ri )
{
    int x;
    int l;

    while ( 1 ) {
        x = C[y];
        for ( l = 0; l <= (y - 1); l++ ) {
            x += ceil( Ri / (T[l] + 0.0) ) * C[l];
        }
        if ( x == Ri ) {
            return Ri;
        }
        Ri++;
    }
}

HP 35s では変数 I と J にアドレス(に相当するもの)を代入すると、(I)、(J) でそのアドレス(に相当するもの)の値を読み書き出来る。ループ制御変数に I や J を使うことで配列への高速なアクセスを可能にする、ことを狙ったものと思われるが、どうもループ制御変数の使い勝手が私的にしっくりこなくて、今回はループ制御変数(すなわち ISG, DSE 命令)は使わなかった。
C, Tグローバル変数なので、C を 116 番地?131 番地に、T を 132 番地?147 番地に配置する。これらのアドレスへ、前述の

    C[0] = 1; T[0] = 5;
    C[1] = 2; T[1] = 8;
    C[2] = 3; T[2] = 10;

を設定するには

; C[0]
116
STO I
1
STO (I)
; C[1]
117
STO I
2
STO (I)
...

とすれば良い。

さて、HP 35s での RTA の実装である。便宜上、ラベルをアルファベットで付けたのと、適宜コメントを入れてある。

A001 : LBL A
; Memory Usage:
; R[] ... 100 .. 115
; C[] ... 116 .. 131
; T[] ... 132 .. 147
;
; function rta( y, Ri ) ;; xreg ... y, yreg ... Ri
;   output
;       xreg ... Response Time of Task #y
;       yreg ... y
;
;   register usage :
;       Y for target task #
;       R for Ri
;       D for initial value of C[y]
;       X for actual response time calculated from Ri
;       L, M for loop control
A002 : STO Y
A003 : 116
A004 : +
A005 : STO I
A006 : R_dw
A007 : STO R
;
A008 : RCL (I)
A009 : STO D
;
; while ( 1 )
; LBL' A
;
; X = C[y]
A010 : RCL D
A011 : STO X
;
; set L as loop counter
; set M as finish value ( y - 1 )
A012 : 0
A013 : STO L
A014 : RCL Y
A015 : 1
A016 : -
A017 : STO M
;
; retrieve C[] from I, T[] from J respectively
A018 : 116
A019 : STO I
A020 : 132
A021 : STO J
;
; for ( l = 0; l <= (y - 1); l++ ) {
; LBL' C
A022 : RCL M   ; Yreg
A023 : RCL L   ; Xreg
A024 : X>Y?
A025 : GTO A048		;LBL' D
;
; x += ceil( Ri / (T[l] + 0.0) ) * C[l];
A026 : RCL R
A027 : RCL (J)
A028 : /
A029 : XEQ B001 ; ceil
A030 : RCL (I)
A031 : *
A032 : X
A033 : +
A034 : STO X
;
; increment I, J, L
A035 : RCL I
A036 : 1
A037 : +
A038 : STO I
A039 : LAST X
A040 : RCL J
A041 : +
A042 : STO J
A043 : 1
A044 : RCL L
A045 : +
A046 : STO L
A047 : GTO A022		;LBL' C
;
; LBL' D
; if ( x == Ri ) {
A048 : RCL X
A049 : RCL R
A050 : X=Y?
A051 : GTO A053		;LBL' E
A052 : GTO A061		;LBL' F
; LBL' E
;
A053 : 100
A054 : RCL Y
A055 : +
A056 : STO I
A057 : X<>Y
A058 : STO (I)
A059 : LAST X
A060 : RTN
; LBL' F
;
; increment Ri and retry
A061 : 1
A062 : +
A063 : STO R
A064 : GTO A010		;LBL' A

計64行だが、チェックサムは 0AB4、LN は 207 になった。正直、ハンドアセンブルデバッグするのは相当しんどかった。
実行するには、前述した C と T をしかるべき値に設定ののち、引数を Ri, y の順にスタックに積んでやらなければならない。例えば C 言語で

    R[0] = rta( 0, 1 );

とやっていたのは、以下のようにして呼び出す:

1
ENTER
0
XEQ A

実行が終了すると 1 が X レジスタに返される。同様に、

    R[2] = rta( 2, 3 );

を計算するには

3
ENTER
2
XEQ A

7 が得られるのに4秒ほどかかった。
冒頭で紹介した論文の例2では、4つのタスクセットに対して RTA を求めているが、HP 35s では R_4 の計算に 12 秒ほど。

もともと RTAHP 35s で実装しようと思った理由は、PC で計算させる際のオーバーヘッドを電卓なら上回ってくれるのでは、という淡い期待があったから。机のスペース(つまりキャッシュである)には限りがあり、もっぱら研究中その上を占めるのは方眼の計算用紙と印刷された論文、教科書等である。HP 35s での、超絶に面倒くさいタスクセットの定義(アドレス116 ?の設定)は、入力ヘルプ用のプログラムを書けばむしろ PC でエディタ編集するよりは早そうだし、何より電卓は小型で場所を取らない。
しかし、肝心の計算に10秒以上はしんどい。計算の開始を R_i-1 + C_i にするとか、R_i の増加を単純な線形ではなくする等、多少の工夫の余地はありそうだが、命令実行が絶対的に遅すぎる。タスクセットが 5 以上の世界では、焼石に水だろう。