ĐẠI HỌC QUỐC GIA TP. HCM
CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
Độc Lập - Tự Do - Hạnh Phúc
------------------oOo--Tp. HCM, ngày 16 tháng 12 năm 2007

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Trần Hồng Hà

Giới tính: Nam ;/ Nữ …

Ngày, tháng, năm sinh: 28/11/1982

Nơi sinh: Lâm Đồng

Chun ngành: Khoa học Máy tính
Khố: 2006
1- TÊN ĐỀ TÀI:
XÂY DỰNG MƠ HÌNH BIỂU DIỄN VI MẠCH LOẠI BẤT ĐỒNG BỘ
2- NHIỆM VỤ LUẬN VĂN: xây dựng mơ hình biểu diễn trung gian vi mạch
loại bất đồng bộ thỏa mãn các u cầu sau.
- Mơ hình biểu diễn trung gian biểu diễn được các vi mạch loại bất đồng bộ.
- Mơ hình hỗ trợ q trình biến đổi từ các đặc tả cấp cao của vi mạch bất đồng bộ
sang mơ hình trung gian này.
- Mơ hình hỗ trợ việc mơ phỏng ở mức hành vi mạch bất đồng bộ.
3- NGÀY GIAO NHIỆM VỤ: 07/2007
4- NGÀY HOÀN THÀNH NHIỆM VỤ: 12/2007
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: TS. Đinh Đức Anh Vũ
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thơng qua.
CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MƠN

(Họ tên và chữ ký)

QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

TS. Đinh Đức Anh Vũ

TS. Đinh Đức Anh Vũ


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học: TS. Đinh Đức Anh Vũ

Cán bộ chấm nhận xét 1: PGS. TS. Nguyễn Hữu Phương

Cán bộ chấm nhận xét 2: TS. Trần Văn Hoài

Luận văn thạc sĩ được bảo vệ tại
HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 30 tháng 01 năm 2008


i

LỜI CAM ĐOAN

Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác
như đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do chính
tơi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một
bằng cấp ở trường này hoặc trường khác.

Ngày 16 tháng 12 năm 2007

Trần Hoàng Hà

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


ii

LỜI CẢM ƠN
Tôi xin gởi lời cảm ơn chân thành nhất đến TS. Đinh Đức Anh Vũ, người
Thầy đã tận tình hướng dẫn tơi trong suốt q trình thực hiện luận văn cao học và
tạo mọi điều kiện để tôi có thể hồn thành luận văn này.
Để hồn thành luận văn này, tôi cũng đã nhận được sự giúp đỡ của các thành
viên dự án PAiD, của bạn bè và người thân. Tôi xin chân thành cảm ơn.
Và tôi xin gởi lời cảm ơn sâu sắc đến gia đình, đã động viên và tạo điều kiện
tốt nhất để tơi có thể tiếp tục theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành
tặng thành quả của luận văn này cho Cha Mẹ. Nhờ công lao dưỡng dục của Người
mà chúng con mới có được thành quả như ngày hơm nay. Con xin hứa sẽ tiếp tục cố
gắng phấn đấu để vươn cao hơn nữa.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ


HVTH: Trần Hoàng Hà


iii

TÓM TẮT LUẬN VĂN
Mạch bất đồng bộ đã được đưa ra vào những năm 1946 nhưng không được
chú ý phát triển trong một thời gian dài. Gần đây mạch bất đồng bộ đã giành được
nhiều sự quan tâm của các nhà khoa học cũng như các công ty. Tuy nhiên việc thiết
kế và sản xuất mạch bất đồng bộ vẫn gặp rất nhiều khó khăn do thiếu các cơng cụ
hỗ trợ thiết kế.
Mục tiêu của đề tài là xây dựng mơ hình biểu diễn trung gian nhằm hỗ trợ việc
thiết kế mạch bất đồng bộ. Mơ hình được đề nghị là mơ hình Petri-DFG. Việc biến
đổi từ các đặc tả cấp cao của mạch bất đồng bộ sang mơ hình Petri-DFG và mô
phỏng vi mạch BĐB ở mức hành vi được hỗ trợ bởi mơ hình đã xây dựng.
Trong mơ hình Petri-DFG, mạng Petri được sử dụng để biểu diễn dòng điều
khiển và cây DFG được dùng để biểu diễn dòng dữ liệu của mạch bất đồng bộ. Với
việc sử dụng mạng Petri, các cấu trúc điều khiển cơ bản như tuần tự, song song và
lặp sẽ được hỗ trợ. Đồng thời, các kênh truyền thông và các giao thức bắt tay cũng
được biểu diễn một cách đầy đủ. Việc kết hợp giữa mạng Petri và cây DFG giúp mơ
hình Petri-DFG biểu diễn vi mạch loại bất đồng bộ một cách hồn chỉnh.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


iv

ABSTRACT

Asynchronous circuits design was invented in 1940s. Because of the
difficulties when design circuits using this approach compared with synchronous
approach, there were not many applications using the asynchronous mechanism. In
recent years, synchronous designs faced with some obstacles for which the best
solutions are asynchronous circuits. Therefore, scientists and companies have paid
more attention to asynchronous design. However, it has not been mature due to the
lack of EDA tools.
In order to encourage the research and development of asynchronous design,
this work proposes an intermediate representation model called Petri-DFG model.
This model is created by the combination of Petri network and data flow graph
(DFG). The control flows and the data flows of asynchronous circuits are denoted
by Petri network and DFG respectively. The Petri-DFG model can support basis
control

