Tài liệu: Luận văn acceleration of random forest on epga

Nghiên cứu tăng tốc thuật toán Random Forest trên FPGA. Phân tích phương pháp tối ưu hiệu suất xử lý dữ liệu và cải thiện tốc độ huấn luyện mô hình học máy.

• Tác giả: Phạm Đình Trung
• Người hướng dẫn: PGS. Phạm Quốc Cường
• Trường học: Trường Đại học Bách khoa TP.HCM
• Chuyên ngành: Kỹ thuật Máy tính
• Đề tài: Acceleration of Random Forest on FPGA
• Loại tài liệu: Luận văn tốt nghiệp
• Năm xuất bản: 2023
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Tổng quan luận văn acceleration of random forest on fpga

Sự phát triển của trí tuệ nhân tạo (AI) đã thúc đẩy nhu cầu về các nền tảng phần cứng hiệu năng cao. Trong số các thuật toán học máy, Random Forest nổi bật nhờ khả năng dự báo chính xác và chống quá khớp hiệu quả. Tuy nhiên, việc triển khai mô hình này trên các thiết bị biên gặp nhiều thách thức về tốc độ xử lý. Machine Learning hardware implementation trở thành hướng nghiên cứu trọng tâm để tối ưu hóa thời gian suy luận. Luận văn này tập trung vào việc thiết kế kiến trúc tăng tốc thuật toán trên nền tảng Field-Programmable Gate Array (FPGA). Đây là giải pháp tối ưu giúp cân bằng giữa hiệu suất xử lý song song và tính linh hoạt trong cấu hình. Hệ thống tích hợp khả năng xử lý hàng ngàn cây quyết định trong thời gian thực. Nghiên cứu thực hiện bởi tác giả Phạm Đình Trung tại Đại học Bách Khoa TP.HCM (HCMUT). Nội dung cốt lõi xoay quanh việc xây dựng các bộ xử lý cây quyết định chuyên biệt. Các thử nghiệm được tiến hành trên các dòng chip hiện đại như Zynq-7000 và Zynq UltraScale+ MPSoC.

1.1. Tầm quan trọng của FPGA acceleration trong AI

FPGA acceleration đóng vai trò quyết định trong việc đưa các mô hình AI phức tạp vào ứng dụng thực tế. Khác với GPU tiêu tốn nhiều năng lượng, FPGA cung cấp khả năng tùy chỉnh phần cứng ở mức thấp. Điều này cho phép tối ưu hóa luồng dữ liệu và giảm thiểu độ trễ truy cập bộ nhớ. Luận văn chứng minh rằng việc sử dụng System-on-Chip (SoC) giúp kết hợp sức mạnh của vi xử lý ARM và logic lập trình được. Sự kết hợp này tạo ra một hệ thống nhúng mạnh mẽ, đáp ứng các tiêu chuẩn khắt khe của ứng dụng IoT.

1.2. Cấu trúc Decision Tree Ensemble và thách thức

Mô hình Decision Tree Ensemble như Random Forest yêu cầu tài nguyên tính toán rất lớn. Mỗi rừng có thể chứa hàng trăm cây với hàng triệu tham số cần xử lý đồng thời. Việc thực hiện tuần tự trên CPU gây ra độ trễ lớn, không thể đáp ứng yêu cầu Real-time classification. Luận văn đề xuất phương pháp mã hóa các quy tắc quyết định thành tập lệnh chuyên dụng. Cách tiếp cận này giúp giảm thiểu không gian lưu trữ và tăng tốc độ truy xuất dữ liệu từ Block RAM (BRAM).

II. Thách thức khi triển khai Machine Learning hardware implementation

Triển khai thuật toán học máy trên phần cứng đối mặt với rào cản về tài nguyên hạn chế. Các mô hình Random Forest thường có kích thước lớn, vượt quá khả năng lưu trữ nội tại của chip. Việc quản lý Resource utilization (LUT, FF, BRAM) là bài toán khó đối với các kỹ sư thiết kế. Nếu không có chiến lược tối ưu, hệ thống dễ rơi vào tình trạng thiếu hụt bộ nhớ hoặc tiêu thụ điện năng cao. Luận văn chỉ ra rằng việc truy cập bộ nhớ ngoài thường xuyên làm tăng đáng kể Inference latency. Ngoài ra, sự khác biệt giữa tính toán số thực dấu phẩy động và số nguyên cũng ảnh hưởng đến độ chính xác. Để giải quyết, nghiên cứu áp dụng kỹ thuật Fixed-point arithmetic và tối ưu hóa cấu trúc dữ liệu. Mục tiêu là xây dựng một kiến trúc có khả năng mở rộng, phù hợp với nhiều loại tập dữ liệu khác nhau. Hệ thống phải đảm bảo tính ổn định khi hoạt động liên tục trong môi trường công nghiệp.

2.1. Vấn đề Inference latency trên các thiết bị biên

Độ trễ suy luận (Inference latency) là thông số then chốt trong các ứng dụng thời gian thực. Trên các kiến trúc CPU truyền thống, việc duyệt qua hàng ngàn nút của cây quyết định diễn ra chậm chạp. Điều này do hạn chế về khả năng tính toán song song và băng thông bộ nhớ. Luận văn tập trung giảm thiểu rào cản này bằng cách thiết kế các Decision Tree Processor (DTP) hoạt động độc lập. Mỗi bộ xử lý có thể thực hiện việc so sánh và rẽ nhánh chỉ trong vài chu kỳ xung nhịp.

2.2. Tối ưu hóa Resource utilization LUT FF BRAM

Việc sử dụng hiệu quả tài nguyên phần cứng như Look up table (LUT) và Flip-Flop (FF) quyết định quy mô của rừng có thể triển khai. Luận văn đề xuất cấu trúc bộ nhớ phân cấp để lưu trữ các quy tắc quyết định. Thay vì lưu địa chỉ tuyệt đối, hệ thống sử dụng địa chỉ tương đối để giảm số bit cần thiết. Kỹ thuật này giúp tiết kiệm đến 50% không gian lưu trữ trên Block RAM (BRAM) mà vẫn đảm bảo tốc độ truy cập nhanh chóng.

III. Phương pháp thiết kế Hardware architecture for Random Forest

Kiến trúc phần cứng đề xuất dựa trên các khối xử lý cây quyết định (DTP) có khả năng cấu hình lại. Toàn bộ hệ thống được mô tả bằng ngôn ngữ SystemVerilog và tích hợp các IP core từ Xilinx Vivado. Điểm đặc biệt của kiến trúc này là khả năng xử lý song song nhiều cây cùng lúc. Các thành phần chính bao gồm Sample FIFO, Samples Manager, DTPs, Accumulator và Out Buffer. Luận văn sử dụng cơ chế Direct Memory Access (DMA) để truyền dữ liệu tốc độ cao giữa PS và PL. Điều này giúp loại bỏ sự can thiệp của CPU trong quá trình xử lý, tối ưu hóa Throughput optimization. Kiến trúc được thiết kế theo dạng module, cho phép dễ dàng thay đổi số lượng DTP để phù hợp với từng nền tảng FPGA cụ thể. Việc tích hợp Pipelining in FPGA vào từng giai đoạn xử lý giúp nâng cao tần số hoạt động của hệ thống. Đây là chìa khóa để đạt được hiệu suất vượt trội so với các giải pháp phần mềm thông thường.

3.1. Ứng dụng Pipelining in FPGA trong bộ xử lý DTP

Kỹ thuật Pipelining in FPGA được áp dụng triệt để trong kiến trúc DTP với 4 giai đoạn: Fetch, Access, Decode và Execute. Việc chia nhỏ quá trình xử lý giúp tăng tần số hoạt động cực đại và cải thiện Parallel processing. Mỗi chu kỳ xung nhịp, một nút mới của cây quyết định được xử lý, tạo ra luồng dữ liệu liên tục. Cấu trúc này cho phép hệ thống duy trì hiệu suất cao ngay cả khi độ sâu của cây tăng lên đáng kể.

3.2. Vai trò của Verilog VHDL trong thiết kế logic

