ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

VŨ VĂN PHÚC

NGHIÊN CỨU CÁC PHƢƠNG PHÁP ĐỂ GIẢM
THIỂU NĂNG LƢỢNG TRONG PHÁT TRIỂN
HỆ THỐNG NHÚNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

VŨ VĂN PHÚC
NGHIÊN CỨU CÁC PHƢƠNG PHÁP ĐỂ GIẢM
THIỂU NĂNG LƢỢNG TRONG PHÁT TRIỂN
HỆ THỐNG NHÚNG
Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC:
PGS.TS. NGUYỄN NGỌC BÌNH

Hà Nội – 2014


góp cho tôi những ý kiến quý báu và chia sẻ những kinh nghiệm hay cho tôi
trong mỗi buổi seminar hàng tuần.
Tôi xin được gửi lời cảm ơn đến các tác giả, nhóm tác giả của những
giáo trình, những công trình khoa học và những bài báo khoa học mà tôi tham
khảo để hoàn thiện luận văn này.


3
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ..............................
DANH MỤC CÁC BẢNG ...................................................................
DANH MỤC CÁC HÌNH VẼ .............................................................
DANH MỤC CÁC KÝ PHÁP.............................................................
MỞ ĐẦU ...............................................................................................
CHƢƠNG 1. TỔNG QUAN..............................................................

1.1
Giới thiệu về hệ thống nhú
1.1.1
Hệ thống nhúng ...............
1.1.2
Phần mềm nhúng .............
1.1.3Hệ thống nhúng thời gian thực ......................................................
1.2
Đặc điểm khác biệt giữa p
thường ..........................................................................................................
1.3
Ứng dụng của hệ nhúng ...
1.4
Xu hướng phát triển của cá

Tối ưu năng lượng bằng p
2.5Một số hướng tiếp cận tối ưu dựa trên lập lịch lệnh hợp ngữ ..........
2.5.1
Ước lượng điện năng của
2.5.2
Sinh mã năng lượng thấp
2.5.3
Thuật toán lập lịch danh s
2.5.4
Giảm thiểu chuyển mạch
2.5.5
Bài toán người đưa hàng á
2.5.6
Lập lịch đàn hồi cho điện
2.5.7
Lập lịch để giảm điện năn
2.5.8
Lập lịch kết hợp 2 mục tiê
2.5.9
Thuật toán lập lịch tới hạn
năng
31
2.5.10
Thuật toán tối ưu bầy đàn
2.6
Một số hướng tiếp cận tối ưu dựa trên tru
2.6.1
Giảm thiểu truy cập bộ nhớ ..................
2.6.2
Cấp phát thanh ghi bằng tô màu đồ thị

5

4.3.1 Tạo bộ chương trình thực nghiệ
4.3.2 Dịch ngược từ mã thực thi sang
4.3.3 Thực hiện chương trình tìm cấu
4.3.4 Thực thi mô phỏng trong Sim-Wattch để ước lượng năng lượng . 47
4.4Đánh giá kết quả thực nghiệm ..........................................................
4.5So sánh kết quả thực nghiệm với phương pháp khác ......................
CHƢƠNG 5. KẾT LUẬN..................................................................
Kết quả đạt được .........................................................................................
Hạn chế và vấn đềchưa giai quyết..............................................................
̉̉

Hướng phát triển .........................................................................................
TÀI LIỆU THAM KHẢO .................................................................
PHỤ LỤC A. MỘT SỐ LỆNH THỰC THI ....................................

A.1. Yêu cầu chuẩn bị môi trường ..............................................................
1.
Platform .........................................................
2. Bộ mã nguồn để tạo chuỗi công cụ phát triển chéo ............................
a.
Cài đặt Simplesim .........................................
b.
Cài đặt Simpleutils-990811 ...........................
c. Cài đặt GCC Cross-Compiler cho kiến trúc SimpleScalar .................
A.2. Công cụ mô phỏng điện năng Sim-Wattch .........................................
PHỤ LỤC B. MỘT SỐ CHƢƠNG TRÌNH DÙNG MÔ PHỎNG 63
PHỤ LỤC C. MỘT SỐ CÔNG TRÌNH KHOA HỌC LIÊN QUAN
..............................................................................................................78

