IKM の構成

動作させることができる．加算器にもまたライブラリとして提供されている加算器 (DW01 add) を利用した．

演算中のデータを保存する PPG Buffer には全ての演算器と入力端子に専用の I/O ポートを用意した．また，書き込みは同期的に，読み出しは非同期的に行うよう に設計した．PPG Buffer の容量は，データのビット長，エントリ数，演算器の個数 に依存する．データのビット長については，基本ビット長に加え，部分積の演算過程 で発生する桁上げを保存するだけの長さが必要である．部分積の演算中に発生する 桁上げを保存するために必要なビット長は再帰の回数が1 回増えるごとに 1 ビット 増える．エントリ数は部分積の数に依存し，部分積の数もまた再帰の回数に依存す る．再帰の回数が 1 回増えるごとに部分積の数は 3 倍になるため，エントリもそれ に対応した数が必要になる．ただし，演算器の数を増やすとより効率のよい演算が可 能になるため，再帰の回数が増えた場合でもエントリ数の増加を抑えることは可能で ある．

本実装では，基本ビット長が 16 で再帰の回数が 2 である場合，18 ビットのエン トリが 10 個必要となる．

ACC の設計

ACCは，加減算器とバッファ (ACC Buffer) で構成され，PPG で生成された部 分積を積算する．構成を図4.14に示す．用いる加減算器の数は，1 個の部分積に対

pp

+ + + + ACC

Buffer

High order Low order

図4.14 ACC の構成

して同時に行うことができる演算数を考慮して 4 とした．これは，表4.8において，

1 行で行う最大の演算数に合わせたものである．設計によっては，より多くの加減算 器を用いる構成も考えられる．加減算器は今までと同様にライブラリとして提供さ れている加減算器 (DW01 addsub) を用いた．

ACC Buffer のI/O ポートは PPG Buffer と同様に演算器および入力端子ごとに 専用のものを用意した．ACC 内部では符号付き演算が行われるため，符号ビットが 必要である．さらに，ACC 内部のビット長は加算による桁上げのために再帰の回数

が 1 回増えるごとに 2 (= dlog₂3e)ずつ増える．ACC Buffer の容量は部分積の数 と演算器の個数に依存し，本実装では，基本ビット長が 16 で，再帰回数が 2である 場合，21 ビットのエントリが 18 個必要となる．

CP の設計

CP は，加算器とレジスタ (Carry Register)で構成され，ACC で積算された係数 (2 回再帰の場合は式(4.20)のp0 から p7) を受け取り，順次桁上げを行うモジュー ルである．構成は図4.15のようになる．CP モジュールは，入力された値の下位 n

Carry Register

+

MUX 0

Sign Extend

High order

P

Low order

図4.15 CP の構成

ビットとそれより上位のビットを分離して，上位のビットを Carry Registerに保存 し次のサイクルで入力される一つ上位の係数に加算する．ただし，最下位項 p0 に対 する桁上げはないので，この場合は 0 を加算する．

CTRL の設計

CTRL モジュールは PPG，ACC，CP モジュールに対して，適切なタイミング で制御信号を送るモジュールである．代表的な制御信号の種類として，PPG Buffer や ACC Buffer に対する読み書きアドレスや Write Enable，ACC 内の加減算器に 対する加減算選択信号，CP 内で最下位項に対して 0 を加算することを指示する信 号がある．以下では，本実装における 2 回再帰の場合を例としてより具体的な制御 の内容を述べる．

CTRL による制御のもとで，PPGは表4.11に示すようなスケジュールで演算を 行う．表は，1個の乗算器と 2 個の加算器について，入力のタイミングと出力結果が 利用可能となるタイミングを示す．

ACC も同様に，CTRL モジュールによる制御のもとで表 4.12,4.13に示すスケ ジュールで演算を行う． 表中の部分積に付けられた添字 L と H は，それぞれ，各 部分積の下位 n ビットとそれ以外の上位ビットを意味する．CP に関しては，最下 位項である p0 が入力されたときに加算すべき桁上げとして 0 を選択するマルチプ

表4.11 R2IKMの PPGにおけるスケジューリング

Multiplier1 Adder1 Adder2

Step Input Input Output Input Output Input Output

1 a0, b0 − − − − − −

2 a₁, b₁ a₀, b₀ − − − − −

