Tổng quan luận án

Hệ thống nhúng và phần mềm nhúng đóng vai trò trọng yếu trong sự phát triển của công nghệ thông tin. Số liệu thống kê được tác giả trích dẫn từ các công trình trước cho thấy: năm 1999 có đến 99% số vi xử lý thuộc về hệ thống nhúng, và đến năm 2011 có trên 95% số vi mạch (chip) sản xuất trên thế giới được sử dụng cho các ứng dụng nhúng. Các sản phẩm nhúng hiện diện phổ biến trong đời sống và công nghiệp, từ thiết bị gia dụng, thông tin liên lạc, thiết bị y tế đến các hệ thống hàng không, vũ trụ và quân sự.

Khác với phần mềm thông thường trên máy tính cá nhân, phần mềm nhúng gắn liền và phụ thuộc chặt chẽ vào môi trường phần cứng, thường xuyên phải hoạt động trong điều kiện bị giới hạn nghiêm ngặt về tài nguyên như tốc độ xử lý của CPU, dung lượng bộ nhớ (RAM, ROM), thời gian sống của pin và các ràng buộc thời gian thực. Tại Việt Nam, nghiên cứu và phát triển hệ thống nhúng còn hạn chế, thiếu sự liên kết chặt chẽ giữa trường đại học, viện nghiên cứu và doanh nghiệp; đa phần 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 nhúng còn ít và chủ yếu làm theo đơn đặt hàng từ đối tác nước ngoài.

Về khoảng trống nghiên cứu, các công trình đi trước chủ yếu tiếp cận tối ưu hóa đơn lẻ ở một giai đoạn (phổ biến nhất là biên dịch mã nguồn ở giai đoạn lập trình), chưa có một mô hình tối ưu tổng thể kết hợp cả kỹ nghệ xuôi (forward engineering) và kỹ nghệ ngược (reverse engineering). Trong giai đoạn thiết kế, các nghiên cứu đánh giá mô hình hướng đối tượng chủ yếu tập trung vào các độ đo chất lượng phần mềm (tính module, tính đóng gói, khả năng tái sử dụng, khả năng bảo trì) mà chưa có độ đo và hàm đánh giá định lượng trực tiếp về hiệu năng và bộ nhớ từ biểu đồ lớp; việc tối ưu đa mục tiêu cân bằng giữa hiệu năng và bộ nhớ trên biểu đồ lớp chưa được giải quyết. Trong giai đoạn lập trình, kỹ thuật tối ưu mã nguồn độc lập máy đích chưa xét đến việc thay thế biểu thức tương đương; việc lập lịch lệnh hợp ngữ hướng đến các kiến trúc vi xử lý nhúng chưa giải quyết thấu đáo việc đánh giá tiêu thụ điện năng trên kiến trúc đường ống lệnh và siêu vô hướng. Trong giai đoạn thực thi, các nghiên cứu chưa kết hợp kỹ nghệ ngược với kỹ thuật tái cấu hình vi xử lý để giảm điện năng tiêu thụ.

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

Bài toán tối ưu đơn mục tiêu được luận án hình thức hóa dưới dạng bài toán quy hoạch toán học với các ràng buộc tương hỗ (đánh số theo văn bản):

  1. Tối ưu hiệu năng: $$f_p \to \min \quad \text{với các ràng buộc} \quad f_e \le f_{e0}, , f_m \le f_{m0}, , f_c \le f_{c0} \tag{1.1}$$

  2. Tối ưu bộ nhớ: $$f_m \to \min \quad \text{với các ràng buộc} \quad f_p \le f_{p0}, , f_e \le f_{e0}, , f_c \le f_{c0} \tag{1.2}$$

  3. Tối ưu tiêu thụ điện năng: $$f_e \to \min \quad \text{với các ràng buộc} \quad f_p \le f_{p0}, , f_m \le f_{m0}, , f_c \le f_{c0} \tag{1.3}$$

  4. Tối ưu chi phí: $$f_c \to \min \quad \text{với các ràng buộc} \quad f_p \le f_{p0}, , f_e \le f_{e0}, , f_m \le f_{m0} \tag{1.4}$$

Trong đó, $f_p$ là hàm đánh giá hiệu năng (thời gian thực thi), $f_e$ là hàm đánh giá điện năng tiêu thụ, $f_m$ là hàm đánh giá dung lượng bộ nhớ, $f_c$ là hàm đánh giá chi phí sản xuất; các giá trị $f_{p0}, f_{e0}, f_{m0}, f_{c0}$ là các ngưỡng giới hạn trên cho phép của hệ thống. Bên cạnh đó, bài toán tối ưu đa mục tiêu được xây dựng trên nguyên lý Pareto nhằm tìm kiếm không gian cân bằng giữa các tiêu chí mâu thuẫn thông qua hàm đa mục tiêu toàn cục kết hợp véc-tơ trọng số $w_i$.

Đối tượng nghiên cứu của luận án là các phương pháp, giải thuật và mô hình tối ưu hóa phần mềm nhúng trong vòng đời phát triển phần mềm (thiết kế, lập trình, thực thi).

