6

最初の質問:

私たちのグループ (電子工学の学生 - 英国) は、最近、PIC16F84A マイクロコントローラーのプログラミングに取り組んでいます。2 つの 8 ビット数を乗算する必要が生じましたが、それぞれの最小値/最大値は不明です。同級生は、次のアイデアを提示しました。

multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
    clrf    OutH            ; clear all non-input variables
    clrf    OutL
mult_loop
    bcf     STATUS,c        ; clear carry bit
    movfw   Num2
    addwf   OutL            ; add Num2 to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH            ; if set, increment OutH
    decfsz  Num1            ; decrement Num1
    goto    mult_loop       ; if Num1 is not zero, repeat loop
    return                  ; else return

これは、コード行数としては非常に短いですが、数が多い場合は実行に比較的長い時間がかかる可能性があると感じました。私は自分で少し考えて、1 つの数値を右にシフトし、もう 1 つの数値を左にシフトし、途中で左にシフトした数値を出力に一定回数追加して、最終的な答え。私はそれを正しく行っていませんでしたが、SOに関するこの質問に出くわしたため、入力数値の1つを次のように表現するというアイデアが得られました。

N = a_0 + a_1*2 + a_2*2^2 + a_3*2^3 + ... + a_7*2^7

その出発点から、2 つの 8 ビット数を乗算して 16 ビット出力 (2 つの 8 ビット レジスタに格納) を得るこの方法を思いつきました。

multiply_numbers:
; Takes numbers in Num1 and Num2L, and returns product in OutH:OutL
    clrf    Num2H           ; clear all non-input variables
    clrf    OutL
    clrf    OutH
mult_loop
    btfsc   Num1,0          ; test LSB of Num1
    call    add_num16       ; if set, add Num2H:Num2L to OutH:OutL
    call    shift_left      ; shift Num2H:Num2L left (multiply by 2)
    rrf     Num1,f          ; shift Num1 right
    clrw                    ; clear working register (0x00)
    bcf     STATUS,z        ; clear zero bit (3) of the STATUS register
    addwf   Num1,w          ; add 0x00 to Num1
    btfss   STATUS,z        ; if Num1 is zero, then exit loop
    goto    mult_loop       ; else, continue with another iteration
    return
add_num16
    movfw   Num2H
    addwf   OutH,f          ; add Num2H to OutH
    bcf     STATUS,c        ; clear carry bit (0) of the STATUS register
    movfw   Num2L
    addwf   OutL,f          ; add Num2L to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH,f          ; increment OutH if set (OutL overflowed)
    return
shift_left
    bcf     STATUS,c        ; clear carry bit
    rlf     Num2L,f         ; rotate Num2L left (carry -> LSB, MSB -> carry)
    rlf     Num2H,f         ; rotate Num2H left, using carry bit from Num2L
    return

この 2 番目の例は、ループが最大 256 回ではなく最大 8 回しか繰り返されないという理由だけで、ほとんどの場合より高速であると思います。

相対速度/効率の私の仮定は正しいですか? コードの 2 番目のブロックは実際に意図したとおりに機能しますか (見落としている潜在的な問題はありますか)。最後に、この乗算は、まだ採用されていない手法を使用してさらに最適化できますか?

前もって感謝します。

PS すべての変数/レジスタは、独自のアドレスで適切に定義されています。広範なコード コメントは、将来参照できる一連のルーチンをコンパイルしようとしているからであり、何が起こっているのか、その理由が一目でわかります。

PPS この質問は、この写真をプログラミングすることへの個人的/趣味的な関心に関連しており、現在のコースワークなどとは何の関係もありません。

マイコン: PIC16F84A
開発環境: MPLABX IDE v1.10
コンパイラ: mpasm (v5.43)

編集＃1：

  • Num1 の LSB をテストし、左シフトされた Num2H:Num2L を OutH:OutL に追加する代わりに、Num1 の MSB をテストし、Num2 を左シフトされた OutH:OutL に追加します。
  • 呼び出されたサブ関数ではなく、'shift_left' をインラインにします。
  • 'mult_loop' をアンロールして、8 回目の反復を最適化します。