DANH MỤC CÁC HÌNH VẼ
Hình 1. Lập lịch danh sách để giảm thiểu năng lượng....................................30
Hình 2. Tổ chức ba cấp độ của bộ nhớ cache.................................................33
Hình 3. Mô hình tối ưu tổng thể......................................................................37
Hình 4. Chương trình phân tích và tạo cấu hình tối ưu...................................40
Hình 5. File hợp ngữ dịch ngược từ mã máy..................................................40
Hình 6. Cấu hình gốc ban đầu.........................................................................41
Hình 7. Cấu hình tối ưu...................................................................................41
Hình 8. Mô hình thực nghiệm.........................................................................43
Hình 9. Thư mục SimpleScalar.......................................................................45
Hình 10. Tiện ích mô phỏng............................................................................45
Hình 11. Biên dịch chéo file .c thành file thực thi..........................................45
Hình 12. Kết quả biên dịch chéo từ file .c sang file thực thi..........................46
Hình 13. Dịch ngược từ mã thực thi sang mã Assembly................................46
Hình 14. Kết quả dịch ngược sang file assembly............................................47
Hình 15. File cấu hình config1.cfg.................................................................48
Hình 16. Thực thi lệnh mô phỏng Sim-Wattch................................................48
Hình 17. Kết quả tiêu thụ điện năng thu được................................................49
Hình 18. Thực hiện Sim-Wattch để mô phỏng tiêu thụ năng lượng................50
Hình 19. Một phần kết quả tiêu thụ điện năng................................................50
Hình 20. Đánh giá điện năng tiêu thụ.............................................................51


Ký pháp
Ep
Bi
Oi,j
n
Ni
Ni,j

năng lượng tiêu thụ làm giảm được năng lượng tốt hơn, góp phần xây dựng
thêm một phương pháp, một hướng tiếp cận mới trong tối ưu năng lượng. Cấu
trúc luận văn gồm các phần sau:
Chương 1.Tổng quan.Trong chương này , chúng tôi hệ thống hóa , giới
thiệu một số khái niệm cơ bản về hệ thống nhúng, phần mềm nhúng, xu
hướng phát triển, khó khăn và thách thức, một số hướng tiếp cận tối ưu trong
hệ thống nhúng nhằm định hướng nghiên cứu cho phù hợp.
Chương 2.Các phương pháp giảm thiểu năng lượng.Trong chương
này, chúng tôi trình bày về tổng quan các phương pháp để giảm thiểu năng
lượng, khái niệm và mục đích của việc giảm thiểu năng lượng nói chung và
của hệ thống nhúng nói riêng, tổng hợp và hệ thống hóa lại các kết quả tối ưu
năng lượng trong hệ thống nhúng thời gian gần đây.
Chương 3.Phương pháp tối ưu điện năng tiêu thụ của hệ thống
nhúng dựa trên kỹ nghệ ngược và tái cấu hình.Nội dung chương này được
mô tả chi tiết phương pháp tối ưu điện năng, đưa ra mô hình tổng quát, giải
thích và triển khai phương pháp.
Chương 4.Thực nghiệm. Chương này sẽ mô tả công cụ được sử dụng
để mô phỏng, xây dựng mô hình thực nghiệm, từ các bài toán thông dụng sẽ
được thử nghiệm dựa trên công cụ và mô hình mô phỏng từ đó đưa ra sự so


10
sánh về các kết quả thực thi và chúng ta có thể đánh giá được sự tối ưu dựa
trên phương pháp mà chúng ta đang sử dụng.
Chương 5.Kết luận.Chương này tổng hơpc̣ , đánh giácác nội dung
nghiên cứu và thực nghiệm về phương pháp tối ưu đã trình bày trong các
chương trước. Trong mỗi giai đoạn, chúng tôi tóm lược về ý tưởng, triển khai
và đánh giá các phương pháp tối ưu cũng như các đóng góp chính của luận án
về lý thuyết và thực tiễn. Đồng thời, chúng tôi cũng trình bày các kết quả
nghiên cứu đã công bố trong các hội nghị, tạp chí về các phương pháp tối ưu.