Sử dụng ngôn ngữ phần cứng Verilog/VHDL (cụ thể là SystemVerilog) giúp kiểm soát chính xác các tài nguyên logic. Luận văn tận dụng các tính năng mạnh mẽ của SystemVerilog để xây dựng các module có tính kế thừa và linh hoạt. Quá trình tổng hợp và mô phỏng được thực hiện trên công cụ Xilinx Vivado, đảm bảo thiết kế đáp ứng các ràng buộc về thời gian (timing constraints). Việc tối ưu hóa mã nguồn ở mức đăng ký (RTL) giúp giảm thiểu diện tích chip và tiêu thụ năng lượng.

IV. Giải pháp Throughput optimization và Model quantization

Để tối đa hóa băng thông, luận văn tập trung vào các chiến lược tối ưu hóa luồng dữ liệu. Throughput optimization đạt được thông qua việc đồng bộ hóa hoạt động của các DTP và bộ tích lũy (Accumulator). Hệ thống có thể xử lý đồng thời nhiều mẫu dữ liệu nhờ cấu trúc hàng đợi linh hoạt. Ngoài ra, kỹ thuật Model quantization được áp dụng để chuyển đổi các tham số từ số thực 32-bit sang 16-bit. Việc giảm độ chính xác bit không làm ảnh hưởng đáng kể đến kết quả dự báo nhưng giúp giảm đáng kể tài nguyên tính toán. Luận văn cũng giới thiệu bộ đệm đầu ra (Out Buffer) được thiết kế đặc biệt để hỗ trợ cả bài toán phân loại và hồi quy. Cơ chế ghi dữ liệu được tối ưu để giảm thiểu xung đột trên bus AXI. Những cải tiến này giúp hệ thống đạt được tốc độ xử lý hàng triệu mẫu mỗi giây. Đây là một bước tiến quan trọng trong việc triển khai Machine Learning hardware implementation hiệu quả.

4.1. Kỹ thuật Fixed point arithmetic và độ chính xác

Sử dụng Fixed-point arithmetic là giải pháp thay thế hiệu quả cho các phép toán dấu phẩy động phức tạp. Việc này giúp giảm diện tích các bộ so sánh và tăng tốc độ xử lý trong STAGE EXECUTE của DTP. Luận văn thực hiện các thực nghiệm so sánh và chứng minh rằng số thực 16-bit đủ để duy trì độ chính xác của mô hình Random Forest. Điều này cực kỳ quan trọng đối với các thiết bị có tài nguyên hạn chế như System-on-Chip (SoC).

4.2. Tối ưu hóa Parallel processing trong Accumulator

Bộ tích lũy (Accumulator) được thiết kế để xử lý các phiếu bầu từ tất cả DTP một cách song song. Sử dụng module Count1bit giúp đếm nhanh số lượng phiếu bầu cho từng nhãn trong bài toán phân loại. Đối với bài toán hồi quy, hệ thống sử dụng các bộ cộng pipeline để tính giá trị trung bình. Khả năng Parallel processing ở giai đoạn cuối này đảm bảo không gây ra hiện tượng nghẽn cổ chai cho toàn bộ hệ thống tăng tốc.

V. Kết quả thực nghiệm và Power efficiency in ML hardware

Hệ thống được đánh giá chi tiết trên hai bo mạch PYNQ-Z2 và Kria KV260. Kết quả thực nghiệm cho thấy tốc độ tăng tốc ấn tượng lên đến 28.11 lần so với vi xử lý Intel Core i7. Điều này khẳng định sức mạnh của FPGA acceleration trong việc xử lý các thuật toán học máy. Đặc biệt, hệ thống duy trì được Power efficiency in ML hardware ở mức rất thấp, chỉ vài Watt. Đây là ưu thế vượt trội khi so sánh với các nền tảng GPU tiêu tốn hàng trăm Watt điện. Luận văn cũng thử nghiệm ứng dụng phân loại lớp phủ bề mặt đất (Land Cover Classification) bằng dữ liệu vệ tinh. Kết quả thu được hoàn toàn tương đồng với các thư viện phần mềm như Scikit-learn nhưng với thời gian thực thi nhanh hơn nhiều. Khả năng hoạt động ổn định trên các nền tảng System-on-Chip (SoC) mở ra cơ hội lớn cho các ứng dụng IoT và giám sát môi trường. Nghiên cứu đã đạt được kết quả xuất sắc và được công bố trên các tạp chí khoa học uy tín.