flow

structures

as

sequence,

parallel

and

iteration.

Moreover,


communication channels and handshaking protocols of asynchronous circuits are
completely described by this model.
The Petri-DFG model proves its worth to be used as the main intermediate
model in PAiD project, which develops a design tool for asynchronous circuits. In
this project, the synthesis process of asynchronous circuits from high level
specifications to gate netlist is conducted efficiently by using Petri-DFG model. In
addition, this model enhances the signal level simulation of asynchronous circuits.
As a sequence, Petri-DFG is a suitable intermediate representation model for
asynchronous circuits design.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


v

MỤC LỤC
LỜI CAM ĐOAN..................................................................................................................... i
LỜI CẢM ƠN.......................................................................................................................... ii
TÓM TẮT LUẬN VĂN......................................................................................................... iii
ABSTRACT............................................................................................................................ iv
MỤC LỤC ..............................................................................................................................v
DANH MỤC HÌNH .............................................................................................................. vii
Chương 1
1.1.
1.2.
1.3.
1.4.


GIỚI THIỆU ĐỀ TÀI.........................................................................................1

Lý do thực hiện đề tài .................................................................................................1
Mục tiêu và giới hạn của đề tài...................................................................................4
Tóm lược những kết quả đạt được ..............................................................................5
Cấu trúc của luận văn..................................................................................................5

Chương 2

CƠ SỞ LÝ THUYẾT..........................................................................................6

2.1. Mạch bất đồng bộ .......................................................................................................6
2.1.1.
2.1.2.
2.1.3.
2.1.4.
2.1.5.
2.1.6.

Khái niệm mạch bất đồng bộ............................................................................................6
Ưu điểm của mạch bất đồng bộ........................................................................................7
Khuyết điểm của mạch bất đồng bộ .................................................................................8
Phân loại mạch bất đồng bộ ...........................................................................................10
Các giao thức mã hóa dữ liệu .........................................................................................12
Các giao thức bắt tay ......................................................................................................15

2.2. Lý thuyết mạng Petri.................................................................................................18
2.2.1. Định nghĩa mạng Petri....................................................................................................18
2.2.2. Tính chất của mạng Petri................................................................................................20


2.3. Đồ thị dịng dữ liệu DFG ..........................................................................................23
Chương 3

NHỮNG CƠNG TRÌNH LIÊN QUAN...........................................................25

3.1. Mạch bounded-delay.................................................................................................25
3.1.1. Fundamental mode mạch Huffman ................................................................................25
3.1.2. Mạch Burst-mode...........................................................................................................27
3.1.3. Một số vấn đề của phương pháp bounded-delay............................................................28

3.2. Mạch Delay-Insensitive ............................................................................................29
3.2.1. Mơ hình I-Net.................................................................................................................30
3.2.2. Biên dịch dựa trên module .............................................................................................30
3.2.3. So sánh giữa mạch DI và mạch bounded-delay .............................................................31

3.3. Mạch Speed-Independent và mạch Quasi-Delay-Insensitive ...................................31
3.3.1. STG ................................................................................................................................32
3.3.2. Change diagrams ............................................................................................................34
3.3.3. Communicating Processes Compilation.........................................................................35

3.4. Vi mạch micropipeline..............................................................................................37
3.5. Đánh giá các mơ hình biểu diễn mạch bất đồng bộ ..................................................39

Luận văn cao học: Xây dựng mô hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


vi


Chương 4

MƠ HÌNH BIỂU DIỄN TRUNG GIAN MẠCH BẤT ĐỒNG BỘ...............42

4.1. Đặt vấn đề .................................................................................................................42
4.2. Hướng giải quyết ......................................................................................................43
4.2.1. Mô hình Petri-DFG ........................................................................................................43
4.2.2. Biểu diễn các phần tử mạch bất đồng bộ bằng mơ hình Petri-DFG...............................44

4.3. Q trình tổng hợp đặc tả Petri-DFG từ đặc tả hình thức.........................................49
4.4. Tổng kết ....................................................................................................................50
Chương 5

HIỆN THỰC .....................................................................................................51

5.1. Hiện thực mơ hình Petri-DFG ..................................................................................51
5.2. Ứng dụng mơ hình Petri-DFG trong dự án PAiD.....................................................53
5.3. Ví dụ quá trình tổng hợp đặc tả Petri-DFG của mạch bất đồng bộ ..........................54
5.3.1. Mạch đếm.......................................................................................................................54
5.3.2. Mạch trọng tài ................................................................................................................56

5.4. Kết luận.....................................................................................................................59
Chương 6
6.1.
6.2.
6.3.
6.4.

KẾT LUẬN........................................................................................................60


Tổng kết ....................................................................................................................60
Những đóng góp của đề tài .......................................................................................61
Hướng phát triển .......................................................................................................61
Cơng trình cơng bố liên quan đến đề tài của tác giả .................................................61

TÀI LIỆU THAM KHẢO.....................................................................................................62
PHỤ LỤC