ít.Công việc chủ yếu vẫn chỉ là gia công phần mềm cho nước ngoài. Bên cạnh
đó chúng ta còn đối mặt một số khó khăn thử thách như để đào tạo được một
chuyên viên có trình độ trong môi trường công nghệ cao đòi hỏi mất khoảng
thời gian ít nhất là 6 tháng đến 1 năm, để có được một sản phẩm nhúng đúng
nghĩa đòi hỏi phải có kiến thức cơ bản, chuyên sâu, giao tiếp chặt chẽ được
với khác hàng,... Như vậy, để chúng ta có thể phát triển được lĩnh vực nhúng
ở Việt Nam cần định hướng chiến lược và đầu tư hợp lý, đào tạo cơ bản và
chuyên sâu, đẩy mạnh nghiên cứu và phát triển cho ngành hệ thống nhúng
ngay từ các trường và các trung tâm, viện nghiên cứu.
1.1.1 Hệ thống nhúng
Hệ thống nhúng (Embedded system) là một hệ thống tiń h toán có khả
năng tự trị được nhúng vào trong một môi trường hay một hệ thống lớn hơn .
Đó là các hệ thống tích hợp cả phần cứng và phần mềm phục vụ các bài toán


12
chuyên dụng.Một hệ thống được nhúng có thể chứa nhiều hệ thống nhúng
khác.
Hệ thống nhúng thường được thiết kế để thực hiện một chức năng
chuyên biệt nào đó.Trong khi máy tính đa năng thực hiện được các chức năng
khác nhau thì hệ thống nhúng chỉ thực hiện một hoặc vài chức năng nhất
định.Hệ thống nhúng thường được thiết kế đi kèm với các yêu cầu cụ thể với
các thiết bị máy móc và phần cứng chuyên dụng.
1.1.2 Phần mềm nhúng
Phần mềm nhúng là phần mềm tích hợp trong các hệ thống
nhúng.Mục đích của phần mềm nhúng nhằm điều khiển phần cứng, cho phép
đáp ứng tương tác người dùng hoặc cung cấp môi trường để phát triển các
phần mềm nhúng tích hợp khác.
Phần mềm nhúng tạo nên phần hồn, phần trí tuệ của các sản phẩm
nhúng.Phần mềm nhúng ngày càng có tỷ lệ giá trị cao trong giá trị của các sản

kiện và đưa ra các kết quả cần thiết trong một ràng buộc thời gian cho trước.
Các ràng buộc thời gian bao gồm thời gian kết thúc hoặc cả thời gian bắt đầu
và kết thúc.
Hệ thời gian thực còn được gọi là hệ thống xác định bởi vì thời gian
đáp ứng cho một sự kiện được giới hạn.Các tác vụ đáp ứng cho sự kiện còn
được gắn với một độ ưu tiên cho trước.Hơn nữa, hệ thống thời gian thực có
khả năng khả chuyển kém khi thay đổi môi trường.
Phân loại hệ thống thời gian thực [29]:
Trong hệ thời gian thực, mọi công việc tính toán đều phải hoàn thành
trước thời gian cho phép (deadline), xác định và nhỏ nhất có thể chấp nhận
được gọi là deadline. Nói cách khác, hệ thống thời gian thực bị ràng buộc về
thời gian và được điều khiển bởi các deadline. Về mặt này, hệ thời gian thực
có thể được chia thành hệ thời gian thực mềm và hệ thời gian thực cứng.
 Hệ thống thời gian thực cứng: chỉ cho phép chênh lệch với deadline
trong một mức độ dao động gần như bằng không. Nếu không hoàn
thành đúng so với deadline thảm họa có thể xảy ra và không còn cách
nào có thể khôi phục được hệ thống, trong trường hợp đó có nghĩa là
toàn bộ hệ thống sẽ bị phá hủy. Ví dụ như lò phản ứng hạt nhân, hệ
thống nhúng trong điều khiển máy bay là hệ thời gian thực cứng, nếu
chậm quyết định có thể dẫn tới thảm họa.
 Hệ thống thời gian thực mềm: là khi hệ thống hoạt động với yêu cầu
