Tài liệu Nghiên cứu các giải thuật song song trên hệ thống x

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRƯƠNG VĂN HIỆU NGHIÊN CỨU CÁC GIẢI THUẬT SONG SONG TRÊN HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU ĐA LÕI LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2011 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRƯƠNG VĂN HIỆU NGHIÊN CỨU CÁC GIẢI THUẬT SONG SONG TRÊN HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU ĐA LÕI Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 60.48.01 LUẬN VĂN THẠC SĨ KỸ THUẬT Người hướng dẫn khoa học: TS. Nguyễn Thanh Bình Đà Nẵng - Năm 2011 LỜI CAM ĐOAN Tôi xin cam đoan: a. Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của TS. Nguyễn Thanh Bình. b. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực về tên tác giả, tên công trình, thời gian và địa điểm công bố. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Tác giả Trương Văn Hiệu MỤC LỤC LỜI CAM ĐOAN................................................................................................ MỤC LỤC ii DANH MỤC CÁC CHỮ VIẾT TẮT...............................................................iv DANH MỤC CÁC BẢNG.................................................................................. DANH MỤC CÁC HÌNH VẼ...........................................................................vi MỞ ĐẦU 1 CHƯƠNG 1: CƠ SỞ LÝ THUYẾT................................................................. 1.1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG................................................ 1.1.1. Tổng quan về tính toán song song.............................................................. 1.1.2. Phân loại các kiến trúc song song............................................................... 1.1.3. Các mô hình lập trình song song...............................................................12 1.1.4. Đánh giá hiệu quả tính toán song song.....................................................14 1.2. THIẾT KẾ GIẢI THUẬT SONG SONG........................................................20 1.2.1. Nguyên lý thiết kế giải thuật song song....................................................20 1.2.2. Nhận thức vấn đề và chương trình có thể song song hóa..........................21 1.2.3. Thiết kế giải thuật song song bằng phân rã phục thuộc dữ liệu.................23 1.2.4. Thiết kế giải thuật song song bằng phương pháp chia để trị.....................24 1.2.5. Ví dụ thiết kế giải thuật song song cho bài toán tính tổng........................25 1.2.6. Ví dụ thiết kế giải thuật song song cho bài toán sắp xếp...........................27 1.3. TỔNG KẾT CHƯƠNG 1................................................................................29 CHƯƠNG 2: CẤU TRÚC HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU VÀ CÔNG NGHỆ TÍNH TOÁN HỖ TRỢ SONG SONG DỮ LIỆU CUDA..............................................................................30 2.1. CẤU TRÚC HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU..........................................30 2.1.1. Giới thiệu công nghệ GPU........................................................................30 2.1.2. Kiến trúc GPU..........................................................................................31 2.1.3. So sánh GPU và CPU...............................................................................35 2.2. CÔNG NGHỆ TÍNH TOÁN HỖ TRỢ SONG SONG DỮ LIỆU CUDA........37 2.2.1. Giới thiệu công nghệ CUDA....................................................................37 2.2.2. Ứng dụng của CUDA trong các lĩnh vực công nghệ.................................39 2.2.3. Môi trường lập trình với CUDA...............................................................40 2.2.4. Mô hình lập trình......................................................................................42 2.2.5. Mô hình bộ nhớ........................................................................................44 2.2.6. Tìm hiểu ngôn ngữ lập trình CUDA.........................................................46 2.2.7. Ví dụ tính toán song song bằng CUDA....................................................58 2.3. TỔNG KẾT CHƯƠNG 2................................................................................60 CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG GIẢI THUẬT SONG SONG TRÊN HỆ THỐNG ĐA LÕI XỬ LÝ ĐỒ HỌA GPU CHO BÀI TOÁN SO SÁNH TRÌNH TỰ.........................................61 3.1. GIỚI THIỆU....................................................................................................61 3.1.1. So sánh trình tự.........................................................................................61 3.1.2. Định nghĩa so sánh trình tự.......................................................................62 3.1.3. Hệ thống ký tự..........................................................................................63 3.1.4. Các phép biến đổi.....................................................................................63 3.1.5. Khoảng cách.............................................................................................63 3.1.6. Sắp hàng trình tự hệ gen...........................................................................64 3.1.7. Các thuật toán sắp hàng trình tự hệ gen....................................................64 3.2. PHÁT BIỂU BÀI TOÁN SO SÁNH TRÌNH TỰ............................................66 3.2.1. Mô tả bài toán...........................................................................................66 3.2.2. Hướng giải quyết bằng giải thuật quy hoạch động....................................67 3.3. THIẾT KẾ GIẢI THUẬT SONG SONG........................................................71 3.3.1. Xây dựng giải thuật...................................................................................71 3.3.2. Cài đặt giải thuật trên CUDA....................................................................72 3.3.3. Kết quả.....................................................................................................73 3.4. ĐÁNH GIÁ KẾT QUẢ CHẠY CHƯƠNG TRÌNH........................................74 3.5. TỔNG KẾT CHƯƠNG 3................................................................................75 KẾT LUẬN 76 DANH MỤC TÀI LIỆU THAM KHẢO........................................................78 PHỤ LỤC 80 DANH MỤC CÁC CHỮ VIẾT TẮT CUDA Compute Unified Device Architecture CPU Central Processing Unit GPU Graphisc Processing Unit SISD Single Instruction Single Data SIMD Single Instruction Multiple Data MISD Multiple Instruction Single Data MIMD Multiple Instruction Multiple Data SDK Software Development Kit AMD Advanced Micro Devices GPGPU General Purpose Computing on Graphics Processing Units DRAM Dynamic Random Access Memory DNA Deoxyribonucleic Acid RNA Ribonucleic Acid AND Associates Degree in Nursing DMA Direct Memory Access NVCC NVIDIA C Compiler SW Smith-Waterman API Application Programming Interface DANH MỤC CÁC BẢNG Số hiệu bảng 26Bảng 1.1. Tên bảng Sắp xếp theo nguyên lý hình ống3.4.1 Bảng kết quả chạy thực nghiệm 69 .1Bảng 1.1. Bảng 1.1. Mô tả phân loại kiến trúc của Flynn Trang 8 DANH MỤC CÁC HÌNH VẼ Số hiệu hình vẽ Mô hình kiến trúc máy SIMD9 8Hình 1.1. Hình 3.1. Hình 4.1. Mô hình kiến trúc máy SISDHình 2.1. Hình 2.1. Hình 5.1. Hình 1.1. Mô tả lập trình giữa các tác vụ dùng chung bộ nhớ Hình 2.1. 14Hình 3.1. Mô tả mối quan hệ các tham số trong công thức tính thời gian truyền thôngHìn h 1.2. Kỹ thuật xen kẽ tính toán và truyền thông giữa P1 và P2 Hình 1.1. 33Hình 2.1. So sánh kiến trúc CPU và GPUHìn h 1.2. Hình 1.1. 36Hình 1.1. Các thao tác thu hồi và cấp phát bộ nhớHình 1.3. Hình 1.2. 41Hình 1.1. Khối luồngHình 1.1. Hình 2.1. Hình 1.1. Hình 2.1. Tên hình vẽ Mô tả kiến trúc Von Neumann Trang 5 Mô hình kiến trúc máy MISD 9 Mô hình kiến trúc máy MIMD 11 10 Mô hình lập trình truyền thông giữa hai tác vụ trên hai máy tính Mô hình lập trình song song dữ liệu 15 11 Tính tổng N số So sánh floating-point của GPU và CPU 24 34 Kiến trúc bộ phần mềm CUDA Vùng nhớ dùng chung mang dữ liệu gần ALU hơn 35 36 Sơ đồ hoạt động truyền dữ liệu giữa Host và Device Mô hình bộ nhớ trên GPU 39 42 Cộng hai ma trận 54 55 12 Số hiệu hình vẽ Nhân hai ma trận 62Hình 1.1. So sánh hai trình tựHình 2.1. Hình 1.1. 65Hình 2.2. Kết quả giải thuật quy hoạch động cho bài toán PSAHình 1.1. Hình 2.3. 3.3.3Hình 1.1. Tên hình vẽ Trang Ví dụ về so sánh trình tự Giải thuật quy hoạch động cho bài toán PSA 58 64 Ma trận đánh giá S(i, j) Phương pháp song song tính giá trị các phần tử ma trận đánh giá 64 67 Ma trận đánh giá 69 -1- MỞ ĐẦU Nhu cầu tính toán trong lĩnh vực khoa học, công nghệ ngày càng cao và trở thành một thách thức lớn. Từ đó các giải pháp nhằm tăng tốc độ tính toán đã được ra đời, từ năm 2001 đến năm 2003 tốc độ của Pentium 4 đă tăng gấp đôi từ 1.5GHz lên đến 3GHz. Tuy nhiên hiệu năng của CPU (Central Processing Unit) không tăng tương xứng như mức gia tăng xung của CPU và việc gia tăng tốc độ xung của CPU nhanh chóng chạm phải ngưỡng tối đa mà cụ thể trong khoảng thời gian 2 năm từ năm 2003 đến năm 2005 tốc độ của CPU chỉ tăng từ 3GHz lên 3.8GHz. Trong quá trình tăng tốc độ xung của CPU các nhà sản xuất đã gặp phải vấn đề về nhiệt độ của CPU sẽ quá cao và các giải pháp tản nhiệt khí đã đến mức tới hạn không thể đáp ứng được khả năng làm mát khi CPU hoạt động ở xung quá cao như vậy. Vì vậy việc gia tăng xung hoạt động của CPU không sớm thì muộn cũng sẽ đi vào bế tắc. Trước tình hình này, các nhà nghiên cứu vi xử lý đã chuyển hướng sang phát triển công nghệ đa lõi, nhiều lõi, với cơ chế xử lý song song trong các máy tính nhằm tăng hiệu năng và tiết kiệm năng lượng. Một trong các công nghệ xử lý song song ra đời đó là GPU (Graphics Processing Unit - bộ xử lý đồ họa). Ban đầu, việc chế tạo GPU chỉ với những mục đích công việc phù hợp với khả năng là tăng tốc độ xử lý đồ họa, cũng như trong ngành trò chơi là chủ yếu. Nhưng đến thời điểm GPU NV30 của NVIDIA ra đời, GPU bắt đầu tham gia vào những công việc khác ngoài đồ họa như: Hỗ trợ tính toán dấu chấm động đơn, hỗ trợ tính toán lên cả ngàn lệnh. Vì thế đã nảy sinh ra ý tưởng dùng GPU để xử lý, tính toán song song những chương trình không thuộc đồ họa. Câu hỏi được đặt ra là làm thế nào để ứng dụng GPU vào việc xử lý tính toán song song? Câu hỏi này nhanh chóng được giải quyết bằng công nghệ CUDA (Compute Unified Device Architecture – kiến trúc thiết bị hợp nhất cho tính toán) của NVIDIA ra đời năm 2007. Với CUDA, các lập trình viên nhanh chóng phát triển các ứng dụng song song trong rất nhiều lĩnh vực khác nhau như: Điện toán hóa học, sắp xếp, tìm kiếm, mô phỏng các mô hình vật lý, chuẩn đoán y khoa, thăm dò dầu khí, … CUDA là bộ công cụ phát triển phần mềm trên GPU được xây dựng -2bằng ngôn ngữ lập trình C. Với CUDA các lập trình viên dùng để điều khiển GPU để xử lý, tính toán song song các dữ liệu lớn. Việc tăng tốc trong quá trình tính toán không những đòi hỏi những thiết bị GPU có khả năng xử lý tốc độ cao với dữ liệu khổng lồ mà cần phải có những giải thuật song song hữu hiệu. Xuất phát từ nhu cầu trên tôi chọn đề tài: “Nghiên cứu các giải thuật song song trên hệ thống xử lý đồ họa GPU đa lõi”. 1. Mục tiêu và nhiệm vụ nghiên cứu Để hoàn thành mục đích ý tưởng đề ra cần nghiên cứu các nội dung như sau: - Tìm hiểu các giải thuật tính toán song song, các cách thiết kế mẫu trong tính toán song song. - Tìm hiểu cấu trúc của GPU - Tìm hiểu và triển khai lập trình song song với CUDA - Phát biểu, phân tích, cài đặt giải thuật cho bài toán đặt ra. - Xây dựng giải thuật và ứng dụng áp dụng giải thuật tính toán song song trên thiết bị đồ họa GPU. - Đánh giá kết quả theo yêu cầu của đề tài. 2. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu Trong khuôn khổ luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn nghiên cứu các vấn đề sau: - Lý thuyết tính toán song song. - Chuyển đổi một số giải thuật xử lý trình tự sang tính toán song song sao cho tốc độ tính toán nhanh hơn giải thuật cũ, phát biểu bài toán thực tế có áp dụng giải thuật trên, cài đặt và giải quyết trên thiết bị xử lý đồ họa GPU bằng ngôn ngữ lập trình CUDA. Phạm vi nghiên cứu -3Nghiên cứu chuyển một số giải thuật cơ bản tuần tự sang song song chạy trên thiết bị đồ họa GPU của NVIDIA bằng ngôn ngữ CUDA. 3. Phương pháp nghiên cứu Đề tài này sẽ kết hợp hai phương pháp nghiên cứu, đó là: Phương pháp nghiên cứu lý thuyết - Nghiên cứu lý thuyết về tính toán song song, các giải thuật tính toán song song. - Nghiên cứu lý thuyết về cơ chế hoạt động tính toán trong GPU. Phương pháp nghiên cứu thực nghiệm Sử dụng phương pháp nghiên cứu lý thuyết kết hợp với nghiên cứu thực nghiệm: - Thiết kế giải thuật song song và cài đặt bằng CUDA. - Triển khai xây dựng ứng dụng. - Chạy thử nghiệm và lưu trữ các kết quả đạt được, sau đó đánh giá lại kết quả. 4. Kết quả dự kiến Nghiên cứu được một số giải thuật tính toán song song. Cài đặt các giải thuật tính toán song song chạy trên thiết bị đồ họa GPU. Xây dựng ứng dụng tính toán trên thiết bị đồ họa GPU sử dụng giải thuật tính toán song song. 5. Ý nghĩa khoa học và thực tiễn của luận văn Về mặt lý thuyết - Nắm được các giải thuật, các mẫu thiết kế tính toán song song. - Khai thác các bộ thư viện CUDA SDK ứng dụng trong ngôn ngữ lập trình song song bằng CUDA. Về mặt thực tiễn -4Việc nghiên cứu và đề xuất giải pháp để “Nghiên cứu các giải thuật song song trên hệ thống xử lý đồ họa GPU”, làm cơ sở để giải quyết một số bài toán cần lượng tính toán lớn với dữ liệu khổng lồ. 6. Bố cục luận văn Nội dung chính của luận văn được chia thành 3 chương như sau: Chương 1: Cơ sở lý thuyết tính toán song song. Trong chương này giới thiệu tổng quan về tính toán song song như: Lịch sử phát triển song song, phân loại kiến trúc song song, các mô hình lập trình song song và đánh giá hiệu quả tính toán song song. Trình bày nguyên lý thiết kế giải thuật song song, giới thiệu một số mẫu thiết kế giải thuật song song bằng phương pháp chia để trị, phương pháp cây nhị phân. Giới thiệu bài toán sắp xếp, bài toán tính tổng dùng giải thuật song song. Qua đây đưa ra cái nhìn tổng quan hơn về tính toán song song. Chương 2: Cấu trúc hệ thống xử lý đồ họa GPU và công nghệ tính toán hỗ trợ song song dữ liệu CUDA. Chương này giới thiệu về thiết bị đồ họa GPU đa lõi của hãng NVIDIA gồm các vấn đề: lịch sử phát triển, mô tả kiến trúc, nguyên lý hoạt động và những ứng dụng trên thiết bị đồ họa này. Đưa ra những so sánh khác biệt của CPU và GPU. Trình bày ngôn ngữ lập trình song song CUDA trên thiết bị đồ họa GPU của hãng NVIDIA. Áp dụng giải quyết một số bài toán cộng ma trận, nhân ma trận, …bằng phương pháp song song dùng ngôn ngữ CUDA thực thi trên thiết bị đồ họa. Chương 3: Xây dựng ứng dụng áp dụng giải thuật song song trên hệ thống đa lõi xử lý đồ họa GPU cho bài toán bắt cặp trình tự. Trong chương này trình bày một số khái niệm cơ bản về tin sinh học: AND, protein, … Từ đó tập trung mô tả bài toán so sánh trình tự sử dụng giải thuật SmithWaterman và giải quyết bằng giải thuật song song bằng CUDA đưa ra những đánh giá về lợi ích của việc sử dụng giải thuật song song. -5- CHƯƠNG 1: CƠ SỞ LÝ THUYẾT Trong chương này giới thiệu tổng quan về tính toán song song như: Lịch sử phát triển song song, phân loại kiến trúc song song, các mô hình lập trình song song và đánh giá hiệu quả giải thuật tính toán song song. Trình bày nguyên lý thiết kế giải thuật song song, giới thiệu một số mẫu thiết kế giải thuật song song bằng phương pháp chia để trị, phương pháp cây nhị phân. Giới thiệu bài toán sắp xếp, bài toán tính tổng dùng giải thuật song song. Qua đây đưa ra cái nhìn tổng quan hơn về tính toán song song. 1.1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 1.1.1. Tổng quan về tính toán song song 1.1.1.1. Lịch sử ra đời tính toán song song Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô hình của John Von Neumann (Xem Hình 1.1. ), với một đơn vị xử lý được nối với một vùng lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi. Hình 1.1. Mô tả kiến trúc Von Neumann Với những bài toán yêu cầu về khả năng tính toán và lưu trữ lớn thì mô hình kiến trúc này còn hạn chế. Để tăng cường sức mạnh tính toán giải quyết các bài toán lớn có độ tính toán cao, người ta đưa ra kiến trúc mới, với ý tưởng kết hợp nhiều bộ xử lý vào trong một máy tính, mà hay gọi là xử lý song song (Multiprocessor) hoặc kết hợp sức mạnh tính toán của nhiều máy tính dựa trên kết nối mạng (gọi là máy tính song song - multicomputer). -6Kể từ lúc này, để khai thác được sức mạnh tiềm tàng trong mô hình máy tính nhiều bộ xử lý song song, cũng như trong mô hình mạng máy tính xử lý song song thì các giải thuật tuần tự không còn phù hợp nữa cho nên việc xây dựng thiết kế giải thuật song song là điều quan trọng. Giải thuật song song có thể phân rã công việc trên các phần tử xử lý khác nhau [5]. 1.1.1.2. Tại sao phải tính toán song song Việc tính toán song song là rất cần thiết. Ngoài hai nguyên nhân chính là nó được dùng để tính toán các bài toán yêu cầu thời gian tính toán lớn và khối lượng dữ liệu lớn còn có các nguyên nhân khác như để sử dụng tài nguyên của các máy khác trong một mạng nội bộ hoặc thông qua mạng internet, có thể sử dụng nhiều tài nguyên tính toán như kết hợp lại tạo nên một siêu máy tính. Do giới hạn về không gian lưu trữ của bộ nhớ trên một máy đơn để giải quyết một vấn đề lớn việc sử dụng nhiều bộ nhớ trên nhiều máy tính là rất hữu hiệu trong trường hợp này. Giới hạn của tính toán tuần tự bao gồm cả hai nguyên nhân thực tế và nguyên nhân vật lý. Ðể xây dựng nên một máy tính tuần tự tốc độ cao gặp rất nhiều hạn chế: Về kích cỡ: Công nghệ chế tạo bộ xử lý cho phép gắn nhiều bóng bán dẫn trên một con chip. Tuy nhiên việc làm này sẽ làm tăng kích thuớc của bộ xử lý. Về tốc độ truyền dữ liệu: Tốc độ truyền của máy tính tuần tự phụ thuộc trực tiếp vào sự di chuyển dữ liệu trong phần cứng. Cho nên việc tăng tốc độ thực hiện phải chủ yếu căn cứ vào các yếu tố tính toán. Về thương mại: Việc tạo ra một bộ xử lý có tốc độ xử lý cao là rất tốn kém. Sử dụng nhiều bộ xử lý nhỏ đạt hiệu quả tương tự mà lại ít tốn kém hơn [7]. 1.1.1.3. Một số khái niệm xử lý song song Định nghĩa về xử lý song song 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 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ý. Phân biệt xử lý song song và xử lý tuần tự -7Trong tính toán tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ được thực hiện một phép toán. Trong tính toán song song thì nhiều bộ xử lý cùng kết hợp với nhau để giải quyết cùng một bài toán cho nên 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. Mục đích của xử lý song song Thực hiện tính toán nhanh trên cơ sở sử dụng nhiều bộ xử lý đồng thời. Cùng với tốc độ xử lý nhanh, việc xử lý song song cũng sẽ giải được những bài toán phức tạp yêu cầu khối lượng tính toán lớ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 Tốc độ xử lý của các bộ xử lý 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. 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 bộ xử lý với giá thành hợp lý. Sự phát triển của công nghệ mạch tích hợp cho phép tạo ra những hệ thống có hàng triệu transistor trên bộ vi xử lý. Hệ thống tính song song Hệ thống tính toán song song là một tập các bộ xử lý (thường 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 với nhau trong hoạt động và trao đổi dữ liệu được với nhau. 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), giải thuật và ngôn ngữ lập trình, … Xét độ phức tạp Độ phức tạp của xử lý song song sẽ lớn hơn xử lý tuần tự rất nhiều và tập trung chủ yếu ở phương diện trao đổi dữ liệu và đồng bộ các tiến trình. Cài đặt giải thuật song song -8Để cài đặt các giải thuật song song trên các máy tính song song, phải sử dụng những ngôn ngữ lập trình song song như: OpenMP với C/C++, MPI với C/C++, … 1.1.2. Phân loại các kiến trúc song song Một trong những phân loại kiến trúc máy tính song song được biết đến nhiều nhất là phân loại của Flynn, được sử dụng từ năm 1966. Michael Flynn dựa vào đặc tính về số lượng bộ xử lý, số chương trình thực hiện, cấu trúc bộ nhớ, … để phân máy tính thành bốn loại dựa trên sự biểu hiện của cặp khái niệm: Dòng lệnh (instruction stream) và dòng dữ liệu (data stream), mỗi loại nằm trong một trong hai trạng thái đơn (single) hoặc đa (multiple) được thể hiện trong Bảng 1.1. Bảng 1.1. Mô tả phân loại kiến trúc của Flynn Dòng lệnh (instruction stream) Trạng thái đơn (single) Trạng thái đơn (single) Trạng thái đa (multiple) Trạng thái đa (multiple) 1.1.2.2. Dòng dữ liệu (data stream) Trạng thái đơn (single) Trạng thái đa (multiple) Trạng thái đơn (single) Trạng thái đa (multiple) Loại kiến trúc SISD Single Instruction Single Data SIMD Single Instruction Multiple Data MISD Multiple Instruction Single Data MIMD Multiple Instruction Multiple Data Kiến trúc đơn dòng lệnh đơn luồng dữ liệu (SISD) Máy tính 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 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. Kiến trúc máy SISD có mô hình hoạt động theo hình Hình 2.1. Hình 2.1. Mô hình kiến trúc máy SISD -91.1.2.3. Kiến trúc đơn dòng lệnh đa luồng dữ liệu (SIMD) Máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý thực hiện theo một luồng các câu lệnh. CPU phát sinh tín hiệu điều khiển tới tất cả các phần xử lý, những bộ xử lý 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 bộ xử lý có luồng dữ liệu riêng. Kiến trúc máy SIMD có mô hình hoạt động theo Hình 3.1. Hình 3.1. Mô hình kiến trúc máy SIMD Mô hình SIMD còn được gọi là SPMD, đơn chương trình và đa 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. 1.1.2.4. Kiến trúc đa dòng lệnh đơn dữ liệu (MISD) Máy tính loại 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 (ngược với máy tính loại SIMD). Kiến trúc máy MISD có mô hình hoạt động mô tả theo Hình 4.1. Hình 4.1. Mô hình kiến trúc máy MISD - 10 1.1.2.5. Kiến trúc đa dòng lệnh đa luồng dữ liệu (MIMD) Máy tính loại MIMD gọi là đa bộ xử lý, trong đó mỗi bộ xử lý 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 bộ nhớ chung khi cần, do vậy giảm thiểu được thời gian trao đổi dữ liệu giữa các bộ xử lý trong hệ thống. Đây là loại kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao nhất và đã có nhiều máy tính được thiết kế theo kiến trúc này, ví dụ: BBN Butterfly, Alliant FX, iSPC của Intel, ... Kiến trúc máy MIMD có mô hình hoạt động theo Hình 5.1. Hình 5.1. Mô hình kiến trúc máy MIMD 1.1.3. Các mô hình lập trình song song 1.1.3.1. Lập trình bộ nhớ dùng chung Lập trình bộ nhớ dùng chung hay còn gọi là lập trình chia sẻ bộ nhớ. Trong mô hình (Xem Hình 1.1. ) này được thiết kế cho máy tính xử lý song song (multiprocessors), các tác vụ chia sẻ không gian địa chỉ dùng chung, được đọc/ghi một cách không đồng bộ. Một số kỹ thuật được dùng trong lập trình bộ nhớ dùng chung như khoá (locks) hay cờ (semaphores) được sử dụng để điều khiển truy nhập đến bộ nhớ dùng chung. Truyền thông giữa các tác vụ thông qua các biến dùng chung. - 11 - Hình 1.1. Mô tả lập trình giữa các tác vụ dùng chung bộ nhớ 1.1.3.2. Lập trình truyền thông điệp Trong máy tính song song cung cấp kỹ thuật truyền thông điệp để trao đổi giữa các tác vụ (Xem Hình 2.1. ). Hai tác vụ nằm trên hai máy khác nhau có thể trao đổi với nhau bằng kỹ thuật truyền thông điệp trên mạng kết nối. Các thông điệp có thể là các lệnh, dữ liệu, tín hiệu đồng bộ hay ngắt. Hai mô hình truyền thông điệp được thực thi và sử dụng là đồng bộ hay không đồng bộ. Hình 2.1. Mô hình lập trình truyền thông giữa hai tác vụ trên hai máy tính 1.1.3.3. Mô hình song song dữ liệu Trong mô hình song song dữ liệu được mô tả ở Hình 3.1. , hầu hết các công việc song song đều tập trung thực hiện các phép toán trên một tập dữ liệu. Tập dữ liệu này thường được tổ chức trong một cấu trúc dữ liệu thông dụng như mảng hoặc khối. Một tập tác vụ sẽ làm việc trên cùng cấu trúc dữ liệu nhưng mỗi tác vụ sẽ làm việc trên một phần dữ liệu khác nhau với cùng phép toán. Mô hình song song dữ liệu thiết kế chủ yếu dành cho máy tính song song kiểu bộ xử lý mảng.