Phạm vi nghiên cứu được xác định cụ thể:

  • Về phạm vi kiến trúc tính toán: 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 lập CPU được giới hạn nghiên cứu và thử nghiệm cho hệ thống tính toán theo kiến trúc Von Neumann.
  • Về phạm vi kiến trúc xử lý: Phương pháp lập lịch lệnh mã hợp ngữ khảo sát trên 3 mô hình kiến trúc CPU gồm đơn lệnh, đường ống lệnh (pipeline) và siêu vô hướng (superscalar, gồm hai biến thể in-order và out-of-order) trong phạm vi các lệnh đơn chu trình.
  • Về phạm vi phần cứng và phần mềm thực nghiệm: Vi điều khiển AT91SAM7X512 (lõi ARM7, kiến trúc RISC) trên bo mạch Netduino và Netduino Plus hoạt động với máy ảo .NET Micro Framework 4.2; môi trường mô phỏng vi xử lý MIPS thông qua phần mềm SimpleScalar và Sim-Wattch; ứng dụng nhận dạng chữ Nôm trên thiết bị di động (PocketPC/điện thoại di động).
  • Về thời gian và địa điểm: Luận án được hoàn thành và bảo vệ năm 2015 tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội.

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

Luận án tổng hợp và phân loại tình hình nghiên cứu liên quan theo từng giai đoạn phát triển phần mềm nhúng:

Trong giai đoạn thiết kế, các nghiên cứu được phân chia thành ba hướng tiếp cận chính:

  1. Tiếp cận dựa trên kỹ nghệ hiệu năng phần mềm (Software Performance Engineering – SPE): Các công trình của Smith (1990), Balsamo (2004), Cortellessa (2000), Pooley (2000), Xu (2003), Bondavalli (2005) và Brunnert (2014) tập trung chuyển đổi mô hình thiết kế sang mô hình hiệu năng. Phần mềm nhúng được đặc tả kiến trúc bằng ngôn ngữ mô hình hóa thống nhất (UML) bổ sung thông tin hiệu năng theo các nghiên cứu của Anne (2006), Berkenkötter (2003), Woodside (2005, 2014), sau đó trích xuất thông tin sang các mô hình đánh giá như mạng hàng đợi (Gu, 2004), mạng hàng đợi phân tầng (Woodside, 2005) hoặc mạng Petri (Merseguer, 2002; Pooley, 2000; Tribastone, 2010).
  2. Tiếp cận dựa trên mã mô phỏng: Các công trình của Thompson, White và Dougherty (2009) xây dựng ngôn ngữ chuyên biệt miền (DSL) trên khung làm việc Eclipse để xây dựng kiến trúc phần mềm trên thiết bị di động, sinh mã mô phỏng nhằm đánh giá hiệu năng và cân bằng thời gian sống của pin. Anastasopoulos và Muthig (2004) nghiên cứu tối ưu trên kỹ nghệ hướng mô hình cho dòng sản phẩm. Các nghiên cứu khác (2008–2012) sử dụng DSL đặc tả mô hình thành phần trên các nền tảng Android, J2ME và giao thức SOAP, HTTP để sinh mã mô phỏng, chạy trên môi trường thực tế để lựa chọn môi trường phát triển.
  3. Tiếp cận dựa trên đánh giá trực tiếp mô hình: Các nghiên cứu đo chất lượng phần mềm hướng đối tượng từ biểu đồ lớp của Genero (2002), Pooley (2000), Yi (2004), Zhou (2012) và nghiên cứu của Al-Haj (2013) đưa ra một số tham số (số lượng lớp, số phương thức, số thuộc tính) nhưng chưa định lượng được công thức tính toán hiệu năng và bộ nhớ.

Trong giai đoạn lập trình, các nghiên cứu tập trung vào hai mức:

  1. Tối ưu mã nguồn mức cao độc lập CPU: Các kỹ thuật biến đổi mã nguồn nhằm giảm truy xuất bộ nhớ và tối ưu vòng lặp để giảm điện năng tiêu thụ (Chen, 2001; Roy, 2009; Su, 2007; Zhang, 2009); kỹ thuật tối ưu kích thước mã thông qua loại bỏ mã chết, thay thế hàm và cấp phát bộ nhớ (Anne, 2006; Cooper, 1999; Debray, 2000; Jones, 2005; Rajan, 2001); tối ưu đa mục tiêu mã nguồn trên nguyên lý Pareto (Gautam, 2006).
  2. Tối ưu mã hợp ngữ hướng CPU: Tập trung vào kiến trúc tập lệnh RISC, CISC cho các bộ xử lý nhúng như ARM, MIPS, AVR, 8051 để cải thiện hiệu năng, giảm năng lượng và kích thước chương trình (Brisk, 2007; Chen, 2005; Cooper, 2002; Lee, 2003; Park, 2001).

Trong giai đoạn thực thi:

  1. Tối ưu môi trường thực thi: Lập lịch tiến trình trên hệ điều hành nhúng dựa trên mô hình quyết định Markov của Cheung và cộng sự (2010); kỹ thuật biên dịch Just-In-Time (JIT) trên máy ảo Java và .NET (Shudo, 2001); quản lý bộ nhớ động (Hassan, 2005; Ratanaworabhan, 2009); tối ưu động trên trình thông dịch PHP (Lattner, 2004; Ngo, 2008; Xu, 2006).
  2. Tối ưu mã thực thi và tối ưu dữ liệu: Tối ưu dựa trên chuyên biệt hóa mã nguồn (Pu, 2005; Schultz, 2003; Thibault, 2000); kỹ thuật mã tự sửa (Pu, 2005); tối ưu dữ liệu và môi trường truyền thông phân tán qua nén dữ liệu và loại bỏ dư thừa thông điệp (Ngo, 2007; Razouk, 2007).

