Thiết kế mạch LSI sắp xếp một dãy số (Sorting Unit)
Mục tiêu: Thiết kế, mô phỏng và thực thi một đơn vị sắp xếp (Sorting Unit) một dãy số theo trật tự tăng hoặc giảm dần như được chỉ ra trong hình dưới.
Hình 1. Ví dụ minh họa quá trình sắp xếp một dãy gồm 4 phần tử theo trật tự tăng dần.
Yêu cầu đối với thiết kế:
– Kích thước dãy số k, và độ rộng N-bit của mỗi phần tử của dãy số được khai báo như tham số cấu hình của thiết kế
– Sorting Unit có giao diện ghép nối với hệ thống vi xử lý như chỉ ra trong Hình 2 sao cho:
o Đơn vị xử lý trung tâm (CPU) có thể viết k phần tử của dãy số cần phân loại
tới bộ đệm bên trong của Sorting Unit.
tới bộ đệm bên trong của Sorting Unit.
o Sau khi khởi tạo xong Sorting Unit, CPU sẽ kích hoạt quá trình tính toán của Sorting Unit bằng cách đặt tín hiệu Start = ‘1’
o Sau khi Sorting Unit kết thúc quá trình sắp xếp nó báo cho CPU biết bằng cách đặt tín hiệu Done = ‘1’; Sorting Unit cần giữ trạng thái này cho đến khi Start = 0.
o Khi Done = ‘1’, CPU có thể tiến hành đọc mảng dữ liệu đã được sắp xếp từ Sorting Unit
o Sau khi kết thúc đọc dữ liệu từ Sorting Unit, CPU xóa tín hiệu Start = 0 để báo phiên làm việc của Sorting Unit đã kết thúc.
Hình 2. Giao diện ghép nối I/O của đơn vị Sorting Unit.
Định nghĩa giao diện vào/ra:
Bảng 1: Mô tả các tín hiệu vào ra của đơn vị sắp xếp.
Thuật toán sắp xếp:
Bảng 2. Mã giả (Pseudo code) mô tả thuật toán.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
— this algorithm is right for any K≥2
[initialize input data]
Beginning: wait for start = ‘1’
Done = ‘0’
for i=0 to k-2 do
A= M[i]
for j=i+1 to k-1 do
B = M[j]
if A > B then
M[i] = B
M[j]= A
A = M[i]
end if
end for
end for
Done = ‘1’
wait for start = ‘0’
go to the beginning
End
|
Hình 3: Máy trạng thái FSMD mô tả thuật toán.
Thiết kế mạch điện thực hiện chức năng xử lý dữ liệu trong đơn vị sắp xếp:
Hình 4: Thiết kế Datapath.
Thiết kế máy trạng thái thực hiện chức năng điều khiển trong đơn vị sắp xếp:
Hình 5: Máy trạng thái FSM.
Mô tả thiết kế bằng ngôn ngữ mô tả phần cứng VHDL
Thiết kế của đơn vị sắp xếp đã được mô tả bằng ngôn ngữ VHDL và nhập vào máy tính để tiến hành mô phỏng kiểm chứng ở bước tiếp theo.
Tải mã nguồn VHDL ở đây.
Hình 7: Một đoạn mã nguồn VHDL mô tả đơn vị sắp xếp.
Mô phỏng thiết kế với bộ mô phỏng ModelSim:
Hình 8: Kết quả mô phỏng.
Phân tích kết quả mô phỏng:
Khung màu đỏ trong hình 8 chỉ ra chuỗi dữ liệu đầu vào gồm 4 phần tử có giá trị 3, 1, 4, 2. Sau thời gian sắp xếp được chỉ thỉ bằng tín hiệu Done = ‘1’, ta có được chuỗi dữ liệu đầu ra gồm 4 phần tử tương ứng nhưng đã được sắp xếp theo trật tự tăng dần như chỉ ra trong khung màu xanh của Hình 8.
Khung màu đỏ trong hình 8 chỉ ra chuỗi dữ liệu đầu vào gồm 4 phần tử có giá trị 3, 1, 4, 2. Sau thời gian sắp xếp được chỉ thỉ bằng tín hiệu Done = ‘1’, ta có được chuỗi dữ liệu đầu ra gồm 4 phần tử tương ứng nhưng đã được sắp xếp theo trật tự tăng dần như chỉ ra trong khung màu xanh của Hình 8.
Quá trình sắp xếp được điều khiển bởi xung start bắt đầu từ thời điểm 460ns và kết thúc tại thời điểm 1612ns. Vì chu kì clock được thiết lập trong testbench là 20ns, nên tổng số chu kỳ được dùng để hoàn thành quá trình sắp xếp là (1600-460)/20 = 57 chu kỳ.
