Nén Bitstream sử dụng Run-Length Encodinh trên nền hệ nhúng FPTGA

Kỹ thuật điện tử & Khoa học máy tính V.H.Thế, T.Thanh, P.N.Nam, P.N.Thắng, "Nén Bitstream sử dụng hệ nhúng FPGA." 126 NéN BITSTREAM Sử DụNG RUN-LENGTH ENCODING TRÊN NềN Hệ NHúNG FPGA Vũ HUY THế*, TRầN THANH**, PHạM NGọC NAM***, PHạM NGọC THắNG* Tóm tắt: Công nghệ FPGA hiện nay được sử dụng rộng rãi trong các hệ thống có thể cấu hình lại. Thông tin cấu hình (bitstream) cho FPGA thường nằm trên một bộ nhớ trong hoặc ngoài. Việc nén bitstream là rất quan trọng trong thiết kế hệ thống cấu hình lại sử dụng FPGA vì nó làm giảm kích thước bitstream, dung lượng của bộ nhớ yêu cầu. Hơn nữa, việc nén bitstream còn cải thiện băng thông và làm giảm thời gian cấu hình hệ thống. Trong bài báo này, các tác giả thực hiện một kỹ thuật nén bitstream sử dụng mã run-length trên nền tảng phần cứng mới. Phần nén bitstream được thực hiện trên máy tính còn phần giải nén thực hiện trên hệ nhúng của FPGA. Kết quả đạt được khả dụng trong thực tế với tỉ số nén tốt, chi phí phần cứng giải nén là chấp nhận được. Từ khóa: FPGA, Nén Bitstream, Mã Run-Length, Tỉ số nén. 1. Mở ĐầU Trong những năm gần đây, FPGA (Field-Programmable Gate Array) đang được sử dụng rộng rãi trong các hệ thống nhúng và cấu hình lại. FGPA được cấu hình nhờ các bitstream được tải lên từ bộ nhớ. Việc nén bitstream đem lại những lợi ích thiết thực như: sử dụng ít dung lượng, và cải thiện băng thông của bộ nhớ lưu trữ thông tin cấu hình và giảm thời gian cấu hình. Do đó, vấn đề này đang nhận được sự quan tâm nghiên cứu của nhiều nhà khoa học. Andreas Dandalis và K. Prasanna đề xuất một thuật toán nén bitstream nhằm giảm thiểu bộ nhớ chứa thông tin cấu hình của FPGA [4]. Kỹ thuật này được ứng dụng với các FPGA dựa trên SRAM kiểu nén từ điển và được bắt nguồn từ thuật toán LZW (Lempel Ziv Welch). Thuật toán này có hiệu năng giải nén cao nhưng chi phí phần cứng giải nén đắt đỏ. Sau đó, Stefan và cộng sự đề xuất một phương pháp nén sử dụng mã toán học và kiểu nén từ điển [5], tuy nhiên hạn chế của các kỹ thuật này là chi phí phần cứng giải nén còn khá cao và chưa có mô hình mạch đệm của phần cứng giải nén. Kỹ thuật nén từ điển sau đó được cải tiến bởi Seong và cộng sự, khi sử dụng các mặt nạ bit (bitmask) [8]. Kỹ thuật nén bitmask được thiết kế để làm giảm kích thước của từ điển từ đó làm tăng hiệu quả nén. Wolfe và Chanin lần đầu tiên đề xuất mã Huffman để nén trên kiến trúc nhúng RISC (Reduced Instructions Set Computer) [6]. Hai phương pháp nén mã mới sử dụng mã V2F (Variable to Fixed) cho hệ thống nhúng đã được đề xuất bởi Y. Xie, W.Wolf và H.Lekatsas [7]. Phương pháp thứ nhất dựa trên mã Tunstall và phương pháp thứ hai dựa trên việc chỉnh sửa mã toán học. Vì độ dài mã được cố định nên hoạt động có thể được thực hiện dễ dàng cùng với chi phí phần cứng O(n) hợp lý cho bộ đệm n-bit, bởi vì tất cả các mã có độ dài giống nhau và chỉ cần một bộ ghi dịch. Kỹ thuật nén bitstream hỗ trợ giải nén song song mà không cần hy sinh hiệu năng nén do Qin và cộng sự đề xuất [9] cho phép tăng băng thông giải mã bằng việc sử dụng nhiều bộ giải mã đồng thời và có thể sử dụng bất kỳ một thuật toán nén nào hiện có. Tuy vậy, mạch đệm sẽ phức tạp hơn nhiều khi độ dài từ mã thay đổi. Như vậy, các thuật toán nén bitstream đã đề xuất có thể chia thành hai nhóm: nhóm đầu tiên có tỉ số nén tốt, nhưng khó chấp nhận trong giải nén vì chi phí và độ phức tạp cao. Nhóm còn lại hiệu quả trong giải nén nhưng lại có tỉ số nén không tốt.Vì vậy, thách thức lớn trong kỹ thuật nén bitstream là tỉ số nén tốt và hiệu quả giải nén cao. Do đó, bài báo sẽ đề xuất một phương án nén và giải nén bitstream trên cơ sở sử dụng mã RLE (Run-length compression) [3]. Phần nén được thực hiện trên máy tính, phần giải nén thực hiện trên nền tảng phần cứng mới, đó là hệ nhúng của FPGA.Kết quả đạt được cho thấy, tỉ số nén tốt và chi phí giải nén chấp nhận được trong ứng dụng thực tế. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014 127 2. NéN BITSTREAM Sử DụNG THUậT TOáN Độ DàI LOạT RLE 2.1. Nêu vấn đề Thông tin cấu hình cho FPGA chứa trong các bộ nhớ thường bị giới hạn về dung lượng và băng thông. Kích thước và băng thông của bộ nhớ lưu trữ thông tin cấu hình trở thành một tham số trong việc xác định số lõi IP (Intellectual Property Core) mà hệ thống có thể được cấu hình và độ trễ trong việc cấu hình lại. Các thuật toán nén bitstream sẽ giải quyết vấn đề bộ nhớ bằng cách giảm kích thước bitstream và tăng tốc độ cấu hình. Các phần cứng giải nén sẽ giải mã và truyền các bit (đã giải nén) tới các CLB (Configurable Logic Block) trên FPGA. Tỉ số nén thường được sử dụng để xem xét hiệu quả của các kỹ thuật nén và được định nghĩa như sau [1]: CP CR OP  (1) trong đó, CR (Compression Ratio) là tỉ số nén, CP (Compressed Program) là kích thước chương trình đã nén, OP (Original Program) là kích thước dữ liệu gốc ban đầu. 2.2. Cấu trúc bitstream của hãng Xilinx Bitstream có thể được chia thành các đơn vị riêng biệt được gọi là các gói tin. Mỗi gói bao gồm một tiêu đề (header) 32-bit, tiêu đề này sẽ định nghĩa các thanh ghi sẽ được ghi vào hoặc đọc ra, số lượng các từ dữ liệu 32-bit trong gói tin, các thông tin khác liên quan đến gói tin. Ngay sau tiêu đề là đến các từ dữ liệu với các thông tin liên quan như trong tiêu đề đã định nghĩa. Bitstream được tạo thành các gói để ghi và cấu hình cho FPGA [10]. Có hai cách được sử dụng để ghi dữ liệu lên FPGA là ghi tuần tự và ghi đa khung MFW (Multipe Frame Write) [11]. Mỗi cách ghi đó bao gồm nhiều gói tin và được thực hiện từ việc thiết lập cho các thanh ghi cấu hình đến việc gửi đi các dữ liệu cấu hình cho thiết bị. Có hai loại bitstream chính sử dụng cho cấu hình FPGA: Bitstream đầy đủ (Full bitstream) và bitstream từng phần (Partial bitstream). Bitstream đầy đủ có chứa tất cả các lệnh cần thiết để khởi tạo FPGA. Thông thường một bitstream cấu hình khởi tạo ban đầu là một bitstream đầy đủ. Bitstream từng phần không chứa các lệnh khởi tạo bởi vì nó được sử dụng để cấu hình FPGA trong quá trình thực thi và sau khi việc khởi tạo cấu hình đã hoàn thành. Một bitstream từng phần sẽ ghi đè lên một vùng cấu hình từng phần. Cấu hình từng phần PR (Partial Reconfiguration) linh hoạt, cho phép sửa đổi, bổ sung một thiết kế trên FPGA bằng cách tải một file cấu hình từng phần ngay khi hệ thống vẫn đang hoạt động. Sau khi một tập tin bit đầy đủ cấu hình cho FPGA, các tập tin bit từng phần có thể được nạp xuống để sửa đổi các khu vực cấu hình lại trong FPGA mà không làm ảnh hưởng đến tính toàn vẹn của các ứng dụng chạy trên các bộ phận khác của thiết bị. FPGA Khối cấu hình lại “A” A4.bit A3.bit A2.bit A1.bit Hình 1. Tiền đề cơ bản của cấu hình từng phần. Như mô tả trên Hình 1, chức năng được thực hiện tại khối cấu hình lại A được sửa đổi bằng cách nạp xuống một trong số các tập tin bit từng phần, A1.bit, A2.bit, A3.bit hoặc A4.bit. Thiết kế FPGA được chia thành hai dạng khác nhau, phần logic cấu hình lại và phần logic tĩnh. Vùng màu xám của khối FPGA đại diện cho phần logic tĩnh và phần khối có nhãn cấu hình lại "A" đại diện cho phần logic cấu hình lại. Phần logic tĩnh vẫn hoạt động bình thường và hoàn Kỹ thuật điện tử & Khoa học máy tính V.H.Thế, T.Thanh, P.N.Nam, P.N.Thắng, "Nén Bitstream sử dụng hệ nhúng FPGA." 128 toàn không bị ảnh hưởng bởi việc nạp xuống một tập tin bit từng phần. Phần logic cấu hình lại được từng phần có thể thay thế bằng nội dung của các tập tin bit từng phần. 2.3. Xây dựng cấu trúc hệ thống Cấu trúc bitstream có nhiều các từ nhị phân giá trị giống nhau được lặp lại liên tiếp. Đây là những vùng tài nguyên của FPGA mà chưa được sử dụng đến. Đặc điểm của bitstream như vậy có thể phát huy được ưu điểm của mã RLE. Thông thường, sau khi giải nén xong, bitstream sẽ được chứa trong khu vực cấu hình của hệ thống, rồi sau đó FPGA sẽ được cấu hình. Tuy nhiên, các tác giả đưa ra giải pháp là sẽ kết hợp với khả năng cấu hình từng phần của các chip FPGA: sau khi giải nén xong, mỗi phần bitstream sẽ được đưa ngay sang khối cấu hình từng phần để thực hiện cấu hình ngay thay vì việc phải chờ giải nén xong toàn bộ bitstream. Như vậy, giải pháp đưa ra có thể làm giảm được thời gian cấu hình của FPGA. Sơ đồ khối của hệ thống được xây dựng như hình 2. Hình 2. Sơ đồ khối hệ thống. Theo cấu trúc hình 2, các tác giả đề xuất phương án thực hiện như sau: Trên máy tính: Sẽ thực hiện nén file cấu hình (file *.bit) của FPGA. Máy tính sẽ được cài đặt chương trình nén theo thuật toán RLE. Kết thúc qu átrình trên máy tính là một file đã được nén. Tiếp theo đó file này sẽ được truyền từ máy tính xuống bộ nhớ được đặt trên Kit FPGA. Trên Kit FPGA: - Khối bộ nhớ: Có nhiệm vụ lưu trữ thông tin cấu hình đã được nén. Các thông tin này sẽ được đọc ra trong quá trình giải nén. - Giải nén RLE: Thực hiện giải nén theo thuật toán RLE. Sau khi giải nén xong thì thông tin cấu hình gốc ban đầu sẽ được chuyển sang khối thực hiện cấu hình để cấu hình cho chip FPGA. - Cấu hình: Khối này thực hiện cấu hình cho FGPA. Thông tin cấu hình từ khối giải nén sẽ được đưa vào khối này để thực hiện cấu hình. Việc cấu hình có thể sẽ được cấu hình toàn phần hoặc là cấu hình từng phần. 2.4. Kết quả thiết kế hệ thống Các tác giả đã xây dựng hệ thống nén và giải nén bitstream gồm hai phần chính: chương trình nén trên máy tính và chương trình giải nén trên Kit FPGA. 2.4.1. Xây dựng phần mềm nén bitstream trên máy tính Chương trình nén trên máy tính được viết bằng Visual C++ có giao diện như hình 3. Trên KIT FPGA Trên máy tính File cấu hình hệ thống (bitstream file) Nén RLE Code đã nén Bộ nhớ Trên FPGA Giải nén RLE Cấu hình Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014 129 Hình 3. Giao diện chương trình nén trên máy tính. Số bít trên mẫu sẽ qui định số lượng các byte tối đa lặp lại liên tiếp (length value) của một ký tự. Theo (1), kết quả khảo sát về sự phụ thuộc của tỉ số nén CR vào dung lượng file bitstream đầu vào với số bít trên mẫu để cố định là 8 bít tương đương với 256 mẫu và thu được kết quả như hình 4. Hình 4. Mối quan hệ tỉ số nén với các file bitstream kích thước khác nhau. Theo như đồ thị hình 4 ta có thể thấy rằng, tỉ số nén có xu hướng giảm khi mà kích thước của file bitstream đầu vào tăng. Điều này là hoàn toàn có lợi bởi lẽ khi đó dung lượng của bộ nhớ lưu trữ sẽ giảm đi rất đáng kể. Tỉ số nén giảm có thể được giải thích như sau: khi kích thước file bitstream tăng thì số lượng các ký tự lặp lại liên tiếp lớn hơn. Chính vì lý do đó mà tỉ số nén sẽ giảm. Kết quả khảo sát về sự phụ thuộc của tỉ số nén vào số lượng bít trên mẫu được mô tả trên biểu đồ ở hình 5. Ta có thể thấy rằng, với cùng một file bitstream đầu vào thì tỉ số nén có xu hướng tăng lên khi mà số bít trên mẫu tăng. Điều này là do khi số lượng bít trên mẫu tăng thì số lượng các ký tự lặp liên tiếp có thể lưu trữ được tăng và kích thước bộ nhớ cần lưu trữ giá trị trên cũng tăng. Tuy nhiên, thực tế, số lượng các ký tự lặp lại liên tiếp không phải chỗ nào cũng nhiều đến như vậy nên tỉ số nén có xu hướng tăng lên khi mà số lượng bít trên mẫu tăng. Do vậy, chúng ta có thể thấy rằng, sử dụng RLE để nén bitstream là rất phù hợp vì nó cho phép tỉ số nén khá nhỏ: với bitstream có dung lượng lớn gần 9 MB mà tỉ số nén đạt được là hơn 5%, một kết quả rất tốt. Điều này sẽ làm giảm chi phí khi bộ nhớ cần lưu trữ khá lớn. Hình 5. Mối quan hệ giữa tỉ số nén và số lượng bít trên mẫu Kỹ thuật điện tử & Khoa học máy tính V.H.Thế, T.Thanh, P.N.Nam, P.N.Thắng, "Nén Bitstream sử dụng hệ nhúng FPGA." 130 2.4.2.Xây dựng phần cứng và chương trình giải nén bitstream trên Kit FPGA Sơ đồ khối chi tiết của phần cứng giải nén bitstream mà các tác giả thực hiện được mô tả trên hình 6. Hình 6. Sơ đồ khối phần cứng giải nén. Giải pháp thực hiện: - Khối Nền tảng phần cứng: các tác giả sử dụng Virtex 6- FPGA ML605 Evaluation Kit. - Khối FPGA: Là chip Virtex 6-xc6vlx240t của hãng Xilinx. Trong chip FPGA này, các tác giả xây dựng một vi xử lý lõi mềm MicroBlaze đơn nhân với tần số xung nhịp là 100 Mhz. Chip lõi mềm sẽ giao tiếp với máy tính thông qua khối UART, đây là bộ điều khiển truyền thông nối tiếp không đồng bộ theo giao thức RS232. Các tác giả sẽ cài đặt thuật toán giải nén trên chip lõi mềm này. Sau khi giải nén xong, bitstream ban đầu được khôi phục sẽ được đưa qua khối cấu hình để thực hiện cấu hình. - Khối Bộ nhớ DRAM: Đây là khối sẽ chứa chương trình giải nén, dữ liệu đã nén từ máy tính gửi xuống và dữ liệu đã giải nén. Trên thực tế, khối DRAM này sẽ được thay bởi một chip nhớ để chứa bitstream đã được nén. Còn dữ liệu sau giải nén sẽ được đưa thẳng sang khối cấu hình. Chương trình giải nén trên FPGA được viết bằng ngôn ngữ C chạy trên vi xử lý lõi mềm MicroBlaze. Hình 7 là ví dụ về kết quả chạy chương trình trên phần cứng thực tế. Kết quả giải nén mô tả trên hình 8. Hình 8. Thời gian giải nén trên phần cứng. Hình 7. Kết quả chạy chương trình giải nén trên phần cứng. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014 131 Trên hình 8 thể hiện mối quan hệ giữa thời gian giải nén của các bitstream có kích thước khác nhau. Chúng ta có thể thấy rằng với những bitstream có kích thước tăng thì thời gian giải nén cũng tăng. Thời gian thực hiện giải nén vẫn còn khá lớn. Việc này có thể sẽ được khắc phục bằng cách tăng tốc độ xung nhịp, số lõi của MicroBlaze, hoặc thiết kế phần cứng giải nén theo thuật toán RLE. 3. KếT LUậN Phương pháp nén bitstream đã trình bày trong bài báo trên cơ sở thuật toán RLE đã cho tỉ số nén tốt hơn so với các kỹ thuật nén bitstream khác. Kỹ thuật nén này kết hợp với khả năng cấu hình từng phần của các FPGA sẽ đem đến một giải pháp hiệu quả trong việc giảm dung lượng và băng thông bộ nhớ yêu cầu. Phần thực hiện giải nén, các tác giả đã thực hiện trên phần mềm nhúng sử dụng vi xử lý lõi mềm MicroBlaze nên thời gian thực hiện giải nén vẫn còn cao. Như vậy, việc thực hiện giải nén RLE trên hệ nhúng của FPGA sẽ phù hợp với những bài toán mà giới hạn về dung lượng và băng thông của bộ nhớ lưu trữ thông tin cấu hình. Trong tương lai, các tác giả sẽ thiết kế phần cứng thực hiện giải nén để giảm thời gian giải nén từ đó góp phần giảm thời gian cấu hình cho hệ thống. TàI LIệU THAM KHảO [1]. Xiaoke Qin, Chetan Muthry, and Prabhat Mishra, “Decode-Aware Compression of FPGA Bitstreams”, IEEE Trans. Very Large Scale Integr. (VLSI) Syst, vol. 19, no. 3, March 2011 [2]. M.K.Drisya, S.Josepth, “Compression of FPGA Bitstreams-A Comparison”, Bonfring International Journal of Power Systems and Integrated Circuits, Vol. 2, Special Issue 1, Part 3, February 2012. [3]. S. Hauck, W.D.Wilson, “Runlength Compression Techniques for FPGA Configurations”, IEEE Symposium on FPGA for Custom Computing Machines, 1999 [4]. A. Dandalis, V. K. Prasanna, “Configuration compression for FPGA-based embedded systems,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 13, no. 12, Dec. 2005, pp . 1394–1398 [5]. R. Stefan and S. Cotofana, “Bitstream compression techniques for Virtex 4 FPGAs”, in Proc. Int. Conf. Field Program. Logic Appl.,2008, pp. 323–328. [6]. A. Wolfe, A. Chanin, “Executing Compressed Programs on an Embedded RISC Architecture”, Proceedings of the International Symposium on Microarchitecture, December 1992,pages 81–91. [7]. Y. Xie, W. Wolf, H. Lekatsas, “Code compression for VLIW processors using variable-to-fixed coding,” in Proc. Int. Symp. Syst. Synth.,2002, vol. 2, no. 04, pp. 138 –143 [8]. S. Seong and P. Mishra, “Bitmask-based code compression for embedded systems,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 27, no. 4, Apr. 2008, pp. 673–685. [9]. Xiaoke Qin, Prabhat Mishra, “Efficient placement of compressedcode for parallal decompression”, VLSI Design, 22nd International Conference, Jan. 2009, pp. 335-340. [10]. “Virtex-4 FPGA Configuration User Guide v1.10 (UG071)”, Xilinx, Inc., San Jose, CA, April 2008. [11]. “Virtex FPGA Series Configuration and Readback v2.8 (XAPP138)”, Xilinx, Inc., San Jose, CA, March 2005. Kỹ thuật điện tử & Khoa học máy tính V.H.Thế, T.Thanh, P.N.Nam, P.N.Thắng, "Nén Bitstream sử dụng hệ nhúng FPGA." 132 ABSTRACT BITSTREAM COMPRESSION USING RUN-LENGTH ENCODING BASE ON FPGA EMBEDDED SYSTEM Field-Programmable Gate Array (FPGAs) are widely used in reconfigurable systems. The configuration information for FPGA has to be stored in internal or external memory as bitstreams.Bitstream compression is very important in reconfigurable system design since it reduces the bitstream size and ban the memory requirement. It also improves the communication bandwidth and there by decreases the reconfiguration time. In this paper, we implemented technique bitstream compression using run-length encoding base on new flatform. Compression was done on the computer and decompression on FPGA embedded system. The result is available, good compression ratio and decompression may be acceptable for hardware implementation. Keywords: FPGA, Bitstream compression, Run-length encoding, Compression ratio. Nhận bài ngày 25 thỏng 12 năm 2013 Hoàn thiện ngày 08 thỏng 01 năm 2014 Chấp nhận đăng ngày 10 thỏng 04 năm 2014 Địa chỉ: * Đại học Sư phạm Kỹ thuật Hưng Yên. ** Viện Điện tử Tin học và Tự động hóa. *** Đại học Bách khoa Hà Nội.