3 a₂, b₂ a₁, b₁ − a₁, a₀ − b₁, b₀ − 4 a3, b3 a2, b2 − a2, a0 a10 b2, b0 b10

5 − a₃, b₃ − a₃, a₁ a₂₀ b₃, b₁ b₂₀

6 − a₁₀, b₁₀ − a₃, a₂ a₃₁ b₃, b₂ b₃₁ 7 − a20, b20 − a20, a31 a32 b20, b31 b32

8 − a31, b31 a0b0(=pp0) − a2031 − b2031

9 − a₃₂, b₃₂ a₁b₁(=pp1) − − − −

10 − a₂₀₃₁, b₂₀₃₁ a₂b₂(=pp2) − − − −

11 − − a3b3(=pp3) − − − −

12 − − a10b10(=pp4) − − − −

13 − − a₂₀b₂₀(=pp5) − − − −

14 − − a31b31(=pp6) − − − −

15 − − a32b32(=pp7) − − − −

16 − − a₂₀₃₁b₂₀₃₁(=pp8) − − − −

レクサを制御する．

ACCとCPの演算は，それぞれ先行する PPGと ACC での演算が完了する前に 開始することができる．つまり，ACC はPPGが 8ステップ目に到達した時点で最 初の部分積 pp0 を受け取ることが可能なので，これに合わせて演算を開始する．ま た，ACC の演算において，最後に求まる係数の中で最も下位の係数は p3 である．

この p3 はACC の 17ステップ目に出力されるため，p0 から p2はこれに先行して 順次 CP に入力することができる．したがって，積 P は乗数 A と 被乗数 B の最 下位桁 a0 と b0 を入力した時点から，(8-1)+(17-1)+4=27 ステップ後に得られる．

表4.12 R2IKMの ACCにおけるスケジューリング (1/2)

Adder-Subtracter1 Adder-Subtracter2 Step Input Input Output Input Output

1 pp0 - - -

-2 pp1 p0,pp0L - p1,pp0L

-3 pp2 p1,pp0H p0+pp0L p2,pp0H p1-pp0L 4 pp3 p1,pp1L p1+pp0H p2,pp1L p2-pp0H 5 pp4 p2,pp1H p1-pp1L p3,pp1H p2+pp1L 6 pp5 p2,pp2L p2-pp1H p3,pp2L p3+pp1H 7 pp6 p3,pp2H p2-pp2L p4,pp2H p3+pp2L 8 pp7 p3,pp3L p3-pp2H p4,pp3L p4+pp2H 9 pp8 p4,pp3H p3+pp3L p5,pp3H p4-pp3L 10 - p1,pp4L p4+pp3H p3,pp4L p5-pp3H 11 - p2,pp5L p1+pp4L p3,pp5L p3-pp4L 12 - p3,pp5H p2+pp5L p4,pp5H p3-pp5L 13 - p3,pp6L p3+pp5H p4,pp6L p4-pp5H 14 - p4,pp6H p3-pp6L p5,pp6H p4+pp6L 15 - p3,pp7L p4-pp6H p5,pp7L p5+pp6H 16 - p3,pp8L p3-pp7L p4,pp8H p5+pp7L

17 - - p3+pp8L - p4+pp8H

表4.13 R2IKMの ACCにおけるスケジューリング (2/2)

Adder-Subtracter3 Adder-Subtracter4 Step Input Input Output Input Output

1 pp0 − − − −

2 pp1 p2, pp0L − p3, pp0L −

3 pp2 p3, pp0H p2−pp0L p4, pp0H p3 +pp0L 4 pp3 p3, pp1L p3−pp0H p4, pp1L p4 +pp0H 5 pp4 p4, pp1H p3 +pp1L p5, pp1H p4−pp1L 6 pp5 p4, pp2L p4 +pp1H p5, pp2L p5−pp1H 7 pp6 p5, pp2H p3 +pp2L p6, pp2H p4−pp2H 8 pp7 p5, pp3L p5 +pp2H p6, pp3L p6−pp2H 9 pp8 p6, pp3H p5−pp3L p7, pp3H p6 +pp3L 10 − p2, pp4H p6−pp3H p4, pp4H p7 +pp3H

11 − − p2 +pp4H − p4−pp4H

12 − − − − −

13 − − − − −

14 − − − − −

15 − p4, pp7H − p6, pp7H −

16 − − p4−pp7H − p6 +pp7H

17 − − − − −