Tổng quan luận án

Luận án tiến sĩ chuyên ngành Kỹ thuật phần mềm (mã số 62 48 01 03) của nghiên cứu sinh Phạm Văn Hưởng, do PGS. Nguyễn Ngọc Bình hướng dẫn khoa học tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội năm 2015, mang tiêu đề "Một số phương pháp tối ưu trong giai đoạn phát triển phần mềm nhúng".

Tính cấp thiết và khoảng trống nghiên cứu

Hệ thống nhúng và phần mềm nhúng chiếm tỷ trọng lớn trong nền công nghiệp vi điện tử và công nghệ thông tin. Theo thống kê được tác giả trích dẫn, năm 1999 có đến 99% số vi xử lý sản xuất ra thuộc về hệ thống nhúng, và đến năm 2011 con số chip dành cho ứng dụng nhúng duy trì ở mức trên 95%. Đặc thù của phần mềm nhúng là vận hành trong môi trường giới hạn nghiêm ngặt về tài nguyên phần cứng như tốc độ vi xử lý (CPU), dung lượng bộ nhớ (RAM, ROM), công suất tiêu thụ và thời lượng nguồn pin, cùng các ràng buộc nghiêm ngặt về mặt thời gian thực. Tại Việt Nam, đa số doanh nghiệp phần mềm tập trung vào phần mềm ứng dụng hoặc gia công, số lượng đơn vị phát triển hệ thống và phần mềm nhúng còn hạn chế và phụ thuộc vào yêu cầu của đối tác nước ngoài.

Về mặt khoa học, tối ưu hóa phần mềm nhúng là bài toán phức tạp, có phạm vi rộng và can thiệp vào nhiều giai đoạn khác nhau trong vòng đời phát triển. Khoảng trống nghiên cứu được tác giả xác định cụ thể như sau:

  • Trong giai đoạn thiết kế: Các nghiên cứu trước đây chủ yếu dựa vào mô phỏng hoặc chuyển đổi mô hình thiết kế sang các mô hình hiệu năng trung gian (như mạng hàng đợi, mạng Petri theo kỹ nghệ hiệu năng phần mềm - SPE) vốn tốn nhiều thời gian và công sức. Chưa có hệ thống độ đo và hàm đánh giá trực tiếp hiệu năng, bộ nhớ từ các thực thể của biểu đồ lớp UML, cũng như chưa có giải pháp tối ưu đa mục tiêu cân bằng trực tiếp ở mức biểu đồ lớp.
  • Trong giai đoạn lập trình: Các trình biên dịch mã nguồn mở (như GCC) đã tích hợp kỹ thuật loại bỏ biểu thức con chung (Common Subexpression Elimination - CSE) trên đồ thị định hướng không chu trình (DAG) nhưng chưa xét đến các biểu thức có quan hệ tương đương đại số/logic; đồng thời việc lập lịch lệnh hợp ngữ nhằm tối ưu hóa đồng thời hiệu năng và năng lượng tiêu thụ trên các cấu hình kiến trúc CPU nhúng khác nhau (đường ống lệnh, siêu vô hướng) còn thiếu vắng các giải pháp tích hợp tự động.
  • Trong giai đoạn thực thi: Các giải pháp tối ưu còn gặp nhiều khó khăn trong việc đánh giá trạng thái động của mã chuyên biệt hóa và chưa kết hợp hiệu quả giữa kỹ nghệ ngược với kỹ thuật tái cấu hình phần cứng CPU để tiết kiệm điện năng tiêu thụ.

Mục tiêu và nội dung nghiên cứu

Mục tiêu tổng quát của luận án là nghiên cứu, đề xuất, cải tiến và triển khai một số phương pháp tối ưu hóa phần mềm nhúng qua ba giai đoạn chính của quy trình phát triển phần mềm (thiết kế, lập trình, thực thi) theo hướng tiếp cận kỹ nghệ xuôi kết hợp kỹ nghệ ngược, làm nền tảng giải quyết bài toán tối ưu tổng thể.

