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 2 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 = 2mlà tổng số bộ xử lý. Cho các bộ xử lý là P 0, P 1 … ..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 3 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.

Thí dụ

Trong Hình (a), X là một ma trận khối trong đó A, B, C, D là chính ma trận. Hình (f) cho thấy ma trận tổng.

Phép nhân ma trận khối

Khi hai ma trận khối là ma trận vuông, thì chúng được nhân giống như cách chúng ta thực hiện phép nhân ma trận đơn giản. Ví dụ,