Đề tài Lập trình song song

Add your company slogan LOGO Trường Đại học Cửu Long Khoa Công Nghệ Thông Tin Đề tài Add your company slogan LOGO Slide 2 Add your company slogan LOGO Slide 3 Add your company slogan LOGO “Số lượng transistor trên mỗi đơn vị inch vuông sẽ tăng lên gấp đôi sau mỗi năm.” Slide 4 Nguồn: Internet Gordon Moore (1929) Add your company slogan LOGO Slide 5 Nguồn: www.developers.net Add your company slogan LOGO Slide 6 Đa nhiệm trong hệ thống đơn lõi Add your company slogan LOGO Slide 7 Đa luồng trong hệ thống đa lõi Add your company slogan LOGO (Parallel Computing) Là chia công việc ra thành các phần nhỏ và thực hiện đồng thời bởi một hệ thống gồm nhiều máy tính kết nối với nhau (Multi-Computer)hoặc nhiều bộ vi xử lý (Multi-Processor) hay bộ vi xử lý đa nhân (Multi-Core). Parallel Programing Là việc lập trình để tách ra các công việc nhỏ và sắp xếp để xử lý song song. Slide 8 Add your company slogan LOGO p: số lượng CPU. T1: thời gian thực thi thuật toán tuần tự. Tp: thời gian thực thi thuật toán song song. Sp: Tốc độ xử lý. Ep: hiệu quả thực hiện phép toán song song so với tuần tự. Slide 9 Add your company slogan LOGO Slide 10 Sự ra đời và phát triển mạnh mẽ của các dòng chip đa lõi (Multi-Core) tạo cơ hội cho sự ra đời của tính toán và lập trình song song. Add your company slogan LOGO Slide 11 Add your company slogan LOGO  Tiến trình là một chương trình đang chạy: - Bộ nhớ được cấp phát bởi hệ điều hành. - Thường không có sự chia sẻ bộ nhớ giữa các tiến trình với nhau.  Ví dụ: Slide 12 Add your company slogan LOGO  Tiểu trình là một dòng điều khiển tuần tự: - Chạy trong không gian bộ nhớ của tiến trình. - Nó có bộ đếm chương trình (program counter) và ngăn xếp(stack frame) riêng. Ví dụ: Trong chương trình WINWORD.exe có các luồng: luồng ghi nhận nhập kí tự, luồng kiểm tra chính tả, luồng hiển thị lên màn hình, luồng quản lý giao diện… Slide 13 Add your company slogan LOGO Slide 14 Add your company slogan LOGO  Born - Mới được tạo ra.  Ready (Runnable) - Sẵn sàng thực thi.  Running - Đang thực thi.  Dead - Bị hệ thống đánh dấu loại bỏ.  Blocked - Không cho phép xử lý.  Sleeping - Khi phương thức Sleep được gọi.  Waiting - Trạng thái ngừng để chờ. Slide 15 Add your company slogan LOGO Slide 16 Add your company slogan LOGO Multi-Computer: nhiều máy tính được kết nối với nhau để cùng xử lý một chương trình. Slide 17 Mô hình Multi-Computer. Add your company slogan LOGO Multi-Processor/Multi-Core: Nhiều bộ vi xử lý trong cùng một máy tính hoặc một bộ vi xử lý gồm nhiều CPU. Slide 18 Mô hình Multi-Processor. Mô hình Multi-Core. Add your company slogan LOGO Hệ thống lai: Kết hợp giữa hai hệ thống trên. Dùng để tạo nên một hệ thống tính toán khổng lồ và phức tạp. Slide 19 Mô hình hệ thống lai. Add your company slogan LOGO  Lập trình song song trên Java.  Lập trình song song trên C#.NET.  Một số ngôn ngữ có thư viện hàm hỗ trợ song song như C/C++, FORTRAN, Python, Ada… cần cài đặt trình biên dịch song song: OpenMP, MPI, MPICH, PyMPI… Slide 20 Add your company slogan LOGO (Message Passing Interface) là một mô hình lập trình song song sử dụng cơ chế truyền thông điệp.  MPI 1.0 phát hành năm 1994.  MPI 2.0 phát hành năm 1997. Thư viện hỗ trợ: Fortran, C, C++… Slide 21 Add your company slogan LOGO Slide 22 Add your company slogan LOGO Gồm ba giai đoạn chính:  Phân chia chương trình thành các công việc con (Sub-task Decomposition).  Phân tích sự phụ thuộc (Dependence Analysic).  Định thời các công việc (Task Scheduling). Slide 23 Add your company slogan LOGO Slide 24 Các thread chạy bên trong máy ảo JVM (Java) hoặc trình biên dịch song song (Ngôn ngữ khác). Mỗi thread có biến dữ liệu và ngăn xếp riêng được cấp phát bởi JVM. JVM chịu sự quản lý của Hệ điều hành. Add your company slogan LOGO Slide 25 Hệ điều hành cấp phát bộ nhớ cho từng ứng dụng riêng biệt. Vì vậy các biến và vùng dữ liệu của các chương trình (tiến trình) khác nhau là khác nhau. Add your company slogan LOGO + Giao tiếp và chuyển đổi nhanh. + Tách công việc để xử lý song song, tiết kiệm thời gian. + Tận dụng tối đa sức mạnh đa lõi. + Khả năng mở rộng và tăng tốc độ tính toán. Slide 26 - Cơ chế giao tiếp, chuyển đổi phức tạp. - Mất thời gian cho việc quản lý đồng bộ dữ liệu. - Khó lập trình, kiểm tra lỗi. - Hình thành hệ thống phức tạp đòi hỏi trình độ cao để có thể quản lý. Add your company slogan LOGO Mỗi thread có một độ ưu tiên khác nhau và có mối quan hệ với nhau. Thread có quyền ưu tiên cao có thể chuyển sang hoặc gọi một thread khác gọi là Context Switching.  Một thread có thể tự động sinh ra thread khác.  Thread có độ ưu tiên cao hơn có thể giành quyền sử dụng CPU từ thread ưu tiên thấp hơn.  Nếu quyền ưu tiên ngang nhau thì xử lý theo cơ chế của hệ điều hành. Slide 27 Add your company slogan LOGO Đồng bộ hóa (Synchronization): Hai hay nhiều thread có thể cùng truy cập vào tài nguyên tại một thời điểm. Các thread được đồng bộ hoá trong Java sử dụng thông qua một Monitor (Semaphore - “Cột tín hiệu”). Chỉ có một thread được sử dụng một monitor vào bất kỳ một khoảng thời gian nào. Slide 28 Add your company slogan LOGO Có hai cách để đồng bộ hoá các thread:  Sử dụng method được đồng bộ hóa. Trong Java, mỗi thread có một monitor cho đến khi từ khóa Synchronized được gọi.  Sử dụng phát biểu (Statement) được đồng bộ hóa. Phát biểu đồng bộ hóa chứa block được đồng bộ hóa, bên trong đặt những đối tượng và những method được đồng bộ hóa. Slide 29 Add your company slogan LOGO Một thread đôi khi cần giao tiếp với những thread khác trong suốt quá trình xử lý. Các lập trình viên gọi đó là Inter-Process Communication (Giao tiếp trong tiến trình). Slide 30 Add your company slogan LOGO Slide 31 Add your company slogan LOGO  Khởi dựng thread bằng Runnable Interface và extends lớp Thread.   Dùng nhiều thread trong một chương trình.  Cài đặt quyền ưu tiên cho thread.  Thực thi đồng bộ hóa các thread.  Đồng bộ dùng method.  Đồng bộ dùng phát biểu đồng bộ hóa.  Giao tiếp giữa các thread.  Sử dụng thread trong Swing. Slide 32 Add your company slogan LOGO Slide 33 class MyThread implements Runnable { Thread t; MyThread() { t = new Thread(this, “My thread”); t.start(); } public void run() { System.out.println("Child thread started"); System.out.println("Child thread terminated"); } } class Demo { public static void main(String args[]) { new MyThread(); System.out.println("Main thread started"); System.out.println("Main thread terminated"); } } Add your company slogan LOGO Một số ví dụ:  Google.com dùng phương thức tìm kiếm song song; khi ta ghõ một từ khóa thì máy chủ tại VN tìm kiếm từ khóa cho ra kết quả ở VN; đồng thời cũng cho ra kết quả các tiếng khác (tiếng Anh, ..) vì thế Google là một trong những trang web dùng lập trình song song mà ta dễ thấy nhất. 34 Add your company slogan LOGO Slide 35  [1] Jim Keogh (2004), Java Dymistyfied, Chapter 12 Multithreading.  [2] www.developers.net  [3] www.google.com.vn  [4] Bách Khoa Toàn Thư Mở  [5] Nguyễn Tuấn Anh (2006), Parallel Computing. Add your company slogan LOGO Slide 36