Một phương pháp tăng tốc phép biến đổi Hadamard bằng kiến trúc Pipeline

Bài viết đề 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.
Nội dung trích xuất từ tài liệu:
Một phương pháp tăng tốc phép biến đổi Hadamard bằng kiến trúc Pipeline Nghiên cứu khoa học công nghệ MỘT PHƯƠNG PHÁP TĂNG TỐC PHÉP BIẾN ĐỔI HADAMARD BẰNG KIẾN TRÚC PIPELINE Phạm Minh Tới1*, Đỗ Xuân Tiến1, Hoàng Thị Phương2 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. Từ khóa: Hệ xử lý chuyên dụng; FPGA; Hadamard; Pipeline. 1. ĐẶT VẤN ĐỀ Trong công trình [4, 5], các tác giả đã thực hiện thuật toán biến đổi Hadamard nhanh (Fast Hadamard Transform) bằng công nghệ FPGA. Tuy nhiên, cấu trúc phần cứng khá phức tạp nên khi ma trận trọng số kích thước lớn để xử lý những luồng dữ liệu vector kích thước 64, 128 bit thì cấu trúc trở nên cồng kềnh nên khó đưa vào các hệ xử lý chuyên dụng. Hơn nữa, các công trình [4, 5] đã cứng hóa thuật toán biến đổi nhanh FHT đối với mã Hadamard [1], song về cơ bản vẫn là cứng hóa thuật toán phần mềm mà chưa cải thiện cấu trúc, đặc biệt là đưa các công nghệ mới như pipeline vào để tăng tốc độ xử lý luồng dữ liệu. Trong công trình [1], tác giả đã có ý tưởng khá tốt là sử dụng ma trận trọng số phụ để hỗ trợ cho ma trận chính thông qua hệ thống pipeline nên có thể thực hiện mã hóa Hadamard mọi kích thước. Điều này cho phép đơn giản hơn nữa cấu trúc ma trận trọng số đã dẫn tới cấu trúc 1 hàng×4 cột so với cấu trúc 8 row×4 col. Vấn đề tốc độ sẽ được giải quyết bằng cách sử dụng kỹ thuật pipeline trong sơ đồ chức năng như được thể hiện trên hình 1. Hình 1. Cấu trúc ma trận trọng số 1 hàng×4 cột. Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 95  Kỹ thuật điều khiển & Điện tử 2. NỘI DUNG CẦN GIẢI QUYẾT 2.1. Cơ sở lý thuyết Trong cấu trúc hệ xử lý tín hiệu số, hệ xử lý song song đặc biệt là ALU của các lõi CPU thường được trang bị ma trận trọng số vì một loạt lớp bài toán xử lý tín hiệu liên quan tới tập hợp số lớn,hệ thống thích nghi, trí tuệ nhân tạo v.v… Các đối tượng trong không gian số được biểu diễn bằng những cấu trúc dữ liệu khá lớn, thường là tập hợp của các dữ liệu kiểu vector nên thay vì một giá trị trọng số thì cần tới cả một ma trận trọng số, đó là những phép xử lý ngưỡng, phép chuyển tọa độ. Trong trường hợp tổng quát có thể biểu diễn phép xử lý tín hiệu số thông qua mối quan hệ hàm: m 1 m 1 n 1 Z   Zi  i 0  (Yi   Wij X j ) i 0 j 0 (1) Mã Hadamard có những ưu điểm vượt trội: đơn giản (chỉ có giá trị 1 hoặc -1); trực giao... nên dễ áp dụng trong hệ thống số. Luồng dữ liệu đầu ra Z trong là tổng giá trị đầu vào tương ứng Yi với tích giá trị dữ liệu đầu vào Xj và trọng số Wij. Đối với mã Hadamard, ví dụ H8, Wij có cấu trúc W8,8 như thể hiện trên hình 2. 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 H 8  1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 1  1  1  1  1  1  1  1 1  1  1  1 1  1  1  1 Hình 2. Mã Hadamard 8×8 tách thành 2 nửa 8×4 và 8×4. Điều quan trọng là H8×8 có thể tách thành 2 nửa ma H8×4 trận khi tách theo cột và nếu như vậy độ phức tạp của ma trận trọng số đã giảm đi một nửa. Cũng như vậy, ma trận trọng số gốc H8×8 cũng có thể tách thành 2 ma trận theo hàng là 2 nửa ma trận H4×8. 2.2. Ma trận trọng số Hadamard tối giản Trong các hệ thống thực tế, đối với cấu trúc ma trận trọng số cần lưu ý là về mặt lý thuyết luôn luôn có thể tạo ra một ma trận trọng số đầy đủ Wi,j, song thực tế không hẳn như vậy do tài nguyên phần cứng là hữu hạn trong khi dữ liệu xử lý không có giới hạn về kích thước. Do vậy, các ma trận trọng số được chế tạo trong các chip thường có kích thước không lớn, vì thế khi xử lý một vector dữ liệu có thể cần phải chia thành 2, 4, 8 ... thì mới thực hiện được nhiệm vụ. Những trường hợp như vậy trọng số của ma trận phải tái nạp nhiều lần gây trễ hệ thống rất lớn. Trong [1] đưa ra một cấu trúc xử lý luồng dữ liệu vector trên ma trận Hadamard với cấu trúc tối giản như thể hiện trên hình 1. Ở đây, ma trận trọng số gốc H8×8 được tách thành 16 ma trận (chia đôi theo cột và chia 8 theo hàng) là 2 nửa ma trận H1×4. Vấn đề là một ma trận khuyết như vậy khi thực hiện với cấu trúc dữ liệu 8×8 thì phải qua nhiều vòng lặp. Hãy xem cách thức làm việc của ma trận khuyết này. Luồng dữ liệu X qua XFIFO đưa 1 word 64 bit vào than ...