Máy truy cập ngẫu nhiên song song

Parallel Random Access Machines (PRAM)là một mô hình, được xem xét cho hầu hết các thuật toán song song. Ở đây, nhiều bộ vi xử lý được gắn vào một khối bộ nhớ. Một mô hình PRAM chứa -

Một tập hợp các loại vi xử lý tương tự.
Tất cả các bộ xử lý chia sẻ một đơn vị bộ nhớ chung. Các bộ xử lý chỉ có thể giao tiếp với nhau thông qua bộ nhớ dùng chung.
Bộ truy cập bộ nhớ (MAU) kết nối bộ xử lý với một bộ nhớ dùng chung.

Đây, n số lượng bộ xử lý có thể thực hiện các hoạt động độc lập trên nsố lượng dữ liệu trong một đơn vị thời gian cụ thể. Điều này có thể dẫn đến việc truy cập đồng thời vào cùng một vị trí bộ nhớ bởi các bộ xử lý khác nhau.

Để giải quyết vấn đề này, các ràng buộc sau đã được thực thi trên mô hình PRAM:

Exclusive Read Exclusive Write (EREW) - Ở đây không có hai bộ vi xử lý nào được phép đọc từ hoặc ghi vào cùng một vị trí bộ nhớ cùng một lúc.
Exclusive Read Concurrent Write (ERCW) - Ở đây không có hai bộ xử lý nào được phép đọc đồng thời từ cùng một vị trí bộ nhớ, nhưng được phép ghi vào cùng một vị trí bộ nhớ cùng một lúc.
Concurrent Read Exclusive Write (CREW) - Ở đây tất cả các bộ vi xử lý được phép đọc đồng thời từ cùng một vị trí bộ nhớ, nhưng không được phép ghi vào cùng một vị trí bộ nhớ cùng một lúc.
Concurrent Read Concurrent Write (CRCW) - Tất cả các bộ xử lý được phép đọc hoặc ghi vào cùng một vị trí bộ nhớ cùng một lúc.

Có nhiều phương pháp để triển khai mô hình PRAM, nhưng những phương pháp nổi bật nhất là -

Mô hình bộ nhớ dùng chung
Mô hình truyền thông điệp
Mô hình song song dữ liệu

Mô hình bộ nhớ dùng chung

Bộ nhớ dùng chung nhấn mạnh vào control parallelism hơn trên data parallelism. Trong mô hình bộ nhớ dùng chung, nhiều quá trình thực thi trên các bộ xử lý khác nhau một cách độc lập, nhưng chúng chia sẻ một không gian bộ nhớ chung. Do bất kỳ hoạt động nào của bộ xử lý, nếu có bất kỳ thay đổi nào trong bất kỳ vị trí bộ nhớ nào, phần còn lại của bộ xử lý sẽ hiển thị.

Khi nhiều bộ xử lý truy cập vào cùng một vị trí bộ nhớ, có thể xảy ra tại bất kỳ thời điểm cụ thể nào, nhiều bộ xử lý đang truy cập vào cùng một vị trí bộ nhớ. Giả sử một người đang đọc vị trí đó và người kia đang viết trên vị trí đó. Nó có thể tạo ra sự nhầm lẫn. Để tránh điều này, một số cơ chế kiểm soát, nhưlock / semaphore, được thực hiện để đảm bảo loại trừ lẫn nhau.

Lập trình bộ nhớ dùng chung đã được thực hiện như sau:

Thread libraries- Thư viện luồng cho phép nhiều luồng điều khiển chạy đồng thời trong cùng một vị trí bộ nhớ. Thư viện luồng cung cấp một giao diện hỗ trợ đa luồng thông qua một thư viện chương trình con. Nó chứa các chương trình con cho
- Tạo và hủy chuỗi
- Lập lịch thực hiện chuỗi
- truyền dữ liệu và tin nhắn giữa các chuỗi
- lưu và khôi phục ngữ cảnh chuỗi

Ví dụ về thư viện luồng bao gồm - luồng SolarisTM cho Solaris, luồng POSIX được triển khai trong Linux, các luồng Win32 có sẵn trong Windows NT và Windows 2000 và các luồng JavaTM như một phần của Bộ phát triển JavaTM tiêu chuẩn (JDK).

Distributed Shared Memory (DSM) Systems- Hệ thống DSM tạo ra một sự trừu tượng của bộ nhớ dùng chung trên kiến trúc được ghép nối lỏng lẻo để thực hiện lập trình bộ nhớ dùng chung mà không cần hỗ trợ phần cứng. Chúng triển khai các thư viện tiêu chuẩn và sử dụng các tính năng quản lý bộ nhớ cấp người dùng nâng cao có trong các hệ điều hành hiện đại. Ví dụ bao gồm Tread Marks System, Munin, IVY, Shasta, Brazos và Cashmere.
Program Annotation Packages- Điều này được thực hiện trên các kiến trúc có đặc tính truy cập bộ nhớ đồng nhất. Ví dụ đáng chú ý nhất về các gói chú thích chương trình là OpenMP. OpenMP thực hiện song song chức năng. Nó chủ yếu tập trung vào việc song song hóa các vòng lặp.

Khái niệm bộ nhớ dùng chung cung cấp khả năng kiểm soát mức độ thấp đối với hệ thống bộ nhớ dùng chung, nhưng nó có xu hướng tẻ nhạt và sai lầm. Nó có thể áp dụng cho lập trình hệ thống hơn là lập trình ứng dụng.

Ưu điểm của lập trình bộ nhớ dùng chung

Không gian địa chỉ toàn cục cung cấp cách tiếp cận lập trình thân thiện với người dùng đối với bộ nhớ.
Do sự gần gũi của bộ nhớ với CPU, việc chia sẻ dữ liệu giữa các quá trình diễn ra nhanh chóng và đồng nhất.
Không cần phải xác định rõ ràng việc truyền dữ liệu giữa các quá trình.
Chi phí truyền thông quy trình là không đáng kể.
Nó rất dễ học.

Điểm mạnh của lập trình bộ nhớ dùng chung

Nó không phải là di động.
Quản lý dữ liệu cục bộ là rất khó khăn.

Mô hình chuyển thông báo

Truyền thông điệp là phương pháp lập trình song song được sử dụng phổ biến nhất trong các hệ thống bộ nhớ phân tán. Ở đây, người lập trình phải xác định độ song song. Trong mô hình này, tất cả các bộ xử lý đều có bộ nhớ cục bộ của riêng chúng và chúng trao đổi dữ liệu thông qua mạng truyền thông.

Các bộ xử lý sử dụng các thư viện truyền thông điệp để liên lạc với nhau. Cùng với dữ liệu được gửi đi, thông báo có chứa các thành phần sau:

Địa chỉ của bộ xử lý mà từ đó tin nhắn được gửi đi;
Địa chỉ bắt đầu của vị trí bộ nhớ của dữ liệu trong bộ xử lý gửi;
Kiểu dữ liệu của dữ liệu gửi;
Kích thước dữ liệu của dữ liệu gửi;
Địa chỉ của bộ xử lý mà thông báo được gửi đến;
Địa chỉ bắt đầu của vị trí bộ nhớ cho dữ liệu trong bộ xử lý nhận.

Các bộ xử lý có thể giao tiếp với nhau bằng bất kỳ phương thức nào sau đây:

Giao tiếp điểm-điểm
Giao tiếp tập thể
Giao diện chuyển thông báo

Giao tiếp điểm-điểm

Truyền thông điểm-điểm là hình thức truyền thông điệp đơn giản nhất. Tại đây, một tin nhắn có thể được gửi từ bộ xử lý gửi đến bộ xử lý nhận bằng bất kỳ chế độ truyền nào sau đây:

Synchronous mode - Tin nhắn tiếp theo chỉ được gửi sau khi nhận được xác nhận rằng tin nhắn trước đó đã được gửi, để duy trì trình tự của tin nhắn.
Asynchronous mode - Để gửi tin nhắn tiếp theo, không cần nhận được xác nhận đã gửi tin nhắn trước.

Giao tiếp tập thể

Giao tiếp tập thể liên quan đến nhiều hơn hai bộ xử lý để truyền thông điệp. Các chế độ sau cho phép giao tiếp tập thể -

Barrier - Chế độ rào cản có thể thực hiện được nếu tất cả các bộ xử lý bao gồm trong giao tiếp chạy một bock cụ thể (được gọi là barrier block) để truyền tin nhắn.
Broadcast - Phát thanh có hai loại -
- One-to-all - Ở đây, một bộ xử lý với một thao tác duy nhất sẽ gửi cùng một thông báo đến tất cả các bộ xử lý khác.
- All-to-all - Tại đây, tất cả các bộ xử lý gửi tin nhắn đến tất cả các bộ xử lý khác.

Tin nhắn được phát đi có thể có ba loại -

