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.
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

Hình 1: Mô hình của một kiến trúc SIMD

Arithmetic
Processor
1

Arithmetic
Processor
2

Arithmetic
Processorn

Control
UnitMemory
Contr
ol
Signa
Data

Stream
1

Data

Stream
2
Processor
1

Processor
2

Processor
N

Memory

Module
1

Memory

Module
2

Memory

Module
N
Module
2Processor2

- 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.
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ẻ

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>

một ma trận C cấp n x n, C = [c
ij
]
nxn
, và được định nghĩa là: c
ij
=



1
0
n
k
A
ik
B
kj
. 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í P
ij
.
Procedure Paralel_Matrix_Matrix(A,B,C)


C[i,j] = C[i,j] + A[i,j]* B[i,j]
Endfor P
ij
Endfor
End Parallel_Matrix_Matrix
Mô hình mảng 3 chiều SIMD cũng có thể áp dụng để nhân ma trận A và B
với n = 2
q
hoặc siêu phẳng với N = n
3
= 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 N
3
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


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


0 0 0 0 0 1 Ma trận B
8
cho biết rằng đường đi trên đồ thị có độ dài 8-1 = 7, và có log
(8-1) = 2
3
tức là có 3 phép nhân liên tiếp để tạo thành ma trận C = B
8
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

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(n
2
) 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(n
3
), 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 n
2
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)

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  D
1
=  3 0 2  D
2
=  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
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 .