............................................................................................................................64

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


vii

DANH MỤC HÌNH
Hình 1.1: Mơ hình hệ thống thiết kế mạch bất đồng bộ ........................................................ 4
Hình 2.1: Mơ hình mạch đồng bộ .......................................................................................... 7
Hình 2.2: Mơ hình mạch bất đồng bộ .................................................................................... 7
Hình 2.3: Các loại hazard ...................................................................................................... 9
Hình 2.4: Mơ hình thời gian trễ ........................................................................................... 10
Hình 2.5: Các loại giao thức bắt tay .................................................................................... 13
Hình 2.6: Giao thức bốn pha - mã hóa 2 dây ....................................................................... 14
Hình 2.7: Mơ hình Pipeline với giao thức bốn pha bundled-data........................................ 15
Hình 2.8: Mơ hình pipeline với giao thức hai pha bundled-data ......................................... 16
Hình 2.9: Cấu trúc latch hiện thực giao thức hai pha .......................................................... 17
Hình 2.10: Mạch một bit, ba tầng sử dụng giao thức bốn pha dual-rail .............................. 17
Hình 2.11: Ví dụ của mạng Petri ......................................................................................... 18

Hình 2.12: Quá trình chuyển trạng thái. .............................................................................. 20
Hình 2.13: Tính sống của mạng Petri .................................................................................. 21
Hình 2.14: Thuộc tính của mạng Petri................................................................................. 23
Hình 2.15: Ví dụ của cây DFG ............................................................................................ 24
Hình 3.1: Bảng dịng chảy và máy trạng thái ...................................................................... 26
Hình 3.2: Bìa Karnaugh và mạch hiện thực có hazard ........................................................ 26
Hình 3.3: Cấu trúc mạch tuần tự Huffman .......................................................................... 27
Hình 3.4: Mạch Burst-mode ................................................................................................ 28
Hình 3.5: Cấu trúc Join và cấu trúc Merge của I-net ........................................................... 30
Hình 3.6: Isochronic fork và mạch delay-insensitive .......................................................... 32
Hình 3.7: So sánh giữa STG/MG, mạng Petri và State Graph ............................................ 33
Hình 3.8: STG với đầu vào chọn và đầu vào khơng chọn ................................................... 33
Hình 3.9: CD và sơ đồ trạng thái tương ứng........................................................................ 35
Hình 3.10: Ví dụ về CSP ..................................................................................................... 37
Hình 3.11: Cấu trúc cơ bản của vi mạch kiểu micropipeline............................................... 38
Hình 3.12: Cấu trúc micropipeline với bộ xử lý và thanh ghi ............................................. 38
Hình 4.1: Cấu trúc tuần tự ................................................................................................... 44
Hình 4.2: Cấu trúc song song............................................................................................... 45

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


viii

Hình 4.3: Cấu trúc rẽ nhánh................................................................................................. 45
Hình 4.4: Cấu trúc lặp.......................................................................................................... 46
Hình 4.5: Giao tiếp sử dụng kênh truyền thơng và giao thức 4-pha.................................... 47
Hình 4.6: Giao tiếp sử dụng kênh truyền thơng và giao thức 2-pha.................................... 47

Hình 4.7: Mơ hình mạch trọng tài........................................................................................ 48
Hình 4.8: Biểu diễn mạch trọng tài bằng mơ hình Petri-DFG............................................. 49
Hình 5.1: Mơ hình biểu diễn trung gian trong quá trình tổng hợp....................................... 54
Hình 5.2: Mạch đếm chưa tối ưu ......................................................................................... 55
Hình 5.3: Mạch đếm tối ưu .................................................................................................. 55
Hình 5.4: Mạch hàm main của mạch trọng tài chưa tối ưu.................................................. 56
Hình 5.5: Mạch hàm main của mạch trọng tài tối ưu .......................................................... 57
Hình 5.6: Mạch Arbiter chưa tối ưu..................................................................................... 58
Hình 5.7: Mạch Arbiter đã tối ưu......................................................................................... 59

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


1

Chương 1

GIỚI THIỆU ĐỀ TÀI

Chương giới thiệu đề tài sẽ trình bày yêu cầu, mục tiêu và nội dung sơ lược
của đề tài. Đồng thời chương này cũng nêu lên những động cơ thúc đẩy việc thực
hiện đề tài trong thực tiễn cũng như trong nghiên cứu.

1.1.

Lý do thực hiện đề tài
Trong lịch sử phát triển của các phương pháp thiết kế vi mạch, phương pháp


thiết kế bất đồng bộ (BĐB) và đồng bộ (ĐB) đều có cùng một xuất phát điểm vào
đầu những năm 1946. Nhưng sau đó do tính chất dễ dàng trong việc thiết kế và khả
năng kháng lỗi tốt phương pháp thiết kế có sử dụng xung clock (mạch ĐB) đã lên
ngôi. Cùng với định luật Moore ra đời, phương pháp thiết kế có xung clock đã
chiếm hầu hết các nghiên cứu và các sản phẩm trong lĩnh vực bán dẫn thời gian này.
Vào những năm 1960, vi mạch BĐB chỉ còn xuất hiện trong các cơng trình nghiên
cứu của các trường đại học nhưng chúng cũng chỉ giành được rất ít sự quan tâm.
Tuy nhiên, vào cuối những thập niên 1980 đầu 1990 cho đến nay vi mạch BĐB đã
hồi sinh [1-3]. Một số trung tâm nghiên cứu về vi mạch BĐB ra đời chẳng hạn các
trung tâm của đại học Manchester, đại học Caltech, đại học Cornell, đại học
Ultah,…Và trong công nghiệp một số công ty như Philips, Sun, Intel, Handshake
Solutions, Fulcrum, Silistix, Achronix, Camgian Networks… đã quan tâm nghiên

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


