Bubble Sort using Hardware


Overall design of hardware


Single Stage Design


Design of Bubble Sort

  • For parallelism, bubble sort is broke down in to odd and even parts.
  • A total of n (number of elements) iterations will be needed.
  • Both odd and even parts can be done in parallel on every iteration.

Basic Idea of Odd and Even Sort




Block Diagram of My Design

parallel_bubble (1).png

  • Those memory are individual registers that are used to store the result of bubble sort.
  • The controller here is responsible for comparing the current values in the registers (current, and the following).


Breakdown of Verilog Design

  • Source code of my design: Bubble_Sort.v
  • Consist of 3 sequential always block and 1 combinational always block
    • Sequential Blocks:
      • Reading of input vector into design
      • Computation of Bubble Sort (Loop Iteration)
      • Dumping of output from design
    • Combinational Block:
      • Computation of Bubble Sort (Swapping of Elements)
        • Consist of ODD and EVEN part
  • in_valid_flag: A new set of input is ready to be computed.
  • bubble_start_flag: Bubble sort is ready to begin. (All input is received)
  • dump_out_flag: Dumping of output is done and ready to reset all states.



Waveform Generation


  • As seen in the waveform, dump_out_flag will initialize all other flags. (Reset to 0)


FSM Implementation of the Same Design

  • Source code for my FSM implementation: Bubble_Sort_FSM.v
  • The implementation of FSM is much simpler than expected.
  • All we need is to define all the states of our design precisely.
  • For my design I used a total of 4 states:
    • INIT_STATE: All the initialization needed for my design. (same as reset)
    • STORE_INPUT: Collects input from testbench.
    • BUBBLE_SORT: Sorts all collected inputs.
    • DUMP_OUTPUT: Dumps/Outputs all sorted inputs.




Waveform Generation (FSM)


  • Pay attention on the state transitions.
  • The small bit before STORE_INPUT is INIT_STATE

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s