Khóa luận Phát triển, tối ưu thuật toán adaptive page layout trên thiết bị nhúng - Nguyễn Tài Tuệ

1  ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Tài Tuệ PHÁT TRIỂN, TỐI ƯU THUẬT TOÁN ADAPTIVE PAGE LAYOUT TRÊN THIẾT BỊ NHÚNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 2  ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Tài Tuệ PHÁT TRIỂN, TỐI ƯU THUẬT TOÁN ADAPTIVE PAGE LAYOUT TRÊN THIẾT BỊ NHÚNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS Nguyễn Việt Hà Cán bộ đồng hướng dẫn: Th.S Vũ Quang Dũng HÀ NỘI - 2010 1  Lời cảm ơn Tôi xin chân thành cảm ơn các thầy cô giáo trường Đại học Công Nghệ trong suốt bốn năm học vừa qua đã trang bị cho tôi nền tảng kiến thức quý báu, rất cần thiết cho việc hoàn thành khóa luận và làm việc sau này. Các thầy cô luôn là những tấm gương mẫu mực về tác phong nghiên cứu khoa học để tôi noi theo. Tôi muốn gửi lời cảm ơn sâu sắc tới PGS.TS Nguyễn Việt Hà, phó hiệu trưởng trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội, cùng Th.S Vũ Quang Dũng, giảng viên bộ môn Công nghệ phần mềm, trường Đại học Công Nghệ. Các thầy đã hết lòng chỉ bảo giúp đỡ tôi trong thời gian học tập tại trường cũng như trong suốt quá trình nghiên cứu hoàn thành khóa luận này. Xin gửi lời cảm ơn tới các thành viên phòng nghiên cứu Toshiba-Coltech đã nhiệt tình cộng tác và chia sẻ cùng tôi trong thời gian làm việc tại đây. Tôi xin gửi lời cảm ơn đến gia đình và bạn bè đã luôn động viên, giúp đỡ tôi trong lúc khó khăn và giúp đỡ tôi trong suốt quá trình học tập và thực hiện khóa luận. Mặc dù đã cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân,nhưng luận văn chắc chắn không tránh khỏi những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo. Một lần nữa xin gửi đến tất cả mọi người lời cảm ơn chân thành nhất. Hà Nội, 15 tháng 5 năm 2010 Sinh viên, Nguyễn Tài Tuệ i Tổng quan Ngày nay TBDĐ đang ngày một trở nên phổ biến bởi những tính năng ưu việt của chúng, tuy nhiên không giống như môi trường PC với màn hình hiển thị lớn và cấu hình mạnh mẽ, các TBDĐ có những hạn chế như màn hình hiển thị nhỏ và có rất nhiều kích thước với mục đích sử dụng khác nhau. Việc xây dựng một giao diện thông minh dành cho các TBDĐ luôn rất quan trọng, một ứng dụng với giao diện thông minh có thể sử dụng trên nhiều loại thiết bị khác nhau như điện thoại di dộng, TV hay thiết bị định hướng GPS của ôtô. Thuật toán Adaptive Page Layout [1] là một giải pháp để đưa ra cách sắp xếp màn hình hiệu quả cho các TBDĐ. Trong khóa luận này tôi sẽ hướng đến việc phát triển, tối ưu thuật toán APL về tốc độ xử lý, bộ nhớ sử dụng cũng như các yêu cầu về giao diện hiển thị khi chạy trên thiết bị nhúng sử dụng kiến trúc vi xử lý ARM. Các phương pháp tối ưu sẽ được kiểm chứng qua kết quả chương trình cài đặt thuật toán APL trên ARM. Đồng thời tôi cũng xây dựng ứng dụng minh họa Health Examination Visualization sử dụng APL như một mô đun để biểu diễn các dữ liệu kiểm tra sức khỏe một cách trực quan (theo yêu cầu bên phía Toshiba) trên ARM, qua đó có thể chứng minh khả năng ứng dụng vào thực tiễn thiết bị nhúng của thuật toán APL áp dụng các cải tiến của tôi. Trong khóa luận của tôi có sử dụng các kết quả tối ưu thuật toán APL trên PC đã được trình bày trong khóa luận của bạn Cao Bắc Tiến[2]. Dựa trên các đặc điểm của kiến trúc ARM tôi thực hiện tối ưu tốc độ tính toán khi cài đặt thuật toán APL trên ARM và các vấn đề về giao diện hiển thị hiển thị của chương trình. ii Abstract Mobile devices are becoming more and more popular because of their mobilty and wire- less technology. However mobile devices are not like a PC which has large screen and powerful capability, they have small screens with many sizes based on various targets. It is very impor- tant to construct an intelligent graphical user interfaces (GUIs) which can be constructed for one application and should be usable on different interactive devices, e.g cell phone, TV or GPS devices on car. Adaptive Page Layout [1] algorithm is a solution for constructing an ef- fective layout on mobile devices. In this thesis, we focus on optimizing the APL algorithm in computation speed, memory consumption and satisfying some requirements of GUIs on em- bedded system using ARM. The optimization methods will be proved by results of the program using APL on ARM. I also build Health Data Visualization Application using APL as a module to visualize health data (based on requirement of Toshiba) on ARM, the application denotes the ablity of my optimization methods on APL in embedded system. In my thesis, I use some results of optmizing APL on PC which are represented in Cao Bắc Tiến graduation thesis. Based on properites of ARM system, I improve APL computation speed and GUI of applications on ARM. iii Bảng từ viết tắt STT Từ hoặc cụm từ Từ viết tắt Chú thích 1 Adaptive Page Layout APL Dàn trang mang tính thích ứng 2 Personal Computer PC Máy tính cá nhân 3 Health Examination Data Visu- alization HEDV Hệ thống trực quan hóa dữ liệu kiểm tra sức khỏe 4 Thiết bị di động TBDĐ 5 Zoomable User Interface ZUI Giao diện người dùng hỗ trợ "zoom" 6 Floating Point Accelerator FPA Thành phần tăng tốc xử lý dấu phảy động 7 Vector Floating Points VFP Thành phần xử lý dấu phảy động 8 Graphical User Interface GUI Giao diện người dùng Bảng 1: Bảng từ viết tắt iv Mục lục 1 Mở đầu 2 2 Cơ sở lý thuyết 4 2.1 Thuật toán Squarified Treemap . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Treemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Squarified Treemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Kiến trúc ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 OpenGL|ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Bài toán đặt ra 10 3.1 Phát triển phần mềm cho ARM . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Các đặc điểm của kiến trúc xử lý ARM . . . . . . . . . . . . . . . . . 10 3.1.2 Xây dựng môi trường phát triển phần mềm cho ARM . . . . . . . . . . 11 3.2 Các yêu cầu về giao diện người dùng . . . . . . . . . . . . . . . . . . . . . . . 11 4 Giải pháp 12 4.1 Giải pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Xây dựng môi trường phát triển phần mềm cho ARM . . . . . . . . . . . . . . 12 v MỤC LỤC 4.3 Sử dụng dấu phẩy tĩnh thay thế cho dấu phẩy động . . . . . . . . . . . . . . . . 13 4.4 Tối ưu mã chương trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5 Demo, thực nghiệm 19 5.1 Thử nghiệm trên ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1.1 Cài đặt thuật toán APL . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.2 Health Data Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2.1 Các bước phát triển hệ thống . . . . . . . . . . . . . . . . . . . . . . . 22 5.2.2 Kiến trúc chương trình . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2.3 Tiền xử lý dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2.4 Cài đặt mô đun dàn trang . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2.5 Một số hình ảnh về giao diện của chương trình . . . . . . . . . . . . . 25 5.2.6 Kết quả kiểm thử demo chương trình . . . . . . . . . . . . . . . . . . . 25 6 Kết luận và hướng phát triển 27 6.1 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.2 Một số hướng phát triển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 A Phụ lục 29 A.1 Demo chương trình hiển thị ảnh . . . . . . . . . . . . . . . . . . . . . . . . . 29 A.2 Phiên bản HEDV chúng tôi phát triển trên nền tảng ARM . . . . . . . . . . . . 29 Tài liệu tham khảo 34 vi Danh sách hình vẽ 2.1 Biểu đồ cây và treemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Các trạng thái của vi xử lý kiến trúc ARM . . . . . . . . . . . . . . . . . . . . 7 2.3 Biểu đồ sử dụng điện năng của các thành phần trong TBDĐ . . . . . . . . . . . 8 4.1 Giao diện WideStudio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Biểu diễn dấu phẩy tĩnh và dấu phẩy động . . . . . . . . . . . . . . . . . . . . 14 5.1 Thử nghiệm thuật toán APL chưa tối ưu . . . . . . . . . . . . . . . . . . . . . 20 5.2 Thử nghiệm thuật toán APL sau khi tối ưu . . . . . . . . . . . . . . . . . . . . 20 5.3 Kết quả tối ưu về hiển thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.4 Đồ thị thể hiện sự tối ưu về tốc độ . . . . . . . . . . . . . . . . . . . . . . . . 24 A.1 Giao diện demo chương trình hiển thị ảnh . . . . . . . . . . . . . . . . . . . . 30 A.2 Demo HEDV phiên bản trên ARM với các mục được chia theo treemap . . . . 31 A.3 Demo HEDV phiên bản trên ARM với các mục được chia theo đường chéo . . . 32 A.4 Thanh công cụ tùy chỉnh hiển thị dữ liệu . . . . . . . . . . . . . . . . . . . . . 33 vii Danh sách bảng 1 Bảng từ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 2.1 SDRAM tiết kiệm năng lượng . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.1 Kết quả test trên ARM về diện tích che phủ(%) . . . . . . . . . . . . . . . . . 22 5.2 Kết quả thực hiện thuật toán APL (trước và sau khi tối ưu) trên ARM . . . . . . 23 5.3 Kết quả kiểm thử demo chương trình . . . . . . . . . . . . . . . . . . . . . . . 26 1 CHƯƠNG 1 Mở đầu Xây dựng dàn trang cho TBDĐ là một vấn đề có cốt yếu trong việc đưa ra một giao diện thông minh với khả năng hỗ trợ người dung cao . Các kỹ thuật sắp xếp giao diện cho TBDĐ hiện nay có rât nhiều hạn về mặt tốc độ cũng như hiệu quả hiển thị. Sự khác biệt về màn hình hiển thị, cấu hình và mục đích sử dụng của các TBDĐ cũng yêu cầu dữ liệu được biểu diễn rất khác nhau. Vì thế hiện nay nhiều thuật toán về dàn trang (page layout) đã được nghiên cứu và phát triển như Layout Manga Algorithm [3] , VIPS (Vision-based Page Segmentation Algorithm) [4], hay Web Page Layout [5]... Nhưng hầu hết các thuật toán này đều được ứng dụng cho nền tảng PC, không thực sự đáp ứng được các yêu cầu khi chuyển đổi và cài trên thiết bị nhúng (như giới hạn về khả năng xử lý, bộ nhớ và màn hình hiển thị...). Trong luận văn này, tôi sẽ chọn thuật toán APL (cho các hình khối có thứ tự) và tiến hành các bước tối ưu để giải quyết bài toán về dàn trang trên TBDĐ. Tôi hi vọng cách tiếp cận và giải quyết bài toán được đưa ra trong khóa luận này sẽ mang lại những ý nghĩa tích cực trong thực tiễn. Ngoài phần mở đầu, bố cục của khóa luận gồm bốn chương tiếp theo: • Chương 2: Trình bày các cơ sở lý thuyết mà tôi sử dụng trong việc giải quyết bài toán của mình. • Chương 3: Trình bày cụ thể những yêu cầu mà bài toán đặt ra. • Chương 4: Trình bày giải pháp đề giải quyết bài toán nêu ở chương 3. 2 CHƯƠNG 1: MỞ ĐẦU • Chương 5: Trình bày các demo, kết quả thực nghiệm đồng thời đánh giá hiệu suất cũng như ý nghĩa thực tiễn. • Chương 6: Kết luận và nêu một số hướng phát triển trong tương lai. 3 CHƯƠNG 2 Cơ sở lý thuyết Trong khuôn khổ vấn đề đã nêu ở phần giới thiệu tôi cần quan tâm đến thuật toán Adaptive Page Layout (dàn trang mang tính thích ứng) [1], thuật toán về trực quan hóa dữ liệu Squarified Treemap [6], các cơ sở và đặc điểm về kiến trúc ARM và thư viện đồ họa OpenGL|ES. Tôi đã sử dụng các kết quả nghiên cứu được trình bày trong khóa luận của bạn Cao Bắc Tiến [2] về thuật toán APL trên PC. 2.1 Thuật toán Squarified Treemap Thuật toán Squarified Treemap [6] là thành phần khá quan trọng trong việc xây dựng demo Health Examination Data Visualization của chúng tôi. Squarified Treemap được phát triển dựa trên treemap. 2.1.1 Treemap Treemap là một dạng biểu diễn cấu trúc dữ liệu có thứ bậc thay thế cho biểu đồ cây. Mỗi hình chữ nhật trong treemap biểu diễn một lá của biểu đồ cây. Và việc chia các hình chữ nhật theo chiều thẳng đứng hoặc chiều ngang thể hiện các lá cùng cấp hay không (Ví dụ: Các lá trên cùng một cấp sẽ được chia theo cùng chiều thẳng đứng hoặc cùng chiều dọc). Và cỡ của mỗi 4 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT hình chữ nhật trong treemap thể hiện cỡ của các lá tương ứng trong biểu đồ cây. Biểu đồ 2.1 thể hiện sự tương ứng giữa biểu đồ cây và treemap. Về mặt ý tưởng một thuật toán treemap sẽ tạo cho mỗi hình chữ nhật một tỉ lệ tương ứng với nó dựa theo đặc điểm dữ liệu của từng hình mà nó biểu diễn sau đó dựa theo các thỉ lệ này sẽ đưa ra một khung hình sắp xếp hù hợp. (a) Biểu đồ cây (b) Biểu diễn theo treemap Hình 2.1: Biểu đồ cây và treemap 2.1.2 Squarified Treemap Thuật toán Squarified Treemap là một trong các thuật toán xây dựng treemap hiệu quả. Squarified Treemap nhằm mục đích cải thiện tính trực quan trong biểu diễn treemaps bằng cách đưa các khối hình chữ nhật trong biểu diễn treemap về các khối hình gần với hình vuông hơn. Điều này sẽ giúp không gian hiển thị được hiệu quả hơn, dễ so sánh cỡ của các khối hình hơn, đồng thời, độ chính xác của việc biểu diễn cũng được cải thiện hơn. Tư tưởng Squarified Treemap được thể hiện qua đoạn mã sau: void s q u a r i f y ( l i s t c h i l d r e n , l i s t row , r e a l w){ r e a l c = head ( c h i l d r e n ) ; i f ( wo r s t ( row , w) <= wor s t ( row++[ c ] , w) s q u a r i f y ( t a i l ( c h i l d r e n ) , row++[ c ] , w ) ; e l s e { l ayou t r ow ( row ) ; s q u a r i f y ( c h i l d r e n , [ ] , w id th ( ) ) ; } } 5 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Với R là danh sách các diện tích cho trước và s là tổng diện tích thì hàm worst được định nghĩa bởi công thức 4: worst(R,w) = max r∈R (max(w2r/s2, s2/(w2r)))(4) width là hàm chỉ ra độ dài của cạnh nhỏ nhất của hình chữ nhật con trong hàng, layoutrow() thêm một hàng con vào hình chữ nhật. Đầu vào của thuật toán Squarify Treemap là danh sách diện tích các hình chữ nhật con cần đưa ra dàn trang. Danh sách row bao gồm các hình chữ nhật sẽ đước sắp. Theo đoạn mã trên một hình chữ nhật con sẽ được lấy ra từ đầu vào (list children) sau đó sẽ so sánh điểm qua hàm đánh giá worst() rồi tiếp tục đưa ra dàn trang mới. 2.2 Kiến trúc ARM Ứng dụng cho các hệ thống nhúng hiện nay ngày càng trở nên phức tạp, không phải đơn giản chỉ là điều khiển một chốt đèn giao thông định thời, đếm số người ra vào cửa, điều khiển động cơ ON-OFF, hiển thị một câu thông báo trên LCD, theo xu thế tất yếu các nhân điều khiển cần có cấu hình mạnh hơn, đáp ứng thời gian thực tốt hơn các nhân điều khiển 8bit đang dùng. Chính sự hạn chế về dung lượng bộ nhớ chương trình-dữ liệu cũng đã ảnh hưởng không ít tới phạm vi ứng dụng của hệ chip vi điều khiển 8bit. Vi điều khiển 8bit gặp phải rất nhiều vấn đề về tính toán số thực, cài đặt thuật toán phức tạp. Các kết quả thu được từ vi điều khiển 8bit ấy luôn bị hạn chế khi ta ứng dụng vào công nghệ cao: truyền thông đa phương tiện, xử lý âm thanh, hình ảnh, các thiết bị hỗ trợ cá nhân , các ứng dụng trong mobile robot linh hoạt, tự hành và ‘biết ứng xử’. Từ những đánh giá trên hệ thống hiện tại cần một kiến trúc vi xử lý đủ mạnh, đáp ứng được tốt về mặt tương tác giao diện người dùng. Do đó trong khóa luận này chúng tôi tập trung vào nghiên cứu phát triển phần mềm chạy trên hệ thống sử dụng hệ vi xử lý ARM 32 bit. Kiến trúc ARM là thành phần quan trọng của nhiều hệ thống nhúng 32-bit đã rất thành công và được sử dụng rộng rãi trong TBDĐ, theo eeglossary [? ] 75% các bộ vi xử lý của các thiết bị nhúng trên thị trường hiện nay sử dụng vi xử lý kiến trúc ARM. Kiến trúc cũng như cách xử lý của ARM có sự khác biệt đối với máy tính cá nhân, điều đó dẫn đến nảy sinh một số khác biệt 6 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT trong việc lập trình trên nền tảng ARM và PC. ARM sử dụng cấu trúc RISC thay vì CISC như PC. RISC tập trung chú ý vào việc giảm tính phức tạp của các chỉ dẫn được thi hành bởi phần cứng bởi vì cung cấp tính mềm dẻo và thông minh trong phần mềm dễ dàng hơn trong phần cứng. Như một hệ quả, thiết kế RISC đặt nhiều yêu cầu đối với trình dịch hơn. Hệ vi xử lý ARM được sử dụng rộng rãi trong các thiết bị di động bởi khả năng tiết kiệm năng lượng của nó. Cơ chế hoạt động linh hoạt của ARM được thể hiện trong hình 2.2, hệ vi xử lý ARM có nhiều trạng thái hoạt động thích hợp với các tác vụ mà CPU phải thực hiện. Trạng thái RUN là khi CPU Hình 2.2: Các trạng thái của vi xử lý kiến trúc ARM đang thực hiện tác vụ, IDLE là trạng thái CPU khi không thực hiện tác vụ nào và chờ thực hiện tác vụ tiếp theo, SUSPEND là khi CPU ngừng hoạt động nhưng lưu các tác vụ đang thực hiện, OFF là trạng thái khi CPU ngừng hoạt động, việc quản lý lính hoạt giữa các trạng thái này giúp tiết kiệm năng lượng tối đa trên hệ thống sử dụng kiến trúc vi xử lý ARM. Hệ thống sử dụng kiến trúc vi xử lý ARM sử dụng SDRAM 2.5V tiết kiệm năng lượng hơn rất nhiều so với loại SDRAM 3.3V thông thường (theo bang. Theo biểu đồ 2.3 [7] chi tiết việc tiêu thụ điện năng Bảng 2.1: SDRAM tiết kiệm năng lượng Loại RAM Điện năng khi chạy(mW) Điện năng khi Suspend(mW) Loại bình thường(3.3V) 891 9.9 Tiết kiệm năng lượng(2.5V) 324 1.2 7 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT của các thành phần trên TBDĐ bình thường sử dụng kiến trúc vi xử lý ARM dành đến 46.5 % năng lượng để dành cho việc hiển thị trên màn hình, do đó việc xây dựng giao diện chương trình chạy trên kiến trúc vi xử lý ARM rất quan trọng đối với việc hoạt động tiết kiệm điện năng của TBDĐ. Các kiến trúc vi xử lý ARM từ ARM7 trở lên có hỗ trợ tính toán với dấu phẩy động sử Hình 2.3: Biểu đồ sử dụng điện năng của các thành phần trong TBDĐ dụng Floating Point Accelerator (FPA) và phần cứng Vector Floating Point accelerator (VFP), tuy nhiên việc tính toán bằng dấu phẩy động tiêu tốn nhiều năng lượng và tốc độ chậm hơn rất nhiều so với dấu phẩy tĩnh, khi đó trình biên dịch C sẽ phải xử lý các tính toán sử dụng dấu phẩy động thay thế bằng nhiều phép toán số học, điều này đòi hỏi nhiều thời gian và năng lượng hơn các phép toán số học thông thường. 8 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 2.3 OpenGL|ES OpenGL|ES [8] cung cấp các giao diện lập trình cho các chương trình ứng dụng đồ họa 2D-3D trên các hệ thống nhúng. Các giao diện lập trình này cho phép chương trình đồ họa giao tiếp với phần cứng dễ dàng hơn với các tính năng ưu việt tương tự như của OpenGL, tuy nhiên thư viện đồ họa OpenGLES đã được rút gọn đi để thích hợp hơn cho việc phát triển phần mềm trên thiết bị nhúng. OpenGL|ES hỗ trợ các kiến trúc vi xử lý ARM (từ ARM7 trở lên) đồng thời thư viện này cũng cho phép thực hiện các phép toán sử dụng dấu phảy tĩnh do đó các ứng dụng phát triển cho ARM có thể sử dụng các giao diện lập trình phong phú từ thư viện này. 9 CHƯƠNG 3 Bài toán đặt ra Mục tiêu bài toán là giải quyết vấn đề hiển thị và tương tác người dùng trên TBDĐ, bởi vậy, ngoài những yêu cầu về giao diện thì có những yêu cầu đặt ra đặc trưng bởi nền tảng thiết bị nhúng. Có thể nói, bài toán bao gồm hai vấn đề lớn: (1) tốc độ xử lý và (2) các yêu cầu về giao diện người dùng. Nội dung khóa luận tập trung vào phát triển tối ưu thuật toán cho ARM do đó các bài toán đặt ra ở đây sẽ dựa trên đặc điểm của kiến trúc ARM. 3.1 Phát triển phần mềm cho ARM 3.1.1 Các đặc điểm của kiến trúc xử lý ARM Các hệ sử dụng kiến trúc xử lý ARM từ ARM7 trở lên được cài đặt phần cứng hỗ trợ tính toán dấu phảy động (FPA và VFP) tuy nhiên việc tính toán dấu phảy động chậm hơn rất nhiều so với dấu phảy tĩnh bởi phải qua FPA. Bên cạnh đó các phép toán với số thực cũng mất chi phí tính toán rất cao. Bởi vậy, cần có giải pháp xử lý các phép tính toán với số thực và chuyển từ dấu phảy động qua dấu phảy tĩnh sử dụng trong APL để thuật toán có thể thực hiện chính xác và đảm bảo hiệu năng xử lý trên ARM. Đặc điểm của kiến trúc ARM yêu cầu các kỹ thuật lập trình phù hợp. 10 CHƯƠNG 3: BÀI TOÁN ĐẶT RA 3.1.2 Xây dựng môi trường phát triển phần mềm cho ARM Đối với máy sử dụng kiến trúc vi xử lý ARM có bộ nhớ và tốc độ tương đối nhỏ, việc phát triển phần mềm và xây dựng trực tiếp trên chúng (hoặc trên giả lập) là rất khó khăn do đó đòi hỏi phải xây dựng một môi trường phát triển phần mềm phù hợp và hiệu quả cho các máy này. Các mô đun cần tích hợp trong biểu diễn dữ liệu trực quan như Treemap [6] được cài đặt rất phức tạp, yêu cầu tính toán với các số tương đối lớn nên việc chuyển đổi, tối ưu mã nguồn của chúng để đưa lên ARM là rất khó khăn. Các thư viện đồ họa hỗ trợ ARM còn rất hạn chế nên việc chọn ra các thư viện đồ họa thích hợp đáp ứng được yêu cầu về cả mặt giao diện lẫn tốc độ xử lý là một vấn đề lớn. 3.2 Các yêu cầu về giao diện người dùng Việc chuyển đổi các mô đun treemap, cũng như mô phỏng dữ liệu thông qua thuật toán APL lên trên thết bị nhúng đặt ra một yêu cầu cần phải đảm bảo tính sử dụng đối với người sử dụng. Giao diện đạt được của chương trình phải có khả năng thích ứng linh hoạt với nhiều kích cỡ màn hình và đưa ra một cách biểu diễn dữ liệu trực quan, linh hoạt. Việc cài đặt thuật toán sử dụng WideStudio là một trong những yêu cầu từ phía Toshiba đối với nhóm phát triển. 11 CHƯƠNG 4 Giải pháp 4.1 Giải pháp Tại chương này chúng tôi xin trình bày việc xây dựng môi trường phát triển phần mềm cho ARM và cài đặt tối ưu thuật toán APL khi đưa lên máy sử dụng kiến trúc vi xử lý ARM. Tôi tập trung vào việc tối ưu về mặt tốc độ của thuật toán khi chạy trên ARM và xây dựng giao diện chương trình phù hợp với thiết bị nhúng trên ARM. 4.2 Xây dựng môi trường phát triển phần mềm cho ARM Để khắc phục việc xây dựng trực tiếp trên thiết bị giới hạn về mặt phần cứng ta sẽ xây dựng môi trường phát triển trên PC sau đó cross-compile để đưa phần mềm qua TBDĐ để chạy. Yêu cầu thiết bị di động và máy chủ PC phải cùng sử dụng Debian GNU/Linux, giao diện xây dựng trên thiết bị sử dụng thư viện đồ họa là X11, OpenGLES. Công cụ phát triển sẽ sử dụng là WideStudio và GNU ToolChain cho ARM, hình 4.1 thể hiện giao diện lập trình của công cụ WideStudio cho hệ thống nhúng. Việc sử dụng WideStudio và Debian có thể tận dụng hệ thống thư viện hỗ trợ ARM phong phú cho Debian và các thư viện đồ họa được tích hợp trong WideStudio. Bên cạnh đó các thư viện và công cụ phát triển đều là miễn phí do đó việc lập trình 12 CHƯƠNG 4: GIẢI PHÁP và đưa ứng dụng vào thực tế sẽ gặp nhiều thuận lợi hơn. Hình 4.1: Giao diện WideStudio 4.3 Sử dụng dấu phẩy tĩnh thay thế cho dấu phẩy động Vì kiến trúc vi xử lý ARM9 hỗ trợ tính toán dấu phẩy tĩnh tốt hơn dấu phẩy động rất nhiều (tăng tốc độ phép toán) do đó các phép toán sử dụng dấu phẩy động phải thay thế bằng dấu phẩy tĩnh. Phép toán sử dụng dấu phảy động sẽ phải sử dụng mô đun FPA tốc độ của mô đun này chậm hơn 10 lần so với mô đun xử lý số nguyên. Biểu diễn của các số sử dụng dấu phẩy động và sử dụng dấu phẩy tĩnh theo hình 4.1 Tôi sẽ sử dụng 1 số nguyên 32 bit để biểu diễn một số dấu phẩy tĩnh với 16 đầu lưu phần nguyên và 16 bit cuối lưu phần thực. Do đó giới hạn của việc biểu diễn bằng giấu phẩy tĩnh sẽ là từ 231. Việc thay thế dấu phẩy động bằng dấu phẩy tĩnh được thực hiện qua các phần: xử lý dữ liệu đầu vào, các hằng số chuyển từ dấu phẩy động sang dấu 13 CHƯƠNG 4: GIẢI PHÁP Hình 4.2: Biểu diễn dấu phẩy tĩnh và dấu phẩy động phẩy tĩnh, thay thế các toán tử bình thường bằng các toán tử sử dấu phẩy động. Xử lý dữ liệu và các hằng số Thay thế các số dấu phẩy động bằng các số sử dụng dấu phẩy tĩnh sử dụng hàm Fixed- FromFloat(float value) và FixedFromInt(int a) theo mã chương trình dưới đây i n l i n e i n t F ixedFromIn t ( i n t a ) { re turn ( a << 1 6 ) ; } i n l i n e i n t F ixedFromFloa t ( f l o a t va l u e ) { re turn ( i n t ) ( v a l u e ∗ (1 < <16) ) ;} Việc biểu diễn việc chuyển từ số nguyên và số thực có dấu phảy động sang số có dấu phảy tĩnh, với số nguyên ta thực hiện phép dịch 16 bit thì khi đó 16 bit đầu sẽ để biểu diễn phần nguyên conf 16 bit sau biểu diễn phần thực. Với số thực vì dùng 16 bít để lưu phần nguyên nên giá trị tuyệt đối của số thực sẽ bị giới hạn < 215 các số nằm ngoài giới hạn sẽ được nhận các giá trị là giới hạn 231 − 1 và 231 của dấu phảy tĩnh, ta nhân với hằng số 65536 (1 « 6) để thu được số sử dụng dấu phảy tĩnh 16 bit biểu diễn phần nguyên và 16 bit biểu diễn phần thực. 14 CHƯƠNG 4: GIẢI PHÁP Thay thế các phép toán Các phép toán với số thực sẽ được thay thế bằng các phép toán với số nguyên kết, do đó có thể làm tăng tốc độ tính toán đáng kể khi đưa chương trình lên ARM (khi chạy trên ARM không cần sử dụng đến FPA và VFP). Phép nhân được thay thế bằng hàm Mul(int a, int b) mã chương trình của hàm Mul(int a, int b) được trình bày dưới đây: i n l i n e long Mul ( i n t a , i n t b ) { re turn ( ( a ∗b ) >> 1 6 ) ; } Việc nhân hai số có thể thực hiện bằng cách nhân hai số dấu phảy tĩnh bình thường sau đó dịch 16 bit để thu được kết quả có dạng dấu phẩy tĩnh như trình bày ở trên. Phép chia được thay thế bằng hàm Div(int a, int b), đây là mã chương trình của hàm Div(int a, int b) i n l i n e i n t Div ( i n t a , i n t b ) { i f ( ( b >> 24) && ( b >> 24) + 1) { re turn Mul ( a >> 8 , I n v e r s e ( b >> 8 ) ) ; } e l s e { re turn Mul ( a , I n v e r s e ( b ) ) ; } } Phép chia sẽ được thực hiện tương đương với việc thực hiện phép nhân Mul và phép nghịch đảo Inverse. Giá trị dưới dạng nghịch đảo sẽ thu được qua phép biến đổi Newton-Raphson (6) xn+1=(2 - A*xn)*xn (6) Tuy nhiên tập lệnh của ARM không cung cấp chỉ lệnh thực hiện việc chia số nguyên do đó phép chia được sử dụng hạn chế để làm tăng tốc độ tính toán. Phép exp sẽ được thực hiện thay thế bởi hàm FixedExp(int val), mã nguồn của hàm được trình bày dưới đây 15 CHƯƠNG 4: GIẢI PHÁP CFixed FixedExp ( CFixed v a l ) { CFixed r e s u l t = 0 ; CFixed tmp = ONE; i n t coun t = 1 ; whi le ( t rue ) { r e s u l t += tmp ; tmp = Div (Mul ( tmp , v a l ) , F ixedFromIn t ( coun t ) ) ; coun t ++; i f ( tmp == 0) break ; } re turn r e s u l t ; } Phép toán exp sẽ được tính sử dụng biến đổi Taylor theo công thức (5) ex = Σnk=0 xk k! +O(xn) (5) 4.4 Tối ưu mã chương trình Thực hiện các phép so sánh Tất cả các chỉ lệnh của hệ vi xử lý ARM đều có 4 bit gọi là các bit điều kiện, chỉ lệnh chỉ được thực hiện khi giá trị của tất các bit này đều là true. Vì vậy khi thực hiện nhiều phép so sánh được nhóm lại có thể loại trừ việc thực thi một số chỉ lệnh qua các bit điều kiện đó. Do đó khi lập trình tôi sẽ nhóm các phép so sánh lại thành một phép toán (nếu có thể) ví dụ (a > 0 & b > 0 & c < 0 & d < 0). Các phép so sánh này đã được nhóm lại sẽ được xử lý nhanh hơn. Các phép 16 CHƯƠNG 4: GIẢI PHÁP so sánh a > 0, b > 0, c < 0, d < 0 đã được nhóm lại qua đó tiết kiệm được thực hiện một số chỉ lệnh. Một điểm đặc biệt nữa khi thực hiện các phép so sánh là kiến trúc vi xử lý ARM sẽ thực hiện việc so sánh với 0 nhanh hơn so với các giá trị khác, khi thực hiện phép so sánh ARM sẽ thực thi chỉ lệnh CMP trong tập lệnh nếu đó là phép so sánh với 0 thì kiến trúc vi xử lý ARM sẽ bỏ qua không tiếp tục thực thi chỉ lệnh này đồng thời sẽ bật các cờ N hoặc Z, N là khi số so sánh âm, Z là khi số so sánh là 0. Qua đó việc so sánh sẽ thực hiện nhanh hơn so với các số thông thường. Ta có thể tiết kiệm thời gian tính toán bằng cách thực hiện việc so sánh với 0 khi có thể, ví dụ trong vòng lặp sau: f o r ( i = 0 ; i <= n ; i + + ) . . . . Có thể thay thế bằng đoạn mã sau: f o r ( i = n ; i >= 0 ; i − − ) . . . Thay vì thực hiện so sánh i với n tại mỗi vòng lặp, ta sẽ so sánh i với 0. Sử dụng kiểu dữ liệu kiến trúc vi xử lý ARM tính toán với kiểu dữ liệu unsigned nhanh hơn kiểu dữ liệu thông thường do đó khi có thể nên dùng kiểu dữ liệu unsigned, toàn bộ các dữ liệu đầu vào của thuật toán APL đều là số không âm do đó có thể hoàn toàn sử dụng kiểu dữ liệu unsigned khi xử lý dữ liệu đầu vào. Đối với các biến cục bộ hay khi truyền tham số tránh sử dụng các biến kiểu char hoặc short bởi khi khởi tạo các kiểu dữ liệu này biến cục bộ sẽ là 8 bit hoặc 16 bit, do đó thanh ghi phải dịch chuyển 24 hoặc 16 bit để thực hiện phép toán, điều này sẽ tốn thêm 1 hoặc 2 chỉ lệnh còn đối với kiểu dữ liệu int thanh ghi không phải thực hiện phép dịch này. Do đó toàn bộ biến cục bộ và tham biến trong mã nguồn chương trình đều sử dụng kiểu dữ liệu int hoặc unsigned int. 17 CHƯƠNG 4: GIẢI PHÁP Tối ưu hàm trong chương trình Số tham số của hàm cũng quyết định tới tốc độ xử lý của kiến trúc vi xử lý ARM. Các chỉ lệnh dùng để gọi hàm của ARM bao gồm 2 loại: • Các chỉ lệnh nhỏ BL, ... MOVE pc, lr thời gian thực hiện rất nhanh tuy nhiên chỉ gọi được các hàm có ít hơn 4 tham số. • Các chỉ lệnh LDM và TDM cần sử dụng stack để lưu các tham số khi gọi hàm tuy nhiên cho phép gọi hàm với nhiều tham số, thời gian thực hiện lâu hơn so với loại chỉ lệnh ở trên. Do đó các hàm trong chương trình cần được thiết kế với ít hơn 4 tham số để tận dụng các chỉ lệnh gọi hàm nhanh hơn. Sử dụng các hàm inline đối với các hàm có số câu lệnh ít ví dụ đối với hàm Mul(int a, int b) của phép nhân dấu phảy tĩnh ta sử dụng i n l i n e Mul ( i n t a , i n t b ) ; Sử dụng hàm inline cho giảm thời gian lưu mã vào thanh ghi đồng thời có thể giảm số lần thực hiện các chỉ lệnh ví dụ đối trong hàm inline khi thực hiện các chỉ lệnh ADD và MUL kiến trúc vi xử lý ARM sẽ thay thế bằng việc sử dụng chỉ lệnh MLA giúp tăng tốc thực hiện chương trình. 18 CHƯƠNG 5 Demo, thực nghiệm 5.1 Thử nghiệm trên ARM Tôi tiến hành thực hiện việc cài đặt thuật toán APL khi chưa tối ưu và sau khi đã tối ưu trên ARM. Chương trình được chạy trên board Amardillo9 sử dụng chip ARM920T, 200MHz, 64MB DRAM, hệ điều hành là Embedded Debian (Linux Kernel Version 2.6). Sạu đó tôi cài đặt chương trình mô hình hóa dữ liệu sức khỏe sử dụng thuật toán APL như một mô đun để biểu diễn dữ liệu. 5.1.1 Cài đặt thuật toán APL Dữ liệu đưa vào là file chứa chiều dài và chiều rộng của các hình khối, sử dụng thuật toán APL để đưa ra kết quả là danh sách các chiều dài chiều rộng mới. Các hình khối có thể được biểu diễn một cách đơn giản như các hình chữ nhật đơn giản được vẽ trên màn hình (sử dụng thư viện đồ họa X11), các hình khối được sắp xếp trên màn hình có thể thấy trên hình 5.1 và 5.2 (ứng với thử nghiệm thuật toán APL chưa tối ưu và tối ưu). Việc tối ưu không gian chết thử nghiệm trên ARM đạt được kết quả rất rõ rệt, kết quả tối ưu về không gian có thể thấy qua bảng 5.1 và đồ thị 5.3. Qua bản kết quả có thể thấy trung bình không 19 CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.1: Thử nghiệm thuật toán APL chưa tối ưu Hình 5.2: Thử nghiệm thuật toán APL sau khi tối ưu gian tối ưu được là 8%. Về tốc độ chạy của các thử nghiệm có thể thấy kết quả so sánh trong bảng 5.2. Qua bảng kết quả 5.2 ta thấy việc tối ưu trên ARM đã tăng tốc độ thực hiện thuật toán APL lên rất nhiều, đặc biệt là với số hình khối càng lớn, tốc độ xử lý được cải thiện gấp nhiều lần lần. Chênh lệch về tốc độ càng được thấy rõ qua đồ thị 5.*4 20 CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.3: Kết quả tối ưu về hiển thị 5.2 Health Data Visualization Ngoài việc tối ưu, phát triển APL, trong khóa luận này, tôi đã tiến hành phát triển một số ứng dụng có sử dụng thuật toán này. Một trong những ứng dụng đó là chương trình: Trực quan hóa dữ liệu kiểm tra sức khỏe (Health Examination Data Visualization - HEDV). HEDV là một trong những dự án của phòng thí nghiệm Toshiba - Coltech. Mục đích của HEDV là nhằm đưa ra mô hình trực quan nhất cho các số liệu kiểm tra sức khỏe, qua đó cho thấy cái nhìn tổng thể về tình hình sức khỏe của người sử dụng. Mục tiêu của dự án là có thể 21 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.1: Kết quả test trên ARM về diện tích che phủ(%) STT Số khối hình Diện tích trước khi tối ưu (%) Diện tích sau khi tối ưu (%) 1 4 63.6 70.59 2 5 41.54 56.39 3 6 74.82 82.97 4 7 74.13 85.12 5 8 71.04 76.05 6 9 77.59 82.43 7 10 83.69 87.98 8 15 84.39 90.66 9 20 85.67 90.41 10 25 83.48 89.34 11 30 83.72 90.23 12 35 85.48 91.06 13 40 84.5 91.76 14 45 83.23 88.06 15 50 88.04 92.75 16 55 86.77 92.3 17 60 84.12 90.44 18 65 84.22 90.16 19 70 85.28 91.24 triển khai HEDV trên cả PC và TBDĐ. Tôi thực hiện việc cài xây dựng chương trình HEDV trên board Armadillo với cấu hình đã nêu trong phần 5.1 Các giới hạn, ràng buộc • Hệ điều hành: Linux Debian • Phần cứng: Hỗ trợ chạy trên ARM. • Ngôn ngữ lập trình: C/C++ 5.2.1 Các bước phát triển hệ thống Hệ thống được phát triển qua các bước sau: 22 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.2: Kết quả thực hiện thuật toán APL (trước và sau khi tối ưu) trên ARM Số hình khối Thời gian tính toán sau khi tối ưu Thời gian tính toán sau khi chưa tối ưu 4 70 120 5 110 200 6 160 300 7 210 450 8 290 630 9 370 870 10 490 1160 15 1340 3540 20 2870 7980 25 5230 15080 30 8670 25500 35 13300 39940 40 19360 58800 45 27080 82800 50 36560 112660 55 48160 149020 60 62000 192480 65 78470 243700 70 97500 304040 - Phân tích cơ sở dữ liệu về sức khỏe, tiền xử lý dữ liệu. - Cài đặt thuật toán APL vào ứng dụng trực quan hóa dữ liệu sức khỏe trên ARM - Sử dụng môi trường đồ họa WideStudio để xây dựng giao diện đồ họa trên ARM. - Kiểm thử với các dữ liệu thực và xem xét thời gian chạy, bộ nhớ sử dụng với số bản ghi dữ liệu tăng lên. 5.2.2 Kiến trúc chương trình Thuật toán APL được cài đặt như một module và được sử dụng bởi hệ thống. Khi phát triển hệ thống HEDV, tôi có cài đặt sử dụng thêm thư viện ZUI đó là Cippolo được phát triển bởi các thành viên trong phòng thí nghiệm Toshiba-Coltech nhằm hỗ trợ người dùng trong việc "zoom" các dữ liệu. Và, cài đặt thuật toán Treemap để sinh ra cấu trúc treemap cho các mục trong mỗi hình chữ nhật. Giao diện đồ họa của chương trình được xây dựng bởi WideStudio sử 23 CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.4: Đồ thị thể hiện sự tối ưu về tốc độ dụng thư viện đồ họa OpenGL|ES để biểu diễn các hình khối cho phép tương tác và biểu diễn một cách linh hoạt. 5.2.3 Tiền xử lý dữ liệu Dữ liệu đầu vào của HEDV là các file cơ sở dữ liệu chứa dữ liệu về sức khỏe, các dữ liệu đó sẽ được tính toán để đưa về dạng hình khối chữ nhật, mỗi hình đại diện cho 1 bản ghi về sức khỏe (Cụ thể phương pháp tính toán được trinh bày trong phụ lục). Dữ liệu về chiều dài và chiều rộng các hình sau đó sẽ được chuyển sang dạng dấu phảy tĩnh bằng các phương pháp đã trình bày trong phần giải pháp. Sau đó dữ liệu này sẽ được sử dụng làm đầu vào cho module sử dụng thuật toán APL để thực hiện dàn trang. 24 CHƯƠNG 5: DEMO, THỰC NGHIỆM 5.2.4 Cài đặt mô đun dàn trang Thuật toán APL được cài đặt như một module và được sử dụng bởi hệ thống. Khi phát triển hệ thống HEDV, tôi có cài đặt sử dụng thêm thư viện ZUI đó là Cippollo (được phát triển bởi các thành viên trong phòng thí nghiệm Toshiba-Coltech) nhằm hỗ trợ người dùng trong việc "zoom" các dữ liệu. Tôi cài đặt thuật toán Treemap để sinh ra cấu trúc treemap cho các mục trong mỗi hình chữ nhật. Tất cả các module này khi đưa nên ARM đều được áp dụng các giải pháp tối ưu về mã nguồn tôi đã trình bày trong chương 4. Giao diện đồ họa của chương trình được xây dựng bởi WideStudio. Cũng cần nhấn mạnh rằng, thời gian để nhóm nghiên cứu làm quen với môi trường đồ họa này là khá ngắn, đồng thời cấu trúc của các module biểu diễn dữ liệu này là rất phức tạp do đó việc áp dụng các giải pháp tối ưu đã trình bày gặp rất nhiều khó khăn. 5.2.5 Một số hình ảnh về giao diện của chương trình 5.2.6 Kết quả kiểm thử demo chương trình Với môi trường tiến hành kiểm thử: Board Armadillo : ARM920T 200MHz, RAM 64 MB Hệ điều hành: Debian 2.6 Kết quả chương trình cho thấy bộ nhớ được sử dụng rất hiệu quả, số hình khối tăng lên cũng không ảnh hưởng nhiều đến việc sử dụng bộ nhớ dựa vào phương thức tải và hiển thị dữ liệu linh hoạt của WideStudio. 25 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.3: Kết quả kiểm thử demo chương trình STT Số bản ghi Thời gian (mili giây) Bộ nhớ (MB) 1 5 0 1.0 2 10 0 1.0 3 20 20 1.0 4 50 230 1.1 5 100 1540 1.2 6 150 5360 1.2 7 200 12470 1.2 8 250 26270 1.3 9 300 46230 1.3 10 350 76090 1.4 11 400 111230 1.4 12 450 162870 1.4 13 500 223160 1.4 26 CHƯƠNG 6 Kết luận và hướng phát triển 6.1 Kết luận Trong khóa luận này tôi đã trình bày các phương pháp tối ưu thuật toán APL để chạy trên ARM chuyển từ dấu phảy tĩnh sang dấu phảy động, các phép tính toán với số thực sang tính toán với số nguyên, các phương pháp tối ưu mã chương trình để chạy trên thiết bị ARM. Các bước cải tiến đó đã đạt được những thành quả đáng kể làm tăng tốc độ hoạt động của cài đặt thuật toán trên ARM. Đồng thời chương HEDV cài đặt trên hệ thống ARM cũng rất có giá trị về mặt ứng dụng. Chúng tôi cũng hi vọng các phương pháp tối ưu APL mà chúng tôi đề xuất cùng với những kết quả thực nghiệm có được sẽ tạo điều kiện cho những nhóm nghiên cứu quan tâm tới vấn đề này có cơ sở tiến hành so sánh, đánh giá và hoàn thiện phương pháp của mình. 6.2 Một số hướng phát triển Qua khóa luận này, cũng cho thấy việc tối ưu APL không những mang lại ý nghĩa quan trọng trong các bài toán về dàn trang trên TBDĐ mà còn có ý nghĩa đối với các bài toán về mô hình hóa dữ liệu. Trong tương lai, chúng tôi sẽ tiếp tục phát triển cải thiện tốc độ thuật toán, cải thiện giới hạn của số sử dụng dấu phảy tĩnh, đồng thời nghiên cứu mở rộng phát triển đối với 27 CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN các bài toán mô hình hóa dữ liệu trên nền tảng 3D. 28 PHỤ LỤC A Phụ lục A.1 Demo chương trình hiển thị ảnh Chương trình đơn thuần sử dụng APL và thư viện xử lý ảnh tích hợp trong bộ công cụ WideStudio cho phép đưa ra một dàn trang trên màn hình thiết bị nhúng để hiển thị các ảnh một cách phù hợp nhất. A.2 Phiên bảnHEDV chúng tôi phát triển trên nền tảng ARM Cửa sổ chính hiển thị danh sách các menu, các thành phần quản lý để tùy biến hiển thị của dữ liệu. Để nhập dữ liệu khám sức khỏe, người dùng sử dụng nút OpenFile. Người dùng có thể thay đổi tùy biến hiển thị bằng cách điều chỉnh qua thanh công cụ (hình A.4). 29 PHỤ LỤC A: PHỤ LỤC Hình A.1: Giao diện demo chương trình hiển thị ảnh 30 PHỤ LỤC A: PHỤ LỤC Hình A.2: Demo HEDV phiên bản trên ARM với các mục được chia theo treemap 31 PHỤ LỤC A: PHỤ LỤC Hình A.3: Demo HEDV phiên bản trên ARM với các mục được chia theo đường chéo 32 PHỤ LỤC A: PHỤ LỤC Hình A.4: Thanh công cụ tùy chỉnh hiển thị dữ liệu 33 Tài liệu tham khảo [1] Takashi MORIMOTO Xinxiao LI*, Yoshifumi TAKAYAMA. Adaptive page layout for ordered blocks. 2008. [2] Cao Bắc Tiến. Phát triển tối ưu thuật toán adaptive page layout trên pc. 2010. [3] A. Girgensohn S. Uchihashi, J. Foote and J. Boreczky. Video manga: Generating semanti- cally meaningful video summaries. ACM Press, 1999. [4] Ji-Rong Wen Wei-Ying Ma Deng Cai, Shipeng Yu. Vips: a vision-based page segmentation algorithm. Technical report, Microsoft Research - Microsoft Corporation, 2003. [5] David H. Salesin Charles Jacobs, Wilmot Li. Adaptive document layout via manifold con- tent. [6] Kees Huizing Mark Bruls and Jarke J. van Wijk. Squarified treemaps. 1999. [7] Cliff Brake. Power management in portable arm based systems. [8] OpenGL ES Common Profile Specification Version 2.0.24 (Full Specification). 2009. 34