2

cứu lnh vực vi mạch BĐB. Các trường đại học và các cơng ty trên đã có những
thành cơng bước đầu trong lĩnh vực này. Họ đã đề ra một số phương pháp luận để
thiết kế mạch BĐB và đã thiết kế thành cơng một số chíp BĐB như Amulet [4] của
đại học Manchester, MiniMIPS [5] của đại học Caltech, TITAC-2 [6] của đại học
Tokyo, ASPRO-216 [7] của trung tâm IMAG ở Grenoble và trong số đó có một số
sản phẩm đã được thương mại hóa như các vi xử lý BĐB 80C51 [8] và ARM996HS
[9] của Philips, Pentium 4 của Intel với một số thành phần không sử dụng xung
clock, vi xử lý DDMP [10] của Sharp. Do vậy việc nghiên cứu về vi mạch BĐB là
một hướng đi hứa hẹn có nhiều ứng dụng trong tương lai.
Vi mạch BĐB đã hồi sinh trở lại và ngày càng chiếm vị trí nhất định trong các

sản phẩm thương mại hiện có trên thị trường mặc dù tỉ lệ của chúng khơng nhiều.
So với vi mạch ĐB, vi mạch BĐB có những tiềm năng [11]:
- Hiệu năng cao do mạch BĐB có thể thực hiện các bước tính tốn tiếp

theo ngay khi thực hiện xong bước tính tốn trước đó mà khơng cần phải
chờ tín hiệu xung clock.
- Tiêu thụ năng lượng thấp: mạch ĐB tiêu thụ dòng rò khi thụ động và

tiêu thụ năng lượng khi hoạt động nhưng mạch BĐB chỉ tiêu thụ năng
lượng khi nó hoạt động. Chính khả năng này tạo cho mạch BĐB trở thành
một giải pháp cho những mạch địi hỏi tiêu thụ rất ít năng lượng như thiết
bị di động, hộ chiếu điện tử, thẻ từ…
- Nhiễu và phát xạ điện từ thấp: do khơng có sự hiện diện của xung

clock, mạch BĐB ít tạo ra nhiễu và phát xạ điện từ so với mạch ĐB. Tính
chất này giúp vi mạch BĐB có tiềm năng trong các ứng dụng như A/D,
bộ thu nhận sóng.
- Dễ dàng kết nối với các hệ thống không đồng nhất khác: các khối BĐB

có thể kết nối với nhau một cách dễ dàng do không phụ thuộc vào xung
clock.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


3

Vi mạch BĐB có một số tính chất vượt trội so với vi mạch ĐB và bước đầu có

ứng dụng trong thực tế. Tuy nhiên việc phát triển vi mạch BĐB cịn gặp nhiều khó
khăn do sự thiếu hụt các công cụ hỗ trợ thiết kế (EDA- Electronic Design
Automation) cho việc mô phỏng, tổng hợp, P&R (place and routing), kiểm tra,…
Do đó, việc phát triển các cơng cụ và xây dựng các mơ hình hỗ trợ cho q trình
thiết kế vi mạch BĐB là điều cần thiết.
Hướng nghiên cứu, thiết kế và sản xuất vi mạch đang và sẽ là một hướng phát
triển đầy tiềm năng ở Việt Nam. Lĩnh vực này đang được các công ty và các trường
đại học đầu tư phát triển nhưng chủ yếu tập trung vào vi mạch ĐB. Như đã trình
bày ở trên, vi mạch BĐB là một giải pháp hứa hẹn nhiều kết quả khả quan và có khả
năng thay thế cho mạch ĐB trong một số ứng dụng. Vì vậy việc nghiên cứu, tìm
hiểu và ứng dụng phương pháp thiết kế vi mạch BĐB là một yêu cầu được đặt ra.
Trong quá trình thiết kế vi mạch, việc đưa ra một mơ hình biểu diễn là một
vấn đề quan trọng. Mơ hình biểu diễn sẽ giúp ích rất nhiều cho các quá trình biểu
diễn, biến đổi, tổng hợp và sản xuất vi mạch. Do đó việc đưa ra một mơ hình biểu
diễn vi mạch BĐB là một yêu cầu cấp thiết và phần nào được giải quyết trong luận
văn này.
Xuất phát từ các lý do trên, luận văn này đưa ra một mơ hình biểu diễn vi
mạch loại BĐB và xây dựng các hàm thư viện hỗ trợ quá trình biểu diễn, mô phỏng
và tổng hợp vi mạch loại BĐB.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


4

1.2.

Mục tiêu và giới hạn của đề tài

Đặc tả mạch
bất đồng bộ

Mơ hình biểu diễn
trung gian

Q trình
mơ phỏng

