Thuật toán song song - Phép nhân ma trận

Ma trận là một tập hợp dữ liệu số và không số được sắp xếp theo một số hàng và cột cố định. Phép nhân ma trận là một thiết kế phép nhân quan trọng trong tính toán song song. Ở đây, chúng ta sẽ thảo luận về việc thực hiện phép nhân ma trận trên các mạng truyền thông khác nhau như mesh và hypercube. Mesh và hypercube có khả năng kết nối mạng cao hơn, vì vậy chúng cho phép giải thuật nhanh hơn các mạng khác như mạng vòng.

Mạng lưới

Cấu trúc liên kết trong đó một tập hợp các nút tạo thành lưới p-chiều được gọi là cấu trúc liên kết lưới. Ở đây, tất cả các cạnh đều song song với trục lưới và tất cả các nút liền kề có thể giao tiếp với nhau.

Tổng số nút = (số nút trong hàng) × (số nút trong cột)

Một mạng lưới có thể được đánh giá bằng cách sử dụng các yếu tố sau:

Diameter
Chiều rộng vết nứt

Diameter - Trong một mạng lưới, dài nhất distancegiữa hai nút là đường kính của nó. Một mạng lưới p-chiều cókP các nút có đường kính là p(k–1).

Bisection width - Chiều rộng đường phân giác là số cạnh tối thiểu cần lấy ra khỏi một mạng để chia mạng mắt lưới thành hai nửa.

Phép nhân ma trận sử dụng mạng lưới

Chúng tôi đã xem xét một mô hình SIMD mạng lưới 2D có các kết nối bao quanh. Chúng tôi sẽ thiết kế một thuật toán để nhân hai mảng n × n bằng cách sử dụng n ² bộ xử lý trong một khoảng thời gian cụ thể.

Ma trận A và B lần lượt có các phần tử a _ij và b _ij . Phần tử xử lý PE _ij biểu diễn a _ij và b _ij . Sắp xếp ma trận A và B sao cho mọi bộ xử lý đều có một cặp phần tử để nhân. Các phần tử của ma trận A sẽ di chuyển theo hướng trái và các phần tử của ma trận B sẽ chuyển động theo hướng lên. Những thay đổi này về vị trí của các phần tử trong ma trận A và B thể hiện mỗi phần tử xử lý, PE, một cặp giá trị mới để nhân.

Các bước trong thuật toán

Gộp hai ma trận.
Tính tất cả các sản phẩm, a _ik × b _kj
Tính tổng khi bước 2 hoàn tất.

Thuật toán

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Mạng siêu khối

Siêu hình lập phương là một cấu trúc n chiều trong đó các cạnh vuông góc với nhau và có cùng độ dài. Siêu hình lập phương n chiều còn được gọi là hình lập phương n hoặc hình lập phương n chiều.

Đặc điểm của Hypercube với 2 ^k nút

Đường kính = k
Chiều rộng đường phân giác = 2 ^{k – 1}
Số cạnh = k

Phép nhân ma trận sử dụng mạng siêu khối

Đặc điểm kỹ thuật chung của mạng Hypercube -

Để cho N = 2^mlà tổng số bộ xử lý. Cho các bộ xử lý là P _0, P ₁ … ..P _N-1 .
Gọi i và i ^b là hai số nguyên, 0 <i, i ^b <N-1 và biểu diễn nhị phân của nó chỉ khác nhau ở vị trí b, 0 <b <k – 1.
Chúng ta hãy xem xét hai ma trận n × n, ma trận A và ma trận B.
Step 1- Các phần tử của ma trận A và ma trận B được gán cho n ³ bộ xử lý sao cho bộ xử lý ở vị trí i, j, k sẽ có a _ji và b _ik .
Step 2 - Tất cả bộ xử lý ở vị trí (i, j, k) tính toán sản phẩm

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 - Tổng C (0, j, k) = ΣC (i, j, k) với 0 ≤ i ≤ n-1, trong đó 0 ≤ j, k <n – 1.

Ma trận khối

Ma trận khối hay ma trận phân vùng là ma trận mà mỗi phần tử tự nó đại diện cho một ma trận riêng lẻ. Các phần riêng lẻ này được gọi làblock hoặc là sub-matrix.