ngữ nghĩa quan hệ
của các chơng trình tổ hợp



TS. trần văn dũng
Bộ môn Toán - ĐH GTVT
Tóm tắt: Các thao tác của các thiết bị dùng để ci đặt cho hệ thống điều khiển có thể đợc mô
phỏng bởi chơng trình, điều đó cho phép phần cứng đợc kiểm chứng bằng các công cụ phần mềm
chuẩn. Trong bi báo ny chúng tôi hình thức hoá ngữ nghĩa sự kiện của ngôn ngữ mô tả phần cứng
dới dạng các quan hệ v sử dụng các quan hệ đó để chứng minh một số tính chất của các chơng
trình tổ hợp, m mỗi chu trình hoạt động của nó l một vòng lặp có điều kiện của một số các phép gán
song song.
Summary:
The actual behaviour of hardware devices available for installation of a control
system can be simulated by a program, and this allows the hardware to be proved correct by standard
software techniques. In this paper we formalise event semantics of Hardware Description Language in
the form of relations and use relation calculus to prove properties (including termination and stability
and uniqueness of final state) of combined programs, each operational cycle of which is defined as a
conditional loop of non-deterministic choices among generalised parallel assignments.


1. Mở đầu
Chơng trình VERILOG [6] đợc sử dụng
rộng rãi để mô hình cấu trúc và hành vi của các
thiết bị phần cứng từ các thiết bị đơn giản đến các
mạng máy tính. Ngữ nghĩa mô phỏng định hớng
của sự kiện đã đợc đề cập nghiên cứu trong [3],
tuy nhiên khi mô tả hoạt động không đồng bộ của
hệ thống gồm nhiều thiết bị song song, nó rẽ

nhánh dẫn đến nhiều kết quả khác nhau. Vì vậy
ngữ nghĩa đó không hỗ trợ việc kiểm chứng các
thiết bị phần cứng. Do đó cần phải có phơng
pháp hình thức hoá ngữ nghĩa sự kiện. Bài báo
này tổng quát hoá ngữ nghĩa mô phỏng bằng
cách đa ra mô hình quan hệ cho VERILOG dựa
trên quan hệ của các trạng thái kết thúc. Bài báo
này xem xét ba lớp chơng trình mô tả hoạt động
của các mạch tổ hợp.
Hai phần đầu của Bài báo hình thức hoá ngữ
nghĩa sự kiện của VERILOG. Phần sau cùng
dành cho việc nghiên cứu các chơng trình tổ
hợp.

2. Ngôn ngữ mô tả VERILOG
Các chơng trình VERILOG đợc sinh ra bới
các qui tắc cú pháp sau:
1. Một chơng trình tuần tự đợc tạo nên từ
các phép gán song song với các phép ghép,
chọn có điều kiện, chọn không tất định:
S ::= SKIP |
v
::= E | S ; S | S < b > S | S S
trong đó
v
là véc tơ các biến Bool, E là véc tơ
các biểu thức Bool có cùng độ dài với
v
.
2. Các hàm tuần tự đang xem xét đợc đánh

số thứ tự. Giả sử ta có m các chơng trình tuần
tự: P
1
, P
2
, , P
m
, chúng có thể có các biến chung.
Giả sử index là hàm dùng để đánh số thứ tự các
chơng trình. Mọi phép gán nằm trong chơng
trình tuần tự đều có chỉ số nh chơng trình đó.
3. Biến Bool tín hiệu ~ x đợc dùng để đánh
dấu sự thay đổi của biến Bool x trong quá trình
thực hiện. Nếu biến Bool x thay đổi, thì gán ~ x là
tt
m
(trong đó tt là hằng đúng, ff là hằng sai).

Chơng trình có số thứ tự i đợc liên kết với thành
phần thứ i của biến tín hiệu (~x)[i].
4. Điều khiển sự kiện g(S) ghi nhận sự thay
đổi của các biến trong chơng trình S đợc định
nghĩa nh sau:
Giả sử S là phép gán
v
:=
E
có số thứ tự i.
Nếu x
1