Q trình
tổng hợp

Hình 1.1: Mơ hình hệ thống thiết kế mạch bất đồng bộ
Hiện nay, hầu hết các mơ hình biểu diễn trung gian mạch BĐB thuộc hai dạng
chính. Dạng thứ nhất là nhóm các mơ hình ở mức trừu tượng thấp, gần với mạch
thực tế nhưng không gần gũi với người thiết kế. Dạng thứ hai là nhóm các mơ hình
ở mức trừu tượng cao, rất tiện lợi cho quá trình thiết kế nhưng việc tổng hợp thường
cho kết quả không tối ưu. Do đó, mục tiêu của đề tài là xây dựng một mơ hình biểu
diễn trung gian vi mạch loại BĐB có mức trừu tượng trung bình làm tăng tính tối ưu
của mạch sau khi tổng hợp và hỗ trợ q trình biểu diễn, mơ phỏng mạch dễ dàng.
Khi đó, các mạch BĐB được biểu diễn bằng một ngôn ngữ cấp cao bất kỳ sẽ được
biến đổi về dạng biểu diễn trung gian (Hình 1.1).
Việc nghiên cứu đưa ra mơ hình biểu diễn trung gian mạch BĐB được giới
hạn ở những khía cạnh sau:
- Mơ hình biểu diễn trung gian biểu diễn được các vi mạch loại BĐB.
- Mơ hình hỗ trợ quá trình biến đổi từ các đặc tả cấp cao của vi mạch

BĐB sang mơ hình trung gian này.
- Mơ hình hỗ trợ việc mơ phỏng ở mức hành vi mạch BĐB.


Luận văn cao học: Xây dựng mô hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


5

1.3.

Tóm lược những kết quả đạt được
Với những mục tiêu và yêu cầu của đề tài, sau thời gian nghiên cứu và hiện

thực, chúng tôi đã xây dựng được mô hình Petri-DFG dùng để biểu diễn trung gian
vi mạch BĐB. Mơ hình này đã được dùng làm mơ hình biểu diễn trung gian trong
dự án PAiD (Project of Asynchronous circuit Design) nhằm nghiên cứu và phát
triển công cụ hỗ trợ việc thiết kế vi mạch BĐB. Dự án này thuộc khuôn khổ những
dự án của Đại học Quốc gia TP. Hồ Chí Minh, được thực hiện tại khoa Khoa Học
và Kỹ Thuật Máy tính trường Đại học Bách Khoa TP. Hồ Chí Minh.
Mơ hình Petri-DFG được xây dựng gồm hai thành phần. Thành phần thứ nhất
là các cấu trúc dữ liệu cho phép biểu diễn vi mạch BĐB. Thành phần thứ hai là các
hàm hỗ trợ việc mô phỏng, biến đổi, tổng hợp và kiểm tra một số tính chất của
mạch.

1.4.

Cấu trúc của luận văn
Cấu trúc các phần còn lại của luận văn được chia thành các chương như sau:
Chương 2 giới thiệu một số lý thuyết sẽ sử dụng trong luận văn. Thứ nhất là lý

thuyết mạch BĐB. Thứ hai là lý thuyết mạng Petri và cây DFG. Đây là các công cụ

được sử dụng để xây dựng mô hình biểu diễn trung gian vi mạch BĐB.
Chương 3 tóm tắt sơ lược các cơng trình liên quan đến đề tài. Những ưu nhược
điểm của các cơng trình này sẽ được phân tích và đánh giá nhằm đưa ra cái nhìn
tổng qt về các mơ hình biểu diễn mạch BĐB hiện nay.
Chương 4 trình bày những vấn đề đặt ra và hướng giải quyết trong quá trình
biểu diễn vi mạch BĐB.
Các vấn đề hiện thực mơ hình biểu diễn trung gian được trình bày ở chương 5.
Chương 6 đưa ra kết luận, đóng góp và hướng phát triển của đề tài.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


6

Chương 2

CƠ SỞ LÝ THUYẾT

Lý thuyết mạch BĐB và các lý thuyết liên quan là kiến thức nền tảng của luận
văn này. Do đó khái niệm về mạch BĐB, phân loại mạch BĐB và các giao thức bắt
tay của mạch BĐB sẽ lần lượt được giới thiệu ở chương này. Ngoài ra, việc biểu
diễn trung gian vi mạch BĐB trong đề tài sử dụng mạng Petri và cây DFG, vì vậy
khái niệm và một số tính chất của mạng Petri và cây DFG cũng được trình bày một
cách khái quát.

2.1.

Mạch bất đồng bộ


2.1.1.

Khái niệm mạch bất đồng bộ

Khái niệm mạch ĐB (Synchronous Circuit): mạch ĐB là mạch thực hiện các
tác vụ trên các tín hiệu rời rạc thời gian (Hình 2.1). Tất cả tác vụ của mạch đều
được bắt đầu và kết thúc phụ thuộc vào một tín hiệu định thời chung hay cịn gọi là
xung clock. Tín hiệu định thời này được tạo bởi một bộ tạo dao động.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


7

Hình 2.1: Mơ hình mạch đồng bộ
Khái niệm mạch BĐB (Asynchronous Circuit): mạch BĐB là mạch thực hiện
các tác vụ trên các tín hiệu nhị phân nhưng các tác vụ có thể thực hiện một cách liên
tục về thời gian (Hình 2.2). Các thành phần của mạch khơng chia sẻ thời gian
chung.