Các mục tiêu và nội dung nghiên cứu cụ thể được đánh số trong luận án gồm:

  1. Xây dựng mô hình tổng thể cho bài toán tối ưu hóa trong phát triển phần mềm nhúng, bao gồm hai hướng tiếp cận: tối ưu trong kỹ nghệ xuôi và tối ưu kết hợp kỹ nghệ ngược.
  2. Đề xuất và phát triển các phương pháp tối ưu phần mềm nhúng trong giai đoạn thiết kế: tối ưu hiệu năng dựa trên đánh giá trực tiếp biểu đồ lớp; tối ưu bộ nhớ chiếm dụng dựa trên sắp xếp tô-pô đồ thị tác vụ phụ thuộc (DTG); cải tiến phương pháp tối ưu hiệu năng và bộ nhớ trên chuyển đổi mô hình; đề xuất phương pháp tối ưu đa mục tiêu (Pareto) trên biểu đồ lớp; tự động hóa một phần thông qua khung làm việc ngôn ngữ chuyên biệt miền (DSL) và bộ công cụ mẫu văn bản T4.
  3. Cải tiến và phát triển các phương pháp tối ưu phần mềm nhúng trong giai đoạn lập trình: tối ưu mã nguồn mức cao độc lập CPU thông qua cải tiến thuật toán loại bỏ biểu thức con chung trên đồ thị DAG bằng cách thay thế biểu thức tương đương; tối ưu truyền dữ liệu bằng kỹ thuật nén; tối ưu mã hợp ngữ hướng CPU bằng thuật toán di truyền (GA) lập lịch lệnh tối ưu hiệu năng và điện năng tiêu thụ cho các kiến trúc đường ống lệnh và siêu vô hướng.
  4. Nghiên cứu và phát triển phương pháp tối ưu trong giai đoạn thực thi: đề xuất phương pháp tối ưu điện năng tiêu thụ kết hợp kỹ nghệ ngược và tái cấu hình CPU dựa trên mô phỏng Sim-Wattch.
  5. Triển khai thực nghiệm kiểm chứng các phương pháp đề xuất trên phần mềm nhận dạng chữ Nôm (cho thiết bị di động và dịch vụ web), các chương trình điều khiển nhúng trên bo mạch Netduino Plus và các chương trình chuẩn cho vi xử lý MIPS.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các phương pháp, kỹ thuật, thuật toán và mô hình tối ưu hóa phần mềm nhúng qua các giai đoạn thiết kế, lập trình và thực thi.
  • Phạm vi nghiên cứu:
    • Về mặt kiến trúc phần cứng: Các phương pháp tối ưu trong giai đoạn thiết kế và tối ưu mã nguồn mức cao được giới hạn trên các hệ thống xây dựng theo kiến trúc Von Neumann.
    • Về mức lệnh hợp ngữ: Nghiên cứu tập trung vào 5 cấu hình kiến trúc CPU (đơn chu trình, đường ống lệnh, siêu vô hướng in-order, siêu vô hướng out-of-order) trong phạm vi các lệnh thực thi đơn chu trình.
    • Về nền tảng thực nghiệm: Sử dụng bo mạch vi điều khiển Netduino và Netduino Plus (chip AT91SAM7X512, lõi ARM7, kiến trúc RISC, máy ảo .NET Micro Framework 4.2), nền tảng mô phỏng vi xử lý MIPS (SimpleScalar, Sim-Wattch), và hệ điều hành PocketPC/Windows cho ứng dụng nhận dạng chữ Nôm.

Tổng quan tài liệu và vị trí của luận án

Tác giả đã hệ thống hóa các công trình nghiên cứu liên quan đến tối ưu hóa phần mềm nhúng theo từng giai đoạn và hướng tiếp cận:

Các hướng nghiên cứu trước đây

  1. Giai đoạn thiết kế:
    • Hướng tiếp cận kỹ nghệ hiệu năng phần mềm (SPE): Cortellessa V., Balsamo S., Smith C.U., Petriu D.B., Anne K. và cộng sự [7, 10, 12, 79, 96, 115, 116] tập trung chuyển đổi mô hình kiến trúc UML (biểu đồ ca sử dụng, biểu đồ tuần tự, biểu đồ hoạt động) sang các mô hình hiệu năng như mạng hàng đợi (Queueing Network), mạng Petri để phân tích thời gian đáp ứng và độ trễ.
    • Hướng tiếp cận mô phỏng dựa trên DSL: Thompson C., White J., Dougherty B. [102] sử dụng DSL trên nền Eclipse để sinh mã mô phỏng đánh giá hiệu năng và cân bằng thời lượng pin trên điện thoại di động; Anastasopoulos M. và Muthig D. [5] áp dụng kỹ nghệ hướng mô hình cho dòng sản phẩm; các nghiên cứu [41, 77, 95, 108, 110, 114] xây dựng mô hình thành phần trên nền tảng Android, J2ME và các giao thức truyền thông SOAP, HTTP để chọn môi trường thực thi tối ưu.
    • Hướng tiếp cận đánh giá độ đo thiết kế: Genero M., Piattini M. và các tác giả [78, 79, 112, 116] đề xuất các bộ độ đo chất lượng phần mềm hướng đối tượng (độ phức tạp, tính đóng gói, tính tái sử dụng, khả năng bảo trì). Một số nghiên cứu sơ khởi [4] xem xét số lượng lớp, thuộc tính, phương thức ảnh hưởng đến hiệu năng nhưng chưa đưa ra công thức định lượng cụ thể.
  2. Giai đoạn lập trình:
    • Tối ưu mã nguồn mức cao: Các kỹ thuật biến đổi vòng lặp, giảm truy xuất bộ nhớ [22, 69, 82, 111]; tối ưu kích thước mã nguồn bằng loại bỏ mã chết, cấp phát động [7, 26, 29, 44, 48, 75, 83]; tối ưu đa mục tiêu trên mã nguồn dựa trên Pareto của các tác giả [27].
    • Tối ưu mã hợp ngữ hướng CPU: Nghiên cứu tập trung vào tập thanh ghi và tập lệnh cho các dòng CPU RISC, CISC [19, 28, 30, 59, 87, 88].
  3. Giai đoạn thực thi:
    • Tối ưu môi trường thực thi: Lập lịch tiến trình theo mô hình Markov [18], kỹ thuật biên dịch tức thời (Just-In-Time - JIT) [104], quản lý bộ nhớ động [68, 90], chuyên biệt hóa mã nguồn và thuật toán [91, 113, 117], kỹ thuật mã tự sửa [91].
    • Tối ưu hướng dữ liệu: Phân nhóm và sắp đặt dữ liệu [57], nén dữ liệu truyền thông và loại bỏ thông điệp dư thừa [74].