thỏa mãn sự ràng buộc trong khung thời gian mềm. Nếu vi phạm và sai
lệch trong khoảng cho phép thì hệ thống vẫn có thể hoạt động và chấp
nhận được. Như vậy hệ thống thời gian thực mềm cho phép một mức
độ chênh lệch nhất định. Ví dụ đầu đọc DVD là hệ thời gian thực mềm
hay hệ thống phát thanh truyền hình, nếu thông tin truyền đi từ trạm


14
phát đến người nghe vài giây thì không ảnh hưởng đến tính thời sự của

 Nếu hệ thống nhúng sử dụng hệ điều hành, thì hầu như nó phải sử
dụng hệ điều hành thời gian thực. Giống như vi xử lý nhúng, hệ điều
hành


15
nhúng cũng có rất nhiều và có cách quản lý khác nhau. Tuy nhiên, mục
tiêu quan trọng là nó phải giải quyết các vấn đề khắt khe về mặt thời
gian và chia sẻ tài nguyên.
 Khó khăn khi xử lý lỗi phần mềm nhúng: Với phần mềm nhúng, việc
dò lỗi chương trình thường thông qua các bộ mô phỏng thiết bị.
 Hệ thống nhúng có ràng buộc về điện năng: Với nhiều hệ thống
nhúng, vấn đề năng lượng được coi là quan trọng hàng đầu. Phương
pháp đầu tiên để duy trì năng lượng là tắt bớt các phần hoặc cả hệ thống
khi có thể tắt được. Có thể là cả vi xử lý. Hầu hết các vi xử lý cho hệ
thống nhúng, có ít nhất một kiểu tiết kiệm năng lượng. Phần mềm
thường đặt vi xử lý trong những chế độ này với các chỉ thị đặc biệt hoặc
ghi một giá trị tới thanh ghi điều khiển bên trong vi xử lý.
 Hệ thống nhúng chạy trong môi trường có điều kiện khắt khe: Hệ
thống nhúng có mặt ở mọi nơi và có thể được thiết kế để làm mọi thứ.
Chính vì thế, khi thiết kế hệ thống, phải đặc biệt chú trọng tới các yếu
tố phần cứng có khả năng chịu được điều kiện môi trường.
1.3

Ứng dụng của hệ nhúng

Như đã trình bày ở trên, phần mềm nhúng có hầu hết trong các lĩnh vực
khác nhau của đời sống, xã hội như trong các sản phẩm truyền thông, các sản
phẩm điện tử tiêu dùng, các phương tiện vận chuyển, máy móc thiết bị y tế,
các thiết bị năng lượng, các thiết bị cảnh báo bảo vệ và các sản phẩm đo và

về thời gian thực, tiêu tốn ít năng lượng và hoạt động tin cậy ổn định
hơn.
 Các hệ nhúng ngày càng có độ mềm dẻo cao đáp ứng các yêu cầu
nhanh chóng đưa sản phẩm ra thị trường, có khả năng bảo trì từ xa, có
tính cá nhân cao.
 Các hệ nhúng ngày càng có khả năng hội thoại cao, có khả năng kết
nối mạng và hội thoại được với các đầu đo cơ cấu chấp hành và với
người sử dụng.
 Các hệ nhúng ngày càng có tính thích nghi, tự tổ chức cao có khả
năng tái cấu hình như một thực thể, một tác nhân.
 Các hệ nhúng ngày càng có khả năng tiếp nhận năng lượng từ nhiều
nguồn khác nhau (ánh sáng, rung động, điện từ trường, sinh học….) để
tạo nên các hệ thống tự tiếp nhận năng lượng trong quá trình hoạt động.
1.5

Những thách thức và các vấn đề còn tồn tại
Hệ thống nhúng hiện đại còn phải đối mặt với các vấn đề sau [2]:
 Độ phức tạp của sự liên kết đa ngành phối hợp cứng – mềm.
 Độ phức tạp của hệ thống tăng cao do nó có kết hợp nhiều lĩnh vực đa
