ĐẠ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 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 Cán hướng dẫn: PGS.TS Nguyễn Việt Hà Cán đồng hướng dẫn: Th.S Vũ Quang Dũng HÀ NỘI - 2010 2      1    Lời cảm ơn Tôi xin chân thành cảm ơn thầy cô giáo trường Đại học Công Nghệ suốt bốn năm học vừa qua trang bị cho tảng kiến thức quý báu, cần thiết cho việc hồn thành khóa luận làm việc sau Các thầy cô gương mẫu mực tác phong nghiên cứu khoa học để 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, Th.S Vũ Quang Dũng, giảng viên 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 bảo giúp đỡ thời gian học tập trường suốt q trình nghiên cứu hồn thành khóa luận Xin gửi lời cảm ơn tới thành viên phịng nghiên cứu Toshiba-Coltech nhiệt tình cộng tác chia sẻ thời gian làm việc Tơi xin gửi lời cảm ơn đến gia đình bạn bè động viên, giúp đỡ lúc khó khăn giúp đỡ tơi suốt q trình học tập thực khóa luận Mặc dù cố gắng hoàn thành luận văn với tất nỗ lực thân,nhưng luận văn chắn khơng tránh khỏi thiếu sót, kính mong q thầy tận tình bảo Một lần xin gửi đến tất người lời cảm ơn chân thành Hà Nội, 15 tháng năm 2010 Sinh viên, Nguyễn Tài Tuệ i Tổng quan Ngày TBDĐ ngày trở nên phổ biến tính ưu việt chúng, nhiên không giống mơi trường PC với hình hiển thị lớn cấu hình mạnh mẽ, TBDĐ có hạn chế hình hiển thị nhỏ có nhiều kích thước với mục đích sử dụng khác Việc xây dựng giao diện thông minh dành cho TBDĐ quan trọng, ứng dụng với giao diện thơng minh sử dụng nhiều loại thiết bị khác điện thoại di dộng, TV hay thiết bị định hướng GPS ơtơ Thuật tốn Adaptive Page Layout [1] giải pháp để đưa cách xếp hình hiệu cho TBDĐ Trong khóa luận tơi hướng đến việc phát triển, tối ưu thuật toán APL tốc độ xử lý, nhớ sử dụng yêu cầu giao diện hiển thị chạy 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 kiểm chứng qua kết chương trình cài đặt thuật tốn APL ARM Đồng thời xây dựng ứng dụng minh họa Health Examination Visualization sử dụng APL mô đun để biểu diễn liệu kiểm tra sức khỏe cách trực quan (theo yêu cầu bên phía Toshiba) ARM, qua chứng minh khả ứng dụng vào thực tiễn thiết bị nhúng thuật tốn APL áp dụng cải tiến tơi Trong khóa luận tơi có sử dụng kết tối ưu thuật toán APL PC trình bày khóa luận bạn Cao Bắc Tiến[2] Dựa đặc điểm kiến trúc ARM thực tối ưu tốc độ tính tốn cài đặt thuật toán APL ARM vấn đề giao diện hiển thị hiển thị chương trình ii Abstract Mobile devices are becoming more and more popular because of their mobilty and wireless 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 important 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 effective 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 embedded 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ừ cụm từ Từ viết tắt Adaptive Page Layout APL Personal Computer PC Health Examination Data Visu- HEDV alization Thiết bị di động TBDĐ Zoomable User Interface ZUI Floating Point Accelerator FPA Vector Floating Points Graphical User Interface VFP GUI Bảng 1: Bảng từ viết tắt iv Chú thích Dàn trang mang tính thích ứng Máy tính cá nhân Hệ thống trực quan hóa liệu kiểm tra sức khỏe Giao diện người dùng hỗ trợ "zoom" Thành phần tăng tốc xử lý dấu phảy động Thành phần xử lý dấu phảy động Giao diện người dùng Mục lục Mở đầu 2 Cơ sở lý thuyết 2.1 Thuật toán Squarified Treemap 2.1.1 Treemap 2.1.2 Squarified Treemap 2.2 Kiến trúc ARM 2.3 OpenGL|ES Bài toán đặt 3.1 10 10 3.1.1 Các đặc điểm kiến trúc xử lý ARM 10 3.1.2 3.2 Phát triển phần mềm cho ARM Xây dựng môi trường phát triển phần mềm cho ARM 11 Các yêu cầu giao diện người dùng 11 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 cho dấu phẩy động 13 4.4 Tối ưu mã chương trình 16 Demo, thực nghiệm 5.1 19 19 5.1.1 Cài đặt thuật toán APL 19 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ý liệu 24 5.2.4 Cài đặt mô đun dàn trang 25 5.2.5 Một số hình ảnh giao diện chương trình 25 5.2.6 5.2 Thử nghiệm ARM Kết kiểm thử demo chương trình 25 Kết luận 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 HEDV phát triển tảng ARM 29 Tài liệu tham khảo 34 vi Danh sách hình vẽ 2.1 Biểu đồ treemap 2.2 Các trạng thái vi xử lý kiến trúc ARM 2.3 Biểu đồ sử dụng điện thành phần TBDĐ 4.1 Giao diện WideStudio 13 4.2 Biểu diễn dấu phẩy tĩnh 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 tối ưu 20 5.3 Kết tối ưu hiển thị 21 5.4 Đồ thị thể tối ưu tốc độ 24 A.1 Giao diện demo chương trình hiển thị ảnh 30 A.2 Demo HEDV phiên ARM với mục chia theo treemap 31 A.3 Demo HEDV phiên ARM với mục chia theo đường chéo 32 A.4 Thanh công cụ tùy chỉnh hiển thị liệu 33 vii CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.1: Thử nghiệm thuật tốn APL chưa tối ưu Hình 5.2: Thử nghiệm thuật tốn APL sau tối ưu gian tối ưu 8% Về tốc độ chạy thử nghiệm thấy kết so sánh bảng 5.2 Qua bảng kết 5.2 ta thấy việc tối ưu ARM tăng tốc độ thực thuật toán APL lên nhiều, đặc biệt với số hình khối lớn, tốc độ xử lý cải thiện gấp nhiều lần lần Chênh lệch tốc độ thấy rõ qua đồ thị 5.*4 20 CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.3: Kết tối ưu hiển thị 5.2 Health Data Visualization Ngoài việc tối ưu, phát triển APL, khóa luận này, tơi tiến hành phát triển số ứng dụng có sử dụng thuật tốn Một ứng dụng chương trình: Trực quan hóa liệu kiểm tra sức khỏe (Health Examination Data Visualization - HEDV) HEDV dự án phịng thí nghiệm Toshiba - Coltech Mục đích HEDV nhằm đưa mơ hình trực quan cho số liệu kiểm tra sức khỏe, qua cho thấy nhìn tổng thể tình hình sức khỏe người sử dụng Mục tiêu dự án 21 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.1: Kết test ARM diện tích che phủ(%) STT Số khối hình Diện tích trước tối ưu (%) Diện tích sau tối ưu (%) 63.6 70.59 41.54 56.39 74.82 82.97 74.13 85.12 71.04 76.05 77.59 82.43 10 83.69 87.98 15 84.39 90.66 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 PC TBDĐ Tôi thực việc cài xây dựng chương trình HEDV board Armadillo với cấu hình nêu 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 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 phát triển qua bước sau: 22 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.2: Kết thực thuật toán APL (trước sau tối ưu) ARM Số hình khối Thời gian tính tốn sau tối ưu Thời gian tính tốn sau chưa tối ưu 70 120 110 200 160 300 210 450 290 630 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 sở liệu sức khỏe, tiền xử lý liệu - Cài đặt thuật toán APL vào ứng dụng trực quan hóa liệu sức khỏe ARM - Sử dụng môi trường đồ họa WideStudio để xây dựng giao diện đồ họa ARM - Kiểm thử với liệu thực xem xét thời gian chạy, nhớ sử dụng với số ghi liệu tăng lên 5.2.2 Kiến trúc chương trình Thuật tốn APL cài đặt module sử dụng 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 Cippolo phát triển thành viên phòng thí nghiệm Toshiba-Coltech nhằm hỗ trợ người dùng việc "zoom" liệu Và, cài đặt thuật toán Treemap để sinh cấu trúc treemap cho mục hình chữ nhật Giao diện đồ họa chương trình xây dựng WideStudio sử 23 CHƯƠNG 5: DEMO, THỰC NGHIỆM Hình 5.4: Đồ thị thể tối ưu tốc độ dụng thư viện đồ họa OpenGL|ES để biểu diễn hình khối cho phép tương tác biểu diễn cách linh hoạt 5.2.3 Tiền xử lý liệu Dữ liệu đầu vào HEDV file sở liệu chứa liệu sức khỏe, liệu tính tốn để đưa dạng hình khối chữ nhật, hình đại diện cho ghi sức khỏe (Cụ thể phương pháp tính tốn trinh bày phụ lục) Dữ liệu chiều dài chiều rộng hình sau chuyển sang dạng dấu phảy tĩnh phương pháp trình bày phần giải pháp Sau liệu sử dụng làm đầu vào cho module sử dụng thuật toán APL để thực 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ài đặt module sử dụng 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 Cippollo (được phát triển thành viên phịng thí nghiệm Toshiba-Coltech) nhằm hỗ trợ người dùng việc "zoom" liệu Tôi cài đặt thuật toán Treemap để sinh cấu trúc treemap cho mục hình chữ nhật Tất module đưa nên ARM áp dụng giải pháp tối ưu mã nguồn trình bày chương Giao diện đồ họa chương trình xây dựng 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 ngắn, đồng thời cấu trúc module biểu diễn liệu phức tạp việc áp dụng giải pháp tối ưu trình bày gặp nhiều khó khăn 5.2.5 Một số hình ảnh giao diện chương trình 5.2.6 Kết 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 chương trình cho thấy nhớ sử dụng hiệu quả, số hình khối tăng lên không ảnh hưởng nhiều đến việc sử dụng nhớ dựa vào phương thức tải hiển thị liệu linh hoạt WideStudio 25 CHƯƠNG 5: DEMO, THỰC NGHIỆM Bảng 5.3: Kết kiểm thử demo chương trình STT Số ghi 10 20 50 100 150 200 250 300 10 350 11 400 12 450 13 500 Thời gian (mili giây) 0 20 230 1540 5360 12470 26270 46230 76090 111230 162870 223160 26 Bộ nhớ (MB) 1.0 1.0 1.0 1.1 1.2 1.2 1.2 1.3 1.3 1.4 1.4 1.4 1.4 CHƯƠNG Kết luận hướng phát triển 6.1 Kết luận Trong khóa luận tơi trình bày phương pháp tối ưu thuật toán APL để chạy ARM chuyển từ dấu phảy tĩnh sang dấu phảy động, phép tính tốn với số thực sang tính tốn với số ngun, phương pháp tối ưu mã chương trình để chạy thiết bị ARM Các bước cải tiến đạt thành đáng kể làm tăng tốc độ hoạt động cài đặt thuật toán ARM Đồng thời chương HEDV cài đặt hệ thống ARM có giá trị mặt ứng dụng Chúng tơi hi vọng phương pháp tối ưu APL mà đề xuất với kết thực nghiệm có tạo điều kiện cho nhóm nghiên cứu quan tâm tới vấn đề có sở tiến hành so sánh, đánh giá hoàn thiện phương pháp 6.2 Một số hướng phát triển Qua khóa luận này, cho thấy việc tối ưu APL mang lại ý nghĩa quan trọng tốn dàn trang TBDĐ mà cịn có ý nghĩa tốn mơ hình hóa liệu Trong tương lai, chúng tơi 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 số sử dụng dấu phảy tĩnh, đồng thời nghiên cứu mở rộng phát triển 27 CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN tốn mơ hình hóa liệu 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 sử dụng APL thư viện xử lý ảnh tích hợp công cụ WideStudio cho phép đưa dàn trang hình thiết bị nhúng để hiển thị ảnh cách phù hợp A.2 Phiên HEDV phát triển tảng ARM Cửa sổ hiển thị danh sách menu, thành phần quản lý để tùy biến hiển thị liệu Để nhập liệu khám sức khỏe, người dùng sử dụng nút OpenFile Người dùng thay đổi tùy biến hiển thị cách điều chỉnh qua 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 ARM với mục chia theo treemap 31 PHỤ LỤC A: PHỤ LỤC Hình A.3: Demo HEDV phiên ARM với mụ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ị 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 pc 2010 [3] A Girgensohn S Uchihashi, J Foote and J Boreczky Video manga: Generating semantically 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 content [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 ... 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... thiết bị khác điện thoại di dộng, TV hay thiết bị định hướng GPS ôtô Thuật toán Adaptive Page Layout [1] giải pháp để đưa cách xếp hình hiệu cho TBDĐ Trong khóa luận tơi hướng đến việc phát triển,. .. tiễn thiết bị nhúng thuật toán APL áp dụng cải tiến tơi Trong khóa luận tơi có sử dụng kết tối ưu thuật toán APL PC trình bày khóa luận bạn Cao Bắc Tiến[2] Dựa đặc điểm kiến trúc ARM tơi thực tối