Vị trí và khoảng trống luận án giải quyết

Luận án định vị trọng tâm vào việc khắc phục các hạn chế còn tồn tại của các công trình đi trước, cụ thể:

  • Thay vì phải chuyển đổi sang mạng Petri hay sinh mã mô phỏng phức tạp, luận án thiết lập phương pháp đánh giá trực tiếp hiệu năng và bộ nhớ từ các thông số hình thức của biểu đồ lớp (số biến tĩnh/đối tượng, số phương thức, tham số, kiểu trả về) kết hợp tự động hóa qua khung làm việc DSL và mẫu T4.
  • Bổ sung quy tắc nhận diện và xử lý biểu thức tương đương vào giải thuật khử biểu thức con chung (CSE) trên đồ thị DAG trong trình biên dịch GCC.
  • Tích hợp giải thuật di truyền (GA) vào bài toán lập lịch lệnh hợp ngữ để tối ưu đồng thời hiệu năng thực thi và giảm chuyển mạch điện dung (tiết kiệm năng lượng) trên các cấu hình CPU đường ống và siêu vô hướng.
  • Đề xuất mô hình kết hợp kỹ nghệ ngược trích xuất đặc tả từ mã thực thi với việc tái cấu hình số lượng đơn vị chức năng của CPU để giảm thiểu công suất hao phí.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

  • Mô hình tối ưu hóa tổng thể: Phân định rõ hai quy trình gồm kỹ nghệ xuôi (Thiết kế $\rightarrow$ Lập trình $\rightarrow$ Thực thi) và kỹ nghệ ngược (Mã thực thi $\rightarrow$ Hợp ngữ $\rightarrow$ Mã nguồn $\rightarrow$ Mô hình thiết kế).
  • Lý thuyết tối ưu hóa:
    • Tối ưu đơn mục tiêu (Single Objective Optimization - SOO): Cực tiểu hóa một hàm mục tiêu (hiệu năng $f_p$, bộ nhớ $f_m$, điện năng $f_e$, hoặc chi phí $f_c$) dưới các điều kiện biên của các tiêu chí còn lại.
    • Tối ưu đa mục tiêu Pareto (Pareto Multi-objective Optimization - PMO): Cân bằng các mục tiêu mâu thuẫn bằng cách xây dựng hàm mục tiêu toàn thể $f = \sum w_i f_i$ với các trọng số $w_i$.
  • Lý thuyết mô hình hóa và biểu diễn cấu trúc:
    • Ngôn ngữ mô hình hóa thống nhất (UML), ngôn ngữ chuyên biệt miền (DSL) và bộ công cụ mẫu biến đổi văn bản (T4).
    • Đồ thị định hướng không chu trình (DAG) trong phân tích khối cơ bản của trình biên dịch; Đồ thị luồng điều khiển (Control Flow Graph - CFG); Đồ thị tác vụ phụ thuộc (Dependent Task Graph - DTG).
  • Lý thuyết kiến trúc máy tính và năng lượng: Mô hình tiêu thụ năng lượng của CPU: $P_{\text{CPU}} = P_d + P_s + P_l$ (công suất động $P_d = \alpha \cdot C_c \cdot f_x \cdot V_c^2$, công suất ngắn mạch $P_s$, công suất rò rỉ $P_l$).

Phương pháp nghiên cứu

Luận án kết hợp phương pháp nghiên cứu định tính và định lượng:

  • Phương pháp định tính: Tiếp cận từ trên xuống (top-down), phân tích, hệ thống hóa và tổng hợp lý thuyết về các kỹ thuật biên dịch chéo, các kiến trúc vi xử lý nhúng, phân loại các mô hình thiết kế và quy trình đồng thiết kế phần cứng – phần mềm.
  • Phương pháp định lượng và thực nghiệm:
    • Xây dựng các công thức toán học định lượng cho các độ đo $S_1$ đến $S_6$, hàm đánh giá hiệu năng $f_p$, hàm chiếm dụng bộ nhớ $f_m$, hàm mục tiêu Pareto.
    • Thu thập dữ liệu thực nghiệm qua đo đạc thời gian thực thi (tính bằng microsecond $\mu s$), số chu kỳ lệnh thực thi của CPU, dung lượng bộ nhớ cấp phát (byte), và mức tiêu thụ điện năng/năng lượng thông qua công cụ mô phỏng chuyên dụng.

Nguồn tư liệu và công cụ thực nghiệm

  • Môi trường phát triển: Microsoft Visual Studio 2010 Express, Microsoft Visual Studio DSL Tools, T4 Template Toolkit, bộ công cụ biên dịch chéo GCC (cho ARM, MIPS, PowerPC).
  • Nền tảng phần cứng: Bo mạch vi điều khiển Netduino và Netduino Plus tích hợp vi xử lý 32-bit ARM7 (AT91SAM7X512), tập lệnh RISC; máy ảo .NET Micro Framework 4.2.
  • Nền tảng mô phỏng: SimpleScalar (mô phỏng kiến trúc tập lệnh MIPS) và Sim-Wattch (mô phỏng phân tích tiêu thụ năng lượng chi tiết của CPU).
  • Tập chương trình kiểm chứng: Bộ chương trình điều khiển ngoại vi nhúng (Netduino_8digit điều khiển 8 LED 7 đoạn, Netduino_LCD điều khiển màn hình HD44780U, Netduino_SerialPort giao tiếp cổng nối tiếp); các bài toán thuật toán (Tháp Hà Nội, 8 quân Hậu); hệ thống phần mềm nhận dạng chữ Nôm trên thiết bị di động PocketPC và Web service.

Nội dung chính theo từng chương

Chương 1. Tổng quan

Chương 1 trình bày tổng quan về phát triển hệ thống nhúng và phần mềm nhúng, chỉ ra sự khác biệt giữa phương pháp truyền thống (phát triển phần cứng cố định trước, sau đó phát triển phần mềm) và phương pháp đồng thiết kế phần cứng – phần mềm (phân chia linh hoạt chức năng phần cứng/phần mềm dựa trên đánh giá hiệu năng, năng lượng, chi phí).

Tác giả đề xuất mô hình tối ưu tổng thể trong phát triển phần mềm nhúng gồm hai hướng tiếp cận chính:

  1. Tối ưu trong kỹ nghệ xuôi: Thực hiện qua 3 giai đoạn:
    • Giai đoạn thiết kế: Lựa chọn mô hình thiết kế tối ưu theo các tiêu chí đơn mục tiêu hoặc đa mục tiêu.
    • Giai đoạn lập trình: Tối ưu mã nguồn mức cao độc lập kiến trúc CPU và tối ưu mã hợp ngữ hướng cấu hình CPU đích.
    • Giai đoạn thực thi: Tối ưu môi trường thực thi (hệ điều hành, máy ảo, biên dịch JIT), tối ưu môi trường truyền dữ liệu và tối ưu mã thực thi.
  2. Tối ưu trong kỹ nghệ ngược: Kết hợp kỹ thuật dịch ngược từ mã thực thi sang hợp ngữ, mã nguồn và mô hình thiết kế để thực hiện các cải tiến tối ưu hóa và cấu hình lại hệ thống.

Chương này cũng thiết lập các công thức toán học tổng quát cho bài toán tối ưu đơn mục tiêu (1.1 đến 1.4) và nguyên lý đa mục tiêu Pareto trong hệ thống nhúng.

Chương 2. Tối ưu phần mềm nhúng trong giai đoạn thiết kế

Chương 2 tập trung giải quyết các bài toán tối ưu ở mức mô hình thiết kế hướng đối tượng:

1. Tối ưu hiệu năng dựa trên biểu đồ lớp

Tác giả đề xuất phương pháp đánh giá trực tiếp hiệu năng biểu đồ lớp dựa trên số lần thao tác bộ nhớ (cấp phát và truy xuất). Hệ thống gồm 6 độ đo thành phần:

  • $S_1$: Kích thước các biến tĩnh trong biểu đồ lớp: $S_1 = \sum_{i \in C} \sum_{j \in Vs_i} \text{size}(as_j)$
  • $S_2$: Kích thước các phương thức tĩnh: $S_2 = \sum_{i \in C} \sum_{j \in Ms_i} \text{size}(Ms_{ij})$
  • $S_3$: Kích thước thực thi các phương thức tĩnh: $S_3 = \sum_{i \in C} \sum_{j \in Ms_i} \left( \sum_{k \in Pm_j} \text{size}(p_k) + \text{size}(re_j) \right)$
  • $S_4$: Kích thước các biến đối tượng: $S_4 = \sum_{i \in C} \sum_{j \in Vo_i} \text{size}(ao_j)$
  • $S_5$: Kích thước các phương thức đối tượng: $S_5 = \sum_{i \in C} \sum_{j \in Mo_i} \text{size}(Mo_{ij})$
  • $S_6$: Kích thước thực thi các phương thức đối tượng: $S_6 = \sum_{i \in C} \sum_{j \in Mo_i} \left( \text{size}(vr_j) + \sum_{k \in Pm_j} \text{size}(p_k) + \text{size}(re_j) \right)$

Hàm đánh giá hiệu năng được xác định theo công thức: $$f_p = \alpha_1 S_1 + \alpha_2 S_2 + \alpha_3 S_3 + \alpha_4 S_4 + \alpha_5 S_5 + \alpha_6 S_6$$ Dựa trên phân tích số thao tác bộ nhớ trong quá trình nạp và thực thi chương trình hướng đối tượng, tác giả xác định bộ trọng số: $\alpha_1 = 2$, $\alpha_2 = 2$, $\alpha_3 = 4$, $\alpha_4 = 3$, $\alpha_5 = 3$, $\alpha_6 = 7$. Giá trị $f_p$ càng nhỏ thể hiện mô hình có hiệu năng càng cao.