5.1. Đánh giá Real time classification trên Kria KV260

Nền tảng Kria KV260 với chip Zynq UltraScale+ cung cấp tài nguyên dồi dào cho các tác vụ AI. Thử nghiệm thực tế cho thấy hệ thống có thể xử lý các tập dữ liệu lớn với độ trễ cực thấp. Khả năng Real-time classification được chứng minh qua việc phân loại hình ảnh vệ tinh với độ phân giải cao. Hệ thống đáp ứng tốt các yêu cầu về băng thông và tốc độ xử lý trong các kịch bản ứng dụng thực tế.

5.2. Phân tích Power efficiency in ML hardware cho IoT

Chỉ số Power efficiency in ML hardware là yếu tố sống còn đối với các thiết bị IoT chạy bằng pin. Luận văn cung cấp số liệu so sánh chi tiết về mức tiêu thụ điện năng trên từng nền tảng. FPGA không chỉ nhanh hơn mà còn tiết kiệm năng lượng hơn đáng kể so với CPU truyền thống. Điều này cho phép triển khai các mô hình Random Forest phức tạp trực tiếp tại hiện trường mà không cần kết nối đám mây.

VI. Kết luận và tương lai của Real time classification trên SoC

Luận văn đã thành công trong việc xây dựng một kiến trúc tăng tốc Random Forest linh hoạt và hiệu quả. Việc kết hợp giữa tối ưu hóa thuật toán và thiết kế phần cứng chuyên biệt đã mang lại hiệu suất vượt trội. Kiến trúc đề xuất không chỉ giải quyết được vấn đề tốc độ mà còn tối ưu hóa tài nguyên BRAM và năng lượng. Trong tương lai, hướng nghiên cứu có thể mở rộng sang việc tự động hóa quá trình chuyển đổi mô hình từ phần mềm sang phần cứng. Việc ứng dụng High-Level Synthesis (HLS) có thể giúp rút ngắn thời gian phát triển và tiếp cận nhiều đối tượng người dùng hơn. Ngoài ra, việc tích hợp thêm các kỹ thuật nén mô hình tiên tiến sẽ giúp triển khai rừng trên các chip FPGA giá rẻ. Sự phát triển của các nền tảng System-on-Chip (SoC) sẽ tiếp tục là động lực cho các nghiên cứu về AI tại biên. Đây là nền tảng quan trọng cho các ứng dụng thông minh trong nông nghiệp, y tế và giao thông vận tải.

6.1. Tiềm năng của High Level Synthesis HLS trong tương lai

Mặc dù luận văn sử dụng SystemVerilog để đạt hiệu suất tối đa, High-Level Synthesis (HLS) đang trở nên phổ biến. HLS cho phép các nhà phát triển sử dụng ngôn ngữ C/C++ để thiết kế phần cứng, giúp giảm thời gian thiết kế. Việc kết hợp kiến trúc tối ưu trong luận văn với các công cụ HLS sẽ tạo ra một quy trình thiết kế tự động hóa mạnh mẽ. Điều này giúp tăng tốc việc triển khai các thuật toán học máy lên FPGA một cách dễ dàng hơn.

6.2. Xu hướng tối ưu hóa mô hình và Model quantization

Xu hướng tiếp theo sẽ tập trung vào việc cực tiểu hóa độ chính xác bit thông qua Model quantization. Việc sử dụng các kiểu dữ liệu dưới 8-bit hoặc thậm chí là mô hình nhị phân có thể tăng tốc độ lên gấp nhiều lần. Luận văn này đã đặt nền móng vững chắc cho việc nghiên cứu các kiến trúc phần cứng siêu tiết kiệm năng lượng. Đây là hướng đi tất yếu để hiện thực hóa tầm nhìn về trí tuệ nhân tạo ở mọi nơi (AI everywhere).

Trích đoạn nội dung tài liệu

