TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG VÀO BÀI TOÁN TỔ HỢP

Lý do chọn đề tài

Toán học tổ hợp là một ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hợp hữu hạn phần tử. Toán tổ hợp có liên quan đến rất nhiều lĩnh vực khoa học như đại số, xác xuất, thống kê, hình học, vật lý thông kê và đặt biệt được ứng dụng nhiều trong ngành khoa học máy tính. Các bài toán cơ bản của toán tổ hợp là cơ sở phát triển các thuật toán cho bài toán sắp xếp, phân rã, hoán vị. Thế nhưng các bài toán tổ hợp thường là các bài toán có độ phức tạp cao, khối lượng tính toán lớn và thời gian tính toán khá dài gây ra những khó khăn cho việc tính toán.

Xã hội hiện đại, phát triển liên tục như hiện nay đặt ra cho chúng ta nhiều vấn đề, nhiều bài toán ngày một phức tạp, nhu cầu tính toán xử lý ngày càng lớn. Việc tính toán tuần tự theo truyền thống không còn đáp ứng tốt nhu cầu lượng tính toán khổng lồ này nữa. Cùng với đó là sự phát triển của các bộ xử lý đa nhân, đa luồng có thể thực hiện đa nhiệm, đa tác vụ cùng lúc. Nhiều hệ thống máy tính lớn là sự liên kết của rất nhiều máy tính với nhau để có thể xử lý tính toán một bài toán phức tạp. Tất cả đã mở ra một thời đại mới, thời đại của tính toán song song.

Tính toán song song là một hình thức tính toán, trong đó nhiều phép tính được thực hiện đồng thời. Dựa trên nguyên tắc chính là một bài toán lớn chia thành những phần nhỏ có thể tính toán độc lập với nhau một cách đồng thời.

Tính toán song song và ứng dụng tính toán song song vào bài toán tổ hợp mang lại nhiều ý nghĩa lớn cho ngành khoa học máy tính cũng như các ngành khoa học liên quan khác. Trước đây đã có những đề tài nghiên cứu về tính toán song song cũng như nghiên cứu về bài toán tổ hợp, nhưng chỉ là những nghiên cứu tách biệt và việc nghiên cứu ứng dụng tính toán song song vào bài toán tổ hợp vẫn chưa thực sự được quan tâm theo đúng sự quan trọng của nó. Thế nên tôi, được sự đồng ý của cán bộ hướng dẫn, lựa chọn đề tài này để làm luận văn.

Mục tiêu nghiên cứu

Nghiên cứu tính toán song song và bài toán tổ hợp.
Đề xuất giải pháp tính toán song song để tính toán bài toán tổ hợp nhằm tăng hiệu quả tình toán, tăng hiệu suất tính toán trên máy tính, hỗ trợ tính toán cho các lĩnh vực khác có liên quan.
Thử nghiệm các giải pháp trên môi trường java với thư viện Thread tính toán song song song.

Đối tượng và phạm vi nghiên cứu

Đối tượng:

Nghiên cứu lý thuyết tính toán song song, các mô hình máy tính, các mô hình tính toán song song, các bước để xây dựng thuật toán song song, các phương pháp phân rã bài toán.
Các bài toán tổ hợp: Dãy bị chặn, tập con, hoán vị của tập hợp.
Ứng dụng tính toán song song vào bài toán tổ hợp, thử nghiệm trên môi trường java với thư viện Thread.

Phạm vi nghiên cứu:

Đề xuất giải pháp thuật toán tính toán song song trên bài toán tổ hợp.
Lập trình ứng dụng tính toán song song vào bài toán tổ hợp bằng thư viện Thread để thử nghiệm thuật toán.

Phương pháp nghiên cứu

Phương pháp nghiên cứu tài liệu
Phương pháp phân tích
Phương pháp tổng hợp
Phương pháp thực nghiệm nêu ví dụ

Ý nghĩa khoa học và thực tiễn của đề tài

Luận văn trình bày lý thuyết tính toán song song, các mô hình tính toán song song, cách xây dựng thuật toán song song, cách phân tách bài toán phân rã để thực hiện song song và các bài toán tổ hợp. Từ đó đề xuất các giải pháp tính toán bằng phương pháp song song cho bài toán tổ hợp tăng hiệu xuất tính toán cho các máy tính. Thử nghiệm thực tiễn trên môi trường Java sử dụng thư viện Thread.

TỔNG QUAN TÍNH TOÁN SONG SONG

. Tính toán song song và các mô hình tính toán song song

. Mô hình SISD (Single Intruction, Single data):

. Mô hình SIMD (Single Intruction, Multiple data):

. Mô hình MISD (Multiple Intruction, Single data):

. Mô hình MIMD (Multiple Intruction, Multiple data):

. Mô hình máy tính PRAM

. Thuật toán song song

Việc xây dựng, thiết kế một chương trình tính toán song song từ một thuật toán tuần tự đã có chúng ta cần trải qua 4 giai đoạn là: phân rã, truyền thông, tích tụ và ánh xạ.

Phân rã: Là công việc sau khi đã xác định và phân tích bài toán. Các công việc tính toán cũng như các nguồn dữ liệu đầu vào, đầu ra được phân rã thành nhiều tác vụ. Từ đó phân tích từng tác vụ và tìm ra các tác vụ có thể tính toán độc lập với nhau về dữ liệu đầu ra, đầu vào hoặc độc lập về cách tính toán…

Truyền thông: là công đoạn thể hiện các tác vụ qua từng luồng thông tin sao cho các luồng đó có thể thực hiện độc lập, đồng thời. Tính toán thực hiện một tác vụ kèm theo những dữ liệu đầu ra, đầu vào. Sau đó được truyền giữa các tác vụ để thực hiện tính toán.

Tích tụ: giai đoạn này sẽ gom các tác vụ đã phân rã ở trên thành những tác vụ lớn hơn giúp giảm chi phí truyền thông nhưng cũng gây ra việc giảm tiềm năng thực hiện đồng thời.

Ánh xạ: là giai đoạn cuối cùng, mỗi tác vụ sẽ được ấn định vào một bộ xử lý nào đó để tiến hành việc tính toán.

. Quy trình xây dựng thuật toán song song

Thuật toán song song là tập các tiến trình hoặc các tác vụ thực hiện đồng thời có thể trao đổi dữ liệu với nhau kết hợp cùng giải quyết một vấn đề lớn. Để thiết kế được thuật toán song song, ta cần quan tâm đến các nguyên lý thiết kế sau:

Nguyên lý tập lịch: Tạo lịch trình để giảm tối thiểu bộ xử lý sử dụng nhưng vẫn giữ không tăng thời gian tính toán theo độ phức tạp.
Nguyên lý hình ống: Thực hiện khi bài toán xuất hiện một dãy các thao tác {T1,T2,…Tn} trong đó Ti+1 thực hiện sau khi Ti kết thúc.
Nguyên lý chia để trị: Chia bài toán thành nhiều phần nhỏ hơn có tính độc lập với nhau để thực hiện song song.
Nguyên lý đồ thị phụ thuộc dữ liệu: phân tích mối quan hệ giữ các dữ liệu để xây dựng đồ thị phụ thuộc dữ liệu từ đó xác định đúng được dữ liệu ra vào trong từng phần của thuật toán song song.
Nguyên lý điều kiện tương tranh: Nếu nhiều tiến trình cũng muốn truy xuất vào cùng một vùng dữ liệu thì cần xem xét điều kiện tương tranh, các tiến trình đó có cản trở nhau hay hay không.

Ngoài ra chúng ta cũng cần chú ý thuật toán song song phải được thiết kết dựa trên những kiến thức về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán.

TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG VÀO BÀI TOÁN TỔ HỢP

. Nguyên lý thiết kế thuật toán song song

Nguyên lý tập lịch: Tạo lịch trình để giảm tối thiểu bộ xử lý sử dụng nhưng vẫn giữ không tăng thời gian tính toán theo độ phức tạp.

Nguyên lý hình ống: Thực hiện khi bài toán xuất hiện một dãy các thao tác {T₁,T₂,…T_n} trong đó T_i+1 thực hiện sau khi T_i kết thúc.

Nguyên lý chia để trị: Chia bài toán thành nhiều phần nhỏ hơn có tính độc lập với nhau để thực hiện song song.

Nguyên lý đồ thị phụ thuộc dữ liệu: phân tích mối quan hệ giữ các dữ liệu để xây dựng đồ thị phụ thuộc dữ liệu từ đó xác định đúng được dữ liệu ra vào trong từng phần của thuật toán song song.

Nguyên lý điều kiện tương tranh: Nếu nhiều tiến trình cũng muốn truy xuất vào cùng một vùng dữ liệu thì cần xem xét điều kiện tương tranh, các tiến trình đó có cản trở nhau hay hay không.

. Các cách tiếp cận trong thiết kế

Trong tính toán song song ta có ba cách tiếp cận để thiết kế:

Thực hiện song song hóa từ những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý.

Thiết kế những thuật toán song song cần phải phù hợp với các kiến trúc song song.

Xây dựng những thuật toán song song từ những thuật toán song song có trước cho phù hợp với điều kiện và môi trường song song thực tế.

. Phân rã

. Phân rã đệ quy

. Phân rã dữ liệu

. Phân rã thăm dò

. Phân tích và đánh giá thuật toán song song

Mức độ tăng tốc của thuật toán song song sử dụng p bộ xử lý được xác định như sau: S_p = T_S/T_p

Trong đó,

T_S là thời gian thực hiện tính toán trên một bộ xử lý

T_p là thời gian thực hiện tính toán trên p bộ xử lý.

Thời gian thực hiện song song, ký hiệu là t_p gồm hai phần t_comp và t_comm.

t_p = t_comp + t_comm

Trong đó, t_comp là thời gian tính toán và t_comm thời gian truyền thông dữ liệu.

TOÁN HỌC TỔ HỢP

. Tập hợp và các nguyên lý cơ bản

. Tập hợp

. Các nguyên lý cơ bản

. Các cấu hình tổ hợp

. Chỉnh hợp

. Tổ hợp

. Hoán vị

. Bài toán liệt kê

. Các phương pháp liệt kê

. Liệt kê từ điển

. Phương pháp sinh

. Các bài toán liệt kê thường gặp

. Dãy bị chặn

Ký hiệu Z là tập các số nguyên. Cho n là một số nguyên dương nào đó, giả sử p và q là 2 dãy số nguyên có độ dài n và ký hiệu như sau:

p=( p₁p₂…p_n), q=(q₁q₂…q_n)| p_i, q_i ∈ Z, ∀i ∈ 1, …, n

Ta có định nghĩa sau:

p ≤ q khi và chỉ khi p_i ≤ q_i ∀i∈ (1 … n)
p < q khi và chỉ khi ∃ j∈ (1 … n) : p_j<q_j và p_i ≤q_i : ∀i∈ (1 … n) và i≠j

Bài toán dãy bị chặn được phát biểu như sau:

Cho hai dãy số nguyên s và g có độ dài n, sao cho s < g, hãy tìm tất cả các dãy số t độ dài n sao cho s ≤ t ≤ g.

Giả sử s=(s₁s₂… s_n) và g=(g₁g₂…g_n), hai dãy này được gọi là các dãy biên. Các dãy cần tìm t=(t₁t₂… t_n) phải thỏa mãn:

t_i ∈ Z ⋀ S_i ≤ t_i ≤ g_i ∀ i ∈ (1 … n) (1)

Định lý 1: Cho s=(s1 s2…s_n) và g=(g1 g2…g_n) là hai dãy biên. Các dãy t=(t₁t₂…t_n) là dãy bị chặn. gọi C là số lượng các dãy t. Khi đó ta có:

C= (2)

Chứng minh:

Ta có: ở vị trí đầu tiên t₁ có thể chọn một trong các giá trị s₁, s₁+1, s₁+2, …, g₁. Nên thành phần t₁ có g₁-s₁+1 cách chọn.

Tương tự như vậy, thành phần t₂ có g₂-s₂+1 cách chọn, thành phần n có g_n-s_n+1 cách chọn. Tương tự lập luận cho t_i với i=1..n kết hợp với nguyên lý nhân ta có số lượng các dãy của t là C=(g₁-s₁+1)x(g₂-s₂+1)x…x(g_n-s_n+1)=

. Bài toán tập con

. Hoán vị n phần tử

. Bài toán phân hoạch

ỨNG DỤNG TÍNH TOÁN SONG SONG VÀO BÀI TOÁN TỔ HỢP

. Bài toán sinh dãy bị chặn

. Xây dựng thuật toán tuần tự:

Thuật toán 1: sinh tất cả dãy bị chặn

BEGIN
Nhập n, s[i], g[i], i=1,…,n //s, g là hai biên nhỏ nhất và lớn nhất
t[i]:=s[i], i=1,…,n
Repeat
Print t[i], i=1,…,n
i:=n;
While t[i] =g[i] do
Begin
t[i]:=s[i];
i:=i-1;
End;
If i>=1 then t[i]:=t[i]+1;
Untill i=0
END