Personalized - Tin nhắn duy nhất được gửi đến tất cả các bộ xử lý đích khác.
Non-personalized - Tất cả các bộ xử lý đích đều nhận được cùng một thông báo.
Reduction - Trong phát sóng giảm, một bộ xử lý của nhóm thu thập tất cả các thông báo từ tất cả các bộ xử lý khác trong nhóm và kết hợp chúng thành một thông báo duy nhất mà tất cả các bộ xử lý khác trong nhóm có thể truy cập.

Điểm mạnh của việc truyền tin nhắn

Cung cấp khả năng kiểm soát song song mức thấp;
Nó là di động;
Ít bị lỗi;
Ít chi phí hơn trong đồng bộ hóa song song và phân phối dữ liệu.

Điểm mạnh của việc truyền tin nhắn

So với mã bộ nhớ dùng chung song song, mã truyền thông báo thường cần nhiều phần mềm hơn.

Thư viện chuyển thư

Có rất nhiều thư viện chuyển thư. Ở đây, chúng ta sẽ thảo luận về hai trong số các thư viện chuyển thư được sử dụng nhiều nhất -

Giao diện truyền thông báo (MPI)
Máy ảo song song (PVM)

Giao diện truyền thông báo (MPI)

Nó là một tiêu chuẩn chung để cung cấp giao tiếp giữa tất cả các quá trình đồng thời trong một hệ thống bộ nhớ phân tán. Hầu hết các nền tảng tính toán song song thường được sử dụng đều cung cấp ít nhất một giao diện truyền thông điệp triển khai. Nó đã được triển khai dưới dạng tập hợp các hàm được xác định trước được gọi làlibrary và có thể được gọi từ các ngôn ngữ như C, C ++, Fortran, v.v. MPIs vừa nhanh vừa di động so với các thư viện truyền thông điệp khác.

Merits of Message Passing Interface

Chỉ chạy trên kiến trúc bộ nhớ chia sẻ hoặc kiến trúc bộ nhớ phân tán;
Mỗi bộ xử lý có các biến cục bộ riêng;
So với máy tính bộ nhớ dùng chung lớn, máy tính bộ nhớ phân tán ít tốn kém hơn.

Demerits of Message Passing Interface

Cần có nhiều thay đổi lập trình hơn đối với thuật toán song song;
Đôi khi khó gỡ lỗi; và
Không hoạt động tốt trong mạng giao tiếp giữa các nút.

Máy ảo song song (PVM)

PVM là một hệ thống truyền thông điệp di động, được thiết kế để kết nối các máy chủ không đồng nhất riêng biệt để tạo thành một máy ảo duy nhất. Nó là một tài nguyên máy tính song song có thể quản lý được. Các vấn đề tính toán lớn như nghiên cứu siêu dẫn, mô phỏng động học phân tử và thuật toán ma trận có thể được giải quyết hiệu quả hơn về chi phí bằng cách sử dụng bộ nhớ và sức mạnh tổng hợp của nhiều máy tính. Nó quản lý tất cả các định tuyến tin nhắn, chuyển đổi dữ liệu, lập lịch tác vụ trong mạng các kiến trúc máy tính không tương thích.

Features of PVM

Rất dễ cài đặt và cấu hình;
Nhiều người dùng có thể sử dụng PVM cùng một lúc;
Một người dùng có thể thực thi nhiều ứng dụng;
Đó là một gói nhỏ;
Hỗ trợ C, C ++, Fortran;
Đối với một chương trình PVM nhất định, người dùng có thể chọn nhóm máy;
Nó là một mô hình truyền thông điệp,
Tính toán dựa trên quy trình;
Hỗ trợ kiến trúc không đồng nhất.

Lập trình song song dữ liệu

Trọng tâm chính của mô hình lập trình song song dữ liệu là thực hiện đồng thời các hoạt động trên một tập dữ liệu. Tập dữ liệu được tổ chức thành một số cấu trúc như mảng, siêu khối, v.v. Các bộ xử lý thực hiện các hoạt động tập thể trên cùng một cấu trúc dữ liệu. Mỗi tác vụ được thực hiện trên một phân vùng khác nhau của cùng một cấu trúc dữ liệu.

Nó là hạn chế, vì không phải tất cả các thuật toán đều có thể được chỉ định về tính song song dữ liệu. Đây là lý do tại sao song song dữ liệu không phải là phổ quát.

Các ngôn ngữ song song dữ liệu giúp chỉ định phân tách và ánh xạ dữ liệu tới các bộ xử lý. Nó cũng bao gồm các câu lệnh phân phối dữ liệu cho phép lập trình viên có quyền kiểm soát dữ liệu - ví dụ, dữ liệu nào sẽ đi trên bộ xử lý nào - để giảm lượng giao tiếp trong bộ xử lý.