BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - LÊ ĐỨC TÙNG CÁC CẤU TRÚC KHUNG CHO LẬP TRÌNH ĐA LÕI Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TIẾN SĨ NGUYỄN HỮU ĐỨC Hà Nội - 2010 Lời cam đoan Tôi - Lê Đức Tùng - xin cam đoan: • Luận văn tốt nghiệp Thạc sĩ công trình nghiên cứu thân hướng dẫn TS.Nguyễn Hữu Đức • Các kết Luận văn tốt nghiệp trung thực, chép toàn văn công trình khác Hà Nội, ngày 05 tháng 10 năm 2010 Lê Đức Tùng i Mục lục Lời cảm ơn v Giới thiệu luận văn 1.1 Lý chọn đề tài 1.2 Mục đích nghiên cứu luận văn 1.3 Luận điểm đóng góp 1.4 Cấu trúc luận văn Lập trình song song theo kiểu cấu trúc khung 2.1 Đặt vấn đề 2.2 Cấu trúc giải thuật khung - Hướng tiếp cận có cấu trúc để 7 quản lý tính toán song song 10 2.3 2.4 Cấu trúc khung chia-trị 14 2.3.1 Đặt vấn đề 14 2.3.2 Hướng tiếp cận ZAPP 14 2.3.3 Hướng tiếp cận FDDC 16 Cấu trúc khung kết hợp lặp 17 ii 0.0 MỤC LỤC 2.5 2.6 2.4.1 Đặt vấn đề 17 2.4.2 Đặc tả cấu trúc khung kết hợp lặp 18 2.4.3 Các vấn đề liên quan đến thực thi song song 20 Cấu trúc khung cluster 22 2.5.1 Đặt vấn đề 22 2.5.2 Đặc tả cấu trúc khung cluster 23 Cấu trúc khung hàng đợi công việc 25 2.6.1 Đặt vấn đề 25 2.6.2 Đặc tả cấu trúc khung hàng đợi công việc 26 Nghiên cứu lý thuyết tính toán giải thuật nhằm áp dụng xây dựng cấu trúc khung 29 3.1 Tổng quan khái niệm Tính toán giải thuật 30 3.2 Phương pháp thiết kế cấu trúc khung song song 32 3.3 Cấu trúc khung song song cho kiểu liệu Danh sách 34 3.4 3.3.1 Định nghĩa đại số cho kiểu liệu danh sách 34 3.3.2 Homomorphism cho danh sách song song 35 3.3.3 Các cấu trúc khung danh sách 36 Cấu trúc khung song song cho kiểu liệu Ma trận 37 3.4.1 Định nghĩa đại số cho mảng hai chiều 37 3.4.2 Homomorphism cho mảng hai chiều 38 3.4.3 Cấu trúc khung song song ma trận hai chiều 39 Nghiên cứu xây dựng cấu trúc khung cho cấu trúc liệu iii 0.0 MỤC LỤC HTA 4.1 4.2 45 Cấu trúc liệu HTA 45 4.1.1 Định nghĩa phân loại cấu trúc liệu HTA 45 4.1.2 Một số khái niệm liên quan đến cấu trúc liệu HTA 49 4.1.3 Một số cách xây dựng cấu trúc liệu HTA 52 Định nghĩa đại số cho cấu trúc liệu HTA 54 4.2.1 Định nghĩa 54 4.2.2 Một số tính chất cấu trúc HTA đại số 56 4.3 Homomorphism 57 4.4 Xây dựng cấu trúc khung cho cấu trúc liệu HTA 58 4.4.1 Cấu trúc khung map 58 4.4.2 Cấu trúc khung reduce 59 4.4.3 Cấu trúc khung zipwith 59 Kết luận hướng phát triển 61 5.1 Kết luận 61 5.2 Hướng phát triển 62 Tài liệu tham khảo 64 Danh sách hình vẽ 66 iv Lời cảm ơn Tôi xin gửi lời cảm ơn sâu sắc đến Tiến sĩ Nguyễn Hữu Đức, người hướng dẫn tận tình theo dõi sát qúa trình làm luận văn Chính Thầy người đưa ý tưởng xây dựng nên cấu trúc liệu HTA song song điểm luận văn tốt nghiệp Tôi xin gửi lời cảm ơn chân thành đến Phó giáo sư, Tiến sĩ Nguyễn Thanh Thủy, Thầy góp ý cho từ bắt đầu làm đề tài, làm rõ hướng cần thiết cho đề tài Chuyến làm việc tháng Viện Tin học Nhật Bản (National Institute of Informatics) mang lại cho nhiều điều Tôi xin gửi lời cảm ơn Giáo sư Zhenjiang Hu Giáo sư hướng dẫn trao đổi với tận tình thời gian làm việc vấn đề Lý thuyết tính toán giải thuật thư viện lập trình SkeTo nhóm ông phát triển Viện Tin học Nhật Bản Đại Học Tokyo Tôi xin gửi lời cảm ơn đến Trung tâm tính toán hiệu cao ĐHBKHN, nơi làm việc, Trung tâm hỗ trợ nhiều mặt chuyên môn điều kiện sở vật chất để hoàn thành luận văn Tôi xin gửi lời cảm ơn đến Phòng thí nghiệm Takeichi - Đại học Tokyo nơi tạo điều kiện cho có buổi thảo luận hàng tuần với nhóm nghiên cứu thời gian làm việc với giáo sư Zhenjiang Hu Cuối cùng, muốn cảm ơn gia đình động viên, giúp đỡ suốt trình học tập nói chung luận văn Thạc sĩ nói riêng, có lẽ thiếu v 0.0 Chương hỗ trợ tinh thần từ gia đình luận văn khó hoàn thành vi Chương Giới thiệu luận văn 1.1 Lý chọn đề tài Tính toán song song giải pháp cho yêu cầu liên quan đến sức mạnh tính toán kích thước nhớ Phương pháp chuẩn để tăng hiệu kết hợp máy tính vi xử lý, để chúng kết hợp với thực thi chương trình Hướng tiếp cận giảm thời gian hoàn thành công việc cách tăng sức mạnh tính toán lẫn kích thước nhớ Trước đây, chương trình song song viết chủ yếu để giải toán khoa học viện nghiên cứu Máy tính song song sử dụng cho ứng dụng phổ thông, giới hạn cho toán tính toán khoa học cần nhớ lớn sức mạnh tính toán Vài năm trở lại đây, phạm vi xử lí song song chuyển dần sang lĩnh vực Khai phá liệu, tìm kiếm web Hơn nữa, việc tạo hệ thống song song phân cụm từ máy PC trở nên dễ ràng nhờ phần mềm trung gian phát triển mạnh mẽ Các công ty lớn Google thực thi công việc tính toán lớn kiến trúc phân cụm [4] Hơn nữa, vi xử lý đa lõi xuất khắp nơi, lên kiến trúc khiến cho lập trình song song trở thành 1.1 Chương vấn đề tất yếu Sẽ không lâu nữa, ngành công nghiệp tính toán phải đối mặt với vấn đề viết chương trình song song hiệu đắn Lập trình song song trở thành thách thức Không giống chương trình tuần tự, chương trình song song thực thi P vi xử lý; điều gánh nặng cho lập trình viên để tận dụng hết vi xử lý cách hiệu Nói chung, lập trình viên cần viết thêm đoạn mã để tiến hành tác vụ sau: phân rã miền toán thành P miền con, xác định P tác vụ để làm việc với miền này, sau đồng tác vụ Mặc dù, khái niệm đơn giản, xong chí lập trình viên chuyên nghiệp cần nỗ lực thực để hoàn thành chúng Đối với lập trình viên quen với lập trình việc viết chương trình song song quan trọng không so với việc giảm thời gian thực thi chương trình Họ muốn xây dựng ứng dụng nhanh chóng dễ dàng Điều thúc đẩy phát triển chế lập trình song song mới, cho phép lập trình viên lập trình dễ dàng viết chương trình tuần tự, chương trình phải chạy nhanh máy tính song song Có số hướng tiếp cận để phát triển công cụ lập trình song song mức cao Các công cụ dừng mức trừu tượng để che giấu thực thi bên giảm thiểu tính phức tạp, người dùng nhanh chóng xây dựng chương trình song song Các công cụ thể dạng Ngôn ngữ lập trình bậc cao thư viện lập trình song song phức tạp MPI hay PVM, lập trình viên không tốn nhiều thời gian để nghiên cứu nhằm lấp khoảng trống kiến thức lập trình song song lập trình Tư tưởng cố gắng làm cho lập trình viên viết chương trình song song thể viết chương trình tuần tự, ngoại trừ số hàm đặc biệt cần biên dịch song song Khi chương trình chạy máy tính song song, trình biên dịch song song tự động sử dụng Lập trình song song theo cấu trúc khung (hay gọi lập trình song 1.1 Chương song có cấu trúc) [3]-[11] lên cách tiếp cận đầy hứa hẹn để đạt mục đích nêu Trong lập trình song song theo cấu trúc khung, lập trình viên xây dựng chương trình song song dựa thành phần tạo sẵn (Ví dụ: cấu trúc khung, mẫu có sẵn), thành phần sẵn có làm cho chương trình thực thi hiệu làm cho tiến trình song song hóa trở lên đơn giản Có nhiều định nghĩa cấu trúc khung, nhìn chung khuôn mẫu cho tính toán song song, tương tác, đóng gói thành khối framework, hay template, hay chí cấu trúc khung khác Các chương trình song song theo kiểu cấu trúc khung dễ hiểu chí với người lập trình song song kinh nghiệm, mã nguồn chương trình nhìn giống với chương trình có luồng thực thi Tuy nhiên, có vài ứng dụng thực phát triển cấu trúc khung song song Có bốn lý lý giải cho điều Thứ nhất, giống design pattern kỹ nghệ phần mềm, cấu trúc khung song song đề cập đến theo cách đặc biệt mà chủ yếu dựa miền ứng dụng Không có nguyên lý rõ ràng việc thiết kế cấu trúc khung, ví dụ làm để tạo cấu trúc khung kết hợp tập cấu trúc khung khác cho mục đích khác Thứ hai, lập trình song song dựa vào tập cố định cấu trúc khung song song thô sơ để đặc tả giải thuật song song, nên người lập trình thường khó khăn muốn chọn sau tích hợp với để phát triển chương trình song song hiệu Trong đa số trường hợp, lý người lập trình cảm thấy miễn cưỡng dùng cấu trúc khung, đơn giản họ không chắn liệu cấu trúc khung có có đủ mạnh để giải vấn đề họ hay không, họ dễ từ bỏ Thứ ba, giải thuật song song đặc tả cấu trúc khung, nên tồn nhiều chi phí thừa Có thể lý giải điều trường hợp đơn giản, có nhiều cấu trúc liệu trung gian không cần thiết truyền cấu trúc khung Cuối cùng, hầu hết hệ thống cấu trúc khung định nghĩa dựa số ngôn ngữ đòi hỏi mở rộng ngôn ngữ 4.1 Chương Hình 4.7: Xây dựng HTA từ lên Hạng phần tử nhỏ hạng phần tử cha Nếu phần tử có hạng nhỏ hạng phần tử cha, chiều đơn “giả” (kích thước = 1) thêm vào để số chiều với chiều phần tử cha Thực tương tự hạng cha bé phần tử 4.1.3 Một số cách xây dựng cấu trúc liệu HTA Xây dựng từ lên Một cách đơn giản để có HTA đồng cách phân chia ma trận mức thấp trước tiên thành miếng lợp sau tiến hành đệ quy việc phân chia miếng lợp kết Tiến trình từ lên này, minh họa Hình 4.7, luôn sinh HTA đồng Theo cách tiếp cận từ lên, cần định nghĩa hàm hta nhận tham số HTA m chiều mảng chưa phân chia m véc tơ p1 , p2 , , pm , (mỗi véc tơ cho chiều HTA) trả HTA định nghĩa việc chia chiều thứ i mảng sau phần tử thứ pi (k)th theo chiều thứ i Ví dụ, cho ma trận D kích thước (10, 12), lệnh C = hta(D, [1, 3, 5, 7], [2, 5, 8]); B = hta(C, [2], [0, 1, 2]); A = hta(B, [0], [0]); 52 4.1 Chương Hình 4.8: Xây dựng HTA từ xuống sinh ba HTA Hình 4.7 Xây dựng từ xuống Phương pháp mức đỉnh xây dựng phần chia Cách tiếp cận linh động cách tiếp cận từ lên chỗ cho phép tạo HTA đồng không đồng HTA tạo từ xuống đệ quy Đầu tiên, HTA rỗng tạo Muốn tạo HTA rỗng dùng hàm tạo: hta(size0 , size1 , , sized−1 ) Trong hàm tạo trên, tham số kích thước chiều mức đỉnh HTA Sau HTA mức đỉnh rống tạo, miếng lợp khởi tạo để chứa HTA ma trận Trước trình bày ví dụ cách tạo HTA từ xuống, cần phải mô tả cách đánh địa miếng lợp HTA Các miếng lợp đánh địa chỉ số dấu ngoặc đơn Một tập thêm số nên thêm vào với mức cần đánh địa HTA Hình 4.8 mô tả trừu tượng trình tạo HTA theo cách từ xuống Cách tạo HTA từ xuống ưa thích cho chương trình song song, không đòi hỏi toàn mảng cấp phát trước HTA tạo; vi xử lí cần cấp phát miếng lợp chứa Thêm nữa, cách cho phép tạo HTA đồng lẫn không đồng theo cách tương tự 53 4.2 Chương Hàm tạo HTA đặc biệt Vì HTA đồng dùng rộng rãi nhất, hàm tạo sinh HTA đồng mức xây dựng Hàm tạo có tham số kích thước miếng lợp mức phân cấp: C = hta((d0 , d1 , , dd−1 )0 , , (d0 , d1 , , dd−1 )l )); Mỗi tham số hàm tạo tuple kích thước d Tham số i kích thước miếng lợp mức i 4.2 Định nghĩa đại số cho cấu trúc liệu HTA 4.2.1 Định nghĩa Như phần trình bày cấu trúc liệu HTA, nhiên cách khởi tạo cho HTA đưa khó khăn việc xây dựng nên cấu trúc khung Vì theo phương pháp sử dụng lý thuyết Tính toán giải thuật cấu trúc liệu phải biểu diễn theo đại số, thứ hai điểm quan trọng cách biểu diễn đại số phải thể khả song song hóa thực thi Luận văn sâu nghiên cứu đề xuất định nghĩa đại số cho cấu trúc liệu HTA sau: data HTA β = Mat β | Tile (HTA β) Trong ngang | (HTA β) (HTA β) | (HTA β) (HTA β) hàm tạo beside, để thể hai HTA bên cạnh theo chiều hàm tạo above, thể hai HTA bên cạnh theo chiều dọc Đơn vị nhỏ HTA ma trận, hay gọi phần tử 54 4.2 Chương Hình 4.9: Ví dụ HTA Cho ma trận β, hàm tạo Mat cấu trúc lên HTA từ ma trận đầu vào β HTA cấu thành từ hai HTA khác, sử dụng hai hàm tạo , HTA cạnh theo chiều ngang theo chiều dọc Hàm tạo Tile tạo lên mức HTA đầu vào trở thành HTA mức Ta xét ví dụ: Hãy cấu trúc lên HTA có hai HTA (hai Miếng lợp) Hai miếng lợp cạnh theo chiều ngang Miếng lợp bên trái chia thành Miếng lợp con, Miếng lợp ma trận gồm phần tử Miếng lợp bên phải ma trận × HTA có cấu trúc minh họa hình 4.9 Cách cấu trúc bước HTA hình 4.9 mô tả hình 4.10 Ban đầu, M 1, M 2, M 5, M HTA gồm ma trận có phần tử, tạo nên từ hàm tạo Mat M 3478 thể HTA gồm ma trận × có phần tử HTA M kết hợp với M thông qua hàm tạo beside để tạo thành HTA, M kết hợp với M thông qua hàm tạo beside tạo thành HTA khác Tiếp tục vậy, ta sử dụng hàm tạo định nghĩa HTA để tạo nên HTA mong muốn 55 4.2 Chương HTA hình 4.10 định nghĩa đại số sau: Tile ( Tile ( (M1 M2) (M5 M6) ) ) Một điểm đáng ý có nhiều cách cấu tạo nên HTA từ định nghĩa HTA, ví dụ, thay sử dụng cách cấu tạo (M1 4.2.2 M2) (M5 M6), ta dùng (M1 M5) (M2 M6) Một số tính chất cấu trúc HTA đại số Tính chất abide (above and beside): Định nghĩa 3.4.1 Tính chất abide có ý nghĩa quan trọng, dựa tính chất abide ta đưa homomorphism có khả tính toán song song cấu trúc liệu HTA, không phụ thuộc vào thứ tự phân tán liệu Tính chất đồng nhất: Một HTA gọi đồng hàm tạo hai HTA thực hai HTA có cấu trúc giống Hai HTA có cấu trúc giống hai HTA có số lượng vị trí hàm tạo giống nhau, đồng thời HTA có cấu trúc giống Ví dụ: • M1, M2, M5, M6 HTA giống • M1 M3478 hai HTA không giống • Miếng lợp (M1) M1 hai HTA không giống 56 4.3 Chương Hình 4.10: Mô tả bước cấu trúc lên HTA • Miếng lợp (M1 M2) Miếng lợp (M1 M2) hai HTA không giống Trong luận văn này, đề cập đến HTA đồng 4.3 Homomorphism Cho trước hàm km , kt , ⊕ ⊗ Hàm h gọi homomorphism HTA định nghĩa 57 4.4 Chương sau: h (Mat a) = km (a) h (Tile x) = kt (h x) h (x y) = (h x) ⊕ (h y) h (x y) = (h x) ⊗ (h y) Trong đó, hai hàm ⊕ ⊗ phải thỏa mãn tính chất kết hợp Hàm h ký hiệu homHT A (km , kt , ⊕, ⊗) Xét ví dụ hàm layer homomorphism HTA Hàm tính toán xem HTA đầu vào có tối đa mức 4.4 layer (Mat a) =0 layer (Tile x) = + (layer x) layer (x y) = (layer x) Max (layer x) layer (x = (layer x) Max (layer x) y) Xây dựng cấu trúc khung cho cấu trúc liệu HTA Dựa định nghĩa homomorphism, rõ ràng homomorphism tốt để song song hóa Tuy nhiên cần phải đưa homomorphism cụ thể để mô tả tốt cho giải thuật tính toán Các homomorphism cấu trúc khung cấu trúc liệu HTA Luận văn đưa cấu trúc khung hay sử dụng là: map, reduce, zipwith 4.4.1 Cấu trúc khung map Cấu trúc khung map áp dụng hàm f tất phần tử mức HTA Sau áp dụng cấu trúc khung, cấu trúc HTA giữ nguyên 58 4.4 Chương Cấu trúc khung map định nghĩa sau: 4.4.2 map(f) (Mat a) = f (a) map(f) (Tile x) = Tile x map(f) (x y) = (map(f) x) ⊕ (map(f) y) map(f) (x y) = (map(f) xx) ⊗ (map(f) y) Cấu trúc khung reduce Cấu trúc khung reduce nhận vào hai đối số hai hàm có tính kết hợp ⊕ ⊗ Hai hàm áp dụng cho phần tử HTA mức, kết Ma trận vô hướng reduce(⊕, ⊗) (Mat a) = a reduce(⊕, ⊗) (Tile x) = reduce(⊕, ⊗) x reduce(⊕, ⊗) (x = (reduce(⊕, ⊗) x) ⊕ (reduce(⊕, ⊗) y) y) reduce(⊕, ⊗) (x y) = ((reduce(⊕, ⊗) x)) ⊗ (reduce(⊕, ⊗) y) Có thể mở rộng cấu trúc khung thành cấu trúc khung hreduce để áp dụng hai hàm đầu vào từ mức i1 đến mức i2 cấu trúc HTA, giá trị trả HTA thay ma trận vô hướng Tuy nhiên phạm vi luận văn, dừng lại cấu trúc khung reduce 4.4.3 Cấu trúc khung zipwith Cấu trúc khung zipwith sử dụng để kết hợp hai cấu trúc liệu HTA thành HTA mới, đầu vào zipwith hai HTA hàm để kết hợp zipwith(f) (Mat a) (Mat a) =f aa zipwith(f) (Tile x) (Tile x) = Tile (zipwith(f) x y) zipwith(f) (x = (zipwith(f) x u) y) (u v) zipwith(f) (x y) (u v) (zipwith(f) y v) = (zipwith(f) x u) (zipwith(f) y v) 59 4.4 Chương Cấu trúc khung zipwith đòi hỏi hai HTA đầu vào phải có cấu trúc giống hệt 60 Chương Kết luận hướng phát triển 5.1 Kết luận Luận văn trình bày rõ lập trình song song theo cấu trúc khung, hướng lập trình có cấu trúc áp dụng cho giải thuật song song Tuy nhiên chưa đủ, lẽ việc thiết kế cấu trúc khung mang tính chất đặc thù cho lĩnh vực, nên việc mở rộng, kết hợp cấu trúc khung khó khăn Lý thuyết tính toán giải thuật lý thuyết quan trọng lĩnh vực Đại số cho lập trình, hướng đầy hứa hẹn để phát triển chương trình cách có hệ thống, áp dụng tính chất đại số toán học lên giải thuật chương trình, luật suy diễn để Chuyển đổi giải thuật chứng minh chặt chẽ Do việc đưa chương trình hiệu rõ ràng đắn Sự kết hợp Lập trình song song theo cấu trúc khung Lý thuyết tính toán giải thuật làm cho lập trình song song gần gũi với người sử dụng, trình phát triển phiên thực thi rõ ràng, thân phần thiết kế cấu trúc khung bao hàm tính song song cao 61 5.2 Chương Luận văn sâu trình bày cấu trúc khung cho hai cấu trúc liệu Danh sách Ma trận Đây hai kiểu liệu bản, sử dụng phổ biến nhiều toán Phiên thực thi hai cấu trúc liệu đóng gói thư viện Lập trình SkeTo [13], [8] Các cấu trúc khung cho kiểu liệu [9] phát triển nhiên chưa có phiên thực thi thư viện SkeTo tính thời điểm luận văn Điểm luận văn đưa định nghĩa đại số cho cấu trúc liệu HTA Cấu trúc HTA thuận lợi để mô tả giải thuật khối cho ma trận [2], nhiên trước chưa có phương pháp rõ ràng để phát triển chương trình dựa cấu trúc liệu Hơn nữa, cấu trúc liệu HTA tối ưu tính cục sử dụng nhớ, tính phân tầng cấu trúc, nên liệu lưu trữ tầng nhớ khác nhau, tốc độ truy xuất nhanh tận dụng nhớ cache [5], [15] Cấu trúc phân tầng HTA phù hợp với cấu trúc nhớ hệ thống tính toán phân tán Các Homomorphism HTA đưa ra, luận văn xây dựng nên cấu trúc khung lập trình song song map, reduce, zipwith 5.2 Hướng phát triển Đưa định nghĩa đại số cho HTA bước quan trọng, phải thể cấu trúc liệu song song Tuy nhiên nhiều công việc để tiếp tục hoàn thiện hướng nghiên cứu Cụ thể sau: • Xây dựng phiên thực thi cho cấu trúc HTA cấu trúc khung Để thuận tiện, sử dụng template ngôn ngữ lập trình C++ để viết cấu trúc khung, kết hợp thư viện lập trình truyền thông điệp MPI để lập trình song song máy phân tán, 62 5.2 Chương sử dụng OpenMP để tối ưu cho đoạn mã chạy máy đa lõi Sau xây dựng xong cần đánh giá hiệu cấu trúc liệu • Đưa framework nhằm phát triển có hệ thống giải thuật dựa cấu trúc khung HTA Trong framework cần có luật để suy diễn giải thuật, mục đích cuối đưa chương trình song song hiệu cách có hệ thống • Xây dựng phiên thực thi HTA hệ thống tính toán GP-GPU Bản thân hệ thống tính toán GP-GPU có hệ thống nhớ phân cấp giống với cách tổ chức HTA, để viết chương trình GP-GPU hiệu quả, người lập trình phải nắm rõ liệu cần lưu vùng nhớ Do vậy, phát triển phiên HTA cho GP-GPU hướng phát triển tốt 63 Tài liệu tham khảo [1] R Bird and O de Moor Algebras of Programming Prentice Hall, 1996 [2] Alfredo Buttari, Julien Langou, Jakub Kurzak, and Jack Dongarra A class of parallel tiled linear algebra algorithms for multicore architectures lapack working note 191 Technical report, 2007 [3] J Darlington, A J Field, P G Harrison, P H J Kelly, D W N Sharp, Q Wu, and R L While Parallel programming using skeleton functions In Proc of the Conference on Parallel Architectures and Reduction Languages Europe (PARLE’93), volume 694, pages 146–160 Springer-Verlag, 1993 [4] J Dean and S Ghemawat Mapreduce: Simplified data processing on large clusters In Symposium on Operating System Design and Implementation (OSDI), 2004 [5] J Guo, G Bikshandi, D Hoeflinger, G Almási, B.B Fraguela, M.J Garzarán, D Padua, and C von Praun Hierarchically tiled arrays for parallelism and locality In Workshop on Performance Engineering Technology and Research Sponsored under the NSF Next Generation Software, (NGS 06), in conjunction with IPDPS Rhodes (Greece), 2006 [6] E Horowitz and A Zorat Divide-and-conquer for parallel processing In IEEE Transactions on Computers, page 582–585, 1983 64 5.2 TÀI LIỆU THAM KHẢO [7] J Jeuring Theories for algorithm calculation PhD thesis, Faculty of Science, Utrecht University, 1993 [8] Yuki Karasawa and Hideya Iwasaki A parallel skeleton library for multicore clusters In 38th International Conference on Parallel Processing (ICPP 2009), pages 84–91, 2009 [9] Kiminori Matsuzaki, Zhenjiang Hu, and Masato Takeichi Parallel skeletons for manipulating general trees In Parallel Computing,Vol.32, No.78, pages 590–603, 2006 [10] D L McBurney and M.R Sleep Experiments with the zapp: Matrix multiply on 32 transputers, heuristic search on 12 transputers Technical report, School of Information Systems Internal Report SYS–C87–10, University of East Anglia, 1987 [11] M.Cole Algorithmic skeletons : a structured approach to the management of parallel computation Pitman, London: Research Monographs in Parallel and Distributed Computing, 1989 [12] F.J Peters Tree machines and divide and conquer algorithms In CONPAR 81, LNCS 111, pages 25–36 Springer-Verlag, 1981 [13] Sketo library project, March 2010 [online] http://www.ipl.t u-tokyo.ac.jp/sketo [14] M Sollin An algorithm attributed to Sollin S Goodman and S Hedetniemi, editors, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, 1977 [15] Michael E Wolf and Monica S Lam A data locality optimizing algorithm pages 30–44, 1991 65 Danh sách hình vẽ 2.1 Đặc tả thị 19 2.2 Thực thi cấu trúc khung hàng đợi công việc 27 3.1 Định nghĩa trực quan cho ba cấu trúc khung mảng hai chiều 40 4.1 HTA đồng (a) Chính quy (b) Không quy 46 4.2 HTA không hợp lệ 47 4.3 HTA hai mức 48 4.4 HTA không đồng với (a) vị trí phân chia khác với miếng lợp liền kề (b) số mức lợp khác 48 4.5 Quy ước đặt tên đánh số mức khác HTA 49 4.6 Minh họa (a) tuple, range, region (b) dist 51 4.7 Xây dựng HTA từ lên 52 4.8 Xây dựng HTA từ xuống 53 4.9 Ví dụ HTA 55 4.10 Mô tả bước cấu trúc lên HTA 57 66 ... Chương Lập trình song song theo kiểu cấu trúc khung Chương giới thiệu Lập trình song song theo kiểu cấu trúc khung Các khái niệm hướng tiếp cận lập trình có cấu trúc đưa Cuối chương số cấu trúc khung. .. nhắc đến cấu trúc khung, mô hình lập trình theo cấu trúc khung Các mục chương 13 2.3 Chương giới thiệu số cấu trúc khung hay sử dụng 2.3 Cấu trúc khung chia-trị 2.3.1 Đặt vấn đề Cấu trúc khung ta... trình bày tóm tắt cấu trúc khung thường hay sử dụng, là: cấu trúc khung chiatrị, cấu trúc khung kết hợp lặp, cấu trúc khung cluster, cấu trúc khung hàng đợi công việc • Chương ba trình bày Lý thuyết