HLS_lab_B_sorting

NTHU EE 110061560 Bob-Wu

Insertion sort

• Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.

• It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

• advantages:

  • Simple implementation
  • Efficient for (quite) small data sets
  • only requires a constant amount O(1) of additional memory space

Merge sort

• Merge sort is an efficient, general-purpose, and comparison-based sorting algorithm.

• advantages:

  • The same amount of data with the same number of running cycles
  • Efficient for (quite) large data sets

build flow

1. Study algorithms
2. Write C++ code and verify on HLS
3. Use vivado for block design
4. Run on pynq

result

Insertion sort vs Merge sort

1. test data : There are two different situations.
2. run cycle time with test data 1
   • input = { 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 }
   • output = { 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 }
3. run cycle time with test data 2
   • input = { 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 }
   • output = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }
4. performance

Insertion sort vs Insertion sort improved

1. test data :
   • input = { 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 }
   • output = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }
2. run cycle time
3. performance
4. utilization