SSブログ
English Version

Z80での高速な乗算処理 [Z80]

 Twitter のタイムラインで見かけた


  (x+y)^2 - (x-y)^2 = 4*x*y  
  ⇒ x*y = ((x+y)^2 - (x-y)^2) / 4  
 

の等式を利用し、テーブルを使って二乗計算を速く行うことで乗算処理を高速にできる・・と言うことがずっと頭の片隅に残っていました。
 時間もあるので少し検討してみたいと思います。以降上記の手法をプラマイ二乗法と記します。

  1. プラマイ二乗法の検討
     8bit の二乗は最大で 16bit になるので二乗の結果を収めた 512 バイトのテーブルが必要になります。上位バイトと下位バイトを必ずペアでアクセスするので上位アドレスの使い回しができるように下位バイトのテーブルと上位バイトのテーブルに分けました。
     コードを考える上で問題となるのが (x + y) が最大 9 ビットになることです。9 ビットになった場合、MSBとそれ以外の 8 ビットを分離して処理しようとすると


       (2^8 + x)^2  
      = 2^16 + 2^8*2*x + x*x  
      = 2^16 + 2^9*x + x*x  
     

    となり、x の二乗を求めた後に 9 bit シフトして加算する必要があり、その後 4 で割るので 18 ビットの演算が必要になります。
     場合分けしてもできそうですが、面倒になる根源は x+y という項があることです。そこで 加算の二乗を使わない方法を考えてみました。


  2. マイナス二乗法
  3.  上記のようにプラスの項が処理を面倒にする原因なので下記のようにマイナスの二乗のみを使ってみることにしました。二乗の回数が1つ増えますが二乗計算はテーブル引きなので低コストで処理出来ます。この手法をマイナス二乗法と呼ぶことにします。


       (x - y)^2 = x^2 -2*x*y + y^2  
      ⇒ x*y = (x^2 + y^2 - (x - y)^2) / 2  
     

     アセンブラで書いたソースが下記になります。それほど最適化していないのでまだのりしろがあると思います。

    今回考案したマイナス二乗法での乗算処理(Z80アセンブラ)
    ; unsigned 8 bits fast multi(my method) ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 016C 7D FMul8: LD A,L ; 4 016D BB CP E ; 4 016E 30 02 JR NC,FMul10 ; 12/7 0170 EB EX DE,HL ; 4 0171 7D LD A,L ; 4 0172 26 03 FMul10: LD H,HIGH MULTBL+1 ; 7 0174 46 LD B,(HL) ; 7 0175 25 DEC H ; 4 0176 4E LD C,(HL) ; 7 0177 93 SUB E ; 4 0178 6F LD L,A ; 4 0179 79 LD A,C ; 4 017A 96 SUB (HL) ; 7 017B 4F LD C,A ; 4 017C 24 INC H ; 4 017D 78 LD A,B ; 4 017E 9E SBC A,(HL) ; 7 017F 47 LD B,A ; 4 0180 6B LD L,E ; 4 0181 56 LD D,(HL) ; 7 0182 25 DEC H ; 4 0183 7E LD A,(HL) ; 7 0184 81 ADD A,C ; 4 0185 6F LD L,A ; 4 0186 78 LD A,B ; 4 0187 8A ADC A,D ; 4 0188 1F RRA ; 4 0189 67 LD H,A ; 4 018A CB 1D RR L ; 8 018C C9 RET ; 10 ; Max 154 = 4+4+(7+4+4)+7+7+4+7+4+4+4+7+4+4+4+7+4+4+7+4+7+4+4+4+4+4+4+8+10  ; Min 151 = 4+4+(12)+7+7+4+7+4+4+4+7+4+4+4+7+4+4+7+4+7+4+4+4+4+4+4+8+10 ; Ave 152.5 ORG ($ + 255) AND 0FF00H ; 8bit ^ 2 table 0200 MULTBL: 0200 00 01 04 09 DB 000H,001H,004H,009H,010H,019H,024H,031H ; low byte 0204 10 19 24 31 0208 40 51 64 79 DB 040H,051H,064H,079H,090H,0A9H,0C4H,0E1H 020C 90 A9 C4 E1 0210 00 21 44 69 DB 000H,021H,044H,069H,090H,0B9H,0E4H,011H 0214 90 B9 E4 11 0218 40 71 A4 D9 DB 040H,071H,0A4H,0D9H,010H,049H,084H,0C1H 021C 10 49 84 C1 0220 00 41 84 C9 DB 000H,041H,084H,0C9H,010H,059H,0A4H,0F1H 0224 10 59 A4 F1 0228 40 91 E4 39 DB 040H,091H,0E4H,039H,090H,0E9H,044H,0A1H 022C 90 E9 44 A1 0230 00 61 C4 29 DB 000H,061H,0C4H,029H,090H,0F9H,064H,0D1H 0234 90 F9 64 D1 0238 40 B1 24 99 DB 040H,0B1H,024H,099H,010H,089H,004H,081H 023C 10 89 04 81 0240 00 81 04 89 DB 000H,081H,004H,089H,010H,099H,024H,0B1H 0244 10 99 24 B1 0248 40 D1 64 F9 DB 040H,0D1H,064H,0F9H,090H,029H,0C4H,061H 024C 90 29 C4 61 0250 00 A1 44 E9 DB 000H,0A1H,044H,0E9H,090H,039H,0E4H,091H 0254 90 39 E4 91 0258 40 F1 A4 59 DB 040H,0F1H,0A4H,059H,010H,0C9H,084H,041H 025C 10 C9 84 41 0260 00 C1 84 49 DB 000H,0C1H,084H,049H,010H,0D9H,0A4H,071H 0264 10 D9 A4 71 0268 40 11 E4 B9 DB 040H,011H,0E4H,0B9H,090H,069H,044H,021H 026C 90 69 44 21 0270 00 E1 C4 A9 DB 000H,0E1H,0C4H,0A9H,090H,079H,064H,051H 0274 90 79 64 51 0278 40 31 24 19 DB 040H,031H,024H,019H,010H,009H,004H,001H 027C 10 09 04 01 0280 00 01 04 09 DB 000H,001H,004H,009H,010H,019H,024H,031H 0284 10 19 24 31 0288 40 51 64 79 DB 040H,051H,064H,079H,090H,0A9H,0C4H,0E1H 028C 90 A9 C4 E1 0290 00 21 44 69 DB 000H,021H,044H,069H,090H,0B9H,0E4H,011H 0294 90 B9 E4 11 0298 40 71 A4 D9 DB 040H,071H,0A4H,0D9H,010H,049H,084H,0C1H 029C 10 49 84 C1 02A0 00 41 84 C9 DB 000H,041H,084H,0C9H,010H,059H,0A4H,0F1H 02A4 10 59 A4 F1 02A8 40 91 E4 39 DB 040H,091H,0E4H,039H,090H,0E9H,044H,0A1H 02AC 90 E9 44 A1 02B0 00 61 C4 29 DB 000H,061H,0C4H,029H,090H,0F9H,064H,0D1H 02B4 90 F9 64 D1 02B8 40 B1 24 99 DB 040H,0B1H,024H,099H,010H,089H,004H,081H 02BC 10 89 04 81 02C0 00 81 04 89 DB 000H,081H,004H,089H,010H,099H,024H,0B1H 02C4 10 99 24 B1 02C8 40 D1 64 F9 DB 040H,0D1H,064H,0F9H,090H,029H,0C4H,061H 02CC 90 29 C4 61 02D0 00 A1 44 E9 DB 000H,0A1H,044H,0E9H,090H,039H,0E4H,091H 02D4 90 39 E4 91 02D8 40 F1 A4 59 DB 040H,0F1H,0A4H,059H,010H,0C9H,084H,041H 02DC 10 C9 84 41 02E0 00 C1 84 49 DB 000H,0C1H,084H,049H,010H,0D9H,0A4H,071H 02E4 10 D9 A4 71 02E8 40 11 E4 B9 DB 040H,011H,0E4H,0B9H,090H,069H,044H,021H 02EC 90 69 44 21 02F0 00 E1 C4 A9 DB 000H,0E1H,0C4H,0A9H,090H,079H,064H,051H 02F4 90 79 64 51 02F8 40 31 24 19 DB 040H,031H,024H,019H,010H,009H,004H,001H 02FC 10 09 04 01 0300 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H ; high byte 0304 00 00 00 00 0308 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H 030C 00 00 00 00 0310 01 01 01 01 DB 001H,001H,001H,001H,001H,001H,001H,002H 0314 01 01 01 02 0318 02 02 02 02 DB 002H,002H,002H,002H,003H,003H,003H,003H 031C 03 03 03 03 0320 04 04 04 04 DB 004H,004H,004H,004H,005H,005H,005H,005H 0324 05 05 05 05 0328 06 06 06 07 DB 006H,006H,006H,007H,007H,007H,008H,008H 032C 07 07 08 08 0330 09 09 09 0A DB 009H,009H,009H,00AH,00AH,00AH,00BH,00BH 0334 0A 0A 0B 0B 0338 0C 0C 0D 0D DB 00CH,00CH,00DH,00DH,00EH,00EH,00FH,00FH 033C 0E 0E 0F 0F 0340 10 10 11 11 DB 010H,010H,011H,011H,012H,012H,013H,013H 0344 12 12 13 13 0348 14 14 15 15 DB 014H,014H,015H,015H,016H,017H,017H,018H 034C 16 17 17 18 0350 19 19 1A 1A DB 019H,019H,01AH,01AH,01BH,01CH,01CH,01DH 0354 1B 1C 1C 1D 0358 1E 1E 1F 20 DB 01EH,01EH,01FH,020H,021H,021H,022H,023H 035C 21 21 22 23 0360 24 24 25 26 DB 024H,024H,025H,026H,027H,027H,028H,029H 0364 27 27 28 29 0368 2A 2B 2B 2C DB 02AH,02BH,02BH,02CH,02DH,02EH,02FH,030H 036C 2D 2E 2F 30 0370 31 31 32 33 DB 031H,031H,032H,033H,034H,035H,036H,037H 0374 34 35 36 37 0378 38 39 3A 3B DB 038H,039H,03AH,03BH,03CH,03DH,03EH,03FH 037C 3C 3D 3E 3F 0380 40 41 42 43 DB 040H,041H,042H,043H,044H,045H,046H,047H 0384 44 45 46 47 0388 48 49 4A 4B DB 048H,049H,04AH,04BH,04CH,04DH,04EH,04FH 038C 4C 4D 4E 4F 0390 51 52 53 54 DB 051H,052H,053H,054H,055H,056H,057H,059H 0394 55 56 57 59 0398 5A 5B 5C 5D DB 05AH,05BH,05CH,05DH,05FH,060H,061H,062H 039C 5F 60 61 62 03A0 64 65 66 67 DB 064H,065H,066H,067H,069H,06AH,06BH,06CH 03A4 69 6A 6B 6C 03A8 6E 6F 70 72 DB 06EH,06FH,070H,072H,073H,074H,076H,077H 03AC 73 74 76 77 03B0 79 7A 7B 7D DB 079H,07AH,07BH,07DH,07EH,07FH,081H,082H 03B4 7E 7F 81 82 03B8 84 85 87 88 DB 084H,085H,087H,088H,08AH,08BH,08DH,08EH 03BC 8A 8B 8D 8E 03C0 90 91 93 94 DB 090H,091H,093H,094H,096H,097H,099H,09AH 03C4 96 97 99 9A 03C8 9C 9D 9F A0 DB 09CH,09DH,09FH,0A0H,0A2H,0A4H,0A5H,0A7H 03CC A2 A4 A5 A7 03D0 A9 AA AC AD DB 0A9H,0AAH,0ACH,0ADH,0AFH,0B1H,0B2H,0B4H 03D4 AF B1 B2 B4 03D8 B6 B7 B9 BB DB 0B6H,0B7H,0B9H,0BBH,0BDH,0BEH,0C0H,0C2H 03DC BD BE C0 C2 03E0 C4 C5 C7 C9 DB 0C4H,0C5H,0C7H,0C9H,0CBH,0CCH,0CEH,0D0H 03E4 CB CC CE D0 03E8 D2 D4 D5 D7 DB 0D2H,0D4H,0D5H,0D7H,0D9H,0DBH,0DDH,0DFH 03EC D9 DB DD DF 03F0 E1 E2 E4 E6 DB 0E1H,0E2H,0E4H,0E6H,0E8H,0EAH,0ECH,0EEH 03F4 E8 EA EC EE 03F8 F0 F2 F4 F6 DB 0F0H,0F2H,0F4H,0F6H,0F8H,0FAH,0FCH,0FEH 03FC F8 FA FC FE

     参考として、テーブルを使わない一般的な乗算処理は下記のようになるのではないかと思います。

    一般的な unsigned 8 ビットの乗算処理(Z80アセンブラ)
    ; unsigned 8 bits normal multi(normal method) ; E <- data0 ; L <- data1 ; HL -> data0 * data1 018D 65 NMul: LD H,L ; 4 018E 2E 00 LD L,0 ; 7 0190 55 LD D,L ; 4 0191 06 08 LD B,8 ; 7 0193 29 NMul10: ADD HL,HL ; 11 0194 30 01 JR NC,NMul20 ; 12/7 0196 19 ADD HL,DE ; 11 0197 10 FA NMul20: DJNZ NMul10 ; 13/8 0199 C9 RET ; 10 ; Max 363 = 4+7+4+7+((11+(7+11)+13)*8-13+8)+10 ; Max 315 = 4+7+4+7+((11+(12)+13)*8-13+8)+10 ; Ave 339


  4. 各方式の比較
     冒頭で紹介した Twitter メッセージには URL も書いてあったのでプラマイ二乗法の処理を確認して見ました。
     二乗テーブルの持ち方は前項で書いたマイナス二乗法と同じですね。x+y が 9 bit になった場合の対処として偶数と奇数の場合に場合分けして処理していました。処理のステート数については「CPC Cycles: 136-172 (154 on average)」と書いてあります。
     三つの方式のステート数の一覧が下表になります。

    No.MethodMaxMinAverage
    1Normal method363315   339.0
    2Minus square method154151   152.5
    3Plamai square method172136   154.0
    ★変更 2023/02/13 Normal method のステート数を修正

     今回作ったマイナス二乗法ノーマル処理の約2倍の速さと言うことになります。
     ネットにあったプラマイ二乗法の処理を下に示しますが、ステート数を数えると Max:158, Min:129, Ave:143.5 になります。
     下記のソースでは引数とリターン値を入れるレジスタのアサインを不自然に感じますが、本来の処理は引数とリターン値を入れるレジスタがリーズナブルな物であり、その分のステート数を加えたものが上記の表内の数値になるのかもしれません(マイナス二乗法でもリターン値をHLに揃えなくてもよければそれだけで数ステート短くなります)。

    ★追記 202/02/19 {
     プラマイ二乗法CPCWiKi に追加される際の議論を見つけました。この中でシフト命令等を変更してより高速化されています。最終ソースのステート数が異なるのはこの為かも知れません。
    }

    ネットで公開されていた高速乗算処理(Z80アセンブラ)
    ; Web version finded in Internet ; A,B <- data0,data1 ; A:E -> data0*data1 019A B8 IMul: cp b ; 4 019B 30 03 jr nc,l1 ; 12/7 019D 5F ld e,a ; 4 019E 78 ld a,b ; 4 019F 43 ld b,e ; 4 01A0 4F l1: ld c,a ; 4 01A1 90 sub b ; 4 01A2 1F rra ; 4 01A3 57 ld d,a ; 4 01A4 79 ld a,c ; 4 01A5 80 add a,b ; 4 01A6 1F rra ; 4 01A7 6F ld l,a ; 4 01A8 26 02 ld h,high(MULTBL) ; 7 01AA 7E ld a,(hl) ; 7 01AB 5D ld e,l ; 4 01AC 6A ld l,d ; 4 01AD 30 0F jr nc,l2 ; 12/7 01AF 96 sub (hl) ; 7 odd 01B0 6B ld l,e ; 4 01B1 5F ld e,a ; 4 01B2 24 inc h ; 4 loads high(sqrhi) 01B3 7E ld a,(hl) ; 7 01B4 6A ld l,d ; 4 01B5 9E sbc a,(hl) ; 7 01B6 57 ld d,a ; 4 01B7 7B ld a,e ; 4 01B8 80 add a,b ; 4 01B9 5F ld e,a ; 4 01BA 7A ld a,d ; 4 01BB CE 00 adc a,0 ; 7 01BD C9 ret ; 10 01BE 96 l2: sub (hl) ; 7 even 01BF 6B ld l,e ; 4 01C0 5F ld e,a ; 4 01C1 24 inc h ; 4 01C2 7E ld a,(hl) ; 7 01C3 6A ld l,d ; 4 01C4 9E sbc a,(hl) ; 7 01C5 C9 ret ; 10 ; Max 158 = 4+(7+4+4+4)+4+4+4+4+4+4+4+4+7+7+4+4+(7+7+4+4+4+7+4+7+4+4+4+4+4+7+10) ; Min 129 = 4+(12)+4+4+4+4+4+4+4+4+7+7+4+4+(12+7+4+4+4+7+4+7+10) ; Ave 143.5


  5. 応用編
     8 ビットの高速な乗算処理ができたので「GAME言語での ASCIIART の高速化」の記事で書いた ASCIIART に適用してみました。
     先の記事では 16 ビットの固定小数点の乗算処理を作って高速化しましたが、今回は手抜きをして次の方法で 8 ビット乗算で 16 ビット乗算を作ってみました。


      (256*x1 + x0)*(256*y1 + y0)
      = 2^16*x1y1 + 2^8*(x0*y1 + x1*y0) + x0*y0
     

     従来のアセンブラで書いた ASCIIART(asciiar2)を実行後に、今回の乗算処理を組み込んだ ASCIIART(fasciiar)を実行した画面が、下図になります。実行環境は Z80 が 12MHz で動作している環境です。

     TeraTerm のマクロで実行時間を計測した結果も表示されていますが、それを見ると実行時間はほぼ同じ(寧ろ若干遅くなっている)ですね。16 ビット化するための上記の展開式の処理のオーバーヘッドが元々の 2 倍速を食いつぶしてしまったようです。

    ★追記 2023/02/17 {
     上記で使用した固定小数点演算では 2byte x 2byte の結果の 4byte の中央の 2byte のみ必要なため、内部では 24 bit の計算をしているので通常のオーバーフロー無しの乗算処理(結果が 32 bit)よりは速いものです。
    }

     それにしても意外だったのは新乗算処理を組み込んだ後、一発で ASCIIART が表示されたことです。気分のいいところでそろそろ筆を置きたいと思います。

    ASCIIART 実行結果


★追記 2023/02/15
 「Z80での高速な乗算処理(その2)最適化」の記事に最適化して更に高速化したことについて記載しました。


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]

nice!(0)  コメント(0) 
共通テーマ:趣味・カルチャー

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。