Khoảng trống nghiên cứu luận án lựa chọn giải quyết bao gồm:

  • Xây dựng mô hình tối ưu tổng thể gắn kết kỹ nghệ xuôi và kỹ nghệ ngược qua 3 giai đoạn.
  • Xây dựng độ đo, hàm đánh giá định lượng hiệu năng và bộ nhớ trực tiếp trên biểu đồ lớp; tự động hóa việc trích xuất và tối ưu bằng DSL và công cụ mẫu T4.
  • Đề xuất phương pháp tối ưu đa mục tiêu dựa trên biểu đồ lớp theo nguyên lý Pareto.
  • Đề xuất phương phá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 thuật toán loại bỏ biểu thức con chung (CSE) trong bộ biên dịch GCC bằng cách bổ sung khả năng nhận diện biểu thức tương đương.
  • Đề xuất giải thuật di truyền (GA) cho bài toán lập lịch lệnh hợp ngữ nhằm tối ưu hiệu năng và điện năng tiêu thụ trên các kiến trúc vi xử lý nhúng.
  • Đề xuất phương pháp tối ưu điện năng tiêu thụ kết hợp phần cứng và phần mềm trên kỹ nghệ ngược và tái cấu hình vi xử lý trong giai đoạn thực thi.

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

Luận án dựa trên các khung lý thuyết, khái niệm và công cụ hình thức sau:

  • Ngôn ngữ mô hình hóa thống nhất (UML) và biểu đồ lớp: Sử dụng để đặc tả kiến trúc logic và cấu trúc thành phần dữ liệu, phương thức của phần mềm nhúng hướng đối tượng.
  • Ngôn ngữ chuyên biệt miền (DSL) và Text Template Transformation Toolkit (T4) của Microsoft: DSL được sử dụng để xây dựng các mô hình đặc tả ngữ nghĩa đồ họa; T4 được sử dụng để viết mã khuôn mẫu tự động trích xuất các thông số từ mô hình ra văn bản (XML, văn bản thuần) phục vụ tính toán.
  • Lý thuyết đồ thị và bài toán sắp xếp tô-pô (Topological Sort): Biểu diễn các phụ thuộc giữa các tác vụ/mô-đun trong phần mềm bằng Đồ thị tác vụ phụ thuộc (Dependent Task Graph – DTG), từ đó áp dụng sắp xếp tô-pô để tìm chuỗi thứ tự thực thi có chi phí bộ nhớ cực tiểu.
  • Lý thuyết chuyển đổi mô hình (Model Transformation – OMT) của tác giả Anne, K.: Áp dụng các quy tắc chuyển đổi mô hình ban đầu sang mô hình tối ưu cấu trúc lớp và cấu trúc dữ liệu.
  • Nguyên lý tối ưu đa mục tiêu Pareto (Pareto Multi-objective Optimization – PMO): Xác định tập các giải pháp tối ưu không bị chi phối (Pareto-optimal set) trên không gian hai chiều giữa hàm hiệu năng $f_1$ và hàm bộ nhớ $f_2$.
  • Lý thuyết biên dịch: Đồ thị luồng điều khiển (Control Flow Graph – CFG), Đồ thị hướng không chu trình (Directed Acyclic Graph – DAG), kỹ thuật loại bỏ biểu thức con chung (Common Subexpression Elimination – CSE).
  • Giải thuật di truyền (Genetic Algorithm – GA) và giải thuật List: Ứng dụng trong việc tìm kiếm chuỗi lập lịch lệnh hợp ngữ tối ưu nhằm giải quyết xung đột dữ liệu (Read-After-Write, Write-After-Write, Write-After-Read) trên đường ống lệnh.
  • Lý thuyết tiêu thụ năng lượng của mạch tích hợp CMOS: Điện năng tiêu thụ của CPU gồm điện năng động ($P_d = C_c \cdot V_c^2 \cdot f_x \cdot \alpha$), điện năng do dòng ngắn mạch ($P_s$) và điện năng rò rỉ ($P_l$).

Phương pháp nghiên cứu thực tế:

  • Phương pháp tiếp cận từ trên xuống (top-down): Khảo sát, hệ thống hóa và phân loại toàn diện lý thuyết tối ưu hóa phần mềm nhúng, sau đó đi sâu nghiên cứu giải pháp cho từng giai đoạn cụ thể.
  • Phương pháp phân tích và tổng hợp lý thuyết: Xây dựng các mô hình toán học định lượng biểu diễn mối quan hệ giữa các thành phần mã nguồn, cấu trúc dữ liệu với số lượng thao tác bộ nhớ và chu kỳ xung nhịp.
  • Phương pháp thực nghiệm kiểm chứng (benchmarking):
    • Đối với giai đoạn thiết kế: Tiến hành thiết kế các biểu đồ lớp khác nhau cho cùng một chức năng, tự động trích xuất tham số, tính giá trị hàm đánh giá, sau đó lập trình thành mã nguồn thực thi trên phần cứng thực tế (bo mạch Netduino Plus chứa vi điều khiển ARM7) để đo thời gian thực thi trung bình qua 100 lần đo và dung lượng bộ nhớ thực tế.
    • Đối với giai đoạn lập trình và thực thi: Tích hợp giải thuật vào bộ biên dịch mã nguồn mở GCC; sử dụng các công cụ mô phỏng phần cứng cấp chu kỳ (cycle-accurate) gồm SimpleScalar và công cụ ước lượng tiêu thụ năng lượng Sim-Wattch cho tập lệnh MIPS; sử dụng môi trường Microsoft Visual Studio 2010 Express và SDK cho .NET Micro Framework 4.2.