Dữ liệu thực nghiệm kiểm chứng hàm đánh giá hiệu năng trên bo Netduino Plus:

Chương trình Biểu đồ Số lớp PT tĩnh TT tĩnh PT động TT động $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ $f_p$ (Điểm) Thời gian thực thi trung bình ($\mu s$)
Netduino_8digit BĐ 1 4 3 0 17 9 12 0 12 68 24 137 1307 5.054.135
BĐ 2 2 10 5 7 4 40 8 84 28 16 45 879 4.777.056
Netduino_LCD BĐ 1 3 1 0 16 17 4 0 4 64 47 108 1113 8.345.647
BĐ 2 3 8 0 9 17 32 0 47 36 47 65 956 8.054.425
Netduino_SerialPort BĐ 1 2 1 0 7 6 4 0 4 28 24 60 600 937.369
BĐ 2 3 8 0 1 6 32 0 64 4 24 8 460 781.022

Kết quả thực nghiệm chứng minh sự tương thích tuyệt đối giữa giá trị hàm dự báo $f_p$ và thời gian thực thi thực tế: Biểu đồ 2 ở cả 3 chương trình đều có giá trị $f_p$ nhỏ hơn và thời gian thực thi đo được trên phần cứng thực tế đều thấp hơn Biểu đồ 1 (mức giảm thời gian thực thi lần lượt là 5,48%, 3,49% và 16,68%).

2. Tối ưu bộ nhớ chiếm dụng trong giai đoạn thiết kế

  • Phương pháp sắp xếp tô-pô trên đồ thị tác vụ phụ thuộc (DTG): Mô hình hóa hệ thống thành đồ thị $G = (U, V)$. Tổng bộ nhớ chiếm dụng tại một thời điểm $M = S_c + S_e + D_s$ (với $S_c$ là kích thước mã lệnh, $S_e$ là vùng nhớ heap cấp phát động, $D_s$ là kích thước dữ liệu tĩnh). Thuật toán sinh tất cả các chuỗi sắp xếp tô-pô hợp lệ để tìm chuỗi thực thi có dung lượng bộ nhớ đỉnh (peak memory) nhỏ nhất. Phương pháp được áp dụng thành công trên các mô-đun của chương trình nhận dạng chữ Nôm.
  • Cải tiến tối ưu trên chuyển đổi mô hình: Tái cấu trúc các phần tử dữ liệu trừu tượng dựa trên tần số sử dụng $n_i$, chuyển đổi mô hình ban đầu sang mô hình tối ưu thông qua khung làm việc DSL và T4.

3. Tối ưu đa mục tiêu dựa trên biểu đồ lớp

Kết hợp các hàm đánh giá thành phần gồm hiệu năng ($f_1 = f_p$), bộ nhớ ($f_2 = f_m$), điện năng ($f_e$) và chi phí ($f_c$) thành hàm đa mục tiêu toàn thể với trọng số tương ứng $w_i$. Tác giả sử dụng nguyên lý Pareto để trích xuất tập các giải pháp thiết kế tối ưu không bị vượt trội (Pareto frontier).

Chương 3. Tối ưu phần mềm nhúng trong giai đoạn lập trình

Chương 3 trình bày các phương pháp tối ưu hóa ở mức mã nguồn và mức hợp ngữ:

1. Tối ưu mã nguồn mức cao độc lập máy đích

  • Cải tiến thuật toán loại bỏ biểu thức con chung (CSE) trong GCC: Trong các trình biên dịch chuẩn, thuật toán CSE biểu diễn khối cơ bản dưới dạng DAG để loại bỏ các phép tính trùng lặp giống hệt nhau về mặt ký tự cú pháp. Tác giả mở rộng thuật toán bằng cách bổ sung khả năng nhận diện các biểu thức tương đương về mặt toán học và logic (ví dụ: các biểu thức giao hoán, phân phối, hoặc biến đổi đại số tương đương) chưa được DAG chuẩn nhận biết, giúp giảm số lượng phép tính số học/logic và giảm số lệnh gán trung gian.
  • Cải tiến hiệu năng dựa trên nén dữ liệu truyền thông: Phân tích sự đánh đổi thời gian trong hệ thống phân tán: $T = T_1 + T_2 + T_3$. Việc nén dữ liệu làm tăng thời gian nén tại client ($T_u$) và giải nén tại server ($T_d$), nhưng giảm đáng kể thời gian truyền trên đường truyền mạng ($T_c$). Luận án xác định ngưỡng kích thước dữ liệu và tỷ lệ nén $r$ sao cho tổng thời gian thực thi $T$ đạt cực tiểu.

