Đồ án Thiết kế giải thuật song song

xử lý trên máy đích. Hiệu năng của giải thuật có thể giảm đi khi đồ thị giải thuật không là đồ thị con của đồ thị con của tổ chức bộ xử lý. Lấy ví dụ như, giả sử chúng ta thực thi giải thuật song song trên mô hình multicomputer sử dụng kỹ thuật định đường store and forward và hai đỉnh kết nối trong đồ thị giải thuật ánh xạ sang hai nút xa nhau (Hình a ). Khi truyền một message từ một bộ xử lý tới bộ xử lý khác sẽ yêu cầu thời gian xấp xỉ gấp hai lần thời gian truyền giữa hai bộ xử lý cạnh nhau hoặc giả sử chúng ta thực thi một giải thuật song song trên mô hình multicomputer với kỹ thuật chuyển mạch và các đỉnh khác nhau trong đồ thị giải thuật ánh xạ sang một liên kết chung trên máy ( Hình b). Nếu truyền thông đồng thời xảy ra giữa hai cặp nút thì tốc độ truyền thông sẽ bị ảnh hưởng không tốt khi dùng chung cùng kết nối. Trên một vài hệ thống, một message sẽ bị khoá tận đến khi message khác kết thúc việc truyền còn trên các hệ thống khác thì kết nối vật lý sẽ bị dồn lại giữa hai kết nối ảo, cắt một nửa băng thông của mỗi kết nối. Trong trường hợp này, hiệu năng sẽ giảm thấp đi bởi vì một message không được sử dụng riêng một đường truyền thông. Hình (b) Hình (a) Định nghĩa : Giả sử là hàm nhúng (embedding ) đồ thị G=(V, E) vào trong đồ thị G(V, E). Dilation của hàm nhúng được định nghĩa như sau: dil() = max { dist((u), (v)) | (u, v) E} với dist(a, b) là khoảng cách giữa hai đỉnh a và b trong đồ thị G. Với V, V là tập các đỉnh E, E là tập các cạnh của G và G. Ví dụ : Dilation =1 nếu G là đồ thị con của G. G G Load (Nạp tải) của hàm : G G là số đỉnh lớn nhất trong V được ánh xạ sang một đỉnh đơn trong V. Congestion ( Sự tắc nghẽn) của hàm : G G là số cạnh lớn nhất trong E được ánh xạ sang một đỉnh đơn trong E. Ta đều mong muốn có thể đạt được Dilation, Load, Congestion đều bằng 1, tuy nhiên điều lý tưởng này khó có thể đạt được trong thực tế. Để tối ưu việc ánh xạ của đồ thị tác vụ bất kỳ vào trong kiến trúc máy đích bất kỳ là bài toán khó có thể giải quyết được ( có độ phức tạp thời gian là NP- complete). Do đó ở đây ta chỉ xem xét bốn đồ thị giải thuật quan trọng là cây nhị phân hoàn chỉnh, cây nhị thức( Binomial Tree), Ring và Mesh sang mạng bộ xử lý thường được ứng dụng là Mesh hai chiều và Hypercube. 3. 2. 1 Ring sang 2-D Mesh Ring được gắn vào trong đồ thị Mesh 2-D. Giả sử hai đồ thị có cùng số đỉnh. Khi đó, việc nhúng với dilation =1 sẽ tồn tại nếu mesh có số chẵn các hàng. Nếu mesh có số lẻ hàng, cột thì không có cách nào để nhúng Ring vào trong Mesh mà không tăng dilation. Hình 3. 11 Nhúng Ring vào trong Mesh 2-D 3. 2. 2 Mesh 2-D sang Mesh 2-D Một Mesh 2-D của đồ thị giải thuật có thể chuyển sang Mesh 2-D của đồ thị trên kiến trúc đích với dilation= 1 nếu (1) A M và A M hoặc (2) A M và A M. với A, A là số hàng, cột của đồ thị giải thuật, M, Mlà số hàng cột của đồ thị Mesh 2-D. Hình 2. 12 Mô tả chuyển Mesh 2-D sang Mesh 2-D với dialtion-1 3. 2. 3 Cây nhị phân hoàn chỉnh sang 2D Mesh Cây nhị phân hoàn chỉnh trong đồ thị giải thuật có chiều cao n có dilation = khi chuyển vào kiến trúc đích 2D Mesh. Hình 2. 13 Chuyển cây nhị phân chiều cao 3 vào Mesh 2-D với dilation=1 3. 2. 4 Cây nhị thức sang Mesh2-D Cây nhị thức (Binimial Tree) trong đồ thị giải thuật có chiều cao n, có dilation = khi chuyển vào đồ thị Mesh 2-D trong kiến trúc đích. Hình 2. 14 Chuyển cây nhị thức chiều cao 4 vào Mesh 2-D với dilation=1 3. 2. 5 Nhúng đồ thị vào trong mạng Hypercube Một đồ thị G là có tính hình khối nếu ta có thể nhúng G vào trong mạng hypercube với dilation=1. Bài toán xác định một đồ thị bất kỳ G có tính hình khối hay không có độ phức tạp NP-complete. Tuy nhiên, bài toán nhúng của một đồ thị kết nối G vào trong một mạng hypercube với n nút tồn tại khi và chỉ khi có thể gán nhãn các cạnh của G theo các số nguyên {1, . . . . , n} như sau: Các cạnh gắn liền với một đỉnh chung có các nhãn khác nhau Trong mỗi đường của G, ít nhất phải có một nhãn xuất hiện số lẻ lần 4 2 1 4 (a) 2 1 1 2 1 3 (b) (c) Trong mỗi chu trình của G không có nhãn được gán lẻ lần. Hình 2. 15 Mô tả các trường hợp không thể nhúng G vào hypercube với dilation=1 3. 2. 6 Cây nhị thức sang Hypercube Cây nhị thức chiều cao n có thể được chuyển vào đồ thị hypercube có n chiều với dilation =1. Hình 2. 16 Đánh số các cạnh của cây nhị thức chiều cao 4, có thể chuyển vào Hypercube có 4 chiều với dilation-1 3. 2. 7 Rings và Meshes sang Hypercube Giả sử hypercube có p = 2 bộ xử lý. Giả sử G(i) là số hiệu bộ xử lý gán cho vị trí vòng thứ i, với 0 i < p. Việc mã hoá G(i) phải có các tiêu chuẩn sau: Các giá trị phải duy nhất, có nghĩa là G(i) = G(j) i = j G(i) và G(i+1) phải khác nhau chỉ 1 bít, với tất cả i: 0 i < p-1 G(p-1) và G(0) phải khác nhau chỉ 1 bít Các tiêu chuẩn này thiết lập lên định nghĩa của mã Gray ( gray code). Có nhiều các xây dựng mã Gray, ở đây ta trình bày xây dựng mã Gray dài hơn từ mã Gray ngắn hơn. Một mã bít Gray là { 0, 1}, tức là G(0) = 0 và G(1) = 1. Giả sử ta có mã Gray d bít, mã Gray (d+1) bít có thể được xây dựng bởi liệt kê mã Gray d bit với tiền tố là 0, tiếp theo tiền tố là 1. Sử dụng kỹ thuật này chúng ta xây dựng mã Gray 2 bít như sau. 01 11 10 Từ mã Gray 2 bít ta xây dựng mã Gray 3 bít như sau: 000 001 011 010 110 111 101 100 Mã Gray ngược được định nghĩa như sau ; G(i) = j khi và chỉ khi G(j) =i Chúng ta sử dụng cả mã Gray và mã Gray ngược để chuyển đồ thị Ring và Mesh vào trong hypercube Ví dụ như, hàm dưới đây định nghĩa bộ xử lý kết tiếp của bộ xử lý i trên đồ thị ring có 2 nút. là : Successor (i) = 0 nếu i = 2 Successor (i) = G(G(i) + 1) trong trường hợp còn lại. Các hàm viết theo ngôn ngữ C tính toán G(i) và G(i) như sau: /* i là vị trí vòng, hàm Gray sẽ đưa ra số hiệu bộ xử lý chiếm giữ vị trí này */ int gray(i) { return ( i ^( i/2)); } / * Truyền vào số hiệu bộ xử lý i, hàm gray-inverse sẽ tính vị trí của bộ xử lý này trong dãy mã Gray*/ int gray-inverse(i) { int answer, mask; answer = i; mask = answer /2; while ( mask > 0) { answer = answer ^ mask ; mask = mask /2; } return ( answer); } Hình 2. 17 Nhúng đồ thị Ring 8 nút vào mạng hypercube có 8 bộ xử lý Bây giờ ta ánh xạ đồ thị mesh nhiều chiều có các kết nối vòng lại vào trong hypercube. Sử dụng mã Gray, với điều kiện kích thước trong mỗi chiều phải là luỹ thừa của 2. Mỗi chiều của đồ thị mesh sẽ được gán một số lượng bit chính xác trong chuỗi mã hoá. Duyệt các nút đồ thị mesh dọc theo chiều này sẽ được một vòng tròn. Mã Gray xác định các giá trị gán cho trường bit. Ví dụ, xem xét ánh xạ đồ thị mesh 4 8 trong đồ thị hypercube 32 bít. Hai bít được dành để mã hoá hàng và 3 bít để mã hoá cột. Mã gray cho ánh xạ đồ thị mesh kích thước 4 8 vào trong đồ thị hypercube 32 nút như sau: 00000 00001 00011 00010 00110 00111 00101 00100 01000 01001 01011 01010 01110 01111 01101 01100 11000 11001 11011 11010 11110 11111 11101 11100 10000 10001 10011 10010 10110 10111 10101 10100 Hình 2. 18 Nhúng đồ thị Mesh 44 vào mạng hypercube 4 chiều với dilation =1 bởi vì mesh là đồ thị con của hypercube. Bất kỳ đồ thị mesh với n đỉnh có thể được chuyển vào trong đồ thị hypercube có chiều với dilation=2. Chương này đã tìm hiểu về kiến trúc các mạng kết nối và đánh giá ảnh hưởng của mạng đến độ trễ và băng thông trong chi phí thời gian truyền thông, cũng như việc ánh xạ tĩnh từ đồ thị tác vụ vào trong kiến trúc mạng kết nối. Những vấn đề này sẽ ảnh hưởng đến chi phí truyền thông trong các tiêu chuẩn đánh giá giải thuật. Chương 4 cơ sở đánh giá giải thuật song song Quá trình thiết kế tạo ra nhiều giải thuật song song cho bài toán, việc chọn ra một giải thuật tối ưu cần phải dựa vào một số tiêu chuẩn đánh giá. Các tiêu chuẩn đó là : Thời gian thực hiện, khả năng tăng tốc, hiệu quả và tính qui mô của giải thuật. 4. 1 Thời gian thực hiện Khi tốc độ tính toán được coi là nguyên nhân chủ yếu của sự quan tâm trong việc xây dựng các máy tính song song, một độ đo quan trọng trong việc đánh giá là thời gian thực hiện. Nó được xác định như là thời gian giải thuật yêu cầu để giải quyết một vấn đề trên máy tính song song, đó là khoảng thời gian kể từ thời điểm ban đầu đến thời điểm kết thúc. Nếu các bộ xử lý khác nhau, tất cả không bắt đầu và kết thúc đồng thời, khi đó thời gian thực hiện bằng thời gian kéo dài giữa thời điểm bộ xử lý đầu tiên bắt đầu tính toán đến thời điểm bộ xử lý cuối cùng kết thúc tính toán. Trước khi thực sự cài đặt một giải thuật song song hay tuần tự đều có sự phân tích về lý thuyết, giải thuật cần bao nhiêu thời gian để giải quyết vấn đề tính toán đã cho. Điều này thường được thực hiện bằng cách tính số các thao tác cơ bản hoặc các bước mà giải thuật thực hiện trong trường hợp xấu nhất. Số các bước như thế là một hàm của kích thước đầu vào ( input size ). Các thao tác cơ bản có thể là phép cộng, so sánh hoặc đổi chỗ, truyền dữ liệu. Mỗi thao tác như vậy yêu cầu một số cố định các đơn vị thời gian trên máy tính đơn bộ xử lý truyền thống. Khác với giải thuật tuần tự, thời gian thực hiện của giải thuật song song là hàm phụ thuộc vào nhiều tham số như kích thước bài toán N, số bộ xử lý, số tác vụ U và các đặc điểm về giải thuật và phần cứng khác. Nếu gọi T là thời gian thực hiện song song thì T= f( N, U, P, . . . ) Trong suốt thời gian thực hiện, mỗi bộ xử lý sẽ đang tính toán, truyền thông hoặc rảnh rỗi. T = ( T + T + T) /p. Trong đó : T là tổng thời gian tính toán T là tổng thời gian truyền thông T là tổng thời gian rỗi. P là số bộ xử lý Hình 3. 1 Mô tả quá trình tính toán của 8 bộ xử lý 4. 1. 1 Thời gian tính toán Thời gian tính toán của giải thuật song song là thời gian dành để thực hiện tính toán. Đối với giải thuật tuần tự thì thời gian này chỉ phụ thuộc vào kích thước của bài toán nhưng với tính toán song song thì việc tính toán lặp trên các tác vụ có thể có. Do đó thời gian tính toán sẽ phụ thuộc vào số tác vụ thực hiện. Đối với mô hình bộ nhớ chung thì số lượng bộ xử lý cũng ảnh hưởng đến tốc độ thực thi trên mỗi bộ xử lý. Thông thường ta có thể xác định bằng thời gian thực hiện tuần tự cộng với bất kỳ thời gian nào thêm vào do thực hiện song song. Chẳng hạn như thời gian tính toán lặp lại cùng một công việc trên các tác vụ. 4. 1. 2 Thời gian truyền thông Thời gian truyền thông của một giải thuật là thời gian các tác vụ dành để gửi và nhận message. Có hai loại truyền thông cần xác định : truyền thông giữa hai tác vụ trên hai bộ xử lý khác nhau và truyền thông giữa hai tác vụ cùng nằm trên cùng bộ xử lý. Thông thường thời gian truyền bên trong bộ xử lý lớn hơn nhiều so với thời gian truyền giữa hai bộ xử lý, nhất là đối với mô hình máy tính song song multicomputers. Trong mô hình multicomputers lý tưởng thì chi phí để gửi một message giữa hai tác vụ định vị trên bộ xử lý khác nhau phụ thuộc vào hai tham số sau : Thời gian khởi tạo message: t là thời gian cần thiết để khởi tạo truyền thông Thời gian truyền dữ liệu: t là thời gian cần thiết để truyền đi dữ liệu có kích thước một word ( 2 byte). t được xác định bởi băng thông vật lý của kênh truyền thông kết nối bộ xử lý nguồn và đích. Công thức tính thời gian gửi message có kích thước L (đơn vị là word) là: T = t + L tw Nếu lượng dữ liệu truyền là nhỏ thì thời gian khởi tạo chiếm phần lớn, còn khi lượng dữ liệu lớn thì thời gian truyền sẽ chiếm tỷ trọng cao. Hình 3. 2 Mô tả mối quan hệ các tham số trong công thức tính thời gian truyền thông Thông thường ts và tw là các thông số được tính toán phụ thuộc vào cụ thể kiến trúc máy tính song song. Hình 3. 3 Bảng xấp xỉ thông số một số máy tính song song ( đơn vị : ms) Tuy nhiên đối với mô hình multicomputer thực tế, ta cần phân tích sự ảnh hưởng của hai kỹ thuật định đường truyền thông là store and forward và circuit-switched cũng như ảnh hưởng của tranh chấp băng thông trên đường truyền giữa các bộ xử lý. Trong sơ đồ của cơ chế store and forward, thời gian cần thiết để gửi một message từ một bộ xử lý tới một bộ xử lý khác tăng tuyến tính với số bước nhảy ( hops) mà message phải tạo ra để đến được đích. Ngược lại, thời gian cần thiết để gửi một message từ một bộ xử lý tới một bộ xử lý khác trong lược đồ chuyển mạch là phụ thuộc rất ít với khoảng cách giữa các bộ xử lý. Do đó ta có thể phát triển thành các công thức sau : Đối với truyền thông định đường theo cơ chế store and forward: Tmsg = ( ts + tw L) D Với D là khoảng cách giữa nút nhận và gửi trong bước định đường. Đối với truyền thông định đường theo cơ chế circuit-switched: Tmsg = ts + tw L – th D Với D là khoảng cách giữa nút nhận và gửi trong bước định đường Th là chi phí gia tăng cho mỗi bước định đường. Trong thực tế, th thường rất nhỏ, ta có thể bỏ qua được. Khi xem xét đến sự tranh chấp băng thông truyền trên mạng kết nối thì công thức tính được thay đổi như sau: Tmsg = ts + tw S L Trong đó S là số bộ xử lý gửi đồng thời trên cùng một đường dây. 4. 1. 3 Thời gian rỗi (Idle) Thời gian tính toán và truyền thông thường đơn giản hơn trong việc xác định bởi vì ta có thể xác định sự phân bố của nó đối với thời gian thực hiện. Thời rảnh rỗi khó có thể xác định bởi vì phụ thuộc vào trình tự các phép được thực hiện. Một bộ xử lý có thể đặt trong trạng thái rỗi nếu thiếu tính toán hoặc dữ liệu để tính toán. Trong trường hợp đầu tiên, thời gian rảnh rỗi có thể tránh được bằng cách sử dụng kỹ thuật căn bằng nạp động. Trong trường hợp thứ hai, bộ xử lý rỗi trong khi tính toán đang chờ dữ liêu dữ liệu từ xa mà dữ liệu này lại đang trong trạng thái sử dụng. Thời này có thể được tránh nếu ta cấu trúc chương trình để có thể thực tính toán hoặc truyền thông trong khí đang chờ dữ liệu từ xa. Kỹ thuật này thường được gọi là xen kẽ tính toán và truyền thông ( overlapping computation and communication) bởi vì tính toán với dữ liệu cục bộ được thực hiện đồng thời với tính toán và truyền thông dữ liệu xa. Cách đơn giản để đạt được điều này là tạo ra nhiều tác vụ trên một bộ xử lý. Trong khi một tác vụ đang bị dùng để chờ dữ liệu ở xa thì tính toán có thể chuyển sang tác vụ khác mà dữ liệu đã sẵn có. Hình 3. 4 Mô tả kỹ thuật xen kẽ tính toán và truyền thông giữa P1 và P2. Hầu hết các máy tính song song đều hỗ trợ thực hiện kỹ thuật lập lịch trình, xen kẽ tính toán và truyền thông do đó thời gian rỗi chiếm tỷ trọng rất nhỏ trong toàn bộ thời gian tính toán, nên thông thường có thể bỏ qua được. 4. 2 Tăng tốc và hiệu quả. Thời gian thực hiện không luôn là thước đo thuận tiên nhất để đánh giá hiệu năng của giải thuật. Khi thời gian thực hiện có xu hướng biến đổi theo kích thước bài toán, thời gian thực hiện phải được tiêu chuẩn hoá khi so sánh hiệu năng giải thuật với kích thước bài toán khác nhau. Hiệu quả của giải thuât được định nghĩa là phần thời gian mà các bộ xử lý dùng để thực hiện công việc có ích, chỉ ra mức độ hiệu quả của một giải thuật khi sử dụng các tài nguyên tính toán của một máy tính song song theo hướng độc lập với kích thước bài toán, được xác định theo công thức sau: Ep = Với T1 là thời gian thực hiện giải thuật tuần tự. Tp là thời gian thực hiện giải thuật song song Ep là hiệu quả giải thuật p là số bộ xử lý Thông thường, Ep 1. Một độ đo khác đánh giá được hiệu năng của giải thuật là khả năng tăng tốc, đây là hệ số mà thời gian thực hiện được giảm đi khi thực hiện bài toán trên p bộ xử lý. Được xác định theo công thức sau: Sp = Với Sp là khả năng tăng tốc T1 là thời gian thực hiện giải thuật tuần tự. Tp là thời gian thực hiện giải thuật song song Hầu hết các trường hợp thì Sp p. Rõ ràng khả năng tăng tốc càng lớn thì giải thuật song song càng tốt. Tuy nhiên năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc như sau: Luật Amdahl : Giả sử s là phần thao tác tính toán cần phải thực hiện tuần tự, trong đó 0 s 1. Khả năng tăng tốc tối đa Sp đạt được bởi một máy tính song song có P bộ xử lý thực hiện tính toán là : Sp Luật trên đã sớm đem lại sự bi quan về một tiềm năng của tính toán song song. Tuy nhiên nếu ta mở rộng vấn đề ra có thể thấy luật Amdahl thích hợp chỉ đối với bài toán cố định hoặc phần trăm tuần tự là độc lập với kích thước bài toán. Điều này thường ít gặp trong thực tế vì các bài toán giải quyết song song thường lớn, khi đó phần tính toán tuần tự sẽ giảm xuống khi kích thước tăng. 4. 3 Tính qui mô Một giải thuật có tính qui mô nếu mức độ song song ít nhất cũng gia tăng tuyến tính theo kích thước bài toán. Một kiến trúc có tính qui mô nếu nó tiếp tục mang lại cùng hiệu năng cho từng bộ xử lý, mặc dù các bộ xử lý được dùng trong bài toán kích thước lớn hơn, khi số lượng bộ xử lý gia tăng. Tính qui mô về thuật toán và kiến trúc là quan trọng, bởi vì từ đó mới có thể cho phép người sử dụng giải quyết các bài toán lớn hơn trong số lượng thời gian như nhau bằng cách mua một máy tính song song với nhiều bộ xử lý hơn. Việc đánh giá tính qui mô của giải thuật thường thông qua một tiêu chuẩn phụ thuộc vào tính hiệu quả. Nếu như giải thuật có thể duy trì hiệu quả là một hằng số hoặc ít nhất là giới hạn dưới > 0 khi số bộ xử lý gia tăng do kích thước bài toán tăng lên. Theo công thức tính hiệu quả: Ep = Để duy trì Ep là hằng số khi T1 cần phải tỷ lệ với pTp. Các giải thuật song song theo dữ liệu thì linh động hơn các giải thuật song song theo chức năng, bởi vì mức độ song song chức năng thường là một hằng số, độc lập với kích thước bài toán, trong khi mức độ song song dữ liệu là một hàm tăng theo kích thước bài toán. Việc tìm hiểu các cơ sở đánh giá giải thuật giúp cho ta có thể xem xét lại các thiết kế đưa ra. Chọn lựa giải thuật tốt cho mô hình máy tính cụ thể là một bài toán không đơn giản. Những đánh giá trên mới chỉ mang tính lý thuyết, nhưng là cơ sở quan trọng khi ta thiết kế giải thuật song song. Chương 5 giải hệ phương trình tuyến tính Sau khi trình bày lý thuyết về thiết kế giải thuật song song, chương sau đây sẽ áp dụng cụ thể vào bài toán giải hệ phương trình tuyến tính. Đây là bài toán quan trọng, thường được áp dụng trong nhiều bài toán khoa học và kỹ thuật. Về lý thuyết, giải hệ phương trình tuyến tính A x= b ta có thể thực hiện như sau: Tìm ma trận nghịch đảo A của A Sau đó tính x= Ab. Tuy nhiên, trong thực tế việc tính ma trận nghịch đảo trực tiếp sẽ rất phức tạp và hơn nữa không phải ma trận nào cũng có ma trận nghịch đảo. Dựa vào các phép biến đổi hệ phương trình như hoán vị, nhân hàng với một hằng số. v. v. để hệ trở lên dễ giải hơn. Điển hình là dùng phép toán với hàng để đưa ma trận hệ số về ma trận tam giác, khử Gauss là dựa theo phương pháp này. Trong luận văn này đề cập đến một phương pháp giải hệ tuyến tính dựa vào phương pháp khử Gauss đó là tách LU. Sau khi đã đưa hệ phương trình về ma trận tam giác sẽ dùng các giải thuật thay thế tiến ( forward substitution) và giải thuật quay lui ( backward substitution) để tính toán ra được kết quả. Giải hệ phương trình tuyến tính sau: ax + ax+ ax+. . . . + ax= b ax + ax+ ax+. . . + ax= b2 a31x1 + a32x + a33 x+. . . . + a 3n x= b3 . . . . . . . . . . . . . . a n1x + a n2x+ a n3x+. . . . + a nnx= bn Ta có thể viết dưới dạng A x = b Trong đó A là ma trận hệ số, b là cột vế phải, x là cột ẩn số của hệ phương trình. Các bước tiến hành giải thuật tách LU như sau: 1) Phân tách A = L * U dựa theo giải thuật khử Gauss. 2) Giải hệ L * y= b => tìm ra vectơ y theo thuật toán thay thế tiến 3) Giải hệ U *x = y => tìm ra nghiệm của bài toán gốc x theo thuật toán thay thế quay lui. Như vậy, để giải hệ phương trình tuyến tính, ta cần giải quyết hai bài toán : tách A= L*U theo giải thuật khử Gauss và giải hệ phương trình tuyến tính có hệ số là ma trận tam giác. 5. 1 Tách A = L*U dựa theo giải thuật khử Guassian Giải thuật khử Gauss dựa trên các phép đổi sơ cấp đối với hàng của ma trận hệ số không làm thay đổi hệ như sau: Nhân các phần tử của hàng j với một số khác không Đổi chỗ hai hàng i và j cho nhau. Cộng vào hàng i các phần tử tương ứng với hàng j. Trong giải thuật khử Gauss, đối với mỗi cột i khử các phần tử dưới đường chéo chính bằng cách cộng với bội số của hàng i với các hàng phía dưới. Giải thuật khử tuần tự như sau: For k = 1 to n-1 For j= k + 1 to n For i = k+1 to n a = a– (a/ a)*a Công việc tính toán trong một bước được minh hoạ như hình vẽ dưới đây: (k, k) (k, i) (j, k) cột k cột i hàng k hàng j i (i, j) Khử Cập nhật Hình 5. 1 Mô tả tính toán trong giải thuật khử Guass Giải thuật tách ma trận A = L * U dựa theo giải thuật khử Gauss ta sẽ được L là ma trận tam giác dưới với các phần tử nằm trên đường chéo chính =1 và U là ma trận tam giác trên. Sau khi kết thúc thủ tục tách, thì L được lưu trữ trong phần dưới đường chéo chính và U được lưu trữ trong phần trên của A. Giải thuật tách tuần tự được trình bày như sau: For k = 1 to n-1 For i= k + 1 to n l = a/a end for j = k +1 to n For i = k +1 to n a = a - l. a end end end Trong giải thuật tuần tự, công việc tính toán l được được ra ngoài vòng lặp trong để giảm chi phí tính toán trong mỗi bước lặp. A = L U Thông thường, giải thuật khử Gauss có sự hoán đổi giữa các hàng để tìm ra phần tử xoay có giá trị tuyệt đối lớn nhất. Tuy nhiên, để đơn giản hoá bài toán, tạm thời bỏ qua vấn đề tìm phần tử xoay có giá trị lớn nhất. Xem xét độ phức tạp của giải thuật. Giải thuật khử Gauss tuần tự yêu cầu khoảng n/3 cặp phép toán cộng nhân, bởi vậy thời gian yêu cầu thực hiện là T= t n/3 với t là thời gian yêu cầu thực hiện phép cộng -nhân. Quá trình thiết kế giải thuật song song được trình bày như sau: a. Phân rã Đối với 2 vòng for i, j = 1, …. , n sẽ hình thành lên ma trận có n phần tử Một cách tự nhiên, ta phân rã ma trận thành n tác vụ, mỗi tác vụ tại vị trí (i, j) sẽ lưu trữ hệ số a, tính toán và lưu trữ các phần tử sau: u nếu i j l nếu i > j Các phần tử 0 dưới đường chéo chính trong ma trận U, phần tử =0 phía trên đường chéo chính và các phần tử =1 trên đường chéo chính không cần phải tính toán và lưu trữ, ta mặc định trong kết quả. b. Truyền thông Các bước tính toán có sự phụ thuộc dữ liệu lẫn nhau nên truyền thông là cần thiết giữa các tác vụ. Truyền thông giữa các tác vụ được mô tả như hình dưới đây. Hình 5. 2 Mô tả truyền thông giữa các tác vụ Khi đó ta có chương trình mô phỏng cho từng tác vụ như sau: Program for task(i, j) For k= 1 to min (i, j) –1 Recv a Recv l a= a- l* a end if i j then broadcast a to task(k, j), k = i +1, …. , n else recv a l= a/ a broadcast l to tasks(i, j), k = j+1, …, n end c. Tích tụ Với mảng hai chiều n n các tác vụ, các chiến lược kết hợp tác vụ như sau: 1-D: kết hợp n/p hàng hoặc cột 2-D: kết hợp các tác vụ thành mảng con 2 chiều (n/) (n/) với các chiến lược này, công đoạn tích tụ đều tạo ra p tác vụ lớn hơn. d. ánh xạ Mỗi tác vụ tạo ra từ công đoạn kết hợp sẽ được ấn định vào một trong p bộ xử lý. Với mỗi chiến lược tích tụ, ta có một giải thuật song song song tương ứng. 5. 1. 1 Giải thuật song song theo hàng Trong công đoạn tích tụ các tác vụ, giải thuật hướng theo hàng sẽ thực hiện việc kết hợp n/p hàng các tác vụ ban đầu thành một tác vụ lớn. Khi đó không cần thiết broadcast l theo chiều ngang bởi vì các tác vụ này được thực thi chỉ trong một tác vụ. Tuy nhiên, chiến lược tích tụ này không song song được việc cập nhật các phần tử nằm cùng trong một hàng. Vẫn yêu cầu broadcast theo chiều dọc để truyền dữ liệu trong mỗi hàng ở trên tới các tác vụ ở dưới để cập nhật dữ liệu. Hình 5. 3 Mô tả truyền thông giữa các tác vụ tích tụ theo hàng Giải thuật theo hàng 1-D như sau: For k=1 to n-1 If k myrows then Broadcast { a: k < j < n } to other tasks Else Recv{ a: k jn } End For i myrows, i > k, l = a/a. end for j = k+1 to n for i myrows, i > k, a= a- l*a end end end Thời gian thực hiện Tính toán độ phức tạp tính toán của thuật toán. -Tại bước thứ k, việc cập nhật các tác vụ yêu cầu khoảng (n-k)/p phép toán. - Độ phức tạp cho toàn bộ n-1 bước sẽ là : T t n/(3p). Tính toán độ phức tạp về truyền thông. Tương tự như tính toán độ phức tạp, số lượng dữ liệu broadcast tại bước thứ k là khoảng n-k, bởi vậy trên mô hình 1-D Mesh, các bộ xử lý nối nhau thành đường thẳng và truyền thông với nhau bằng kỹ thuật circuit-switched với ảnh hưởng của khoảng cách giữa các bộ xử lý t h nhỏ có thể bỏ qua. Ta có chi phí cho truyền thông sẽ là T (p-1) tn + (p-1)t n/2 Tổng thời gian thực hiện là : T t n /(3p) + t(p-1)n + t(p-1) n/2 Các vấn đề đặt ra cho việc thực thi giải thuật song song theo hàng là: Phân tán công việc không đều, mỗi tác vụ sẽ đi vào trạng thái rỗi ngay khi hàng cuối cùng được hoàn thành. Nếu tác vụ quản lý khối các hàng liên tiếp thì bộ xử lý được ấn định tương ứng sẽ rỗi thời gian rất lâu trước khi toàn bộ tính toán được hoàn thành. Hơn nữa, công việc cập nhật các hàng sẽ ít đi nhanh chóng khi số hiệu hàng gia tăng. Các phương pháp giải quyết cho vấn đề này là: ấn định các hàng tới các tác vụ theo chu trình, với hàng thứ i được ấn định tới task thứ i mod n hoặc ấn định theo kiểu chu trình khối (block-cyclic) hoặc Pipeline việc tính toán và truyền dữ liệu, với phương pháp này sẽ cải thiện được hiệu năng của giải thuật song song. Thay vì làm việc trên cùng một bước lặp tại một thời điểm, tất cả các bộ xử lý có thể được lập lịch trình thực hiện một cách không đồng bộ. Trong khi pipeline giải thuật khử Gauss thì mỗi bộ xử lý sẽ thực hiện độc lập bất kỳ hoạt động gửi hoặc tính toán trừ phi nó đang chờ nhận dữ liệu dùng cho hoạt động đó. + Tại bước k, mỗi tác vụ hoàn thành cập nhật phần còn lại của nó trước khi chuyển tới bước tiếp theo k+1. Tuy nhiên tác vụ quản lý hàng k+1 có thể broadcast ngay sau khi nó được cập nhật trước khi nó tiếp tục việc cập nhật phần còn lại của bước thứ k. + Với chiến lược gửi trước “ send ahead” sẽ cho phép các tác vụ khác bắt đầu tiến hành công việc trên tác vụ tiếp theo sớm hơn bởi vì thời gian chờ đợi dữ liệu cần thiết cho việc tính toán đã được rút gọn. 5. 1. 2 Giải thuật song song theo cột Việc tích tụ theo cột cũng tương tự như giải thuật theo hàng, với n/p cột các tác vụ cơ sở tạo thành một tác vụ lớn. Khi thực thi giải thuật sẽ không phải broadcast các hàng theo chiều dọc nhưng ngược lại phải broadcast theo chiều ngang cho các task vụ nằm bên phải. Không song song được việc tính toán hệ số nhân của các hàng dùng vào việc khử các phần tử dưới đường chéo chính cũng như song song việc cập nhật các phần tử bất kỳ cột nào đưa ra. Hình 5. 4 Mô phỏng truyền thông giữa các tác vụ tích tụ theo côt Giải thuật LU theo cột được mô phỏng như sau: For k=1 to n-1 If k mycols then For i=k+1 to n l= a/a end broadcast { l: k < i n } to other tasks Else Recv{ l: k jn } End For i mycols, j > k, For i= k +1 to n a= a- l*a end end end Tính toán độ phức tạp giải thuật, các vấn đề cũng như phương pháp giải quyết cũng tương tự như giải thuật song song tích tụ theo hàng. 5. 1. 3 Giải thuật song song hai chiều Tiếp theo chúng ta sẽ xem xét giải thuật tách A=L*U hai chiều, khi đó mảng (n/) (n/) các tác vụ cơ sở sẽ được kết hợp lại tạo thành tác vụ lớn. Việc tích tụ này sẽ kết hợp đặc điểm của giải thuật theo cột và giải thuật theo hàng. Như broadcast theo chiều ngang và chiều dọc được yêu cầu để truyền thông các đoạn ma trận theo hàng và các hệ số nhân theo cột Hình 5. 5 Mô phỏng truyền thông giữa các tác vụ tích tụ kết hợp Giải thuật song song kết hợp được mô phỏng như sau: For k=1 to n-1 If k myrows then Broadcast { a: j mycols, j > k} to other tasks in my task column Else Recv{ a: j mycols, j > k} End If k mycols then For i myrows, i < k l = a/a. end broadcast { l: i myrows, i > k} to other tasks in my task row end else recv { l: i myrows, i > k} end for j mycols, j > k for i myrows, i > k, a= a - l a end end end Tính toán thời gian thực hiện của thuật toán. Tại bước thứ k, việc cập nhật bởi mỗi tác vụ yêu cầu khoảng (n-k)/p phép toán. Do đó tổng số trên n-1 bước sẽ là : T t tn/(3p) Số lượng dữ liệu broadcast tại bước k dọc theo mỗi hàng mỗi cột của mỗi tác vụ khoảng (n-k)/, bởi vậy trên mô hình 2-D mesh Ta có T 2 tn + tn/ Tổng thời gian thực hiện là: T tn/(3p) + 2 tn + t n/ Cũng tương tự như giải thuật tích tụ theo hàng hoặc cột, giải thuật kết hợp có các vấn đề như: Mỗi tác vụ sẽ trở nên rỗi ngay sau khi các hàng và cột của nó hoàn thành. Số lượng công việc tính toán ít đi khi số hiệu hàng và cột tăng lên. Để cải thiện vấn đề cân bằng nạp và tính đồng thời người ta có thể ấn định hàng cột vào tác vụ theo chu trình, với hệ số của ma trận A là a ấn định vào tác vụ (i mod , j mod ). Ngoài ra có thể ấn định theo khối- chu trình (block-cyclic). Hiệu năng có thể năng cao bằng cách pipeline tính toán và truyền dữ liệu. Tại bước thứ k, mỗi tác vụ sẽ hoàn thành việc cập nhật ma trận con còn lại trước khi chuyển đến bước thứ k+1. Công việc broadcast mỗi đoạn của hàng k+1, tính toán và broadcast mỗi đoạn hệ số nhân cho bước thứ k+1 có thể được khởi tạo ngay sau khi các đoạn liên quan đến hàng k+1 và cột k+1 được cập nhật bởi tác vụ quản lý nó, trước khi hoàn thành việc cập nhật còn lại cho bước thứ k Với chiến lược gửi trước “send ahead” sẽ cho phép các tác vụ khác tiến hành công việc trên bước tiếp theo sớm hơn. 5. 1. 4 Khử Gauss với kỹ thuật lựa chọn phần tử xoay Do các hàng của hệ phương trình tuyến tính không ràng buộc thứ tự, cho nên ta có thể hoán đổi các hàng cho nhau mà không ảnh hưởng đến hệ. Việc chọn phần tử xoay a sao cho giá trị tuyệt đối lớn nhất nhằm tránh khả năng chia cho phần tử rất nhỏ và nhằm đảm bảo chắc chắn rằng số nhân không vượt quá 1 về độ lớn, làm giảm đi sự khuyếch đại lỗi do làm tròn. Với partial pivoting dẫn đến sự tách L*U theo hình thức sau: PA = LU Với P là ma trận chuyển vị của A Nếu PA=LU thì hệ Ax=b sẽ trở thành PAx = LU x= Pb Từ đó ta có giải hệ tam giác dưới Ly= Pb theo giải thuật rút gọn tiến, tiếp theo sẽ giải hệ tam giác trên với giải thuật rút gọn quay lui U x= y. Với kỹ thuật partial pivoting sẽ làm phức tạp việc thực thi song song giải thuật khử Gauss và ảnh hưởng thực sự đến hiệu năng. Đối với giải thuật tích tụ theo cột thì việc tìm kiếm theo phần tử xoay là không yêu cầu truyền thông giữa các tác vụ nhưng tính toán hoàn toàn tuần tự. Mỗi khi phần tử xoay được tìm thấy thì chỉ số của hàng xoay phải được truyền thông tới các tác vụ khác, và các hàng phải được hoán chuyển một các hoàn toàn hay hình thức trong mỗi tác vụ. Với giải thuật tích tụ theo hàng, tìm kiếm phần tử trục xoay sẽ được song song nhưng yêu cầu truyền thông giữa các tác vụ và ngăn cản pipeline giữa các bước tính toán liên tiếp. Nếu hoán chuyển hàng hoàn toàn thì chỉ có hai tác vụ liên quan đến, còn nếu hoán chuyển hình thức( chỉ số hàng được thay đổi ) thì việc ánh xạ các hàng tới các tác vụ sẽ đựợc thay đổi, điều này có thể làm giảm đi tính đồng thời và cân bằng nạp của giải thuật. Với giải thuật kết hợp hàng và cột, tìm kiếm trục xoay được song song nhưng yêu cầu truyền thông giữa các tác vụ dọc trên cột và ngăn cản pipeline giữa các bước tính toán liên tiếp. Do kỹ thuật partial pivoting tác động làm giảm hiệu năng nên có một vài lựa chọn được đưa ra nhằm hạn chế vấn đề tìm kiếm : Tìm kiếm phần tử xoay chỉ nằm trong khối các hàng Tìm kiếm có mức ngưỡng 5. 2 Giải hệ phương trình với ma trận hệ số tam giác Sau khi thực hiện phân rã A= L*U, ta sẽ thu được: L là ma trận tam giác dưới ( lower triangular ) bởi vì tất cả các phần tử phía trên đường chéo chính đều = 0, l= 0 với i < j. U là ma trận tam giác trên ( upper triangular) bởi vì tất cả các phần tử phía dưới đường chéo chính đều = 0, u= 0 với i> j. Đối với các giải thuật trực tiếp giải hệ phương trình tuyến tính thì việc đưa ma trận hệ số về ma trận tam giác là điều quan trọng bởi vì hệ tuyến tính ma trận hệ số tam giác thường dễ giải bằng các bước khử liên tiếp. Giải thuật tuần tự giải L* y = b. Đối với hệ phương trình tam giác thấp, y có thể tìm được bằng giải thuật rút gọn tiến. Giải thuật được trình bày như sau: x=(b- , i=1, …, n for j=1 to n x= b/l for i = j+1 to n b= b- lx end end Giải thuật tuần tự giải U * x = y Đối với hệ phương trình tam giác trên, x có thể tìm được bằng giải thuật rút gọn quay lui. Giải thuật được trình bày như sau: x=(b- , i=1, …, n for j=1 to n x= b/u for i = 1 to j-1 b= b- ux end end Phân tích độ phức tạp của giải thuật tuần tự. Giải thuật rút gọn tiến và rút gọn quay lui yêu cầu khoảng n/2 phép nhân và số lượng tương tự đối với phép cộng, bởi vậy thời gian tính toán đối với mô hình tuần tự là: T= t n/2 Với t là thời gian tính toán cho cặp phép nhân và cộng. Trong mục này chỉ xem xét xây dựng giải thuật song song đối với hệ phương trình tam giác dưới, hệ phương trình tam giác trên sẽ được giải tương tự. Phân rã Phân rã bài toán thành các tác vụ, mỗi tác vụ tương ứng với một phần tử trong ma trận L cần cập nhật. For i=2, …, n, j= 1, …, i-1 tác vụ (i, j). Mỗi tác vụ sẽ + lưu trữ l + tính toán lx - For i = 1, …, n, tác vụ (i, i). Mỗi tác vụ sẽ + lưu trữ l và b + tính tổng t= + tính toán và lưu trữ x= (b- t)/l Với việc phân chia này dẫn đến mảng 2 chiều tam giác n( n-1)/2 tác vụ. b. Truyền thông Đối với các tác vụ for j=1, …, n-1, mỗi tác vụ task(j, j) sẽ broadcast x tới task(j, j), i=j+1, . . , n. for i=2, . . , n tính tổng các kết quả thu gọn lx từ các tác vụ task(i, j), j=1, …, i-1. tới task(i, i). Truyền thông giữa các tác vụ được mô phỏng theo hình vẽ sau: Hình 5. 6 Mô tả truyền thông giữa các tác vụ Program for task (i, j), ij If i=j then If i> 1 then Recv sum reduction t else t=0 end x=(b-t)/l broadcast x to tasks(k, i), k=i+1, . . , n else recv x t = lx send t for sum reduction across tasks (i, k), k=1, …. , i-1, to task(i, i) end c. Tích tụ Với mảng hai chiều tác vụ, các chiến lược tích tụ tự nhiên là : Kết hợp n/p hàng hoặc cột Kết hợp hàng cột với ma trận con kích thước (n/) (n/) trong cả hai trường hợp đều đem lại p tác vụ d. ánh xạ Mỗi tác vụ sẽ được ấn định vào một trong p bộ xử lý. 5. 2. 1 Giải thuật song song tích tụ theo hàng Khi đó sẽ kết hợp p hàng tác vụ cơ sở tạo ra một tác vụ lớn. Với các tích tụ này sẽ không cần truyền thông để thực hiện rút gọn tổng trên hàng bởi vì bất kỳ hàng nào được đưa ra đều được chứa toàn bộ trong một tác vụ. Không thực hiện song song trong việc tính những tổng này. Tuy nhiên vẫn yêu cầu broadcast theo chiều dọc để truyền thông các thành phần của x. Hình 5. 7 Mô tả truyền thông giữa các tác vụ tích tụ theo hàng Giải thuật song song tích tụ theo hàng được mô phỏng như sau: For j=1 to n If j myrows then x= b/l broadcast x to other tasks else recv x end for i myrows, i > j, b= b- l x end end Các vấn đề đặt ra khi kết hợp theo hàng Mỗi tác vụ sẽ rỗi ngay sau khi thành phần lời giải tương ứng với hàng cuối cùng trong tác vụ đó được tìm ra. Nếu ta kết hợp liên tiếp các hàng vào một tác vụ thì có thể tác vụ sẽ rỗi một thời gian lâu trong khi toàn bộ tính toán hoàn thành Tính toán sẽ nhiều lên khi số hiệu hàng tăng lên Các phương pháp giải quyết Cân bằng nạp và tính đồng thời có thể được cải thiện bằng cách ấn định các hàng vào các tác vụ theo chu trình với hàng i được ấn định vào tác vụ i mod p. Có các cách ánh xạ khác như chu trình-khối (block-cyclic) hay đối đầu ( reflection ). Hình 5. 8 Mô tả truyền thông giữa các tác vụ ánh xạ chu trình Hình 5. 9 Mô tả truyền thông giữa các tác vụ ánh xạ đối đầu Tính toán thời gian thực hiện của giải thuật Nếu các bước liên tiếp được pipeline thì thời gian thực hiện xấp xỉ là T= t(n + 2n(p-1))/(2p) + (t+ t)(n-1) - Nếu không pipeline được các bước tính toán liên tiếp thì số hạng thể hiện chi phí truyền thông được nhân thêm với một hệ số : + p-1 đối với máy tính song song có mạng kết nối bộ xử lý hình 1-D Mesh + 2(-1) đối với máy tính song song có mạng kết nối bộ xử lý hình 2-D Mesh + log(p) đối với máy tính song song có mạng kết nối bộ xử lý hình hypercube Những hệ số này thể hiện chiều dài đường truyền thông thực hiện broadcast. Cải thiện hiệu năng Hiệu năng có thể cải thiện thực sự bằng chiến lược “gửi trước “( send ahead) trong đó tại mỗi bước thứ j tác vụ quản lý hàng j+1 có thể tính toán x và broadcast x trước khi hoàn thành cập nhật đối với x. Hiệu quả đạt được của pipeline bị tác động mạnh bởi cấu trúc mạng và ánh xạ các hàng tới các tác vụ. Ví dụ ánh xạ chu trình trên mạng Ring cho phép hoàn thành hầu hết khả năng pipeline trong khi kiến trúc Hypercube thì thấp hơn nhiều. 5. 2. 2 Giải thuật song song tích tụ theo cột Tiếp theo chúng ta sẽ xem xét việc tích tụ theo 1 chiều hướng cột, với n/p cột các tác vụ cơ sở hình thành nên tác vụ lớn. Khi tích tụ theo cột thì không cần thiết broadcast các thành phần của x theo chiều dọc, bởi vì bất kỳ cột ma trận nào đưa ra đều nằm hoàn toàn trong cùng một tác vụ. Truyền thông theo chiều ngang vẫn được yêu cầu để rút gọn các tổng tính ở vòng lặp bên trong. Tuy nhiên không có thực thi song song trong việc tính toán các tích số có kết quả từ thành phần được đưa ra từ x. Hình 5. 9 Mô tả truyền thông giữa các tác vụ tích tụ theo cột Giải thuật được mô phỏng như sau For j=1 to n t= 0 for j mycols, j < i t = t + lx end if i mycols then recv sum reduction of t x= ( b-t)/l else send t for sum reduction across tasks end end Cũng tương tự giải thuật đối với hàng, các vấn đề đặt ra trong cân bằng nạp và tính đồng thời gồm có: Các tác vụ vẫn còn rỗi tận đến khi phần tử lời giải tương ứng với cột đầu tiên của nó được tính. Nếu mỗi tác vụ quản lý một khối liên tục các cột thì một tác vụ vẫn có thể rỗi trong suốt thời gian hầu hết công việc tính toán. Số lượng công việc tính toán sẽ giảm đi khi số hiệu cột tăng lên. Các phương pháp giải quyết ấn định các cột vào các tác vụ theo chu trình với cột thứ j ấn định vào trong task j mod p Việc ánh xạ khác cũng có thể thực hiện như chu trình khối ( block-cyclic) hay đối đầu (reflection) Hình 5. 10 Mô tả truyền thông giữa các tác vụ tích tụ ánh xạ chu trình Hình 5. 11 Mô tả truyền thông tích tụ ánh xạ đối đầu 5. 2. 3 Giải thuật song song hai chiều Tiếp theo ta xem xét việc tích tụ theo hai chiều với mỗi tác vụ lớn được tạo thành bởi kết hợp mảng con hai chiều ( n/) ( n/) tác vụ ban đầu. Giải thuật này kết hợp đặc điểm của hai giải thuật tích tụ theo cột và theo hàng. Với giải thuật này, broadcast được yêu cầu theo chiều dọc và rút gọn tổng theo chiều ngang được yêu cầu truyền thông giữa các thành phần lời giải và tích luỹ các kết quả vòng lặp bên trong một cách tương ứng. Các vấn đề đối với giải thuật Nếu mỗi tác vụ quản lý một khối liên tiếp hàng và cột thì chúng ta sẽ có một giải thuật khối các tác vụ nhỏ với hiệu quả và tính đồng thời thấp. Hơn nữa với cách tiếp cận này sẽ dẫn đến chỉ có (p + ) /2 là không trống rỗng. Lãng phí gần một nửa các bộ xử lý trong ma trận Mesh 2-D. Để giải quyết vấn đề này thì việc ấn định theo cách chu trình các hàng và cột tới các tác vụ, với phần tử ma trận hệ số l được ấn định vào tác vụ (i mod , j mod ), kết quả là có p tác vụ không trống rỗng, bởi vậy ma trận Mesh 2-D có thể được sử dụng. Hình 5. 12 Mô tả truyền thông tích tụ kết hợp Hình 5. 13 Mô truyền thông giữa các tác vụ ánh xạ chu trình Nhưng ta nhận thấy vòng lặp trên các thành phần lời giải liên tiếp và thực hiện tương ứng với rút gọn tổng theo chiều ngang và broadcast theo chiều dọc, do đó vẫn có hạn chế về tính đồng thời bởi vì thực hiện tính toán cho mỗi thành phần chỉ liên quan đến một hàng tác vụ và một cột tác vụ. Để giải quyết vấn đề này, một giải thuật tốt hơn có thể đạt được bằng cách tính toán các thành phần lời giải trong một nhóm , điều này cho phép tất cả các tác vụ cập nhật kết quả một cách đồng thời. Mỗi bước của giải thuật này gồm có 4 pha như sau: Việc tính toán thành phần lời giải tiếp theo bởi các tác vụ trong ma trận tam giác thấp sử dụng giải thuật song song tích tụ hai chiều. Việc broadcast các thành phần lời giải kết quả theo chiều dọc từ các tác vụ trên đường chéo chính tới các tác vụ trong ma trận tam giác trên Tính toán cập nhật kết quả được thực hiện bởi tất cả các tác vụ. Rút gọn tổng theo chiều ngang sẽ được thực hiện bởi các tác vụ trong ma trận tam giác trên đến các tác vụ trên đường chéo chính. Hình 5. 14 Mô tả các pha trong giải thuật tính toán theo nhóm Tính toán thời gian thực hiện Toàn bộ thời gian yêu cầu được tính toán một cách xấp xỉ là: T= tn/(2p)+ (4(t+ t) + 5 t) n với s là chiều dài đoạn. Như vây ta đã áp dụng tiến trình thiết kế vào trong bài toán giải hệ phương trình tuyến tính. Đây là bài toán cơ bản, có nhiều ứng dụng trong các giải thuật song song thiết kế cho bài toán phức tạp. Chương tiếp sẽ trình bày phương pháp mô phỏng một số giải thuật song song đã thiết kế và đánh giá qua thời gian thực hiện. 5. 3 Thực thi giải thuật Các giải thuật song song cho bài toán giải hệ phương trình tuyến tính được thiết kế cho mô hình tính toán nhiều bộ xử lý. Mỗi máy tính thực hiện một hoặc nhiều tiến trình, trao đổi dữ liệu thông qua mạng truyền thông kết nối. Tuy nhiên ta vẫn có thể mô phỏng được giải thuật trên mô hình máy tính đơn bộ xử lý với việc phân chia thời gian, xử lý một cách xen kẽ các tiến trình. 5. 3. 1 Xây dựng chương trình  Trên một máy tính đơn bộ xử lý thì tại một thời điểm chỉ có một tiến trình thực hiện, do đó các tiến trình không thể đồng thời thực hiện song song nhiều dòng lệnh trên máy tính một bộ xử lý. Trong các hệ điều hành hỗ trợ tính toán song song thì vấn đề này có thể giải quyết bằng cách tạo ra các processor logic, mỗi processor này quản lý một tiến trình tương ứng và thực hiện tiến trình khi nhận được processor vật lý. Với mô hình phân chia thời gian này, các tiến trình sẽ có cảm giác như đang chỉ có duy nhất một tiến trình sử dụng hệ thống. Trong khi thực thi tiến trình song song, mỗi tiến trình có thể thuộc một trong ba trạng thái sau: Nhập Khởi tạo Sẵn sàng Thực hiện Ngắt Kết thúc Vào từ chế độ phân chia thời gian Ra trong chế độ phân chia thời gian Hình 6. 1 Công việc và trạng thái tiến trình Tiến trình nằm trong trạng thái sẵn sàng khi đã được cung cấp đầy đủ tài nguyên để thực hiện, chờ đợi được cung cấp processor vật lý. Tiến trình trong trạng thái thực khi đang thực hiện các lệnh trên processor vật lý. Còn tiến trình trong trạng thái ngắt khi đợi xuất hiện một sự kiện hoặc cung cấp tài nguyên để thực hiện. Tại mỗi thời điểm, có nhiều tiến trình đang tồn tại và có trạng thái riêng. Do đó, để quản lý được các tiến trình song song trong máy tính đơn bộ xử lý, các hệ điều hành cần phải tổ chức lưu thông tin trạng thái tiến trình vào khối điều khiển tiến trình PCB ( Process Control Block). Khối điều khiển này sẽ chứa toàn bộ trạng thái của tiến trình. Các tiến trình chủ yếu nằm trong hai trạng thái là sẵn sàng và ngắt. Tổ chức các tiến trình trong cùng một trạng thái thành một dòng hàng đợi thực sự ( tức là tổ chức theo kiểu FIFO). Khi một tiến trình được cung cấp processor vật lý, các thông tin trong bảng mô tả như bộ đếm chương trình, các thanh ghi, con trỏ stack được nạp vào trong processsor và lưu trữ giá trị hiện thời của CPU. Khi dừng tiến trình lại để chuyển sang tiến trình khác, cần thiết phải lưu trạng thái của các thanh ghi vào PCB. Khi bắt đầu thực hiện một tiến trình mới, cần nạp các trạng thái được lưu trong PCB vào trong processor. Chương trình cần duy trì được các hàng đợi trạng thái trong khi thực hiện, bởi vì các hàng đợi thể hiện trạng thái của tất cả các tiến trình đang tồn tại. Công cụ để các tiến trình có thể thực hiện chính xác là ngắt. Ngắt sẽ phân chia thời gian tính toán cho từng tiến trình, các thiết bị ngoại vi sử dụng ngắt để báo cho processor biết sự thay đổi trạng thái của mình. Trên quan điểm lập trình, từ góc độ processor, ta có thể định nghĩa ngắt ngừng đột xuất việc thực hiện một tiến trình để chuyển sang thực hiện tiến trình khác khi có một sự kiện nào đó xảy ra. Như vậy ngắt là công cụ chuyển điều khiển tới một tiến trình khác mà tiến trình hiện tại không biết. Phần lớn các máy tính đều có đồng hồ độc lập đo khoảng thời gian. Do đó có thể dùng đồng hồ để điều khiển processor theo thời gian. Cần xác lập một khoảng thời gian nhất định cho đồng hồ và giá trị này tự động được giảm dần cho đến khi xuất hiện tín hiệu ngắt đồng hồ. Bằng cách này có thể tạo đồng hồ riêng cho từng tiến trình và việc xử lý dòng xếp hàng kết hợp với thứ tự ưu tiên trở nên dễ dàng hơn nhiều. mỗi phần tử của danh sách ứng với dòng xếp hàng chứa tên tiến trình và khoảng thời gian cần cung cấp processor. Mỗi lần có ngắt đồng hồ báo hết thời gian thì hệ thống kích hoạt tiến trình khác và nạp khoảng thời gian mới bộ đếm thời gian. Tuy nhiên để quản lý các tiến trình như các hệ điều hành 32 bít, ta cần truy xuất vào hệ thống, lấy được các trạng thái của tiến trình đang thực hiện. Với các ngôn ngữ lập trình thông thường thì việc thực hiện các tiến trình song song như thế sẽ rất khó bởi vì người lập trình phải phụ thuộc vào trình biên dịch của ngôn ngữ cụ thể. Đối với bài toán giải hệ phương trình tuyến tính thì các tiến trình được thiết kế phụ thuộc vào tham số hàng, cột. Do đó, đơn vị phân chia là thời gian thực hiện một hàng cột, mỗi tiến trình sẽ thực hiện một hàng hoặc cột sau đó chuyển sang tiến trình khác thực hiện. Lý do giải quyết bài toán lớn vì nếu với bài toán nhỏ do tốc độ của máy tính là quá lớn nên thời gian để giải quyết một bài toán là rất nhỏ ( chỉ khoảng micro giây) nên ta không thể nhận biết được lợi ích của việc thực hiện song song. Vì vậy, bài toán đưa ra thử nghiệp yêu cầu cần phải có số bậc lớn. Mặt khác, do hạn chế về ngôn ngữ thực hiện (ngôn ngữ C), bộ nhớ dành cho chương trình tối đa là 640KB nên việc lưu trữ và trao đổi dữ liệu là hạn chế. Để có thể giải quyết được bài toán lớn ta phải thực hiện việc lưu trữ và truy xuất với bộ nhớ bên ngoài ( ổ đĩa cứng). Cụ thể việc thực hiện được minh hoạ như sau: Tất cả các hệ số của hệ phương trình được lưu trữ ở bộ nhớ ngoài. Khi cần một hệ số nào thì hệ số đó sẽ được đọc vào bộ nhớ trong ( biến tạm thời). Sau khi xử lý xong thì tất cả các biến tạm thời đó lại được lưu trở lại bộ nhớ ngoài ( tất cả các biến đã xử lý và chưa xử lý). Quá trình cứ tiếp tục như vậy cho đến khi chương trình kết thúc. Kết quả sẽ được lưu ra bộ nhớ ngoài. Thước đo đánh giá sự khác biệt giữa thực hiện song song và thực hiện tuần tự đó là thời gian thực hiện của chương trình với cùng một đầu vào. Thời gian thực hiện song song sẽ được tính toán theo cách sau : Khi bắt đầu thực hiện tiến trình ta khởi tạo bộ đếm thời gian (sẽ lấy theo đồng hồ hệ thống). Như vậy mỗi tiến trình sẽ có một bộ đếm thời gian riêng. Khi tiến trình thực hiện xong ( một hàng hoặc một cột), bộ đếm được lưu lại và sẽ được tiếp tục tính toán khi ta bắt đầu lại tiến trình này ( giá trị khởi tạo cho bộ đếm thời gian của tiến trình này là thời gian của việc thực hiện tiến trình này trước đó). Sau khi thực hiện xong thì thời gian thực hiện song song sẽ bằng thời gian lớn nhất mà một trong các tiến trình trên thực hiện. Để so sánh ta sẽ thực hiện giải bài toán này theo giải thuật tuần tự và sẽ thu được thời gian thực hiện tuần tự này, sau đó đem so sánh thời gian đã thu được ở bước thực hiện song song để thấy được hiệu quả của giải thuật song song. 5. 3. 3 Các hạn chế và hướng phát triển chương trình Chương trình được thực hiện trên mô hình máy tính đơn bộ xử lý nên những đánh giá về thời gian không hợp lý bởi vì chưa tính toán được chi phí thời gian truyền thông. Ngoài ra chưa thể áp dụng phân chia thời gian vào bài toán bất kỳ. Các giải thuật song song được thiết kế trên mô hình nhiều bộ xử lý, do đó để đánh giá được giải thuật cũng như thấyđược hiệu quả về thời gian, ta nên xây dựng chương trình trên mô hình máy tính song song Multiprocessor hoặc Multicomputer. Thông thường để giảm chi phí sản xuất máy tính song song, các bài toán song song thường được thực thi trên mạng cục bộ kết nối các máy tính cá nhân sẵn có dựa trên hỗ trợ của hệ điều hành mạng như Unix, Window NT với môi trường tính toán PVM hay MPI. Kết luận Báo cáo đã đề cập đến những vấn đề chung khi thiết kế giải thuật song song như các mô hình tổ chức giải thuật song song, đưa ra các công đoạn trong quá trình thiết kế, cũng như các vấn đề liên quan khi đánh giá hiệu quả giải thuật. áp dụng vào bài toán cụ thể và xây dựng chương trình minh hoạ cho những thiết kế. Tuy nhiên, với hạn chế về thời gian và kiến thức nên chưa xây dựng được chương trình mô phỏng trên nhiều máy tính khác nhau để có thể đánh giá được đúng thời gian thực hiện giải thuật song song. Hiện nay, tính toán song song đang đóng vai trò quan trọng trong các ứng dụng thực tế cũng như các bài toán phục vụ nghiên cứu khoa học. Tìm hiểu được các vấn đề liên quan đến thiết kế giải thuật sẽ đóng vai trò quan trọng khi phát triển ứng dụng song song. Tài liệu tham khảo Nguyễn Thanh Tùng, Giáo trình cơ sở chuyên nghành hệ điều hành, 1995. Nguyễn Đình Trí, Toán cao cấp I, NXB Giáo dục, 1998. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 1998. Nguyễn Thúc Hải, Mạng máy tính và hệ thống mở, NXB Giáo dục, 1997. Michael J. Quinn, Parallel Computing Theory and Practice, NXB McGraw-Hill, 1994. Albert Y. Zomaya, Parallel and Distributed Computing Handbook, NXB McGraw-Hill, 1996. M. Sasikumar, Dinesh Shikhare, P. Ravi Prakash, Introduction To Parallel Processing, Prentice Hall of India, 2000 Joel M. CrichLow, An Introduction to Distributed and Parallel Computing, Prentice Hall, 1997 Ian Foster, Designing and Building Parallel Programs, 1995 10. htttp://www. llnl. gov/computing/turorials/workshops/workshop /parallel_computing 11. Michael Tischer, Cẩm nang lập trình hệ thống, NXB Giáo dục, 1996