Nguồn dữ liệu và chương trình thử nghiệm:

  • Bộ chương trình điều khiển ngoại vi nhúng viết bằng C# cho nền tảng Netduino/Netduino Plus: chương trình điều khiển 8 LED 7 thanh (Netduino_8digit), chương trình điều khiển màn hình LCD HD44780U (Netduino_LCD), chương trình giao tiếp qua cổng nối tiếp (Netduino_SerialPort).
  • Phần mềm nhận dạng chữ Nôm trên điện thoại di động (chạy trên môi trường PocketPC) kết hợp dịch vụ web phân tán (Web Service).
  • Các thuật toán kiểm thử kinh điển: bài toán Tháp Hà Nội, bài toán 8 quân Hậu.
  • Bộ chương trình nhúng mã nguồn C/hợp ngữ được biên dịch và mô phỏng trên kiến trúc vi xử lý MIPS.

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, phân tích so sánh giữa phương pháp truyền thống (phát triển phần cứng trước, sau đó phát triển phần mềm và tích hợp, thiếu linh hoạt) và phương pháp đồng thiết kế phần cứng – phần mềm (co-design, phát triển song song, tối ưu hóa phân chia phần cứng – phần mềm). Tác giả khái quát quy trình phát triển phần cứng theo mô hình chữ Y qua 4 mức (hệ thống, CPU, logic, mạch tích hợp) và quy trình phát triển phần mềm theo mô hình thác nước qua các bước phân tích, thiết kế, lập trình, kiểm thử, triển khai và bảo trì.

Từ việc phân tích thực trạng, 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 kết hợp cả kỹ nghệ xuôi và kỹ nghệ ngược qua 3 giai đoạn:

  1. Giai đoạn thiết kế: Tối ưu mô hình thiết kế theo kỹ nghệ xuôi nhằm chọn mô hình tốt nhất, đồng thời áp dụng kỹ nghệ ngược từ mã nguồn hoặc mã hợp ngữ chuyển ngược về mô hình thiết kế để tái cấu trúc.
  2. Giai đoạn lập trình: Phân chia thành hai mức là tối ưu mã nguồn mức cao độc lập CPU đích và tối ưu mã hợp ngữ hướng vi xử lý nhúng cụ thể.
  3. Giai đoạn thực thi: Tối ưu môi trường thực thi (hệ điều hành, máy ảo, trình thông dịch), tối ưu dữ liệu truyền thông và tối ưu mã thực thi (tái cấu hình phần cứng CPU).

Chương 1 cũng thiết lập hệ thống các tiêu chí tối ưu hóa cơ bản gồm: hiệu năng ($f_p$), bộ nhớ ($f_m$), tiêu thụ điện năng ($f_e$) và chi phí ($f_c$); xây dựng bài toán tối ưu đơn mục tiêu có ràng buộc từ công thức (1.1) đến (1.4); xác lập hướng tiếp cận tối ưu đa mục tiêu dựa trên nguyên lý Pareto và xác định quy trình nghiên cứu, triển khai của luận án.

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

Chương 2 trình bày các phương pháp tối ưu hóa phần mềm nhúng trong giai đoạn thiết kế theo hướng tiếp cận đánh giá trực tiếp mô hình:

  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á hiệu năng phần mềm nhúng trực tiếp từ biểu đồ lớp dựa trên số lần thao tác truy xuất và cấp phát bộ nhớ. Đầu tiên, 10 tham số được trích xuất từ biểu đồ lớp:
Tham số Ký hiệu Mô tả
Biến tĩnh $as_j$ Thuộc tính tĩnh thứ $j$ của lớp, cấp phát khi nạp chương trình
Biến đối tượng $ao_j$ Thuộc tính thứ $j$ của đối tượng, cấp phát khi tạo đối tượng
Tham số phương thức $p_k$ Tham số thứ $k$ của một phương thức
Tập lớp $C$ Tập hợp các lớp trong biểu đồ
Tập phương thức tĩnh $Ms_i$ Tập phương thức tĩnh trong lớp thứ $i$
Tập biến tĩnh $Vs_i$ Tập thuộc tính tĩnh trong lớp thứ $i$
Tập phương thức đối tượng $Mo_i$ Tập phương thức đối tượng trong lớp thứ $i$
Tập biến đối tượng $Vo_i$ Tập thuộc tính đối tượng trong lớp thứ $i$
Tập tham số $Pm_j$ Tập tham số của phương thức thứ $j$
Biến tham chiếu $vr_j$ Biến tham chiếu gọi phương thức thứ $j$
Kiểu trả về $re_j$ Kiểu dữ liệu trả về từ phương thức thứ $j$

Từ các tham số trên, tác giả xây dựng 6 độ đo kích thước bộ nhớ:

Độ đo Ký hiệu Công thức tính toán
Kích thước biến tĩnh $S_1$ $S_1 = \sum_{i=1}^{|C|} \sum_{j=1}^{|Vs_i|} size(as_j)$
Kích thước phương thức tĩnh $S_2$ $S_2 = \sum_{i=1}^{|C|} |Ms_i| \cdot size(ref)$
Kích thước thực thi phương thức tĩnh $S_3$ $S_3 = \sum_{i=1}^{|C|} \sum_{j=1}^{|Ms_i|} \left[ \sum_{k=1}^{|Pm_j|} size(p_k) + size(re_j) \right]$
Kích thước biến đối tượng $S_4$ $S_4 = \sum_{i=1}^{|C|} \sum_{j=1}^{|Vo_i|} size(ao_j)$
Kích thước phương thức đối tượng $S_5$ $S_5 = \sum_{i=1}^{|C|} |Mo_i| \cdot size(ref)$
Kích thước thực thi phương thức đối tượng $S_6$ $S_6 = \sum_{i=1}^{|C|} \sum_{j=1}^{|Mo_i|} \left[ size(this) + \sum_{k=1}^{|Pm_j|} size(p_k) + size(re_j) \right]$

