Chào mừng các bạn
»»-((¯`·(¯`vŽ¯)--»*** MasterSpy *** «--(¯`vŽ¯)·`¯))-«« - PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ
ღLONELYღ
  Home
  => Cách tạo một trang web cho riêng mình !
  => Một số địa chỉ trang web hay dành cho bạn, ....cho tôi !
  => 5 bước cơ bản để diệt tận gốc Spyware
  => 10 điều “lính mới” nên biết
  => 10 bước để lập kế hoạch cho nghề nghiệp tương lai của bạn
  => 15 LỜI KHUYÊN HỌC TIẾNG ANH
  => 21 kho lưu dữ liệu miễn phí trên Internet
  => PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ
  => 50 cuốn sách văn học cần đọc
  => Những bài học từ Adam Khoo
  => Dùng Admodify.net để quản trị và phục hồi Exchange 2003
  => Cuộc đời của Albert Einstein
  => Cảnh giác với hacker và keylogger!
  => Phần mềm miễn phí giúp bảo vệ computer khi online
  => Học thi - cần ăn uống hợp lý
  => Hacker “oánh” mỗi PC chỉ mất 39 giây
  => Xác định nguyên nhân máy tính tự khởi động !
  => Diệt virus Autorun
  => Bấm dây mạng !
  => Bảo vệ mắt khi sử dụng máy tính !
  => Blog ra đời như thế nào?
  => Bài tập Pascal kiểu bản ghi !
  => Hướng dẫn ôn tập lập trình Pascal căn bản !
  => Cách Diệt Virus
  => Cách gỡ bỏ thủ công Symantec Antivirus an toàn (Phần I)
  => Tổng hợp các lệnh ngoài DOS
  => Cài HIREN BOOTCD vào ổ cứng để cứu hộ
  => Cài windows media player 11 ( không cần active window)
  => Cấu hình mạng ADSL cho người dùng tại nhà
  => Thiết Lập Sevice trong windows XP (giúp máy chạy nhanh hơn)
  => Giới Thiệu Centos
  => Chẩn đoán lỗi của màn hình !
  => Chọn DNS truy cập mạng !
  => Kinh nghiệm phòng chống virus, spyware
  => Trắc nghiệm nghiệp vụ kế toán bằng tiếng Anh !
  => Hướng dẫn chụp hình bằng webcam
  => Tổng Hợp Code Dùng Trong Việc Tạo BLOG
  => Công dụng của các dịch vụ trong Windows
  => Sử dụng Popcap game mãi mãi !
  => Cử nhân CNTT không làm CNTT
  => Tìm hiểu DNS.Các bước thiết lập khi mới đăng ký tên miền
  => Làm DNS server online
  => Nội dung định nghĩa về vật chất của Lê Nin
  => Đọc và ... suy nghĩ !
  => Đôi điều về bảo mật hệ thống mạng trong công ty!
  => Khắc phục lỗi 999 Error của Yahoo
  => Chuyển dữ liệu của ổ C từ FAT32 thành NTFS
  => Gỡ password CMOS bằng cách nào?
  => Phần I: Cơ bản về lỗi "màn hình xanh" trong Windows
  => Tổng quan về Group Policy - từ đơn giản đến phức tạp !
  => Gửi nhiều file qua Yahoo Mail
  => Từ XP cài Hacao Linux 2.16 Pro (file ISO) vào đĩa cứng (LiveCD)
  => Chịu thuế và không chịu thuế
  => Hội thảo qua mạng với NetMeeting
  => HOST Free
  => Hướng dẫn download trên megaupload
  => KGB nén File từ 450MB còn 1.43MB rất tiện chia sẻ file trên mạng
  => Khắc phục rớt mạng liên tục
  => Kiến trúc Oracle
  => Thành công trên giảng đường đại học
  => Kỹ thuật Photoshop cơ bản !
  => Kinh nghiệm học tiếng ANH
  => KInh nghiệm học TOÁN CAO CẤP
  => Đôi điều về quá trình làm luận văn (Phần 2)
  => Làm theme cho Blog 360
  => Chia sẻ những điều học được từ cách làm việc theo nhóm
  => Vạch kế hoạch cho tương lai
  => Các Lệnh Cơ Bản trong LINUX
  => Lịch sử các nước ĐẾ QUỐC
  => Lịch sử Việt Nam
  => Links những trang web hay
  => Tạo mail server online bằng IP Động
  => Tự làm giao diện cho Yahoo Mash!
  => Mấy điểm cần tránh
  => Hỏi về IPHONE
  => Máy tính không khởi động từ ổ đĩa cứng!...?
  => MIÊU TẢ SẢN PHẨM MÁY IN hp1320
  => Phá Deep Freeze - Cướp lấy password!!!
  => Những "tuyệt chiêu" chọn mua laptop cũ
  => NHỮNG NGUYÊN TẮC CƠ BẢN CỦA BÁO CHÍ
  => Tìm hiểu nhân của hệ điều hành Linux
  => Sửa lỗi NTLDR is missing
  => Ổ cứng chóng hỏng vì... điều hòa nhiệt độ
  => Những phím tắt thông dụng trong Photoshop 7.0
  => Phím tắt trong WORDS
  => Bí mật của PHỤ NỮ
  => Hướng dẫn post hình lên mạng, và 1 số website để upload hình
  => Chương trình quản lý số điện thoại !
  => Quản lý các mạng Windows dùng script - Phần 2: Hoàn chỉnh script -
  => Cấu hình cho máy in N2500
  => Xóa nick của mình trong Friend List của người khác
  => Rollback Rx Pro:
  => User và pass của một số router
  => Giải pháp sao lưu trực tuyến miễn phí (Phần cuối)
  => Vài điều về Scanner
  => Chọn hệ điều hành của bạn
  => Làm server online tận dụng đường truyền ADSL
  => Thuật toán - Cấu trúc dữ liệu
  => So sánh Oracle và SQL Server ?
  => Cấu hình các công nghệ bảo vệ mạng Windows XP SP2 trên một máy tính
  => Tổng quan về tiết kiệm điện khi sử dụng máy tính !
  => Phần IV: Xử lý sự cố phần cứng
  => CÁC VẤN ĐỀ VỀ SỨC KHỎE PHỤ NỮ
  => Sử dụng phím tắt với Internet Explorer 7
  => SỰ PHÁT TRIỂN CỦA SINH VẬT
  => Nguồn gốc máng cỏ giáng sinh
  => Sưu tầm câu đố !
  => SVCHOST
  => Phòng chống virus cho mạng máy tính doanh nghiệp: kinh nghiệm thực tế
  => Các lệnh căn bản trong ngôn ngữ html
  => Sức mạnh của card đồ họa !
  => Cách tải Nhạc nét
  => Triết học và tâm sự của các nhà giáo
  => Phát triển chiều cao
  => Tăng tốc toàn bộ máy tính bằng tay
  => Tăng tốc WinXP
  => Chống mất cắp cho laptop với Laptop Alarm
  => Tạo file ghost!
  => Tạo một CSS layout từ một bản thiết kế (Phần 1 đến 8)
  => Tạo nick ảo trong Yahoo Messenger
  => Tết Đoan Ngọ bắt đầu từ giữa trưa
  => Thói quen tốt: Nghĩ vậy mà không phải vậy
  => Thomas Edison & những phát minh vĩ đại -
  => Windows Vista: các thủ thuật nhỏ khi sử dụng
  => Thủ thuật Blog 360
  => Thủ thuật Internet Explorer 7
  => Thủ thuật tăng tốc cho Windows
  => Thủ thuật Visual basic
  => Thủ thuật Yahoo! Messenger
  => Yahoo Messenger
  => Khám phá mạng xã hội Yahoo! Mash
  => Mẹo tìm kiếm
  => Tìm kiếm trong Excel
  => Tóc hợp khuôn mặt
  => Tokyo - Một chuyến đi
  => Mười quy luật then chốt về Bảo mật
  => Tổng hợp tất cả các kỹ thuật vượt tường lửa
  => Trang trí USB
  => Thuật toán - Cấu trúc dữ liệu CRC (Cyclic Redundancy Check)
  => Các Tuyệt kỹ khiến phái nữ phải ngã lòng
  => CÁCH UP ẢNH QUA HOST TẠI DIỄN ĐÀN
  => Quản lý danh sách bạn chat trong Yahoo! Messenger
  => Error Doctor 2007
  => TuneUp Utilities® 2007
  => Bộ gõ tiếng Việt: Unikey
  => Hướng dẫn viết bài
  => Tường lửa mới trong Windows Vista và Windows Server Longhorn
  => Web 2.0 không chỉ là công nghệ
  => Các website hữu ích về du học bậc sau đại học tại Hoa Kỳ
  => Wi-fi và an toàn thông tin
  => Thuật toán - Cấu trúc dữ liệu So khớp chuỗi với các ký tự wildcard
  => Xóa địa chỉ và homepage
  => USB không cho ghi
  => Yêu cầu của Quản trị mạng
  => Cách Add Feed trong Blog 360
  => Cách tạo theme trong suốt
  => Đề cương KT-Chính Trị
  Contact
  Guestbook
  Story
  Kiếm tiền thật dễ dàng

