ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ TOAN
NGHIÊN CỨU, THIẾT KẾ VÀ MÔ HÌNH HÓA MỘT MẠNG
TRÊN CHIP (NOC: NETWORK-ON-CHIP) VỚI CẤU TRÚC
LIÊN KẾT 2D-MESH
LUẬN VĂN THẠC SĨ
Hà Nội - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Mục lục
Lời cảm ơn i
Lời cam đoan ii
Mục lục iii
Danh mục hình vẽ v
Danh mục các từ viết tắt vii
Lời mở đầu 1
Chương 1. Hệ thống trên một vi mạch 3
1.1. Giới thiệu về hệ thống trên vi mạch 3
1.2. Các vấn đề truyền thông bên trong chip 4
1.3. Từ hệ thống trên chip đến mạng trên chip 5
1.4. Quy trình thiết kế hệ thống trên chip 7
Chương 2. Mạng trên chip và các khái niệm cơ bản 11
2.1. Mạng trên chip 11
2.2. Các khái niệm cơ bản về mạng trên chip 12
2.2.1. Tôpô mạng 12
2.2.2. Kỹ thuật truyền thông 14
2.2.3. Cơ chế truyền thông 15
2.2.4. Thuật toán định tuyến 17
2.2.5. Kỹ thuật điều khiển luồng dữ liệu và tắc nghẽn 18
2.2.6. Chất lượng dịch vụ mạng 20
Chương 3. Thiết kế, mô hình hoá và mô phỏng 22
3.1. Đặt vấn đề 22
3.2. Bộ định tuyến sử dụng trong thiết kế 23
3.3. Xây dựng mạng 2×2 25
- iv-
3.4. Phương pháp mô hình hoá, mô phỏng và kiểm chứng thiết kế. 28
3.5. Kết quả mô phỏng và kiểm chứng 31
3.5.1. Mô hình hóa và mô phỏng trên một bộ định tuyến 31
mesh; (c) 2D torus; (d) Binary tree; (e) Fat-tree. 13
Hình 2.3: Cơ chế truyền thông Lưu trữ và chuyển tiếp (SAF). 15
Hình 2.4: Cơ chế truyền thông VCT. 16
Hình 2.5: Cơ chế truyền thông Wormhole. 16
Hình 2.6: Hiện tượng tắc nghẽn tĩnh (deadlock). 19
Hình 2.7: Sử dụng kênh ảo để tránh deadlock. 19
Hình 2.8: Hiện tượng tắc nghẽn động (Livelock) 20
Hình 3.1: Mô hình mạng trên chip 2D-mesh với kích thước 2×2. 22
Hình 3.2: Mô hình bộ định tuyến được phát triển tại phòng thí nghiệm SIS. 23
Hình 3.3: Định dạng các flit. 24
Hình 3.4: Mô hình mạng 2×2 trên chip. 26
Hình 3.5: (a) Các đ
ư
ờ
ng kết nối giữa hai bộ định tuyến/lõi IP b
ấ
t kỳ; (b) Giao thức
truyền thông bắt tay “send-accept”. 26
Hình 3.6: Quy trình mô hình hóa, mô phỏng và kiểm chứng thiết kế. 28
Hình 3.7: Môi trường kiểm tra và mô phỏng chức năng hoạt động của mạch. 29
Hình 3.8: Lưu đồ thuật toán của IP phát. 30
Hình 3.9: Lưu đồ thuật toán của IP nhận. 31
- vi-
Hình 3.10: Môi trường kiểm tra, mô phỏng chức năng hoạt động của một bộ định
tuyến. 32
Hình 3.11: Kết quả mô phỏng trên một bộ định tuyến. 32
Hình 3.12: Môi trường kiểm tra, mô phỏng chức năng hoạt động của hai router. 34
Hình 3.13: Kết quả mô phỏng quá trình truyền dữ liệu từ IP00 đến IP01. 35
Hình 3.14: Kết quả mô phỏng quá trình truyền dữ liệu từ IP01 đến IP00. 36
RAM : Random Access Memory
RF : Radio Frequency
ROM : Read Only Memory
RTL : Register Transfer Level
SoC : System-on-Chip
SAF : Store-And-Forward
TTL : Time To Live
TDM : Time Division Multiplex
VC : Virtual Channel
VCT : Virtual Cut-Through
VHDL : Very High Speed Integrated Circuits HDL
VLSI : Very Large Scale Integration
WH : Wormhole
- 1- Lời mở đầu
Cùng với sự tiến bộ của công nghệ tích hợp bán dẫn, xu thế công nghệ thiết kế
chip là tích hợp ngày càng nhiều khối tính toán trên cùng một chip đơn nhằm đáp ứng
các yêu cầu của ứng dụng. Các khối tính toán này có thể là các bộ xử lý, các khối xử lý
tín hiệu số (DSP: Digital Signal Processors), các bộ nhớ (RAM, ROM), các bộ mã hoá
và giải mã, hay các đơn vị xử lý vào/ra như Ethernet, Bluetooth… Các khối tính toán
này thường được gọi là lõi IP (Intellectual Property). Một hệ thống mà trước kia phải
xây dựng trên một hay nhiều bo mạch lớn thì bây giờ có thể được tích hợp lên trên một
chip và do đó hình thành thuật ngữ “hệ thống trên chip”, trong tiếng Anh gọi là
“System-on-Chip” (SoC). Hệ thống trên một chip được biết đến như là một phương
pháp thiết kế gần đây nhất cho phép tích hợp trên hệ thống khoảng từ vài chục đến vài
trăm lõi IP như đã kể trên. Tuy nhiên, việc tích hợp nhiều lõi IP lên trên một chip dẫn
đến nhu cầu truyền thông trên chip tăng lên. Vì thế các phương thức truyền thông
truyền thống như kết nối điểm-điểm, kết nối bus chung không còn đáp ứng được nhu
- 3- Chương 1. Hệ thống trên một vi mạch
Chương này giới thiệu khái quát về một hệ thống trên vi mạch, đặc điểm của một
hệ thống trên một phiến tinh thể, tiếp đến là các vấn đề truyền thông bên trong vi mạch từ
đó đi đến giới thiệu lý do chuyển từ mô hình hệ thống trên chip thông thường sang mô
hình mạng trên chip. Cuối cùng là giới thiệu về quy trình thiết kế hệ thống trên vi mạch.
1.1. Giới thiệu về hệ thống trên vi mạch
Ngày nay, đi liền với sự phát triển công nghệ bán dẫn là công nghệ thiết kế và
chế tạo vi mạch đã cho phép tích hợp cả một hệ thống hoàn chỉnh lên trên một phiến
tinh thể (silicon). Với ý tưởng ban đầu là tích hợp tất cả các thành phần của một hệ
thống máy tính hay một hệ thống điện tử khác trên một vi mạch đơn (chip đơn).
Nhưng không lâu sau, hệ thống trên chip (SoC: System-on-Chip) đã được mở rộng, nó
nên việc thiết kế SoC đã trở lên đơn giản hơn nhiều, người thiết kế chỉ việc tích hợp
các lõi và thiết lập sự truyền thông giữa chúng. Vì vậy, phương pháp thiết kế mang lại
hiệu quả cao, rút ngắn chu kỳ thiết kế và góp phần làm giảm giá thành thiết kế. Tuy
nhiên, với hệ thống tích hợp nhiều lõi IP (các lõi này hoạt động song song và độc lập
nhau) sẽ nảy sinh một số vấn đề trong truyền thông trên chip như trễ lan truyền trên
dây và trên các cổng logic, vấn đề về truyền thông cục bộ và toàn cục, rồi vấn đề về
hiệu suất hoạt động,…
Độ trễ: Khi công nghệ thiết kế chip ngày càng phát triển, kích thước tăng, độ
tích hợp ngày càng cao và các ứng dụng đòi hỏi đáp ứng thời gian thực thì vấn đề độ
trễ lại trở lên hết sức quan trọng [4]. Vì vậy, đòi hỏi người thiết kế phải giải quyết các
vấn đề liên quan đến độ trễ đáp ứng trên các dây dẫn (cục bộ và toàn cục) và trên các
cổng logic. Trong đó, trễ trên các cổng logic thường rất nhỏ còn trễ trên đường dây là
rất lớn. Trong các trễ trên dây dẫn lại có sự khác biệt khá lớn giữa dây dẫn cục bộ (là
trễ trên dây dẫn nối bên trong lõi IP) và dây dẫn toàn cục (là trễ trên các dây nối các
lõi IP với nhau). Hơn nữa, trong cùng hệ thống thì độ trễ trên các dây nối lõi IP gần và
- 5-
IP xa là khác nhau. Vì vậy, các nhà thiết kế cần phải tìm giải pháp để giải quyết vấn đề
về độ trễ.
Đồng bộ toàn cục: Vì quá trình xử lý trong chip được chia nhỏ thành các xử lý
bên trong các lõi IP mà các lõi IP này hoạt động song song và độc lập với nhau (mỗi
lõi IP hoạt động ở một xung clock riêng) nên để đạt được sự đồng bộ toàn cục giữa
các xung clock của các lõi IP với nhau là rất khó. Chính vì vậy, người ta nghĩ ra một
giải pháp mới gọi là hệ thống GALS (Globally Asynchronous - Locally Synchronous:
đồng bộ cục bộ - dị bộ toàn cục). Với giải pháp này, mỗi lõi IP trong hệ thống làm việc
với một xung clock riêng và đồng bộ cục bộ trong lõi, còn khi ra khỏi lõi, các lõi IP
làm việc với nhau thông qua các phương thức bắt tay (handshaking) hay hỏi/đáp mà
không liên quan đến các xung clock. Nhờ có giải pháp này mà việc xây dựng các hệ
thống lớn hơn, với nhiều lõi IP làm việc với nhiều xung clock riêng sẽ trở lên dễ dàng
hơn.
DSP
a. Cấu trúc liên kết điểm-điểm
BUS
Memory
CPU
I/O
Memory
CPU
I/O
b. Cấu trúc bus
Memory
CPU
I/O
Memory
CPU
I/O
c. Cấu trúc mạng
Hình 1.2: Cấu trúc truyền thông trên chip.
Để khắc phục các nhược điểm của kết nối điểm-điểm người ta thường kết nối
theo kiểu bus, vì kết nối bus đem lại hiệu quả cao hơn và các thành phần trong hệ
thống có thể chia sẻ chung kênh truyền thông. Bên cạnh đó thì giá thành thực hiện kết
nối bus thấp hơn, đơn giản hơn và dễ thực hiện hơn. Tuy nhiên, khi công nghệ thiết kế
hệ thống phát triển (gồm nhiều lõi IP) thì kết nối theo kiểu bus bộc lộ một số hạn chế
như: khi số đơn vị xử lý trên hệ thống tăng dẫn đến dung lượng truyền thông trên chip
tăng và năng lượng sử dụng cho truyền thông tăng lên đáng kể, đặc biệt là với các bus
chủ. Ngoài ra, nếu kết nối quá nhiều sẽ rất khó khăn trong việc kiểm soát thông tin. Để
hạn chế những nhược điểm này, người ta xây dựng hệ thống bus có sử dụng crossbar
bus như AMBA [2]. Nhưng phương pháp này chưa giải quyết được triệt để các vấn đề
của hệ thống bus.
lược quy trình thiết kế và chế tại một hệ thông vi mạch hiện tại.
Quy trình thiết kế và chế tạo một hệ thống trên vi mạch cũng giống như quy
trình thiết kế và chế tạo VLSI (Very Large Scale Integration), bao gồm nhiều công
đoạn khác nhau, xuất phát từ yêu cầu bài toán đi đến xây dựng các đặc tả, thiết kế
mạch dựa trên các đặc tả vừa xây dựng… cho đến thực hiện các mặt nạ cho thiết kế,
chế tạo wafer, kiểm tra, đóng vỏ và xuất xưởng. Quy trình thiết kế hệ thống trên chip
có thể được mô tả như Hình 1.3.
Quy trình này có thể chia thành hai giai đoạn chính đó là giai đoạn thiết kế logic
(logical design) và giai đoạn thiết kế vật lý (physical design). Mỗi giai đoạn lại được
chia thành các công đoạn nhỏ hơn nhằm đơn giản và tối ưu quá trình thiết kế.
* Giai đoạn thiết kế logic
Giai đoạn này có thể chia thành 4 bước sau:
Bước 1 (System design): Đây là bước thiết kế đặc biệt quan trọng, ở bước này
người thiết kế phải lý giải được toàn bộ hệ thống mà mình sắp thiết kế. Ngoài ra,
người thiết kế còn phải hiểu rõ nguyên lý hoạt động của toàn hệ thống, các đặc điểm
về công nghệ, tốc độ xử lý mức độ tiêu thụ năng lượng, cách bố trí các chân, các lược
đồ khối, các điều kiện vật lý như kích thước, nhiệt độ, điện áp Bước này đòi hỏi
- 8-
người thiết kế phải có sự am hiểu về hệ thống, có kiến thức chuyên môn sâu, rộng và
có nhiều kinh nghiệm trong thiết kế.
Hình 1.3: Quy trình thiết kế một hệ thống trên chip.
Bước 2 (Funcion design): Sau bước thiết kế hệ thống, người thiết kế căn cứ
vào yêu cầu của bài toán thiết kế, sử dụng các ngôn ngữ thiết kế phần cứng như
VHDL, hoặc Verilog-HDL, hoặc System-C… để hiện thực các chức năng logic của
thiết kế. Quá trình thiết kế mà chỉ quan tâm tới chức năng của mạch dựa trên kết quả
tính toán cũng như sự luân chuyển dữ liệu giữa các register (flip-flop) được gọi là thiết
kế mức RTL (Register Transfer Level). Để kiểm tra tính đúng đắn của mạch, người
thiết kế có thể dùng một trong các công cụ mô phỏng như: VCS của hãng Synopsys,
kiểm chứng tính đúng đắn của hệ thống và mức độ đáp ứng của hệ thống so với yêu
cầu đặt ra. Nếu không đạt thì quay lại các bước trên để chỉnh sửa và tối ưu thiết kế.
Bước 8 (Tape out): Sau khi mô phỏng kiểm chứng thành công, toàn bộ quá
trình thiết kế vật lý sẽ được tapeout ra một file (*.gds hay *.gds2 ) và gửi đến nhà máy
sản xuất.
Giai đoạn thiết kế này đòi hỏi người thiết kế phải là các chuyên gia thực thụ, có
nhiều kinh nghiệm trong lĩnh vực này. Ngoài ra, còn cần phải có sự đầu tư về trang
thiết bị chế tạo.
- 10-
Tóm lại, chương này cho ta một cái nhìn tổng quan về một hệ thống trên vi
mạch và các vấn đề gặp phải trong quá trình thiết kế hệ thống trên vi mạch, sự ra đời
của mô hình mạng trên chip (NoC), và quy trình thiết kế một hệ thống trên vi mạch.
Chương tiếp theo sẽ giới thiệu một mô hình mạng trên chip cụ thể, đồng thời sẽ làm rõ
các khái niệm cơ bản về mạng trên chip. - 11-
Hình 2.1: Một NoC hai hướng 3×3 [8].
- Bộ phối ghép mạng thích ứng (NA: Network Adapter): cung cấp giao diện
kết nối giữa lõi IP và bộ định tuyến. NA thực hiện đóng gói dữ liệu được cung cấp bởi
IP thành các gói, các gói lại được phân chia thành các đơn vị dữ liệu nhỏ hơn (gọi là
flit) trước khi chúng được gửi vào mạng. Các flit được sử dụng cốt để tối thiểu nhu cầu
sử dụng bộ đệm và dây dẫn trong mạng.
- Các liên kết (Links): là nhóm các dây dẫn song song kết nối giữa các bộ định
tuyến. Độ rộng dữ liệu của các đường liên kết phụ thuộc vào số các dây dẫn bó lại với
nhau và số đường tín hiệu được sử dụng. Trên các đường liên kết, tại một thời điểm
chỉ có một flit dữ liệu được truyền. Các đường liên kết có nhiệm vụ kết nối các bộ
định tuyến với các bộ NA.
2.2. Các khái niệm cơ bản về mạng trên chip
2.2.1. Tôpô mạng
Tôpô (topology) mạng là cách bố trí của các phần tử trong một hệ thống mạng.
Nó quy định tổ chức vật lý của mạng và do đó thường được mô hình hoá bằng các cấu
trúc hình học. Giống như trong mạng máy tính, tôpô mạng trên chip cũng có nhiều
loại. Hình 2.2 giới thiệu một số tôpô mạng thường dùng cho mạng trên chip.
- 13-
(a)
(b) (c)
(d) (e)
Hình 2.2: Các tôpô mạng thường dùng cho mạng trên chip: (a) chordal ring; (b) 2D-mesh; (c)
2D torus; (d) Binary tree; (e) Fat-tree.
* Tôpô mạng chordal ring: thực chất là một tôpô mạng ring (các nút mạng nối
với nhau thành một vòng kín) có bổ sung thêm các dây cung giữa các bộ định tuyến
đối diện (Hình 2.2a). Ưu điểm của tôpô mạng này cho phép hiệu năng truyền thông
nguyên mạng vì tài nguyên bị chiếm giữ cho đường kết nối trong suốt quá trình truyền
tin và chỉ được giải phóng khi việc truyền dữ liệu hoàn tất. Nếu trong thời gian kênh
truyền bị chiếm dụng, có một nhu cầu truyền thông khác muốn qua một trong các nút
của kênh đó phải chờ đến khi kênh truyền được giải phóng mới được truyền. Ngoài ra,
trong kỹ thuật chuyển mạch kênh này còn có nhược điểm muốn thêm hoặc bớt bộ định
tuyến phải sửa đổi lại bộ điều khiển trung tâm.
* Kỹ thuật chuyển mạch gói
Là kỹ thuật thực hiện chia dữ liệu thành nhiều gói tin và các gói này được
chuyển tiếp theo từng chặng. Mỗi gói tin bao gồm thông tin định tuyến và dữ liệu. Các
gói tin có thể được truyền trên các đường khác nhau và có thể cùng dịch chuyển tại
một thời điểm. Tại đích đến, các gói tin hợp thành dữ liệu ban đầu. Kỹ thuật chuyển
mạch này có ưu điểm là tiết kiệm được thời gian truyền và tài nguyên mạng (vì không
cần truyền cả gói dữ liệu lớn), tăng hiệu suất đường truyền (vì một kết nối giữa hai bộ
định tuyến có thể dùng chung cho nhiều gói, các gói xếp hàng và truyền đi nhanh nhất
khi có thể), nếu trong quá trình truyền gặp tắc nghẽn thì gói tin đó có thể đi theo
đường khác để đến đích. Trong trường hợp, gói tin truyền bị lỗi thì chỉ cần truyền lại
gói tin đó thay vì phải truyền lại toàn bộ dữ liệu gốc. Ngoài ra, kỹ thuật này không cần
bộ điều khiển trung tâm vì trong các gói tin đã chứa đựng đầy đủ các thông tin định
tuyến. Tuy nhiên, kỹ thuật này có nhược điểm là trễ đường truyền lớn do qua mỗi bộ
định tuyến dữ liệu được lưu trữ, xử lý trước khi truyền đi. Vì thế, đòi hỏi các bộ định
tuyến phức tạp và độ trễ đáp ứng tín hiệu lớn hơn.
- 15-
Tùy theo mức độ yêu cầu của truyền thông mà ta có thể lựa chọn một trong hai
kỹ thuật trên. Trong đó, kỹ thuật chuyển mạch gói được sử dụng phổ biến hơn, trên
nhiều ứng dụng hơn, còn kỹ thuật chuyển mạch kênh thường dùng trong các ứng dụng
đòi hỏi khắt khe về thời gian thực, trễ đáp ứng gần như bằng không.
2.2.3. Cơ chế truyền thông
Trong kỹ thuật chuyển mạch gói có ba cơ chế truyền thông là: Lưu trữ và
chuyển tiếp, Virtual-Cut-Through và Wormhole [9]. Trong các cơ chế truyền thông
Hình 2.4: Cơ chế truyền thông VCT.
* Wormhole (WH)
Trong cơ chế truyền thông Wormhole, các flit của gói tin được di chuyển trong
mạng một cách tuần tự. Khi bộ định tuyến nhận được flit tiêu đề của gói tin, nó sẽ quyết
định chặng tiếp theo và ngay lập tức chuyển flit tiêu đề đi đến các nút kế tiếp trong
mạng (như mô tả ở Hình 2.5). Flit tiêu đề có nhiệm vụ thiết lập đường truyền của gói dữ
liệu, các flit còn lại sẽ được truyền trên đường mà flit tiêu đề đã thiết lập. Đường truyền
này chỉ được đóng lại và giải phóng tài nguyên khi flit cuối cùng của gói tin đi qua.
Hình 2.5: Cơ chế truyền thông Wormhole.
- 17-
Vì các flit dữ liệu đi theo một đường, việc định tuyến được thực hiện bởi các bộ
định tuyến, nên nó có ưu điểm tốn ít không gian bộ đệm (vì không gian bộ đệm chỉ cần
lưu trữ một flit) bộ định tuyến trở lên đơn giản, nhỏ gọn và độ trễ đáp ứng nhỏ. Vì vậy,
mà cơ chế này được sử dụng rất phổ biến. Nhưng nó có nhược điểm là rất dễ xảy ra
deadlock, nếu một flit bị chặn thì các flit theo sau cũng sẽ bị chặn theo, dẫn đến tất cả
các bộ định tuyến trong kết nối bị ảnh hưởng. Khi đó, các kết nối khác không thể sử
dụng được bất kỳ bộ định tuyến nào trên đường dẫn đó. Một giải pháp được đặt ra là
sử dụng kênh ảo để chia sẻ gánh nặng cho đường dẫn.
Trong ba cơ chế trên, cơ chế định tuyến SAF thường được dùng trong các mạng
máy tính vì trong mạng máy tính người ta không quan tâm đến kích thước bộ đệm.
Nhưng trong NoC, vì không gian thực thi hạn chế nên vấn đề kích thước bộ đệm
được quan tâm. Bởi vậy, NoC thường sử dụng cơ chế định tuyến Wormhole vì cơ
chế này có độ trễ đáp ứng thấp và tốn ít không gian bộ đệm.
2.2.4. Thuật toán định tuyến
Trong truyền thông thì thuật toán đóng vai trò hết sức quan trọng, nó có nhiệm
vụ xác định đường đi từ nguồn tới đích cho một gói tin. Thuật toán định tuyến tối ưu
sẽ đem lại hiệu năng truyền thông cao. Vì vậy, việc nghiên cứu và lựa chọn thuật toán
định tuyến sao cho vừa sử dụng tối ưu các liên kết truyền thông vừa đơn giản trong
luồng phải đảm bảo các vấn đề đồng bộ toàn cục và đồng bộ cục bộ. Có nhiều kỹ thuật
điều khiển luồng dữ liệu như kỹ thuật dừng và đợi (Stop and Wait), kỹ thuật cửa sổ
trượt (Sliding Window), kỹ thuật điều khiển luồng dữ liệu sử dụng kênh ảo Trong
đó, kỹ thuật điều khiển luồng dữ liệu sử dụng kênh ảo là một kỹ thuật điều khiển luồng
hữu hiệu, nó có khả năng tránh được sự tắc nghẽn (deadlock), tận dụng dây dẫn triệt
để, cải thiện hiệu suất và cho ra sự khác nhau về chất lượng dịch vụ,… Nên để đảm
bảo dữ liệu truyền trong mạng được chính xác, yêu cầu kỹ thuật điều khiển luồng dữ
liệu phải tránh deadlock và livelock.
Deadlock (còn gọi tắc nghẽn tĩnh): Hiện tượng deadlock xảy ra khi một hoặc
nhiều gói tin (packet) bị treo trong một khoảng thời gian không xác định. Hình 2.6 chỉ
ra một trường hợp tắc nghẽn của deadlock. Packet 1 được định tuyến từ R1 đến R2 đến
R3 và đến R4, còn packet 2 được định tuyến từ R3 đến R4 đến R1 và đến R2. Hai
packet này đồng thời được gửi đi, packet 1 xuất phát từ R1 nhưng đến R3 bị chặn lại,
còn packet 2 bắt đầu xuất phát R3 nhưng đến R1 cũng bị chặn lại vì các bộ định tuyến
này thiếu không gian bộ đệm. Chính vì vậy, hai gói tin đều bị chặn không gói nào
được truyền đến đích do cả hai gói cùng chờ quá trình giải phóng nguồn tài nguyên bị
gói tin còn lại chiếm dụng.
Copyright: Tài liệu đại học ©