path: root/multiplier/hdl/gen_wallace.py

#!/usr/bin/python3
import argparse

def gen_half_adder():
	print(f"---------- Half adder generation ----------")
	f = open(f"half_adder.sv", "w")
	f.write(f"""module half_adder (
	input logic a,
	input logic b,
	output logic sum,
	output logic carry
);

assign sum = a ^ b;
assign carry = a & b;

endmodule
""")
	f.close()

def gen_full_adder():
	print(f"---------- Full adder generation ----------")
	f = open(f"full_adder.sv", "w")
	f.write(f"""module full_adder (
	input logic a,
	input logic b,
	input logic c,
	output logic sum,
	output logic carry
);

assign sum = a ^ b ^ c;
assign carry = (a & b) | (c & (a ^ b));

endmodule
""")
	f.close()

def gen_multiplier(bits):
	print(f"\n---------- {bits} Bit Top Level Multiplier Generation ----------")
	f = open(f"multiplier.sv", "w")
	f.write(f"""module multiplier(
	input  logic [{bits-1}:0] a,
	input  logic [{bits-1}:0] b,
	output logic [{2*bits-1}:0] c
);

	logic [{bits-1}:0] partial_prod [0:{bits-1}];
	logic [{2*bits-1}:0] partial_sum;

	assign c = partial_sum;

	wallace_adder wadder0(partial_prod, partial_sum);
	partial_products partprod0(a, b, partial_prod);

endmodule
""")
	f.close()

def gen_partial_products(bits):
	print(f"------------ {bits} Bit Partial Products Generation ------------")
	f = open(f"partial_products.sv", "w")
	f.write(f"""module partial_products
(
	input  logic [{bits-1}:0] a,
	input  logic [{bits-1}:0] b,
	output logic [{bits-1}:0] c [0:{bits-1}]
);

always @ (*) begin
	integer i;
	for (i = 0; i < {bits}; i=i+1) begin
		c[i][{bits-1}:0] = {{{bits}{{b[i]}}}} & a;
	end
end

endmodule
""")

	f.close()

def add_half_adder(reduction_layers, instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug):
	# Generates nets and updates the layer net array
	curr_col_net_idx = len(reduction_layers[curr_layer][col_idx])
	next_col_net_idx = len(reduction_layers[curr_layer][col_idx+1])
	cout = f"layer{curr_layer}_col{col_idx}_net{curr_col_net_idx}"
	sout = f"layer{curr_layer}_col{col_idx+1}_net{next_col_net_idx}"

	reduction_layers[curr_layer][col_idx].append(cout)
	reduction_layers[curr_layer][col_idx+1].append(sout)

	# Adds half adder to instantiations
	net_names[prev_layer].append(cout)
	net_names[prev_layer].append(sout)
	a, b = [col.pop() for i in range(2)]
	instantiations[prev_layer].append(f"half_adder ha_add{curr_layer}_{len(instantiations[prev_layer])} ({a}, {b}, {cout}, {sout});")

	# Debug Print half adder
	if debug:
		print(f"half_adder ha_add{curr_layer}_{len(instantiations[prev_layer])} ({a}, {b}, {cout}, {sout});")

	pass

def add_full_adder(reduction_layers, instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug):
	# Generates nets and updates the layer net array
	curr_col_net_idx = len(reduction_layers[curr_layer][col_idx])
	next_col_net_idx = len(reduction_layers[curr_layer][col_idx+1])
	cout = f"layer{curr_layer}_col{col_idx}_net{curr_col_net_idx}"
	sout = f"layer{curr_layer}_col{col_idx+1}_net{next_col_net_idx}"
	reduction_layers[curr_layer][col_idx].append(cout)
	reduction_layers[curr_layer][col_idx+1].append(sout)

	# Adds nets and adders to be instantiated
	net_names[prev_layer].append(cout)
	net_names[prev_layer].append(sout)
	a, b, cin = [col.pop() for i in range(3)]
	instantiations[prev_layer].append(f"full_adder fa_add{curr_layer}_{len(instantiations[prev_layer])} ({a}, {b}, {cin}, {cout}, {sout});")

	# Debug Print half adder
	if debug:
		print(f"full_adder fa_add{curr_layer}_{len(instantiations[prev_layer])} ({a}, {b}, {cin}, {cout}, {sout});")