2. Tối ưu mã hợp ngữ hướng đến CPU hệ thống nhúng

  • Áp dụng các kỹ thuật cơ bản: đổi tên thanh ghi để triệt tiêu phụ thuộc dữ liệu giả (ghi-sau-đọc WAR, ghi-sau-ghi WAW), thay thế lệnh phức tạp bằng chuỗi lệnh đơn giản tiêu thụ ít chu kỳ máy.
  • Lập lịch lệnh bằng thuật toán di truyền (GA):
    • Biểu diễn mỗi chuỗi lệnh hợp ngữ thành một nhiễm sắc thể. Hàm thích nghi đánh giá tổng số chu kỳ thực thi của khối lệnh dựa trên bảng thời gian trễ của từng lệnh và các xung đột đường ống (pipeline hazard).
    • Thực nghiệm lập lịch trên 3 kiến trúc CPU: đường ống lệnh chuẩn, kiến trúc siêu vô hướng in-order và kiến trúc siêu vô hướng out-of-order. Kết quả cho thấy thuật toán GA cho hiệu năng vượt trội so với thuật toán danh sách (List scheduling) truyền thống.
    • Tối ưu điện năng tiêu thụ: Đánh giá thông qua tổng chuyển mạch điện dung $C_c$. Việc sắp xếp lại thứ tự lệnh giúp giảm số lượng cổng logic bị đảo trạng thái giữa các chu kỳ liên tiếp, giảm công suất chuyển mạch động $P_d$.

Chương 4. Tối ưu phần mềm nhúng trong giai đoạn thực thi

Chương 4 nghiên cứu các kỹ thuật tối ưu can thiệp tại môi trường thực thi:

1. Tối ưu môi trường thực thi và tái cấu hình CPU

  • Phân tích kỹ thuật chuyên biệt hóa tĩnh và động trên các hệ thống thông dịch và máy ảo (.NET Micro Framework, Java Virtual Machine).
  • Phương pháp tối ưu điện năng dựa trên kỹ nghệ ngược và tái cấu hình CPU:
    • Quy trình: Trích xuất đặc tả từ mã thực thi để xác định chính xác số lượng đơn vị chức năng (Functional Units: ALU, FPU, bộ nhớ đệm, thanh ghi) mà chương trình thực sự sử dụng tại từng giai đoạn chạy.
    • Tái cấu hình kiến trúc CPU: Tắt hoặc cô lập các đơn vị chức năng không hoạt động ($Nu - Nu_1$) để triệt tiêu dòng rò và công suất tĩnh $P_s, P_l$.
    • Thực nghiệm kiểm chứng bằng công cụ mô phỏng năng lượng Sim-Wattch cho thấy mức tiết kiệm năng lượng đáng kể so với việc duy trì cấu hình CPU đầy đủ trong suốt thời gian thực thi.

2. Tối ưu môi trường truyền dữ liệu và mã tự sửa

  • Tối ưu hóa giao thức truyền thông phân tán bằng cách loại bỏ các trường tiêu đề và thông điệp dư thừa, kết hợp cơ chế nén gói tin thích ứng.
  • Đánh giá khả năng áp dụng kỹ thuật mã tự sửa (Self-modifying code) trong việc giảm dung lượng bộ nhớ chương trình và thích ứng động với điều kiện tham số môi trường thực thi.

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả cụ thể và tự nêu các đóng góp mới về mặt lý luận khoa học cũng như thực tiễn ứng dụng như sau:

Đóng góp về mặt lý luận và phương pháp

  1. Xây dựng mô hình tổng thể về bài toán tối ưu hóa trong phát triển phần mềm nhúng, bao quát các tiêu chí tối ưu (hiệu năng, bộ nhớ, điện năng, chi phí, đa mục tiêu) xuyên suốt ba giai đoạn (thiết kế, lập trình, thực thi) theo hai hướng tiếp cận kỹ nghệ xuôi và kỹ nghệ ngược.
  2. Xây dựng hệ thống 6 độ đo thành phần ($S_1 - S_6$) cùng hàm đánh giá hiệu năng ($f_p$) định lượng dựa trên số thao tác bộ nhớ trực tiếp từ biểu đồ lớp UML mà không cần qua mô phỏng đầy đủ; thiết lập phương pháp tối ưu đa mục tiêu dựa trên nguyên lý Pareto ở mức thiết kế lớp.
  3. Đề xuất phương pháp tối ưu dung lượng bộ nhớ đỉnh dựa trên sắp xếp tô-pô trên đồ thị tác vụ phụ thuộc (DTG).
  4. Cải tiến thuật toán loại bỏ biểu thức con chung (CSE) trong trình biên dịch GCC dựa trên việc phát hiện và thay thế các biểu thức tương đương đại số trên đồ thị DAG.
  5. Phát triển phương pháp lập lịch lệnh hợp ngữ sử dụng thuật toán di truyền (GA) giúp tối ưu đồng thời hiệu năng và giảm chuyển mạch điện dung tiêu thụ điện năng cho các kiến trúc CPU đường ống lệnh và siêu vô hướng.
  6. Đề xuất phương pháp tối ưu điện năng tiêu thụ ở giai đoạn thực thi kết hợp giữa kỹ nghệ ngược và kỹ thuật tái cấu hình động phần cứng CPU.

