Luận văn thạc sĩ: Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị

Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị nhằm nâng cao khả năng thực hiện của chương trình, giảm thời gian thực hiện, góp phần nâng cao hiệu năng hoạt động của hệ thống.
Nội dung trích xuất từ tài liệu:
Luận văn thạc sĩ: Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị 1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N T N TH NG THU T TOÁN SONG SONG GI I QUY T M T S BÀI TOÁN V LÝ THUY T Đ TH Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011 2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TSKH Tr n Qu c Chi n Ph n bi n 1: Ph n bi n 2: Lu n văn s ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu ttính h p t i Đ i h c Đà N ng vào ngày ….. tháng 10 năm 2011 * Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm h c li u, Đ i h c Đà N ng. 3 M Đ U 1. Lý do ch n ñ tài: Khoa h c k thu t ngày càng phát tri n, ñ t ra nhi u bài toán v i kh i lư ng tính toán r t l n. Trong s ñó có nh ng bài toán mà k t qu ch có ý nghĩa n u ñư c hoàn thành trong kho ng th i gian cho phép. Ví d như các tính toán trong th i gian th c, mô ph ng s chuy n ñ ng c a các phân t , tính quĩ ñ o chuy n ñ ng c a v t th trong không gian, d báo th i ti t... Đ gi i quy t nh ng bài toán này, ngư i ta ñã nghiên c u tăng t c ñ tính toán b ng hai phương pháp hay k t h p c hai: Phương pháp 1: C i ti n công ngh , tăng t c ñ x lý c a máy tính. Công vi c này ñòi h i nhi u th i gian, công s c và ti n c a, nhưng t c ñ cũng ch ñ t ñư c ñ n m t gi i h n nào ñó. Phương pháp 2: Chia bài toán ra thành nh ng công vi c nh ñ có th ch y song song trên nhi u b x lý. Vi c phát tri n công ngh tính toán theo phương pháp 2 ñã cho ra ñ i công ngh tính toán song song, ñó là vi c s d ng ñ ng th i nhi u tài nguyên tính toán ñ gi i quy t m t bài toán. Các tài nguyên tính toán có th bao g m m t máy tính v i nhi u b vi x lý hay m t t p các máy tính k t n i m ng hay là m t s k t h p c a hai d ng trên. Công ngh tính toán song song cho phép gi m th i gian th c thi bài toán tùy thu c cách phân chia và s b x lý th c thi chương trình. Nguyên t c quan tr ng nh t c a tính toán song song chính là tính ñ ng th i hay x lý nhi u tác v cùng m t lúc. Trong tính toán song song hi n nay, có hai công ngh chính: Th nh t là s d ng các siêu máy tính v i r t nhi u b x lý ñư c tích h p bên trong ñư c thi t k ñ ng b c v ph n c ng và ph n m m. Các công ngh ñư c áp d ng trong các siêu máy tính thư ng là các công ngh tiên ti n làm cho giá thành c a h th ng siêu máy tính tăng r t cao.Vì 4 th các siêu máy tính thư ng ñư c s d ng trong các lĩnh v c mà v n ñ tính toán ph c t p, nh y c m và yêu c u th i gian th c như mô ph ng th c hi n c a các ñ ng cơ máy bay, qu c phòng, vũ tr ... Cách th hai là k t n i các máy tính l i v i nhau và cùng th c hi n bài toán. H th ng các máy tính k t n i này chính là h th ng tính toán song song phân c m. H th ng này có ưu ñi m là giá thành r hơn r t nhi u so v i siêu máy tính có cùng s c m nh (do s d ng các thi t b thông thư ng) và tính linh ho t c a h th ng (s nút, s b x lý, b nh , thi t b m ng... ñ u mang tính tuỳ bi n cao). S phát tri n m nh m c a m ng máy tính, các công ngh m ng hi n nay ñã l p ñi h n ch v truy n thông trong h th ng máy tính song song phân c m làm cho nó ñư c phát tri n r ng rãi. Các lĩnh v c s d ng h th ng tính toán song song phân c m thư ng yêu c u tính toán không quá l n, không yêu c u th i gian th c như x lý nh, nh n d ng vân tay, tính toán k t c u công trình, mô ph ng các thí nghi m... V i s ra ñ i c a chíp ña lõi (multi-core) và x lí ña lu ng (multi- threads) thì vi c khai thác h t kh năng x lí c a nó là m t v n ñ c n quan tâm hi n nay. Tuy nhiên v i l p trình truy n th ng (l p trình tu n t ), các câu l nh, các quá trình x lý ñư c th c h ên m t cách l n lư t, tu n t như v y s không phát huy h t hi u năng c a b vi x lý ña lõi. Các nhà s n xu t chip và ph n m m máy tính ñã b t ñ u nh ng n l c ñ ñ nh hư ng gi i phát tri n ph n m m, cung c p cho h nh ng công c t t hơn trong vi c l p trình ña lõi. Đi u ñó có nghĩa là ngư i l p trình ph i l p trình l i theo m t cách khác ñ t n d ng s gia tăng v s lõi. V i m c ñích tìm hi u và nghiên c u v thu t toán song song, tôi ch n ñ tài “Thu t toán song song cho m t s bài toán v lí thuy t ñ th ” nh m tìm hi u, nghiên c u và tìm gi i pháp song song cho m t s bài toán v lý thuy t ñ th trên cơ s nh ng thu t toán tu n t truy n th ng. 5 2. M c tiêu c a ñ tài: Tìm hi u, nghiên c u và xây d ng thu t toán song song cho m t s bài toán c th ñ nâng cao kh năng th c hi n c a chương trình, gi m th i gian th c hi n, góp ph n năng cao hi u năng ho t ñ ng c a h th ng. 3. Đ i tư ng và ph m vi nghiên c u: + Đ i tư ng nghiên c u: - XLSS và thu t toán song song. - Lý thuy t ñ th . + Ph m vi nghiên c u: - M t s bài toán v lý thuy t ñ th : Tìm ñư ng ñi, cây bao trùm. 4. Phương pháp nghiên c u: - Nghiên c u lý thuy t: XLSS, thu t toán song song, lý thuy t ñ th . - Tìm hi u m t s thu t toán cơ b n: Tìm ñư ng ñi, cây bao trùm. - Nghiên c u và xây d ng thu t toán song song. 4.1 Ý nghĩa khoa h c và th c ti n c a ñ tài: - Nghiên c u và tìm gi i pháp nâng cao hi u năng c a h th ng b ng XLSS. - Có th áp d ng cho m t s lĩnh v c c th và m t s bài toán có ñ ph c t p v th i gian l n, nh ng bài toán th i gian th c. 4.2 B c c c a ñ tài: N i dung c a ñ tài này bao g m 3 chương: Chương 1: Tính toán song song và thu t toán song song. - Chương này gi i thi u t ng quan v tính toán song song, thu t toán song song, các mô hình l p trình song song. Chương 2: Lí thuy t ñ th . - Chương này gi i thi u ...