Một phương pháp tăng tốc phép biến đổi Hadamard bằng kiến trúc pipeline
Tóm tắt: Đối với các hệ xử lý chuyên dụng, vấn đề dung hòa giữa tốc độ xử lý và
độ tin cậy của hệ luôn luôn được đặt ra cho các nhà thiết kế [5, 7]. Dựa trên ý tưởng
tối giản cấu trúc của bộ mã hóa Hadamard trong lõi CPU của [1], bài báo đề xuất
giải pháp cứng hóa thuật toán Hadamard bằng công nghệ FPGA kết hợp với kiến
trúc pipeline nhằm vừa bảo đảm được tốc độ vừa nâng cao độ tin cậy hệ thống do có
cấu trúc đơn giản hơn. Khi so sánh cấu trúc ma trận 1 hàng×4 cột với cấu trúc ma
trận 8 hàng×4 cột cho thấy độ phức tạp đã giảm được gần 8 lần nhưng tốc độ thực
hiện mã hóa luồng vector 64bit trên ma trận tối giản vẫn không thay đổi. Kết quả mô
phỏng trên ModelSim và thực thi trên Xilinx ISE Design Suite cho thấy hiệu năng của
phương án đề xuất có nhiều ưu việt hơn so với các phương pháp khác.
iện trên hình 3. Căn cứ vào sơ đồ hình 6, cấu trúc phần cứng bao gồm khối tạo tín hiệu điều khiển DRIVER FSM, khối ma trận chính-phụ (SYGN 64 bit), khối thao tác song song với phép tính nhân- cộng tích lũy và khối dẫn dữ liệu ra FIFO, khối đầu ra FIFO. Hai phương án được lựa chọn thực thi biến đổi Hadamard để tiện so sánh. Phương án thứ nhất là phương án không sử dụng ma trận trọng số phụ, còn phương án thứ hai là phương án có sử dụng ma trận trọng số phụ. Máy trạng thái [2, 7] của 2 phương án được thể hiện trên hình 7a và 7b. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc kiến trúc pipeline.” 100 a) b) Hình 7. a) Máy trạnh thái không có ma trận phụ; b) Máy trạnh thái có ma trận phụ. Tương ứng với máy trạng thái là lưu đồ vòng lặp thao tác của ma trận trọng số Hadamard không có ma trận phụ và ma trận trọng số Hadamard có ma trận phụ như thể hiện trên hình 8. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 101 Hình 8. Vòng lặp thao tác cho a)ma trận trọng số Hadamard không có ma trận phụ, b) ma trận trọng số Hadamard có ma trận phụ. Như trên hình 8 cho thấy vòng lặp thao tác chính có sự khác biệt về thời gian thao tác. Đối với vòng lặp thao tác cho ma trận trọng số Hadamard không có ma trận phụ, hệ phải mất 80 clock mới xử lý xong 1 vector dữ liệu kích thước 8 byte, trong khi đó, với vòng lặp thao tác cho ma trận trọng số Hadamard có ma trận phụ, hệ chỉ mất 16 clock để xử lý xong 1 vector dữ liệu kích thước 8 byte. Sự chênh lệch là rất rõ. 3.2. Thực hiện mô phỏng và phân tích kết quả Khi chạy chương trình viết theo thuật toán hình 7 trên ModelSim6.5c cho thấy sự phù hợp với lưu đồ thuật toán thể hiện trên hình 7a và hình 8a. Đối với phương án không sử dụng ma trận trọng số phụ [4, 5] cho thấy sự phù hợp với lưu đồ thuật toán thể hiện trên hình 7a và hình 8a. Trong giai đoạn khởi đầu, hệ thống tiêu tốn 130 clock. Từ clock thứ 131 đến clock thứ 138 là giai đoạn kết xuất dữ liệu của nửa đầu ma trận trọng số và sau 32 clock, tới clock thứ 169 hệ thống mới kết xuất nửa sau ma trận trọng số. Khoảng thời gian tiêu tốn để nạp nửa ma trận trọng số là 32 clock. Quá trình này được mô phỏng trên ModelSim6.5c và được thể hiện trên đồ thị thời gian hình 9a và 9b. Đối với phương án có sử dụng ma trận trọng số phụ cho thấy sự phù hợp với máy trạng thái và lưu đồ thuật toán thể hiện trên hình 7b và hình 8b. Từ clock thứ 131 đến clock thứ 138 là thời gian kết xuất dữ liệu của nửa đầu ma trận trọng số và ngay sau đó là clock thứ 139 hệ thống thực hiện kết xuất nửa sau ma trận trọng số. Khoảng thời gian tiêu tốn để nạp nửa ma trận trọng số là 1 clock. Quá trình này được mô phỏng trên ModelSim6.5c và được thể hiện trên hình 10. Điều lưu ý là ma trận trọng số Hadarmad chỉ bao gồm giá trị +1 và -1 nên trong phần thiết kế chỉ cần sử dụng 1 bit để phân biệt. Bit đó là bit sign được ký hiệu trên sơ đồ và trong chương trình. Bit sign=0 tương đương với giá trị trọng số +1, còn bit sign=1 tương đương với giá trị trọng số -1. Cách làm này đã tiết kiệm tài nguyên rất nhiều và làm cấu trúc ma trận trọng số phụ được đơn giản đi nhiều. Điều quan trọng nhất là cấu trúc phần cứng trong sơ đồ tối giản đã giảm đi gần 8 lần trong khi tốc độ không thay đổi do mạch hồi tiếp có sử dụng kỹ thuật pipeline nên chỉ cần một clock là đã thực hiện xong phép nhân trọng số và tích lũy giá trị mới. Clock trong mạch này cao gấp 8 lần clock hệ thống. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc kiến trúc pipeline.” 102 a) b) Hình 9. a) Quá trình nhân và cộng tích lũy với nửa đầu ma trận trọng số; b) Quá trình nhân và cộng tích lũy với nửa sau ma trận trọng số. Hình 10. Quá trình nhân và cộng tích lũy của hệ thống có ma trận trọng số phụ. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 103 Sử dụng ISE Design Suite 14.1 của Xilinx để thực thi phần cứng trên chip FPGA [2,7] XC3S500E-PQ208 đã cho ra kiến trúc có chức năng tương ứng với sơ đồ hình 6 và hoạt động theo thuật toán của máy trạng thái hình 7. Dưới đây là bảng thông tin về tài nguyên sử dụng (trích xuất từ cửa sổ phần mềm Xilinx ISE Design Suite) cho phương án không sử dụng ma trận trọng số phụ: Các cấu trúc logic được sử dụng Đã sử dụng (Dung lượng chip Đã sử dụng tính theo % tài nguyên Number of Slices 3154 4656 67% Number of Slice Flip Flops 3415 9312 36% Number of 4 input LUTs 2920 9312 31% Number of bonded IOBs 27 158 17% Number of GCLKs 1 24 4% Và dưới đây là bảng thông tin về tài nguyên sử dụng (trích xuất từ cửa sổ phần mềm Xilinx ISE Design Suite) cho phương án có sử dụng ma trận trọng số phụ: Các cấu trúc logic được sử dụng Đã sử dụng Dung lượng chip Đã sử dụng tính theo % tài nguyên Number of Slices 3197 4656 68% Number of Slice Flip Flops 3446 9312 37% Number of 4 input LUTs 2971 9312 31% Number of bonded IOBs 25 158 15% Number of GCLKs 1 24 4% Điều đặc biệt là tài nguyên của phương án không sử dụng ma trận trọng số phụ và có sử dụng ma trận trọng số phụ không chênh lệch nhiều, ví dụ số lượng Slices là 3154 so với 3197; số lượng input LUTs là 2920 so với 2971 Điều này có được là do phương pháp biểu diễn giá trị trọng số Hadarmad bằng 1 bit thay vì 1 byte. Hơn nữa với chip Xilinx gói XC3S500E-PQ208 chỉ tiêu tốn hết 68% dung lượng mà không cần phải sử dụng tới các cấu trúc FPGA cao hơn như FPGA Virtex-5 hay Virtex-6. 4. KẾT LUẬN Đối với các hệ xử lý chuyên dụng, vấn đề dung hòa giữa tốc độ xử lý và độ tin cậy của hệ luôn luôn được đặt ra cho các nhà thiết kế. Kiến trúc hệ xử lý Hadamard trong bài báo sử dụng phương pháp tối giản cấu trúc phần cứng để nâng cao độ tin cậy nhưng tốc độ vẫn không thay đổi nhờ sử dụng kiến trúc pipeline trong mạch hồi tiếp thông minh. Cụ thể: Ma trận trọng số được tối giản (1 hàng×4 cột) đã nâng cao được độ tin cậy so với cấu trúc ma trận trọng số đầy đủ (8 hàng×4 cột). Hơn nữa, khi sử dụng ma trận trọng số phụ thực hiện chức năng copy giá trị ma trận trọng số từ ma trận trọng số phụ vào ma trận trọng số chính và kiến trúc pipeline thực hiện chức năng hồi tiếp giá trị kết quả trung gian để xử lý trong chu trình vòng lặp đã nâng cao tốc độ làm việc lên so với các phương pháp khác do quá trình tái nạp nửa ma trận trọng số chỉ cần trong một chu kỳ clock thay vì 32 chu kỳ clock. Điều này cho phép trong thực tế chỉ cần sử dụng các chip FPGA thông thường thay vì phải sử dụng các chip FPGA cao cấp như Virtex-5 hay Virtex-6. Chương trình được viết trên ngôn ngữ mô tả phần cứng VHDL nên bám sát được cấu trúc phần cứng. Các khối chức năng đều được viết tách riêng thành các modul chương trình nên khi chỉnh sửa hay bổ sung tính năng hệ thống trở nên dễ dàng. Điều này cho phép mở rộng quy mô ma trận trọng số Hadamard khi cần thiết và điều khiển việc chia tách hàng và cột của ma trận trở nên khả thi hơn. Lời cảm ơn: Nhóm tác giả cảm ơn sự hỗ trợ của Phòng thí nghiệm Điện tử số và vi xử lý của Bộ môn Kỹ thuật Vi xử lý Khoa Vô tuyến điện tử, Học viện Kỹ thuật quân sự. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc kiến trúc pipeline.” 104 TÀI LIỆU THAM KHẢO [1]. Hoàng Thị Phương. “Thiết kế biến đổi HADAMARD tốc độ cao sử dụng trong các hệ vi xử tín hiệu số”. Tạp chí Khoa học Giáo Dục Kỹ Thuật, Đại học SPKT thành phố Hồ Chí Minh, năm 2014, số 27, tr. 09-16. [2]. Trịnh Quang Kiên, Lê Xuân Bằng. “Thiết kế logic số”. Nxb Học viện kỹ thuật quân sự, 2011. [3]. Trịnh Quang Kiên, Đào Văn Lân. “Nghiên cứu cải tiến hệ thống kiểm tra tên lửa Х35Э (3M-24E) trong tổ hợp tên lửa đối hạm URAN-E”. Đề tài NCKH cấp Bộ Quốc phòng 2011-2013. [4]. Sanat Kamal Bahi, Jim Plusquellic. “FPGA implementation of a fast Hadamard transformer for WCDMA”. Proceeding FPGA '03 Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays. Pages 237 – 237. [5]. Ankit Agrawa, Amit Joshi. “FPGA Implementation of 4-Point and 8-Point Fast Hadamard Transform”. International Journal of Computer Applications (0975 – 8887) Volume 124 – No.3, August 2015. [6]. Vijayalakshmi Saravanan. “An optimizing pipeline stall reduction algorithm for power and performance on multi-core CPUs”. Human-centric Computing and Information Sciences. 29 January 2015. [7]. Miodrag Bolic, Jonathan Parri. “Accessing an FPGA-based hardware accelerator in a paravirtualized environment”. Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2013 International Conference. Sept. 29 2013-Oct. 4 2013. pp: 1-9. ABSTRACT A METHOD TO INCREASE THE HADAMARD TRANSFORM SPEED WITH PIPELINE ARCHITECTURE For specialized microprocessor systems, the problem of compromise between processing speed and its reliability always has been posed to the designers. Based on the idea of minimizing the structure of the Hadamard encoder in the CPU core [1], a hardening of a Hadamard algorithm by FPGA technology in combination with pipeline architecture to ensure both high speed and high reliability due to the simpler structure of the system is proposed in this paper. When comparing the 1 row × 4 column matrix structure with the 8 row × 4 column matrix, the complexity was reduced to approximately 8 times, but the speed of 64-bit data vector encoding on the minimal matrix remained unchanged. Simulation results on ModelSim and implementation on the Xilinx ISE Design Suite show that performance of the proposed approach is more superior than other approaches. Keywords: Specialized microprocessor systems; FPGA; Hadamard; pipeline. Nhận bài ngày 02 tháng 5 năm 2018 Hoàn thiện ngày 11 tháng 6 năm 2018 Chấp nhận đăng ngày 10 tháng 8 năm 2018 Địa chỉ: 1 HVKTQS; 2 Đại học Sư phạm Kỹ thuật Nam Định. * Email: phamminhtoi@gmail.com.
File đính kèm:
- mot_phuong_phap_tang_toc_phep_bien_doi_hadamard_bang_kien_tr.pdf