Tóm tắt Luận án Tiến sĩ ngành Công nghệ thông tin: Các phương pháp tối ưu trong phát triển phần mềm nhúng

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> Công trình được hoàn thành tại:<br /> Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội.<br /> <br /> Người hướng dẫn khoa học: PGS.TS. Nguyễn Ngọc Bình<br /> Phản biện 1: ………………………………………………<br /> Phạm Văn Hưởng<br /> <br /> Phản biện 2: ………………………………………………<br /> Phản biện 3: ……………………………………………....<br /> <br /> CÁC PHƯƠNG PHÁP TỐI ƯU<br /> TRONG PHÁT TRIỂN PHẦN MỀM NHÚNG<br /> Luận án tiến sĩ sẽ được bảo vệ trước hội đồng cấp Đại học Quốc gia chấm<br /> <br /> Chuyên ngành: Kỹ thuật phần mềm<br /> <br /> luận án tiến sĩ họp tại…………………………………………<br /> Vào hồi giờ ngày tháng năm<br /> <br /> Mã số: 62 48 01 03<br /> <br /> Có thể tìm hiểu luận án tại:<br /> <br /> TÓM TẮT LUẬN ÁN TIẾN SĨ NGÀNH CÔNG NGHỆ THÔNG<br /> TIN<br /> <br /> - Thư viện Quốc gia Việt Nam<br /> - Trung tâm Thông tin – Thư viện, Đại học Quốc gia Hà Nội<br /> <br /> Hà Nội – 2014<br /> 1<br /> <br /> 2<br /> <br /> Chương 1. TỔNG QUAN<br /> <br /> Tối ưu trong kỹ nghệ xuôi<br /> <br /> Tối ưu hóa trong kỹ nghệ ngược<br /> <br /> Giai đoạn thiết kế<br /> <br /> 1.1. Tổng quan về tối ưu phần mềm hệ thống nhúng<br /> <br /> Mô hình thiết<br /> kế<br /> <br /> Trong luận án này, đầu tiên chúng tôi điều tra, phân tích các nghiên cứu liên quan<br /> để xây dựng mô hình tổng thể cho bài toán tối ưu phần mềm nhúng như trong Hình 1.1.<br /> <br /> Tối ưu trong giai<br /> đoạn thiết kế<br /> <br /> Mô hình thiết<br /> kế<br /> <br /> Mô hình thiết<br /> kế tốt<br /> <br /> Bài toán tối ưu phần mềm nhúng được chia thành hai hướng tiếp cận chính là tối ưu trong<br /> kỹ nghệ xuôi và tối ưu hóa kết hợp với kỹ nghệ ngược. Hướng tiếp cận tối ưu trong kỹ<br /> <br /> Chuyển đổi ngược<br /> <br /> nghệ xuôi, bắt đầu từ đặc tả yêu cầu, có thể thiết kế phần mềm nhúng theo các mô hình<br /> thiết kế khác nhau và dựa trên các phương pháp tối ưu trong giai đoạn thiết kế để lựa<br /> chọn các mô hình tốt. Trong giai đoạn cài đặt, từ các mô hình thiết kế tốt, có thể cài đặt<br /> phần mềm nhúng theo mã nguồn mức cao độc lập CPU và thực hiện các phương pháp tối<br /> ưu trên mã nguồn mức cao. Vấn đề tối ưu phần mềm nhúng trong giai đoạn thiết kế và tối<br /> ưu mã nguồn mức cao cũng tương tự như phần mềm thông thường. Mã nguồn mức cao<br /> được biên dịch chéo để tạo thành mã hợp ngữ gắn với một CPU nhúng cụ thể. Trong mức<br /> mã hợp ngữ, các phương pháp tối ưu mức thường mang tính đặc thù theo kiểu kiến trúc<br /> <br /> Giai đoạn cài đặt<br /> <br /> Các khía<br /> cạnh tối ưu:<br /> - Tối ưu hiệu<br /> năng<br /> - Tối ưu bộ<br /> nhớ, …<br /> - Tối ưu đa<br /> mục tiêu<br /> <br /> Mã nguồn mức<br /> cao<br /> <br /> Tối ưu độc lập<br /> CPU<br /> <br /> Mã nguồn mức<br /> cao tốt<br /> <br /> Biên dịch chéo<br /> <br /> biên dịch và liên kết để tạo ra các tệp tin thực thi. Trong giai đoạn thực thi, các phương<br /> <br /> Mã hợp ngữ<br /> (80x86, ARM,<br /> MIPS, Power, …)<br /> <br /> pháp tối ưu phần mềm nhúng chủ yếu tập trung vào tối ưu môi trường thực thi, đặc tả dữ<br /> liệu và tái cấu hình CPU.<br /> <br /> Mã hợp ngữ tối ưu<br /> <br /> CPU và môi trường phần cứng cụ thể của mỗi hệ thống nhúng. Mã hợp ngữ có thể được<br /> <br /> Căn cứ vào các nghiên cứu về phương pháp tối ưu trong kỹ nghệ xuôi, chúng tôi<br /> <br /> Tối ưu hướng<br /> CPU đích<br /> <br /> Hợp dịch và<br /> liên kết<br /> <br /> Mã nguồn<br /> mức cao<br /> <br /> Dịch ngược<br /> <br /> Mã hợp ngữ (80x86,<br /> ARM, MIPS,<br /> Power, …)<br /> <br /> Dịch ngược<br /> <br /> cũng đưa ra hướng tiếp cận tối ưu hóa dựa trên kỹ nghệ ngược. Kỹ nghệ ngược là một<br /> khía cạnh quan trọng trong tái kỹ nghệ phần mềm. Đây là một xu hướng nghiên cứu mới<br /> và triển vọng trong phát triển phần mềm nói chung. Kỹ nghệ ngược có thể được thực hiện<br /> theo các mức khác nhau như từ mã thực thi dịch ngược sang mã hợp ngữ, từ mã hợp ngữ<br /> <br /> Tệp tin thực thi:<br /> - Dạng nhị phân<br /> - Mã máy ảo<br /> <br /> có thể dịch ngược sang mã nguồn mức cao, từ mã nguồn mức cao được chuyển ngược<br /> thành các mô hình thiết kế. Mã hợp ngữ cũng có thể được chuyển ngược thành mô hình<br /> mà không cần thông qua mã nguồn mức cao. Đầu ra tại mỗi mức trong kỹ nghệ ngược có<br /> thể được tối ưu theo mức tương ứng trong kỹ nghệ xuôi. Như vậy tối ưu hóa trong kỹ<br /> nghệ ngược là sự kết hợp giữa kỹ nghệ ngược và mức tối ưu tương ứng trong kỹ nghệ<br /> xuôi.<br /> <br /> Giai đoạn thực thi: tối ưu môi trường, dữ liệu,<br /> mã thực thi<br /> <br /> Hình 1.1: Mô hình tối ưu tổng thể trong phát triển phần mềm nhúng<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1.2. Phạm vi, nội dung, phương pháp nghiên cứu và kết cấu luận án<br /> Theo mô hình tổng thể đã đưa ra trong Hình 1.1, tối ưu phần mềm nhúng là bài<br /> toán phức tạp bao gồm nhiều khía cạnh tối ưu, và có thể tiến hành trong các giai đoạn<br /> khác nhau và có hai cách tiếp cận là dựa trên kỹ nghệ xuôi và kỹ nghệ ngược. Mục tiêu<br /> nghiên cứu trong luận án nhằm xây dựng một khung nhìn tổng thể về tối ưu phần mềm<br /> nhúng theo các giai đoạn trong vòng đời phần mềm và nghiên cứu các phương pháp tối<br /> ưu một cách hệ thống từ giai đoạn thiết kế đến triển khai. Trên cơ sở đó, các nghiên cứu<br /> trong luận án sẽ góp phần làm nền tảng ban đầu để giải quyết bài toán tối ưu tổng thể một<br /> cách hệ thống theo cả kỹ nghệ xuôi và kỹ nghệ ngược. Trong mỗi giai đoạn tối ưu, chúng<br /> tôi hệ thống, phân nhóm và đánh giá phương pháp tối ưu làm cơ sở lý thuyết để đưa ra<br /> một số cải tiến các phương pháp hiện tại cũng như đề xuất và phát triển một số phương<br /> pháp tối ưu mới nhằm góp phần giải quyết bài toán tối ưu tổng thể. Theo đó, trong luận<br /> án, chúng tôi sẽ thực hiện các nội dung nghiên cứu cụ thể sau:<br />  Tổng hợp, hệ thống và xây dựng mô hình tổng thể về tối ưu phần mềm nhúng.<br />  Nghiên cứu, đề xuất và triển khai một số phương pháp tối ưu hướng cấu trúc cho<br /> phần mềm nhúng trong giai đoạn thiết kế như tối ưu hiệu năng, tối ưu bộ nhớ và<br /> tối ưu đa mục tiêu theo hướng tiếp cận dựa trên mô phỏng và dựa trên đánh giá mô<br /> hình.<br />  Nghiên cứu, đề xuất và phát triển một số phương pháp cải tiến hiệu năng mã<br /> nguồn mức cao độc lập kiến trúc đích. Đồng thời chúng tôi cũng đề xuất và triển<br /> khai một số phương pháp mới tối ưu hiệu năng và năng lượng mức mã hợp ngữ<br /> dựa trên lập lịch tập lệnh.<br />  Tổng hợp các phương pháp tối ưu trong giai đoạn thực thi và đề xuất, triển khai<br /> phương pháp tối ưu dựa trên kỹ nghệ ngược và tái cấu hình CPU.<br />  Phát triển phần mềm nhúng (nhận dạng chữ Nôm) trên điện thoại di động cũng<br /> như xây dựng bộ chương trình nhúng mức thấp để thử nghiệm và đánh giá các<br /> phương pháp tối ưu.<br /> Cấu trúc tổng thể của luận án được chỉ ra trong Hình 1.2 và các chương còn lại của<br /> luận án được tổ chức như sau: Chương 2: Tối ưu phần mềm nhúng trong giai đoạn thiết<br /> kế; Chương 3: Tối ưu phần mềm nhúng trong giai đoạn cài đặt; Chương 4: Tối ưu phần<br /> mềm nhúng trong giai đoạn thực thi; Chương 5: Tổng hợp các chương trình thực<br /> nghiệm; Chương 6: Kết luận.<br /> <br /> LUẬN ÁN<br /> - Điều tra, phân tích, tổng hợp hiện trạng nghiên cứu<br /> - Xây dựng mô hình tối ưu tổng thể<br /> - Các công trình đã xuất bản liên quan đến hệ thống nhúng: [1, 3,<br /> 4, 5, 7, 8]<br /> <br /> Chương 1. Tổng quan<br /> <br /> Chương 2. Tối ưu<br /> trong giai đoạn thiết kế<br /> <br /> Dựa trên đánh giá biểu đồ lớp:<br /> - Các nghiên cứu liên quan: [3, 8, 9, 10, 21, 24, 26, 34, 36, 41,75]<br /> - Công trình đã xuất bản: [6, 9]<br /> <br /> Tối ưu hiệu năng<br /> <br /> Tối ưu bộ nhớ<br /> <br /> Dựa trên chuyển đổi mô hình:<br /> - Các nghiên cứu liên quan: [6, 7, 24, 34, 61, 73, 82, 93, 106, 108]<br /> - Đề xuất: Tối ưu hiệu năng dựa trên DSL, T4 và thu gọn mô hình<br /> Dựa trên sắp xếp Tô-pô<br /> - Các nghiên cứu liên quan: [25, 59, 73, 74, 109]<br /> - Các công trình đã xuất bản: [2, 10]<br /> Dựa trên chuyển đổi mô hình<br /> - Các nghiên cứu liên quan: [7, 34, 35, 36, 50, 68, 82, 92, 93, 104]<br /> - Đề xuất: Tối ưu bộ nhớ dựa trên DSL, T4 và chuyển đổi mô hình<br /> <br /> Tối ưu đa mục<br /> tiêu dựa<br /> <br /> - Các nghiên cứu liên quan: [4, 34, 36, 42, 44, 48, 50, 52, 73, 74,<br /> 88, 95, 98, 105]<br /> - Công trình đã xuất bản: [4, 5, 8, 11]<br /> <br /> Chương 3. Tối ưu<br /> trong giai đoạn cài đặt<br /> Tối ưu mã nguồn<br /> độc lập CPU<br /> Tối ưu mã hợp<br /> ngữ hướng CPU<br /> Chương 4. Tối ưu trong<br /> giai đoạn thực thi<br /> <br /> Dựa trên thay thế biểu thức tương đương<br /> - Các nghiên cứu liên quan: [12, 29, 43, 46, 69, 72]<br /> - Công trình đã xuất bản: [12]<br /> Dựa trên nén dữ liệu<br /> - Các nghiên cứu liên quan: [20, 45, 53, 66, 70, 71, 91]<br /> - Các nghiên cứu liên quan: [28, 30, 33, 56, 69, 72, 78]<br /> - Đề xuất: Tối ưu phần mềm nhúng dựa trên kỹ nghệ ngược (chờ<br /> phản biện ở tạp chí SCI: IEICE). Tối ưu hiệu năngdựa trên lập lịch<br /> tập lệnh mức CPU (chờ phản biện vòng 2 ở tạp chí SCI: JCSC)<br /> <br /> Tối ưu môi<br /> trường thực thi<br /> <br /> - Các nghiên cứu liên quan: [18, 31, 39, 49, 67, 85, 90]<br /> - Đề xuất: Tối ưu điện năng tiêu thụ dựa trên kỹ nghệ ngược và tái<br /> cấu hình CPU (báo cáo tại FAIR 2014)<br /> <br /> Tối ưu dữ liệu<br /> <br /> Các nghiên cứu liên quan: [39, 55, 85, 86]<br /> <br /> Tối ưu mã thực<br /> thi<br /> Chương 5. Tổng hợp các<br /> chương<br /> trình<br /> thực<br /> nghiệm<br /> Chương 6. Kết luận<br /> <br /> Các nghiên cứu liên quan: [39, 85, 86]<br /> Xây dựng các công cụ DSL và T4: Biểu đồ lớp, biểu đồ tác vụ phụ<br /> thuộc<br /> Xây dựng các chương trình tối ưu: hiệu năng, bộ nhớ, đa mục tiêu<br /> Tổng hợp các chương trình thử nghiệm: Chữ Nôm, tháp Hà Nội, 8<br /> quân Hậu, sắp xếp nhanh và các chương trình nhúng với giao diện<br /> dòng lệnh cho MIPS<br /> <br /> Hình 1.2: Cấu trúc tổng thể luận án<br /> <br /> 3<br /> <br /> 4<br /> <br /> Chương 2. TỐI ƯU PHẦN MỀM NHÚNG TRONG<br /> <br /> ii.<br /> <br /> Xây dựng các độ đo và hàm đánh giá hiệu năng<br /> Các tham số từ biểu đồ lớp<br /> <br /> <br /> <br /> GIAI ĐOẠN THIẾT KẾ<br /> <br /> Bảng 2.1. Các tham số sử dụng để đánh giá hiệu năng<br /> Tham số<br /> <br /> Các nghiên cứu về tối ưu trong giai đoạn thiết kế được chia thành ba cách tiếp cận<br /> đó là tối ưu dựa trên mô phỏng, dựa trên SPE và dựa trên đánh giá trực tiếp từ các mô<br /> hình đặc tả phần mềm. Theo cách tiếp cận dựa trên mô phỏng, từ các đặc tả phần mềm sẽ<br /> sinh mã mô phỏng và thực thi mã mô phỏng trên môi trường thật hoặc môi trường giả lập<br /> để thống kê, đánh giá nhằm lựa chọn mô hình tốt. Theo cách tiếp cận SPE, từ đặc tả kiến<br /> trúc phần mềm sẽ chuyển sang các mô hình hiệu năng sau đó đánh giá mô hình hiệu năng<br /> để chọn thiết kế tốt. Tuy nhiên cách tiếp cận SPE chỉ dùng cho lớp bài toán tối ưu hiệu<br /> năng trong giai đoạn thiết kế. Cách tiếp cận dựa trên đánh giá trực tiếp các đặc tả phần<br /> mềm là một cách tiếp cận mới, hiện tại có rất ít nghiên cứu và chỉ tập trung vào đánh giá<br /> hiệu năng phần mềm. Kết quả tối ưu phần mềm nhúng trong giai đoạn thiết kế nhằm đạt<br /> được các mô hình phần mềm tốt và các lựa chọn như môi trường, công cụ, thư viện, nền<br /> tảng được đưa ra sớm. Ngoài ra đạt được sự phân chia phần cứng – phần mềm tốt cũng là<br /> một kết quả tối ưu mức hệ thống có ý nghĩa trong giai đoạn này.<br /> Tối ưu phần mềm nhúng trong giai đoạn thiết kế, ngoài các mục tiêu về hiệu năng,<br /> điện năng tiêu thụ, bộ nhớ, chi phí, … còn các mục tiêu tối ưu mang tính đặc thù trong<br /> giai đoạn thiết kế như tính tin cậy, tính an toàn, tính tái sử dụng, tính tái cấu trúc. Đây là<br /> các mục tiêu tối ưu cụ thể. Đồng thời, các phương pháp tối ưu được chia thành ba nhóm:<br /> tối ưu đơn mục tiêu, tối ưu đa mục tiêu và tối ưu chuyển từ đa mục tiêu sang đơn mục<br /> tiêu. Trong chương này, sau khi tổng hợp nghiên cứu các phương pháp tối ưu hiện tại,<br /> chúng tôi đề xuất và phát triển một số phương pháp tối ưu đó là phương pháp tối ưu hiệu<br /> năng phần mềm nhúng dựa trên đánh giá biểu đồ lớp và dựa trên chuyển đổi mô hình, tối<br /> ưu mức chiếm dụng bộ nhớ dựa trên sắp xếp Tô-pô, dựa trên chuyển đổi mô hình và tối<br /> ưu đa mục tiêu.<br /> <br /> 2.1. Tối ưu hiệu năng trong giai đoạn thiết kế<br /> 2.1.1. Tối ưu hiệu năng dựa trên biểu đồ lớp<br /> i.<br /> <br /> Ý tưởng<br /> Ý tưởng cơ bản của phương pháp tối ưu hiệu năng phần mềm nhúng dựa trên biểu<br /> <br /> Ký hiệu<br /> <br /> Mô tả<br /> <br /> Biến tĩnh<br /> <br /> as<br /> <br /> Là một thuộc tính tĩnh của một lớp. Được cấp phát bộ<br /> nhớ ngay khi nạp chương trình.<br /> <br /> Biến đối tượng<br /> <br /> ao<br /> <br /> Là một thuộc tính của đối tượng. Được cấp phát bộ<br /> <br /> Tham số phương thức<br /> <br /> p<br /> <br /> Là một tham số của một phương thức<br /> <br /> Tập các lớp<br /> <br /> A<br /> <br /> Là tập các lớp trong biểu đồ<br /> <br /> Tập các phương thức tĩnh<br /> <br /> B<br /> <br /> Tập các phương thức tĩnh của một lớp<br /> <br /> Tập các biến tĩnh<br /> <br /> C<br /> <br /> Tập các thuộc tính tĩnh của một lớp<br /> <br /> Tập các phương thức đối<br /> tượng<br /> <br /> D<br /> <br /> Tập các phương thức đối tượng trong một lớp<br /> <br /> Tập các biến đối tượng<br /> <br /> E<br /> <br /> Tập các thuộc tính tượng trong một lớp<br /> <br /> Tập các tham số<br /> <br /> F<br /> <br /> Tập các tham số của một phương thức<br /> <br /> Biến tham chiếu<br /> <br /> vr<br /> <br /> Biến tham chiếu để gọi một phương thức<br /> <br /> Kiểu trả về<br /> <br /> re<br /> <br /> Kiểu dữ liệu trả về từ một phương thức<br /> <br /> nhớ khi đối tượng được tạo.<br /> <br /> <br /> <br /> Các độ đo ảnh hưởng đến hiệu năng<br /> Bảng 2.2. Các độ đo ảnh hưởng đến hiệu năng<br /> <br /> Độ đo<br /> <br /> Công thức tính<br /> <br /> Ký hiệu<br /> <br /> Kích thước các biến<br /> tĩnh<br /> <br /> S1<br /> <br /> =<br /> <br /> )<br /> <br /> (2.1)<br /> <br /> size(<br /> <br /> )<br /> <br /> (2.2)<br /> <br /> +<br /> <br /> size(<br /> <br /> | |<br /> <br /> =<br /> <br /> S2<br /> <br /> | |<br /> <br /> | |<br /> <br /> Kích thước thực thi<br /> <br /> đồ lớp là phân tích, đánh giá trực tiếp các thành phần trong biểu đồ lớp và xây dựng hàm<br /> <br /> các<br /> <br /> đánh giá hiệu năng để lựa chọn biểu đồ lớp tốt.<br /> <br /> phương<br /> <br /> thức<br /> <br /> =<br /> <br /> (size(<br /> <br /> tĩnh<br /> Kích thước các biến<br /> đối tượng<br /> <br /> 5<br /> <br /> size(<br /> | |<br /> <br /> Kích thước các<br /> phương thức tĩnh<br /> <br /> Chỉ số<br /> <br /> S3<br /> <br /> | |<br /> <br /> | |<br /> <br /> =<br /> <br /> S4<br /> <br /> size(<br /> | |<br /> <br /> 6<br /> <br /> ))<br /> <br /> (2.3)<br /> <br /> | |<br /> <br /> | |<br /> <br /> )<br /> <br /> (2.4)<br /> <br /> Kích<br /> <br /> thước<br /> <br /> phương<br /> <br /> thức<br /> <br /> các<br /> đối<br /> <br /> ii.<br /> <br /> =<br /> <br /> S5<br /> <br /> size(<br /> | |<br /> <br /> tượng<br /> <br /> )<br /> <br /> (2.5)<br /> <br /> | |<br /> <br /> đổi từ tĩnh sang động và ngược lại.<br /> <br /> Kích thước thực thi<br /> các phương thức đối<br /> <br /> Các phép biến đổi trên mô hình<br /> Để tối ưu hiệu năng chúng tôi đưa ra ba phép biến đổi là thu gọn kiểu dữ liệu,<br /> chuyển đổi tham số của các phương thức thành các thành viên dữ liệu của lớp và chuyển<br /> <br /> =<br /> <br /> S6<br /> <br /> (size<br /> | |<br /> <br /> tượng<br /> <br /> +<br /> <br /> | |<br /> <br /> size(<br /> <br /> ))<br /> <br /> (2.6)<br /> <br /> | |<br /> <br /> iii.<br /> <br /> Thực nghiệm<br /> Bảng 2.4. Tổng hợp kết quả tối ưu và thử nghiệm thực tế<br /> <br />  Hàm đánh giá hiệu năng<br /> Chúng tôi xây dựng hàm đánh giá hiệu năng fp theo các độ đo tĩnh như trong công<br /> <br /> Tháp Hà Nội<br /> <br /> 2583<br /> <br /> 1962<br /> <br /> 2357<br /> <br /> 1753<br /> <br /> 8 quân Hậu<br /> <br /> 1862<br /> <br /> 1506<br /> <br /> 1664<br /> <br /> 1355<br /> <br /> Sắp xếp nhanh<br /> <br /> 1025<br /> <br /> 847<br /> <br /> 983<br /> <br /> 639<br /> <br /> độ đo tương ứng và S1 đến S6 được tính theo các công thức từ (2.1) đến (2.6).<br /> +<br /> <br /> )+b×<br /> <br /> +g×(<br /> <br /> +<br /> <br /> Mô hình tối ưu<br /> <br /> fp<br /> <br /> thức (2.7). Trong công thức (2.7), a, b, g và e là các hệ số phụ thuộc của hiệu năng vào<br /> <br /> = a×(<br /> <br /> Mô hình ban đầu<br /> <br /> Chương trình thử<br /> nghiệm<br /> <br /> )+e×<br /> <br /> Hiệu năng thực<br /> tế<br /> <br /> fp<br /> <br /> Hiệu năng thực<br /> tế<br /> <br /> (2.7)<br /> <br /> 2.2. Tối ưu bộ nhớ trong giai đoạn thiết kế<br /> iii.<br /> <br /> Thực nghiệm<br /> <br /> 2.2.1. Tối ưu bộ nhớ dựa trên sắp xếp Tô-pô<br /> <br /> Bảng 2.3. Tổng hợp tham số, độ đo và hàm đánh giá hiệu năng chương trình 8 quân Hậu<br /> <br /> Biểu đồ<br /> <br /> Số<br /> lớp<br /> <br /> Số<br /> Số<br /> Số<br /> Số<br /> phương thuộc phương thuộc<br /> thức<br /> tính<br /> thức<br /> tính<br /> tĩnh<br /> tĩnh<br /> động<br /> động<br /> <br /> S1<br /> <br /> S2<br /> <br /> S3<br /> <br /> S4<br /> <br /> S5<br /> <br /> S6<br /> <br /> i.<br /> <br /> fP<br /> <br /> theo một tập các tác vụ thỏa mãn một đồ thị phụ thuộc; các tác vụ này có thể thực hiện<br /> theo các thứ tự khác nhau mà không làm thay đổi kết quả; mỗi thứ tự thực thi chính là<br /> <br /> 1<br /> <br /> 6<br /> <br /> 3<br /> <br /> 3<br /> <br /> 10<br /> <br /> 14<br /> <br /> 12<br /> <br /> 12<br /> <br /> 20<br /> <br /> 40<br /> <br /> 56<br /> <br /> 96<br /> <br /> 1088<br /> <br /> 2<br /> <br /> 3<br /> <br /> 8<br /> <br /> 10<br /> <br /> 3<br /> <br /> 7<br /> <br /> 32<br /> <br /> 40<br /> <br /> 48<br /> <br /> 12<br /> <br /> 28<br /> <br /> 36<br /> <br /> 708<br /> <br /> 3<br /> <br /> 4<br /> <br /> 1<br /> <br /> 7<br /> <br /> 12<br /> <br /> 10<br /> <br /> 4<br /> <br /> 28<br /> <br /> 4<br /> <br /> 48<br /> <br /> 40<br /> <br /> 100<br /> <br /> 1044<br /> <br /> 4<br /> <br /> 4<br /> <br /> 4<br /> <br /> 14<br /> <br /> 9<br /> <br /> 3<br /> <br /> 16<br /> <br /> 56<br /> <br /> 24<br /> <br /> 36<br /> <br /> 12<br /> <br /> 80<br /> <br /> 944<br /> <br /> 5<br /> <br /> 2<br /> <br /> 8<br /> <br /> 15<br /> <br /> 3<br /> <br /> 2<br /> <br /> 32<br /> <br /> 60<br /> <br /> 48<br /> <br /> 12<br /> <br /> 8<br /> <br /> 36<br /> <br /> 688<br /> <br /> 2.1.2. Tối ưu hiệu năng dựa trên chuyển đổi mô hình<br /> i.<br /> <br /> Ý tưởng<br /> Ý tưởng cơ bản của phương pháp này như sau: phần mềm nhúng được thực thi<br /> <br /> Ý tưởng<br /> Ý tưởng của phương pháp tối ưu hiệu năng phần mềm nhúng trong giai đoạn thiết<br /> <br /> một sắp xếp Tô-pô trên đồ thị phụ thuộc; đánh giá và lựa chọn sắp xếp Tô-pô có dung<br /> lượng bộ nhớ chiếm dụng ít nhất.<br /> ii.<br /> <br /> Đồ thị phụ thuộc và sắp xếp Tô-pô<br /> Phần mềm nhúng có thể được đặc tả bằng một đồ thị tác vụ phụ thuộc. Mỗi tác vụ<br /> được định nghĩa như một hàm với tên, kiểu trả về và danh sách tham số. Các tác vụ có<br /> thể độc lập hoặc phụ thuộc lẫn nhau. Theo đó, chương trình có thể biểu diễn bằng đồ thị<br /> phụ thuộc G và được định nghĩa theo công thức (2.9).<br /> G = với U = {ui | i = 1..N}<br /> <br /> và<br /> <br /> V Í {vij = (ui, uj); i, j = 1..N}<br /> <br /> (2.9)<br /> <br /> Trong đó:<br /> <br /> kế dựa trên biến đổi mô hình là dựa vào các phép chuyển đổi trên mô hình để đưa mô<br /> <br /> -<br /> <br /> Mỗi đỉnh ui tương ứng với một tác vụ i<br /> <br /> hình thiết kế ban đầu về mô hình tối ưu.<br /> <br /> -<br /> <br /> Mỗi cạnh vij cho biết tác vụ j phụ thuộc vào tác vụ i và chỉ được thực hiện khi tác<br /> vụ i đã kết thúc.<br /> <br /> 7<br /> <br /> 8<br /> <br />