Biển xanh ... cát trắng

 


PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ
BẰNG NHỮNG THUẬT TOÁN SONG SONG

Nguyễn Mậu Hân, Phạm Xuân Thiện
Trường Đại học Khoa học, Đại họcHuế
 
1. Giới thiệu:
Ngày nay, những thành công trong việc áp dụng logic vào hệ thống cơ sở dữ liệu để xử lý thông tin đang được nhiều nhà tin học quan tâm, đặc biệt là vấn đề tìm lời giải tối ưu của chương trình logic nói chung và datalog nói riêng. Ở lĩnh vực này, các ứng dụng về dự báo thời tiết, chẩn đoán bệnh... đang ngày một đặt ra nhiều yêu cầu mới như tốc độ xử lý, khối lượng công việc thực hiện. Trong chương trình logic và datalog người ta đã đưa ra những phương pháp và thuật toán xử lý như phương pháp xử lý từ dưới lên (bottom up), phương pháp xử lý từ trên xuống (top down), phương pháp ma tập, tối ưu hóa các câu vấn tin hội, các đệ qui tuyến tính... nhưng các thuật toán này chỉ thực hiện trong môi trường xử lý tuần tự mà chưa chú ý đến môi trường xử lý song song.
Trong thực tế, chưa có một máy tính song song nào cũng như cách phân chia công việc cho các bộ xử lý nào có thể áp dụng có hiệu quả cho mọi bài toán. Do đó, việc chọn lựa mô hình máy tính và cách phân chia công việc để thực hiện song song bài toán đóng một vai trò quan trọng. Trong phạm vi bài báo này chúng tôi xin giới thiệu một vài thuật toán song song thực hiện nhóm các quy tắc đệ quy có quan hệ bao đóng bắc cầu nhằm rút ngắn thời gian thực hiện cũng như chi phí kết nối.

                                                              
  
 
                                                                                                                                                                                                                                                                          Stream2
   ···   
 
   
                                                                               
 
 