, x
2,
, x
k
là tất cả các biến xuất hiện trong
E
, thì
g(S) =
df
(~ x
1
)[i] (~ x
2
)[i] (~ x
k
)[i]
Nếu S = P op Q, trong đó op { ;, , < b >},
thì
g(P op Q) =
df
g(P) g(Q) và
index(P op Q) =
df
index(P) index (Q)
Nếu S = g(P) P, thì g(S) =
df
g(P) và
index(g(P) P) = index(P)
Phép ghép hai chơng trình song song có
tập index rời nhau đợc định nghĩa nh sau:

P||Q =
df
(g(P) P) (g(Q) Q)
Phép ghép song song có tính chất giao
hoán, kết hợp và phân phối với phép chọn không
tất định và phép chọn có điều kiện.
VERILOG chơng trình có dạng @ g(S) S,
ở đó S = P
1
|| P
2
|| || P
m
và P
1
, P
2
, , P
m
là các
chơng trình tuần tự hoặc các chơng trình
VERILOG có các tập index nhau.
Ta định nghĩa g(@ g(S) S) =
df
(g(S))
Chơng trình thành phần P
i
đợc gọi là
một nhánh. Nếu sự thay đổi của biến x làm cho
g(P

i
) thay đổi giá trị từ ff sang tt, thì ta nói ~ x đã
kích hoạt điều khiển sự kiện g(P
i
) và khi đó nhánh
P
i
trở nên có thể hoạt động đợc.
Bổ đề 1
(a) g(P||Q) = g(P) g(Q)
(b) index(P||Q) =
df
index(P) index (Q)
(c) P||Q =(P||Q) < g(P||Q) > SKIP
Hành vi của một chơng trình phần cứng
đợc mô tả bởi một dãy vô hạn các bớc mô
phỏng sau
1. Tại thời điểm ban đầu của mỗi bớc mô
phỏng cho đầu vào một giá trị xác định. Giá trị
mới của đầu vào có thể kích hoạt một số các điều
khiển sự kiện. Các nhánh tơng ứng sẽ đợc kích
hoạt và có thể hoạt động.
2. Môi trờng sẽ chọn không tất định một
trong các nhánh đợc kích hoạt để thực hiện.
3. Việc thực hiện một nhánh đợc kích hoạt
P
i
đợc gọi là một bớc cơ sở, nó bao gồm các
thao tác nhỏ sau:
Thực hiện chơng trình P

i
.
Xoá điều khiển sự kiện của nhánh P
i
để chỉ
nhánh đó đã thực hiện.
Truyền sự thay đổi của các biến tạo nên
bởi sự thực hiện chơng trình P
i
.
4. Khi không có nhánh nào kích hoạt nữa, thì
bớc mô phỏng đang xét dừng và chờ nhập giá trị
mới cho đầu vào. Nếu luôn luôn có một nhánh
đợc kích hoạt sau mỗi bớc cơ sở thì bớc mô
phỏng đó không dừng.
3. Ngữ nghĩa quan hệ
Hành vi của mỗi bớc mô phỏng có thể mô
hình bởi một phép lặp của một phép ghép không
tất định một số các nhánh song song kết hợp với
một số thao tác phụ sau mỗi bớc cơ sở nh xóa
hoặc ghi nhận sự thay đổi của các biến,
Định nghĩa 1 (Ngữ nghĩa sự kiện). Giả sử
(@g(S) S) là một chơng trình VERILOG với các
biến v
1
, v
2,
, v
n
và m chỉ số khác nhau. Giả sử