Hàm đánh giá hiệu năng $f_p$ biểu diễn số thao tác bộ nhớ được thiết lập như sau: $$f_p = \alpha \cdot S_1 + \beta \cdot S_3 + \gamma \cdot S_4 + \delta \cdot S_6 \tag{2.7}$$ Qua phân tích quá trình thực thi:

  • Thành phần tĩnh được nạp 1 lần và truy xuất 1 lần, do đó $\alpha = 2$.
  • Phương thức tĩnh cần 1 thao tác truy xuất con trỏ lệnh, 1 lần cấp phát tham số, ít nhất 1 lần truy xuất nạp tham số và 1 lần truy xuất lưu kết quả trả về, do đó $\beta = 4$.
  • Thuộc tính đối tượng cần 1 thao tác cấp phát động và 2 thao tác truy xuất (truy xuất lệnh tạo và truy xuất qua con trỏ), do đó $\gamma = 3$.
  • Phương thức đối tượng cần khởi tạo đối tượng (1 cấp phát, 2 truy xuất) kết hợp quá trình thực thi phương thức (ít nhất 1 cấp phát, 3 truy xuất), do đó $\delta = 7$. Công thức rút gọn: $f_p = 2 \cdot S_1 + 4 \cdot S_3 + 3 \cdot S_4 + 7 \cdot S_6$. Giá trị $f_p$ càng nhỏ thể hiện hiệu năng thiết kế càng tốt.

Tác giả phát triển khung làm việc trên DSL và T4 để tự động trích xuất thuộc tính mô hình và tính giá trị $f_p$. Thử nghiệm trên 3 chương trình điều khiển nhúng trên bo Netduino Plus:

Chương trình Biểu đồ lớp $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ Giá trị hàm $f_p$ Thời gian thực thi thực tế trung bình ($\mu s$)
Netduino_8digit Biểu đồ 1 12 0 12 68 24 137 1307 5.054.135
Biểu đồ 2 40 8 84 28 16 45 879 4.777.056
Netduino_LCD Biểu đồ 1 4 0 4 64 47 108 1113 8.345.647
Biểu đồ 2 32 0 47 36 47 65 956 8.054.425
Netduino_SerialPort Biểu đồ 1 4 0 4 28 24 60 600 937.369
Biểu đồ 2 32 0 64 4 24 8 460 781.022

Môi trường thực thi thử nghiệm gồm: Vi điều khiển AT91SAM7X512 (lõi ARM7, kiến trúc tập lệnh RISC), bo mạch Netduino và Netduino Plus, máy ảo .NET Micro Framework 4.2, phần mềm mô phỏng Microsoft Visual Studio 2010 Express. Kết quả đo kiểm 100 lần chạy khẳng định các biểu đồ lớp có giá trị $f_p$ nhỏ hơn đều có thời gian thực thi thực tế nhanh hơn.

  1. Tối ưu hiệu năng dựa trên chuyển đổi mô hình (OMT): Luận án cải tiến phương pháp của Anne, K. bằng cách sử dụng DSL và T4 để tự động hóa quá trình nhận diện các mẫu thiết kế và thực hiện chuyển đổi mô hình tối ưu.

  2. Tối ưu bộ nhớ trong giai đoạn thiết kế:

  • Tối ưu bộ nhớ chiếm dụng dựa trên sắp xếp tô-pô: Biểu diễn cấu trúc module và phụ thuộc thành đồ thị tác vụ phụ thuộc (DTG). Bằng thuật toán sắp xếp tô-pô, luận án tìm ra chuỗi thứ tự gọi các hàm/module sao cho tổng dung lượng bộ nhớ ngăn xếp (stack) và heap cấp phát tại thời điểm đỉnh là nhỏ nhất. Thử nghiệm trên module nhận dạng chữ Nôm đã xác định được chuỗi tô-pô có đỉnh bộ nhớ chiếm dụng thấp nhất.
  • Tối ưu bộ nhớ chiếm dụng dựa trên chuyển đổi mô hình: Tái cấu trúc mô hình dữ liệu trừu tượng, gom cụm các cấu trúc dữ liệu có cùng chu kỳ sống để giảm phân mảnh và dung lượng bộ nhớ cấp phát tĩnh.
  1. Tối ưu đa mục tiêu dựa trên biểu đồ lớp: Xây dựng hàm đa mục tiêu kết hợp giữa hàm hiệu năng $f_1$ ($f_p$) và hàm bộ nhớ $f_2$ ($f_m$) dựa trên nguyên lý tối ưu Pareto, cho phép người thiết kế xác định tập nghiệm Pareto để cân bằng giữa tốc độ thực thi và không gian bộ nhớ của phần mềm nhúng.

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ã nguồn và mã hợp ngữ:

  1. Quá trình biên dịch chéo và các mức tối ưu: Phân tích cơ chế hoạt động của trình biên dịch chéo (cross-compiler), các giai đoạn phân tích từ vựng, cú pháp, ngữ nghĩa, sinh mã trung gian và sinh mã máy đích, cùng các mức tối ưu hóa chuẩn (O1, O2, O3, Os) trong GCC.

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

  • Cơ sở lý thuyết tối ưu mã nguồn mức cao: Phân tích cấu trúc khối cơ bản (basic block) và biểu diễn đồ thị hướng không chu trình (DAG).
  • Cải tiến tối ưu độ trễ trên thay thế biểu thức tương đương: Phương pháp loại bỏ biểu thức con chung (CSE) truyền thống chỉ nhận diện các biểu thức giống hệt nhau về mặt cú pháp. Tác giả đề xuất cải tiến thuật toán CSE trong GCC bằng cách tích hợp tập luật nhận diện các biểu thức tương đương về ngữ nghĩa toán học/logic (ví dụ: thay thế phép nhân lũy thừa bằng phép dịch bit, áp dụng luật giao hoán, kết hợp). Kết quả thực nghiệm cho thấy thời gian thực thi chương trình sau tối ưu giảm rõ rệt so với bản biên dịch chuẩn.
  • Cải tiến hiệu năng phần mềm nhúng trên nén dữ liệu: Nghiên cứu tác động của việc nén dữ liệu truyền thông bằng kỹ thuật GZIP và các thuật toán nén nhẹ đối với các ứng dụng nhúng phân tán, xác định ngưỡng kích thước dữ liệu mà tại đó thời gian nén và giải nén nhỏ hơn thời gian truyền dữ liệu thô qua mạng.
  1. Tối ưu mã hợp ngữ hướng đến các CPU hệ thống nhúng:
  • Phân tích các kỹ thuật tối ưu cơ bản trên mã hợp ngữ: đổi tên thanh ghi, thay thế lệnh phức tạp bằng chuỗi lệnh đơn giản, loại bỏ mã thừa.
  • Tối ưu hiệu năng trên lập lịch lệnh: Xung đột dữ liệu (RAW, WAW, WAR) gây ra các khoảng trễ (stall cycle) trong đường ống lệnh. Luận án đề xuất phương pháp lập lịch lệnh hợp ngữ sử dụng giải thuật di truyền (GA). Một nhiễm sắc thể biểu diễn một hoán vị hợp lệ của chuỗi lệnh (thỏa mãn đồ thị phụ thuộc dữ liệu). Hàm thích nghi đánh giá tổng thời gian trễ thực thi. Thử nghiệm trên 3 kiểu kiến trúc CPU: kiến trúc đường ống lệnh, kiến trúc siêu vô hướng in-order và siêu vô hướng out-of-order cho thấy GA giảm số chu kỳ trễ tốt hơn so với thuật toán lập lịch danh sách (List Scheduling) truyền thống.
  • Tối ưu điện năng tiêu thụ trên lập lịch lệnh: Dựa trên mô hình điện dung chuyển mạch của CPU, giải thuật GA được thiết lập để tối thiểu hóa số lần thay đổi trạng thái bit giữa các lệnh liên tiếp và tắt các đơn vị chức năng nhàn rỗi trong CPU. Kết quả đánh giá thông qua điện dung chuyển mạch $C_c$ chứng minh giải thuật GA tiết kiệm điện năng tiêu thụ tốt hơn thuật toán List.

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

Chương 4 tập trung vào các giải pháp tối ưu trong môi trường thực thi của phần mềm nhúng:

  1. Tối ưu môi trường thực thi:
  • Phân tích phương pháp lập lịch tiến trình tối ưu hiệu năng và điện năng trên hệ điều hành nhúng.
  • Tối ưu trong thời gian thực thi dựa trên chuyên biệt hóa mã (code specialization): Tự động phát hiện các tham số bất biến trong thời gian chạy để nạp phiên bản hàm được tối ưu chuyên biệt.
  • Tối ưu điện năng tiêu thụ trên kỹ nghệ ngược và tái cấu hình CPU: Luận án đề xuất phương pháp phân tích tệp tin thực thi thông qua dịch ngược sang mã hợp ngữ, xác định các khối chức năng phần cứng CPU (ALU, FPU, bộ nhân, các cổng logic) không được chương trình sử dụng hoặc sử dụng với tần suất thấp. Từ đó, tiến hành tái cấu hình hệ thống (tắt nguồn hoặc ngắt xung nhịp các khối chức năng nhàn rỗi), giúp giảm tiêu thụ điện năng từ cấu hình đầy đủ ($E_1$) xuống cấu hình tối ưu ($E_2$). Thử nghiệm mô phỏng trên Sim-Wattch và SimpleScalar cho kiến trúc MIPS xác nhận mức năng lượng tiết kiệm đáng kể.

  1. Tối ưu dựa trên cải tiến môi trường truyền dữ liệu: Đánh giá thời gian xử lý cục bộ trên thiết bị di động ($T_1$), thời gian xử lý trên máy chủ ($T_2$) và thời gian truyền dữ liệu trên đường truyền ($T_3$) trong mô hình ứng dụng nhận dạng chữ Nôm phân tán, từ đó xác định phân chia tác vụ tối ưu.

  2. Tối ưu hóa chương trình thực thi dựa trên mã tự sửa (self-modifying code): Đánh giá tính khả thi và phạm vi ứng dụng của kỹ thuật tự sửa đổi các đoạn mã lệnh trong bộ nhớ RAM khi chương trình đang chạy để loại bỏ các lệnh nhảy điều kiện không cần thiết.

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