Hình 1: Mô hình của một kiến trúc SIMD
 
Arithmetic
Processor1
Arithmetic
Processor2
Arithmetic
Processorn
Control
Unit
 
Memory
Control
Signal
Data
Stream1
Data
Stream2
Data
Stream3
 Instruction           Results
2. Một số kiến trúc song song:

- Kiến trúc SIMD(Single instruction multiple data)    
Trong một máy SIMD, nhiều thành phần xử lí được giám sát bởi một đơn vị điều khiển. Tất cả những thành phần xử lí đều nhận cùng mệnh lệnh từ đơn vị điều khiển nhưng lại thực hiện trên những tập dữ liệu khác nhau và đến từ những luồng dữ liệu khác nhau. Một máy SIMD biểu diễn ở hình 1 với những đặc điểm sau: xử lí phân tán trên một số lượng lớn phần cứng, thực hiện đồng thời trên nhiều thành phần dữ liệu khác nhau và thực hiện cùng một câu lệnh trên các thành phần dữ liệu.
 

Processors
 
 
 
 
 
 
 
Global Memory
Hình 2:Mô hình MIMD chặt, truy cập bộ nhớ đều
 
 
Interconnection Network
                                  ....
Processor1
Processor2
ProcessorN
                                  ....
Memory
Module1
Memory
Module2
Memory
ModuleN
         - Kiến trúc MIMD (Multiple instruction multiple data):

