Description
Description:
The selection sort algorithm is a simple comparison-based sorting algorithm. It works by
dividing the input into two parts: the subarray of sorted elements and the subarray of unsorted
elements. In each iteration, the algorithm selects the smallest (or largest, depending on the sorting
order) element from the unsorted subarray and swaps it with the first element of the unsorted
subarray.
This process continues until the entire array becomes sorted. At each step, the smallest
(or largest) element is identified and “selected” to be placed in its correct position. This selection
process gives the algorithm its name. The selection sort algorithm has an average and worst-case
time complexity of O(n^2), where n is the number of elements in the array. It is not suitable for
large datasets since its time complexity grows quadratically. However, it has the advantage of
being simple to understand and implement.
For more information you can use following sources:
https://www.geeksforgeeks.org/selection-sort/
SSC Design:
You are to design a sorter circuit that uses the selection sort algorithm to sort a block of 256
16-bit unsigned words in an ascending order. Figure 1 shows the top-view specification of the
selection sorter circuit (SSC). Data collected becomes available in a memory buffer between the
wrapper and the SSC.
The memory buffer has read and write signals for its read and write
operations. A wrapper sitting next to our processing element (PE), sorter circuit, is responsible for
collecting data and informing our PE that data collection is completed and sorting can start. This
is done by the wrapper issuing a complete positive pulse on the start signal. When sorting is
completed, the SSC issues a complete positive pulse on its done signal.
The Datapath and Controller of the SSC are illustrated in Figure 2 and Figure 3, respectively.
After achieving a positive pulse on the start signal, two counters and all registers are reset to zero.
Once a complete pulse is detected on the start signal, the sorting procedure begins and the value 1
is loaded into counter2.
Counter1 is addressing the last word of the sorted part of the memory
block. At this state it is addressing the first word of the memory buffer. The data and its address
are saved in the Min_reg and Minaddr_reg, respectively. In each cycle, counter2 increments by
one, and the corresponding data is obtained from the memory buffer.
This data is then compared
with the data of Min_reg. If a smaller data value is found, it is saved along with its address. This
procedure repeats until the value of counter2 reaches 255. At this point, the minimum value from
the unsorted section has been identified and needs to be moved to the sorted portion. The
movement of the minimum value occurs in three update stages: update0, update1, and update2.
During these stages, the minimum value is replaced with the first member of the unsorted section,
whose address is determined by the value of counter1 that is incremented by one.
This process continues until the value of counter1 reaches 255, indicating that all the data has
been sorted.
Assignment:
You are provided with the design of SSC. You are to:
1. Show Verilog description of the components of the datapath and then enclose them in the
complete datapath.
2. Show Verilog description of the controller according to the provided FSM, using Huffman
modeling style.
3. In a top-level Sorter Circuit architecture, put the datapath and controller of the circuit
together.
4. Generate an appropriate testbench to test your design (Control the duration of running a
testbench, using “$stop or $finish”).
***For initializing the memory buffer use the given data.txt file (Use $readmemb for reading text
IO).
Attention:
This homework covers “Review – Logic Design at RT Level” and “Chapter 2 – Verilog HDL
for design and test” modules on Canvas.
Deliverables:
All Verilog codes and a complete report containing all parts of the assignment. Make sure that
your deliverable follows all mentioned rules in the assignment part of “ECE5724 – Comprehensive
Format Syllabus.pdf” file. The file has been posted on Canvas.
Figure 1: Top view of Selection Sorter Circuit
Memory Buffer comparator Minaddr_Reg Temp_Reg Addr Mux Data Mux Min_Reg
Write
Read
clk
clk
rst
Write data
Read data
Address
clk
rst
l t
Load_Min
Load_Addr
Cnt2_out
Sel_DMux
Sel_AMux
2
Cnt2_out
clk
rst
Load_Temp
Read_reg
Write_reg
16
16
16
8
Cnt2_out
Sel_AMux
Sel_DMux
Read_reg
Write_reg
clk
rst
Load_min
Load_min
Cnt1_out
Min_reg
Temp_reg
Cnt1_out
rst
Load_Temp AMux
Cnt1_out
Sel_Mux
Sel_Mux
Figure 2: Selection Sorter Circuit Datapath
update2 update1
idle start init
Find min
update0 C02=0
C01=0
Start=1 Start=0
Start=1 C02=1
reset C01=1
8-bit counter1
clk
rst
en_cnt1
co1
cnt1_out
8-bit counter2
clk
rst
en_cnt2
co2
cnt2_out
pl_cnt2
8
cnt1_out+1
en_cnt2=1
pl_cnt2=1
Load_min=1
Read_reg=1
Sel_Amux=00
Sel_Mux= 0
en_cnt2=1
Sel_AMux=01
Read_reg=1
Sel_Mux= 1
Sel_AMux=00
Load_Temp=1
Read_reg=1
Sel_AMux=00
Sel_DMux=0
Write_reg=1
en_cnt1=1
Sel_AMux=10
Sel_DMux=1
Write_reg=1
done
Done=1
Done=0
Figure 3: Selection Sorter Circuit Controller