VIETNAM NATIONAL UNIVERISTY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY (HCMUT) FACULTY OF COMPUTER SCIENCE & TECHNOLOGY G RADUATION THESIS A CCELERATION OF R ANDOM F OREST ON FPGA M AJOR : COMPUTER ENGINEERING COUNCIL: COMPUTER ENGINEERING 2 Superviosrs: Assoc. Pham Quoc Cuong - HCMUT PhD(c). Kieu Do Nguyen Binh - UEC Reviewer: Assoc. Tran Ngoc Thinh - HCMUT Authors: Pham Dinh Trung - 1952512 HO CHI MINH CITY - June-2023 ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc KHOA:KH & KT Máy tính ____ NHIỆM VỤ LUẬN ÁN TỐT NGHIỆP BỘ MÔN:KHMT ____________ Chú ý: Sinh viên phải dán tờ này vào trang nhất của bản thuyết trình HỌ VÀ TÊN: Phạm Đình Trung _____________________ MSSV: 1952512 ______ NGÀNH: Kỹ thuật Máy tính ___________________ LỚP: MT19CLC ____________ 1.

Đầu đề luận án: Acceleration of Random Forest on FPGA 2. Nhiệm vụ (yêu cầu về nội dung và số liệu ban đầu): - Conduct a thorough survey on the topic of FPGA-based random forest acceleration - Propose an FPGA-based architecture with pipeline for acceleration - Implement the proposed architecture with Verilog-HDL - Deploy the system with FPGA platforms - Evaluate the system with different dataset 3. Ngày giao nhiệm vụ luận án: 10/01/2023 4. Ngày hoàn thành nhiệm vụ: 01/6/2023 5.

Họ tên giảng viên hướng dẫn: Phần hướng dẫn: 1) PGS. Phạm Quốc Cường _______________________________________________ 2) __________________________________________________________________________ 3) __________________________________________________________________________ Nội dung và yêu cầu LVTN đã được thông qua Bộ môn. Ngày 10 tháng 01 năm 2022 CHỦ NHIỆM BỘ MÔN GIẢNG VIÊN HƯỚNG DẪN CHÍNH (Ký và ghi rõ họ tên) (Ký và ghi rõ họ tên) Phạm Quốc Cường Phạm Quốc Cường PHẦN DÀNH CHO KHOA, BỘ MÔN: Người duyệt (chấm sơ bộ):________________________ Đơn vị: _______________________________________ Ngày bảo vệ: __________________________________ Điểm tổng kết: _________________________________ Nơi lưu trữ luận án: _____________________________ TRUONG DAI HOC BACI-1 KHOA C<)NG HOA XA H<)I CHU NGHiA VI).tT NAM KHOA KH & KT MAY TINH D(}c I~p - T1,1· do - H~nh phuc Ngity 12 thitng 6 nam 2023 PHIEU DANH GIA LU~N VAN/ DO AN ;T OT NGHI~P (Ditnh cha ngiu}i hu6ng Mn/phan bi?n) 7. I-19 va ten SV: Phc;im Dinh Trung 1952512 Computer Engineering 2.

8~ tai: Acceleration of Random Forest on FPGA 3. I-19 ten nguc'ri hu&ng d~n/phan biE;n: Phc;im Qu6c CU'6'ng 4. T6ng quat v~ ban thuy~t minh: s6 trang: s6 chuang: s6 bang s6 li~u s6 hinh ve: s6 tai li~u tham khao: Ph~n m~m tinh toan: 1-Ii~n v~t (san ph~m) 5. Nhfrng uu di~m chinh cua LV/ BATN: - The student fulfills all the requirements of the capstone project when the proposed and implemented system that can accelerate random forest in FPGA devices.

- The student achieved an outstanding result with a 01 publication. - Experimental results are conducted excellently. - The report is written with a perfect approach. Nhfrng thi~u s6t chinh cua LV/BATN: - It is much better if the student can find a suitable dataset to compare the proposed work 1 with published work in the literture.

D~ nghi: Bugc bao v~ IBJ B6 sung them d~ bao v~ o Khong dugc bao v~ o 8. Cac cau hoi SV phai tra lc'ri trn&c 1-19i d6ng: 9. Danh gia chung (b~ng chfr: Xu~t s~c, Gioi, Kha, TB): Di~m: 10110 Ky ten (ghi ro h9 ten) Ph~m Quoc Cuong TRƯỜNG ĐẠI HỌC BÁCH KHOA CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM KHOA KH & KT MÁY TÍNH Độc lập - Tự do - Hạnh phúc ---------------------------- Ngày tháng năm PHIẾU ĐÁNH GIÁ LUẬN VĂN/ ĐỒ ÁN TỐT NGHIỆP (Dành cho người hướng dẫn/phản biện) 1. Họ và tên SV: Phạm Đình Trung MSSV: 1952512 Ngành (chuyên ngành):Kỹ thuật Máy tính 2.