ngành, kết hợp phần cứng – phần mềm, trong khi các phương pháp thiết
kế và kiểm tra chưa chín muồi. Khoảng cách giữa lý thuyết và thực
hành lớn và còn thiếu lý thuyết hoàn chỉnh cho khảo sát phân tích tính
toàn cục các hệ nhúng.


17
 Thiếu phương pháp phân tích tối ưu giữa các thành phần tạo nên hệ
nhúng bao gồm lý thuyết điều khiển tự động, thiết kế máy, công nghệ
phần mềm, điện tử, vi xử lý, các công việc hỗ trợ khác.
 Thách thức đối với độ tin cậy và tính mở hệ thống.

phân cấp bộ nhớ ẩn (cache) có thể có một hoặc nhiều lựa chọn kiến trúc bộ
nhớ. Cuối cùng, từ góc nhìn ràng buộc, người thiết kế hệ thống nhúng cần


18
đảm bảo không chỉ về mục tiêu hiệu năng mà còn về chi phí năng lượng, ràng
buộc thời gian thực. Hiệu năng hệ thống cần được xem xét không chỉ do tốc
độ CPU mà còn do việc nạp bus (đường truyền hệ thống) đến các đơn vị lưu
trữ mức mạch như bộ nhớ chính, ổ đĩa ngoài. Thậm chí cần xét cả bộ nhớ ẩn
L2 trong ngữ cảnh đa CPU. Nói tóm lại, bộ nhớ và hệ thống bus là nguyên
nhân dẫn đến chi phí chung của hệ thống tổng thể. Và do đó, người thiết kế hệ
thống cần cố gắng tối giản các yêu cầu bộ nhớ với mục đích giảm chi phí tổng
thể của hệ thống.
1.6.1 Tối ưu hiệu năng
Tối ưu hiệu năng bao hàm nhiều lĩnh vực và có ý nghĩa khác
nhau.Trong phát triển phần cứng có thể gồm tốc độ xử lý của CPU, tốc độ
truy xuất bộ nhớ. Trong phần mềm, hiệu năng có thể gồm: thời gian thực thi
ứng dụng, thời gian phân tích lỗi, thời gian biên dịch, …Ví dụ như trong các
hệ thống nhúng mức cao như ứng dụng Mobile trong môi trường phân tán,
thời gian thực thi ứng dụng bao gồm thời gian xử lý tại các nút tính toán và
thời gian truyền dữ liệu trong mạng. Khi kích thước dữ liệu truyền thông lớn,
sẽ ảnh hưởng nhiều đến tốc độ thực hiện. Do đó để cải tiến hiệu năng phần
mềm nhúng trong môi trường phân tán dựa trên kỹ thuật nén dữ liệu. Có rất
nhiều phương pháp được áp dụng như:
 Cải tiến hiệu năng mã nguồn: Do hạn chế về tốc độ CPU, bộ nhớ cũng
như các tài nguyên thực thi, việc cải tiến, tối ưu hiệu năng phần mềm
nhúng có ý nghĩa quan trọng. Dựa trên khía cạnh cải tiến hiệu năng, cải
tiến mã nguồn theo các khía cạnh sau.



Sử dụng biến toàn cục: Khi sử dụng các hàm trong chương

trình. Khi gọi hàm, các tham số, các biến cục bộ mới được cấp phát
bộ nhớ trong vùng ngăn xếp và được thu hồi khi hàm kết thúc.
Ngược lại, các biến toàn cục sẽ được cấp phát bộ nhớ ngay từ khi
chương trình được nạp vào bộ nhớ. Do đó việc sử dụng các biến
toàn cục thay thế cho các biến cục bộ cũng làm giảm thời gian thực
thi của chương trình. Tuy nhiên khi sử dụng các biến toàn cục có thể
phá vỡ tính mô-đun của chương trình và có thể không đảm bảo toàn
vẹn dữ liệu khi nhiều hàm cùng sử dụng biến toàn cục.



Thay thế vòng lặp: Trong nhiều trường hợp, các cấu trúc lặp có
thể được thay thế bằng các câu lệnh tuần tự cũng làm giảm thời gian
thực thi vì loại bỏ được thời gian quay lui của con trỏ lệnh, tiết kiệm
được thời gian kiểm tra điều kiện dừng và thời gian thay đổi giá trị
biến lặp.