Hình 2.2: Mơ hình mạch bất đồng bộ

2.1.2.
2.1.2.1.

Ưu điểm của mạch bất đồng bộ
Hiệu năng cao (high performance)


Mạch BĐB có thể thực hiện bước tính tốn tiếp theo ngay khi thực hiện xong
bước tính tốn trước đó mà khơng cần phải chờ tín hiệu xung clock. Tính chất này
giúp cho mạch BĐB có khả năng tăng hiệu suất hoạt động. Tuy nhiên khả năng này
cũng bị giới hạn một phần do những phí tổn để có được tính chất trên so với mạch
ĐB.
2.1.2.2.

Tiêu thụ năng lượng thấp (low power dissipation)

Mạch ĐB tiêu thụ dòng rò khi thụ động (tắt xung clock) và tiêu thụ năng
lượng khi hoạt động (xung clock bật). Ngược lại mạch BĐB chỉ tiêu thụ năng lượng
khi nó hoạt động. Bất kỳ một bộ phận nào của mạch đều sẽ trở về trạng thái thụ
động và không tiêu thụ năng lượng ngay sau khi hoạt động. Chính khả năng này tạo

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


8

cho mạch BĐB trở thành một giải pháp cho những mạch địi hỏi tiêu thụ rất ít năng
lượng như thiết bị di động, hộ chiếu điện tử, thẻ từ…
2.1.2.3. Nhiễu và phát xạ điện từ thấp (low noise and low electro-magnetic
emission)
Do khơng có sự hiện diện của xung clock, mạch BĐB ít tạo ra nhiễu và phát
xạ điện từ so với mạch ĐB. Tính chất này thể hiện cả trên miền thời gian và miền
tần số và đã được khảo sát trên một số vi xử lý thực tế (80C51 BĐB của Philips so
với các chip ĐB khác cùng loại [11]). Tính chất này giúp vi mạch BĐB có tiềm

năng trong các ứng dụng như A/D, bộ thu nhận sóng.
2.1.2.4.

Dễ dàng kết nối với các hệ thống không đồng nhất khác

Khái niệm SOC (system-on-a-chip) ngày càng được ứng dụng nhiều trong xu
thế phát triển của quá trình thiết kế chip. Khi đó một con chip sẽ bao gồm rất nhiều
các thành phần khác nhau, trong đó một số phần được cung cấp bởi hãng khác hay
tái sử dụng một thiết kế đã có. Việc kết nối giữa các thành phần đặt ra cho các nhà
phát triển những bài toán đau đầu vì các thành phần này có thể phải giao tiếp theo
các tần số xung clock khác nhau. Mạch BĐB có thể là một giải pháp hồn thiện cho
bài tốn này. Vì các khối BĐB có thể kết nối với nhau một cách dễ dàng do không
phụ thuộc vào xung clock.

2.1.3.
2.1.3.1.

Khuyết điểm của mạch bất đồng bộ
Hazard

Hazard được xem như là một xung khơng mong muốn (unwanted glich) của
tín hiệu. Có 4 loại hazard Hình 2.3:

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


9


Hình 2.3: Các loại hazard
Dịng dữ liệu trên mạch ĐB chỉ có ý nghĩa khi xung clock tích cực, nghĩa là
trong khoảng thời gian giữa một chu kì xung thì dữ liệu có thay đổi cũng khơng ảnh
hưởng kết quả của mạch. Ngược lại dòng dữ liệu trên mạch BĐB truyền qua các
thành phần ln có ý nghĩa khi hai thành phần bắt tay truyền dữ liệu cho nhau. Nếu
hazard xảy ra sẽ làm cho kết quả của mạch bị sai lệch.
Để giải quyết vấn đề hazard trong mạch BĐB phải sử dụng các giải pháp để
loại bỏ hazard chẳng hạn thêm các tổ hợp dư thừa, thêm các phần tử làm trễ, các
mạch bắt tay (hand shake)… các giải pháp trên làm mạch trở nên phức tạp dẫn đến
hậu quả là mạch sẽ bị giảm hiệu suất.
2.1.3.2.

Deadlock

Một tập tiến trình được gọi là bị deadlock nếu khơng có tiến trình nào giải
phóng tiến trình khác cho đến khi nó tự giải phóng mình. Do mạch BĐB thực hiện
các giao thức bắt tay nên nếu không được thiết kế tốt sẽ làm cho các thành phần
trong mạch phải chờ đợi nhau, dẫn đến deadlock.
2.1.3.3.

Thiếu các công cụ hỗ trợ thiết kế

Hầu hết các công cụ hỗ trợ thiết kế đều được thiết kế cho mạch ĐB. Các cơng
cụ này có thể tổng hợp được các mạch BĐB, nhưng chúng không nhằm mục tiêu
phục vụ cho mạch BĐB nên không giải quyết được một số trở ngại đặc trưng của
mạch BĐB.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà



10