Đề tài: Acceleration of Random Forest on FPGA (Tăng tốc giải thuật Random Forest trên FPGA) 3. Họ tên người hướng dẫn/phản biện: PGS. Trần Ngọc Thịnh 4. Tổng quát về bản thuyết minh: Số trang: 83 Số chương: 6 Số bảng số liệu: 15 Số hình vẽ: 39 Số tài liệu tham khảo: 42 Phần mềm tính toán: Hiện vật (sản phẩm) 5.

Những ưu điểm chính của LV/ ĐATN: This thesis proposed an architecture on FPGA to accelerate random forest prediction including multiple Decision Tree Processors (DTP which can process multiple trees at the same time. The pipelining technique is applied to increase its performance. The number of DTPs can be easily reconfigured to be suitable for the hardware resource of a specific hardware platform. The Accumulator and Out Buffer is also designed to compute in pipeline to maximize the operating frequency and parallel nature of the system.

The whole system is a combination of components designed with SystemVerilog and Xilinx IP. The system is implemented and evaluated on PYNQ-Z2 and Kria KV2601 boards which can achieve throughput speed-ups by up to 28.11× when compared to an Intel core i7 processor, respectively. Furthermore, the system also has a very low power consumption that is suitable for IoT applications. Những thiếu sót chính của LV/ĐATN: The system has not yet been compared to other FPGA-based works.

Đề nghị: Được bảo vệ  Bổ sung thêm để bảo vệ  Không được bảo vệ  8. Các câu hỏi SV phải trả lời trước Hội đồng: a. The author explains the main contribution and discusses the results compared to other FPGA- based works. Đánh giá chung (bằng chữ: Xuất sắc, Giỏi, Khá, TB): Excellent (Xuất sắc) Điểm : 10/10 Ký tên (ghi rõ họ tên) Trần Ngọc Thịnh This thesis is dedicated for our parents and our instructors at HCMUT.

S TATEMENT OF O RIGINALITY I assure that contents in this report are product of study and implementation process. I do not copy any document or publication. All references are used with citations. All experiment results are derived from real experiments done by myself and not published in any other work.

Some results and ideas come from previously published in scientific paper: • Trung Pham-Dinh, Cuong Pham-Quoc, Tran Ngoc Thinh, Binh Kieu Do Nguyen, Pham Cong Kha. A flexible and efficient FPGA-based random forest architecture for IoT applications. In: Internet of Things 2023, pp. Elsevier(2023) • Trung Pham-Dinh, Bao Bach-Gia, Lam Luu-Trinh, Minh Nguyen-Dinh, Hai Pham-Duc, Khoa Bui-Anh, Xuan-Quang Nguyen & Cuong Pham- Quoc.

An FPGA-Based Solution for Convolution Operation Accelera- tion. In: ICIot2022, pp. Springer (2022) Pham Dinh Trung vi A CKNOWLEDGMENT First, I would like to sincerely thank Associate Professor Pham Quoc Cuong for his enthusiastic support during my university studies and thesis. Thank you, Mr Kieu Do Nguyen Binh, for closely following the thesis research process, sup- porting me in solving complex problems, and developing direction for the the- sis.

I want to thank Mr Nguyen Xuan Quang, Mr Tran Hoang Quoc Bao and Mr Huynh Phuc Nghi in CE lab for spending time to exchange knowledge with me in my study field. Besides, I would like to express my gratitude and respect to all lecturers in the Faculty of Computer Science and Engineering and the Ho Chi Minh City University of Technology. They have helped me have a solid knowledge base for my report research. In addition, I would like to thank my colleagues and seniors at Marvell com- pany for helping me during my internship and teaching me professional knowl- edge, study, and work skills.

I thank my family for giving me solid spiritual support so that I can devote all my energy to the report. Thank you, Bach Gia Bao, Luu Trinh Lam, Nguyen Dinh Minh and Tran Canh Trieu for supporting me in my study and writing papers. Besides, my thesis will not be going well without support from K20 students: Bui Anh Khoa, Huynh Trung Nhat, Le Tu Quan, Le Ngoc Minh Thu, Nguyen Phan Anh Tuan. And lastly, thank God for giving me the strength and energy to finish my report and continue on my chosen path.

Ho Chi Minh City, May 01st , 2023 Pham Dinh Trung vii A BSTRACT Nowadays, AI technology is applied to various fields such as agriculture, medicine, transportation, politics and education. AI is now a trend thanks to the rapid development of hardware platforms. Powerful hardware makes com- plex computation in the AI algorithm executable. Many hardware platforms include multi-core CPU and Graphic Processing Unit (GPU).

However, FPGA is an efficient choice for AI applications because it balances processing speed and flexibility. One of the most popular machine learning algorithms is the ran- dom forest which is applied in various applications. Despite its high prediction strength, the inference time of this model is significantly high because it usu- ally contains thousands of decision trees, and each tree has thousands of pa- rameters. Random forest is costly in computation and resources.

Therefore, the model is challenging to fit in an edge device and run in real-time. This the- sis proposes an architecture for accelerating the Random Forest model on an FPGA-based SoC platform. The architecture is flexible and efficient to be im- plemented on various edge computing platforms. To increase the performance, I design a pipeline architecture for decision tree processors, accumulators and a vote buffer.

This allows the whole system to operate at high frequency and in- creases parallel computing ability. I apply several methods to reduce memory usage for storing the forest to solve hardware limitations. Therefore, the design is easy to be implemented on edge devices. The system will be implemented on multiple FPGA devices and evaluated by comparing it with Intel CPU.

viii C ONTENTS Statement of Originality vi Statement of Originality vi Acknowledgment vii Acknowledgment vii Abstract viii List of Figures xi List of Tables xiii 1 Introduction 1 1. 4 2 Background and Related work 5 2.1 Field Programmable Gate Array and System on Chip .2 Kria KV260 platform .6 Geographical Random Forest .1 Random Forest applications .2 Random Forest on FPGA .2 Memory structure of a Decision Tree Processor. 21 ix C ONTENTS x 4 Implementation 24 4.2 PS-PL communication .3 Acceleration Core - TOP .2 Decision Tree Processor Implementation .4 Out Buffer Implementation .5 Parameters of the acceleration core.3 Land cover classification application .4 Performance and energy efficiency analysis .1 DMA transfer time .4 Land Cover Classification Application. 67 6 Conclusion 71 Bibliography 73 7 Publications 77 7.1 A flexible and efficient FPGA-based random forest architecture for IoT applications.

77 L IST OF F IGURES 2.1 Basic FPGA Architecture .2 Basic MPSoC Zynq Architecture .3 Kria KV260 Vision AI Starter Kit [1] .4 A simple example of decision tree .5 A simple example of random forest .7 Pipeline tree level architecture .1 General architecture of Random Forest accelerator .2 Structure of a Tree RAM .3 Trees in a Tree RAM is divided into different subsets .1 System implementation on Xilinx SoC .2 ZYNQ Processing System IP on ZYNQ 7000 SoC .3 Central Direct Access Memory IP on ZYNQ 7000 SoC .4 General design of Decision Tree Processor .5 Decision Tree Processor Implementation .6 Block diagram for generating next control signal .7 Block diagram for generating update signal .8 General design of Accumulator .9 Design of classification accumulation .10 Count1bit module .11 Design of regression accumulation .12 Design of Out Buffer .13 Clear-on-read feature when PS reading Out buffer .14 Load initialization file in Block Memory Generator .1 PYNQ-Z2 board diagram .2 Kria KV260 board diagram .3 Block design for DMA transferring time experiment .4 Hardware resources usage comparison for regression .5 Hardware resources usage comparison for classification .6 DTP simulation on Vivado. 57 xi L IST OF F IGURES xii 5.7 Speed-ups comparison w.t performance of 1-DTP configuration on regression problem .8 Speed-ups comparison w.t performance of Intel core i7 on re- gression problem .9 Power (W) comparison on regression problem .10 Speed-ups comparison w.t performance of 1-DTP configuration on classification problem .11 Speed-ups comparison w.