方法 2 の改善:

multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
    clrf    OutL            ; clear all non-input variables
    clrf    OutH
; 1st iteration
    btfsc   Num1,7          ; test MSB of Num1
    call    add_num8        ; if set, add Num2 to OutH:OutL
    bcf     STATUS,c        ; clear carry bit
    rlf     OutL,f          ; rotate OutL left (carry -> LSB, MSB -> carry)
    rlf     OutH,f          ; rotate OutH left, using carry bit from OutL
    rlf     Num1,f          ; shift Num1 left
; 2nd iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 3rd iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 4th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 5th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 6th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 7th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 8th iteration
    btfss   Num1,7          ; test MSB of Num1
    return                  ; if not set, then return. else...
add_num8
    bcf     STATUS,c        ; clear carry bit (0) of the STATUS register
    movfw   Num2
    addwf   OutL,f          ; add Num2L to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH,f          ; increment OutH if set (OutL overflowed)
    return
4

2 に答える 2

5

はい。これを行うための古典的な「トリック」がたくさんあります。

まず、乗数が 2 の累乗の和として解釈できることを知っていれば、被乗数ビットがゼロ以外の場合に乗数を巧妙に乗数に追加するだけです。

第 2 に、追加される値は被乗数のサイズのみです。16 (部分および) 最終製品が必要ですが、16 ビットの追加を行う必要はありません。8ビットの加算を行い、キャリーを伝播できます。これは通常、アセンブラで簡単に実行できます。

時間を短縮するために、ループの途中で呼び出して ADD ルーチンを実行したくありません。コードをインライン化して、呼び出しと戻りにかかる時間を節約し、レジスタ シャッフルを最適化します。最後に、ちょうど 8 回ループします。このようなループを 8 回アンロールして、カウンターのオーバーヘッドを回避し、カウンターをいじる必要があるために発生する「レジスタープレッシャー」を下げて、最適化の自由度を高めることは価値があります。

PIC コントローラについては何も述べていないことに注意してください。実際、PIC コントローラの命令セットについては知りません。しかし、私が言ったことは、8 ビットの乗算を実装するすべての人に関係があります。(16、32、および 64 ビットの乗算には同等のトリックがあります)。したがって、次のコードを抽象的に記述できます。

 mul16: // computes M1 * M2 --> P where M1 and M2 are 8 bit values, P is 16 bits
        // P is represent by Plow and Phigh 8 bit values.
        // reset the (partial) product
        Plow=0; Phigh=0; // all 16 bits 
       // First iteration:          
       if msb(M1)==1 then { Plow+=M2; if carry then Phigh++; /* propagate carry */ }
       shift M1 left bit;
       shift (Phigh,Plow) left one bit
       // Second iteration
            <same as first>
       <3rd ..7th iteration, same as first>
       // 8th iteration
        if msb(M1)==1 then { Plow+=M2; if carry then Phigh++ }
       // dont bother: shift M1 left bit;
       // dont bother: shift (Phigh,Plow) left one bit   
       <done>

"if msb(M1)..." および "shift M1 left one bit" と書かれているものは、多くの場合、アセンブリ言語の "shift left" 命令を使用して簡単に実装できることに気が付くかもしれません。 -} 同様に、「キャリーの場合 ... 1 を加算」は、多くの場合、「キャリーの加算」命令で実装されます。

これを PIC 用に再コーディングするのはあなたに任せます。

于 2012-05-21T01:37:53.657 に答える
4

なんてこった。私は約 30 年間、アセンブラで乗算コードを書いていません。これは、6502 アセンブラで Apple II のコードを書いていた時代にさかのぼります。

2番目のアプローチの方がはるかに高速であることは間違いありません。8回の追加と8回のシフトは、最大256回の追加よりもはるかに高速です.

しかし、私はあなたがそれを後ろに持っていると思います。

num1 の MSB から開始し、そのビットが 1 の場合、結果に num2 を追加します。num1 の LSB 以外の各ビットの後、結果を 1 だけ左にシフトします。

于 2012-05-21T02:27:26.280 に答える