Một máy tính MIMD là một hệ thống nhiều bộ xử lí và nhiều bộ nhớ, trong đó mỗi bộ xử lí có một đơn vị xử lí riêng và thực hiện chương trình riêng. Các máy MIMD có các đặc trưng sau: xử lí phân tán thông qua một số các bộ xử lí độc lập, chia sẻ tài nguyên chứa trong hệ thống bộ nhớ chính, mỗi bộ xử lí thực hiện độc lập, đồng thời và thực hiện các chương trình riêng. Các hệ thống MIMD thực hiện các phép toán theo dạng song song không đồng bộ, các nút hoạt động hợp tác chặt chẽ nhưng thực hiện độc lập.

 
 
 
                                        ...                   ...
Hình 3: Mô hình MIMD rời, truyền thông điệp, bộ nhớ cục bộ (NUMA) MIMD
 
 
Interconnection Network
                                          ....
Memory
Modulem
 
 
Processorm
Memory
Module1
Processor1
 
Memory
Module2
 
Processor2
Những máy tính MIMD gồm các bộ kết nối chặt và các bộ kết nối rời tùy thuộc vào cách thức mà các bộ xử lí truy cập vào bộ nhớ của các bộ xử lí khác. Những bộ xử lí kết nối chặt được chia sẻ từ một hệ thống bộ nhớ chung được hiểu là hệ thống phân chia bộ nhớ. Đối với hệ thống MIMD kết nối rời chia sẻ từ bộ nhớ hệ thống nhưng mỗi bộ xử lí có một bộ nhớ riêng được hiểu như hệ thống truyền thông điệp. Những máy tính truyền thông điệp gởi đến nhiều máy tính trong đó mỗi bộ xử lí có bộ nhớ riêng của nó và chỉ truy cập đến bộ xử lí đó. Kiến trúc truyền thông điệp MIMD được hiểu như bộ nhớ phân tán. Hình 2 chỉ ra cấu trúc của một hệ thống chia xẻ bộ nhớ MIMD trong đó bất kỳ bộ xử lí N nào cũng có thể truy cập đến bất kỳ bộ xử lí M nào thông qua mạng kết nối. Một hệ thống MIMD chia xẻ bộ nhớ còn được gọi là một hệ thống truy cập bộ nhớ đều (UMA). Hình 3 chỉ ra cấu trúc của một hệ thống truyền thông điệp. 

3. Nguyên tắc thiết kế thuật toán song song: Để đưa vào khái niệm thực hiện song song cho một ngôn ngữ tuần tự, chúng ta dùng những qui ước sau cho tính toán song song:
        - Câu lệnh Parbegin và Parend: Những khối được đóng ngoặc bằng những ký hiệu như Parbegin & Parend hoặc Cobegin và Coend. Mô hình parbegin và parend cho phép chúng ta giới thiệu những tiến trình đồng qui. Mỗi câu lệnh trong khối là một tiến trình tách rời.
 
         - Câu lệnh Forall: Câu lệnh này có thể sử dụng để giả thực hiện song song cho những đoạn mã khi có một câu lệnh đơn được thực hiện dị bộ hoặc đồng bộ trong song song. Cú pháp cơ bản là: Forall định danh: Dạng vùng IN {Parall / Syn}
                             <Câu lệnh 1>
                             <Câu lệnh 2>
                             ....
                             <Câu lệnh k>
                                         End.