Độ phức tạp của thuật toán sinh tất cả dãy bị chặn này xấp xỉ bằng O(n*aⁿ) với a = max {(g₁-s₁+1),(g₂-s₂+1),…,(g_n-s_n+1)}.

. Xây dựng thuật toán song song:

Ta xây dựng thuật toán tính toán song song tìm tất cả các dãy bị chặn n phần tử với cách chọn k=(g₁-s₁+1)*(g₂-s₂+1),…,(g_p-s_p+1) là tổng số bộ xử lý của chương trình (1<p<n) như sau:

Thuật toán 2: song song sinh tất cả dãy bị chặn

Begin
Nhập n, p (p∈ {2,3, … , n − 1})
Nhập s[i] và g[i], i = 1, … , n
k=(g₁-s₁+1)*(g₂-s₂+1)*…*(g_p-s_p+1); p=(2, 3,…,n-1) //k là số bộ xử lý
//Bộ xử lý đầu tiên tìm k đoạn con, rồi phân cho các bộ xử lý khác

Begin

//tìm dãy bị chặn theo thuật toán 1 và gửi dữ liệu đến các bộ xử lý

1. s’[i]=s[i], i=1,…,p
2. g’[i]=g[i], i=1,…,p
3. c_j:=Sinh dãy bị chặn(s’(i), g’(i)), j=1,…,k //theo thuật toán 1.
4. Gửi s[i] ở bước 3 đến tất cả bộ xử lý phụ
5. Gửi (c_j đến p_j (j=1,…,k)
6. Gửi g[i] ở bước 3 đến tất cả các bộ xử lý phụ

End;

// k bộ xử lý phụ thực hiện đồng thời,

Begin

1. Nhận dữ liệu
2. Tạo s_j bằng cách chèn các phần tử s[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
3. Tạo g_j bằng cách chèn các phần tử g[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
4. t_j[i]:=Sinh dãy bị chặn (s_j(i), g_j(i)), j=1,…,k, i=1,…,n //theo thuật toán 1.
5. In kết quả
6. Gửi thông tin về bộ xử lý chính.

End;

End.

. Bài toán tìm tập con

. Xây dựng thuật toán tuần tự

Thuật toán 3: tìm tập con

Begin
Nhập n và tập hợp X ={x₁ x₂… x_n}
s[i]:=0, i = 1, … , n
g[i]:=1, i = 0, … , n
Thuật toán 1 sinh tất cả các dãy số bị chặn t thỏa s ≤ t ≤ g
Thuật toán 4 chuyển các dãy số bị chặn t thành các tập hợp con của X
End

Thuật toán 4: chuyển các dãy bị chặn t thành các tập con X

Begin
t:=(t₁t₂…t_n) //t dãy nghịch thế ngược đã được sinh ra ở trên
Khởi tạo danh sách L = ϕ
For i=0 to n do
If t_i=1 then chèn phần tử x_i vào dãy L
X₁:=L //s là 1 tập con của X
End.

Áp dụng công thức (2) của định lý 1 cho 2 dãy biên s_i và g_i ta có độ phức tạp của thuật toán xấp xỉ = 2ⁿ.

. Xây dựng thuật toán song song

Thuật toán 5: song song tìm tập con của tập có n phần tử

Begin
Nhập n, p (p∈ {2,3, … , n − 1})
s[i]:=0, i = 1, … , n
g[i]:=1, i = 1, … , n
k:=2^p; p=(2, 3,…,n-1) // k là số bộ xử lý
//Bộ xử lý đầu tiên tìm k đoạn con, rồi phân cho các bộ xử lý khác

Begin

//tìm dãy bị chặn theo thuật toán 1 và gửi dữ liệu đến các bộ xử lý

1. s’[i]=s[i], i=1,…,p
2. g’[i]=g[i], i=1,…,p
3. c_j:=Sinh dãy bị chặn(s’(i), g’(i)), j=1,…,k //theo thuật toán 1.
4. Gửi s[i] ở bước 3 đến tất cả bộ xử lý phụ
5. Gửi (c_j đến p_j (j=1,…,k)
6. Gửi g[i] ở bước 3 đến tất cả các bộ xử lý phụ

End;

// k bộ xử lý phụ thực hiện đồng thời,

Begin

1. Nhận dữ liệu
2. Tạo s_j bằng cách chèn các phần tử s[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
3. Tạo g_j bằng cách chèn các phần tử g[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
4. t_j[i]:=Sinh dãy bị chặn (s_j(i), g_j(i)), j=1,…,k, i=1,…,n //theo thuật toán 1.
5. Chuyển tất cả các dãy bị chặn t_j[i] thành các tập con theo thuật toán 4.
6. In kết quả
7. Gửi thông tin về bộ xử lý chính.

End;

End.

. Ví dụ minh họa tìm tất cả tập con con của tập có 4 phần tử

. Phân tích

Với cách chọn số bộ xử lý k=2^p (1<p<n)

Vì các dãy bị chặn con cho từng bộ xử lý tạo ra bằng cách lấy p phần tử đầu trong dãy nhị phân ban đầu và thêm 0 vào cho đủ n phần tử nên các dãy chặn con điều nằm trong khoản từ s=(0…0) và g=(1…1) (n phần tử).

Số dãy bị chặn tại mỗi bộ xử lý phụ là 2^n-p dãy. Đồng thời số bộ xử lý là k=2^p nên ta có tổng số dãy con tạo ra là 2^p * 2^n-p=2ⁿ dãy.

Vậy độ phức tạp của thuật toán 5 song song tìm tập con của tập có n phần tử xấp xỉ 2^n-p +T với T là thời gian truyển thông giữa các bộ xử lý. T phụ thuộc vào từng hệ thống vật lý thực tế.

. Bài toán liệt kê hoán vị

. Phép thế, nghịch thế

Một phép thế σ trên tập X_n được gọi là một chuyển trí hai phần tử i, j thuộc X_n nếu σ(i) = j, σ(j) = i và σ(k) = k, với mọi k ∈ X_n, k ≠ i, k ≠ i.

Giải sử tập hợp X_n = {1,2,3,..,n}, (n>1) Một song ánh σ: X_n→X_n được gọi là phép thế trên tâp X_n. Tập tất cả các phép thế ký hiệu là S_n.

Phép thế σ: X_n→ X_n được biểu diễn như sau:

Trong đó, σ(i) là ảnh của phần tử i ∈ X_n được viết ở dòng dưới, trong cùng một cột với i.

Như vậy, ảnh của các phần tử của tập X_n qua mỗi phép thế cho ta một hoán vị trên tập X_n. Nguợc lại, mỗi hoán vị lại xác định một phép thế, chẳng hạn, hoán vị. Vì vậy, số các phép thế trên tập X_n bằng số các hoán vị trên tập X_n, nghĩa là bằng n!. Như vậy, tập S_n có n! phần tử.

Phép nghịch thế được hiểu như sau: Giả sử một phép thế trên tập X_n. Với i, j ∈ X_n, i ≠ j, ta nói cặp (σ(i), σ(j)) là một nghịch thế của σ nếu i <j nhưng σ(i) > σ(j).

Vậy trên tâp X_n có n phần tử và có n! phép thế, ứng với mỗi phép thế ta có số nghịch thế khác nhau. Ta gọi dãy nghịch thế như sau: Dãy nghịch thế là dãy gồm số nghịch thế tại tại từng phần tử trong phép thế nhất định.

. Xây dựng thuật toán tuần tự

Định lý 2: Cho hai dãy biên s=(0…0) (có n phần tử 0) và g=(0 1 2…n-1). Các dãy số bị chặn t thỏa là dãy nghịch thế ngược của tập X_n= {1, 2, 3,…, n}, ( ). Số dãy t bằng n! nghịch thế ngược s=(0…0) tương ứng với hoán vị (1 2 …n); nghịch thế ngược g=(0 1 2 …n-1) tương ứng với hoán vị (n n-1… 1).

Chứng minh: Cho X_n= {1, 2, 3,…, n}, ( ). Hoán vị đầu tiên là (1 2 3 …n).

Ta thấy trước 1 không có gặp ngịch thế nào nên số nghịch thế của 1 bằng 0, trước 2 không có gặp ngịch thế nào nên số nghịch thế của 2 bằng 0, tương tự như vậy số nghịch thế của 3, 4,…,n đều bằng 0. Suy ra, dãy nghịch thế ngược ứng với hoán vị đầu tiên là (0…0) (có n phần tử 0).

Hoán vị cuối cùng của X_n theo từ điển tăng dần là (n n-1….1). Ta nhận thấy rằng trước n không có gặp ngịch thế nào nên số nghịch thế của n bằng 0, trước n-1 có 1 gặp ngịch thế nên số nghịch thế của n-1 bằng 1, tương tự như vậy ta có số nghịch thế của (n-2 n-3…1) tăng dần lên một đơn vị (2 3…n-1). Suy ra, dãy nghịch thế ứng với hoán vị (n n-1…1) là (n-1…0). Từ đó ta tiếp tục suy ra dãy nghịch thế ngược ứng với hoán vị (n n-1…1) là 01…n-1.

Từ hoán vị (1 2 …n) đến (n n-1…1) có n! hoán vị nên từ dãy nghịch thế ngược (0…0) đến (0 1 … n-1) cũng có n! dãy bị chặn t.

Thuật toán 6: liệt kê hoán vị

Begin
Nhập n
s[i]:=0, i = 1, … , n
g[i]:=i, i = 0, 1, … , n − 1
Thuật toán 1 sinh tất cả các dãy số bị chặn t là dãy nghịch thế ngược của tâp X_n (thỏa s ≤ t ≤ g)
Thuật toán 7 chuyển các dãy số bị chặn t (dãy nghịch thế ngược) thành các dãy hoán vị
End

Thuật toán 7: chuyển dãy bị chặn thành dãy hoán vị

Begin
t:=(t₁t₂…t_n) // t dãy nghịch thế ngược
Khởi tạo danh sách L có một phần tử có giá trị n
For i=2 to n do
If t_i=0 then chèn phần tử có giá trị n+1-i vào trước L
Else if t_i=len(L) then chèn n+1-i vào sau L
Else chèn phần tử có giá trị n+1-i vào vị trí ti+1 trong L
s:=L //s là dãy hoán vị
End.

Trong thuật toán chuyển dãy bị chặn thành hoán vị ta thấy việc chuyển dãy bị chặn chỉ là duyệt từng phần tử trong dãy t nên có độ phức tạp xấp xỉ bằng O(n).

Vậy độ phức tạp của Thuật toán 6: liệt kê hoán vị là O(n*aⁿ) với a = max {(g₁-s₁+1),(g₂-s₂+1),…,(g_n-s_n+1)}.

. Xây dựng thuật toán song song:

Xét thấy dãy bị chặn là dãy gồm có n chữ số và số lượng dãy con của dãy bị chặn là n! thế nên việc lựa chọn k như sau k = p! với 1<p<n (vì tính toán song song cần ít nhất 2 bộ xử lý).

Thuật toán 8: song song liệt kê hoán vị

Begin
Nhập n, p (p∈ {2,3, … , n − 1})
s[i]:=0, i = 1, … , n
g[i+1]:=i, i = 0, 1, … , n− 1
k:=p!; p=(2, 3,…,n-1) // k là số bộ xử lý
//Bộ xử lý đầu tiên tìm k đoạn con, rồi phân cho các bộ xử lý khác

Begin

//tìm dãy bị chặn theo thuật toán 1 và gửi dữ liệu đến các bộ xử lý

1. s’[i]=s[i], i=1,…,p
2. g’[i]=g[i], i=1,…,p
3. c_j:=Sinh dãy bị chặn(s’(i), g’(i)), j=1,…,k //theo thuật toán 1.
4. Gửi s[i] ở bước 3 đến tất cả bộ xử lý phụ
5. Gửi (c_j đến p_j (j=1,…,k-1)
6. Gửi g[i] ở bước 3 đến tất cả các bộ xử lý phụ

End;

// k bộ xử lý phụ thực hiện đồng thời,

Begin

1. Nhận dữ liệu
2. Tạo s_j bằng cách chèn các phần tử s[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
3. Tạo g_j bằng cách chèn các phần tử g[i] vào bên phải của c_j (j=1,…,k) //j là chỉ số của k bộ xử lý phụ
4. t_j[i]:=Sinh dãy bị chặn (s_j(i), g_j(i)), j=1,…,k, i=1,…,n //theo thuật toán 1.
5. Chuyển các dãy bị chặn t_j[i] thành các dãy hoán vị theo thuật toán 7
6. In kết quả
7. Gửi thông tin về bộ xử lý chính.

End;

End.

. Ví dụ minh họa cho thuật toán:

. Ví dụ 1: tìm tất cả các hoán vị của dãy s có 3 phần tử

. Ví dụ 2: tìm tất cả các hoán vị của dãy s có 4 phần tử

. Chứng minh thuật toán song song là đúng

Trước tiên, các dãy biên s_j và g_j trên k-1 bộ xử lý phụ thỏa công thức dãy bị chặn (1) t_i∈ Z ⋀ s_i ≤ t_i ≤ g_i ∀i ∈ (1 … n), có nghĩa là s_j và g_j nằm trong dãy bị chặn với dãy biên nhỏ nhất là s[i]:=0, i = 1, … , n và dãy biên lớn nhất g[i+1]:=i, i = 0, 1,…, n−1. Thật vậy, s_j,g_j tính được nhờ bước 7.2, 7.3 trong thuật toán song song bằng cách chèn thêm các phần tử 0 vào trước và p, p+1, n-1 vào bên phải c_j nên g_j[i] ≤ g[i], i=1,…, n. Còn s_j+1có được dựa vào c_j+1 nên ta luôn có s[i] ≤ s_j[i], i=1,..,n. Như vậy, s_j và g_j thỏa công thức (1) với 2 dãy biên s[i] và g[i], i=1,…,n.

Tiếp theo, ta chứng minh tổng số dãy bị chặn trên k-1 bộ xử lý phụ là n!. Khi chọn p (p∈ {2, 3, … , n−1}) thì số bộ xử lý phụ tham gia tìm các dãy bị chặn là k’=k-1=p! (các bộ xử tìm các dãy nghịch thế là đều nhau). Theo cách tính định lý 1, số lượng dãy bị chặn là C= thì số lượng các dãy bị chặn của đoạn 1 mà bộ xử lý p₁ tính là Mỗi bộ xử lý phụ còn lại cũng sẽ tìm số lượng các dãy bị chặn bằng với bộ xử lý p₁, nghĩa là bằng:

Áp dụng công thức (2) của định lý 1 cho 2 dãy biên s_j và g_j ta có số lượng các dãy bị chặn tương ứng với mỗi bộ xử lý phụ là:

=(p+1)*(p+2)*….* n.

Mặt khác, ta lại có số bộ xử lý phụ k’=k-1=p! nên ta có số lượng các dãy bị chặn tên k-1 bộ xử lý phụ là:

(k-1) !*(p+1)*(p+2)*….* n = p!*(p+1)*(p+2)*….* n = n!

Như vậy, ta có số lượng các dãy bị chặn trên k-1 bộ xử lý phụ là n! tương đương với n! hoán vị. Suy ra thuật toán song song đúng với hoán vị n phần tử là n!.

Theo cách chứng minh thuật toán song song là đúng thì khi chia cho k-1 bộ xử lý phụ thì độ phức tạp tính toán của thuật toán song song là (n * bⁿ)/ (k-1) với b=. Vậy độ phức tạp của thuật toán song song là (n * bⁿ)/ (k-1) +T, với b= và T là thời gian truyển thông giữa các bộ xử lý. T phụ thuộc vào từng hệ thống vật lý thực tế.

THỬ NGHIỆM VỚI THƯ VIỆN THREAD

. Thread

. Giới thiệu chung

. Các hàm trong thư viện Thread

. Cơ chế Socket

. Lập trình thử nghiệm tìm tập con

Bảng 4.1. Kết quả thời gian tính toán tuần tự và song song

Số lượng phần tử n=	Thời gian tính toán tuần tự (t)	Tính toán song song
		2 bộ xử lý			4 bộ xử lý
		Thời gian trao đổi dữ liệu (t2_td)	Thời gian tính toán	Tổng thời gian (t2)	Thời gian trao đổi dữ liệu (t4_td)	Thời gian tính toán	Tổng thời gian (t4)
20	2084	2650	1358	4008	3356	660	4016
21	4304	3768	2259	6027	2702	1321	4023
22	8811	2719	5304	8023	3228	2788	6016
23	20087	2379	11688	14067	3838	10171	14009
24	42621	1724	34284	36008	5305	24715	30020
25	91399	2231	59798	62029	4434	53926	58360

Biểu đồ 4.1. Biểu đồ thời gian tính toán tuần tự, tính toán song song

. Lập trình thử nghiệm bài toán tìm hoán vị n phần tử

Bảng 4.3. Kết quả thử nghiệm tính toán song song

Số lượng phần tử n=	Thời gian tính toán tuần tự (t)	Tính toán song song
		2 bộ xử lý			6 bộ xử lý
		Thời gian trao đổi dữ liệu (t2_td)	Thời gian tính toán	Tổng thời gian (t2)	Thời gian trao đổi dữ liệu (t6_td)	Thời gian tính toán	Tổng thời gian (t4)
8	72	1796	37	1833	3967	51	4018
9	382	1793	219	2012	3921	104	4025
10	3919	2407	2108	4515	3266	1048	4314
11	49275	2342	29078	31420	3574	19130	22704
12	662828	2020	367128	369148	4123	289151	293274

Hình 4.1 Biểu đồ so sánh thời gian tính toán giữa hai thuật toán

Qua biểu đồ ta có những nhận xét sau:

Thời gian tính toán tuần tự là cao hơn so với tổng thời gian tính toán song song trên cùng một bài toán. Khi số lượng phần tử tăng, bài toán dần phức tạp thì khoảng cách tính toán song song và tính toán tuần tự tăng dần.
Trong tính toán song song, thời gian trao đổi dữ liệu với cùng số bộ xử lý là tương đối đều nhau. Chỉ tăng khi ta tăng số bộ xử lý. Số bộ xử lý càng cao thì thời gian trao đổi dữ liệu càng lớn.
Trong tính toán song song, khi số bộ xử lý tăng thời gian tính toán giảm.
Với giá trị số lượng phần tử lớn thì thời gian trao đổi dữ liệu giữa các bộ xử lý là không đáng kể.

TỔNG KẾT

. Kết luận

Suốt quá trình lịch sử, máy tình càng ngày càng phát triển. Từ những chiếc máy tính cồng kềnh với tốc độ xử lý chậm, khả năng tính toán kém thì giờ đây các bộ xử lý đã rất nhỏ gọn, tiện dụng với tốc độ xử lý nhanh, khả năng tính toán vượt qua rất nhiều lần bộ não của con người. Sự phát triển của các bộ xử lý là nền móng cho các ứng dụng hoạt động bên trên. Các thiết bị ngoại vi, cũng như thiết bị lưu trữ, bộ nhớ và tốc độ xử lý… cải tiến, phát triển mạnh mẽ của đã giúp cho công việc lập trình trở nên dễ dàng hơn, thuận lợi hơn. Các giả thiết của lý thuyết toán học dần trở nên khả thi, các lĩnh vực nghiên cứu thuật toán và triển khai thực tế cũng thực tế hơn. Và tính toán song song cũng là một trong những bước ngoặc của khoa học máy tính cũng như toán học. Bằng việc phân rã bài toán thành các bài toán nhỏ hơn để xử lý đồng thời, tính toán song song đã cải thiện được tốc độ xử lý một các đáng kể. Qua đó nó giải quyết được các yêu cầu của xã hội đặt ra.

Thế nhưng ngày nay khi xã hội đang phát triển ở mức cao, cũng như cuộc cách mạng công nghiệp 4.0 đang lan tỏa, con người ta hướng đến việc vạn vật kết nối, trí tuệ nhân tạo, dữ liệu lớn,… Cách mạng 4.0 vừa là cơ hội để phát triển vừa là thách thức cho cả nhân loại. Những tính toán khổng lồ được đặt ra với yêu cầu thời gian nghiệm ngặt. Qua lịch sử sử phát triển và thực tại cho thấy tính toán song song vẫn là một trong những giải phát hữu hiệu. Sự phát triển, những rào càng về số lượng các bộ xử lý không còn là vấn đề nang giải nữa. Những bộ xử lý lớn chứa hàng lượng lớn các bộ xử lý phụ, hay những hệ thống kết nối hàng trăm, hàng nghìn các máy tính lại với nhau để có thể giải quyết được nhiều bài toán phước tạp với hiệu năng và hiệu xuất đáp ứng được những nhu cầu cấp thiết.

Chính bởi sức mạnh của tính toán song song, các ứng dụng thực thi trên máy tính song song đang là hướng nghiên cứu thu hút được nhiều sự quan tâm.

Đây là một đề tài có tính thực tiễn cao. Nhìn chung đề tài đã đạt được mục đích nghiên cứu đã đề ra.

. Hướng phát triển

Trong thời gian tới tôi sẽ tiếp tục nghiên cứu để áp dụng kỹ thuật phân đoạn nghiệm cho một số bài toán khác như: phân rã, lập lịch, xử lý số liệu chuỗi theo thời gian, phân lớp dữ liệu… để ứng dụng nhiều hơn vào trong toán học tổ hợp cũng như những bài toán khác. Từ đó tạo tiền đề cho một số ứng dụng có liên quan.

LIỆN HỆ:

SĐT+ZALO: 0935568275

E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN\HUYNH LE DAI NGOC