Mục tiêu: Xây dựng thuật toán, thiết kế mức RTL, mô hình hóa bằng ngôn ngữ mô tả phần cứng VHDL, tiến hành mô phỏng kiểm chứng bằng ModelSIM mạch LSI thực hiện chức năng tìm ước số chung lớn nhất của hai số.

1. Yêu cầu thiết kế

Xây dựng mạch điện tử thực hiện chức năng tìm ước số chung lớn nhất GCD (Greatest Common Divisor ) của hai số nguyên 16-bit x, y.

Ví dụ tìm ước số chung lớn nhất của hai số:

            GCD(12,8) = 4

            GCD(13,5) = 1

            …

            GCD(x, y) = ?

Hình 1 chỉ ra giao diện các cổng ghép nối vào/ra của đơn vị tìm ước số chung lớn nhất. Các cổng vào/ra gồm có cổng đầu vào dữ liệu x_i, y_i và cổng đầu ra dữ liệu GCD_o.

Chức năng của hệ thống phải đảm bảo đầu ra là giá trị GCD của các đầu vào, tức là GCD_o = GCD(x_i, y_i). Do đó, nếu đầu vào là 12 và 8, đầu ra phải là 4. Nếu đầu vào là 13 và 5, đầu ra phải là 1.

Hình 1: Giao diện ghép nối I/O của đơn vị tìm ước số chung lớn nhất.

2.  Thực hiện

2.1. Thuật toán

Chúng ta bắt đầu bằng việc xây dựng một thuật toán thực hiện việc tìm ước số chung nhỏ nhất của hai chữ số x, y.

Phương pháp toán học được dùng để tìm ước số chung lớn nhất của hai số x, y có thể được mô tả như sau:

Giả thiết không mất tính tổng quát ta có x > y. Như vậy ta có thể phân tích x theo y như sau:

            x = a*y + r

Xảy ra hai khả năng như sau:

• Nếu r = 0 khi đó a chính là ước số chung lớn nhất của x và y, do đó GCD(x, y) = y
• Nếu r ≠ 0 khi đó ước số chung lớn nhất của x và y cũng là ước số chung lớn nhất của y và r tức là GCD(x, y) = GCD(y, r)

Từ mô hình toán học ở trên ta xây dựng một thuật toán đệ quy cho việc tìm ước số chung lớn nhất của hai số nguyên x và y như sau:

• Đánh giá x và y, nếu y > x thì đảo vị trí x và y cho nhau
• Tìm số dư r của phép chia x cho y
• Nếu r = 0 thì chuyển sang bước (4) ngược lại đặt x = r quay lại bước (1)
• Gán GCD(x,y) = y

Tiếp theo chúng ta mô hình hóa thuật toán trên bằng các chương trình dùng ngôn ngữ bậc cao để tiến hành đánh giá và tối ưu hóa thuật toán từ đó tìm ra một giải pháp phù hợp nhất cho thực hiện phần cứng. Ở cấp độ này, chúng ta có thể phân tích số lượng phép tính, chủng loại phép tính và kích thước của các biến được thuật toán yêu cầu. Nói cách khác, chúng ta có thể phân tích thuật toán về độ phức tạp về mặt thời gian tính toán và độ phức tạp về thực hiện phần cứng. Cho trường hợp tính GCD, chúng ta có hai cách để triển khai thuật toán trên như chỉ ra trong Bảng 1. Nếu giả sử chúng ta có thể sử dụng phép tính modulo “%” (phép tính tìm số dư của phép chia hai số), chúng ta có thể viết một chương trình như chỉ ra trong Chương trình 1. Chương trình này sử dụng ít bước lặp hơn để tìm ra giá trị ước chung lớn nhất nhưng độ phức tạp phần cứng lại cao hơn do yêu cầu phép tính %. Chương trình 2 thực hiện cùng chức năng tìm ước chung lớn nhất với chỉ sử dụng phép tính trừ (-) do đó yêu cầu về độ phức tạp thực hiện phần cứng thấp hơn nhưng lại cần nhiều lần lặp hơn để tính ra được ước số chung lớn nhất.

