Tài liệu Nghiên cứu và ứng dụng các thuật toán giải các bài toán tính toán trên computer cluster

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ---------------- PHAN THỊ GIANG NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN GIẢI CÁC BÀI TOÁN TÍNH TOÁN TRÊN COMPUTER CLUSTER LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 ii LỜI CAM ĐOAN Học viên xin khẳng định tất cả các kết quả được trình bày trong luận văn là của riêng học viên, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì không trung thực, học viên xin hoàn toàn chịu trách nhiệm. Học viên Phan Thị Giang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii LỜI CẢM ƠN Luận văn được thực hiện tại trường Đại học Công nghệ Thông tin và Truyền Thông – Đại học Thái Nguyên dưới sự hướng dẫn của GS.TS Nguyễn Thanh Thuỷ. Trước hết học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn Thanh Thuỷ, người đã có những định hướng, những kiến thức quý báu, những lời động viên và chỉ bảo giúp học viên vượt qua những khó khăn để học viên hoàn thành tốt luận văn của mình. Học viên xin được bày tỏ lòng cảm ơn và sự kính trọng của mình đến các thầy cô giáo Trường Đại học Công nghệ Thông tin và Truyền Thông, Đại học Thái Nguyên, các thầy bên Viện Công nghệ thông tin, đặc biệt là các thầy cô giáo đã giảng dạy và giúp đỡ học viên trong suốt quá trình học tập tại trường. Học viên cũng đặc biệt cảm ơn tới bạn bè lớp Cao học K9, các đồng nghiệp đã luôn động viên, giúp đỡ học viên trong quá trình học tập và công tác, để học viên hoàn thành nhiệm vụ được giao. Xin chân thành cảm ơn sự quan tâm, giúp đỡ, chia sẻ, động viên về tinh thần và vật chất của người thân trong gia đình, bạn bè để học viên hoàn thành luận văn. Thái Nguyên, tháng 10 năm 2012 Học viên Phan Thị Giang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv MỤC LỤC LỜI CAM ĐOAN ............................................................................................. 1 LỜI CẢM ƠN ................................................................................................. iii MỤC LỤC ........................................................................................................iv MỞ ĐẦU ........................................................................................................... 1 1. Lý do chọn đề tài ........................................................................................ 1 2. Đối tượng và phạm vi nghiên cứu .............................................................. 1 3. Hướng nghiên cứu của đề tài ...................................................................... 1 4. Phương pháp nghiên cứu ............................................................................ 2 5. Ý nghĩa khoa học của đề tài........................................................................ 2 6. Cấu trúc của luận văn ................................................................................. 2 Chƣơng 1. LÝ THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN .............. 3 1.1. Giới thiệu chung ...................................................................................... 3 1.2. Lý thuyết xử lý song song ....................................................................... 3 1.2.1. Khái niệm .......................................................................................... 3 1.2.2. Phân biệt xử lý song song với tuần tự ............................................... 3 1.2.3. Phân loại máy tính song song............................................................ 6 1.2.4. Song song hóa trong máy tính tuần tự ............................................ 11 1.3. Lý thuyết xử lý phân tán ........................................................................ 14 1.3.1. Khái niệm ........................................................................................ 14 1.3.2. Tính toán phân tán ........................................................................... 15 1.4. Các phương pháp giải bài toán bằng xử lý song song và phân tán ....... 15 1.4.1. Mô hình gửi/nhận thông báo ........................................................... 16 1.4.3. Mô hình lập trình ............................................................................. 19 1.4.4. Lập trình trên cụm máy tính ............................................................ 23 Chƣơng 2. CLUSTER VÀ TÍNH TOÁN PHÂN TÁN BẰNG CLUSTER26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v 2.1. Mô hình chung của hệ thống Cluster ..................................................... 26 2.1.1. Mô hình ........................................................................................... 26 2.1.2. Chế độ hoạt động của Cluster ......................................................... 27 2.1.3. Một số ứng dụng trong Cluster ....................................................... 29 2.2. Các ưu điểm của hệ thống Cluster ......................................................... 30 2.3. Các thành phần của Cluster Service ...................................................... 32 2.4. Nguyên tắc hoạt động của Server Cluster ............................................. 37 2.5. Cách cài đặt và cấu hình Cluster trên Linux.......................................... 42 2.5.1. Khái niệm LVS................................................................................ 43 2.5.2. Các mô hình LVS ............................................................................ 44 2.5.3. Mô hình Virtual Server via NAT .................................................... 44 2.5.4. Mô hình Virtual Server via Tunneling ............................................ 45 2.5.5. Mô hình Virtual Server via Direct Routing .................................... 46 2.5.6. Cách triển khai các mô hình ............................................................ 47 2.5.7. Các bước triển khai LVS via Direct Routing .................................. 47 2.6. Tính toán phân tán bằng Cluster ............................................................ 53 2.6.1. Lập trình trên môi trường MPI ........................................................ 53 2.6.2. Cài đặt MPICH2 .............................................................................. 55 2.6.3. Tính toán trên MPI .......................................................................... 57 2.6.4. Các mô hình tương tác trong lập trình MPI .................................... 61 Chƣơng 3. CÀI ĐẶT THỬ NGHIỆM .......................................................... 66 3.1. Phương trình vi phân đạo hàm riêng ..................................................... 66 3.2. Phương trình Laplace............................................................................. 67 3.3. Công thức lặp Jacobi ............................................................................. 69 3.3.1. Giá trị riêng của ma trận lặp Jacobi ................................................ 70 3.3.2. Tính toán Jacobi .............................................................................. 71 3.4. Song song hóa thuật toán ....................................................................... 73 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi 3.5. Kết quả thực hiện ................................................................................... 74 3.5.1. Thông tin chung về hệ thống .............................................................. 74 3.5.2. Giao diện và lệnh thực hiện............................................................. 74 3.5.3. Kết quả thực hiện tuần tự ................................................................ 77 3.5.4. Kết quả thực hiện thực hiện xử lý song song trên nhiều máy ......... 77 3.6. Nhận xét và đánh giá ............................................................................. 78 KẾT LUẬN VÀ KIẾN NGHỊ ....................................................................... 79 1. Kết luận ..................................................................................................... 79 2. Kiến nghị................................................................................................... 79 TÀI LIỆU THAM KHẢO ............................................................................. 80 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii DANH MỤC HÌNH VẼ Hình 1.1. Mô hình xử lý tuần tự ........................................................................ 4 Hình 1.2. Mô hình xử lý song song ................................................................... 4 Hình 1.3. Mô hình của kiến trúc SISD.............................................................. 7 Hình 1.4. Mô hình của kiến trúc SIMD ............................................................ 8 Hình 1.5. Mô hình MISD .................................................................................. 8 Hình 1.6. Mô hình của kiến trúc MISD ............................................................ 9 Hình 1.6.1. Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai đoạn 10 Hình 1.7. (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU ........... 10 Hình 1.8. Mô hình của kiến trúc MIMD ......................................................... 11 Hình 1.9. Hệ thống bộ nhớ phân cấp .............................................................. 13 Hình 1.10. Dịch đơn chương trình, đa thao tác dữ liệu .................................. 20 Hình 1.11. Sự trao đổi thông điệp giữa hai tiến trình ..................................... 22 Hình 1.12. Sự trao đổi thông điệp của các máy tính trong hệ PVM ............... 24 Hình 1.13. Gọi hàm pvm_psend() và pvm_precv() ........................................ 25 Hình 2.1. Nguyên lý hoạt động của một Cluster ............................................. 28 Hình 2.2. Linux Virtual Server ....................................................................... 43 Hình 2.3. Mô hình Virtual Server via NAT ..................................................... 45 Hình 2.4. Mô hình Virtual Server via Tunneling ............................................ 46 Hình 2.5. Mô hình Virtual Server via Direct Routing ................................... 47 Hình 2.6. Mô hình chuẩn gồm 4 server ........................................................... 48 Hình 2.7. 6 vi xử lý kết nối với nhau thành hình tròn .................................... 63 Hình 2.8. Các vi-xử-lý kết nối với nhau thành lưới ........................................ 64 Hình 3.1. Miền Ω và đường biên ∂Ω .............................................................. 67 Hình 3.2. Sai phân hữu hạn (Finite difference) .............................................. 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn viii Hình 3.3. Phương trình Laplace/Poisson biểu diễn trên một hình lưới hình chữ nhật với Nx x Ny điểm. .................................................................................... 69 Hình 3.4. Cấu trúc dải của ma trận lặp Jacobi cho phương trình Laplace/ Poisson ........................................................................................................... 70 Hình 3.5. Thực hiện tính toán Jacobi trên một đối tượng ............................... 73 Hình 3.6a. Đăng nhập vào trung tâm với tên ccs1.hnue.edu.vn ..................... 75 Hình 3.6b. Nhập thông tin tài khoản ............................................................... 75 Hình 3.6c. Sử dụng phần mềm winscp để đăng nhập vào hệ thống ............... 75 Hình 3.6d. Các file trên tài khoản đăng nhập vào hệ thống ............................ 76 Hình 3.7. Thời gian thực hiện trên tính toán tuần tự > 200s ............................ 77 Hình 3.8a. Lệnh qsub –q l1 –l nodes=2:ppn=4 Laplace.script trên 2 ............ 77 Hình 3.8b. Kết quả thời gian thực hiện ........................................................... 77 Hình 3.8c. Kết quả lưu trữ trên tệp. dat .......................................................... 78 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay có rất nhiều bài toán phức tạp và các ứng dụng thực tế cần phải tính toán, giải trên một số lượng lớn các dữ liệu, nếu chúng ta sử dụng máy tính thông thường để thực thi thì sẽ mất rất nhiều thời gian và công sức. Để giải quyết được những khó khăn trên chúng ta có thể sử dụng một hệ thống máy tính được kết nối với nhau gọi là Computer Cluster. Trong cuốn luận văn này học viên đã thực hiện tìm hiểu cách thức xây dựng một Computer Cluster cho việc giải quyết bài toán lớn (Phương trình Laplace với công thức lặp Jacobi) bằng cách song song hóa để đưa ra sự so sánh về thời gian thực hiện khi xử lý tuần tự. 2. Đối tƣợng và phạm vi nghiên cứu - Lý thuyết xử lý song song, xử lý phân tán. - Hệ thống Computer Cluster. - Một số bài toán thực tế trong Khoa học kỹ thuật. - Ngôn ngữ xử lý song song MPI (Message Passing Interface). 3. Hƣớng nghiên cứu của đề tài - Nghiên cứu các lý thuyết xử lý song song, xử lý phân tán. - Nghiên cứu cách xây dựng và vận hành Computer Cluster, tìm hiểu các khả năng của Computer Cluster. Nghiên cứu cách cài đặt các thuật toán xử lý song song trên Computer Cluster. - Giải quyết một số bài toán thực tế trong khoa học kỹ thuật. - Tìm hiểu thêm về ngôn ngữ xử lý song song MPI. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 4. Phƣơng pháp nghiên cứu - Về lý thuyết: + Ứng dụng các kết quả của lý thuyết xử lý song song. + Nắm bắt cách thức xây dựng và hoạt động của Computer Cluster, từ đó xây dựng và triển khai Computer Cluster theo yêu cầu của các bài toán. + Nghiên cứu triển khai các thuật toán xử lý song song trên Computer Cluster. - Về thực nghiệm: + Xây dựng và triển khai Computer Cluster. + Cài đặt liên quan tới bài toán thực tế. 5. Ý nghĩa khoa học của đề tài Luận văn nghiên cứu chi tiết lý thuyết xử lý song song và xử lý phân tán, nghiên cứu việc cài đặt hệ thống Cluster server và ứng dụng để giải phương trình vi phân đạo hàm riêng Laplace, một phương trình có ứng dụng lớn trong khoa học kỹ thuật và có cách giải rất phức tạp. Các kết quả khả quan thu được sẽ minh chứng nói lên triển vọng tính toán song song của Computer Cluster. 6. Cấu trúc của luận văn Nội dung của luận văn được chia thành 3 chương như sau: Chương I: Lý thuyết xử lý song song và phân tán. Chương II: Cluster và tính toán phân tán bằng Cluster. Chương III: Cài đặt thử nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chƣơng 1 LÝ THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN Trong chương này chúng ta sẽ tìm hiểu thế nào là xử lý song song và xử lý phân tán. Đồng thời đưa ra các mô hình diễn tả cách thức hoạt động trong việc xử lý dữ liệu. 1.1. Giới thiệu chung Hiện nay lý thuyết xử lý song song và xử lý phân tán đang được quan tâm và nghiên cứu để giải quyết những bài toán lớn và cần tốc độ tính toán cao mà trước đó một máy tính không thể làm được. Nó là một vấn đề quan tâm đối với các nhà nghiên cứu ngày nay để sử dụng chiến thuật hợp tác tương tự trong việc xây dựng các siêu máy tính có thể thực hiện hàng nghìn tỉ tính toán trong một giây. Hầu hết các siêu máy tính đều sử dụng phương pháp xử lý song song, chứa một giàn các bộ vi xử lý cực nhanh, làm việc đồng loạt để giải quyết những bài toán phức tạp, dữ liệu lớn như dự báo thời tiết hoặc mô phỏng vụ nổ hạt nhân, vv… 1.2. Lý thuyết xử lý song song 1.2.1. Khái niệm Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một bài toán, nói chung xử lý song song được thực hiện trên những hệ thống đa bộ xử lý [7]. 1.2.2. Phân biệt xử lý song song với tuần tự Trong tính toán tuần tự với một bộ xử lý (BXL) thì tại mỗi thời điểm chỉ thực hiện được một phép toán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Hình 1.1: Mô hình xử lý tuần tự - Bài toán được tách thành một chuỗi các câu lệnh rời rạc - Các câu lệnh được thực hiện một cách tuần tự - Tại mỗi thời điểm chỉ thực hiện được một câu lệnh Trong tính toán song song thì nhiều BXL cùng kết hợp với nhau để giải quyết một bài toán nên sẽ giảm được thời gian xử lý vì mỗi thời điểm có thể thực hiện đồng thời nhiều phép toán. Hình 1.2. Mô hình xử lý song song Mục đích của xử lý song song: là thực hiện tính toán nhanh trên cơ sở sử dụng nhiều BXL đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý song song cũng giải được những bài toán lớn hơn, phức tạp hơn. Ba yếu tố chính dẫn đến việc xây dựng các hệ thống xử lý song song: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây dựng những hệ thống có nhiều BXL với giá thành hợp lý. 2. Sự phát triển của công nghệ mạch tích hợp (VLSI) cho phép tạo ra những hệ thống có hàng triệu transistor trên một chip. 3. Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới hạn, không thể cải tiến thêm được do vậy dẫn tới đòi hỏi phải thực hiện xử lý song song. Những yếu tố trên thúc đẩy các nhà nghiên cứu phải tập trung khai thác công nghệ xử lý song song. Vấn đề xử lý song song liên quan trực tiếp đến kiến trúc máy tính, phần mềm hệ thống (hệ điều hành), thuật toán và ngôn ngữ lập trình, v.v… Một máy tính song song: là một tập các BXL (thường là cùng một loại) kết nối với nhau theo một kiến trúc nào đó để có thể hợp tác trong hoạt động và trao đổi dữ liệu được với nhau [5]. Các máy tính song song có thể phân thành nhiều loại dựa vào các đặc trưng của các kiến trúc và việc tổ chức bộ nhớ. Phần lớn các hệ điều hành ngày nay đều hỗ trợ đa xử lý/đa nhiệm và cho phép thực hiện việc xử lý song song. Như vậy, để xử lý song song chúng ta phải có nhiều BXL (các đơn vị tính toán độc lập) cùng hoạt động và quan trọng hơn là chúng ta phải thiết kế các thuật toán để chúng cùng tham gia "giải quyết một bài toán". Nói cách khác, những tiến trình thực hiện trên mỗi BXL phải trao đổi dữ liệu với nhau để giải quyết một bài toán cho trước. Trường hợp ngược lại thì đó không phải là xử lý song song. Chúng ta dễ nhận thấy là độ phức tạp của xử lý song song sẽ lớn hơn xử lý tuần tự rất nhiều, tập trung chủ yếu ở phương diện truyền thông và sự đồng bộ các tiến trình. Một trong các mục đích chính của xử lý song song là nghiên cứu và xây dựng những thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 là phát triển các thuật toán song song. Câu hỏi tự nhiên là đánh giá một thuật toán song song như thế nào được gọi là thích hợp cho xử lý song song? Đối với thuật toán tuần tự thì chúng ta có thể thống nhất cách đánh giá dựa vào thời gian thực hiện thuật toán, không gian bộ nhớ và khả năng lập trình, v.v... Đánh giá thuật toán song song thì phức tạp hơn nhiều, ngoài những tiêu chuẩn trên còn phải bổ sung thêm những tham số về số BXL, khả năng của các bộ nhớ cục bộ, sơ đồ truyền thông và các giao thức đồng bộ hoá, v.v... Để cài đặt các thuật toán song song trên các máy tính song song chúng ta phải sử dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình song song đang được sử dụng như: Fortran 90, nCUBE C, Occam, C-Linda, PVM với C/C++, CDC 6600, v.v... 1.2.3. Phân loại máy tính song song Dựa vào các đặc tính về số lượng BXL, số chương trình thực hiện, cấu trúc bộ nhớ, v.v..., Michael Flynn (1966) [8] đã đưa ra cách phân loại nổi tiếng được nhiều người chấp nhận. Máy tính song song được phân chia thành các loại: + SISD: Single Instruction Stream, Single Data Stream: Đơn luồng lệnh, đơn luồng dữ liệu. + SIMD: Single Instruction Stream, Multiple Data Stream: Đơn luồng lệnh, đa luồng dữ liệu. + MISD: Multiple Instruction Stream, Single Data Stream: Đa luồng lệnh, đơn luồng dữ liệu. + MIMD: Multiple Instruction Stream, Multiple Data Stream: Đa luồng lệnh, đa luồng dữ liệu. a) Mô hình SISD (Simple Instruction Simple Data) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi register được gọi là bộ đếm chương trình được sử dụng để nạp địa chỉ của lệnh tiếp theo khi xử lý tuần tự và kết quả là thực hiện theo một thứ tự xác định của các câu lệnh. Hình 1.3 mô tả hoạt động của máy tính theo mô hình SISD. Hình 1.3. Mô hình của kiến trúc SISD Mô hình SISD còn được gọi là SPSD (Simple Program Simple Data), đơn chương trình và đơn luồng dữ liệu. b). Mô hình SIMD (Simple Instruction Multiple Data) Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý (nhiều hơn một đơn vị) thực hiện theo một luồng các câu lệnh. CU phát sinh tín hiệu điều khiển tới tất cả các phần tử xử lý, những BXL này cùng thực hiện một phép toán trên các mục dữ liệu khác nhau, nghĩa là mỗi BXL có luồng dữ liệu riêng. Mô hình SIMD còn được gọi là SPMD, đơn chương trình và đa luồng dữ liệu. Đây chính là mô hình máy tính phổ biến có trên thị trường như: DAP và Connection Machine CM-2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Hình 1.4. Mô hình của kiến trúc SIMD c) Mô hình MISD (Multiple Instruction Simple Data) Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn được gọi là MPSD (đa chương trình, đơn luồng dữ liệu). Hình 1.5. Mô hình MISD Kiến trúc kiểu này có thể chia thành hai nhóm:  Lớp các máy tính yêu cầu những đơn vị xử lý (PU) khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến trúc khó và hiện nay chưa có loại máy tính nào được sản xuất theo loại này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Hình 1.6. Mô hình của kiến trúc MISD  Lớp các máy tính có các luồng dữ liệu được gửi tuần tự theo dãy các CPU liên tiếp. Đây là loại kiến trúc hình ống, xem xét như sau: Nguyên lý hình ống (pipelined) dựa vào phương pháp phân đoạn hoặc chia nhỏ một tiến trình tính toán thành một số đoạn nhỏ hơn để thực hiện trong các pha liên tiếp. Tất cả các giai đoạn của một tiến trình được thực hiện tuần tự, khi thực hiện xong thì bắt đầu thực hiện của tiến trình tiếp theo. Mỗi pha thực hiện xong sẽ gửi kết quả cho pha tiếp theo. Như vậy, trong cách thực hiện theo nguyên lý hình ống, khi một giai đoạn công việc đang thực hiện thì một giai đoạn khác có thể nạp dữ liệu vào và dữ liệu vào của giai đoạn này có thể là kết quả của giai đoạn trước nó. Ví dụ, hình 1.6.1 mô tả một tiến trình được phân thành 4 giai đoạn thực hiện tuần tự, nhưng có thể thực hiện song song theo nguyên lý hình ống để tăng tốc độ tính toán khi phải thực hiện nhiều tiến trình như thế. Một tiến trình được chia thành 4 giai đoạn: Thực hiện tuần tự hai tiến trình phải qua 8 giai đoạn: Thực hiện theo hình ống hai tiến trình trên chỉ cần trải qua 5 giai đoạn: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Hình 1.6.1. Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai đoạn Nếu ký hiệu Si là thời gian cần thiết để thực hiện giai đoạn thứ i thì: Tổng thời gian tính toán tuần tự là: 2*(S1 + S2 + S3+ S4) Tổng thời gian tính toán hình ống là: S1 + S2 + S3+ S4 + S4 Nguyên lý hình ống có thể áp dụng theo hai mức:  Hình ống theo đơn vị số học: Các đơn vị số học và logic ALU được tổ chức thành mảng, các phép toán bên trong được thực hiện theo nguyên lý hình ống (hình 1.7.(a)).  Hình ống theo đơn vị câu lệnh: Các đơn vị điều khiển CU được phân đoạn và tổ chức theo hình ống (hình 1.7.(b)). Hình 1.7.(a) Xử lý hình ống theo ALU (b) Xử lý hình ống theo CU d) Mô hình MIMD (Multiple Instruction Multiple Data) Máy tính loại MIMD còn gọi là đa BXL, trong đó mỗi BXL có thể thực hiện những luồng lệnh (chương trình) khác nhau trên các luồng dữ liệu riêng. Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào được bộ nhớ chung (global) khi cần, do vậy giảm thiểu được sự trao đổi giữa các BXL trong hệ thống. Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 hỗ trợ xử lý song song cao nhất và đã có nhiều máy tính được sản xuất theo kiến trúc này, ví dụ: BBN Butterfly, Alliant FX, iSPC của Intel, v.v... Luồng lệnh 1 CU 1 CU 2 Luồng lệnh 2 . . . CU n Phần tử xử lý 1 Phần tử xử lý 2 . . . Luồng lệnh n Phần tử xử lý n Luồng dữ liệu 1 Luồng dữ liệu 2 Luồng dữ liệu n Hình 1.8. Mô hình của kiến trúc MIMD 1.2.4. Song song hóa trong máy tính tuần tự Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế. Nhưng cấu trúc phần cứng thường là trong suốt đối với những người lập trình. Sau đây chúng ta tìm hiểu về kỹ thuật song song áp dụng trong các máy tính có một BXL. a) Đa đơn vị chức năng Hầu hết các máy tính truyền thống chỉ có một đơn vị số học và logic (ALU) trong BXL. Ở mỗi thời điểm nó chỉ có thể thực hiện một chức năng. Nhiều máy tính thực tế hiện nay có thể có nhiều đơn vị chức năng (nhất là những chức năng chuyên biệt) và những đơn vị này có thể thực hiện song song được. Ví dụ máy CDC 6600 (thiết kế năm 1964) có 10 đơn vị chức năng được tổ chức trong một BXL. Những đơn vị chức năng này độc lập với nhau và do vậy có thể thực hiện đồng thời. Thường đó là các đơn vị thực hiện các Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 phép toán rất cơ bản như: phép cộng, nhân, chia, tăng giảm, các phép logic và các phép dịch chuyển (shift). Với 10 đơn vị chức năng và 24 thanh ghi (register), máy tính CDC 6600 có thể thực hiện tính toán với tốc độ tăng lên đáng kể, đáp ứng được nhiều bài toán xử lý song song. Vấn đề chính đối với những máy tính loại này là cần phải xây dựng bộ lập lịch tối ưu để phân chia các câu lệnh thực hiện sao cho tận dụng được tối đa các đơn vị chức năng cũng như các tài nguyên mà máy tính cung cấp. b) Xử lý theo nguyên lý hình ống trong CPU Nhiều pha thực hiện khác nhau của các câu lệnh có thể thực hiện theo nguyên lý hình ống, ví dụ nạp cậu lệnh về từ bộ nhớ, giải mã (decode), xác định các toán hạng, thực hiện các phép số học/logic và lưu trữ kết quả, v.v. Những câu lệnh trong chương trình có thể thực hiện gối đầu nhau theo nguyên lý hình ống và nó sẽ hiệu quả hơn khi dựa vào kỹ thuật tạo ra vùng đệm dữ liệu. Bằng cách thực hiện như trên thì trong quá trình thực hiện của BXL có thể thực hiện được nhiều câu lệnh gối đầu nhau trong cùng một thời gian. Trước khi một câu lệnh kết thúc thực hiện thì câu lệnh tiếp theo đã có thể thực hiện pha giải mã, câu lệnh khác lại có thể được nạp về, v.v... c) Sự gối đầu CPU và các thao tác vào/ra (I/O) Nhiều phép vào/ra có thể thực hiện đồng thời đối với nhiều nhiệm vụ tính toán khác nhau bằng cách sử dụng những bộ điều khiển vào/ra, các kênh hay những BXL vào/ra khác nhau. Nhiều máy tính hiện nay có nhiều bộ điều khiển thiết bị vào/ra, cho phép đa xử lý vào/ra do vậy tăng được tốc độ trao đổi dữ liệu giữa các thiết bị ngoài với CPU. d) Các hệ thống bộ nhớ phân cấp Tốc độ các phép toán thực hiện trong BXL nhanh hơn rất nhiều so với việc truy cập vào bộ nhớ và tốc độ truy cập vào bộ nhớ trong (RAM) nhanh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn