Khóa luận Nghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thị

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM HUỲNH BÁ THANH TÙNG TRẦN VIỆT CƯỜNG NGHIÊN CỨU TÍNH TOÁN LƯỚI VÀ THỬ NGHIỆM MỘT SỐ THUẬT TOÁN LÝ THUYẾT ĐỒ THỊ KHOÁ LUẬN CỬ NHÂN TIN HỌC TP. HCM, NĂM 2005 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM HUỲNH BÁ THANH TÙNG - 0112079 TRẦN VIỆT CƯỜNG - 0112339 NGHIÊN CỨU TÍNH TOÁN LƯỚI VÀ THỬ NGHIỆM MỘT SỐ THUẬT TOÁN LÝ THUYẾT ĐỒ THỊ KHÓA LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TS. TRẦN ĐAN THƯ Th.S NGUYỄN THANH SƠN NIÊN KHÓA 2001-2005 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN LỜI CẢM ƠN Chúng em xin bày tỏ lòng biết ơn chân thành nhất đến Thầy Trần Đan Thư và thầy Nguyễn Thanh Sơn, hai Thầy đã tận tâm hướng dẫn, giúp đỡ chúng em trong suốt thời gian thực hiện luận văn này. Chúng con xin gửi tất cả lòng biết ơn sâu sắc và sự kính trọng đến ông bà, cha mẹ, cùng toàn thể gia đình, những người đã nuôi dạy chúng con trưởng thành đến ngày hôm nay. Chúng em cũng xin chân thành cám ơn quý Thầy cô trong Khoa Công nghệ thông tin, trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, hướng dẫn, giúp đỡ và tạo điều kiện cho chúng em thực hiện tốt luận văn này. Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của các anh chị và tất cả các bạn, những người đã giúp chúng tôi có đủ nghị lực và ý chí để hoàn thành luận văn này. Mặc dù đã cố gắng hết sức, song chắc chắn luận văn không khỏi những thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy Cô và các bạn. TP.HCM, 7/2005 Nhóm sinh viên thực hiện Huỳnh Bá Thanh Tùng - Trần Việt Cường LỜI NÓI ĐẦU Nhân lọai ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ Thông tin, một trong những nghành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển kèm theo các thiết bị phần cứng cũng như phần mềm tiện ích. Sự phát triển đó đã kéo theo rất nhiều nghành khác phát triền theo, trong đó có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển, tốc độ xử lý của các thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính toán của con người vẫn còn là rất lớn. Hiện nay vẫn còn rất nhiều vấn đề mà các nhà khoa học cùng với khả năng tính toán của các máy tính hiện nay vẫn chưa giải quyết được hay giải quyết được nhưng với thời gian rất lớn. Các vấn đề đó có thể có thể là : Mô hình hóa và giả lập Xử lý thao tác trên các dữ liệu rất lớn Các vấn đề “grand challenge” (là các vấn đề không thể giải quyết trong thời gian hợp lý) Lời giải cho những vấn đề này đã dẫn đến sự ra đời của các thế hệ siêu máy tính. Tuy nhiên việc đầu tư phát triển cho các thiết bị này gần như là điều quá khó khăn đối với nhiều người, tổ chức, trường học…. Chính vì lẽ đó mà ngày nay người ta đang tập trung nghiên cứu cách cách sử dụng các tài nguyên phân bố một cách hợp lý để tận dụng được khả năng tính toán của các máy tính đơn. Những giải pháp này được biết đến với nhiều tên gọi khác nhau như meta-computing, salable-computing, global- computing, internet computing và gần nhất hiện nay là peer to peer computing hay Grid computing. Đây là phương pháp nhằm tận dụng khả năng của các máy tính trên toàn mạng thành một máy tính “ảo” duy nhất, nhằm hợp nhất tài nguyên tính toán ở nhiều nơi trên thế giới để tạo ra một khả năng tính toán khổng lồ, góp phần giải quyết các vấn đề khó khăn trong khoa học và công nghệ. Ngày nay nó đang càng được sự hỗ trợ mạnh hơn của các thiết bị phần cứng, băng thông… Grid Computing có khả năng chia sẻ, chọn lựa, và thu gom một số lượng lớn những tài nguyên khác nhau bao gồm những siêu máy tính, các hệ thống lưu trữ, cùng với những nguồn dữ liệu, các thiết bị đặt biệt… Những tài nguyên này được phân bố ở các vùng địa lý khác nhau và thuộc về các tổ chức khác nhau. Hình ảnh minh họa cho các tài nguyên phân phối Nhận thấy được nhu cầu phát triển ấy, nhóm chúng em đã quyết định chọn thực hiện đề tài “Nghiên cứu tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồ thị” Mục tiêu của đề tài đề ra tìm hiểu được về tính toán lưới qua đó tận dụng các kiến thức có được để có thể cài đặt một số thuật toán trên lý thuyết đồ thị, nhằm có thể giải quyết các vấn đề tìm đường đi khi số đỉnh tương đối lớn… Các nội dung chính: Nghiên cứu tính toán lưới Tìm hiểu các môi trường hỗ trợ Tìm hiểu lập trinh song song và phân tán Cài đặt một số thuật toán với kiến thức có được Nội dung của luận văn được chia làm 6 chương : Chương 1. Giới thiệu : Giới thiệu tổng quan về tính toán lưới, khái niệm lịch sử phát triển. Chương 2. Tính toán song song và phân bố : Trình bày về các kiến trúc, mô hình xử lý song song và phân bố, cách thức xây dựng chương trình, thiết kế thuật toán… Chương 3. Các môi trường hỗ trợ tính toán lưới : Tìm hiểu về các môi trường đang được sử dụng và nghiên cứu hiện nay trên thế giới. Chương 4. Mô hình lập trình truyền thông điệp - MPI : Mô hình cụ thể được dùng để phát triển ứng dụng MPI. Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị : Cách thức xây dựng chương trình , các khái niệm lý thuyết, thực nghiệm thực tế … Chương 6. Kết luận – Hướng phát triển : Nêu các kết quả đã đạt được, một số vấn đề còn tồn tại, định hướng mục tiêu mở rông phát triển đề tài trong tương lai. Mục lục 3.3.1. Một số môi trường Grid 59 3.3.2. Những mô hình lập trình và công cụ hỗ trợ 63 3.3.3. Môi trường cài đặt 69 3.4. Những kỹ thuật nâng cao hỗ trợ lập trình 81 3.4.1. Các kỹ thuật truyền thống 81 3.4.2. Các kỹ thuật hướng dữ liệu 82 3.4.3. Các kỹ thuật suy đoán và tối ưu 83 3.4.4. Các kỹ thuật phân tán 83 3.4.5. Nhập xuất hướng Grid 84 3.4.6. Các dịch vụ giao tiếp cấp cao 84 3.4.7. Bảo mật 86 3.4.8. Dung lỗi 86 3.4.9. Các siêu mô hình và hệ thống thời gian thực hướng Grid 88 3.5. Kết luận 89 Chương 4. Mô hình lập trình truyền thông điệp - MPI 91 4.1. Các khái niệm cơ bản 92 4.2. Cấu trúc chương trình MPI 95 4.3. Trao đổi thông tin điểm-điểm 96 4.3.1. Các thông tin của thông điệp 97 4.3.2. Các hình thức truyền thông 97 4.3.3. Giao tiếp blocking 99 4.3.4. Giao tiếp non-blocking 104 4.4. Trao đổi thông tin tập hợp 110 4.4.1. Đồng bộ hóa 110 4.4.2. Di dời dữ liệu trong nhóm 110 4.4.3. Tính toán gộp 114 4.5. Các kiểu dữ liệu 118 4.5.1. Những kiểu dữ liệu đã được định nghĩa 118 4.5.2. Các kiểu dữ liệu bổ sung 119 4.5.3. Pack và UnPack 123 4.6. Quản lý nhóm và communicator 124 4.6.1. Tổng quan 124 4.6.2. Nguyên tắc sử dụng 126 Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị 129 5.1. Các khái niệm cơ bản 129 5.2. Dijkstra 130 5.2.1. Tuần tự 130 5.2.2. Song song 134 5.2.3. Thực nghiệm chương trình 136 5.3. Prim 138 5.3.1. Tuần tự 138 5.3.2. Song song 141 5.3.3. Thực nghiệm chương trình 143 5.4. Bellman – Ford 143 5.4.1. Tuần tự 143 5.4.2. Song song 147 Chương 6. Kết luận – Hướng phát triển 151 6.1. Kết luận 151 6.2. Hướng phát triển 151 Tài liệu tham khảo 153 Danh sách hình Hình 1-1 : 3 tầng của Grid 16 Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson 20 Hình 2-2 : Kiến trúc SISD 20 Hình 2-3 : Kiến trúc SIMD 21 Hình 2-4 : Kiến trúc MISD 23 Hình 2-5 : Kiến trúc MIMD 24 Hình 2-6 : Mô hình chía sẽ không gian bộ nhớ 28 Hình 2-7 : Mô hình truyền thông điệp 29 Hình 3-1 : mô hình NetSolve 60 Hình 3-2 : Các thành phần của Globus 63 Hình 4-1 : Các tiến trình tạo lập trên mô hình lập trình MPI 92 Hình 4-2 : Cách thức truyền thông của các process 94 Hình 4-3 : Blocking và non-blocking 94 Hình 4-4 : Group, communicator và rank 95 Hình 4-5 : Cấu trúc của chương trình MPI 96 Hình 4-6 : Giao tiếp blocking 99 Hình 4-7 : Thứ tự các xử lý 102 Hình 4-8 : Cách thức xử lý tiến trình 104 Hình 4-9 : Giao tiếp non-blocking 104 Hình 4-10 : Broadcast dữ liệu 110 Hình 4-11 : Ví dụ hàm Scatter 111 Hình 4-12 : Hàm MPI_Gather 112 Hình 4-13 : Hàm MPI_Allgather 112 Hình 4-14 : Hàm MPI_Alltoall 114 Hình 4-15 : Hàm MPI_Reduce 114 Hình 4-16 : Sử dụng 8 xử lý để tính giá trị tuyệt đối 116 Hình 4-17 Hàm Mpi-Allreduce 117 Hình 4-18 : Hàm MPI_Reduce_scatter 117 Hình 4-19 : Hàm MPI_Scan 118 Hình 4-20 : MPI_Type_contiguous 120 Hình 4-21 : MPI_Type_vetor 121 Hình 4-22 : MPI_Type_indexed 122 Hình 4-23 : MPI_Type_struct 122 Hình 5-1. Thuật toán Dijkstra tuần tự 134 Hình 5-1.1. 131 Hình 5-1.3. 132 Hình 5-1.4. 133 Hình 5-1.5 133 Hình 5-1.6 134 Hình 5-2 : Thuật toán Dijkstra song song 135 Hình 5-3. Thuật toán Prim tuần tự 141 Hình 5-3 : Thuật toán Prim song song 142 Hình 5-4: Thuật toán Bellman-Ford tuần tự 145 Hình 5-5 : Thuật toán Bellman-Ford song song 149 Giới thiệu Các khái niệm Trong những năm đầu thập niên 90, nhiều nhóm nghiên cứu đã bắt đầu khai thác các nguồn tài nguyên tính toán phân tán trên Internet. Các nhà khoa học đã tập trung và sử dụng hàng trăm các máy trạm để thực hiện các chương trình song song như thiết kế phân tử và hiển thị đồ họa máy tính. Trong khi đó các nhóm nghiên cứu khác đã kết hợp các siêu máy tính lớn lại với nhau thành một siêu máy tính ảo duy nhất, rồi phân phối các phần của một ứng dụng rất lớn cho các máy tính trên một mạng diện rộng, ví dụ như máy tính giả lập các ứng dụng như tương tác giữa chất lõng và cánh quạt của chân vịt tàu…Thêm vào đó phạm vi của các dự án nghiên cứu này đã nêu ra tiềm năng thực sự của mạng máy tính, cùng với cơ sở phần mềm và tin học để phát triển nó xa hơn. Hệ thống đa bộ xử lý (Multiprocessor Systems - MPs), Cluster, Grids là các ví dụ của kiến trúc tính toán phân tán. Trong MPs, các bộ xử lý được kết hơp chặt chẽ với nhau, thông qua bộ nhớ chia sẽ chung và đường truyền kết nối rất cao. Ví dụ như là PVPs (Parallel Vector Processors), chúng hầu như rất thích hợp cho tính toán hiệu năng cao, như là các ứng dụng song song dựa vào trao đổi thông điệp tốc độ cao giữa các tiến trình song song. Trong khi đó Cluster lại là các máy tính đơn hay đa bộ xử lý được kết hợp tương đối với nhau thông qua đường mạng, vì thế nó chậm hơn từ 1 đến 2 lần so với kết nối MP. Ví dụ như cluster Beowulf chạy Linux, hay TCF (Technical Compute Farm) của Sun chạy hệ điều hành Solaris/TM. Chúng được sử dụng cho các tính toán số lượng lớn, phân phối các tác vụ tính toán (thường là không song song) cho các bộ xử lý, rồi thu thập lại các kết quả tính toán vào kết quả toàn cục. Các tính toán này có thể là việc hiển thị hàng ngàn khung hình để làm phim hay là giả lập việc kiểm tra và thiết kế để xây dựng thế hệ tiếp theo của chip VLSI. Hay như trong công nghệ sinh học, đó là việc cắt lớp hàng trăm ngàn chuỗi gen. Trong khi MPs và Cluster chỉ là các hệ thống đơn, thường là trong một domain đơn. Grid điện toán bao gồm các cluster của mạng các MPs hay/và cluster, nằm trên nhiều domain khác nhau, phân bố ở nhiều phòng ban, xí nghiệp hay thậm chí là trên mạng Internet. Về bản chất, những grid có một độ phức tạp cao hơn, đặc biệt là ở tầng trung gian, trong việc thực thi, quản lý, và sử dụng các tài nguyên tính toán phân tán, và ở tầng ứng dụng là việc thiết kế, phát triển, chạy các phần mềm để triển khai grid một cách hiệu quả. Tóm lại Grid là một kiến trúc tính toán phân tán cho phép chuyển giao các tài nguyên lưu trữ và tính toán như thể là một dịch vụ trên Internet. Đây là bước phát triển tiếp theo về cơ sở hạ tầng kỹ thuật, cho phép kết nối các máy tính phân tán, các thiết bị lưu trữ, các thiết bị di động, các thiết bị di động, các công cụ, cơ sở dữ liệu, và các ứng dụng phần mềm, và cung cấp cách thức truy cập duy nhất đến cộng đồng người dùng để cho phép tính toán, trao đổi thông tin và cộng tác. Một số hệ thống grid hiện tại như là NASA Information Power Grid (IPG); DoD Distance Computing và NetSolve cho chia sẽ và khai thác phần mềm toán học; Nimrod cho chia sẽ tài nguyên trên phạm vi trường học; SETI@Home cho tìm kiếm trí thông minh ngòai trái đất; hay là APGrid để kết nối các trung tâm máy tính ở vành đai Châu Á Thái Bình Dương trong tương lai gần. Hình 1-1 : 3 tầng của Grid Grid là một cơ sở hạ tầng về phần cứng lẫn phần mềm cung cấp truy cập phụ thuộc, thích hợp, rộng khắp và chi phí thấp vào các khả năng tính toán. Trong một tương lai không xa, những grid này sẽ được các kỹ sư, nhà khoa học, khoa học thực nghiệm, công ty, tổ chức, môi trường, giáo dục và đào tạo, khách hàng, … sử dụng rộng rãi. Chúng sẽ dành riêng cho tính toán theo yêu cầu, tính toán trên thông tin nhạy cảm, tính toán cộng tác, và siêu tính toán, dựa trên cơ sở của khách hàng/nhà cung cấp. Ngày nay chúng ta đang thấy những nỗ lực đầu tiên nhằm khai thác một cách có hệ thống các nguồn tài nguyên tính toán lưới trên mạng Internet. Những dự án này được gọi là peer-to-peer computing, như SETI@home, Distributed.Net và Folderol, cho phép người dùng Internet tải về các dữ liệu khoa học, chạy trên các máy cá nhân theo chu trình xử lý chia sẽ, và gửi lại kết quả cho cơ sở dữ liệu trung tâm. Gần đây có một dự án ở một trường đại học, được gọi là Compute Power Market, được xây dựng nên nhằm phát triển các kỹ thuật phần mềm cho phép tạo lập những Grid, mà ở đó bất cứ ai cũng có thể mua hay bán khả năng khả năng tính toán giống như cách sử dụng điện hiện nay. Những thách thức đối với tính toán lưới Hầu hết các kỹ thuật phức tạpbên dưới dành cho Grid hiện nay đang được tiếp tục phát triển. Các môi trường Grid mẫu tồn tại giống như các dự án Globus và Legion. Đồ án EcoGrid thì đang nghiên cứu cách thức quản lý tài nguyên, và các khối xây dựng như vậy đang tồn tại trong trình quản lý tài nguyên mang tính thương mại của phần mềm Sun Grid Engine. Diễn đàn Grid (GGF – Global Grid Forum), được thành lập vào năm 1998, đã tập hợp được hàng trăm các nhà khoa học để cùng nhau nghiên cứu và thảo luận về một kiến trúc Grid chung. Trong đó vẫn còn tồn tại một số thách thức sau: Phát triền phần mềm ứng dụng cho Grid Chỉ ra và truy cập các nguồn tài nguyên tính toán thích hợp trên môi trường phân tán Định nghĩa những giao tiếp chuẩn cho phép giao tiếp giữa các khối Grid với nhau, nhằm đáp ứng nhu cầu phát triển ứng dụng. Bảo đảm các truy cập được xác nhận và truyền dữ liệu an toàn. Cung cấp các dịch vụ cho phép theo dõi, quảng cáo và kết xuất báo cáo. Thiết kế các nghi thức mạng cho việc trao đổi và định dạng thông điệp. Tính toán song song và phân bố Khái niệm Ngày nay trong khi công nghệ ngày một phát triển thì nhu cầu về tốc độ tính toán của các hệ thống máy tính cũng ngày một tăng cao. Các lĩnh vực đòi hỏi tính tóan hiệu năng cao như là mô hình số và giả lập các vấn đề của khoa học và công nghệ. Ngoài ra nó còn nhằm giải quyết các lọai vấn đề cần tốc độ xử lý cao như: Mô hình hóa và giả lập Mô hình các mẫu DNA Mô hình hóa chuyển động của các phi hành gia … Xử lý/Thao tác trên các dữ liệu rất lớn Xử lý ảnh và tín hiệu Khai thác dữ liệu và cơ sở dữ liệu Xác định địa chấn … Các vấn đề “grand challenge” (là những vấn đề không thể giải quyết trong thời gian “hợp lý”, như cần 100, 1000,…năm để có đáp án) Mô hình khí hậu Sự chuyển động của chất lỏng Bộ gene con người Mô hình chất bán dẫn … Xuất phát từ nhu cầu đó đã dẫn đến sự cần thiết phải có những hệ thống song song và phân bố nhằm tận dụng tối đa khả năng thực thi của các bộ xử lý, và để giải quyết các vấn đề nan giải trên. Nền tảng tính toán song song và phân bố Trong phần này chúng ta sẽ xem xét cách tổ chức logic và vật lý của các nền tảng song song và phân tán. Cách tổ chức logic liên quan đến quan điểm của người lập trình (kiến trúc xử lý song song và phân bố) trong khi cách tổ chức vật lý liên quan đến cách cơ cấu thực sự của các phần cứng bên dưới. Trong tính toán song song thì từ quan điểm của người lập trình gồm 2 thành phần chính quan trọng đó là cách thức thể hiện các tác vụ song song (cấu trúc điều khiển) và những phương pháp xác định tương tác giữa các tác vụ này (mô hình giao tiếp). Kiến trúc xử lý song song và phân bố Máy tính song song có thể được chia theo 2 lọai chính là : dòng điều khiển (control flow) và dòng dữ liệu (data flow). Máy tính song song dòng điều khiển dựa chủ yếu theo các nguyên tắc của máy tính Von Neumann, ngọai trừ nhiều dòng điều khiển có thể thực hiện vào bất cứ thời gian nào. Máy tính song song dòng dữ liệu , đôi khi được biết đến là “phi Von Neumann”, thì hoàn toàn khác biệt ở chỗ nó không có con trỏ trỏ tới các chỉ thị hiện hành hay trung tâm điều khiển. Ở đây chúng ta chỉ tập trung vào các máy tính song song dòng điều khiển. Năm 1966, M.J.Flynn đã phân chia các hệ thống máy tính dựa trên dòng chỉ thị và dòng điều khiển thành 4 loại sau: SISD (Single Instruction stream, a Single Data stream) SIMD (Single Instruction stream, Multiple Data streams) MISD (Multiple Instruction streams, a Single Data stream) MIMD (Multiple Instruction streams, Multiple Data streams) Phân theo mức độ hay được sử dụng: MIMD > SIMD > MISD Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson SISD Hình 2-2 : Kiến trúc SISD Kiến trúc này tương tự với kiến trúc Von Neumann. Một đơn vị điều khiển tiếp nhận một chỉ thị đơn từ bộ nhớ, sau đó đưa vào cho bộ xử lý thực thi trên một đơn vị dữ liệu được chỉ ra trong chỉ thị nhận được, và cuối cùng là đưa kết quả nhận được vào bộ nhớ. SIMD Hầu hết các máy tính song song ban đầu đều được thiết kế theo kiến trúc SIMD. Trong kiến trúc này, một đơn vị xử lý trung tâm sẽ thông dịch và quảng bá các tín hiệu điều khiển thích hợp cho các bộ xử lý theo chiều kim đồng hồ. Từng bộ xử lý sẽ thực thi các chỉ thị một cách đồng thời, và chúng cũng có quyền không tiếp nhận trên các chỉ thị nào đó. Sự phổ biến của kiến trúc SIMD là do tính năng của các ứng dụng song song ban đầu và từ yêu cầu của nền kinh tế. Theo quan điểm của người dùng thì các ứng dụng sử dụng kiến trúc SIMD thì dễ dàng được lập trình hơn và tận dụng hiệu quả hơn các thiết bị phần cứng. Hình 2-3 : Kiến trúc SIMD Bên trong SIMD, tồn tại hai lựa chọn thiết kế cơ bản sau: SIMD đồng bộ và bất đồng bộ. Trong một máy SIMD, từng bộ xử lý có thể thực thi hay bỏ qua các chỉ thị được quảng bá dựa vào trạng thái cục bộ của nó hay những điều kiện phụ thuộc vào dữ liệu. Tuy nhiên điều này có thể dẫn đến xử lý một vài tính toán điều kiện không hiệu quả. Một cách giải quyết khả thi là sử dụng phiên bản bất đồng bộ của S1IMD, được biết đến là SPMD (Single Program Multiple Data), trong đó từng bộ xử lý sẽ chạy một bản sao của chương trình chung. Điểm thuận lợi của SPMD là trong lúc tính toán biểu thức điều kiện “if-then-else”, từng bộ xử lý sẽ chỉ thực hiện ở nhánh thích hợp mà không mất thời gian cho các chi phí tính toán khác. Chip SIMD tùy chọn hay thống nhất (commodity). Một máy SIMD có thể được thiết kế dựa trên những thành phần thống nhất hay là từ những con chip tùy chọn. Trong cách tiếp cận thứ nhất thì các thành phần có xu hướng rẻ hơn do sản xuất hàng loạt. Tuy nhiên những thành phần mang mục đích chung như vậy có thể chứa các yếu tố không cần thiết cho một thiết kế cụ thể nào đó. Những thành phần thêm vào có thể làm phức tạp việc thiết kế, sản xuất và kiểm thử các máy SIMD và cũng có thể đem lại khiếm khuyết về tốc độ xử lý. Còn các thành phần tùy chọn thì nhìn chung hỗ trợ tốt hơn cho thực thi tuy nhiên nó cũng dẫn đến chi phí cao hơn cho việc phát triển. Khi việc tích hợp nhiều bộ xử lý cùng với bộ nhớ dư dật trên một con chip VLSI đơn trở nên khả thi, thì việc kết hợp ưu điểm của 2 cách tiếp cận trên là hoàn toàn có thể. MISD Mô hình này hầu như không thấy nhiều trong các ứng dụng. Một trong những lý do là bởi vì hầu hết các ứng dụng không thế áp dụng một cách dễ dàng vào kiến trúc MISD, điều này dẫn đến việc thiết kế ra một kiến trúc để thỏa mãn cho một mục đích chung là điều không thể. Tuy nhiên có thể áp dụng các bộ xử lý song song kiểu MISD vào trong một ứng dụng cụ thể nào đó. Hình 2-4 : Kiến trúc MISD Trong hình trên là ví dụ về một bộ xử lý song song với kiến trúc MISD. Một dòng dữ liệu đơn đi vào một máy tính gồm 5 bộ xử lý. Nhiều phép biến đổi được thực hiện trên từng đơn vị dữ liệu trước khi nó được chuyển sang một (hay nhiều) bộ xử lý khác.