Chúng ta hãy so sánh hai thuật toán này khi tính toán GCD của hai số 42 và 8 để thấy Chương trình 1 cần ít bước lặp hơn Chương trình 1. Chương trình 2 sẽ trải qua vòng lặp bên trong của nó với các giá trị x và y như sau: (42; 8), (34,8), (26 , 8), (18,8), (10,8), (2,8), (2,6), (2,4), (2,2), do đó xuất ra ước chung lớn nhất là 2. Thuật toán thứ 1 sẽ trải qua vòng lặp bên trong của nó với các giá trị x và y như sau: (42,8), (8.2), (2.0), do đó xuất ra ước chung lớn nhất là 2. Thuật toán 1 hiệu quả hơn về mặt thời gian nhưng lại có độ phức tạp tính toán cao hơn vì sử dụng phép tính %. Do đó, chúng ta sẽ sử dụng thuật toán 2 cho việc thiết kế mạch phần cứng thực hiện chức năng GCD.

Bảng 1. Thuật toán tìm ước số chung lớn nhất của hai số nguyên.

2.2. FSMD

Để bắt đầu xây dựng mạch điện thực hiện chức năng tính GCD, trước tiên chúng ta chuyển đổi chương trình thành sơ đồ máy trạng thái phức tạp FSMD như Hình 2. Như tên gọi của nó các trạng thái của FSMD có thể bao gồm các biểu thức số học của tổ hợp các đầu vào và đầu ra bên ngoài hoặc biến. FSMD tương phản với sơ đồ trạng thái FSM thuần túy trong đó chỉ bao gồm các biểu thức boolean của chỉ các đầu vào và đầu ra bên ngoài, không có các biến. Do đó, các sơ đồ trạng thái phức tạp này trông giống như một chương trình tuần tự, trong đó các câu lệnh đã được lập lịch để thực hiện trong các trạng thái.

Hình 2: FSMD.

Bước tiếp theo của chúng ta là phân chia chức năng máy FSMD thành các thành phần cấu trúc gồm đơn vị xử lý dữ liệu datapath và bộ điều khiển như trong Hình 3. Phần datapath phải bao gồm một sự kết nối của các mạch tổ hợp và tuần tự. Phần điều khiển phải bao gồm một FSM thuần túy (tức là chỉ chứa các phép và điều kiện trên biến logic).

Hình 3. Phân tích máy trạng thái FSMD thành bộ điều khiển và datapath.

2.3.  Đơn vị xử lý dữ liệu Datapath

Hình 4 chỉ ra kiến trúc Datapath được đề xuất cho thực hiện chức năng tính toán ước chung lớn nhất giữa hai số.

Hình 4: Datapath.

2.4. Bộ điều khiển Controller

Sau khi thiết kế xong datapath chúng ta tín hành chuyển đổi máy trạng thái FSMD trong Hình 2 thành máy trạng thái FSM trong Hình 5 mô tả hoạt động của bộ điều khiển. Máy trạng thái FSM có các trạng thái và chuyển tiếp giống như máy FSMD. Tuy nhiên, trong FSM chúng ta đã thay thế các phép tính và điều kiện phức tạp bằng các phép tính và điều kiện trên các biến logic và tạo ra các tín hiệu điều khiển hoạt động của datapath. Giao diện các tín hiệu vào/ra của bộ điều khiển được mô tả trong Hình 6.

Hình 5: FSM of controller.

Hình 6. Giao diện các cổng tín hiệu vào/ra của bộ controller.

3.  Kiểm chứng 

Hình 7. Kết quả mô phỏng mạch GCD với phần mềm ModelSIM.

Kết quả mô phỏng chỉ ra mạch tính được đúng ước số chung lớn nhất của hai số x, y bất kỳ.

Hình 8. Kết quả tổng hợp mạch GCD với phần mềm Synopsys DC.

Hình 7 chỉ ra kết quả tổng hợp mạch GCD bằng phần mềm Synopsys DC với hai phong cách thực hiện mạch GCD khác nhau. Có thể thấy từ kết quả tổng hợp, mạch GCD được mô tả ở mức RTL có hiệu quả thực thi phần cứng tốt hơn so với mạch cùng chức năng nhưng được mô tả theo hành vi (thuật toán).

Mô phỏng và kiểm chứng: