Thiết kế phần cứng tính toán các hàm toán học dựa trên xấp xỉ tuyến tính hai mức
Tóm tắt: Bài báo này trình bày một phương pháp tính toán các hàm toán học
phổ biến dựa trên hai mức xấp xỉ. Trong mức xấp xỉ thứ nhất, hàm được xấp xỉ bằng
phương pháp xấp xỉ phân đoạn tuyến tính đều. Sau đó, ở mức xấp xỉ thứ hai các
hàm lỗi do mức xấp xỉ thứ nhất sẽ được xấp xỉ bởi phương pháp phân đoạn tuyến
tính có nội suy đối xứng nhằm giảm thiểu độ phức tạp của phần cứng. Dựa trên
phương pháp đề xuất, kiến trúc phần cứng để tính toán các hàm toán học điển hình
được thiết kế và thực thi. Các kết quả thực thi cho thấy kiến trúc phần cứng đề xuất
đạt được hiệu quả về tốc độ.
ao cho maxij nhận giá trị cực tiểu trong đoạn thứ j . Thuật toán tìm các hệ số tối ưu được mô tả như bảng 1. Bài báo sử dụng một chương trình Matlab thực hiện thuật toán trên để tính toán các hệ số ija và ijb tối ưu cho các hàm 2log ( ), sin( ), 1 / , , 1x x x x x và 2 x với các khoảng giá trị đầu vào được chuẩn hóa như thể hiện trên bảng 2 và tương ứng với xấp xỉ mức 1 gồm 8 đoạn ( 1 3n ) và ở xấp xỉ mức 2 sử dụng xấp xỉ phân đoạn nội suy đối xứng trong đó mỗi hàm ( ')ie x được xấp xỉ bởi hai cặp đoạn đối xứng. Bảng 3 thể hiện kết quả các hệ số ija và ijb tối ưu cho hàm 2log ( )x . Bảng 1. Thuật toán tìm hệ số tối ưu của xấp xỉ mức 2. 1: BEGIN: Khởi tạo mảng giá trị ija Khởi tạo mảng giá trị ijb Khởi tạo đoạn giá trị j 2: for i = 1: length( ija ) for j = 1:length( ijb ) for k = 1:length( 'x ) tính ( ')ij x theo công thức (3) end end end 3: for i = 1: length( ija ) for j = 1:length( ijb ) tính ij max ijmax( ( '))x end end 4: Tính ij maxmin( ) 5: END: Xuất giá trị a, b tương ứng với ij maxmin( ) Bảng 2. Khoảng giá trị đầu vào chuẩn hóa của các hàm. Hàm 2log ( )x sin( )x 1 x x 1 x 2x Khoảng giá trị đầu vào chuẩn hóa [1, 2) [0, 1) [1, 2) [1, 2) [1, 2) [0, 1) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 57 Bảng 3. Các hệ số ija và ijb tối ưu ở mức xấp xỉ thứ 2 của hàm 2log ( )x . 0 ( ')e x 00a 00b 01a 01b 4 ( ')e x 40a 40b 41a 41b 42 2058.2 52 20791.2 52 0 7 102 2 20672.2 1( ')e x 10a 10b 11a 11b 5 ( ')e x 50a 50b 51a 51b 5 6 92 2 2 2072.2 6 92 2 201024.2 6 72 2 2040.2 72 20561.2 2 ( ')e x 20a 20b 21a 21b 6 ( ')e x 60a 60b 61a 61b 5 72 2 2065.2 7 82 2 20986.2 62 2088.2 72 20427.2 3( ')e x 30a 30b 31a 31b 7 ( ')e x 70a 70b 71a 71b 5 92 2 2048.2 7 9 102 2 2 20775.2 62 2051.2 82 20512.2 III. KIẾN TRÚC PHẦN CỨNG VÀ KẾT QUẢ THỰC THI Kiến trúc tổng quát thực thi các hàm toán học của phương pháp đề xuất có dạng như hình 5. Trong mức xấp xỉ thứ nhất thực hiện tính toán hàm ( ')if x như công thức (1). Trong đó, các giá trị ( )if x và 1( ) ( )i if x f x được lưu vào trong các bảng tra (LUT: Lookup Table) được sử dụng để tính toán hàm ( ')if x . Phép chia cho 1i ix x trong công thức (1) được thay thế bởi một phép dịch bởi vì nó là một số lũy thừa của 2. Ở mức xấp xỉ thứ 2, thực hiện xấp xỉ các hàm lỗi bằng phương pháp xấp xỉ phân đoạn tuyến tính có đối xứng. Khối xấp xỉ sửa lỗi sẽ bao gồm 12n khối xấp xỉ tương ứng với 12n hàm ( ')ie x . Hình 5. Kiến trúc phần cứng tổng quát. Chúng tôi đã thực thi kiến trúc đề xuất để tính toán các hàm 2log ( ), sin( ), 1 / , , 1x x x x x và 2 x với định dạng 23 bit thập phân dữ liệu đầu vào và đầu ra. Về nguyên tắc khi tăng số phân đoạn ở mức xấp xỉ thứ nhất ( 1n lớn) thì sẽ đạt được độ chính xác cao hơn, tuy nhiên, điều đó sẽ dẫn đến tăng độ phức tạp phần cứng. Vì vậy, để dung hòa giữa độ phức tạp phần cứng và độ chính xác nhận được chúng tôi thực thi với xấp xỉ mức 1 với 8 phân đoạn ( 1 3n ). Ngoài ra, trong mức xấp xỉ thứ hai, mỗi Kỹ thuật điều khiển & Điện tử S. V. Thuận, H. V. Phúc, T. V. Khẩn, “Thiết kế phần cứng xấp xỉ tuyến tính hai mức.” 58 hàm lỗi ( ')ie x được xấp xỉ bởi phân đoạn tuyến tính của hai cặp đoạn đối xứng. Các kiến trúc đề xuất đã được mô hình trên ngôn ngữ VHDL và thực thi trên thiết bị FPGA Xilinx Virtex6 với công cụ tổng hợp Xilinx ISE 12.4 Suite. Kết quả thực thi trên FPGA của các kiến trúc đề xuất thể hiện trên bảng 4. Bảng 5 thể hiện kết quả tổng hợp bằng Synopsys Design Compiler cho các hàm khác nhau của phương pháp đề xuất với mục đích tối thiểu tài nguyên trên công nghệ CMOS 90 nm. Phương pháp đề xuất cũng được so sánh với kết quả trong [9] với cùng định dạng 23 bit thập phân của dữ liệu đầu vào và đầu ra. Phương pháp đề xuất đã đạt được tốc độ cao hơn đáng kể so với phương pháp trong [9]. Tuy nhiên, tài nguyên chiếm lớn hơn so với kết quả trong [9]. Bảng 4. Kết quả thực thi của các kiến trúc đề xuất trên FPGA Xilinx Virtex6. Hàm 2log ( )x sin( )x 1 x x 1 x 2x Slices 789 755 1005 897 894 885 Delay(ns) 6.79 6.76 7.28 6.78 7.33 7.73 ADP(×103) 5.42 5.10 7.32 6.08 6.55 6.84 Bảng 5. Kết quả tổng hợp trên Synopsys Design Compiler. Hàm Đề xuất Trong [9] Diện tích ( µm2) Độ trễ (ns) Diện tích (µm2) Độ trễ (ns) 2log ( )x 26695 3.98 24023 12.69 sin( )x 24452 3.86 22890 13.08 1 x 32736 3.99 24137 12.63 x 27213 3.83 16043 12.03 1 x 28752 4.00 22317 12.83 2x 30887 3.86 18913 12.16 IV. PHÂN TÍCH LỖI Để đánh giá độ chính xác của phương pháp đề xuất, chúng tôi phân tích lỗi gây ra bởi các thành phần phần cứng trong sơ đồ thực thi và tác động của chúng tới đầu ra. Các lỗi này bao gồm lỗi lượng tử do độ rộng bit hạn chế của các từ nhớ trong ROM (ký hiệu là ROM ), lỗi gây ra bởi bộ nhân rút gọn ( MUL ), lỗi xấp xỉ do xấp xỉ mức hai ( 2apx ) và lỗi làm tròn của bộ cộng cuối cùng ( ADD ). Vì vậy, lỗi tổng cộng sẽ là: 2total ROM MUl ADD apx (6) Bảng 6. Lỗi của các modul phần cứng. Modul ROM Bộ nhân rút gọn Bộ cộng Độ rộng bit FB MB AB Modul 12 FB 12 MB 12 AB ROM 12 FB MUL 12 2F MB B ADD 12 AB Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 59 Ký hiệu ,F MB B và AB là độ rộng bit tương ứng của các bộ nhớ ROM, bộ nhân rút gọn và bộ cộng, chúng ta có thể biểu diễn lỗi do các thành phần phần cứng này gây ra như trên bảng 6. Lỗi xấp xỉ ở mức 2, 2apx , được xác định là lỗi tuyệt đối lớn nhất do xấp xỉ ở mức 2 của tất cả các hàm ( ')ie x . Trong thực thi phần cứng chúng tôi thực hiện xấp xỉ mức 1 với 8 phân đoạn ( 1 3n ) tương ứng tạo ra 8 hàm lỗi ( ')ie x và mỗi hàm lỗi này được xấp xỉ bởi phân đoạn tuyến tính của hai cặp đoạn đối xứng. Độ rộng bit của ROM và bộ cộng là 23 bit ( 23F AB B ) và độ rộng bit của bộ nhân rút gọn là 20 bit ( 20MB ). Khi đó, các thành phần lỗi và lỗi tổng cộng tương ứng với hàm khác nhau được biểu diễn như trên bảng 7. Bảng 7. Các lỗi thành phần và lỗi tổng cộng của thực thi các hàm. Hàm 2log ( )x sin( )x 1 x x 1 x 2 x ROM 2 -24 2-24 2-24 2-24 2-24 2-24 MUL 2 -23+ 2-19 2-23+ 2-19 2-23+ 2-19 2-23+ 2-19 2-23+ 2-19 2-23+ 2-19 ADD 2 -24 2-24 2-24 2-24 2-24 2-24 2apx 9.85×10- 5 7.95×10- 5 7.93×10- 5 2.04×10- 5 6.17×10- 5 8.79×10-4 total 1.01×10- 4 8.16×10- 5 8.14×10- 5 2.25×10- 5 6.38×10- 5 9.01×10-5 V. KẾT LUẬN Bài báo này đã trình bày một phương pháp tính toán các hàm toán học được ứng dụng phổ biến trong xử lý tín hiệu số dựa trên xấp xỉ hai mức, mức xấp xỉ thứ nhất dựa trên phương pháp xấp xỉ phân đoạn tuyến tính đều và mức xấp xỉ thứ hai là bước xấp xỉ hàm lỗi gây ra bởi mức đầu tiên theo phương pháp xấp xỉ phân đoạn tuyến tính có đối xứng. Các thực thi một số hàm toán học điển hình theo phương pháp đề xuất đã cho thấy hiệu quả về tốc độ xử lý. Vì vậy, kiến trúc đề xuất là phù hợp với các ứng dụng đòi hỏi tốc độ xử lý cao. TÀI LIỆU THAM KHẢO [1]. J. E. Volder, "The CORDIC Trigonometric Computing Technique," IRE Transactions on Electronic Computers, vol. EC-8, pp. 330-334, 1959. [2]. A. S. Noetzel, "An interpolating memory unit for function evaluation: analysis and design," IEEE Transactions on Computers, vol. 38, pp. 377-384, 1989. [3]. G. H. Garcia and W. J. Kubitz, "Minimum Mean Running Time Function Generation Using Read-Only Memory," IEEE Transactions on Computers, vol. C-32, pp. 147- 156, 1983. [4]. P. T. P. Tang, "Table-lookup algorithms for elementary functions and their error analysis," in Proceedings 10th IEEE Symposium on Computer Arithmetic, 1991, pp. 232-236. [5]. I. Koren and O. Zinaty, "Evaluating elementary functions in a numerical coprocessor based on rational approximations," IEEE Transactions on Computers, vol. 39, pp. 1030-1037, 1990. Kỹ thuật điều khiển & Điện tử S. V. Thuận, H. V. Phúc, T. V. Khẩn, “Thiết kế phần cứng xấp xỉ tuyến tính hai mức.” 60 [6]. J. A. Pineiro, S. F. Oberman, J. M. Muller, and J. D. Bruguera, "High-speed function approximation using a minimax quadratic interpolator," IEEE Transactions on Computers, vol. 54, pp. 304-318, 2005. [7]. M. J. Schulte and E. E. Swartzlander, "Hardware designs for exactly rounded elementary functions," IEEE Transactions on Computers, vol. 43, pp. 964-973, 1994. [8]. E. G. Walters and M. J. Schulte, "Efficient function approximation using truncated multipliers and squarers," in 17th IEEE Symposium on Computer Arithmetic (ARITH'05), 2005, pp. 232-239. [9]. S. F. Hsiao, H. J. Ko, and C. S. Wen, "Two-Level Hardware Function Evaluation Based on Correction of Normalized Piecewise Difference Functions," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 59, pp. 292-296, 2012. ABSTRACT A HARDWARE DESIGN FOR FUNCTION EVALUATION BASED ON TWO LINEAR APPROXIMATION LEVELS In this paper, a common method for computing math functions based on two approximation levels is presented. At the first approximation level, these math functions are approximated by the equal linear segment approximation approach. After that, at the second approximation level, the error functions in the first step will be approximated by the linear segment method, having symmetric interpolation, to reduce hardware complexity. Based on the proposed method, the hardware structure to compute typical math functions are designed and implemented. The performance results show that the proposed hardware achieves speed efficiency. Key words: Computer arithmetic; Function evaluation; Piecewise polynomial approximation. Nhận bài ngày 09 tháng 03 năm 2017 Hoàn thiện ngày 22 tháng 5 năm 2017 Chấp nhận đăng ngày 20 tháng 6 năm 2017 Địa chỉ: Học viện Kỹ thuật quân sự. *Email: saivanthuan@gmail.com
File đính kèm:
- thiet_ke_phan_cung_tinh_toan_cac_ham_toan_hoc_dua_tren_xap_x.pdf