Luận văn Giải thuật song song để phân tích và cài đặt một số lớp giải bài toán phi tuyến

o các tiến trình đích. Để linh hoạt cho việc trao đổi, người ta thường gán cho mỗi thông điệp một thẻ bài (tag) và nó được sử dụng để phân biệt các thông điệp trao quá trình trao đổi. Ví dụ: để gửi thông điệp x từ tiến trình số 1 tới tiến trình số 2 và gán cho y, ta viết: send(&x, 2, 5); ở tiến trình số 1 và ở tiến trình số 2 gọi receive(&y, 1, 5); II.2.2.5.3 Truyền thông nhóm Nhiều chương trình phân tán cần phát tán và nhận dữ liệu từ nhiều tiến trình phân tán, nghĩa là cần trao đổi với từng nhóm trong chương trình song song. Để thực hiện truyền thông theo nhóm, chúng ta có thể sử dụng: Broacast(): phát tán cùng một thông điệp cho tất cả các tiến trình trên kênh mych. Broadcast(mych:channel,tag:int, msg:message_type); Hoạt động của lệnh Broadcast() được mô tả như hình 2-9. Các tiến trình tham gia trao đổi trong phát tán dữ liệu phải được xác định. Trong hình 2-9, tiến trình số 0 được xem như tiến trình gốc chứa dữ liệu ở mảng buf để phát tán cho những tiến trình khác. Theo qui ước của mô hình SPMD, mọi tiến trình đều thực hiện cùng một chương trình nên trong hình 2-9 tất cả các tiến trình đều gọi hàm Broadcast(). Hành động phát tán dữ liệu sẽ không thực hiện được cho đến khi tất cả các tiến trình đều thực hiện lời gọi Broadcast(). Hình 2-9 Hoạt động phát tán dữ liệu Reduce(): thực hiện phép toán số học/logic trong nhóm các tiến trình và gửi kết quả tới tiến trình gốc. Reduce(mych:channel,op:op_type, res:Result_type,root: int,tag:int, msg:message_type); Trong đó, Op_type = {MAX, MIN, SUM, PROD, LAND, LOR, BAND, BOR, LXOR, BXOR}} Ví dụ: hình 2-10 mô tả hàm Reduce() tập hợp các giá trị từ n tiến trình và thực hiện phép cộng (SUM) ở tiến trình gốc. Hình 2-10 Hoạt động của hàm Reduce() Scatter(): phân tán công việc cho các tiến trình. Dữ liệu ở mảng buff được chia nhỏ thành n đoạn và phân tán cho n tiến trình trên kênh mych. Scatter(mych:channel, n:int, Buff[N]:DataType); Hàm này được sử dụng để gửi phần tử thứ i của một mảng dữ liệu tới cho tiến trình thứ i. Hình 2-11 mô tả hoạt động của Scatter(). Tương tự trường hợp của Broadcast(), ở đây nhóm các tiến trình kể cả tiến trình gốc phải được xác định. Hình 2-11 Hoạt động của hàm Scatter() Gather(): ngược lại so với hàm Scatter(), dữ liệu được gửi đi theo hàm Scatter() được xử lý bởi những tiến trình nhận được và sau đó được tập hợp lại cho một tiến trình. Gather(mych:channel,Buff[N]:DataType,root:int,sendbuff[N]:DataType); Ngược lại hàm Scatter(), dữ liệu từ tiến trình thứ i được nhận về ở tiến trình gốc và được đưa vào phần tử thứ i của mảng buf, được mô tả như hình 2-12. Hình 2-12 Hoạt động của hàm Gather() Barrier(): thực hiện việc đồng bộ hoá những tiến trình cùng gia nhập một kênh truyền. Mỗi tiến trình phải chờ cho đến khi tất cả các tiến trình khác trên kênh đạt đến điểm đồng bộ hoá bằng lời gọi Barrier() trong chương trình. Barrier(mych:channel); II.2.3 Lập trình trên cụm máy tính. Mô hình truyền thông điệp nêu trên được sử dụng rất hiệu quả để lập trình song song theo cụm máy tính. Một môi trường cho hệ thống nhiều máy tính, nhất là các cụm máy tính đã được phát triển và được sử dụng phổ biến hiện nay là PVM (Parallel Virtual Machine). PVM cung cấp môi trường phần mềm để truyền thông điệp cho các hệ máy tính thuần nhất và cả không thuần nhất. PVM có một tập hợp các hàm thư viện được viết bằng C hoặc Fortran. Mỗi chương trình được viết bằng C, được biên dịch để chạy trên những kiểu máy tính xác định trên mạng. Nếu mạng gồm những máy tính cùng kiểu thì chương trình chỉ cần dịch một lần. Mỗi nút trong mạng (LAN) phải truy cập đến hệ thống tệp chứa các chương trình đã được dịch để thực hiện. Tập các máy tính được sử dụng trong mạng phải được định nghĩa theo các mức ưu tiên để chạy các chương trình. Điều này được thực hiện trên tập máy ảo song song PVM [5]. Cách thực hiện tốt nhất là tạo ra một danh sách tên gọi của các máy tính và đặt ở hostfile. Tệp này được PVM đọc để thực hiện các chương trình. Mỗi máy tính có thể chạy một hay nhiều tiến trình (chương trình ứng dụng). Các chương trình ứng dụng chạy trong các máy tính thông qua các tiến trình của PVM để trao đổi với nhau trên mạng như hình 2-13. Các tiến trình PVM yêu cầu đủ thông tin để chọn lựa đường truyền dữ liệu. PVM Chương trình ứng dụng PVM Chương trình ứng dụng PVM Chương trình ứng dụng Máy tính trạm Máy tính trạm Máy tính trạm Trao đổi thông điệp trên mạng Hình 2-13 Sự trao đổi thông điệp của các máy tính trong hệ PVM Các chương trình của PVM thường được tổ chức theo mô hình chủ-tớ (master-slave), trong đó tiến trình chủ được thực hiện trước tiên, sau đó các tiến trình tớ sẽ được tạo ra trong tiến trình chủ đó. Hàm phát sinh tiến trình mới trong PVM là: pvm_spawn(). Một tiến trình muốn tham gia vào hệ PVM thì nó phải ghi danh bằng cách gọi hàm pvm_mytid(). Các tiến trình muốn được huỷ bỏ thì gọi hàm pvm_exit(). Các chương trình trao đổi thông điệp với nhau thông qua các hàm pvm_send() và pvm_recv(). Tất cả các thủ tục gửi đều không bị chặn (dị bộ) còn các thủ tục nhận thì hoặc bị chặn (được đồng bộ) hoặc không bị chặn. Các thao tác chính của việc gửi và nhận dữ liệu được thực hiện ở các bộ đệm buffer. Nếu dữ liệu được gửi đi là một danh sách các mục có cùng kiểu thì trong PVM sử dụng pvm_psend() và pvm_precv(). Hình 2-14 mô tả hoạt động của hai tiến trình trao đổi một mảng dữ liệu với nhau. . . . pvm_precv(); . . . Tiến trình 2 send buffer . . . pvm_send(); . . . Tiến trình 1 Chờ thông điệp Tiếp tục xử lý Hình 2-14 Gọi hàm pvm_psend() và pvm_precv() Khi dữ liệu chuyển đi là phức tạp, gồm nhiều kiểu khác nhau thì chúng phải được đóng gói lại (pack) để gửi đến buffer, sau đó tiến trình nhận lại mở gói (unpack) để nhận về dữ liệu tương ứng. Đó là các hàm: pvm_pkint() và pvm_upkint() cho dữ liệu kiểu int pvm_pkfloat() và pvm_upkfloat() cho dữ liệu kiểu float pvm_pkstr() và pvm_upkstr() cho dữ liệu kiểu string, v.v. Lưu ý: thứ tự mở gói để lấy dữ liệu ra phải đúng theo thứ tự mà chúng được đóng gói ở tiến trình gửi. Bộ đệm buffer để gửi dữ liệu là mặc định và nó phải được khởi tạo ở tiến trình gửi bằng lệnh pvm_inítend(). Hình 2-14 mô tả nguyên lý hoạt động nêu trên. Tương tự, các lệnh khác về trao đổi thông điệp theo nhóm như: pvm_bcast(), pvm_scatter(), pvm_gather(), pvm_reduce(), v.v. II.2.4 Đánh giá các chương trình song song Để sử dụng hiệu quả các thuật toán song song, chúng ta cần phải biết cách đánh giá nó. Thời gian thực hiện song song Để đánh giá được độ phức tạp tính toán của các thuật toán song song, ngoài số bước tính toán chúng ta còn cần đánh giá thời gian truyền thông của các tiến trình. Trong một hệ thống truyền thông điệp, thời gian truyền thông điệp cũng phải được xem trong thời gian thực hiện của thuật toán. Thời gian thực hiện song song, ký hiệu là tp gồm hai phần tcomp và tcomm tp = tcomp + tcomm Trong đó, tcomp là thời gian tính toán và tcomm - thời gian truyền thông dữ liệu. Thời gian tính toán tcomp được xác định giống như thuật toán tuần tự. Khi có nhiều tiến trình tiến trình thực hiện đồng thời thì tính thời gian thực hiện của tiến trình phức tạp nhất (thực hiện lâu nhất). Trong phân tích độ phức tạp tính toán, chúng ta luôn giả thiết rằng, tất cả các bộ xử lý là giống nhau và thao tác cùng một tốc độ như nhau. Đối với những cụm máy tính không thuần nhất thì điều này không đảm bảo do vậy, việc đánh giá thời tính toán của những hệ như thế là rất phức tạp. Thời gian truyền thông tcomm lại phụ thuộc vào kích cỡ của các thông điệp, vào cấu hình kết nối mạng đường truyền và cả cách thức truyền tải thông điệp, v.v. Công thức ước lượng thời gian truyền thông được xác định như sau: tcomm = tstartup + n * tdata Trong đó, + tstartup là thời gian cần thiết để gửi những thông điệp không phải là dữ liệu. Nó bao gồm cả thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói ở nơi nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số. + tdata là thời gian cần thiết để chuyển một từ dữ liệu (một mục dữ liệu) từ nơi gửi tới nơi nhận, được giả thiết là hàng số và n là số từ dữ liệu được trao đổi trong hệ thống. Ví dụ: Giả sử cần thực hiện cộng n số trên hai máy tính, trong đó mỗi máy cộng n/2 số với nhau và tất cả các số đó được lưu ở máy tính thứ nhất. Kết quả của máy tính thứ hai khi được tính xong sẽ được chuyển về máy tính thứ nhất để nó công hai kết quả bộ phận với nhau. Bài toán này được phát biểu như sau: Máy tính thứ nhất gửi n/2 số cho máy tính thứ hai Cả hai máy tính cộng n/2 số một cách đồng thời Máy tính thứ hai chuyển kết quả tính được về máy tính thứ nhất Máy tính thứ nhất cộng hai kết quả để có kết quả cuối cùng. Thời gian tính toán (ở bước 2 và 4): tcomp = n/2 + 1 Thời gian truyền thông (ở bước 1 và 3): tcomm = (tstartup + n/2 * tdata) + (tstartup + tdata) = 2*tstartup + (n/2 + 1) * tdata Độ phức tạp tính toán là O(n) và độ phức tạp truyền thông cũng là O(n), do vậy độ phức tạp nói chung của thuật toán trên cũng là O(n). Tóm lại, để giải những bài toán đặt ra một cách hiệu quả trên những máy tính mà chúng ta có, vấn đề chính làm thế nào để xây dựng được những thuật toán song song. Cách làm khá thông dụng là biến đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng song song về dạng song song phù hợp hơn sao vẫn bảo toàn được tính tương đương trong tính toán. Do đó, khi biến đổi chúng ta cần trả lời hai câu hỏi: Kiến trúc nào phù hợp cho bài toán? Những bài toán loại nào sẽ xử lý hiệu quả trong kiến trúc song song cho trước? Và dựa vào những nguyên lý thiết kế chính: nguyên lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên lý đồ thị phụ thuộc dữ liệu, nguyên lý điều kiện tranh đua để xây dựng một số thuật toán song song thường dùng như các thuật toán sắp xếp, tìm kiếm, các thuật toán toán tính toán trên ma trận, hay nhiều thuật toán tính toán khác Để đánh giá được tính hiệu quả của thuật toán song song thường phải dựa vào độ phức tạp của thuật toán. Độ phức tạp tính toán của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Để áp dụng cơ chế xử lý song song, chúng ta có thể sử dụng các hệ điều hành hiện nay ví dụ như Window, OS/2, và UNIX và một số ngôn ngữ lập trình, chẳng hạn như C, Java,.. và một số mô hình lập trình song song. Một trong các mô hình lập trình song song đang được sử dụng phổ biến hiện nay là mô hình truyền thông điệp. Trong mô hình truyền thông điệp, các tiến trình chia sẻ với nhau kênh truyền thông. Kênh truyền thông là khái niệm trừu tượng của đường truyền thông vật lý giữa các tiến trình. Các kênh được truy cập bởi hai phương thức: send() và receive(). Để bắt đầu trao đổi được với nhau thì một tiến trình phải gửi đi (send) một thông điệp vào kênh truyền và có một tiến trình khác yêu cầu nhận (receive) thông điệp đó. Sự trao đổi được hoàn tất khi dữ liệu đã được chuyển từ nơi gửi tới nơi nhận. Mô hình truyền thông điệp nêu trên được sử dụng rất hiệu quả để lập trình song song theo cụm máy tính. Một môi trường cho hệ thống nhiều máy tính, nhất là các cụm máy tính đã được phát triển và được sử dụng phổ biến hiện nay là PVM . PVM cung cấp môi trường phần mềm để truyền thông điệp cho các hệ máy tính thuần nhất và cả không thuần nhất. CHƯƠNG III GIẢI THUẬT SONG SONG CHO MỘT SỐ BÀI TOÁN PHI TUYẾN Trong phần này chúng tôi trình bày phương pháp giải một số bài toán phi tuyến. Nhiều bài toán phi tuyến khá phức tạp thì ít khi tìm được nghiệm đúng mà chỉ là xấp xĩ. Khi giải hệ phương trình phi tuyến bằng phương pháp tuyến tính hoá, ta đều phải giải hệ phương trình đại số tuyến tính. Đầu tiên, chúng tôi khảo sát bài toán giải hệ phương trình tuyến tính. III.1 Bài toán giải hệ phương trình tuyến tính Giả sử có hệ phương trình tuyến tính được viết dưới dạng ma trận Ax = b Trong đó, A = (ai,j) là ma trận hằng số cấp n´n, x là vector nghiệm và b là vector hằng số. Một trong các cách giải hệ phương trình tuyến tính là sử dụng phương pháp khử Gaussian để đưa ma trận A về ma trận tam giác trên. Phương pháp Gaussian dựa vào đặc tính của các phương trình tuyến tính là bất kỳ một hàng nào cũng có thể thay thế bằng chính nó được cộng thêm với hàng khác được nhân với một hằng số. Thuật toán Guassian bắt đầu từ hàng thứ nhất và tìm cách khử dần cho đến hàng cuối cùng chỉ còn lại một phần tử. Ở hàng thứ i, những hàng thứ j đứng dưới i ( j > i) được thay bằng: hàng j + (hàng i)*(-aj,i/ai,i), nếu ai,i khác 0. Kết quả là tất cả các phần tử trong cột thứ i đứng dưới hàng i đều trở thành 0. aj,i = aj,i + ai,i (-aj,i / ai,i) = 0 Tất nhiên nếu ai,i = 0 thì phải tìm cách thay đổi thứ tự các hàng trong hệ phương trình tuyến tính sao cho tất cả các phần tử trên đường chéo chính của ma trận A là khác 0. Lưu ý khi ma trận A không suy biến thì luôn chuyển được về dạng sao cho tất cả các phần tử trên đường chéo chính aii ¹ 0. Quá trình này được mô tả như trong hình 3-1. Hàng i Hàng j Hàng cột Bước tiếp theo aj,i Cột i Đã khử về 0 Cần khử về 0 Hình 3-1 Phương pháp khử Gaussian Thuật toán Gaussian (tuần tự) được viết như sau: for(i = 0; i < n-1; i++)/* Trừ hàng đầu tiên */ for(j = i+1; j < n; j++){ m = a[j][i]/a[i][i]; for(k = i; k < n; k++) a[j][k] = a[j][k] – a[i][k]*m; b[j] = b[j] – b[i] * m; } Độ phức tạp tính toán của thuật toán Gaussian là O(n3). Cài đặt thuật toán Gaussian song song. Từ thuật toán tuần tự nêu trên chúng ta thấy chu trình trong cùng làm thay đổi hàng j và thực hiện những phép toán độc lập với nhau. Do vậy, có thể chia nhỏ bài toán bằng cách cho mỗi bộ xử lý giữ một hàng thực hiện trên hàng đó. Thuật toán song song thực hiện như sau: Bộ xử lý P0 giữ hàng 0 và phát tán (broadcast) tất cả các phần tử của hàng đầu tiên cho n-1 bộ xử lý còn lại. Các bộ xử lý thực hiện các phép nhân với những hệ số tương ứng và thay đổi trên hàng của mình. Các phần tử ở hàng thứ i được phân tán bởi Pi là: a[i][i+1], a[i][i+2], …, a[i][n-1] và b[i], tổng cộng là n-i+1 phần tử. Đánh giá thuật toán Giá truyền thông: Giả sử các thông điệp được phát tán trong từng nhịp. Thông điệp được phát tán lần thứ i chứa n-i+1 phần tử, suy ra công thức tính thời gian truyền thông của hệ thống sẽ là: tcomm = (tstartup + (n-i+1)tdata) = ((n-1)tstartup + ((n+1)(n+2)/2 –3)tdata) Vậy độ phức tạp truyền thông là O(n2). Độ phức tạp tính toán: Các bộ xử lý Pj bên dưới Pi sẽ nhận được dữ liệu từ Pi chuyển tới và tính toán trên những n-j+2 số của hàng đó. Chúng thực hiện n-j+2 phép nhân và n-j+2 phép cộng. Do đó, số các phép toán cơ sở sẽ là: tcomp = (n – j + 2) = ((n+3)(n+2)/2 –3) = O(n2). Sau khi đã chuyển ma trận hệ số về dạng ma trận tam giác trên, chúng ta có thể xây dựng thuật toán song song để giải hệ phương trình thu được theo phương pháp thế quay lui. Ví dụ, áp dụng thuật toán khử Gaussian đưa về hệ phương trình dạng: 2x1 - 2x2 - 2x3 + 1x4 = 5 2x2 - 1x3 + 3x4 = 4 1x3 - 3x4 = 0 4x4 = 4 Giải phương trình cuối cùng thu được x4 = 1 sau đó thế vào phương trình thứ ba (ở trên) ta tính được x3 = 3. Bằng cách đó, chúng ta thế những biến đã được xác định quay lui lên phía trên để tính được x2 = 2, x1 = 7. Giả sử A là ma trận tam giác trên và b là vector hằng số. Thuật toán giải hệ phương trình tuyến tính Ax = b được xây dựng như sau: spawn(Pi), 0 < i £ p /* tạo ra p tiến trình *? for(i = n; i > 1; i--){ x[i] = b[i]/a[i,i]; forall Pj where 1 £ j £ p do { for(k = j; k <i; k += p){ b[k] = b[k] – x[i] * a[k][i]; a[k][i] = 0; } } } III.2 Bài toán phi tuyến III.2.1. Phát biểu bài toán phi tuyến Trong phần này chúng ta nghiên cứu giải thuật để giải hệ phương trình phi tuyến và bài toán phi tuyến bình phương nhỏ nhất. Bài toán của những phương trình phi tuyến được cho bởi: F : Rn ® Rn , tìm x* Î Rn sao cho F(x*) = 0, (3.1) và bài toán phi tuyến bình phương nhỏ nhất được cho bởi : F : Rn ® Rm , tìm x* Î Rn sao cho Minú êF( x* )ú ê2, (3.2) trong đó giả thiết rằng F( x) là hàm khả vi liên tục. Ví dụ : Bài toán Broyden, với h là tham số thực là hệ phương trình phi tuyến III.2.2 Giải thuật tuần tự giải bài toán phi tuyến bằng phương pháp Tensor Hệ phương trình phi tuyến và bài toán phi tuyến bình phương nhỏ nhất được ứng dụng rất nhiều trong thực tiễn và đã có nhiều phương pháp để giải chúng. Đặc biệt đối với một số bài toán phi tuyến tại nhiều điểm, F’(x*) có điều kiện xấu hoặc suy biến với một dãy số khuyết nhỏ. Trong trường hợp này, phương pháp Tensor cải tiến có hiệu quả hơn phương pháp chuẩn (Newton hoặc Gaussian-Newton). Phương pháp Tensor cũng đặc biệt có hiệu quả đối với những bài toán khi F’(x*) không suy biến. Bây giờ chúng tôi giới thiệu phương pháp Tensor. Cho triển khai Taylor đến cấp hai có dạng: Phương pháp Tensor căn cứ vào mỗi phép lặp trên mô hình bậc hai của hàm phi tuyến hay còn gọi là mô hình Tensor: (3.3) với J(xc) = F’(xc) là ma trận Jacôbi tại xc, và Tc Î Rmxnxn là đối tượng ba chiều được gọi là số hạng tensor tại xc. Số hạng tensor được chọn sao cho mô hình có phép nội suy giá trị hàm từ phép lặp trước. Kết quả này trong Tc tồn tại một dãy p tensor, điều đó quyết định đến hiệu quả của phương pháp Tensor. Sau khi định hình mô hình thì bài toán tổng quát được giải; nghĩa là tại mỗi phép lặp của phương pháp Tensor, cực tiểu hoá của mô hình sẽ được sử dụng nếu không tìm thấy nghiệm của bài toán. Phương pháp Tensor là phương pháp tổng quát có hữu hiệu đối với bài toán khi mà Jacôbi có nghiệm là suy biến hoặc điều kiện xấu. Mỗi phép lặp dựa trên dạng bậc hai của hàm phi tuyến F(x). Riêng chọn số hạng tensor Tc Î Rm x n x n bởi vì số hạng bậc hai Tcdd trong (3.3) là dạng đơn giản và dễ sử dụng. Chúng ta dùng số hạng tensor cho phép mô hình cục bộ M(xc + d) theo giá trị nội suy của hàm F(x) tại phép lặp đã qua (past) là x – k . Như vậy mô hình sẽ trở thành: F(x –k ) = F(xc) + F’(xc)sk + ½ Tc sksk , k = 1,..,p (3.4) với sk = x – k - xc , k = 1,..,p. Những điểm đã qua (past points) là x –1, .., x– p được chọn vì thế tập hợp các hướng sk chiều từ xc đến những điểm được chọn sẽ độc lập tuyến tính mạnh; chúng ta yêu cầu mỗi hướng sk phải tạo một góc tối thiểu 45 độ với không gian con sinh bởi hướng đã qua (past directions) được chọn trước đó. Thủ tục tìm kiếm hướng độc lập tuyến tính dễ dàng thi hành, bằng cách sử dụng thuật toán Gram-Schmidt [4]. Sau khi chọn hướng đã qua độc lập tuyến tính, chúng ta hình thành số hạng tensor. Schnabel và Frank [16] đã chọn Tc là ma trận nhỏ nhất thoả mãn điều kiện nội suy (3.4) như sau: (3.5) tuỳ thuộc vào Tcsksk = 2(F(x –k ) – F(xc) – F’(xc)sk), với , theo tiêu chuẩn Frobenius của Tc được định nghĩa bởi : (3.6) Nghiệm của (3.5) là tổng của dãy p-1 tensor , (3.7) với ak là cột thứ k của A Î Rm x p , A được định nghĩa bởi A = ZM –1, Z là ma trận cấp (m x p) mà cột Zj = 2(F(x –j ) – F(xc) – F’(xc)sj) và M là ma trận cấp (p x p) được định nghĩa bởi M(i, j) = (siTsj)2, 1 £ i, j £ p. Như vậy Sử dụng số hạng tensor mà chúng ta vừa tìm được, thì mô hình Tensor (3.3) trở thành M(xc + d) = F(xc) + F’(xc)d + . (3.8) Dạng đơn giản của số hạng bậc hai trong (3.8) là chìa khoá vừa có hiệu quả trong việc định hình, trong lưu trữ và giải bằng mô hình Tensor. Đầu tiên của mô hình Tensor là định hình, nghiệm của mô hình được tìm thấy. Nó có thể không tồn tại nghiệm; trong trường hợp này thay bằng tìm cực tiểu. Vì thế, chúng ta giải bài toán tổng quát sau đây Tìm d Î Rn sao cho ÷êM(xc + d)÷ê2 cực tiểu (3.9) Để giải (3.9) có thể biến đổi đưa về giải m – n + q phương trình toàn phương p ẩn, cộng với giải n - q phương trình tuyến tính n - p ẩn. Ở đây q = p khi F’(x) là không suy biến, thường rank(F’(xc)) ³ n-p và q > p trong trường hợp khác. Những bước chính của thuật toán được mô tả: 1. Phép biến đổi trực giao của không gian các biến số được sử dụng để biến m phương trình n ẩn về dạng tuyến tính n-p biến số trong và dạng toàn phương chỉ còn lại p biến số trong 2. Sử dụng phép biến đổi trực giao của những phương trình để khử n – p phép biến đổi tuyến tính của biến số từ n – q phương trình. Kết quả là hệ (m - n+ q) phương trình toàn phương p ẩn trong và một hệ n – q phương trình tuyến tính n – p ẩn trong . 3. Tối ưu hoá phi tuyến không ràng buộc, sử dụng [17] để cực tiểu hoá theo tiêu chuẩn l2 của (m-n+q) phương trình toàn phương p ẩn trong 4. Hệ của (n-q) phương trình tuyến tính mà là tuyến tính còn lại n-p ẩn được giải trong . Lời giải chi tiết, đầy đủ bởi thuật toán 3.1 như sau: Thuật toán 3.1.Tìm nghiệm của mô hình Tensor {Tìm bước tensor dt } Cho p £ n, F Î Rm , J Î Rm x p, S Î Rn x p , {Chú thích bước 1-2: Biến đổi hệ m phương trình n ẩn F + Jd + 1/2 A{STd}2 = 0 (3.10) thành hệ m phương trình n ẩn trong và (3.11)} Bước 1. Tìm trực giao Q Î Rn x n sao cho với (3.12) và là ma trận hình tam giác. Bước 2. Tính và cho và lần lượt biểu thị cho n-p cột trước và p cột sau của tương ứng. Cũng định nghĩa và cho và lần lượt biểu thị n-p thành phần đầu tiên và p thành phần cuối cùng của tương ứng. {Chú thích bước 3-4 : Chuyển đổi hệ phương trình (3.11) về dạng (3.13) Như vậy, nó trở thành hệ của n-q phương trình với n ẩn (3.14) và hệ m-n+q phương trình với p biến (3.15)} Bước 3. Tìm trực giao và ma trận hoán vị sao cho (3.16) với là ma trận tam giác trên và n-q là (số) hạng của . Bước 4. Tính toán (3.17) Tương tự tính và cho và biểu thị cho n-q dòng trên và m-n+q dòng dưới của tương ứng; cũng vậy, tính và cho và biểu thị cho n-q thành phần đầu tiên và m-n+q thành phần cuối cùng của tương ứng. Bước 5. Giải {Tìm } (3.18) Bước 6. Tìm bằng cách giải (3.19) Nếu q > p, tối thiểu hoá chuẩn l2, được tìm thấy. Bước 7. Tính toán Bước (step) Newton hoặc Gaussian-Newton được tính toán dễ như là kết quả phụ cho việc tìm nghiệm của bước tensor. Sử dụng bước tensor và bước Newton hoặc bước Newton-Gaussian là một phần trong thuật toán toàn cục xác định bước lặp tiếp theo đã được bổ sung trong [7], đó là tìm kiếm đường thẳng (line search ) và miền tin cậy (trust region ). Phương pháp miền tin cậy được sử dụng trong [7] là bước miền tin cậy hai chiều trên không gian con sinh bởi hướng đi xuống dốc nhất và bước tensor (hoặc bước chuẩn). Lý do chính để chọn phương pháp này vì nó có cấu trúc dễ dàng, có mối quan hệ khép kín đến những thuật toán kiểu gấp khúc (dog-leg) trên cùng không gian con và có thể đóng kín tốt nhất đối với những thuật toán bước miền tin cậy trong thực tiễn. Bây giờ chúng ta thảo luận cách giải xấp xĩ của bài toán miền tin cậy bằng cách cực tiểu hoá trên không gian con hai chiều. Cách giải quyết miền tin cậy hai chiều của mô hình Tensor là tính toán nghiệm xấp xĩ đối với (3.20) bằng cách thực hiện cực tiểu hoá hai chiều, (3.21) với dt là bước tensor và g là hướng đi xuống dốc nhất (hướng gradient). Phương pháp này sẽ luôn luôn đưa ra bước mà rút gọn mô hình bậc hai về nhỏ nhất, cũng vậy những thuật toán kiểu gấp khúc (dogleg) thì biến đổi d thành từng khúc tuyến tính trong không gian con tương tự. Mỗi bước lặp của thuật toán Tensor, mô hình miền tin cậy có thể giải được (3.21) hoặc cực tiểu hoá mô hình tuyến tính chuẩn trên không gian con hai chiều sinh bởi bước chuẩn Newton (hoặc Gaussian-Newton) và hướng đi xuống dốc nhất. Bây giờ chúng ta xác định bước miền tin cậy hai chiều đối với phương pháp Tensor: Thuật toán 3.2 Miền tin cậy (Trust region) hai chiều đối với phương pháp Tensor: Cho dt là bước tensor, dn là bước chuẩn, g = J(xc)TF(xc), là bán kính của miền tin cậy và xc là bước lặp hiện hành Bước 1. Nếu dt được chọn thì (3.22) tuỳ thuộc vào {Chú thích: Để tìm nghiệm (3.22) nó tương đương với việc tìm cực tiểu toàn cục của phương trình với a sau đây với ak và sk được định nghĩa như ở trên. (3.22’) Ta chia khoảng (-dc; dc) thành nint khoảng con, sử dụng nint = 40 nếu dc > 0.01, ngược lại nint = 10) và thực hiện cực tiểu hoá cục bộ f(a) trong khoảng con [ak, ak+1] nếu một trong các điều kiện 1.2, 1.3, hoặc 1.4 được thoả mãn. B 1.1. B 1.2. Nếu f’(ak) 0 thì bắt đầu tìm từ điểm mà giá trị hàm là min(f(ak), f(ak+1)). B 1.3. Nếu f’(ak) < 0, f’(ak+1) < 0 thì Nếu f(ak) < f(ak+1) thì bắt đầu tìm từ ak+1 Ngược lại “cực tiểu hiện hành” = ak+1; B 1.4. Nếu f’(ak) > 0, f’(ak+1) > 0 thì Nếu f(ak) > f(ak+1) thì bắt đầu tìm từ ak+1 ngược lại “cực tiểu hiện hành” = ak; B 1.5. Nếu f(”cực tiểu toàn cục”) > f(“cực tiểu hiện hành”) thì ”cực tiểu toàn cục” := “cực tiểu hiện hành” k = k + 1; ak+1 = ak + subint Go to Bước 1.2 } Ngược lại {dn được chọn} tuỳ thuộc vào (Thực hiện bằng thủ tục giống như các bước từ 1.1-1.5 đã thảo luận). {Chú thích. Điều này tương đương với việc tìm cực tiểu toàn cục của phương trình với a sau đây: }. Bước 2. Nếu bước tensor được chọn thì Đặt Ngược lại Bước 3. Kiểm tra bước lặp mới và cập nhật bán kính miền tin cậy B 3.1. x+ = xc + d B 3.2. Nếu Ở đây khi dn được chọn hoặc khi dt được chọn Thì bước toàn cục d thành công Ngược lại Giảm miền tin cậy Go to Bước 1. Một phương pháp được sử dụng để điều chỉnh miền bán kính trong khoảng giữa của những bước là thuật toán TRUPDATE trong [11]. Miền bán kính đầu tiên có thể được thay thế tuỳ theo người sử dụng. Thuật toán tìm kiếm đường thẳng được sử dụng là dạng chuẩn toàn phương quay lui để tìm đường thẳng sẽ không trình bày ở đây. Để bước nào phù hợp với thuật toán tại mỗi phép lặp thì chúng ta phải chọn bước đó. Thuật toán chọn bước như sau: Thuật toán 3.3. Chọn bước {Step selection} Cho Jc(xc) = Xấp xĩ của F’(xc), g = J(xc)TF(xc) là gradient của tại xc, dt = nghiệm hoặc cực tiểu của mô hình tensor dn = Bước Newton –J(xc)– 1F(xc) hoặc Bước Gaussian-Newton –(J(xc)TJ(xc))–1 J(xc)TF(xc) nếu J(xc) là điều kiện đủ tốt, Bước Levenberg-Marquardt –(J(xc)TJ(xc) + mI)–1 J(xc)TF(xc) trong trường hợp khác, với e = epsilon, MT = Mô hình tensor, MN = Mô hình Gaussian-Newton. Nếu (Nghiệm hoặc cực tiểu của mô hình tensor không tìm thấy) Hoặc ((Cực tiểu của mô hình tensor không có nghiệm nào) Và ( Hoặc Thì x+ ¬ xc + ldn, l Î(0;1] được chọn bằng thuật toán tìm kiếm đường thẳng, hoặc x+ ¬ xc + ldn - bg, a,b được chọn bằng thuật toán miền tin cậy Ngược lại x+ ¬ xc + ldt, l Î(0;1] được chọn bằng thuật toán tìm kiếm đường thẳng, hoặc x+ ¬ xc + ldt - bg, a,b được chọn bằng thuật toán miền tin cậy Kết thúc. Sau đây là thuật toán lặp tổng thể của phương pháp Tensor Thuật toán 3.4. Thuật toán lặp bằng phương pháp Tensor Cho trước m, n, xc, F(xc) Bước 1. Tính toán F’(xc) và lựa chọn có dừng hay không, nếu không : Bước 2. Chọn những điểm đã qua để sử dụng trong mô hình tensor tối đa là từ những điểm mới xảy ra gần đây. Bước 3. Tính toán số hạng bậc hai của mô hình tensor Tc, sao cho nó là phép nội suy F(x) của mô hình Tensor tại tất cả các điểm đã được chọn ở Bước 2 Bước 4. Tìm nghiệm của mô hình Tensor hoặc cực tiểu của nó (trong chuẩn l2) nếu nó không có nghiệm thực. Bước 5. Tính toán bước chuẩn Newton hoặc Gaussian-Newton như là kết quả phụ của Bước 4 vừa nêu. Bước 6. Chọn bước tensor hoặc bước chuẩn. Bước 7. Chọn x+ sử dụng chiến lược tìm kiếm đường thẳng hoặc miền tin cậy hai chiều toàn cục. Bước 8. Đặt xc = x+, F(xc) = F(x+), nhảy đến Bước 1. III.2.3 Giải thuật song song của bài toán phi tuyến bằng phương pháp Tensor . III.2.3.1 Song song xấp xĩ Jacobi Cách giải quyết mà chúng ta sử dụng trong song song xấp xĩ của ma trận Jacobi bằng sai phân độc lập trên hướng tách hàng của hàm F. Khi ước lượng của hàm F được tách ra thì ước lượng Jacobi có thể rất đơn giản trong song song như sau: Thuật toán của chúng ta có dữ liệu phân tán và những hàm gần như khối cho nên sự tính toán nhập vào của hàm ước lượng và nhân tử hoá được cân bằng bởi sử dụng ánh xạ đóng từ tập Ik của những hàng được phân đến cho bộ xử lý k = {i / i-1 = k mod p}, k = 0,..,p – 1, i = 1,..,m. Ở đây công việc nhập vào trở nên cân bằng tốt hơn khi m/p tăng lên. Nút chương trình song song của hàm ước lượng F(x) là: Thuật toán 3.5 Song song của hàm ước lượng {evaluate} i ¬ processid + 1; While i <= m do Ước lượng(fi(x)) tại xk được nạp vào; i = i + p; EndWhile. Để xấp xĩ Jacobi bằng sai phân hữu hạn bộ xử lý (i-1)mod p tính toán hàng i của Jacobi bằng (3.23) ở đây thường kích thước bước (stepsize) Một nút (node) chương trình của xấp xĩ song song đối với Jacobi bằng thuật toán sau: Thuật toán 3.6 Ước lượng song song Jacobi i ¬ processid + 1 While i <= m do For j = 1 to n do Ước lượng(fi(x + hj ej) EndFor i = i + p EndWhile. III.2.3.2 Song song nhân tử hoá QR và giải lùi Bây giờ tìm hiểu và nghiên cứu thuật toán nhân tử hoá QR và xấp xĩ sai phân hữu hạn của Jacobi. Ở đây, hiệu quả của nhân tử hoá song song QR là hết sức quan trọng đối với chúng ta, khi nhân tử hoá QR đầy đủ được yêu cầu tại mỗi phép lặp. Khi tính hiệu quả song song của nhân tử hoá QR luôn luôn tồn tại thì chúng ta không cần nghiên cứu song song nhân tử hoá Householder theo hướng hàng mới. Để thay vào, chúng ta cung cấp song song nhân tử hoá Householder theo hướng hàng của Coleman và Plassman được thảo luận trong [21]. Coleman và Plassman đã tìm thấy song song của nhân tử hoá QR có hiệu quả hơn thuật toán nhân tử hoá song song lai (hybrid) (Householder/Givens) ở trước. Để làm rõ thuật toán QR song song của Coleman và Plassman, xem xét nhân tử hoá QR của ma trận A cấp (m x n). Tại bước j của nhân tử hoá j-1 dòng đầu tiên của R và j-1 vectơ Householder đã được tính toán và chỉ có (m-j+1) x (n-j+1) ma trận con bên phải ở dưới của A cần thiết được làm nhân tử. Đặt A(j) là ma trận con của A, với ak(j) là cột, k = j,..,n. Một phép biến đổi P(j) rút gọn cột đầu tiên của A(j) là aj(j) được cho bởi , với . (3.24) Để xác định ak(j+1), k = j+1,..,n, đúng với một dãy cập nhật đến A(j) cần được tính toán như sau: . (3.25) với ak( j ) được xác định trước. Giả thiết rằng hàng j được phân cho một bộ xử lý có tên là leader. Chú ý rằng v( j ) thích hợp với a( j ) không kể thành phần đầu tiên, vì vậy phần của tích trong bộ phận v( j )Tak( j ) đối với mỗi bộ xử lý chính là aj( j )Tak( j ) trừ phi trên leader với a( j ) và v( j ) khác nhau trong thành phần đầu tiên. Coleman và Plassman[21] đã giúp cho cơ sở lập luận này là kết hợp truyền thông để tính toán v( j ) với truyền thông được yêu cầu đối với dãy khuyết-một cập nhật đến phần còn lại của ma trận . Nét đại cương của thuật toán nhân tử hoá QR song song của Coleman và Plassman được phác hoạ như sau Đặt dòng j phân cho bộ xử lý mà được chỉ định là leader, là vector được sử dụng trong sự tính toán của và a k(j) hằng số không đổi, k = j+1,..,n và tập giá trị đầu Ik = {i/ i Î [1; n], i-1 =k mod p}, k = 0,..,p-1. Thuật toán 3.7 Thuật toán song song QR Householder hướng hàng Proc(k) : Chương trình đối với bộ xử lý k For j = 1 to n do If (k = leader) then xoá {j} từ Ik; Tính toán tích nhỏ al(j) Taj(j) với l = j,..,n For mỗi i Î Ik do EndFor Tổ hợp lại sử dụng phép lấy tổng (gather-sum) If (k = leader) then Cập nhật Cập nhật Tính toán hệ số [al,…, an ] với l = j+1,..,n và truyền đi kết quả Cập nhật những cột, l = j + 1,..,n For mỗi i Î Ik do EndFor EndFor Enddo. Cột xoay kết hợp chặt chẽ trong thuật toán 3.7 như sau. Cột chuẩn của ma trận A là đầu tiên tại điểm khởi đầu của thuật toán và cập nhật sau mỗi cấp tính toán thu được cột chuẩn A(j). Ví dụ, mục đích tại cấp j trong cột chuẩn của nhân tử hoá QR được biết bởi leader. Cột chuẩn lớn nhất, kmax được xác định bởi leader, kết quả được truyền đi và những cột j và kmax đổi chỗ cho nhau bởi tất cả các bộ xử lý. Sau cấp j của thuật toán, chuẩn được cập nhật có thể thu được từ công thức (3.26) với k = j+1,…,n bằng leader và kết quả được gởi đến leader tiếp theo (tương tự như bộ xử lý tiếp theo của mạng hình tròn) đối với j+1 của thuật toán QR. Từ khi giải song song tam giác đã được nghiên cứu rộng rãi với nhiều kết quả hợp lý, chúng ta sử dụng đơn giản một phiên bản đã hiệu chỉnh của phương pháp giải tam giác mà Coleman và Li [10] đã đề xuất dựa trên cơ sở kỹ thuật mạng hình tròn và giả thiết rằng ma trận cột được phân cho những nút trong trong hình khép kín . Khi chúng ta làm theo phương pháp hướng hàng, chúng ta cải biên phương pháp giải tam giác theo hướng cột thành hướng hàng. Thủ tục song song giải tam giác theo hướng hàng đã thảo luận bằng thuật toán 3.6. Trong thủ tục này, chúng ta giải hệ phương trình tam giác trên Ux = b, với n hàng của ma trận U được phân phối cho p nút trong hình khép kín. Chúng ta quy cho nút chứa dòng i là P(i). Vì vậy, đúng với sự phân công khép kín, P(i) = P(k) nếu và chỉ nếu i = k mod p. Quy trình của thuật toán thật đơn giản: Mảng XSUB chứa (p-1) nghiệm bộ phận [xi , xi + 1,…, xi + p-2] đi vòng quanh hình tròn, từ P(i) đến P(i –1) với i = n down to 1. Vừa mới đến tại P(i), x(i) đã được xác định, XSUB thay đổi vị trí và gửi đến nút P(i-1) và cuối cùng P(i) trừ Ulk xk từ bl với mỗi l < i sao cho P(l) = P(i) và mỗi k sao cho xk thuộc XSUB. Trong thủ tục danh sách được ghi cuối cùng, nếu chỉ số ra ngoài phạm vi thì quay lại giá trị giả định là 0 (zero); tất cả các biến số ban đầu đều 0. Chú ý: Câu lệnh trong dấu ngoặc vuông của thủ tục cho biết địa chỉ gián tiếp. Chẳng hạn, b[1: nrows] nghĩa là tại hầu hết nrows thành phần của vectơ b trên nút này nhưng không cần thiết là nrows đầu tiên của n thành phần vectơ b. Trong trường hợp đặc biệt, thành phần thứ n của vectơ b được phân cho những nút trong ánh xạ đóng phù hợp với những hàng được phân công. Trong nhiều thủ tục, những thành phần được quy trực tiếp. Chẳng hạn, b(i) quy cho thành phần thứ i của n thành phần vector b, nhưng không phải là thành phần thứ i của mảng b[1: m] trên nút này. Thuật toán 3.8. Thuật toán song song giải tam giác theo hướng hàng Procedure PRTS(XSUB[1 : p-1], b[1 : nrows], U([1 : nrows], 1 : n)) For i = n downto 1 do If processid = P(i) then If i < n then Receive XSUB(1: p - 1) EndIf b(i) ¬ b(i) – U(i, i + 1: i + p – 1) ´ XSUB(1 : p – 1) b(i) ¬ b(i)/U(i, i) XSUB(2: p – 1) ¬ XSUB(1: p – 2) XSUB(1) ¬ b(i) If i > 1 then Send XSUB(1: p – 1) to nút P( i – 1) EndIf For k = i to i +p-1 do For mỗi l sao cho P(l) = processid, l < i then B(l) ¬ b(l) – U(l, k) ´ XSUB(k – i+ 1) EndFor EndFor EndIf EndFor Enddo. III.2.3.3 Giải thuật song song của bài toán phi tuyến bằng phương pháp Tensor Bây giờ chúng ta thảo luận giải thuật Tensor song song để giải hệ phương trình phi tuyến và bài toán phi tuyến bình phương nhỏ nhất trên bộ nhớ cục bộ đa xử lý. Ở đây, chúng ta trình bày ở mức khái quát của giải thuật song song Tensor và các thủ tục song song chi tiết ở phần Phụ lục. Trong mỗi nút có một tên duy nhất là một- số nằm trong phạm vi [0, p – 1] với p là số của bộ xử lý và ma trận có cột từ 1 đến n và hàng từ 1 đến m, khi đó n, m là số chiều của cột và hàng của ma trận này. Phương pháp song song bước lặp k của Newton (hoặc Gaussian-Newton) gồm song song xấp xĩ sai phân hữu hạn Jacôbi J(xk) sử dụng thuật toán JEVAL, tính toán song song gradient g(xk) sử dụng thuật toán GRAD, nhân tử hoá song song QR của J(xk) sử dụng thuật toán 3.7 với cột xoay, tính toán song song QTF(xk), giải lùi song song Rdn = -QTF(xk) sử dụng thuật toán 3.8 để thu được bước Newton (Gaussian-Newton) dn, tìm kiếm đường thẳng song song (line search) sử dụng thuật toán LSEARCH hoặc miền tin cậy song song sử dụng thuật toán TREGION để tính toán bước lặp tiếp theo xp và F(xp) và thuật toán tuần tự NLSTP để kiểm tra tiêu chuẩn kết thúc. Phương phápTensor song song tại phép lặp k bao gồm : Song song xấp xĩ sai phân hữu hạn Jacôbi J(xk) sử dụng thuật toán JEVAL, - Tính toán song song gradient g(xk) = J(xk)TF(xk) sử dụng thuật toán GRAD, Hình thành số hạng tensor A song song sử dụng thuật toán FORMT, - Sử dụng thuật toán tuần tự QLFAC để thu được nhân tử hoá QS của mảng , - Tính song song tích của J(xk) lần với ma trận Householder Q sử dụng thuật toán JMULQ, - Song song nhân tử hoá của J(xk) sử dụng thuật toán 3.7 với cột xoay từ cột 1 đến n – 1, - Tính toán song song và sử dụng thuật toán QMULV, Cực tiểu hoá song song của m-n+1 phương trình toàn phương một ẩn , nếu m = n sử dụng thuật toán SLVN hoặc nếu m > n sử dụng thuật toán SLVMN, - Giải lùi song song để thu n-1 thành phần mảng sử dụng thuật toán DSOLV, - Tính toán song song dn giống như kết quả phụ của bước tensor sử dụng thuật toán SSPROD, Tính toán tuần tự và để thu được bước tensor, Chọn tuần tự giữa bước chuẩn hoặc bước tensor sử dụng thuật toán DECIDE, Tìm kiếm đường thẳng song song sử dụng thuật toán LSEARCH hoặc miền tin cậy song song sử dụng thuật toán TREGION để tính toán bước lặp tiếp theo xp và F(xp) Và thuật toán tuần tự NLSTP để kiểm tra tiêu chuẩn kết thúc. . Bây giờ chúng tôi đưa ra giải thuật song song chủ và nút (Host and Node) bằng phương pháp Tensor sau đây: Giải thuật song song của phương pháp Tensor Giải thuật Chủ (Host) 1. Nút chủ gởi đến trạm điều khiển nút 0, Số chiều m và n của bài toán, Phương pháp để sử dụng ( method = 0 : phương pháp Newton/Gaussian-Newton, method = 1 : phương pháp Tensor ), Chiến lược toàn cục (global strategy) để sử dụng (global = 0 : Tìm kiếm đường thẳng (line search), global = 1 : Miền tin cậy hai chiều (two-dimensinal trust region), Cờ hiệu flag với ý nghĩa như sau: flag = 0 : chỉ có mã tuần tự thực hiện flag = 1 : cả mã tuần tự và song song thực hiện flag = 2: chỉ có mã song song thực hiện và cuối cùng là bắt đầu ước chừng x0 Giải thuật nút (Node) {Chú thích : Những bước yêu cầu truyền thông được ký hiệu với “*”} 2. If mynode = 0 then 2.1 Nhận dữ liệu đầu tiên từ chủ (host) 2.2 If flag = 0 then 2.2.1 Thực hiện mã tuần tự, thời gian, và gởi kết quả đến host Else If flag = 1 then 2.2.2 Thực hiện mã tuần tự, thời gian 2.2.3 Truyền dữ liệu đầu tiên Else 2.2.4 Truyền dữ liệu đầu tiên EndIf Else 2.3 Nhận dữ liệu đầu tiên từ nút 0 EndIf 3. If mynode = 0 then startime = mclock( ) 4. Mỗi nút của nó tính toán biến cục bộ của chúng nrows = é (m + p – mynode – 1)/p)ù , là số dòng của Jacôbi sẽ được phân phát cho nó mpart(i) = mynode + 1 + (i –1).p, i = 1,…,nrows là chỉ số tương ứng đối với những dòng được phân phát 5. itn = 0 6. Tính toán F(x0) trong song song. Ở đây, Bộ xử lý j tương đương với F(mpart(i)), i = 1,…, nrows 7. Tính toán sai phân hữu hạn Jacôbi J tại x0 trong song song sử dụng thuật toán JEVAL *8. Tính toán gradient g tại x0 trong song song sử dụng thuật toán GRAD {Chú thích : g kết thúc trên mọi bộ xử lý } *9. Thực hiện nhân tử hoá QRP của Jacôbi trong song song sử dụng thuật toán 3.7 w/ cột xoay (column pivoting) *10. Tính toán QTF sử dụng thuật toán QMULV *11. Thực hiện giải lùi Rdn = -QTF trong song song sử dụng thuật toán 3.8 để có được bước chuẩn dn { Chú thích : Giải dn kết thúc trên Bộ xử lý 0. Hơn nữa mỗi nút i có n-i thành phần sau cùng của dn. Khi dn cần phân phối đến tất cả các nút, nút 0 sẽ gởi thành phần dn(i), i = 1,..,nút đến nút = 1,..,p 12. If global = 0 then *12.1 Tìm phép lặp xp tiếp theo trong song song sử dụng thuật toán LSEARCH Else *12.2 Tìm phép lặp xp tiếp theo trong song song sử dụng thuật toán TREGION EndIf *13. Tính toán trong song song sử dụng thuật toán INFN {Chú thích: kết thúc trên Bộ xử lý 0} 14. Tính toán Jacôbi J tại xp trong song song sử dụng thuật toán JEVAL *15. Tính toán gradient g tại xp trong song song sử dụng thuật toán GRAD 16. If mynode = 0 then 16.1 Kiểm tra tiêu chuẩn kết thúc sử dụng thuật toán NLSTP 16.2 If termnode ¹ 0 then 16.2.1 time = mclock( ) – startime 16.2.2 Gởi kết quả đến host EndIf EndIf 17. Định hình vectơ phân phối S là nơi lưu trữ vectơ định hướng trước (có nghĩa là S = x0 – xp) 18. Định hình vectơ phân phối FV là nơi lưu trữ giá trị hàm trước (có nghĩa là FV =F( x0 )) 19. xc = xp và Fc = Fp 20. itn = itn + 1 *21. If method = 0 then thực hiện các bước 9,10, 11 22. If method = 1 then 22.1 22.2 Định hình số hạng tensor A trong song song sử dụng thuật toán FORMT 22.3 If mynode = 0 then 22.3.1 Thực hiện nhân tử hoá QL của sử dụng QLFAC *22.3.2 Truyền đi mảng n +2 chiều Else *22.3.3 Nhận mảng từ nút 0 EndIf EndIf 23. Tính toán trong song song, với Q từ nhân tử hoá QL của sử dụng thuật toán JMULQ *24. Thực hiện nhân tử hoá của từ cột 1 đến n – 1 trong song song (có nghĩa là ) sử dụng thuật toán 3.7 w/ cột xoay *25. Tính toán và trong song song sử dụng thuật toán QMULV 26. If m = n then *26.1 Tính toán nghiệm hoặc cực tiểu hoá của trong song song sử dụng thuật toán SLVN Else m > n *26.2 Tính toán cực tiểu của trong song song sử dụng thuật toán SLVMN {Chú thích: Giải quyết và số dư tensres của tensor kết thúc trên mỗi bộ xử lý} *27. Thực hiện giải lùi trong song song để có được sử dụng DSOLV *28. Tính toán bước chuẩn giống kết quả phụ của bước tensor trong song song sử dụng thuật toán SSPROD 29. If mynode = 0 then 29.1 Tính toán và 29.2 Quyết định chọn bước chuẩn hoặc tensor sử dụng thuật toán DECIDE *29.3 Truyền bước đã chọn Else *29.4 Nhận bước chọn từ nút 0 EndIf 30. If global = 0 then *30.1 Tìm phép lại tiếp theo xp trong song song sử dụng thuật toán LSEARCH ELSE *30.2 Tìm phép lại tiếp theo xp trong song song sử dụng thuật toán TREGION EndIf 31. Tính toán sai phân hữu hạn Jacôbi J tại xp trong song song sử dụng thuật toán JEVAL *32. Tính toán gradient g tại xp trong song song sử dụng thuật toán GRAD *33. Tính toán trong song song sử dụng thuật toán INFN 34. If mynode = 0 then Kiểm tra tiêu chuẩn kết thúc sử dụng thuật toán NLSTP và gởi kết quả đến host nếu termcode ¹ 0 35. If method = 1 then 35.1 FV = Fc 35.2 S = xc – xp xc = xp và Fc =Fp EndIf Go to bước 20 End. III.3 Cài đặt thử nghiệm và đánh giá kết quả. Trong phần này tập trung vào cài đặt thuật toán: giải hệ phương trình tuyến tính. Thuật toán được cài đặt thử nghiệm trên mạng LAN và sử dụng mô hình truyền thông điệp dựa trên Ethernet. III.3.1 Xây dựng chương trình cài đặt thuật toán Mỗi chương trình thực hiện bao gồm ba khối (như hình 3-2): Khối tạo lập dữ liệu cho phép người sử dụng đọc dữ liệu đầu vào từ thuật toán K-Means hoặc xác định các tham số đầu vào (Mandelbrot). Khối thực hiện thuật toán tiến hành phân cụm (thuật toán K-Means) hoặc phát sinh (Mandelbrot). Khối hiển thị kết quả hiển thị các cụm sau khi đã phân (K-means ) hoặc hiển thị sau khi phát sinh (Mandelbrot) Khối tạo lập dữ liệu Khối thực hiện thuật toán Khối hiển thị kết quả Hình 3-2 Sơ đồ thực hiện chương trình Ngôn ngữ lập trình được sử dụng để cài đặt là Java. Đây là ngôn ngữ lập trình hổ trợ nhiều kỹ thuật để kết nối và triệu gọi các đối tượng từ xa. a. Tạo lập dữ liệu Tạo lập dữ liệu có tác dụng chuẩn bị đầu vào cho các thuật toán. Để cài thuật toán Gaussian ta chỉ cần tạo ra một mảng 2-chiều a để lưu hệ số và mảng 1-chiều b để lưu vector tự do b. Cài đặt các thuật toán. Cấu trúc dữ liệu Cấu trúc dữ liệu biễu diễn trong các thuật toán là các mảng động. Ta sử dụng mảng động hai chiều để lưu trữ mảng a và mảng động một chiều b. Mô hình cài đặt chung cho thuật toán song song. Bước 1: Kết nối các máy (workstation) tham gia giải quyết bài toán Bước 2: Có bao nhiêu workstation tham gia tính toán sẽ tạo ra bấy nhiêu luồng (thread) thực hiện. Bước 3 Trên mỗi luồng ta triệu gọi các phương thức từ xa tương ứng. Trên mỗi workstation đã cài sẵn các hàm để tính toán. Máy chủ chỉ cần gọi các hàm từ xa trên các workstation tham gia tính toán. Bước 4: Tập hợp các kết quả gởi về từ các workstation. Nếu thuật toán chưa kết thúc thì máy chủ tiếp tục phân chia công việc để yêu cầu workstation tiếp tục tính toán. Java hỗ trợ các kỹ thuật để ta thực hiện các bước từ bước 1 đến bước 4 như sau: Bước 1: Ta sử dụng gói thư viện Java.net để kết nối đến các máy, bao gồm các lớp: Socket và ServerSocket: Tạo ra đường kết nối giữa các máy InetAddress : Quản lý địa chỉ Ip và tên của các máy đã kết nối. DatagramPackage và URL: để gởi hoặc nhận gói tin được truyền trên các máy đã kết nối Bước 2: Tạo các luồng. Từ bước 1 ta xác định được có bao nhiêu workstation tham gia tính toán. Sử dụng lớp java.lang.Thread và the java.lang.Runnable để tạo và quản lý các luồng. Bước 3: Triệu gọi các phương thức từ xa. Thông thường các chương trình được viết dưới dạng các hàm. Mã lệnh của hàm được nạp vào và cho thi hành ngay trên máy cục bộ. Điều mà chúng ta quan tâm là các hàm hay các đối tượng được nạp vào từ máy nào đó và gọi chúng từ máy khác. RMI (Remote Method Invoke) của Java hỗ trợ cho ta cách thức để giao tiếp giữa các đối tượng Java có mã lệnh cài đặt (bao gồm các phương thức và thuộc tính) nằm trên các máy khác nhau có thể triệu gọi lẫn nhau. Về thực tế thì đối tượng Java trên hai máy không triệu gọi lẫn nhau một cách trực tiếp mà phải thông qua máy trung gian. Lớp trung gian này tồn tại ở cả hai phía: máy khách (nơi gọi phương thức của đối tượng ở xa) và máy chủ (nơi đối tượng thực sự được cài đặt để thực thi mã lênh của phương thức). Phía máy khách lớp trung gian này được gọi là stub (lớp móc), phía máy chủ lớp trung gian này gọi là skeletion (lớp nối). Ta có thể hình dung lớp stub và skeletion là hai người môi giới giúp các đối tượng từ xa giao dịch với nhau. Trình biên dịch của Java (rmic) sẽ giúp ta tạo ra hai lớp stub và skeletion. Khi cài đặt hai thuật toán trên ta sử dụng gói java.rmi, sử dụng các phương thức: Naming.bind(): Sử dụng trên máy chủ để đăng ký đối tượng với chương trình rmiregistry đang chạy. Naming.lookup(): Sử dụng trên máy khách để yêu cầu bộ quản lý rmiregistry trên máy chủ trả về tham chiếu đến các đối tượng. Trên các máy chủ (thực chất các các workstation) ta cài đặt các lớp HelloImpl để giải quyết một phần của thuật toán bao gồm các phương thức: Đối với thuật toán Gaussian ta xây dựng hai phương thức: public double [][] tinh(double aa[][],int sd,int c,int i,int vtbd,int vtkt); aa: mảng 2-chiều chứa hệ số, cột cuối cùng của mảng aa chứa vector b sd: Số dòng cần thực hiện c: kích cỡ của mảng. i: cột cần tính. vtbd: Dòng bắt đầu cần tính trong ma trận aa. vtkt: Dòng cuối cùng cần tính trong ma trận aa. Hàm này trả về một mảng 2-chiều sau khi đã khử ở cột i, từ dòng vtbd đến dòng vtkt public double [][] tinh1(double a[][],int dong,int cot,int i) a: mảng 2-chiều chứa hệ số, cột cuối cùng của mảng aa chứa vector b dong,cot: kích cỡ của mảng . i: cột cần tính. Hàm này tính toán trên một máy và trả một mảng 2-chiều sau khi đã khử ở cột i. Bước 4. Tập hợp các kết quả gởi về từ các workstation. Sau khi các workstation hoàn thành công việc tức là mỗi workstation đã khử xong một phần của cột thứ i. Kết quả của mỗi phần sẽ gởi về Server, Server sẽ tập hợp các kết quả đó thành một mảng 2-chiều mới, sau đó tiếp tục gởi mảng này đến các workstation để khử cột i+1. Quá trình này tiếp tục đến khi đã khử hết mảng a, Server tách cột cuối cùng của mảng 2-chiều a về cho mảng mảng b và đưa ra nghiệm. III.4.2 Kết quả thực nghiệm Thuật toán trên được cài đặt thử nghiệm trên mạng LAN và sử dụng mô hình truyền thông điệp dựa trên Ethernet. Cấu hình của các Workstation như sau: CPU Memory Card mạng Pentium 4 512MB 100Mbps Kết quả thực nghiệm đo được trên thuật toán Guass trên như sau: Đầu vào: Mảng 2-chiều a và mảng 1-chiều b. Kết quả : Đo được thời gian thực hiện (tính bằng giây) trên các máy tham gia Bậc Một máy Hai máy 4x4 0.1 1.29 6x6 0.79 1.62 10x10 1.87 3.54 15x15 3.71 5.73 20x20 8 10.06 25x25 16.53 17.03 30x30 28.15 28.17 35x35 46.51 48.64 40x40 72.42 67.82 45x45 101.54 95.5 50x50 137 130.46 55x55 172.9 164.46 Từ bảng kết quả trên ta có biểu đồ so sánh giữa bậc với thời gian thực hiện như sau: Biểu đồ so sánh giữa thời gian và số chiều của ma trận. Từ dữ liệu của hai bảng trên ta có nhận xét sau: Nếu số chiều của ma trận càng nhỏ thì thời gian tính toán rất ít trong khi đó thời gian truyền thông nhiều. Do đó, một máy thì thời gian thực hiện nhanh hơn. Nếu số chiều của ma trận càng lớn thì thời gian tính toán càng lớn. Do đó, hai máy thì thời gian thực hiện nhanh hơn một máy. Thuật toán trên được cài đặt theo cách phân chia tác vụ động, vì vậy cứ máy khách tính toán xong gởi kết quả về máy chủ, máy chủ tập hợp kết quả, sau đó tiếp tục phân chi công việc và gởi yêu cầu đi. Do vậy, thời gian truyền thông rất nhiều.Ví dụ số chiều của ma trận là 51 và có hai máy tham gia tính toán, như vậy số lần truyền thông cho một máy là: 25*2=50 lần truyền thông, hai máy : 2*25*2=100 lần truyền thông. Vì vậy nếu thuật toán cài đặt trên mạng LAN thì không tối ưu vì thời gian truyền thông giữa các máy lớn, nếu cài trên máy tính song song thì hiệu quả rất cao. KẾT LUẬN Qua thời gian nghiên cứu và thực hiện luận văn, chúng tôi đã được một số kết quả nhỏ sau đây: Nắm được cách tổ chức và kiến trúc máy tính song song, các mô hình lập trình song song Nghiên cứu các nguyên lý, các cách tiếp cận để thiết kế thuật toán song song, các phương pháp biến đổi nhằm loại bỏ các phụ thuộc dữ liệu để chuyển từ một chương trình tuần tự về chương trình song song. Thông qua đó, chúng tôi đã phân tích và đánh giá được thuật toán song song …. Khảo sát và chuyển đổi một số thuật toán từ môi trường tuần tự sang môi trường song song. Cài đặt thử nghiệm thuật toán giải hệ phương trình tuyến tính trên môi trường mạng LAN với mô hình truyền thông điệp. Hướng phát triển của luận văn: Giải quyết triệt để các bài toán đặt ra, có thể xây dựng và phát triển giải thuật song song cho nhiều lớp bài toán phi tuyến khác nữa. Xác định ngưỡng của chương trình, tức là đối với mỗi thuật toán cần bao nhiêu bộ xử lý là tốt nhất Nếu có đầy đủ cơ sở vật chất nên thử nghiệm thuật toán trên các cấu trúc song song khác nhau, trên cơ sở đó mới có những nhận xét và đánh giá chính xác về thuật toán khi thực hiện trên mỗi loại kiến trúc song song này.