Đóng góp về mặt thực tiễn

  • Xây dựng thành công khung làm việc DSL và bộ mẫu T4 tích hợp trong môi trường Visual Studio, cho phép thiết kế đồ họa trực quan và tự động trích xuất đặc tả, tự động tính toán các độ đo và lựa chọn mô hình thiết kế tối ưu.
  • Xây dựng phần mềm nhận dạng chữ Nôm chạy trên thiết bị di động (PocketPC) và nền tảng dịch vụ web phân tán, ứng dụng hiệu quả các giải pháp tối ưu bộ nhớ, nén dữ liệu và nâng cao hiệu năng thực thi, đóng góp thiết thực cho công tác bảo tồn di sản văn hóa chữ Nôm.
  • Cung cấp bộ chương trình thực nghiệm chuẩn và mã nguồn công cụ tối ưu trên nền vi điều khiển Netduino/Netduino Plus và môi trường mô phỏng MIPS (SimpleScalar, Sim-Wattch).

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án

  • Về phạm vi kiến trúc: Các mô hình đánh giá ở giai đoạn thiết kế và tối ưu mã nguồn mức cao chủ yếu giả định trên nền tảng phần cứng theo kiến trúc Von Neumann truyền thống, chưa mở rộng cho các hệ thống phần cứng không đồng nhất (Heterogeneous Systems) hoặc các bộ xử lý chuyên dụng DSP/GPU.
  • Về phạm vi tối ưu mức lệnh: Phương pháp lập lịch lệnh hợp ngữ bằng thuật toán di truyền GA mới khảo sát trên 5 cấu hình vi xử lý đơn luồng và giới hạn trong phạm vi các câu lệnh thực thi đơn chu trình.
  • Về mức độ tích hợp kỹ nghệ ngược: Việc chuyển đổi ngược từ mã thực thi/hợp ngữ lên mô hình thiết kế mức cao mới được đề xuất ở dạng quy trình khung và thực nghiệm từng phần, chưa xây dựng thành một công cụ tự động hóa hoàn toàn khép kín.

Hướng nghiên cứu tiếp theo

  • Mở rộng hệ thống độ đo và các hàm đánh giá sang các mô hình kiến trúc phần cứng hiện đại như kiến trúc đa lõi (Multi-core SoC), vi xử lý nhúng hỗ trợ xử lý song song mức dữ liệu (SIMD/Vector).
  • Tích hợp sâu các cải tiến thuật toán CSE và thuật toán lập lịch lệnh GA vào nhân của các bộ trình biên dịch mở chuẩn công nghiệp (như LLVM/Clang và nhánh chính của GCC).
  • Phát triển hoàn thiện công cụ phân tích mã thực thi tự động phục vụ kỹ nghệ ngược và tái cấu hình động phần cứng trên các chip FPGA/ASIC.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học: Cung cấp tài liệu tham khảo chi tiết về phương pháp nghiên cứu tối ưu hóa phần mềm nhúng, cách thức mô hình hóa toán học các ràng buộc tài nguyên phần cứng thành các độ đo phần mềm, và kỹ thuật áp dụng giải thuật di truyền trong tối ưu hóa mã lệnh.
  • Giảng viên và nhà nghiên cứu chuyên ngành Công nghệ thông tin/Kỹ thuật phần mềm: Là nguồn tài liệu giảng dạy cho các học phần chuyên sâu về Hệ thống nhúng, Kỹ nghệ phần mềm, Lý thuyết trình biên dịch và Tối ưu hóa hệ thống máy tính.
  • Kỹ sư phát triển phần mềm nhúng và hệ thống IoT: Có thể tham khảo trực tiếp khung làm việc DSL/T4 (trình bày tại Phụ lục P.1) để áp dụng đánh giá tự động mô hình lớp ngay từ khâu thiết kế trên Visual Studio; áp dụng các quy tắc tối ưu hóa cấu trúc dữ liệu, nén truyền thông và tinh chỉnh mã hợp ngữ trên các dòng vi điều khiển lõi ARM và vi xử lý MIPS.

Câu hỏi thường gặp

1. Hàm đánh giá hiệu năng trên biểu đồ lớp $f_p$ được tính toán như thế nào và tại sao các trọng số lại có giá trị $\alpha_1=2, \alpha_2=2, \alpha_3=4, \alpha_4=3, \alpha_5=3, \alpha_6=7$?

Hàm $f_p = 2 S_1 + 2 S_2 + 4 S_3 + 3 S_4 + 3 S_5 + 7 S_6$ ước lượng số lần thao tác bộ nhớ (cấp phát và truy xuất). Các trọng số được xác lập dựa trên cơ chế nạp và thực thi trong mô hình hướng đối tượng:

  • Biến tĩnh ($S_1$) và phương thức tĩnh ($S_2$) chỉ cần 1 thao tác cấp phát khi nạp chương trình và 1 thao tác truy xuất ($\alpha_1 = \alpha_2 = 2$).
  • Thực thi phương thức tĩnh ($S_3$) cần 1 truy xuất lệnh, 1 cấp phát tham số, 1 truy xuất tham số và 1 truy xuất kết quả trả về ($\alpha_3 = 4$).
  • Biến đối tượng ($S_4$) và phương thức đối tượng ($S_5$) cần 1 cấp phát động và 2 thao tác truy xuất tham chiếu ($\alpha_4 = \alpha_5 = 3$).
  • Thực thi phương thức đối tượng ($S_6$) bao gồm chi phí tạo đối tượng cộng với chi phí thực thi phương thức (gồm con trỏ this), tổng cộng cần ít nhất 2 thao tác cấp phát và 5 thao tác truy xuất ($\alpha_6 = 7$).

