.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "examples/design_examples/streaming_radix_3.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_examples_design_examples_streaming_radix_3.py: ============================== Streaming Radix-3 Winograd DFT ============================== In this example, a streaming radix-3 Winograd DFT is implemented. .. GENERATED FROM PYTHON SOURCE LINES 9-10 Model the algorithm as a signal flow graph (SFG) .. GENERATED FROM PYTHON SOURCE LINES 10-53 .. code-block:: Python from b_asic.sfg import SFG from b_asic.special_operations import Input, Output c30 = 1/2 c31 = 14189 / 2**14 * 1j in0 = Input("x0") in1 = Input("x1") in2 = Input("x2") a0 = in1 + in2 a1 = in2 - in1 a2 = a0 + in0 m0 = c30 * a0 m1 = c31 * a1 a3 = in0 - m0 a4 = a3 + m1 a5 = a3 - m1 out0 = Output(a2, "X0") out1 = Output(a4, "X1") out2 = Output(a5, "X2") # Create a signal-flow-graph (SFG) sfg = SFG([in0, in1, in2], [out0, out1, out2]) # Simulate the SFG to validate import numpy as np from b_asic.simulation import Simulation rng = np.random.default_rng() data = [[rng.random() + 1j * rng.random()] for _ in range(3)] fft_reference = np.fft.fft([d[0] for d in data]) sim1 = Simulation(sfg, data) sim_res = sim1.run() assert np.allclose(sim_res[0], fft_reference[0], atol=1e-3) assert np.allclose(sim_res[1], fft_reference[1], atol=1e-3) assert np.allclose(sim_res[2], fft_reference[2], atol=1e-3) .. GENERATED FROM PYTHON SOURCE LINES 54-55 Display it .. GENERATED FROM PYTHON SOURCE LINES 55-58 .. code-block:: Python sfg.display() .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_001.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 59-60 Display the SFG with l1-norm values for all signals .. GENERATED FROM PYTHON SOURCE LINES 60-63 .. code-block:: Python sfg.display(info="l1-norm") .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_002.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_002.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 64-65 Introduce scaling such that the l1-norm values do not exceed 1 (safe-scaling) .. GENERATED FROM PYTHON SOURCE LINES 65-87 .. code-block:: Python sfg["add1"].out0_scale = 1 sfg["sub2"].out0_scale = 1 sfg["add0"].out0_scale = 1 sfg["add2"].out0_scale = 1 sfg["sub1"].out0_scale = 1 sfg["add0"].in1_scale = 1 sfg["sub0"].in0_scale = 1 sfg = sfg.remove_operation("cmul0") sfg["sub0"].in0_scale = 0 sfg["sub0"].out0_scale = 1 sim1 = Simulation(sfg, data) sim_res = sim1.run() assert np.allclose(sim_res[0], fft_reference[0]/4, atol=1e-3) assert np.allclose(sim_res[1], fft_reference[1]/4, atol=1e-3) assert np.allclose(sim_res[2], fft_reference[2]/4, atol=1e-3) sfg.display(info="l1-norm") .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_003.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_003.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 88-89 First we must define the latency and execution time for each type of operation .. GENERATED FROM PYTHON SOURCE LINES 89-99 .. code-block:: Python from b_asic.core_operations import Addition, Subtraction, ConstantMultiplication sfg.set_latency_of_type(Addition, 1) sfg.set_execution_time_of_type(Addition, 1) sfg.set_latency_of_type(Subtraction, 1) sfg.set_execution_time_of_type(Subtraction, 1) sfg.set_latency_of_type(ConstantMultiplication, 2) sfg.set_execution_time_of_type(ConstantMultiplication, 1) .. GENERATED FROM PYTHON SOURCE LINES 100-105 We want a streaming implementation using the minimal amount of operators, i.e. one parallel input and one parallel operation -> the operations should be distributed over three clock cycles. Let us use a scheduling algorithm for that. .. GENERATED FROM PYTHON SOURCE LINES 105-123 .. code-block:: Python from b_asic import Schedule, HybridScheduler # We need 1 PE of each type resources={Addition: 1, Subtraction: 1, ConstantMultiplication: 1} # Specify the input and output timing constraints input_times = {f"in{i}": i for i in range(3)} output_delta_times = {f"out{i}": i for i in range(3)} scheduler = HybridScheduler( max_resources=resources, input_times=input_times, output_delta_times=output_delta_times, ) # Schedule over three cycles, enable cyclic scheduling to allow wrapping around the schedule edge schedule = Schedule(sfg, scheduler, schedule_time=3, cyclic=True) schedule .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_004.svg :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_004.svg :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 124-125 Map to an architecture with the desired number of PEs and the minimal amount of memories and multiplexing. .. GENERATED FROM PYTHON SOURCE LINES 125-142 .. code-block:: Python from b_asic.resource_assigner import assign_processing_elements_and_memories from b_asic.architecture import Architecture # Automatic resource assignment pes, mems, direct = assign_processing_elements_and_memories( schedule, strategy="ilp_min_mux", memory_read_ports=1, memory_write_ports=1, memory_total_ports=2, memory_type="RAM", ) # Create an architecture and display it arch = Architecture(pes, mems, "r3", direct) arch .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_005.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_005.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 143-144 Generate VHDL for the created architecture. .. GENERATED FROM PYTHON SOURCE LINES 144-156 .. code-block:: Python from b_asic.data_type import DataType from b_asic.code_printer import VhdlPrinter # Use a fixed-point complex data type using 16 bits for each part WL = 16 dt = DataType(WL, is_complex=True) # Generate VHDL code for the architecture with registers on I/O ports printer = VhdlPrinter(dt) printer.print(arch, path="generated_separate", io_registers=True) .. GENERATED FROM PYTHON SOURCE LINES 157-158 Simulate and generate a testbench for the design. .. GENERATED FROM PYTHON SOURCE LINES 158-191 .. code-block:: Python from b_asic.tb_printer import CocotbPrinter # Generate N complex points within the unit disk N = 1000 rng = np.random.default_rng() step = 2**(-(WL - 1)) half = 2**(WL - 1) def _rand_unit_disk(rng, n): out = [] while len(out) < n: re = rng.integers(-half, half) * step im = rng.integers(-half, half) * step if re**2 + im**2 < 1: out.append(re + 1j * im) return out data = [_rand_unit_disk(rng, N) for _ in range(3)] # Run a simulation with the generated input data for N iterations sim = Simulation(schedule.sfg, data, dt) sim.run_for(N) # Generate the testbench for the simulation results tb_printer = CocotbPrinter(sim.results) tb_printer.print( arch, schedule, path="generated_separate", simulator="questa", # can be set to any simulator that Cocotb supports, e.g. "ghdl" or "nvc" waves=True, # enable waveform generation io_registers=True, # specify that I/O ports have registers ) .. GENERATED FROM PYTHON SOURCE LINES 192-194 Let us now model the algorithm using "AddSub" operations i.e. an operation that adds or subtracts based on a control signal. .. GENERATED FROM PYTHON SOURCE LINES 194-201 .. code-block:: Python from b_asic.core_operations import AddSub sfg = sfg.rewrite(AddSub, Addition) sfg = sfg.rewrite(AddSub, Subtraction) sfg .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_006.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_006.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 202-203 Do the same scheduling and mapping to an architecture again. .. GENERATED FROM PYTHON SOURCE LINES 203-227 .. code-block:: Python sfg.set_latency_of_type(AddSub, 1) sfg.set_execution_time_of_type(AddSub, 1) resources={AddSub: 2, ConstantMultiplication: 1} scheduler = HybridScheduler( max_resources=resources, input_times=input_times, output_delta_times=output_delta_times, ) schedule = Schedule(sfg, scheduler, schedule_time=3, cyclic=True) schedule pes, mems, direct = assign_processing_elements_and_memories( schedule, strategy="ilp_min_mux", memory_read_ports=1, memory_write_ports=1, memory_total_ports=2, memory_type="RAM", ) arch = Architecture(pes, mems, "r3", direct) arch .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_007.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_007.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 228-229 Generate VHDL and a testbench for the new architecture. .. GENERATED FROM PYTHON SOURCE LINES 229-245 .. code-block:: Python printer.print(arch, path="generated_addsub", io_registers=True) sim = Simulation(schedule.sfg, data, dt) sim.run_for(N) tb_printer = CocotbPrinter(sim.results) tb_printer.print( arch, schedule, path="generated_addsub", simulator="questa", waves=True, io_registers=True, ) .. GENERATED FROM PYTHON SOURCE LINES 246-259 We can convert "cmul1" into addsubs with shifts on the inputs. If we use 3 addsub PEs we have three addsub operations to spare on the constant multiplication, since the algorithm contains 6 addsub operations to compute over 3 cycles. 7095/8192 is the best approximation using three addsubs so let us use that one. Factorize the constant multiplication into smaller parts. This is done since the CSD representation of these constants is optimal, which is not the case for 7095/8192. Start by propagating the imaginary multiplication into the inputs of "addsub3" and "addsub4" as well as factoring the constant into two smaller parts and rewriting them into addsubs with shifts. .. GENERATED FROM PYTHON SOURCE LINES 259-281 .. code-block:: Python c310 = ConstantMultiplication(55/64) c311 = ConstantMultiplication(129/128) sfg = sfg.replace("cmul1", c310) sfg = sfg.insert_operation_after("cmul0", c311) sfg["addsub3"].mul_j = True sfg["addsub4"].mul_j = True sfg = sfg.rewrite(AddSub, ConstantMultiplication) # Validate the modified SFG data = [[rng.random() + 1j * rng.random()] for _ in range(3)] fft_reference = np.fft.fft([d[0] for d in data]) sim1 = Simulation(sfg, data) sim_res = sim1.run() assert np.allclose(sim_res[0], fft_reference[0]/4, atol=1e-3) assert np.allclose(sim_res[1], fft_reference[1]/4, atol=1e-3) assert np.allclose(sim_res[2], fft_reference[2]/4, atol=1e-3) sfg .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_008.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_008.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 282-285 Now we can proceed with scheduling and mapping to an architecture consisting of 3 addsub PEs, because we now have 9 addsub operations to compute over 3 cycles. .. GENERATED FROM PYTHON SOURCE LINES 285-309 .. code-block:: Python sfg.set_latency_of_type(AddSub, 1) sfg.set_execution_time_of_type(AddSub, 1) resources={AddSub: 3} scheduler = HybridScheduler( max_resources=resources, input_times=input_times, output_delta_times=output_delta_times, ) schedule = Schedule(sfg, scheduler, schedule_time=3, cyclic=True) schedule pes, mems, direct = assign_processing_elements_and_memories( schedule, strategy="ilp_min_mux", memory_read_ports=1, memory_write_ports=1, memory_total_ports=2, memory_type="RAM", ) arch = Architecture(pes, mems, "r3", direct) arch .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_009.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_009.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 310-311 Generate VHDL and a testbench for the new architecture .. GENERATED FROM PYTHON SOURCE LINES 311-328 .. code-block:: Python printer.print(arch, path="generated_shiftandadd", io_registers=True) data = [_rand_unit_disk(rng, N) for _ in range(3)] sim = Simulation(schedule.sfg, data, dt) sim.run_for(N) tb_printer = CocotbPrinter(sim.results) tb_printer.print( arch, schedule, path="generated_shiftandadd", simulator="questa", waves=True, io_registers=True, ) .. GENERATED FROM PYTHON SOURCE LINES 329-330 Finally, by unfolding the schedule, the schedule can be further optimized due to increased flexibility. .. GENERATED FROM PYTHON SOURCE LINES 330-334 .. code-block:: Python sfg = sfg.unfold(2) sfg.display() .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_010.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_010.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 335-336 We then schedule the unfolded SFG, i.e. scheduling 2 iterations of the algorithm over 6 cycles. .. GENERATED FROM PYTHON SOURCE LINES 336-356 .. code-block:: Python from b_asic import Schedule, HybridScheduler, AddSub sfg.set_latency_of_type(AddSub, 1) sfg.set_execution_time_of_type(AddSub, 1) resources={"addsub": 3} input_times = {f"in{i}_0": i for i in range(3)} input_times |= {f"in{i}_1": i+3 for i in range(3)} output_delta_times = {f"out{i}_0": i for i in range(3)} output_delta_times |= {f"out{i}_1": i+3 for i in range(3)} scheduler = HybridScheduler( max_resources=resources, input_times=input_times, output_delta_times=output_delta_times, ) schedule = Schedule(sfg, scheduler, schedule_time=6, cyclic=True) schedule .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_011.svg :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_011.svg :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 357-360 Manual schedule optimization, written out to the terminal when using the scheduling GUI, "schedule.edit()". We achieve a schedule with a latency of one less clock cycle and reduce the number of concurrent reads/writes to memory. Thus we also expect this optimization to reduce the number of memories by one. .. GENERATED FROM PYTHON SOURCE LINES 360-373 .. code-block:: Python schedule.move_operation('addsub3_1', -1) schedule.move_operation('out0_0', -1) schedule.move_operation('out1_0', -1) schedule.move_operation('out2_0', -1) schedule.move_operation('out0_1', -1) schedule.move_operation('out1_1', -1) schedule.move_operation('out2_1', -1) schedule.move_operation('addsub2_0', 1) schedule.move_operation('addsub4_1', -1) schedule.move_operation('addsub0_0', 1) schedule .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_012.svg :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_012.svg :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 374-375 Generating an architecture for the optimized schedule. .. GENERATED FROM PYTHON SOURCE LINES 375-387 .. code-block:: Python pes, mems, direct = assign_processing_elements_and_memories( schedule, strategy="ilp_min_mux", memory_read_ports=1, memory_write_ports=1, memory_total_ports=2, memory_type="RAM", ) arch = Architecture(pes, mems, "r3", direct) arch .. image-sg:: /examples/design_examples/images/sphx_glr_streaming_radix_3_013.png :alt: streaming radix 3 :srcset: /examples/design_examples/images/sphx_glr_streaming_radix_3_013.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 388-391 As seen, the architecture now only consists of three memories, which is an improvement compared to the previous one. Finally, generate VHDL and a testbench for the optimized architecture. .. GENERATED FROM PYTHON SOURCE LINES 391-408 .. code-block:: Python printer.print(arch, path="generated_optimized", io_registers=True) data = [_rand_unit_disk(rng, N) for _ in range(6)] sim = Simulation(schedule.sfg, data, dt) sim.run_for(N) tb_printer = CocotbPrinter(sim.results) tb_printer.print( arch, schedule, path="generated_optimized", simulator="questa", waves=True, io_registers=True, ) .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 2.219 seconds) .. _sphx_glr_download_examples_design_examples_streaming_radix_3.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: streaming_radix_3.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: streaming_radix_3.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: streaming_radix_3.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_