2.2.1. Nhân ma trận trên kết nối lới hai chiều với mô hình tính toán Simd.
A Lower Bound Gentleman (1978) đã chỉ ra rằng việc nhân 2 ma trận cỡ n*n trên kết nối lới hai chiều với mô hình tính toán SIMD cần O(n) bớc tải dữ liệu.
Định nghĩa 2.1:
Cho dữ liệu sẵn có trớc đây sử dụng bộ xử lý đơn ở chế độ tính toán song song. Hàm δ(k) là số lợng tối đa các bộ xử lý mà dữ liệu đợc truyền với k b- ớc tải dữ liệu hoặc ít hơn. Trong kết nối lới hai chiều với mô hình tính toán SIMD δ(0) = 1; δ(1) = 5; δ(2) = 13; δ(k) = 2*k2 + 2*k + 1;
Bổ đề 2.1:
Giả sử rằng nhân hai ma trận A và B có cỡ là n*n và mỗi thành phần A và B đợc lu trử chính xác một lần và không có thành phần xử lý nào chứa hơn một phần tử của ma trận khác. Nếu ta bỏ qua bất cứ một tiện ích chuyển dữ liệu nào thì việc nhân ma trận A và B để có ma trận C có cỡ là n*n cần ít nhất S bớc tải dữ liệu với δ(2S) ≥ n2.
Chứng minh:
Xem một phần tử mảng Ci,j của ma trân kết quả thì phần tử này là kết quả của dòng i ma trận A và cột j của ma trân B. Phải có một đờng dẫn từ các bộ xử lý nơi mỗi phần tử này đợc lu trữ, đến nơi kết quả Ci,j đợc lu trử.
Nói cách khác việc tạo ra ma trận C cần ít nhất S bớc tải dữ liệu.
Chú ý rằng các đờng dẫn này có thể đợc sử dụng để xác định tập hợp các đờng dẫn có độ dài ít nhất là 2S từ phần tử bu,v, tới mỗi phần tử ai,j, với 1≤ i,j ≤ n;
Đó là bởi vì có một đờng dẫn có độ dài S từ bu,v đến bộ xử lý có Ci,v đ- ợc tìm thấy và cũng có một đờng dẫn độ dài ít nhất là từ ai,j đến Ci,v. Vì vậy, tồn tại một tuyến dẫn ít nhất dài 2S từ phần tử bu,v đến phần tử ai,j tơng tự các
đờng này cũng chỉ ra tập hợp những đờng dẫn có độ dài 2s từ phần tử au,v
đến mỗi phần tử bi,j mà ở đó 1≤ i,j ≤ n;
Định lý 2.1:
Nhân ma trận trên kết nối lới hai chiều với mô hình tính toán SIMD yêu cầu Ω(n) hoặc với các giá trị lớn xấp xỷ S ≥ 0.35n.
Chứng minh:
Từ bổ đề 2.1 ta có δ(2S) ≥ n2. Trên kết nối lới hai chiều với mô hình tính toán SIMD δ(S) = 2*S2 +2*S +1.
V× vËy δ(2S) ≥ 2*(2s)2 +2*(2S) +1.
Kết hợp hai điều trên ta có:
8S2 + 4S +1 ≥ n2
S2+
2 S +
8 1 ≥
8 n2
(S+
4 1)2+
16 1 ≥
8 n2
=> S ≥
4 1 4
* 2 2
n − .
Một giải thuật tối u: Cho kết nối lới hai chiều với mô hình tính toán SIMD có sự nối kết nối vòng. Dễ dàng chia một giải thuật có n2 bộ xử lý để
nhân hai mảng n*n trong O(n) thời gian. Từ n3 các phép nhân đợc yêu cầu (giả sử chúng ta đang dùng giải thuật tính toán tuyến tính). Nên cách duy nhất để n2 bộ xử lý có thể hoàn thành các phép nhân trong O(n) thời gian để cho các bộ xử lý O(n2) có mặt trong các kết quả của từng bớc. Kiểm tra sự
định vị ban đầu về các ma trận đối với các bộ xử lý, thành phần xử lý đặt tại hàng i, cột j hàm chứa ai,j và bi,j , để ý rằng trong trạng thái duy nhất này chỉ có n bộ xử lý chứa các cặp và 1 cặp vô hớng(scalars) phù hợp với phép nhân.
Tuy nhiên ta có thể xếp xen kẽ các ma trận A và B để mỗi bộ xử lý có một cặp vô hớng cần đợc nhân. Hơn nữa một quá trình quay lên của các phần tử trong B và một quá trình sang trái của các phần tử trong A thì mỗi bộ xử lýcác phần tử cùng với các giá trị đã đợc nhân.
b0.3 b0.2 b2.3
b2.3 b1.2
b0.1
a3.2 a2.1 a1.0
a0.0 b0.0
a0.1 b0.1
a0.2 b0.2
a0.3 b0.3
a1.0 b1.0
a1.1 b1.1
a1.2 b1.2
a1,3 b13
a2,0 b20
a2.1 b2,1
a2.2 b2.2
a2.3 b2.3
a3.2 b3.2 a3.1
b3.1 a3.0
b3.0
a3.3 b3.3
a0.0 b0.0
a0.1 b1.1
a0.2 b2.2
a0.3 b3.2
a1.1 b1.0
a1.2 b2.1
a1.3 b3.2
a0.3 b3.3
a2.2 b2.0
a2.3 b3.1
a2.0 b0.2
a2.1 b1.3
a3.1 b1.2 a3.0
b0.3 a3.3
b3.0
a3.2 b2.3
a3.0 a3.1 a2.0
a0.0 b0.0
a0.1 b1.1
a0.2 b2.2
a0.3 b3.3
a1,3 b3,2 a1.2
b2.1 a1.1
b0.1
a2,2 b0,2
a2,3 b3.1 a3.3
b3.0
H×nh 2.1
Nhìn vào hoạt động của một bộ xử lý đơn trong hình 2.2 sau đây, sau khi các ma trận A và B đợc xếp xen kẽ, bộ xử lý p1(1,2) thực hiên phép nhân và cộng hình thành kết quả c1,2
H×nh 2.2
Giải thuật nhân ma trận trên kết nối lới hai chiều với mô hình tính toán SIMD
{******************************************}
a1.1 b
1.2
a1.3 a1.0
a1.2
b2.2 b3.2 b0.2
a1.2 a1.3
a1.0 b
0.2
a1.1
b1.2 b2.2 b3.2
a1.3 b3.2
a1.1 a1.2
a1.0
b0.2 b1.2 b2.2
a1.0 a1.1 a1.2 b
2.2
b1.2
a1.3
b3.2 b0.2
Golbal n,k Local a,b,c Begin
{stagger marices}
for k 1 to n-1 do
for all p(i,j) where 1≤ i,j ≤ n do if i>k then a⇐ east(a)
endif if j>k then b ⇐ south(b) endif
endfor endfor
{ compute dot products}
for all p(i,j) where 1 ≤ i,j ≤ n c← a*b
endfor
for k ← 1 to n-1 do
for all p(i,j) where 1≤ i,j ≤ n do a ⇐ east(a)
b ⇐ sout(b) c ⇐ c+a*b endfor
endfor endfor end
{******************************************}
Giả sử nhân hai ma trận cỡ 2*2 trên máy tính song song có 2 bộ xử lý thì
mỗi bộ xử lý tính 1 dòng của ma trận kết quả
vÝ dô tÝnh:
Bộ xử lý p1 tính: c11 = 2*1 + 2*4 = 10 c12 = 2*5 + 2*2 = 14 Bộ xử lý p2 tính: c21 = 1*1 + 3*4 = 13 c22 = 1*5 + 3*2 = 11
Nh vậy, ta thấy rằng số lợng công việc phải thực hiện đợc chia đôi cho hai bộ xử lý, do đó độ phức tạp của thuật toán sẽ giảm một nửa.
2.2.2:Nhân ma trận trên kết nối dịch chuyển chuyển đổi theo mô– hình tính toán simd
Định lý 2.3:
Cho n3 = 23q bộ xử lý trên kết nối dịch chuyển–chuyển đổi theo mô
hình tính toán SIMD, hai ma trận có cỡ n*n có thể đợc nhân trong O(logn) thêi gian (Dekel et al. 1981)
Giải thuật cho kết nối dịch chuyển–chuyển đổi theo mô hình tính toán SIMD đóng vai trò định đờng hay giới thiệu giải thuật kết nối Hypecube theo mô hình tính toán SIMD. Có 13 log n bớc cho mô hình dịch chuyển- chuyển đổi, cũng có thể thực hiện đờng đi đó gần hơn bằng giải thuật kết nối Hypecube theo mô hình tính toán SIMD trong 5 log n bớc.Từ đây nhân ma trận trên kết nối dịch chuyển–chuyển đổi theo mô hình tính toán SIMD, có độ phức tạp O(logn), cho n3 = 23q bộ xử lý các phần tử.
2.3. Giải thuật cho cho bộ đa xử lý
A B C
2 2 1 3
1 5 4 2
10 14 13 11
=
Nhân ma trận có thể đợc thực hiện song song hoá trên bộ đa xử lý.
Trong giải thuật nối tiếp đầu chơng này cho ba vòng lặp có thể đợc song song hoá đợc. Điều đó đặt ra một câu hỏi thú vị : Có nhiều vòng lặp, tất cả
đều có khả năng song song hoá đợc, nhng khi nào thì nên chọn vòng lặp nào
để song song hoá?
Tổng phí tơng tác: Là lợng công việc đợc thực hiện giữa quá trình t-
ơng tác của các bộ xử lý, vì mục đích của chúng ta cực tiểu hoá tổng phí trong quá trình song song, nên chúng ta phải tối đa hoá tổng phí tơng tác bất cứ khi nào có thể.
Trong trờng hợp với nhân ma trận, chúng ta có thể song song hoá
vòng j hoặc vòng i mà không gây nên những vấn đề gì bởi vì sự phụ thuộc dữ liệu duy nhất nằm ở bên ngoài vòng trong cùng. Nếu chúng ta làm song song vòng j thì giải thuật song song n đồng bộ hoá và tổng phí tơng tác của mã song song là O(n3/p). Trên mỗi bộ xử lý có bộ nhớ riêng UMA vòng i đ- ợc song song hoá sẽ thực thi nhanh hơn.
Một giải thuật song song cho mô hình đa bộ xử lý có bộ xử lý riêng UMA đợc minh hoạ, các biến i, j, k và t đại diện cho các biến địa phơng để xử lý.
Tính phức tạp của giải thuật này là gì? mỗi quá trình tính toán n/p hàng của ma trận C, thời gian cần thiết để tính một hàng đơn là O(n2), do đó với một số ma trận cỡ lớn thì thời gian thực hiện sẽ tăng lên nhiều lần.
Giải thuật nhân ma trận cho đa bộ xử lý.
{******************************************}
Global n
a[0 (n-1)][0 (n-1)] … … b[0 (n-1)][0 (n-1)]… …
c[0 (n-1)][0 (n-1)]… …
Local i,j,k t Begin
For all pm where 1 m p do≤ ≤ For i ← m to n step p do For j ← i to n do t ← 0
for k ←1 to n do
t ← t + a[i][k] * b[k][j]
endfor endfor endfor endfor end
{******************************************}
Các quá trình đồng bộ duy nhất chỉ một lần, khi đó sự đồng bộ ở trên là O(p). vì thế độ phức tạp hầu hết của giải thuật song song này là
O(n3/p + p). chú ý vì chỉ có n hàng nên hầu hết với n bộ xử lý có thể thực thi giải thuật này.
Thờng thì có thể bỏ qua thời gian truy cập bộ nhớ? Đúng, đối với đa bộ xử lý có UMA nơi mỗi ô nhớ toàn cục có khoảng cách tơng tự nhau đến mỗi bộ xử lý. Nhng không đợc bỏ qua thời gian truy cập bộ nhớ trên sự kết nối với bộ đa xử lý. Khi một số phần tử của ma trận có thể truy cập đợc dễ dàng hơn các cái khác. Nhớ lại rằng kết nối với bộ đa xử lý cần giữ biến cục bộ càng nhiều thì bộ nhớ sẽ càng tốt. Thực vậy một điển hình truy nhập bộ xử lý phải thực thi n/p hàng của A mà nó còn phải thực hiện mỗi phần tử của B là n/p lần. Chỉ một phép cộng và một phép nhân đơn giản xảy ra cho mỗi phần tử của B đợc chuyển tải.
Một phơng pháp khác đợc tìm thấy để phân chia vấn đề, phơng pháp tốt đó là lợi dụng khối nhân ma trận. Giả sử A và B ma trận cỡ n*n, n = 2k.
A và B đợc coi là những khối của ma trận nhỏ hơn k*k:
Chia A và B thành từng khối. C đợc xác định nh sau:
Nếu ta thiết kế bộ xử lý để làm khối nhân ma trận, thì phép nhân và phép cộng trên mỗi phần tử ma trận sẽ tăng lên. Ví dụ giả sử rằng có
p = (n/k)2 bộ xử lý. Nhân ma trận đợc thực hiện bằng cách chia A và B thành từng khối cỡ k*k, mỗi khối nhân yêu cầu 2k2 bộ nhớ đã chuyển tải, k3 phép cộng và k3 phép nhân. Số lợng của các thao tác toán học trên mỗi lần truy cập bộ nhớ tăng từ 2, ở giải thuật trớc đến k = n/p trong giải thuật mới một sự cải tiến đáng kể.
Ostlund, Hibbard and Whiteside (1982) đã tiến hành nhân giải thuật trên Cm* cho nhiều ma trận kích cỡ khác nhau.
Giải thuật nhân khối ma trận thực hiện tốt hơn trên đa bộ xử lý UMA bởi vì nó tăng số lợng tính toán đợc thực hiện trên bộ nhớ. Vì những nguyên nhân tơng tự mà một số lựa chọn các kiểu khối để tối đa hoá bộ nhớ đệm có thể mang lại một giải thuật nối tiếp, hớng-khối nhân ma trận đợc thực thi nhanh hơn giải thuật đã đợc chỉ ra trong mục 2-1.
Một ví dụ về cách tiếp cận khối ma trận đến nhân ma trận song song
= A11 A12
A21 A22
B11 B12
B21 B22
A B =
= C11 C12 =
C21 C22
A11B11+A12B21 A11B12+A12B22
A21B11+A22B21 A21B12+A22B22 C
1 0 2 3 4 -1 1 5 -2 -3 -4 2 -1 2 0 0
-1 1 2 -3 -5 -4 2 -2 3 -1 0 2 1 0 4 5
=
8 -1 14 16 9 7 26 17 7 14 -2 14 -9 -9 2 -1
Bíc 1: TÝnh ci,j = Ai,1B1,j
Bíc 2: TÝnh ci,j = ci,j + Ai,2B2,j
Hình 2.4: Độ tăng trởng của giải thuật nhân ma trận trên Cm*.
Nh vậy, trong phạm vi chơng này chúng ta đã nghiên cứu một vài giải thuật nhân ma trận trên mô hình Máy tính song song, tuy nhiên có nhiều giải thuật để thực hiện điều này nh giải thuật kết nối Hypercube trên mô hình tính toán SIMD, giải thuật hớng hàng cột…
n=48 n=36
n=24
1 4 9 16 12
10 8
6 4 2
n=30
-1 1 2 -3 1 8 6 -10 17 10 -10 12 -9 -9 2 -1
1 0 4 -1
-1 1 5 -4
1 0 4 -1
2 -3 2 -3 -2 -3
-1 2
-1 1 -5 -4
-2 -3 -1 2
2 -3 2 -3
=
-4 -2 0 0
3 -1 1 0
-4 2 0 0
0 2 4 5
8 -1 14 16 9 7 26 17 7 14 -2 14 -9 -9 2 -1
2 3 1 5
3 -1 1 0
2 3 1 5
0 2 4 5
=
---
Chơng III
Giải quyết các hệ tuyến tính
Trong chơng này chúng ta khảo sát các giải thuật song song, dùng để giải các hệ phơng trình tuyến tính. Nhiều vấn đề của các ngành khoa học và công nghệ có thể làm thành một hệ thống của các phơng trình tuyến tính.
Bởi vì việc giải quyết các vấn đề của hệ thống thờng khá lớn. Đó là một lý do đúng để giải quyết các hệ thống của máy tính song song có hiệu quả.
Trong mục 3.1, chúng ta thực hiện 2 ví dụ và xây dựng thuật ngữ dùng ở phần sau của chơng này. Mục 3.2 đến 3.4 các phơng pháp giải trực tiếp đối với các hệ tuyên tính
Cuối cùng mục 3.5 mô tả giải thuật đờng dốc liên hợp một giải thuật hội tụ nhanh để giải quyết các hệ phơng trình tuyến tính nhất định
3.1 ThuËt ng÷
Phần này định nghĩa một vài điểm quan trọng và minh hoạ các vấn đề có thể đợc giải quyết đối với hệ thống tuyến tính.
Định nghĩa 3.1:
Phơng trình tuyến tính n biến x1, x2, x3, , x… n là một phơng trình đợc viết bởi
a1x1 + a2x2 + a3x3 + + a… nxn = b (3.1)
với a1 , a2, a3, , a… n là các hằng số
Định nghĩa 2:
Một tập hữu hạn các phơng trình tuyến tính của các biến
x1, x2, x3, , x… n có thể đợc gọi là hệ phơng trình tuyến tính của hệ tuyến tính hoặc là một hệ tuyến tính. Một tập số s1, s2, s3, , s… n, là một giải pháp để một hệ thống của các phơng trình tuyến tính nếu và chỉ nếu nó tạo đợc sự thay
thế x1 = s1, x2 = s2, x3 = s3, ,x… n = sn. Thoả mãn mọi phơng trình trong hệ tuyÕn tÝnh.
Một hệ của n phơng trình tuyến tính với n biến đợc viết
a11x1 + a12x2 +a13x3 + +a… 1nxn = b1
a21x1 + a22x2 +a23x3 + +a… 2nxn = b2
a131x1 + a32x2 +a33x3 + +a… 3nxn = b3 (3.2)
… … … … an1x1 + an2x2 +an3x3 + +a… nnxn = bn
Thờng dùng biểu thức Ax = b với A là một ma trận n*n chứa các giá
trị ai,js và x và b là một vector n-phần tử, thành xis và bis tơng ứng. Các biến cục bộ và các phần tử của ma trận A là khác 0, làm thế nào để tính đợc các giá trị của x, trong tờng hợp chung nhất, một giải thuật tuyến tính tuần tự có
độ phức tạp thời gian là O(n3) để có thể giải đợc hệ tuyến tính, đây là một vấn đề của nhiều hệ tuyến tính không có dạng đặc biệt một ví dụ đợc lấy từ Hailiday và Resnick (1974). Xem mỗi phần tử của mạch trong hình 3.1, hai nguồn bin cung cấp E1 và E2 đối với mạch ba điện trở là R1, R2, và R3. Cho những giá trị của nó và chúng ta muốn tính 3 dòng điện i1, i2 và i3 bằng cách
áp dụng dịnh luật của vật lý chúng ta có thể thành lập hệ ba phơng trình, với ba biến i1, i2 và i3 cha biết
i1 -i2 +i3 = 0
-R1i1 +R3i3 = -E1 (3.3) -R2i2 -R3i3 = E2
E
2
E
1
R1 i1 R3 R2
E1 E
2
i2 i3
Hình 3.1 Một mạch điện và ba điện trở
Hệ phơng trình với giá trị bằng 0 ở bên phải có thể đợc giải quyết nhanh hơn hệ phơng trình có dạng bình thờng. Ví dụ nh hệ 3 phơng trình hoặc hệ 3
đờng chéo
Định nghĩa 3.3:
Một ma trận a có cỡ n*n là một ma trận tam giác trên nÕu i>j ⇒ ai,j = 0
Định nghĩa 3.4:
Một ma trận A cỡ n*n là một ma trận tam giác dới nếu i<j ⇒ ai,j = 0
Hệ tam giác trên và tam giác dới có thể đợc giải với độ phức tạp tính toán O(n2).
Định nghĩa 3.5:
Một ma trận A cỡ n*n đợc gọi là ma trận đờng chéo nếu và chỉ nếu i - j> 1 ⇒ ai,j = 0
Một hệ tuyến tính Ax = b có thể đợc gọi là một hệđờng chéo nếu nh các hệ số của ma trận A làm thành một đờng chéo, giải thuật liên tục với độ phức tạp thơi gian O(n), dùng để giải hệ đờng chéo này. Giả thiết rằng chúng ta muốn xác định trạng thái nhiệt độ chính thức phân phối trên một thanh vật chất ở hình 3.2 sau.
H×nh 3.2
Chúng ta giả thiết rằng thanh đó có một trục ngang và tất cả các điểm trên trục ngang đó có cùng một nhiệt độ, điều này cho phép chúng ta mô tả
nhiệt độ nh là một hàm khoảng cách từ một điểm đến cuối của thanh. Chúng ta giả sử rằng nhiệt độ T1, T2 là điểm đầu và cuối của thanh là cố định trong suốt quá trình có nguồn điện, cuối cùng chúng ta giả sử rằng thanh này đợc bao phủ bởi cùng một loại vật chất( thanh đồng chất ) nói cách khác độ nóng trên toàn thanh này là không thay đổi.
Xác dịnh trạng thái nhiệt độ ở tại 4 điểm x1, x2, x3, x4 có thể đợc xác
định bởi một hệ phơng trình tuyến tính
x x1 x2 x3 x4
T1 T2
E
2
E
1
x1 – 0.5x2 = 0.5T1
-0.5x1 + x2 - 0.5x3 = 0 (3.4) 0.5x2 + x3 – 0.5x4 = 0
-0.5x3 + x4 = 0.5T2
Đây là ba định nghĩa mà chúng ta thờng dùng trong những trờng hợp sau này:
Địng nghĩa 3.6:
Một ma trận A cỡ n*n là ma trận tam giác trội nếu ai,i >∑j=i ai,j víi 1 ≤ i,j ≤ n.
Định nghĩa 3.7:
Một ma trận A cỡ n*n là một ma trận đối xứng nếu aji = aị
Định nghĩa 3.8:
Một ma trận A cỡ n*n là một ma trận nghịch đảo nếu nh ma trận đó là ma trận đối xứng và ma trận tam giác trội và aii > 0 với 1 ≤ i,j ≤ n.
3.2 phơng pháp thế ngợc ( back suutitution)
Trong phần này chúng ta miêu tả tính song song của một giải thuật dùng để giải quyết hệ tuyến tính Ax = b, với A là ma trận tam giác trên. Cho hệ phơng trình tuyến tính, với A là ma trận tam giác trên cỡ n*n. Dùng giải thuật thay thế để giải quyết hệ tuyến tính với độ phức tạp thời gian O(n2). Hãy xem giải thuật này bằng một ví dụ đơn giản, giả sử chúng ta giải hệ
1x1 + 1x2 – 1x3 + 4x4 = 8 - 2x2 – 3x3 + 1x4 = 5
2x3 – 3x4 = 0 (3.5) 2x4 = 4
Chúng ta có thể giảiphơng trình cuối cùng khi mà nó chỉ có một biến. Từ đó chúng ta xác định đợc x4 = 2, chúng ta có thể làm đơn giản các phơng trình còn lại bằng cách thay thế những giá trị của x4 vào các phơng trình:
1x1 + 1x2 – 1x3 = 0 - 2x2 – 3x3 = 3
2x3 = 6 (3.6) 2x4 = 4
Bây giờ thì phơng trình thứ ba chỉ có một biến và chúng ta dùng phép chia
đơn giản để có x3 = 3. Tiếp theo chúng ta dùng phơng trình này để đơn giản hai phơng trình còn lại
1x1 + 1x2 = 3
- 2x2 = 12
2x3 = 6 (3.7) 2x4 = 4 Chúng ta có phơng trình đơn giản thứ hai chỉ chứa có một biến dùng phép
chia b2 cho a22. Ta đợc x2 = -6.sau đó lấy x2*a22 từ bớc một chúng ta có ph- ơng trình 1x1 = 3
- 2x2 = 2
2x3 = 6 (3.8) 2x4 = 4
và nó thật dễ dàng để giải x1 = 3
Một giải thuật thay thế ngợc có độ phức tạp thời gian O(n2).
Sau đây là hai giải thuật Back.Substitution(SISD) và Back.Substitution(uma multiprocessor)
Giải thuật tuần tự giải hệ ph ơng trình tuyến tính với A là ma trận tam giác( back.substitution(sisd)):
{******************************************}
Global n { cỡ của hệ thống}
a[1..n][1..n] { phần tử của a } b[1..n] { phần tử của b } x[1..n] { phần tử của x } i { chỉ số hàng } j { chỉ số cột } begin
2 for 1 ← n dowto 1 do x[i] ← b[i]/a[i][i]
3 for 1 ← 1 to i-1 do
4 b[j] ← b[j] – x[i] * a[j][i]
5 a[j][i] ← 0 6 endfor
endfor end
{******************************************}
Giải thuật song song dùng bộ xử lý riêng UMA trên đa bộ xử lý (
back.substitution(uma multiprocessor)):
{******************************************}
Global n { cỡ của hệ thống}
P { số bộ xử lý}
a[1..n][1..n] { phần tử của a } b[1..n] { phần tử của b } x[1..n] { phần tử của x } i { chỉ số hàng } local k { chỉ số cột } j { bộ xử ký chỉ định}
begin
for 1 ← n dowto 2 do x[i] ← b[i] / a[i][i]
forall pj where 1 ≤ j ≤ p do for k ← j to i-1 step p do b[k] ← b[k] – x[i] * a[k][i]
a[k][i] ← 0 endfor
endforall endfor end
{******************************************}
Với giải thuật này chúng ta có thể sử dụng để giải quyết các hệ phơng trình tuyến tính n ẩn, đầu tiên bộ xử lý thứ nhất sẽ tính giá trị xn và gửi giá trị này
đến tất cả các bộ xử lý, từ đó các bộ xử lý này sẽ thay các giá trị xn đã biết vào tất cả các phơng trình chứa ẩn xn tiếp tục bộ xử lý p2 sẽ tính đợc xn-1 nó cũng gửi giá trị này đến tất cả các bộ xử lý và cứ thế cho đến khi tìm đợc hết giá trị các ẩn của x .
3.3 phơng pháp khử Gauss
Trong phần này mô tả tính song song của giải thuật khử Gauss là một giải thuật nổi tiếng để giải hệ tuyến tính Ax = b, khi ma trận A có các giá
trị khác không. Phơng pháp khử Gauss đa ma trận a về dạng ma trận tam