1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
#!/usr/bin/env python3
from tabulate import tabulate
import matplotlib
import matplotlib.pyplot as plt
# finds the two's compliment of a given number
def twos_comp(num, length):
if num == 0:
return 0
return abs((num ^ ((1 << length) - 1)) + 1)
# arithmaticlly shifts right; divides by 2
def arithmatic_shiftr(num, length, times):
for t in range(times):
num = (num >> 1) | ((1 << length - 1) & num)
return num
# arithmaticlly shifts left; multiplies by 2
def arithmatic_shiftl(num, length):
if num & (1 << length - 1):
return (num << 1) | (1 << length - 1)
else:
return (num << 1) & ~(1 << length - 1)
# only used for debugging function to allow python to natively use two's compliment numbers
def twoscomp_to_int(num, length):
if num & (1 << length - 1):
return (-1 * twos_comp(num, length))
return num & (1 << length) - 1
def debug(results):
headers = ['multiplicand bin', 'multiplier bin', 'multiplicand dec', 'multiplier dec', 'expected bin', 'expected dec', 'booth', 'mod booth']
table = []
for [multiplicand_bin, multiplier_bin, result_booth, result_booth_mod, length] in results:
multiplicand = twoscomp_to_int(multiplicand_bin, length)
multiplier = twoscomp_to_int(multiplier_bin, length)
expected = multiplicand * multiplier
expected_bin = (twos_comp(expected, length * 2), expected) [expected > 0]
success_b = [bin(result_booth), "PASS"] [result_booth == expected_bin]
success_bm = [bin(result_booth_mod), "PASS"] [result_booth_mod == expected_bin]
table.append([bin(multiplicand_bin), bin(multiplier_bin), multiplicand, multiplier, bin(expected_bin), expected, success_b, success_bm])
with open("report/debug_table.tex", "w") as f:
f.write(tabulate(table, headers, tablefmt="latex_longtable"))
print("\nCHECKS: \n", tabulate(table, headers), "\n")
def booth(multiplier, multiplicand, length):
operations = 0
multiplicand_twos_comp = twos_comp(multiplicand, length)
result = multiplier << 1 # extended bit
for i in range(length): # iteration count is size of one operand
op = result & 0b11
if op == 0b01:
operations += 1 # add upper half by multiplicand
result += multiplicand << (length + 1)
if op == 0b10:
operations += 1 # subtract upper half by multiplicand
result += multiplicand_twos_comp << (length + 1)
result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows
result = arithmatic_shiftr(result, (length * 2) + 1, 1)
result = result >> 1
return (result, operations)
def booth_mod(multiplier, multiplicand, length):
operations = 0
# extend workspace by *two* bits, MSB to prevent overflow when mult/sub by 2
multiplicand |= ((1 << length - 1) & multiplicand) << 1
multiplicand_twos_comp = twos_comp(multiplicand, length + 1)
result = multiplier << 1
for i in range(int((length) / 2)): # number of iterations is half the
op = result & 0b111
match op: # take action dependent on last two bits
case 0b010 | 0b001: # add upper half by multiplicand
print("add")
result += multiplicand << (length + 1)
case 0b011: # add upper half by 2x multiplicand
print("add * 2")
result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1)
case 0b100: # subtract upper half by 2x multiplicand
print("sub * 2")
result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1)
case 0b101 | 0b110: # subtract upper half my multiplicand
print("sub ")
result += multiplicand_twos_comp << (length + 1)
if op != 0b111 and op != 0:
operations += 1
result &= (1 << ((length * 2) + 2)) - 1 # get rid of any overflows
result = arithmatic_shiftr(result, (length * 2) + 2, 2)
# shifts the workspace right by one, while duplicating extra sign bit to second MSB, and clearing the MSB.
# this ensures the result length is 2x the operands.
result = ((result | ((1 << ((length * 2) + 2)) >> 1)) & ((1 << ((length * 2) + 1)) - 1)) >> 1
return (result, operations)
if __name__ == "__main__":
# set up headers for tables
result_headers = ['multiplicand', 'multiplier', 'result (bin)', 'result (hex)']
result_table = []
opcount_headers = ['multiplicand', 'multiplier', 'length', 'booth', 'modified booth']
opcount_table = []
lengths = []
ops_booth = []
ops_mod_booth = []
debug_results = []
# Reads operands from file.
# Each line needs to contain two operands in binary two's compliment form seperated by a space.
# Leading zeros should be appended to convey the length of operands.
# Operands must have the same size.
with open('input.txt') as f:
input_string = f.read().split('\n')
for operation in input_string:
if operation == '' or operation[0] == '#':
continue
length = len(operation.split(" ")[0])
multiplicand = int(operation.split(" ")[0], 2)
multiplier = int(operation.split(" ")[1], 2)
# get result and operation count of both algorithims
result_booth = booth(multiplier, multiplicand, length)
result_mod_booth = booth_mod(multiplier, multiplicand, length)
# gather data for matplotlib
ops_booth.append(result_booth[1])
ops_mod_booth.append(result_mod_booth[1])
lengths.append(length)
# gather data for report results table
result_table.append([bin(multiplicand), bin(multiplier), bin(result_booth[0]), hex(result_booth[0])])
# gather data for test function to check if simulator is working
debug_results.append([multiplicand, multiplier, result_booth[0], result_mod_booth[0], length])
# gather data for operation count table
opcount_table.append([bin(multiplicand), bin(multiplier), length, result_booth[1], result_mod_booth[1]])
# tests validity of results
debug(debug_results)
# generate tables for report
print(tabulate(result_table, result_headers, tablefmt="latex"))
print(tabulate(opcount_table, opcount_headers))
# output
with open("report/result_table.tex", 'w') as f:
f.write(tabulate(result_table, result_headers, tablefmt="latex_booktabs"))
with open("report/speed_table.tex", "w") as f:
f.write(tabulate(opcount_table, opcount_headers, tablefmt="latex_booktabs"))
# set up plotting
matplotlib.use("pgf")
matplotlib.rcParams.update({
"pgf.texsystem": "pdflatex",
'font.family': 'serif',
'text.usetex': True,
'pgf.rcfonts': False,
})
# generate table for operations vs operand length
plt.gcf().set_size_inches(w=4.5, h=3.5)
plt.plot(lengths, ops_booth, '^--m', label='booths algorithim')
plt.plot(lengths, ops_mod_booth, 'v--c', label='modified booths algorithim')
plt.gca().set_xlabel("Length of Operands")
plt.gca().set_ylabel("Number of Additions and Subtractions")
plt.legend(loc='upper left')
plt.savefig('report/performance.pgf')
# generate table of iterations vs operand length
iters_booth = []
iters_mod_booth = []
for length in lengths:
iters_booth.append(length)
iters_mod_booth.append(int(length / 2))
plt.figure()
plt.gcf().set_size_inches(w=4.5, h=3.5)
plt.plot(lengths, lengths, '^--m', label='booths algorithim')
plt.plot(lengths, [int(l/2) for l in lengths], 'v--c', label='modified booths algorithim')
plt.gca().set_xlabel("Operand Length")
plt.gca().set_ylabel("Number of iterations")
plt.legend(loc='upper left')
plt.savefig('report/iterations.pgf')
|