Các đóng góp mới về mặt lý luận và khoa học do tác giả tự nêu trong luận án gồm có:

  1. Xây dựng mô hình tối ưu tổng thể cho bài toán phát triển phần mềm nhúng, bao quát cả 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.
  2. Xây dựng hệ thống 6 độ đo ($S_1$ đến $S_6$) và hàm đánh giá hiệu năng ($f_p$) định lượng trực tiếp từ biểu đồ lớp UML dựa trên số thao tác bộ nhớ; đề xuất phương pháp tối ưu hiệu năng và phương pháp tối ưu đa mục tiêu Pareto trên biểu đồ lớp.
  3. Đề xuất phương phá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) trong giai đoạn thiết kế.
  4. Cải tiến phương pháp tối ưu hiệu năng và bộ nhớ dựa trên chuyển đổi mô hình (OMT) bằng việc ứng dụng ngôn ngữ chuyên biệt miền (DSL) và bộ công cụ mẫu mã T4.
  5. Cải tiến thuật toán loại bỏ biểu thức con chung (CSE) trong bộ biên dịch GCC trên cơ sở nhận diện và thay thế các biểu thức tương đương.
  6. Đề xuất phương pháp lập lịch lệnh mã hợp ngữ sử dụng giải thuật di truyền (GA) nhằm tối ưu đồng thời hiệu năng và điện năng tiêu thụ cho các kiến trúc CPU đường ống lệnh và siêu vô hướng.
  7. Đề xuất phương pháp tối ưu điện năng tiêu thụ kết hợp phần cứng và phần mềm trong giai đoạn thực thi dựa trên kỹ nghệ ngược và tái cấu hình vi xử lý.

Các kết quả thực tiễn và kiến nghị giải pháp:

  • Xây dựng thành công khung làm việc trên nền tảng Visual Studio DSL Tools và T4, cho phép tự động hóa quy trình thiết kế mô hình đồ họa, sinh đặc tả văn bản và đánh giá, lựa chọn biểu đồ lớp tối ưu.
  • Xây dựng bộ công cụ phần mềm thử nghiệm: chương trình tối ưu hiệu năng trên biểu đồ lớp, chương trình tối ưu đa mục tiêu Pareto, chương trình tối ưu bộ nhớ tô-pô, chương trình phân tích mã hợp ngữ và lập lịch lệnh tự động.
  • Triển khai ứng dụng nhận dạng chữ Nôm trên thiết bị cầm tay PocketPC kết hợp dịch vụ web phân tán, góp phần bảo tồn di sản văn hóa quốc gia và kiểm chứng các giải pháp tối ưu hóa dữ liệu truyền thông.
  • Kiến nghị áp dụng quy trình đánh giá sớm ngay từ giai đoạn thiết kế mô hình kiến trúc thay vì dồn toàn bộ nỗ lực tối ưu vào giai đoạn lập trình và biên dịch.

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

Hạn chế của luận án theo công bố của tác giả:

  • Về phạm vi kiến trúc: 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 lập máy đích mới giới hạn nghiên cứu và thử nghiệm cho các hệ thống tính toán theo kiến trúc Von Neumann.
  • Về tập lệnh và vi xử lý: Phương pháp tối ưu trên lập lịch lệnh hợp ngữ mới khảo sát trên tập lệnh đơn chu trình của một số kiến trúc CPU cụ thể (ARM7, MIPS), chưa mở rộng sang các lệnh đa chu trình phức tạp.
  • Về mức độ tự động hóa: Phương pháp tối ưu kết hợp phần cứng và phần mềm trên kỹ nghệ ngược ở giai đoạn thực thi mới dừng lại ở mức độ phân tích và mô phỏng trên công cụ phần mềm (Sim-Wattch, SimpleScalar), chưa tích hợp hoàn chỉnh thành công cụ tự động hóa khép kín trên phần cứng thực tế.

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

  • Mở rộng các độ đo và hàm đánh giá từ biểu đồ lớp sang các biểu đồ hành vi khác của UML như biểu đồ tuần tự (sequence diagram) và biểu đồ trạng thái (state machine diagram).
  • Nghiên cứu thuật toán lập lịch lệnh hợp ngữ cho các tập lệnh phức tạp có độ trễ thay đổi và các lệnh đa chu trình.
  • Nghiên cứu tối ưu hóa phần mềm nhúng trên các hệ thống vi xử lý đa lõi không đồng nhất (heterogeneous multi-core).
  • Phát triển hoàn thiện công cụ tự động hóa quy trình kỹ nghệ ngược từ mã máy sang mô hình thiết kế để phục vụ bài toán tái cấu trúc toàn diện.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên ngành hữu ích cho các nhóm đối tượng sau:

  • Nghiên cứu sinh, học viên cao học và sinh viên ngành Kỹ thuật phần mềm, Hệ thống nhúng và Khoa học máy tính: Tham khảo cơ sở lý thuyết về kỹ nghệ hiệu năng phần mềm (SPE), phương pháp hình thức hóa các độ đo phần mềm hướng đối tượng và kỹ thuật lập lịch lệnh trên đường ống vi xử lý.
  • Giảng viên giảng dạy các môn học về Kiến trúc máy tính, Thiết kế hệ thống nhúng, Trình biên dịch và Kỹ nghệ phần mềm: Có thể sử dụng các ví dụ định lượng, công thức toán học và mô hình thực nghiệm trong Chương 2 và Chương 3 làm học liệu giảng dạy.
  • Kỹ sư thiết kế và phát triển phần mềm nhúng tại các doanh nghiệp công nghệ: Tham khảo khung làm việc DSL/T4 để tự động hóa sinh mã và đánh giá sớm chất lượng kiến trúc phần mềm trước khi lập trình chi tiết, cũng như áp dụng các kỹ thuật cấu hình trình biên dịch và lập lịch lệnh để tối ưu thời gian thực thi và dung lượng bộ nhớ.