nhánh P có tập chỉ số là I. Ngữ nghĩa sự kiện với
tập chỉ số I đợc định nghĩa nh sau:
(g(P) P
e,I
) =
df
(g(I))
T
; (P ||
DIS
event(P, I)
trong đó
1. Biểu thức Bool g[I] nhận đợc bằng cách
thay thế các biến ~ x trong g(S) với chỉ số I bằng

thành phần thứ I tơng ứng của véc tơ tín hiệu
(~x)[i].
2. Ký hiệu b
T
ký hiệu giả thiết SKIP < b > T
3. P ||
DIS
Q biểu diễn phép ghép song song
rời nhau của hai chơng trình P và Q [5], ở đó
chúng không có đầu ra chung.
4. Chơng trình event (P) đợc dùng để xoá
các điều khiển sự kiện đã dùng khi P đợc thực
hiện và truyền sự thay đổi của các biến cho các
nhánh khác trong chơng trình.
event(R,I) =

df
v
1
, , v
n
R k : 1 k n
(~ v
k
= (~v
k
clear(I)) bool(v
k
v
k
)
m
)
Bổ đề 2
1. event (P < b > Q,I) = event(P, I)< b >
event(Q, I)
2. event (P Q,I) = event(P, I) event(Q, I)
3. event (v
1
,v
2
:= e
1
,e
2
,I) =

= event(v
1
:= e
1
,I) ||
DIS
event(v
2
:= e
2
,I)
3. event (v:= e,I) = k : 1 k n
(~ v
k
= (~v
k
clear(I));












=

=
=
fiSKIPex
tt::x~0e0x
tt::x~1e1xif
m
m

Định nghĩa 2 (Bớc mô phỏng). Giả sử
@ g(S) S là chơng trình VERILOG, trong đó
S = P|| || Q và v

1
, v
2,
, v
n
là các biến của
chúng. Giả sử P, , Q có các tập chỉ số rời nhau
I, , J, tơng ứng. Ta định nghĩa bớc lặp mô
phỏng là bớc lặp sau:
@ g(S) S =
df
var ~ v
1,
~v
2
, , ~v
n
:=in(v

1
), in(v
n
);
(g[I] g[J] * g[I] P
e,I
g[J] Q
e,J
)
end ~ v
1,
~v
2
, , ~v
n
trong đó in(v
I
) = tt
m
nếu v
I
là đầu vào mà giá trị
mới khác với giá trị cũ.
4. Các chơng trình tổ hợp
Trong phần này chúng ta nghiên cứu các
chơng trình, mà các nhánh của chúng là các
phép gán song song. Đây là lớp các chơng trình
phần cứng mô tả hoạt động của các mạch tổ hợp,
trong đó mỗi một phép gán song song
x

:=
E

biểu diễn một thiết bị lấy giá trị
E
gán cho đầu
ra của dây
x
. Ta gọi các cặp (x
I
, E
I
) là một bổ
sung.
Định nghĩa 3. Chơng trình tổ hợp là một
chơng trình VERILOG dạng @g(P) P, trong đó
P = (
x
:=
E
) || || (
z
:=
F
) và không một biến
nào xuất hiện nhiều hơn một lần ở vế trái các
phép gán.
Định nghĩa 4. (Trạng thái ổn định). Cho
chơng trình tổ hợp nh đã định nghĩa trong Định
nghĩa 3. Giả sử VAR là tập tất cả các biến và

STATE: VAR {0, 1}
Trạng thái s STATE đợc gọi là ổn định
đối với Comb P nếu với mọi I (<v
I
> s = <E
I
> s) =
true, trong đó (x
I
, E
I
) là một bổ sung bất kỳ trong
Comb P và <E
I
> s ký hiệu giá trị của biểu thức E
tại trạng thái s.
Hàm kiểm tra tính ổn định d(P) và điều
kiện ổn định c(P) của các trạng thái của chơng
trình Comb P là các hàm logic sau:
d(P) =
df
(
x
:=
E
) ( z :=
F
)
c(P) =
df

(ơg[1]
x
:=
E
) (ơg[m]
z
:=
F
),
ở đó: g[1]= g(
x
:=
E
), , g[m] = g(
z
:=
F
).
Các chơng trình tổ hợp biến đổi từ trạng
thái ổn định này sang trạng thái ổn định khác.
Định lý 1.
c(P)
T
; Comb P = c(P)
T
; Comb P; d(P)

trong đó b

ký hiệu là khẳng định SKIP < b >

và là chơng trình ABORT.
Ta có thể bổ sung việc kiểm tra tính ổn định
vào trong điều kiện của phép lặp mà không ảnh
hởng đến hành vi của chơng trình.

Định lý 2.
c(P)
T
; Comb P = c(P)
T
; (g(P) ơ d(P)) * P
e,
trong đó P
e
= g[1](
x
:=
E
)
e,1
g[m]
(
z
:=
F
)
e,m

5. Các chơng trình tổ hợp luỹ đẳng
Trong mục này chúng ta nghiên cứu một lớp

các chơng trình con, mà mỗi phép gán của nó
lũy đẳng.
Định nghĩa 5. Chơng trình P đợc gọi là
lũy đẳng, nếu P; P = P.
Bổ đề 3. Mọi chơng trình tổ hợp đều lũy
đẳng.
Định nghĩa 6. Chơng trình tổ hợp đợc gọi
là lũy đẳng theo thành phần nếu mọi nhánh của
nó là lũy đẳng.
Bắt đầu từ một trạng thái ổn định một
chơng trình tổ hợp lũy đẳng theo thành phần
gồm hai nhánh có thể bắt đầu từ một nhánh, sau
đó thực hiện nhánh kia và cứ tiếp tục nh vậy cho
đến khi đạt đợc trạng thái ổn định.
Định lý 3. Nếu P = Q || R và Q, R là hai
chơng trình lũy đẳng, thì
c(P)
T
; Comb P; end ~
x
, ~
z
= c(P)
T
;
Comb(Q;R R;Q);end ~
x
, ~
z


Định nghĩa 7. Chơng trình P đợc gọi là
không mở rộng, nếu P
k+1
= P
k
, trong đó
X

[4]. C. Delgado Kloos and P. T. Breuer. Formal
Semantics for VHDL. Kluwer Academic Publisher,
(1995).
n+1
=
df
(X;X
n
) và X
1
=
df
X.
Khi chu trình mô phỏng của chơng trình tổ
hợp kết thúc, trạng thái của nó thờng không
đợc xác định một cách duy nhất. Đối với chơng
trình lũy đẳng có thể dễ dàng kiểm tra tính dừng
và tính duy nhất của trạng thái kết.
Định lý 4. Nếu P = Q || R và Q, R là hai
chơng trình lũy đẳng, sao cho P;Q và Q;R là hai
chơng trình không mở rộng, thì khi đó Comb P
luôn luôn dừng khi xuất phát từ trạng thái ban đầu

thỏa mãn điều kiện c(P).
6. Kết luận
Bài báo cung cấp cho ngôn ngữ mô tả phần
cứng ngữ nghĩa sự kiện dựa trên mô hình quan
hệ. Ban đầu các chơng trình tổ hợp ở trạng thái
ổn định và đợc kích hoạt bởi các giá trị mới cung
cấp cho các thiết bị đầu vào. Các nhánh kích
hoạt của chơng trình sẽ đợc lụa chọn một cách
không tất định để thực hiện. Bài báo chứng tỏ
rằng một chơng trình phần cứng tơng đơng
với một phép lặp của phép lựa chọn không tất
định của một số các chơng trình tuần tự có
chung các biến. Nếu chơng trình đợc thiết kế
tốt, thì chúng sẽ luôn luôn dừng và đạt trạng thái
kết thúc duy nhất. Đối với một lớp các chơng
trình lũy đẳng bài báo đa ra thuật toán hữu hiệu
xét tính dừng của nó. Việc nghiên cứu các tính
chất dừng và trạng thái kết duy nhất của một số
lớp chơng trình khác là đề tài nghiên cứu tiếp
theo.

Tài liệu tham khảo
[1]. K. C. Davis. A denotational definition of the VHDL
simulation Kernel. University of Cincinnati.
[2]. M. Gordon. Why higher-order logic is a good
formalsm for specifying and verifying hardware.
Formal Aspect of VLSI Design, 153-177, (1986).
[3]. M. Gordon. Event and Cycle Semantics of
Hardware Description Languages. University of
Cambridge Computer Laboratory, (1998).

[5]. C. A. R. Hoare and He Jifeng. Unifying Theory of
Programing. Prentice Hall, (1998).
[6]. Open VERILOG International. VERILOG Hardware
Description Language Reference Manual, Version
1.0.
[7]. D. E. Thomas and P. R. Mooby. The VERILOG
Hardware Description Language. Kluwer Academic
Publishers, (1995)
[8]. Tran Van Dung and He JiFeng. A Theory of
Combinational Programs. UNU/IIST Report No
162Ă