2. Phương pháp tối ưu bộ nhớ chiếm dụng dựa trên sắp xếp tô-pô giải quyết bài toán gì?

Phương pháp này áp dụng cho các hệ thống nhúng có các tác vụ phụ thuộc lẫn nhau biểu diễn qua đồ thị DTG. Do các tác vụ giải phóng bộ nhớ heap sau khi thực thi xong, thứ tự kích hoạt các tác vụ sẽ quyết định dung lượng bộ nhớ đỉnh (peak memory) cần cấp phát tại một thời điểm $M = S_c + S_e + D_s$. Thuật toán sắp xếp tô-pô duyệt qua các chuỗi thứ tự thực thi hợp lệ để tìm ra chuỗi có dung lượng bộ nhớ chiếm dụng cực đại là nhỏ nhất, giúp phần mềm chạy vừa vặn trong dung lượng RAM giới hạn của thiết bị.

3. Cải tiến của luận án đối với kỹ thuật loại bỏ biểu thức con chung (CSE) trong trình biên dịch GCC là gì?

Thuật toán CSE truyền thống trong GCC xây dựng đồ thị DAG cho từng khối cơ bản và chỉ triệt tiêu các biểu thức hoàn toàn giống nhau về mặt chuỗi cú pháp. Cải tiến của luận án là bổ sung khả năng phát hiện các biểu thức tương đương về mặt toán học và logic (ví dụ các biến thể đại số của phép toán số học giao hoán, phân phối). Việc thay thế bằng biểu thức tương đương giúp loại bỏ triệt để các phép tính dư thừa mà cấu trúc DAG chuẩn bỏ sót, từ đó rút ngắn thời gian thực thi của khối lệnh.

4. Thuật toán di truyền (GA) được ứng dụng trong việc lập lịch lệnh hợp ngữ như thế nào?

Mỗi chuỗi lệnh hợp ngữ trong một khối cơ bản được mã hóa thành một nhiễm sắc thể. Quá trình lai ghép và đột biến tái sắp xếp thứ tự các lệnh nhằm thỏa mãn các ràng buộc phụ thuộc dữ liệu thực (RAW), đồng thời triệt tiêu các xung đột đường ống (pipeline stalls) và giảm chuyển mạch logic giữa các thanh ghi. Hàm thích nghi đánh giá đồng thời hai tiêu chí: tổng số chu kỳ xung nhịp thực thi (tối ưu hiệu năng) và mức chuyển mạch điện dung $C_c$ (tối ưu điện năng tiêu thụ).

5. Phương pháp tối ưu điện năng ở giai đoạn thực thi dựa trên tái cấu hình CPU hoạt động theo nguyên lý nào?

Phương pháp phân tích chương trình đang thực thi để xác định số lượng đơn vị chức năng CPU (như ALU, FPU, bộ nhớ đệm) thực sự tham gia tính toán ở từng phân đoạn. Thông qua kỹ thuật tái cấu hình, hệ thống sẽ ngắt xung nhịp hoặc cắt nguồn đối với các đơn vị chức năng nhàn rỗi, từ đó triệt tiêu dòng công suất ngắn mạch ($P_s$) và công suất rò rỉ tĩnh ($P_l$), giảm tổng công suất tiêu thụ $P_{\text{CPU}}$ của bộ xử lý mà không làm ảnh hưởng đến tính đúng đắn của chương trình.

Kết luận

Luận án của tác giả Phạm Văn Hưởng đã giải quyết bài toán tối ưu hóa phần mềm nhúng thông qua việc xây dựng mô hình tối ưu tổng thể kết hợp giữa kỹ nghệ xuôi và kỹ nghệ ngược qua 3 giai đoạn: thiết kế, lập trình và thực thi. Điểm trọng tâm của công trình là thiết lập hệ thống độ đo định lượng đánh giá trực tiếp hiệu năng và bộ nhớ từ biểu đồ lớp UML thông qua khung làm việc DSL/T4, cải tiến thuật toán loại bỏ biểu thức con chung trong GCC, tối ưu lịch lệnh hợp ngữ bằng giải thuật di truyền và tiết kiệm điện năng bằng tái cấu hình CPU. Các kết quả nghiên cứu đã được kiểm chứng thực nghiệm chặt chẽ trên nền tảng phần cứng bo mạch Netduino Plus, vi xử lý MIPS và hệ thống nhận dạng chữ Nôm phân tán, cung cấp các đóng góp có giá trị khoa học và khả năng ứng dụng thực tế.