Ví dụ: hầu hết các cơng cụ tổng hợp đều loại bỏ các cổng dư thừa mà người
thiết kế đưa vào để giải quyết vấn đề hazard.
Việc phát triển các công cụ hỗ trợ cho thiết kế mạch BĐB gặp phải bài toán
con gà và quả trứng. Nghĩa là khi thị trường của mạch BĐB cịn nhỏ các cơng ty sẽ
không đầu tư vào việc thiết kế các EDA hỗ trợ thiết kế và nếu khơng có các EDA
thì ngành thiết kế vi mạch BĐB sẽ khó phát triển được.
2.1.3.4.

Thiếu kinh nghiệm thiết kế

Hiện nay trên thế giới, mạch ĐB được tìm hiểu, đi sâu nghiên cứu và có ứng
dụng rộng rãi. Các kỹ sư chủ yếu được đào tạo thiết kế mạch ĐB nên khơng có kinh
nghiệm trong lĩnh vực thiết kế mạch BĐB. Đây có thể được xem là trở ngại lớn nhất
trong việc phát triển mạch BĐB.

2.1.4.

Phân loại mạch bất đồng bộ

Việc phân loại mạch BĐB có thể dựa vào hai tiêu chuẩn: thời gian trễ hay hoạt
động của mạch [11], [12].
2.1.4.1.

Phân loại mạch bất đồng bộ dựa trên thời gian trễ

Hình 2.4: Mơ hình thời gian trễ

Khi phân loại mạch dựa trên thời gian trễ (Hình 2.4) ta quan tâm đến các giả
thiết về thời gian trễ của các phần tử trong mạch như các cổng và các dây dẫn.
a) Bounded – delay

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


11

Mơ hình mạch bounded – delay được sử dụng cho mạch BĐB cũng giống như
mơ hình sử dụng cho mạch ĐB. Mơ hình này giả định rằng thời gian trễ trên các
phần tử mạch và trên các dây dẫn là biết trước hay ít nhất cũng bị giới hạn. Tham
khảo Hình 2.4, thời gian trễ dA, dB, dC, d1, d2, d3 là biết trước hay bị giới hạn.
b) Delay – Insensitive (DI)
Mạch DI là mạch thực hiện các tác vụ một cách chính xác với thời gian trễ
trên đường dây cũng như thời gian trễ trên cổng là số dương và khơng xác định.
Tham khảo Hình 2.4, các thời gian trễ dA, dB, dC, d1, d2, d3 là tùy ý.
c) Quasi – Delay – Insensitive (QDI)
Mạch DI rất nhỏ, chỉ có những mạch được tạo từ thành phần C – element và
các cổng đảo mới có thể hiện thực bằng mạch DI.
Những mạch thuộc lớp DI thêm ràng buộc thời gian trễ ở những nhánh (wired
– fork) phải bằng nhau thì gọi là mạch QDI. Ở các nhánh wired – fork thì việc
truyền tín hiệu xảy ra cùng thời điểm, những nhánh này gọi là nhánh đồng đẳng
(isochronic). Như Hình 2.4 ở trên ngoài những giả thiết cho mạch DI mạch QDI cịn
có thêm ràng buộc d2 = d3.
d) Speed – Independence (SI)
Mạch SI là mạch thực hiện chính xác các tác vụ khi giả thiết rằng thời gian trễ
trên cổng là dương, không xác định và thời gian trễ trên dây là lý tưởng (ideal zero

– delay). Tham khảo Hình 2.4: dA, dB, dC tùy ý nhưng d1=d2=d3=0.
2.1.4.2.

Phân loại mạch bất đồng bộ dựa trên hoạt động

Phân loại dựa trên hoạt động của mạch là việc phân loại dựa trên sự tương tác
giữa mạch BĐB và môi trường bên ngồi.
a) Fundamental mode

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


12

Q trình giao tiếp giữa mạch và mơi trường bên ngồi thường bao gồm hai
bước. Đầu tiên q trình giao tiếp xảy ra khi mơi trường bên ngồi nhận được tín
hiệu đầu ra từ mạch và gởi tín hiệu đầu vào mới đến. Sau đó q trình tính tốn xảy
ra, khi đó mạch sẽ đáp ứng tín hiệu đầu vào mới nhận được bằng giá trị đầu ra mới.
Vì vậy mơi trường khơng thể gởi thêm bất kỳ một tín hiệu đầu vào mới nào khi
mạch chưa hoàn thành việc tính tốn các giá trị đầu vào trước đó. Do vậy hai quá
trình trên phải phân biệt với nhau và phải xen kẽ nhau.
Mơ hình Normal Fundamental mode chỉ cho phép một ngõ nhập thay đổi
trong mỗi quá trình giao tiếp.
b) Burst mode
Trong mơ hình này ở mỗi trạng thái của mạch chỉ có một tập các đầu vào
(input burst) được chấp nhận. Mỗi tập (burst) được mô tả bằng một tập các thay đổi
của tín hiệu. Khơng có một tín hiệu nào được lặp lại trong một tập và không một tập
nào là tập con của một tập khác, bởi vì mỗi tập sẽ xác định hoạt động của mạch