Các phần có giá trị tham khảo cao nhất trong văn bản:

  • Mục 2.1 của Chương 2: Cung cấp đầy đủ định nghĩa toán học, công thức tường minh của 6 độ đo ($S_1 - S_6$) và cách thiết lập hệ số cho hàm đánh giá hiệu năng $f_p$.
  • Phụ lục P1: Hướng dẫn chi tiết cách thiết lập khung làm việc DSL và viết mẫu T4 trong Visual Studio để tự động trích xuất thông số mô hình và sinh mã.
  • Mục 3.3 của Chương 3: Cơ chế biểu diễn nhiễm sắc thể và hàm thích nghi trong giải thuật di truyền áp dụng cho bài toán lập lịch lệnh tránh xung đột dữ liệu trên đường ống vi xử lý.

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

  1. Hàm đánh giá hiệu năng $f_p$ trên biểu đồ lớp được thiết lập dựa trên nguyên lý nào và có công thức ra sao? Trả lời: Hàm $f_p$ được thiết lập dựa trên việc định lượng số lần thao tác truy xuất và cấp phát bộ nhớ (cả tĩnh và động) của các thành phần trong biểu đồ lớp khi chương trình thực thi. Công thức tổng quát là $f_p = \alpha \cdot S_1 + \beta \cdot S_3 + \gamma \cdot S_4 + \delta \cdot S_6$, trong đó $S_1$ là kích thước biến tĩnh, $S_3$ là kích thước thực thi phương thức tĩnh, $S_4$ là kích thước biến đối tượng, $S_6$ là kích thước thực thi phương thức đối tượng. Dựa trên phân tích cơ chế nạp và gọi hàm, các hệ số phụ thuộc được xác lập cụ thể là $\alpha = 2, \beta = 4, \gamma = 3, \delta = 7$, đưa đến công thức: $f_p = 2 \cdot S_1 + 4 \cdot S_3 + 3 \cdot S_4 + 7 \cdot S_6$. Giá trị $f_p$ càng nhỏ thì hiệu năng càng cao.

  2. Kết quả kiểm chứng thực nghiệm hàm $f_p$ trên phần cứng bo mạch Netduino Plus cho thấy điều gì? Trả lời: Thử nghiệm trên 3 chương trình (Netduino_8digit, Netduino_LCD, Netduino_SerialPort) với 2 biểu đồ lớp khác nhau cho mỗi chương trình cho thấy: phiên bản có giá trị $f_p$ thấp hơn luôn có thời gian thực thi thực tế đo được qua 100 lần chạy ngắn hơn. Ví dụ, với Netduino_8digit, biểu đồ 1 có $f_p = 1307$ tương ứng thời gian chạy $5.054.135 , \mu s$, trong khi biểu đồ 2 có $f_p = 879$ tương ứng thời gian chạy giảm xuống còn $4.777.056 , \mu s$.

  3. Luận án giải quyết bài toán tối ưu bộ nhớ chiếm dụng trong giai đoạn thiết kế bằng kỹ thuật gì? Trả lời: Luận án biểu diễn các phụ thuộc giữa các module/tác vụ thành Đồ thị tác vụ phụ thuộc (DTG). Sau đó, áp dụng thuật toán sắp xếp tô-pô để duyệt các chuỗi thực thi hợp lệ và tính toán kích thước vùng nhớ ngăn xếp (stack) cùng heap cần cấp phát tại mỗi bước. Chuỗi tô-pô nào có dung lượng bộ nhớ đỉnh cực tiểu sẽ được chọn làm thứ tự thực thi chính thức.

  4. Phương pháp tối ưu mã hợp ngữ trong giai đoạn lập trình được thực hiện cho những kiến trúc vi xử lý nào? Trả lời: Luận án nghiên cứu và thử nghiệm tối ưu mã hợp ngữ cho 3 kiểu kiến trúc vi xử lý nhúng gồm: kiến trúc đơn lệnh, kiến trúc đường ống lệnh (pipeline) và kiến trúc siêu vô hướng (in-order và out-of-order) trong phạm vi các lệnh đơn chu trình, sử dụng giải thuật di truyền (GA) để lập lịch lệnh nhằm giảm thiểu chu kỳ trễ do xung đột dữ liệu và giảm điện dung chuyển mạch.

  5. Đóng góp của luận án đối với bộ biên dịch mã nguồn mở GCC là gì? Trả lời: Luận án đề xuất cải tiến thuật toán loại bỏ biểu thức con chung (CSE) trong GCC bằng cách tích hợp thêm tập luật nhận diện các biểu thức tương đương toán học và logic trên đồ thị DAG, giúp loại bỏ các đoạn tính toán trùng lặp mà trình biên dịch nguyên bản không nhận diện được do khác biệt cú pháp.

Kết luận

Luận án tiến sĩ 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 một cách hệ thống thông qua việc đề xuất mô hình tối ưu tổng thể kết hợp 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. Trọng tâm đóng góp của luận án là việc xây dựng thành công hệ thống độ đo và hàm đánh giá định lượng trực tiếp hiệu năng, bộ nhớ và tối ưu đa mục tiêu Pareto trên biểu đồ lớp UML, kết hợp công cụ tự động hóa DSL và T4. Các giải pháp cải tiến thuật toán CSE trong GCC, lập lịch lệnh hợp ngữ bằng giải thuật di truyền và tái cấu hình vi xử lý trong giai đoạn thực thi đã được kiểm chứng bằng thực nghiệm định lượng trên phần cứng ARM7 và môi trường mô phỏng MIPS, tạo nền tảng khoa học và thực tiễn rõ ràng cho lĩnh vực kỹ thuật phần mềm nhúng.