パタヘネの”第3章:コンピュータにおける算術演算”にある、3.3乗算の補足説明です。
“乗算は、ハードウェア的には、前述した加算処理とシフト処理で実装できる”を確認するために、Cでコードを作成しました。
当然ながら、乗算命令が下記のような形でソフトウェア的に実装されているというわけではないです。
下記のような振る舞いを行う”電子回路が組まれる”という意味だけど、
回路的として説明すると分かり辛いので、説明としてコードとして記述しただけです。
#include <stdio.h> main() { int a = 11; int b = 12; // int c = multi( a, b ); int c = multi_by_shift( a, b ); printf( "c=%d\n", c ); } //------------------------------------------------- // 普通に掛け算を行う //------------------------------------------------- int multi( int a, int b ) { return a * b; } //------------------------------------------------- // 加算とシフト命令だけで、掛け算を行う //------------------------------------------------- int multi_by_shift( int multiplicand, int multiplier ) { // 値の初期化 int product = 0; // 積 //-------------------------------------------- // multiplicandを全ビット処理するまで繰り返し //-------------------------------------------- int loop = 0; for ( loop = 0; loop < 32; loop++ ) { // 最下位ビットを取り出す int t0 = multiplicand & 0x0001; // 最下位ビットが立っていたら、乗数を足しこむ int t1 = (t0 == 0) ? 0 : multiplier; product += t1; // for debug printf( "loop[%02d] 0x%02x 0x%08x -> %3d %3d\n", loop, t0, multiplier, t1, product ); // 被乗数をシフト(次の処理対象ビットをずらす) multiplicand >>= 1; // 乗数をシフト(桁上げを行う) multiplier <<= 1; } return product; } |
基本的な考えかた上記の通りだが、この形のままでCPU設計を行うと、掛け算にかかる処理時間が非常に長くなってしまう。
なので、通常はここからさらに最適化を行う。
方法の1つは、0～31bit分シフトされた値を一気に求めて、同時に2つづつ足しこみを行う。
そうするとビット数がnの場合の計算量が O(n)から O(log n)に減少する。
(一方でH/W的には、たくさんの加算器を用意する必要があるが、最近のトランジスタは十分に小さいので無視できるレベル)
また、下記はx86環境のアセンブリ(gccで生成したもの。本当はmipsのコードが欲しかったけど、環境がないのであきらめた。
multiは”imull”命令で乗算しているけど、_multi_by_shiftでは乗算命令がなくなっている。
_multi:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
imull 12(%ebp), %eax
popl %ebp
ret
.section .rdata,"dr"
.align 4
_multi_by_shift
pushl %ebp
movl %esp, %ebp
subl $56, %esp
movl $0, -12(%ebp)
movl $0, -16(%ebp)
movl $0, -16(%ebp)
jmp L4
L7:
movl 8(%ebp), %eax
andl $1, %eax
movl %eax, -20(%ebp)
cmpl $0, -20(%ebp)
je L5
movl 12(%ebp), %eax
jmp L6
L5:
movl $0, %eax
L6:
movl %eax, -24(%ebp)
movl -24(%ebp), %eax
addl %eax, -12(%ebp)
movl -12(%ebp), %eax
movl %eax, 20(%esp)
movl -24(%ebp), %eax
movl %eax, 16(%esp)
movl 12(%ebp), %eax
movl %eax, 12(%esp)
movl -20(%ebp), %eax
movl %eax, 8(%esp)
movl -16(%ebp), %eax
movl %eax, 4(%esp)
movl $LC1, (%esp)
call _printf
sarl 8(%ebp)
sall 12(%ebp)
addl $1, -16(%ebp)
L4:
cmpl $31, -16(%ebp)
jle L7
movl -12(%ebp), %eax
leave
ret |
関連記事
コメントを残す