ngay khi các tín hiệu trong một tập xảy ra.
Trong burst mode, mơi trường bên ngồi sẽ khơng thay đổi các tín hiệu đầu
vào khi mạch đang thực hiện việc tính tốn và tín hiệu ngõ ra có thể được tạo ra
trong khi mạch xử lý các tín hiệu ngõ nhập tiếp theo. Có nghĩa rằng q trình tính
tốn và q trình giao tiếp có thể phủ lấp lẫn nhau.
c) Input-Output mode
Trong mơ hình này q trình tính tốn và q trình giao tiếp của mạch có thể
xảy ra tùy ý và chỉ bị giới hạn bởi giao thức truyền nhận giữa mạch và mơi trường
bên ngồi.

2.1.5.

Các giao thức mã hóa dữ liệu

Khi các giả thiết về thời gian của các loại mạch càng nới lỏng như các loại
mạch DI, QDI và SI việc truyền nhận dữ liệu giữa hai mạch diễn ra trong một thời

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


13

gian khơng xác định trước. Do đó, cần phải có cơ chế để nhận biết sự kết thúc của
quá trình truyền nhận dữ liệu. Các giao thức truyền nhận dữ liệu được trình bày sau
đây hỗ trợ việc mã hóa dữ liệu trên đường truyền và giúp nhận biết việc kết thúc của
quá trình truyền nhận dữ liệu [12], [13].
2.1.5.1.


Bundled-data protocol

Thuật ngữ “bundled-data” ám chỉ có sự “đóng gói” giữa các dây request, ack
và data Hình 2.5a.
Trong giao thức 4 pha bundled-data Hình 2.5b, các dây request và ack sử dụng
mức luận lý để mã hóa thơng tin đi kèm với dây data. Thuật ngữ bốn pha nói lên số
bước được sử dụng khi giao tiếp:
- Bên gửi gửi data và gán request lên 1.
- Bên nhận lấy data và gán ack lên 1.
- Bên gửi đáp lại bằng cách gán request về 0 (lúc này khơng có data).
- Bên nhận công nhận điều này bằng cách gán ack về 0. Lúc này bên gửi

sẽ thiết lập một chu kì mới.

Hình 2.5: Các loại giao thức bắt tay

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


14

Giao thức bốn pha bundled-data được dùng trong hầu hết các mạch số thiết kế.
Tuy nhiên nó có hạn chế là khi các dây request và ack phải trở về 0 sẽ tiêu tốn thời
gian và năng lượng không cần thiết. Giao thức hai pha bundled-data có thể giải
quyết được vấn đề trên.
Giao thức hai pha bundled-data Hình 2.5c, các dây request và ack sử dụng
mức tín hiệu để mã hóa thơng tin đi kèm với các dây data. Điều này có nghĩa là
khơng có sự khác biệt khi chuyển trạng thái từ 0 sang 1 hay từ 1 sang 0 trên các dây

request và ack. Do đó giao thức này có thể tạo ra mạch có khả năng thực hiện nhanh
hơn giao thức bốn pha bundled-data, tuy nhiên việc hiện thực mạch hai pha
bundled-data sẽ phức tạp hơn do phải kiểm tra ở mức tín hiệu.
2.1.5.2.

Dual-rail protocol

Giao thức bốn pha dual-rail Hình 2.6 mã hóa tín hiệu request vào dữ liệu. Giao
thức này sử dụng 2 dây để truyền 1 bit dữ liệu. Dây d.t biểu diễn cho mức logic 1,
và dây còn lại d.f sử dụng để biểu diễn cho mức 0.

Hình 2.6: Giao thức bốn pha - mã hóa 2 dây
Có 4 bước thực hiện giao tiếp:
- Bên gửi phát ra kí tự hợp lệ.
- Bên nhận lấy data và gán ack lên 1.

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà


15

- Bên gửi đáp lại bằng cách phát ra kí tự empty.
- Bên nhận gán ack xuống 0.

Giao thức hai pha dual-rail cũng sử dụng 2 dây {d.t, d.f} để mã hóa 1 bit, tuy
nhiên sự mã hóa là ở mức tín hiệu cũng giống như giao thức bốn pha dual-rail. Giao
thức này khơng có trạng thái empty, khi dây ack thay đổi trạng thái thì đồng thời
cập nhật dữ liệu.


2.1.6.

Các giao thức bắt tay

Các giao thức bắt tay được trình bày sau đây là một hiện thực của các giao
thức mã hóa dữ liệu ở phần trên có sử dụng cổng C-Muller. Cổng C-Muller là cổng
cơ bản của mạch BĐB, cổng này sẽ có giá trị đầu ra là 0(1) nếu cả hai giá trị đầu
vào là 0(1) và các trường hợp khác giá trị đầu ra sẽ không thay đổi.
2.1.6.1.

Bốn pha bundled-data

Bốn pha bundled-data pipeline hiện thực rất đơn giản. Muller pipeline sẽ đóng
vai trị là “clock” nội bộ của mạch. Hình 2.7(a) cho thấy mạch FIFO (khơng có sự
tính tốn dữ liệu), trong khi Hình 2.7(b) biểu diễn dữ liệu truyền qua mạch tính
tốn, do đó cần phải làm trễ tín hiệu request để q trình truyền nhận đúng.

Hình 2.7: Mơ hình Pipeline với giao thức bốn pha bundled-data

Luận văn cao học: Xây dựng mơ hình biểu diễn vi mạch loại bất đồng bộ

HVTH: Trần Hoàng Hà