def add_passthrough(reduction_layers, instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug):
# Assigns passthrough for remaining logic and updates the counter
	curr_col_net_idx = len(reduction_layers[curr_layer][col_idx])
	passthrough = f"layer{curr_layer}_col{col_idx}_net{curr_col_net_idx}"

	# Adds passthrough to netlist array
	reduction_layers[curr_layer][col_idx].append(passthrough)

	# Adds the assign statement to passthrough
	net_names[prev_layer].append(passthrough)
	input_net1 = col.pop()
	instantiations[prev_layer].append(f"assign {passthrough} = {input_net1};")

	if debug:
		print(f"assign {passthrough} = {input_net1};")

def gen_adder_tree(bits, debug):
	print(f"--------------- {bits} Bit Adder Tree Generation ---------------")

	# Parameters of the adder tree generate script
	num_cols = (2 * bits)
	layer_limit = 50

	# Initialize reduction layer array
	reduction_layers = []

	# Initialize instantiations and net names
	ha_instantiations = []
	fa_instantiations = []
	pass_instantiations = []
	net_names = []

	# Partial layer is the "zeroeth" reduction layer, initialize it
	curr_layer = 0
	reduction_layers.append([[] for i in range(num_cols)])

	# Fill up partial layer
	for i in range(bits):
		for j in range(bits):
			reduction_layers[curr_layer][i+j].append(f"partial_prod[{i}][{j}]")

	# Debug partial layer print
	if debug:
		print(f"\n--------- LAYER {curr_layer} -------------")
		for col_idx, reduce in enumerate(reduction_layers[curr_layer]):
			print(f"Col: {col_idx}, Length: {len(reduce)}, {reduce}")

	# Build out subsequent reduction layers
	curr_layer = 1
	prev_layer = 0

	instantiation_idx = 0

	# Run until we can add the remaining bit vectors together or non-convergent solution
	while (len(max(reduction_layers[prev_layer], key=len)) > 2 and curr_layer < layer_limit):
		# Allocate next layer
		if debug:
			print(f"--------- LAYER {prev_layer} -------------")
		reduction_layers.append([[] for i in range(num_cols)])
		pass_instantiations.append([])
		ha_instantiations.append([])
		fa_instantiations.append([])
		net_names.append([])

		carry_propogation = 0
		extra_ha = (len(max(reduction_layers[prev_layer], key=len)) == 3)
		fa_used = False
		ha_used = False

		# Counts how many bits need to be eventually removed by this bit
		for col_idx, col in enumerate(reduction_layers[prev_layer]):

			# Check that this is actually solvable using only 2*bits output
			if (col_idx+1 == len(reduction_layers[prev_layer]) and (len(col) + carry_propogation) > 2):
				print("Cannot SOLVE")
				return -1

			# Debug print for this column
			if debug:
				print(f"Index: {col_idx}, Length: {len(col)}")

			next_layer_size = carry_propogation
			carry_propogation = 0

			# Add full adders if needed
			while (len(col) > 3):
				add_full_adder(reduction_layers, fa_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)
				fa_used = True
				# 1 carry will go to the next column next layer, and the sum will go to this col next layer
				carry_propogation += 1
				next_layer_size += 1

			if (len(col) == 3):
				# Only add half adder if no propogations or other adders created
				if (fa_used == False and (ha_used == False or extra_ha == True) and next_layer_size == 0):
					add_half_adder(reduction_layers, ha_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)
					ha_used = True
				else:
					fa_used = True
					add_full_adder(reduction_layers, fa_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)

				# Increment the propogation and current size
				carry_propogation += 1
				next_layer_size += 1

			if (len(col) == 2):
				# Only add half adder if there is propogation from previous columns and if there is less than three in the next col, else pass through both
				if (fa_used == False and (ha_used == False or extra_ha == True) and next_layer_size == 1 ):
					add_half_adder(reduction_layers, ha_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)
					ha_used = True
					carry_propogation += 1
					next_layer_size += 1
				else:
					add_passthrough(reduction_layers, pass_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)
					add_passthrough(reduction_layers, pass_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)

			if (len(col) == 1):
				add_passthrough(reduction_layers, pass_instantiations, net_names, col, col_idx, curr_layer, prev_layer, debug)

		# Update the layer indices
		prev_layer = curr_layer
		curr_layer += 1

		# Debug reduction layer print
		if debug:
			for col_idx, reduce in enumerate(reduction_layers[prev_layer]):
				print(f"Col: {col_idx}, Length: {len(reduce)}, {reduce}")


	# Debug final reduction layer to be added
	if debug:
		print("\n--------- BIT PAIRS ----------")
		add_layer = list(zip(reduction_layers[prev_layer]))
		add_layer.reverse()
		for bit_pair in add_layer:
			print(bit_pair[0])

	# Add the two remaining rows of bits at the end
	bit_vector_0 = "{ "
	bit_vector_1 = "{ "
	for bit_pair_idx, bit_pair in enumerate(reversed(list(zip(reduction_layers[prev_layer])))):

		# Exclude MSB if no overflows to it
		if (len(bit_pair[0]) == 0 and bit_pair_idx == 0):
			continue

		# Generate bit string for both vectors, order doesn't matter here
		bit_vector_0 += f"{bit_pair[0][0]}, "
		if (len(bit_pair[0]) == 2):
			bit_vector_1 += f"{bit_pair[0][1]}, "
		else:
			bit_vector_1 += "1'b0, "

	bit_vector_0 = bit_vector_0[:-2] + "}"
	bit_vector_1 = bit_vector_1[:-2] + "};"

	f = open(f"wallace_adder.sv", "w")

	# Start by printing module declaration
	f.write(f"module wallace_adder (\n")
	f.write(f"\tinput  logic [{bits-1}:0] partial_prod[0:{bits-1}],\n")
	f.write(f"\toutput logic [{2*bits-1}:0] partial_sum\n")
	f.write(");\n\n")

	# Print out net names
	for net_layer in net_names:
		netstring = "logic "
		net_idx_len = len(net_layer)
		for net_idx, net in enumerate(net_layer):
			if (net_idx != net_idx_len - 1):
				netstring += f"{net}, "
			else:
				netstring += f"{net};"
		f.write(netstring + '\n')

	# Print out entire reduction tree and calculate stats
	ha_count = 0
	fa_count = 0
	for layer in range(len(pass_instantiations)):
		f.write(f"\n//----------- Reduction Layer {layer+1} Start --------------\n\n")
		for passthrough in pass_instantiations[layer]:
			f.write(passthrough + '\n')

		for half_adder in ha_instantiations[layer]:
			ha_count += 1
			f.write(half_adder + '\n')

		for full_adder in fa_instantiations[layer]:
			fa_count += 1
			f.write(full_adder + '\n')

	# Print final two number adder

	f.write(f"\n//----------- Adding Layer Start --------------\n\n")
	f.write(f"assign partial_sum = {bit_vector_0} + {bit_vector_1}\n")

	# Endmodule
	f.write("\nendmodule\n")

	f.close()

	# Print stats of the wallace adder
	print(f"{ha_count} Half Adders Used")
	print(f"{fa_count} Full Adders Used")
	print(f"{len(pass_instantiations)-1} Reduction Layers")

def main():
	parser = argparse.ArgumentParser(prog="Multiplier Generator", description="Generates a n bit multiplier based on the bits argument provided",
				epilog="bits sets the bit width of the multiplier, the output of the multiplier is 2 times the number of bits")
	parser.add_argument("bits", type=int, help="The bit width of the multiplier")
	parser.add_argument("-p", "--pipeline", help="Generates specified number of pipeline barriers")
	parser.add_argument("-s", "--stages", nargs='+' help="Generates stages at specific reduction layers")
	parser.add_argument("-a", "--adder", help="Generates the full and half adders for you to use", action='store_true')
	parser.add_argument("-d", "--debug", help="Enables debug prints during generation scripting", action='store_true')
	args = parser.parse_args()

	bits = args.bits
	pipeline = args.pipeline
	stages = args.stages
	debug = args.debug
	adder  = args.adder

	print(pipeline)
	print(stages)

	if (adder):
		gen_half_adder()
		gen_full_adder()

	gen_multiplier(bits)
	gen_partial_products(bits)

	if (gen_adder_tree(bits, debug) == -1):
		return -1

	print("----------- GENERATION COMPLETE WITHOUT ERROR ----------- \n\n")

if __name__ == "__main__":
	main()