Trong đó, định danh là một biến được tạo thành bên trong mã khối và thuộc khối Forall. Dạng vùng là một dạng dữ liệu được xác định một vùng giá trị và ghi rõ số những tiến trình song song được tạo ra bởi câu lệnh Forall. Một tiến trình được tạo ra cho mỗi giá trị trong phạm vi vùng và trong mỗi tiến trình định danh nhận 1 giá trị tương ứng và những câu lệnh là những đoạn mã thực hiện trong song song. Dạng PARALL xác định việc thực hiện những tiến trình đồng bộ nghĩa là xử lí song song MIMD. Dạng SYNC xác định những tiến trình đồng bộ, nghĩa là xử lí song song SIMD.
        - Câu lệnh In Parallel: Một câu lệnh In Parallel cho phép những phép toán thực hiện nhiều hơn một câu lệnh đồng thời, có nhiều thành phần của một mảng. Cú pháp cơ bản là:
For <biểu thức liên quan chỉ số mảng> do In Parallel
<Câu lệnh 1>
...
<Câu lệnh k>
End In Parallel
 
         - Câu lệnh In Parallel Processor: Định nghĩa giả mã này tương tự như trong câu lệnh song song, ngoại trừ "vòng lặp" chứa một chỉ số bộ xử lí thay vì một chỉ số mảng. Cú pháp tổng quát có dạng sau:
For <bộ xử lí P>, <biểu thức boolean liên quan chỉ số bộ xử lí> do in parallel
<câu lệnh 1>
...
<câu lệnh k>
end In parallel
           - Câu lệnh Par
Nhiều ngôn ngữ song song có khả năng thực hiện những câu lệnh đồng thời, như trong cấu trúc Par sau:
    Par {
          <câu lệnh 1>
          ......
          <câu lệnh k>
}
Từ khóa Par chỉ ra rằng những câu lệnh trong phần thân được thực hiện một cách đồng thời. Đây là song song mức dòng lệnh.
4. Những thuật toán song song: Những thuật toán song song được giới thiệu gồm: thuật toán đồ thị song song và thuật toán tính toán song song được áp dụng để tính toán bao đóng bắc cầu của đồ thị.
a. Những thuật toán tính toán song song: để thực hiện, người ta thường phân chia bài toán thành những bài toán con có kích thước nhỏ hơn, gồm 2 dạng:
+ Phân chia khối:Ma trận được phân chia thành từng nhóm gồm một số dòng hoặc cột và gán cho các bộ xử lí riêng. Mỗi nhóm chứa một số dòng (cột) bằng nhau, hoặc có thể phân chia những dòng (cột) cho các bộ xử lí theo một chu trình.
+ Phân chia bảng ô vuông:Ma trận được phân thành những ma trận con nhỏ hơn phân bố giữa các bộ xử lí và tất cả những ma trận con có cùng kích thước và được phân chia cho cả hai dòng và cột và không có bộ xử lí nào được gán cho dòng hoặc cột đầy đủ. Tóm lại, sự phân chia bảng ô vuông ánh xạ ma trận thành một ma trận vuông những bộ xử lí 2 chiều.
Xét phép nhân ma trận A cấp n x n, A = [aij]nxn và ma trận B = [bij]nxn là một ma trận C cấp n x n, C = [cij]nxn, và được định nghĩa là: cij = AikBkj. Ta có thể áp dụng mô hình mảng SIMD 2 chiều hoặc 3 chiều trên những kiến trúc thích hợp. 
- Mô hình mảng SIMD 2 chiều:
Pha 1, bộ xử lí Pij lưu trữ A[i,j] và B[i,j]. Sau đó gửi các thành phần để tạo ra tích C = A*B bằng cách quay lên thành phần của B và quay trái với thành phần A. Pha 2, tính tích vô hướng trong mỗi bộ xử lí. Pha 3, kết quả của 2 pha được gửi đến các bộ xử lí kề nhau hướng trái và lên trên của ma trận A và B. Sau 3 pha, c[i,j] của tích được thể hiện trong bộ xử lí Pij.
Procedure Paralel_Matrix_Matrix(A,B,C)
For k = 0 to n-1 do                                                                                          *Phase1*
    For Pij where 0£ i,j£ n-1 do in parallel
If i > k then A[i,j-1] Ü A[i,j]   Endif
If j > k then B[i-1,j] Ü B[i,j]    Endif
                Endfor Pij
Endfor
For Pij where 0£ i,j£ n-1 do in parallel                         *Phase 2*
C[i,j] = A[i,j] * B[i,j]
Endfor Pij
For k = 0 to n-1 do                                                                                          *Phase3*
    For Pij where 0£ i,j£ n-1 do in parallel
A: Pij Ü (move-left) A: Pij
B:Pij Ü (move-up) B: Pij
C[i,j] = C[i,j] + A[i,j]* B[i,j]
                Endfor Pij
Endfor
End Parallel_Matrix_Matrix
Mô hình mảng 3 chiều SIMDcũng có thể áp dụng để nhân ma trận A và B với n = 2q hoặc siêu phẳng với N = n3 = 2 3q bộ xử lí. Nhiều thuật toán tính toán song song như: thuật toán Warshall, thuật toán chèn cạnh (Insert Edge), thuật toán Nhân ma trận đơn vị, trong đó đặc biệt thuật toán nhân ma trận boolean, độ phức tạp thời gian là élog(n-1)ù lần với N3 bộ xử lý.
- Thuật toán Nhân ma trận Boolean(Boolean matrix multiplication)
 Những thành phần của ma trận cũng như tích ma trận là nhị phân, nghĩa là mỗi thành phần của chúng là 0 hoặc 1.
 Thuật toán: parallel matrix_matrix(A,B,C)
            For j =0 to n-1 do in parallel ( 0 £ i£ n-1)
                        A(0,i,j) = 1
            Endfor
            For j = 0 to n-1 do in paralllel
                        For k= 0 to n-1 do in parallel                            B(0,j,k) =A(0,j,k)
                        Endfor
            Endfor
            For i = 0 to élog(n-1)ù do
begin    Parallel_Matrix_matrix(A,B,C);
For j =0 to n-1 do in parallel
                         For k = 0 to n-1 do in paralllel
Begin     A(0,j,k) :=C(0,j,k);  
           B(0,j,k) :=C(0,j,k)
End;
                        End
                        End
Endfor;
Endfor;
Để tính quan hệ suy dẫn (gọi IDB) từ những quan hệ CSDL và qui tắc đã cho, ta có:
BEGIN Weimatrix; Parallel_Matrix-boolean(W[n,n]);
For i:= 1 to n do
     For j:=1 to n do
     begin v[i] := Name(i);   v[j]:= Name(j);
                             writeln("tên quan hệ IDB(",v[i],v[j], D[i,j],")");
    end;
END.
Ví dụ:                         (1) ancestor(X,Y):- parrent(X,Y);
(2) ancestor(X,Y):- parrent(X,Z) & ancestor(Z,Y);
và tập sự kiện: parrent(1,2), parrent(2,3), parrent(3,4), parrent(4,5), parrent(5,6):
                                                                                                                                                            1    1    0    0    0     0
                  2                   4                       6                              0    1    1    0    0     0
0    0    1    1    0     0                                                                                                           0    0    0    1    1     0
   1                           3                  5                                                     0    0    0    0    1     1
   Hình 2.3.Đồ thị G với ma trận kề:                               0    0    0    0    0     1
 
   1   1   0   0   0    0                 1    1    0    0    0     0                                                   1    1    1    0    0     0  
   0   1   1   0   0    0                             0    1    1    0    0     0                                                   0    1    1    1    0     0
   0   0   1   1   0    0         x      0    0    1    1    0     0                           =                      0    0    1    1    1     0
   0   0   0   1   1    0                             0    0    0    1    1     0                                                   0    0    0    1    1     0  
   0   0   0   0   1    1                             0    0    0    0    1     1                                                   0    0    0    0    1     1
   0   0   0   0   0    1                 0    0    0    0    0     1                                                   0    0    0    0    0     1
 
B                                    x                    B                                                                    =                                                    B2
 

 

