Tài liệu Nghiên cứu một số thuật giải heuristic cho bài toán pot và ứng dụng

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- Đặng Phương Nga NGHIÊN CỨU MỘT SỐ THUẬT GIẢI HEURISTIC CHO BÀI TOÁN POT VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2014 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: NCVC.PGS.TS. Lê Huy Thập Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Cây toán tử là cách thể hiện bằng đồ thị của một câu truy vấn dạng SQL (Structured Query Language) hay AQL (Algebraic Query Language). Dạng đặc biệt của cây toán tử là cây toán tử đường ống POT (Pipelined Operator Tree). POT là cây mà một số toán tử của nó có thể thực hiện song song với dữ liệu ra của toán tử này có thể là dữ liệu vào của toán tử. Trên POT, chúng ta có thể thực hiên các thao tác như cân bằng tải, lập lịch truy vấn tối ưu, thực hiện các nhát cắt cục bộ, phân phối các toán tử cho các bộ xử lí,.... được thực hiện bởi các thuật toán. Khi POT đã được xử bởi các thuật toán, thì việc thực hiện câu truy vấn tương ứng sẽ giảm tối đa thời gian truyền dữ liệu, tăng tốc độ truy cập. Đề tài nghiên cứu các thuật toán Heuristic trên POT là vấn đề chưa được nghiên cứu và chưa được ứng dụng cụ thể trong thực tế. Kết quả đạt được của đề tài có thể được ứng dụng để giải quyết các bài toán phân chia toán tử trong câu truy vấn của hệ CSDL phân tán và hệ đa xử lý phân tán. Có thể ứng dụng cho các vấn đề thực tế khác như chấm thi tuyển vào các cơ sở đào tạo, bán hàng qua mạng…. Sau một thời gian tìm hiểu những vấn đề nêu trên, tôi xin chọn đề tài “Nghiên cứu một số thuật giải heuristic cho bài toán POT và ứng dụng” làm đề tài nghiên cứu luận văn của mình. Ngoài phần mở đầu và kết luận, luận văn này gồm 3 chương: Chương 1: Trình bày tổng quan về các phương pháp phân mảnh dữ liệu và cách tái cấu trúc quan hệ, phương pháp tạo cây toán tử SQL và AQL từ các mảnh. Chương 2: Giới thiệu bài toán POT và các thuật toán trên POT, nghiên cứu các thuật toán Heuristic cho bài toán POT Chương 3: Ứng dụng tại trường THCS Gia Thanh, nhằm giảm tối đa chi phí truyền thông và tăng tốc độ truy cập giữa các vị trí mạng của trường. 2 CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1. Các phương pháp phân mảnh và khôi phục các quan hệ. 1.1.1. Các phương pháp phân mảnh Các kiểu phân mảnh cơ bản là: - Phân mảnh ngang. + Phân mảnh ngang nguyên thủy + Phân mảnh ngang dẫn xuất - Phân mảnh dọc. - Phân mảnh hỗn hợp. 1.1.1.1. Phân mảnh ngang Thông tin về CSDL cần thiết cho phân mảnh ngang. Thông tin về CSDL là thông tin về lược đồ khái niệm toàn cục của CSDL. Tức là chúng ta cần biết được cách mà quan hệ con sẽ hợp lại với nhau như thế nào. Trong mô hình quan hệ, các liên kết giữa các thực thể cũng được biểu thị bằng quan hệ. Với mục đích thiết kế phân tán, các mối liên kết cũng được mô hình hoá theo kiểu mô hình quan hệ. Theo cách này, chúng ta sẽ vẽ một đường nối có hướng từ quan hệ Parent đến quan hệ Child. Có hai loại phân mảnh ngang cơ bản là: phân mảnh ngang nguyên thuỷ và phân mảnh ngang dẫn xuất. Phân mảnh ngang nguyên thủy Phân mảnh ngang nguyên thuỷ là phân rã một quan hệ thành các tập gồm các bộ dựa trên các vị từ được định nghĩa trên quan hệ đó. Phân mảnh ngang nguyên thuỷ được định nghĩa bằng một thuật toán chọn trên các quan hệ nguồn của một lược đồ CSDL. Mảnh ngang Ri bao gồm các bộ của R được chọn ra theo công thức: Ri = 𝜎Fi(R), 1≤ i ≤ z. Trong đó Fi là công thức chọn được sử dụng để có được mảnh Ri. Chú ý rằng chúng ta xét Fi có dạng chuẩn hội, nó là một vị từ hội sơ cấp (mi). 3 Phân mảnh ngang dẫn xuất Phân mảnh ngang dẫn xuất là phân mảnh một quan hệ dựa vào các vị từ được định nghĩa trên quan hệ chủ (Parent). Phân mảnh ngang dẫn xuất là phân mảnh ngang trên quan hệ đích của một đường nối dựa theo phép toán chọn trên quan hệ nguồn của đường nối đó. Nếu cho trước một đường nối L, trong đó Nguon (L) = S và Dich (L) = R, các mảnh ngang dẫn xuất của R được định nghĩa là: Ri = R Si, 1 ≤ i ≤ Trong đó  là số lượng các mảnh được định nghĩa trên R, và Si = 𝜎Fi(S) với Fi là công thức định nghĩa mảnh ngang nguyên thuỷ Si. Các thông tin cần cho phân mảnh ngang dẫn xuất : Muốn thực hiện phân mảnh ngang dẫn xuất, chúng ta cần ba thông tin vào: tập các mảnh của quan hệ nguồn, quan hệ đích và tập các vị từ nối nửa giữa nguồn và đích Một số vấn đề phức tạp cần phải chú ý. Trong lược đồ CSDL, chúng ta hãy gặp nhiều đường nối đến một quan hệ R (ví dụ như trong hình 1.1, PhanNhiem có hai đường nối đến). Như thế có thể có nhiều cách phân mảnh ngang dẫn xuất cho R. Quyết định chọn cách phân mảnh nào cần dựa trên hai tiêu chuẩn: (1) Phân mảnh có đặc tính nối tốt hơn. (2) Phân mảnh được sử dụng trong nhiều ứng dụng hơn. 1.1.1.2.Phân mảnh dọc Cho R là một quan hệ trên tập các thuộc tính Ω = {A1, A2,…, An}. Khi đó phân mảnh dọc quan hệ R sinh ra các mảnh R1, R2,, …, Rn sao cho mỗi mảnh là một quan hệ chứa một tập con các thuộc tính cuả quan hệ R và khóa của nó. Tức là Ω sẽ được phân mảnh sao cho Ω = Ω1 ᴗ Ω2 ᴗ…. Ωn, trong đó Ri là mảnh quan hệ trên các thuộc tính Ωi, i=1…k. 4 Mục đích của phân mảnh dọc là phân chia quan hệ R thành tập các quan hệ nhỏ hơn để có nhiều ứng dụng có thể chỉ cần thực hiện trên một mảnh, điều này làm giảm đáng kể chi phí. Mảnh tối ưu là mảnh sinh ra một lược đồ phân mảnh cho phép giảm thiểu thời gian thực hiện của ứng dụng trên mảnh đó. Kỹ thuật phân mảnh dọc phức tạp hơn phân mảnh ngang, vì số lựa chọn phân hoạch rất lớn. Trong trường hợp có m thuộc tính không phải khóa chính, thì số mảnh có thể là mm. Để có được lời giải tối ưu cho bài toán phân mảnh dọc rất khó, không hiệu quả. Vì vậy vần phải sử dụng các phương pháp Heuristic cho phân mảnh dọc các quan hệ toàn cục. Có hai phương pháp Heuristic: a. Nhóm thuộc tính: bắt đầu gán mỗi thuộc tính cho một mảnh và trong mỗi bước, nối một số mảnh lại với nhau cho đến khi thỏa mãn điều kiện phân mảnh. b. Tách mảnh: bắt đầu bằng một quan hệ và quyết định cách phân chia quan hệ dựa trên hành vi truy xuất của các ứng dụng trên các thuộc tính. Ở đây chúng ta chỉ xem xét kỹ thuật tách mảnh vì nó thích hợp với phương pháp thiết kế CSDLPT từ trên xuống. Việc nhân bản các thuộc tính khóa của quan hệ toàn cục trong các mảnh là một đặc trưng của phương pháp phân mảnh dọc cho phép khôi phục quan hệ toàn cục và bảo đảm tính toàn vẹn ngữ nghĩa và làm giảm đi quá trình trao đổi dữ liệu. Vì vậy phương pháp phân mảnh dọc chỉ đề cập đến các thuộc tính không khóa. 1.1.1.3.Phân mảnh hỗn hợp Trong đa số các trường hợp, phân mảnh ngang hoặc phân mảnh dọc đơn giản cho một lược đồ CSDL không đủ đáp ứng các yêu cầu từ các ứng dụng. Trong trường hợp đó, phân mảnh dọc có thể được thực hiện sau một phân mảnh ngang hoặc ngược lại, sinh ra một lối phân hoạch có cấu trúc cây (Hình 1.3). Bởi vì, hai loại chiến lược phân hoạch này được áp dụng lần lượt, chọn lựa này được gọi là phân mảnh hỗn hợp (hybrid fragmentation). 5 1.1.2 Tái cấu trúc quan hệ 1.Tái thiết quan hệ phân mảnh ngang Tái thiết quan hệ từ các mảnh thực hiện bằng toán tử hợp trong cả phân mảnh ngang nguyên thủy lẫn dẫn xuất  một quan hệ R với phân mảnh FR = {R1, R2, R3, … Rm} ta có: R = ∪ Ri; ∀Ri ∈ FR 2. Tái thiết quan hệ phân mảnh dọc Quan hệ R có phân mảnh dọc FR = {R1, R2, R3, … Rr} và các thuộc tính khóa K R= K Ri, ∀Ri ∈ FR 3. Tái thiết phân mảnh hỗn hợp Trong phân mảnh hỗn hợp, hai loại phân mảnh ngang và phân mảnh dọc này được áp dụng lần lượt. Vì thế tùy vào từng trường hợp cụ thể, chúng ta tái thiết phân mảnh hỗn hợp dựa trên tái thiết quan hệ phân mảnh ngang và tái thiết phân mảnh dọc đã nêu ở trên. 1.2. Phương pháp tạo cây toán tử dạng SQL và dạng AQL từ các mảnh. Cây toán tử là cách thể hiện bằng đồ thị của một câu truy vấn dạng SQL (Structured Query Language) hay AQL (Algebraic Query Language). 1.2.1. Chuyển SQL sang AQL 1.Các phép toán quan hệ 2. Các câu lệnh trong SQL 3. Chuyển SQL sang AQL Phép chiếu: được kí hiệu là π, sau đó là các thuộc tính nằm sau SELECT, nêu điều kiện liên quan đến thuộc tính của quan hệ xuất hiện trong mệnh đề FROM. 6 Phép chọn: được kí hiệu là σ, sau đó là các thuộc tính nằm sau WHERE, nêu điều kiện liên quan đến thuộc tính của quan hệ xuất hiện trong mệnh đề FROM. Thường sử dụng AND, OR, NOT, BETWEEN, các phép toán so sánh. Phép kết nối: được kí hiệu là , trong mệnh đề WHERE thường có điều kiện kết nối nếu như trong mệnh đề FROM có nhiều hơn hai quan hệ. 1.2.2. Tạo cây toán tử dạng SQL và AQL Định nghĩa cây toán tử: Một cây toán tử là cây với mỗi nút lá biểu thị cho một quan hệ được lưu trong cơ sở dữ liệu, nút không phải là lá biểu thị một quan hệ trung gian được sinh ra bởi phép toán quan hệ. Chuỗi các phép toán để đi theo hướng lá đến gốc, gốc biểu thị kết quả vấn tin. Cách biến đổi câu vấn tin phép tính quan hệ trở thành một cây toán tử như sau: i. Trước hết tạo ra các nút lá là các quan hệ trong SQL các nút lá nằm sau FROM. ii. Nút gốc được tạo ra như phép chiếu chứa các thuộc tính kết quả, các thuộc tính này nằm sau SELECT. iii. Lượng tử hoá (vị từ sau WHERE ) được chuyển thành các phép tính quan hệ thích hợp (phép chọn, phép nối ,…) đi từ các nút lá đến gốc. Chuỗi này có thể được cho trực tiếp qua thứ tự xuất hiện của các vị trí và các toán tử. 1.3 Kết luận chương 1 Trong CSDl quan hệ, các thể hiện của quan hệ là các bảng. Vấn đề là tìm một kiểu phân mảnh phù hợp để phân rã một bảng thành nhiều bảng con khác nhau, sao cho các câu vấn tin được tham chiếu đến các bảng dữ liệu một cách đơn giản nhất. Có ba loại phân mảnh cơ bản bao gồm: - Phân mảnh ngang 7 + Phân mảnh ngang nguyên thủy: Một quan hệ được thực hiện trên các vị từ được định nghĩa trên chính quan hệ đó. + Phân mảnh ngang dẫn xuất: Phân mảnh quan hệ dừa vào vị từ được định nghĩa trên quan hệ chủ. - Phân mảnh dọc: chia một quan hệ thành nhiều quan hệ con. Phân mảnh dọc cho phép vấn tin với các quan hệ nhỏ hơn nên giảm được số truy cập và tăng tốc độ truy cập. - Phân mảnh hỗn hợp: là tổng hợp của phân mảnh ngang và phân mảnh dọc. Tùy vào công việc sau đó chọn kiểu phân mảnh nào cho phù hợp. Trong mô hình tổ chức dữ liệu, việc lưu trữ dữ liệu dạng cây giúp cho công việc tìm kiếm dữ liệu trở nên dễ dàng hơn gọi là cây toán tử. Cây toán tử là cách thể hiện bằng đồ thị của một câu truy vấn dạng SQL hay AQL. 8 CHƯƠNG 2. MỘT SỐ THUẬT TOÁN GIẢI BẰNG HEURISTIC 2.1. Giới thiệu bài toán POT và các thuật toán trên POT. Chúng ta sẽ tập trung nghiên cứu vào bài toán xác định cây truy vấn tối ưu cho toán tử mà một số toán tử của cây có thể thực hiện song song với nhau. Còn những đỉnh khác phải thực hiện tuần tự tức là dữ liệu sản xuất ra tại đỉnh này là dữ liệu tiêu thụ tại đỉnh kế tiếp sau của cây toán tử. Cây toán tử với tính chất này được gọi là cây toán tử dạng ống- POT (Pipelined Operator Tree). Gọi T = (V,E), là cây toán tử với V là tập đỉnh, mỗi đỉnh đại diện cho một toán tử, E là tập các cạnh, ti là trọng số của đỉnh i, cij là trọng số của cạnh (i,j), và p là số bộ xử lý. Vì mỗi cây toán tử kiểu này đều đẳng cấu với ma trận liền kề IP (Isomorphous) [10], [11] mà đỉnh, chính là tiêu đề cột và hàng kèm với trọng số ti của nó và Ô (cell) - giao của cột và hàng, chính là trọng số cạnh cij. Giữa T và IP có một song ánh, cho nên khi nói về cây toán tử T chúng ta có thể hiểu là ma trận liền kề IP. Do đó có thể gọi ma trận liền kề IP là ma trận truy vấn, IP truy vấn hay đơn giản là IP. Để xử lý (bằng máy tính) đồ thị nói chung- cây toán tử nói riêng, người ta dùng IP. Định nghĩa 2.1. Cây truy vấn của cây toán tử T (IP truy vấn) là một phân hoạch các đỉnh của V (hàng hoặc cột của IP) thành p tập F1,…,Fp, với tập đỉnh (cộthàng) thuộc Fk do bộ xử lý thứ k thực thi. Chi phí để thực hiện tại bộ xử lý k là chi phí thực hiện các đỉnh trong Fk cộng với trọng số từ các đỉnh này đến các đỉnh trên những bộ xử lý khác. Nói cách khác, chi phí thực hiện Fk và tổng trọng số của các cạnh (cell) nối từ một đỉnh (cột- hàng) bất kỳ trong Fk đến một đỉnh (cột- hàng) bên ngoài. Quy ước, cij= 0 nếu không có cạnh từ i đến j. Định nghĩa 2.2.Tải trên bộ xử lý k, kí hiệu Lk, là chi phí thực hiện các toán tử định vị trên bộ xử lý này cộng với chi phí truyền thông từ bộ xử lý k đến các bộ xử lý 9 khác. Nghĩa là, L K =  (ti   Cij ) hoặc L K =  (ti   Cell ij ) , trong trường hợp iFK jFK iFK jFK IP. Định nghĩa 2.3. Gọi L là thời gian hoàn thành cây truy vấn dạng ống được tính từ thời gian các toán tử khởi động cho đến khi toán tử cuối cùng hoàn tất công việc. Một cây tối ưu sẽ tồn tại ít nhất một bộ xử lý ở tình trạng “ bão hòa”. Tức là thời gian thực thi của cây truy vấn tối ưu với p bộ xử lý được xác định bởi biểu thức: L= maxl ≤k ≤ pLk= maxl ≤k ≤ p[  (ti   Cij ) ] iFK jFK Hoặc: L= maxl ≤k ≤ pLk= maxl ≤k ≤p[  (ti   Cell ij ) ] trong trường hợp IP. iFK jFK Định nghĩa 2.4. Tỉ lệ tải tại toán tử. Tỉ lệ tải tại toán tử i trên bộ xử lý k được 1 tính bởi công thức: fi= (ti+  Cij ),  i V. 𝐿 jFK Từ các định nghĩa trên, chúng ta định nghĩa bài toán lập cây toán tử dạng ống như sau: Bài toán POT: Cho cây toán tử dạng ống T = (V,E), trong đó V là tập các toán tử ( gọi là các đỉnh), ti là chi phí khi dùng toán tử i ( trọng số của đỉnh i thuộc V), Cij chi phí truyền thông giữa hai bộ xử lý ( trọng số của cạnh (i,j) thuộc E); p là số bộ xử lý ( k= l,…,p). Hãy tìm một truy vấn với thời gian trả lời cực tiểu. Nghĩa là: Tìm một phân hoạch (Fl,…,Fp) của V, tức là gom các toán tử vào các nhóm {Fk}k=l,…,p sao cho: L= maxl ≤k ≤ pLk= maxl ≤k ≤ p[  (ti   Cij ) ] là ít nhất. iFK jFK Hoặc: L= maxl ≤k ≤ pLk= maxl ≤k ≤p[  (ti   Cell ij ) ] là ít nhất, trong trường hợp IP. iFK jFK 10 Đây là bài toán NP - khó. Để tìm lời giải tối ưu cho cây toán tử dạng ống, chúng ta xây dựng một thuật toán trên cơ sở sử dụng hai phép toán gộp đỉnh và cắt cạnh của cây toán tử để quyết định vị trí các đỉnh kề nhau nên đặt cùng một nhóm Fk nào đó hay không, tức là những toán tử nào sẽ được giao cho bộ xử lý k thực hiện. 2.1.1. Các thuật toán tách - gộp các đỉnh của POT Định nghĩa 2.5. Cho cây toán tử T(V,E), toán tử Gop(i,j) hay (Collapse(i,j)) gộp hai đỉnh i và j trong tập Fk để tạo ra đỉnh m như sau: - t m = t i + t j. - Các cạnh nối với i và j được chuyển thành nối với m Định nghĩa 2.6. Cho cây toán tử T(V,E), toán tử Tach(i, j) (hay cut(i,j)) được sử dụng cắt cạnh (i, j) với hai đỉnh i và j trong tập Fk để tách hai đỉnh này như sau: - i và j thuộc hai tập Fk, Fl khác nhau. - Các đỉnh i và j sẽ có trọng số mới là: tinew = tiold + cij tjnew = tjold + cij 1.Thuật toán gộp: Gop(i,m) gộp hàng con i vào hàng cha m. Giả sử IP truy vấn cấp n ×n Input: Hàng con i, hàng cha m Output: IP truy vấn đã gộp hàng con i vào hàng cha m Begin t m = tm + t i For k=1 to n do cm,k+=ci,k End For Ghi nhãn hàng con i vào bên cạnh hàng cha m 11 Xóa hàng i và cột i End. Độ phức tạp của thuật toán là O(n). 2.Thuật toán Tách Tach(i,m) tách hàng con i ra khỏi hàng cha m. Input: Toán tử cần tách Output: Các toán tử đã được tách Begin tmnew = tmold + ci,m {với i là hàng con, m là hàng cha} tinew = tiold + ci,m {với i là hàng con, m là hàng cha} End. Độ phức tạp của thuật toán là O(n). 2.1.2. Thuật toán Dividing Giả sử có p bộ xử lý, n công việc x1, x2,…, xn có thời gian thực hiện lần lượt là t1, t2,…, tn. Mỗi công việc có thể thực hiện trên một bộ xử lý bất kỳ nhưng phải thực hiện trọn vẹn. Hãy tìm cách phân chia n công việc cho p bộ xử lý sao cho thời gian hoàn thành là nhanh nhất. Thuật toán Dividing Đầu vào: - JOBS: tập gồm có n công việc x1, x2,…, xn - Cây toán tử đơn điệu T, chứa các t1,…, tn, là thời gian thực hiện tương ứng với các công việc và khác 0. - p: số bộ xử lý 12 - F: tập gồm các phân hoạch F1,F2,…Fp để phân chia công việc vào đó. Tập F ban đầu được khởi tạo bằng rỗng (Ø) Đầu ra: - Tập kết quả F chứa các Fi và các công việc xi đã được phân chia. Cách thức hoạt động: Bước 1: - Nhập vào tập công việc JOBS = {x1,…, xn} - Nhập vào tập thời gian thực hiện các công việc T = {t1,…, tn} - Nhập vào số lượng mảnh dữ liệu p và khởi tạo tập F = {F1,…,Fp} = Ø Bước 2: - Chọn ra Fi có tổng t(Fi) là nhỏ nhất trong tập F - Chọn ra xj có tj lớn nhất trong tập JOBS. - Đưa xj vào tập Fi - Loại bỏ xj khỏi tập JOBS Bước 3: - Kiểm tra xem tập JOBS có rỗng không. + Nếu không quay lại bước 2 + Nếu có thì thực hiện bước 4 Bước 4: - Lưu phân hoạch F với các phần tử (F1,…, Fp) chứa các phần tử xj sao cho thời gian hoàn thành các công việc là nhanh nhất. Thuật toán Dividing độ phức tạp đa thức. 2.1.3. Thuật toán Dividing-BalancedCuts Chúng ta thấy rằng đầu ra của thuật toán BalancedCuts [4] là một phân hoạch liên thông có số tập như ý muốn (số tập này phụ thuộc vào số bộ xử lý). Nếu áp dụng thuật toán BalancedCuts cho các trường hợp bộ xử lý thay đổi từ p đến n thì sẽ thu 13 được (n-p+l) bộ cây tối ưu tương ứng. Sau đó kết quả của mỗi trường hợp sẽ được áp dụng tiếp cho thuật toán phân chia công việc Dividing. Cuối cùng ta thu được (n-p+l) cây truy vấn vừa bảo đảm tính tối ưu truyền thông vừa đảm bảo cân bằng tải. Chúng ta chọn kết quả tốt nhất trong (n-p+l) cây này để làm cây truy vấn tối ưu. Kết quả kết hợp này bao giờ cũng không xấu hơn kết quả của từng thuật toán riêng lẻ. Thuật toán Dividing-BalancedCuts Đầu vào: - Cây toán tử đơn điệu T, chứa các t1,…, tn, là thời gian thực hiện tương ứng với các công việc và khác 0. - p: số bộ xử lý Đầu ra: - Kết quả phân hoạch F chứa các (F1, F2, … Fp) sao cho max1≤i≤pCost(Fi) là nhỏ nhất. Kết quả của thuật toán phân hoạch (F1,F2,…,Fp) sao cho maxCost (Fi) là nhỏ nhất. Thuật toán Dividing-BalancedCuts có độ phức tạp đa thức. Thuật toán được áp dụng khá tốt không những cho những cây truy vấn thông thường với yêu cầu về cân bằng tải mà còn cho các cây truy vấn hình sao. Tính đúng đắn của thuật toán được suy từ thuật toán BalancedCuts. Khi n= p thì kết quả của thuật toán chính là kết quả của thuật toán BalancedCuts. 2.2. Nghiên cứu các thuật toán Heuristic cho bài toán POT 2.2.1. Giới thiệu thuật toán nhát cắt cục bộ cho bài toán POT Thuật toán nhát cắt cục bộ (LocalCuts) là một mở rộng của thuật toán tìm cây tối ưu cho cây toán tử POT. Mở rộng này có thể giải quyết trong trường hợp số nhóm sinh ra bởi thuật toán LocalCuts nhiều hơn số bộ xử lý cho phép, đồng thời bảo đảm yếu tố cân bằng tải giữa các bộ xử lý. 14 2.2.2. Thuật toán LocalCuts Thuật toán LocalCuts Input:  Cây toán tử đã qua tiền xử lý T [4], gồm n đỉnh.  Tham số α> 1, trong đó α là một giá trị nhỏ hơn tỉ số giữa trọng số của đỉnh lá và cạnh số cạnh nối đỉnh lá đó với đỉnh mẹ. Output : Phân hoạch liên thông (Tl,…,Tk). Thuật toán xem xét sử dụng toán tử Collapse hay cut cho một đỉnh lá và đỉnh cha của nó ( xem xét khả năng nối nó với đỉnh cha vào một phân hoạch liên thông). Cách thức hoạt động: Bước 1: - Nhập vào tập thời gian thực hiện các công việc T = {t1,…, tn} - Nhập vào tham số α > 1 Bước 2: - Xét đỉnh con j - Nếu tj > α.cjm thực hiện toán tử cut(j,m). - Nếu tj ≤ α.cjm thực hiện toán tử collapse(j,m). Bước 3: - Kiểm tra xem nếu còn đỉnh cha m có đỉnh con i không. + Nếu có quay lại bước 2 + Nếu không thì thực hiện bước 4 Bước 4: - Lưu phân hoạch liên thông T với các phần tử (T1,…, Tk) . Nhận xét: Thuật toán có độ phức tạp O(n), n là số đỉnh của cây toán tử đã qua tiền xử lý. 15 Kết quả thuật toán là một phân hoạch liên thông không thể đoán trước được nên thông thường thuật toán này sẽ cùng đi đôi với một thuật toán khác (cân bằng tải chẳng hạn) để phân phối các phân hoạch liên thông này cho các bộ xử lý. Thuật toán LocalCuts chỉ xem xét sử dụng toán tử collapse hay cut cho một đỉnh lá và đỉnh cha của nó (hay xem xét khả năng nối nó với đỉnh cha vào một phân hoạch liên thông), nên quyết định này độc lập với trọng số của đỉnh cha, do đó trong một số trường hợp sẽ làm tăng trọng số của đỉnh cha lên một cách đáng kể. Từ đây, chúng ta có thể gộp các đỉnh trong mảnh và dùng thuật toán Dividing để cân bằng tải trên các bộ xử lý (với số lượng) cho trước. Chú ý: Có thể gán cho các giá trị α > 1 khác nhau để được các phân hoạch khác nhau. 2.2.3.Thuật toán cân bằng tải dựa vào Dividing Giả sử có p bộ xử lý, n công việc x1, x2,…, xn có thời gian thực hiện lần lượt là t1, t2,…, tn. Mỗi công việc có thể thực hiện trên một bộ xử lý bất kỳ nhưng phải thực hiện trọn vẹn. Thuật toán cân bằng tải dựa vào nguyên tắc sau: “ Giao công việc có thời gian thực hiện lớn nhất trong các công việc chưa được phân công cho bộ xử lý hiện thời có tải ít nhất” trong đó, tải của bộ xử lý k được xác định bởi công thức L K =  (t   C iFK i jFK ij ) Đầu vào: - JOBS: tập gồm có n công việc x1, x2,…, xn - Cây toán tử đơn điệu T, chứa các t1,…, tn, là thời gian thực hiện tương ứng với các công việc và khác 0. - p: số bộ xử lý 16 - F: tập gồm các phân hoạch F1, F2,…, Fp để phân chia công việc vào đó. Tập F ban đầu được khởi tạo bằng rỗng (Ø) Đầu ra: - Tập kết quả F chứa các Fi và các công việc xi đã được phân chia. Cách thức hoạt động: Bước 1: - Nhập vào tập công việc JOBS = {x1,…,xn} - Nhập vào tập thời gian thực hiện các công việc T = {t1,…, tn} - Nhập vào số lượng mảnh dữ liệu p và khởi tạo tập F = {F1,…,Fp} = Ø Bước 2: - Chọn ra Fi có Tải(Fi) là nhỏ nhất trong tập F - Chọn ra xj có tj lớn nhất trong tập JOBS. - Đưa xj vào tập Fi - Loại bỏ xj khỏi tập JOBS Bước 3: - Kiểm tra xem tập JOBS có rỗng không. + Nếu không quay lại bước 2 + Nếu có thì thực hiện bước 4 Bước 4: - Lưu lại tập kết quả phân hoạch (F1,…,Fp). Thuật toán trên có độ phức tạp O(n2). Tuy thuật toán không để ý trọng số nhưng đơn giản và bảo đảm cân bằng tải giữa các bộ xử lý nên thường được sử dụng kết hợp với các thuật toán khác để cho những kết quả tốt hơn. 2.2.4. Ví dụ minh họa Thuật toán cân bằng tải kết hợp với thuật toán LocalCuts: 17 2.3. Kết luận chương 2 Giải thuật Heuristic cho phép tìm kiếm phương án phân chia công việc tốt nhất cho các bộ xử lý để tối ưu về cân bằng tải và truyền thông. Đặc biệt, việc trình bày song song giữa cây toán tử và IP truy vấn bằng ánh xạ đẳng cấu cho phép chúng ta vừa có cái nhìn trực quan rõ ràng dễ hiểu vừa có thể sử dụng một ngôn ngữ lập trình bậc cao để thể hiện kết quả với dữ liệu thực trên các mảng. 18 CHƯƠNG 3: ỨNG DỤNG TẠI TRƯỜNG THCS GIA THANH, NHẰM GIẢM TỐI ĐA CHI PHÍ TRUYỀN THÔNG VÀ TĂNG TỐC ĐỘ TRUY CẬP GIỮA CÁC VỊ TRÍ MẠNG CỦA TRƯỜNG 3.1 Bài toán Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường tính toán phân tán như môi trường tính toán song song. Trong quá trình hoạt động thực tiễn, công việc của tác giả đòi hỏi phải quản lý học sinh trong môi trường tính toán phân tán vì thế nhằm giảm tối đa chi phí truyền thông và tăng tốc độ truy cập giữa các vị trí mạng của trường, tác giả ứng dụng lí thuyết vào xây dựng cơ sở dữ liệu quản lý học sinh. Áp dụng bảng vấn tin cho bài toán lập lịch Các bước để áp dụng bảng vấn tin vào bài toán lập lịch:  Xây dựng trước câu vấn tin SQL.  Tạo lập cây toán tử với: - i: các nút (toán tử) trong cây toán tử. - ti: trọng số của nút thứ i, là chi phí (thời gian xử lý hoặc chi phí tiền) thực hiện phép toán tại nút này. - Cij: trọng số cạnh, là chi phí (thời gian hoặc chi phí tiền) để truyền dữ liệu từ toán tử i sang toán tử j hoặc ngược lại.  Chuyển cây toán tử sang bảng IP (truy vấn)  Áp dụng thuật toán Dividing cơ bản hoặc thuật toán cân bằng tải (có thuật giải Heuristic) để giải bài toán phân chia công việc . 3.2. Xây dựng Cơ sở dữ liệu Với bài toán trên, tác giả dựa vào quá trình hoạt động thực tiễn đề đề xuất xây dựng cơ sở dữ liệu quản lý học sinh. Với các bảng như sau:  Môn học: Chứa thông tin về các môn học trong trường có giảng dạy.  Khối học: Chứa thông tin về các khối học trong trường.  Khối học: Chứa thông tin về các lớp học của trường.