Khử đệ quy: Việc sử dụng đệ quy trong chương trình làm việc
biểu diễn thuật toán và tổ chức chương trình tốt hơn nhưng lại làm
mất nhiều thời gian chuyển điều khiển chương trình (overhead). Bản
chất của đệ quy là quá trình gọi chương trình con nhiều lần nên việc
khử đệ quy cũng là một giải pháp tốt để cải tiến hiệu năng chương
trình.






Sử dụng lệnh goto: Sử dụng cấu trúc goto thường phá vỡ cấu
trúc chương trình và là kỹ thuật khuyến cáo không nên sử dụng
trong kỹ nghệ phần mềm. Tuy nhiên, trong lập trình phần mềm
nhúng, sử dụng goto có thể loại bỏ các cấu trúc phức tạp hoặc chia
sẻ các đoạn code lặp. Do đó sử dụng câu lệnh goto có thể giảm được
kích thước chương trình.
 Giảm kích thước bộ nhớ: Trong một số trường hợp, kích thước bộ nhớ
ROM và RAM hạn chế, việc giảm kích thước bộ nhớ sử dụng của phần
mềm nhúng là cần thiết. Để giảm kích thước bộ nhớ sử dụng, cần giảm
sự phụ thuộc vào dữ liệu toàn cục, vùng nhớ ngăn xếp, vùng nhớ heap.
Những kỹ thuật tối ưu bộ nhớ sử dụng thường do người lập trình thực
hiện sẽ tốt hơn chương trình dịch vì tổ chức và cấp phát bộ nhớ phụ
thuộc vào ngữ nghĩa của các thành phần trong chương trình như cấp
phát động, cấp phát tĩnh. Vì ROM thường chi phí thấp hơn RAM tính
theo mỗi byte nhớ nên một chiến lược để giảm dung lượng dữ liệu toàn
cục có thể được thực hiện bằng cách chuyển dữ liệu hằng vào ROM.
Điều này có thể được thực hiện tự động bởi chương trình dịch nếu khai
báo với từ khóa const. Hầu hết các trình biên dịch C đặt mọi dữ liệu
hằng toàn cục vào các đoạn dữ liệu đặc biệt như là các vùng có thể


21
được ghi cứng trên ROM. Kỹ thuật này có tác dụng khi sử dụng nhiều
dữ liệu hằng dạng chuỗi, bảng trong thời gian thực thi. Trong trường
hợp dữ liệu không thay đổi khi thực thi chương trình nhưng không cần
thiết phải là hằng, các đoạn dữ liệu hằng có thể được đặt vào bộ nhớ lai
như flash, EFROM.
1.6.2 Tối ưu năng lượng

22
nhúng. Ngoài ra, cũng cần kết hợp tối ưu kích thước cả phần cứng và phần
mềm.
1.6.4 Tối ưu chi phí
Đối với các hệ thống nhúng thông dụng, đặc biệt là đồ điện gia dụng,
sức cạnh tranh trên thị trường là một vấn đề cực kì quan trọng, do đó cần sử
dụng hiệu quả các thành phần phần cứng cũng như chi phí phát triển phần
mềm.
Tổng kết chƣơng 1
Chương 1 đã trình bày tổng quan về hệ thống nhúng, sự phát triển của
hệ thống nhúng, phần mềm nhúng. Trong chương này cũng tổng kết lại xu
hướng phát triển của hệ thống nhúng trong giai đoạn tiếp theo, bên cạnh đó
cũng đưa ra những thách thức và các vấn đề còn tồn đọng mà các hệ thống
nhúng gặp phải. Đồng thời , chúng tôi cũng tổng hợp một số hướng tiếp cận
trong tối ưu hê c̣thống nhúng. Trên cơ sởđó, chương này đa ̃cung cấp đươcc̣ bức
tranh tổng quát chung cho bài toán tối ưu hệ thống nhúng . Từ bức tranh tổng
quát này, chúng tôi sẽ tập trung nghiên cứu vào các phương pháp giảm thiểu
năng lươngc̣ trong Chương 2.