1    1    1    1    1     1        
và tương tự cho: B2  x B2 = B4                    B4 x B=  B8                =                      0    1    1    1    1     1  
0    0    1    1    1     1        
0    0    0    1    1     1        
0    0    0    0    1     1
0    0    0    0    0     1                    
 
Ma trận B8 cho biết rằng đường đi trên đồ thị có độ dài 8-1 = 7, và có log é(8-1)ù = 23 tức là có 3 phép nhân liên tiếp để tạo thành ma trận C = B8 và ta thu được những cặp cạnh kết nối sau: (1,2),(1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6).
b. Thuật toán đồ thị song song:
* Thuật toán Floyd: Thuật toán bao gồm n bước. Bước đầu tiên, cạnh i, j (1£ i,j£ n) được thay với đường dẫn có giá trị nhỏ nhất từ i đến j cho phép thông qua đỉnh 1. Ma trận kết quả sau bước đầu tiên là W(1)ij. Đến bước thứ 2, đường dẫn từ i đến j được tính toán từ bước đầu tiên được thay bằng đường dẫn có giá trị nhỏ nhất từ i đến j thông   qua đỉnh 1 và 2. Đường dẫn được kí hiệu là W(2)ij = Min {w(1)ij, w(1)i2+w(1)2j}, trong đó ma trận kết quả là W(2)ij. Để tính toán W(k)ij, là giá trị nhỏ nhất của một đường dẫn từ i đến j:   
                                         Wij                                                                         k= 0
W(k)ij =                 Min(W(k-1)ij, (W(k-1)ik+ W(k-1)kj) 0 £ k £ n-1
 
 Thuật toán minh họa như sau:
Procedure sequential_shortest_path(W[n,n])
Array D[n,n], W[n,n]
For i,j = (1,2...n) D[i,j] Ü W[i,j]
For k = (1,2...n)
For i= (1,2...n)
For j = (1,2...n)   D[i,j] Ü min {D[i,j], (D[i,k] + D[k,j])}
                        Return D
End sequential_shortest_path.
                        Thuật toán tuần tự đòi hỏi n phép lặp, và mỗi phép lặp yêu cầu O(n2) thời gian. Do đó, toàn bộ thời gian thực hiện của thuật toán tất cả cặp đường dẫn ngắn nhất tuần tự là O(n3), D khởi đầu có trọng số giữa các đỉnh như sau:
            W(i,i) = 0
            W(i,j) ³ 0 nếu i ¹ j
            W(i,j) = ¥ nếu cạnh (k,j) không tồn tại.
                        Thuật toán sử dụng n2 bộ xử lí và được tổ chức thành một mảng 2 chiều. Bộ xử lí Pij tính toán giá trị W(k)ij trong đó k = 1,2,..n. Thuật toán thể hiện élognù phép lặp và đường dẫn ngắn nhất giữa các cặp đỉnh, mỗi phép lặp k, bộ xử lí Pij cần những giá trị W(k-1)ij, W(k-1)ik và W(k-1)kj.
Procedure parallel_shortest_path(W[n,n]).
Array D[n,n], W[n,n], T[n,n]
For all i,j = (1,2...n) in parallel do D[i,j] Ü W[i,j]
Repeat élognù lần
            For all i,j,x = (1,2...n) in parallel do
            T[i,x,j] Ü D[i,x] + D[x,j]
            For all i,j= (1,2...n) in parallel do
            D[i,j] Ü min (D[i,x], T[i,1,j],T[i,1,j],...T[i,n,j]).
Return D
         For i:= 1 to n do
     For j := 1 to n do 
if (d[i,j] > 0 and d[i,j] ¹ +¥)   then E = E È E(v[i], v[j], d[i,j] );
End parallel_shortest_path.
Ví dụ: Tìm tất cả các cặp thành phố đã cho có chi phí thấp nhất.
(1) Tour(A,B,N): -distance(A,B,N)   (2) Tour(A,B,N):-tour(A,C,M) & tour(C,B,L).
Với các khoảng cách: Distance(1,1,1), Distance(1,2,10), Distance(1,3,5), Distance(2,3,2), Distance(2,5,1), Distance(3,2,3), Distance(3,4,2), Distance(4,5,4), Distance(5,4,6).


1    10    5    ¥    ¥                                            1    10    5    ¥    ¥                              1    10    5    ¥    ¥          ¥    0     2    ¥    1                            ¥    0     2    ¥    1                               ¥    0     2    ¥     1
W =     ¥    3     0    2    ¥             D1 =      ¥    3     0    2    ¥              D2 =    ¥    3     0    2      4
           ¥   ¥    ¥     0    4                                                          ¥   ¥     ¥    0    4                               ¥    ¥    ¥    0     4
                        ¥   ¥    ¥     6    0                                 ¥   ¥     ¥    6    0                               ¥    ¥    ¥    6     0
           
     1     8     5    7     9                                            1     8    5    7    9                                 1    8     5    7     9
                 ¥    0     2     4    1                                                  ¥    0     2    4    1                                ¥    0     2    4     1
D3 =   ¥    3     0     2    4                                 D4 =    ¥    3     0    2    4                    D5 =    ¥    3     0    2     4
          ¥    ¥     ¥     0   4                                             ¥   ¥    ¥    0    4                                             ¥   ¥    ¥    0     4
                 ¥   ¥     ¥     6   0                                       ¥   ¥    ¥    6    0                                             ¥   ¥    ¥    6     0
      Ta được: tour(1,1,1); tour(1,2,8), tour(1,3,5), tour(1,4,7), tour(1,5,9), tour(2,3,2); tour(2,4,4), tour(2,5,1), tour(3,2,3); tour(3,4,2), tour(4,5,4), tour(5,4,6). Khác với thuật toán tất cả cặp đường dẫn ngắn nhất của Dijkstra, thuật toán Floyd thậm chí nếu tồn tại một số cạnh nào đó có trọng số âm nghĩa là những trọng số nào đó của các cạnh trong đường dẫn âm.
5. Kết luận: Xử lý song song đang là phương tiện thực hiện có hiệu quả các bài toán có thời gian tính toán lớn, dù chúng có độ phức tạp đa thức. Việc đưa các bài toán được thực hiện trong môi trường xử lý tuần tự trước đây về môi trường xử lý song song là một vấn đề có ý nghĩa thực tiễn. Ở đây, tận dụng ưu điểm cuả mô hình mảng SIMD hai chiều chúng tôi đề xuất phương pháp xử lý song song cho lớp các bài toán có liên quan đến tính toán ma trận và các bài toán về đồ thị.
TÀI LIỆU THAM KHẢO
1.       Jeffrey D. Ullman. Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức (3 tập), Nhà xuất bản thống kê (1996)
2.       Barry Wilkinson, Michael Allen. Parallel Programming, techniques and applications using networked workstations and parallel computers, Prentice Hall, Upper Saddle River, New Jersey 07458.
3.       Seyed H.Roosta. Parallel Processing and Parallel Algorithms theory and computation, Springer, Oswego, New York (1999)
4.       Clement T.Yu, Weiyi Meng. Principles of Database Query Processing for Advanced Applications, Morgan Kaufman Inc (1998)
5.       Hong. Parallel Query Processing Using Shared Memory Multiproseccors and Disk Arrays, Univesity of California, Berkeley, August (1992)
 
TÓM TẮT
Bài báo đề xuất phương pháp xử lý song song cho các thuật toán của chương trình logic nói chung và datalog nói riêng nhằm tăng tốc độ và khối lượng công việc xử lý.
 
A PARALLEL METHOD TO PROCESS LOGIC AND DATALOG FIELD  
Pham Xuan Thien, Nguyen Mau Han
College of Sciences, Hue University
SUMMARY
This paper suggests a parallel processing method to increase speed up and work processing in logic and datalog field .
 
Today, there have been 1 visitors (18 hits) on this page!
=> Do you also want a homepage for free? Then click here! <=
Đến với thành phố biển Vũng Tàu