Các cấu trúc khung cho lập trình đa lõ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 đoanTôi - Lê Đức Tùng - xin cam đoan:• Luận văn tốt nghiệp Thạc sĩ này là công trình nghiên cứu của bản thântôi dưới sự hướng dẫn của TS.Nguyễn Hữu Đức.• Các kết quả trong Luận văn tốt nghiệp là trung thực, không phải saochép toàn văn của bất kỳ công trình nào khác.Hà Nội, ngày 05 tháng 10 năm 2010Lê Đức Tùngi Mục lụcLời cảm ơn v1 Giới thiệu luận văn 11.1 Lý do chọn đề tài.
- 41.4 Cấu trúc luận văn.
- 52 Lập trình song song theo kiểu cấu trúc khung 72.1 Đặt vấn đề.
- 72.2 Cấu trúc giải thuật khung - Hướng tiếp cận có cấu trúc đểquản lý các tính toán song song.
- 102.3 Cấu trúc khung chia-trị.
- 142.3.1 Đặt vấn đề.
- 162.4 Cấu trúc khung kết hợp lặp.
- 172.4.2 Đặc tả cấu trúc khung kết hợp lặp.
- 182.4.3 Các vấn đề liên quan đến thực thi song song.
- 202.5 Cấu trúc khung cluster.
- 222.5.1 Đặt vấn đề.
- 222.5.2 Đặc tả cấu trúc khung cluster.
- 232.6 Cấu trúc khung hàng đợi công việc.
- 252.6.1 Đặt vấn đề.
- 252.6.2 Đặc tả cấu trúc khung hàng đợi công việc.
- 263 Nghiên cứu các lý thuyết tính toán trên giải thuật nhằm ápdụng xây dựng cấu trúc khung 293.1 Tổng quan về khái niệm Tính toán trên giải thuật.
- 303.2 Phương pháp mới thiết kế các cấu trúc khung song song.
- 323.3 Cấu trúc khung song song cho kiểu dữ liệu Danh sách.
- 343.3.1 Định nghĩa đại số cho kiểu dữ liệu danh sách.
- 343.3.2 Homomorphism cho danh sách song song.
- 353.3.3 Các cấu trúc khung trên danh sách.
- 363.4 Cấu trúc khung song song cho kiểu dữ liệu Ma trận.
- 383.4.3 Cấu trúc khung song song trên ma trận hai chiều.
- 394 Nghiên cứu xây dựng cấu trúc khung cho cấu trúc dữ liệuiii 0.0 MỤC LỤCHTA 454.1 Cấu trúc dữ liệu HTA.
- 454.1.1 Định nghĩa và phân loại cấu trúc dữ liệu HTA.
- 454.1.2 Một số khái niệm liên quan đến cấu trúc dữ liệu HTA .
- 494.1.3 Một số cách xây dựng cấu trúc dữ liệu HTA.
- 524.2 Định nghĩa đại số mới cho cấu trúc dữ liệu HTA.
- 544.2.2 Một số tính chất của cấu trúc HTA đại số.
- 574.4 Xây dựng các cấu trúc khung cho cấu trúc dữ liệu HTA.
- 584.4.1 Cấu trúc khung map.
- 584.4.2 Cấu trúc khung reduce.
- 594.4.3 Cấu trúc khung zipwith.
- ChínhThầy là người đã đưa ra ý tưởng xây dựng nên cấu trúc dữ liệu HTA songsong là điểm mới trong luận văn tốt nghiệp này.Tôi xin gửi lời cảm ơn chân thành đến Phó giáo sư, Tiến sĩ NguyễnThanh Thủy, Thầy đã góp ý cho tôi ngay từ khi mới bắt đầu làm đề tài,làm rõ các hướng đi cần thiết cho đề tài này.Chuyến đi làm việc 5 tháng tại Viện Tin học Nhật Bản (National Instituteof Informatics) mang lại cho tôi nhiều điều.
- Giáo sư đã hướng dẫn và trao đổi với tôi tận tình trong thờigian làm việc về vấn đề Lý thuyết tính toán trên giải thuật cũng như thư việnlập trình SkeTo do nhóm của ông phát triển tại Viện Tin học Nhật Bản vàĐại Học Tokyo.Tôi xin gửi lời cảm ơn đến Trung tâm tính toán hiệu năng cao -ĐHBKHN, nơi tôi đang làm việc, Trung tâm đã hỗ trợ tôi rất nhiều về mặtchuyên môn cũng như điều kiện cơ sở vật chất để hoàn thành luận văn này.Tôi xin gửi lời cảm ơn đến Phòng thí nghiệm Takeichi - Đại học Tokyonơi tạo điều kiện cho tôi có các buổi thảo luận hàng tuần với nhóm nghiêncứu ở đó trong thời gian làm việc với giáo sư Zhenjiang Hu.Cuối cùng, con muốn cảm ơn gia đình đã động viên, giúp đỡ trong suốtquá trình học tập nói chung và luận văn Thạc sĩ nói riêng, có lẽ nếu thiếu sựv 0.0 Chương 0hỗ trợ tinh thần từ gia đình thì luận văn này khó có thể hoàn thành được.vi Chương 1Giới thiệu luận văn1.1 Lý do chọn đề tàiTính toán song song đang là giải pháp cho các yêu cầu liên quan đến sứcmạnh tính toán và kích thước bộ nhớ.
- Phương pháp chuẩn để tăng hiệu nănglà kết hợp các máy tính hoặc các bộ vi xử lý, để chúng kết hợp với nhau cùngthực thi một chương trình.
- Trướcđây, các chương trình song song được viết ra chủ yếu để giải quyết các bàitoán khoa học trong các viện nghiên cứu.
- Máy tính song song hiếm khi đượcsử dụng cho các ứng dụng phổ thông, chỉ giới hạn cho các bài toán tính toánkhoa học cần bộ nhớ lớn và sức mạnh tính toán.Vài năm trở lại đây, phạm vi của xử lí song song chuyển dần sang cáclĩnh vực mới như Khai phá dữ liệu, tìm kiếm trên web.
- Hơn nữa, việc tạo racác hệ thống song song phân cụm từ các máy PC trở nên dễ ràng hơn nhờcác phần mềm trung gian đang phát triển mạnh mẽ.
- Hơn nữa, hiện nay các bộ vi xử lý đa lõi xuất hiện khắp nơi,sự nổi lên của các kiến trúc mới này khiến cho lập trình song song trở thành1 1.1 Chương 1vấn đề tất yếu.
- Sẽ không lâu nữa, ngành công nghiệp tính toán sẽ phải đốimặt với vấn đề viết các chương trình song song hiệu quả và đúng đắn.Lập trình song song trở thành một thách thức.
- Không giống như chươngtrình tuần tự, chương trình song song được thực thi trên P bộ vi xử lý.
- điềunày là gánh nặng cho lập trình viên để tận dụng hết các bộ vi xử lý mộtcách hiệu quả.
- Nói chung, lập trình viên cần viết thêm các đoạn mã để tiếnhành các tác vụ sau: phân rã miền của bài toán thành P miền con, xác địnhP tác vụ để làm việc với các miền này, sau đó đồng bộ các tác vụ.
- Mặc dù,đây là các khái niệm đơn giản, xong thậm chí những lập trình viên chuyênnghiệp cũng cần những nỗ lực thực sự để hoàn thành chúng.Đối với những lập trình viên đã quen với lập trình tuần tự thì việc viếtcác chương trình song song cũng quan trọng không kém so với việc giảmthời gian thực thi của chương trình.
- Điều này thúc đẩy phát triển các cơ chế lậptrình song song mới, cho phép lập trình viên lập trình dễ dàng như đang viếtchương trình tuần tự, hơn nữa chương trình đó phải chạy nhanh nhất có thểtrên các máy tính song song.Có một số hướng tiếp cận để phát triển các công cụ lập trình song songmức cao.
- Các công cụ này dừng ở mức trừu tượng để che giấu sự thực thibên dưới và giảm thiểu tính phức tạp, do vậy người dùng sẽ nhanh chóngxây dựng các chương trình song song.
- Các công cụ này thể hiện dưới dạnglà một Ngôn ngữ lập trình bậc cao mới hoặc thư viện lập trình song songphức tạp như MPI hay PVM, và do vậy lập trình viên không tốn quá nhiềuthời gian để nghiên cứu nhằm lấp khoảng trống kiến thức giữa lập trình songsong và lập trình tuần tự.
- Tư tưởng sẽ là cố gắng làm cho lập trình viên cóthể viết các chương trình song song như thể đang viết chương trình tuần tự,ngoại trừ một số hàm đặc biệt cần biên dịch cả song song và tuần tự.
- Khichương trình chạy trên máy tính song song, trình biên dịch song song sẽ tựđộng được sử dụng.Lập trình song song theo cấu trúc khung (hay còn gọi là lập trình song2 1.1 Chương 1song có cấu trúc) [3]-[11] đã nổi lên là một cách tiếp cận đầy hứa hẹn đểđạt được mục đích nêu trên.
- 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 trên các thành phần đãtạo sẵn (Ví dụ: các cấu trúc khung, các mẫu có sẵn), các thành phần sẵncó này làm cho chương trình thực thi hiệu quả và làm cho tiến trình songsong hóa trở lên đơn giản.
- Có rất nhiều định nghĩa về cấu trúc khung, nhưngnhìn chung nó là các khuôn mẫu cho tính toán song song, và các tương tác,nó được đóng gói thành các khối như framework, hay template, hay thậmchí là một cấu trúc khung khác.
- Các chương trình song song theo kiểu cấutrúc khung rất dễ hiểu thậm chí với những người lập trình song song ít kinhnghiệm, bởi vì mã nguồn của chương trình nhìn rất giống với một chươngtrình tuần tự có một luồng thực thi duy nhất.Tuy nhiên, chỉ có một vài ứng dụng thực sự được phát triển bằng các cấutrúc khung song song.
- Thứ nhất,giống như các design pattern trong kỹ nghệ phần mềm, các cấu trúc khungsong song được đề cập đến theo cách khá đặc biệt mà chủ yếu dựa trên cácmiền ứng dụng.
- Không có một nguyên lý rõ ràng trong việc thiết kế cấu trúckhung, ví dụ như làm thế nào để tạo các cấu trúc khung mới hoặc kết hợptập các cấu trúc khung khác nhau cho các mục đích khác nhau.
- Thứ hai,bởi vì lập trình song song dựa vào tập cố định các cấu trúc khung song songthô sơ để đặc tả giải thuật song song, nên người lập trình thường khó khănkhi muốn chọn đúng và sau đó tích hợp với nhau để phát triển các chươngtrình song song hiệu quả.
- Trong đa số trường hợp, lý do tại sao người lậptrình cảm thấy miễn cưỡng khi dùng các cấu trúc khung, chỉ đơn giản là vìhọ không chắc chắn liệu các cấu trúc khung đã có có đủ mạnh để giải quyếtvấn đề của họ hay không, và do vậy họ rất dễ từ bỏ.
- Thứ ba, vì giải thuậtsong song được đặc tả bằng các cấu trúc khung, nên tồn tại rất nhiều chi phíthừa.
- Có thể lý giải điều này bằng một trường hợp đơn giản, đó bởi vì cónhiều cấu trúc dữ liệu trung gian không cần thiết được truyền giữa các cấutrúc khung.
- Cuối cùng, vì hầu hết các hệ thống cấu trúc khung được địnhnghĩa dựa trên một số ngôn ngữ mới hoặc đòi hỏi mở rộng ngôn ngữ hiện tại3 1.3 Chương 1bằng các cú pháp mới, và do vậy, dưới góc nhìn của lập trình viên, nó khônghoàn toàn giấu đi được tất cả chi tiết ở mức thấp của lập trình song song.Người lập trình tuần tự (người lập trình song song ít kinh nghiệm) thườngcảm thấy không thoải mái khi sử dụng chúng.Từ những lý do trên dẫn đến đề tài đi sâu tìm hiểu về cách thiết kế, xâydựng cấu trúc khung cho các hệ thống lập trình song song đa lõi.1.2 Mục đích nghiên cứu của luận vănLuận văn có mục đích nghiên cứu sau:• Nghiên cứu hướng tiếp cận lập trình song song theo cấu trúc khung• Nghiên cứu Lý thuyết tính toán trên giải thuật nhằm áp dụng xây dựngcấu trúc khung• Xây dựng cấu trúc khung cho cấu trúc dữ liệu HTAĐối tượng nghiên cứu gồm:• Hệ thống tính toán song song• Ngôn ngữ lập trình song song• Đại số cho lập trìnhPhạm vi nghiên cứu của luận văn giới hạn trong các cấu trúc dữ liệu songsong, thiết kế chương trình dựa trên các lý thuyết về Đại số cho lập trình.1.3 Luận điểm cơ bản và đóng góp mớiXây dựng nên các chương trình song song là công việc phức tạp, người lậptrình cần phải nắm rõ sự điều phối công việc giữa các tiến trình, chính điều4 1.4 Chương 1này là cho lập trình song song khó đi vào thực tế.
- Từ luận điểm này luậnvăn muốn tìm hiểu về phương pháp để xây dựng nhanh chóng và đơn giảncác chương trình song song.Luận điểm cơ bản thứ hai trong luận văn cần phải nói đến đó là việc sửdụng lý thuyết Đại số cho lập trình để xây dựng chương trình.
- Dựa trên lýthuyết này, việc định nghĩa ra các cấu trúc đại số mới là rất thuận tiện, đồngthời việc suy luận, tính toán trên các cấu trúc đại số là chặt chẽ dựa trêncác định lý, bổ đề và các luật đại số.Đóng góp mới của đề tài là đã đưa ra được định nghĩa đại số cho cấutrúc dữ liệu HTA, homomorphism và các cấu trúc khung trên cấu trúc dữliệu này.1.4 Cấu trúc luận vănLuận văn được chia thành 5 chương, tổ chức như sau:• Chương một đưa các các vấn đề cơ bản có liên quan đến luận văn.• Chương hai trình bày cơ bản về hướng tiếp cận lập trình song songtheo cấu trúc khung, mô hình và tư tưởng lập trình theo cấu trúc khungđược đưa ra trong chương này.
- Chương này cũng trình bày tóm tắt 4cấu trúc khung thường hay được sử dụng, đó là: cấu trúc khung chia-trị, cấu trúc khung kết hợp lặp, cấu trúc khung cluster, và cấu trúckhung hàng đợi công việc.• Chương ba trình bày về Lý thuyết tính toán trên giải thuật, đây khôngphải là một lý thuyết mới, tuy nhiên việc áp dụng nó để xây dựng cấutrúc khung lại là một hướng tiếp cận mới.
- Sự kết hợp này cho phépdễ dàng xây dựng nên các cấu trúc khung một cách có hệ thống.
- Tuynhiên theo lý thuyết này, các cấu trúc khung phải được xây dựng trên5 1.4 Chương 1các cấu trúc dữ liệu cơ bản.
- Chương này cũng trình bày thiết kế củacác cấu trúc khung cho hai kiểu dữ liệu là Danh sách và Ma trận.• Chương bốn trình bày về cấu trúc dữ liệu HTA mà tác giả đã xâydựng dựa trên sự kết hợp của lập trình song song theo cấu trúc khungvà Lý thuyết tính toán trên giải thuật.• Chương năm nêu kết luận và hướng phát triển của luận văn.6 Chương 2Lập trình song song theo kiểucấu trúc khungChương này giới thiệu về Lập trình song song theo kiểu cấu trúc khung.
- Cáckhái niệm cơ bản về hướng tiếp cận lập trình có cấu trúc được đưa ra.
- Cuốichương là một số các cấu trúc khung phổ biến đã được sử dụng trong lậptrình.2.1 Đặt vấn đềÝ tưởng của hệ thống lập trình theo cấu trúc khung dựa trên hai vấn đề sau.Thứ nhất, trong ngữ cảnh lập trình tuần tự, những thách thức đặt ra đểtạo nên các giải thuật tốt cần được liên tục nghiên cứu mở rộng.
- Khi kinhnghiệm lập trình nhiều hơn, lại nảy sinh việc chọn lựa kỹ thuật thực thi chogiải thuật, một kỹ thuật có thể phù hợp với một số vấn đề nhưng cũng có thểkhông tốt với các vấn đề khác.
- Dochúng ta đã biết cách thực thi cấu trúc tính toán cơ bản của từng kỹ thuật,7 2.1 Chương 2nên chỉ cần đưa ra những chi tiết cần thiết cho chương trình mới.Dựa vào ý tưởng trên, có thể đưa ra một hệ thống theo phương pháp nhưsau: Ban đầu, cần xác định tập các kỹ thuật giống nhau, mỗi kỹ thuật cócấu trúc tính toán có thể thực thi song song được.
- Nếu các cấu trúc cơ bảncó thể song song hóa được thì các thể hiện của cấu trúc đó cũng có thể cókhả năng song song hóa.
- Thay vì tạo ra các cấu trúc lập trình song song mới,ta cố gắng nhúng các kỹ thuật song song trong các cấu trúc cú pháp của môhình lập trình, và do đó người dùng sẽ dùng nó như là cấu trúc chính trongchương trình của họ.
- Hơn nữa, ta mong muốn dưới góc nhìn của người dùngthì các cấu trúc này là không song song.Tư tưởng của vấn đề thứ hai là làm sao để giải quyết vấn đề thứ nhấttheo cách mạch lạc và ở mức cao.
- Đây chính là khái niệm “Hàm bậc cao”.“Hàm bậc cao” thể hiện sức mạnh của các ngôn ngữ lập trình hàm.
- Dưới đâyđưa ra giải thích ngắn gọn về khái niệm “Hàm bậc cao”.Các hàm đơn giản nhận đối số đầu vào là một số kiểu dữ liệu nào đó, dữliệu trả về sẽ có một kiểu dữ liệu nào đó.
- Kiểu của hàm này được mô tả như sau:square : int → intMột số hàm có thể hoạt động dựa trên các dữ liệu gồm nhiều hơn một kiểudữ liệu, bởi các hoạt động mà hàm đó tiến hành không quan tâm đến chitiết đối số, mà chỉ là cấu trúc của đối số đó.
- Ví dụ điển hình cho hàm kiểuđó là hàm “head”, hàm này có đối số đầu vào là một danh sách các mục cókiểu dữ liệu nào đó, hàm sẽ trả về mục dữ liệu đầu tiên trong danh sách.
- Rõràng ta thấy kiểu dữ liệu của các mục dữ liệu là không ảnh hưởng đối vớihàm, và các hàm như vậy được gọi là có tính chất đa hình.
- Kiểu của hàm8 2.1 Chương 2được biểu thị dùng các biểu tượng giả để biểu diễn các kiểu dữ liệu tùy ý.Như vậy, “head” có kiểu là:head : [a.
- atrong đó, dấu ngoặc vuông biểu thị cho “danh sách” và “a” biểu thị cho bấtkỳ kiểu dữ liệu nào.Hàm bậc cao phức tạp hơn một chút.
- Hàm kết quả là sự kết hợp có cấu trúc giữa các hàmđối số và một số hàm khác có thể có

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt