Bubble Sort using Hardware

 

Overall design of hardware

bubble_sort.png

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

Selection_087.png

Selection_088.png

[source]

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.

flags.png

 

Waveform Generation

Selection_090.png

  • 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.

 

FSM.png

 

Waveform Generation (FSM)

Selection_091.png

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s