BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

TỐI ƯU HÓA TRONG THIẾT KẾ
BỘ XỬ LÝ SỐ SONG SONG

NGÀNH: XỬ LÝ THÔNG TIN VÀ TRUYỀN THÔNG
MÃ SỐ:

NGUYỄN ĐỨC TIẾN

Người hướng dẫn khoa học: TS. NGUYỄN KIM KHÁNH

HÀ NỘI 2008


Luận văn thạc sỹ

Mở đầu

Lời cảm ơn

Tôi xin gửi lời chân thành cảm ơn tiến sĩ Nguyễn Kim Khánh. Thầy là người đã
giúp tôi lựa chọn được luận văn phù hợp và hữu ích, vạch ra những bước đi đầu tiên
của luận văn. Trong quá trình thực hiện luận án, đã phát sinh rất nhiều khó khăn
nhưng dưới sự gợi ý, chỉ bảo của thầy, các vấn đề đã được giải quyết. Cảm ơn sự
quan tâm, giúp đỡ, hướng dẫn tận tình của thầy xuyên suốt quá trình nghiên cứu xây
dựng luận án, đưa luận án tới thành công.


2

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

2.1

Giới thiệu kiến trúc máy tính cao cấp và công nghệ xử lý song song ...........12
2.1.1.

Bốn kỷ nguyên computing ........................................................................................ 13

2.1.2.

Kỷ nguyên ‘Batch’ .................................................................................................... 13

2.1.3.

Kỷ nguyên ‘Chia sẻ thời gian’ .................................................................................. 13

2.1.4.

Kỷ nguyên ‘Máy tính bàn’ ........................................................................................ 14

2.1.5.

Kỷ nguyên ‘Mạng’ .................................................................................................... 15

2.1.6.



2.5.2.

Cơ chế điều khiển...................................................................................................... 27

2.5.3.

Kỹ thuật chuyển mạch............................................................................................... 27

2.5.4.

Tôpô .......................................................................................................................... 27

PHÂN TÍCH HỆ THỐNG ...............................................................................32

3.1.

Nguyên tắc phân loại mạng tương kết .............................................................33

3.2.

Mạng tương kết động dựa trên nền bus ..........................................................33
3.2.1.

Hệ thống đơn bus ...................................................................................................... 33

3.2.2.

Hệ thống đa bus......................................................................................................... 34



Mạng đơn tầng .......................................................................................................... 40

3.3.3.

Mạng đa tầng............................................................................................................. 43

3.3.4.

Các trở ngại của mạng tương kết đa tầng.................................................................. 47

Mạng tương kết tĩnh ..........................................................................................50
3.4.1.

Mạng kết nối đầy đủ.................................................................................................. 50

3.4.2.

Mạng kết nối giới hạn ............................................................................................... 51

3.4.3.

Mạng cube................................................................................................................. 53

3.4.4.

Mạng Mesh................................................................................................................ 54

3.4.5.



Luật Gustafson-Barsis ............................................................................................... 68

Hiệu năng của mạng tương kết.........................................................................69
3.8.1.

Băng thông của mạng Crossbar................................................................................. 70

3.8.2.

Băng thông của mạng đa bus..................................................................................... 72

3.8.3.

Băng thông của mạng đa tầng ................................................................................... 73

3.9.

Khả năng mở rộng của kiến trúc song song ....................................................75

3.10.

Chuẩn đo hiệu năng...........................................................................................79

4

PHÁT TRIỂN ỨNG DỤNG............................................................................86

4.1



ĐÁNH GIÁ KẾT QUẢ ....................................................................................93

6

KẾT LUẬN ........................................................................................................96

7

PHỤ LỤC ..........................................................................................................97

7.1

Mô hình chip PTBDC8x ....................................................................................97

7.2

Pipeplining trong PTBDC8x .............................................................................97

7.3

Hệ thống mini MIMD ........................................................................................98

7.4

Phân xử lệnh trong mini MIMD.......................................................................99

7.5

Mã nguồn VHDL của mạng tương kết ..........................................................100

Hình 2-4: Phân loại kiến trúc vô hướng và mảng .....................................................17
Hình 2-5: Kiến trúc SIMD ........................................................................................19
Hình 2-6: Hai mô hình kiến trúc SIMD ....................................................................20
Hình 2-7: Hai mô hình kiến trúc MIMD...................................................................21
Hình 2-8: Sự kết hợp của mô hình DSM ..................................................................22
Hình 2-9: Phân loại mạng tương kết .........................................................................26
Hình 2-10: Mạng tương kết bộ nhớ chia sẻ ..............................................................28
Hình 2-11: Hệ thống đơn bus và đa bus....................................................................28
Hình 2-12: Một số mạng tĩnh thông dụng.................................................................29
Hình 2-13: Một số mạng động thông dụng ...............................................................30
Hình 3-1: Phân loại mạng tương kết dựa trên topo...................................................33
Hình 3-2: Mạng tương kết động đơn bus ..................................................................34
Hình 3-3: Một số mô hình mạng đa bus....................................................................36
Hình 3-4: Kỹ thuật bus handshaking.........................................................................38
Hình 3-5: Mạng crossbar 8 x 8..................................................................................39
Hình 3-6: Các cách cấu hình chuyển mạch 2 x 2......................................................40
Hình 3-7: Mạng cube với N = 8 ................................................................................41
Hình 3-8: Mạng PM2I với N = 8 ..............................................................................42
Hình 3-9: Mạng tương kết đa tầng ............................................................................44
Hình 3-10: Qui tắc chuyển mạch bằng địa chỉ đích..................................................44
Hình 3-11: Mạng Shuffle-Exchange (SEN) kích thước 8 x 8...................................45
Hình 3-12: Mạng Banyan 8 x 8.................................................................................46

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

vi


Luận văn thạc sỹ



Luận văn thạc sỹ

Mở đầu

Danh mục bảng
Bảng 1: Bốn kỷ nguyên Computing..........................................................................14
Bảng 2: So sánh hiệu năng của một số mạng động...................................................29
Bảng 3: So sánh hiệu năng của một số mạng tĩnh ....................................................31
Bảng 4: Đặc trưng của một số hệ thống đơn bus thương mại...................................34
Bảng 5: Đặc tính của một số hệ thống đa bus ...........................................................35
Bảng 6: Số lần giả lập chuyển đổi giữa 3 kiểu mạng................................................43
Bảng 7: So sánh hiệu năng của một số mạng động...................................................60
Bảng 8: So sánh hiệu năng của một số mạng tĩnh ....................................................62
Bảng 9: Ví dụ về đặc tính topo của một số mạng tĩnh ..............................................69
Bảng 10: Đặc tính topo của một số mạng tĩnh ..........................................................69
Bảng 11: Hiệu năng của một số mạng động .............................................................71
Bảng 12: Khoảng cách từ node 0000 tới các node khác ...........................................74
Bảng 13: Hiệu năng của một số mạng tĩnh ...............................................................74
Bảng 14: Hệ số tăng tốc tương ứng với các giá trị của m và n .................................76
Bảng 15: Hiệu năng tương ứng với các giá trị của m và n........................................76
Bảng 16: Chương trình đo số nguyên CINT92 .........................................................80
Bảng 17: Chương trình đo số dấu phẩy động CFP92 ...............................................80
Bảng 18: 5 SPEC92 so sánh thời gian thực hiện giữa 2 hệ thống ............................82
Bảng 19: Ví dụ về kết quả đo theo chuẩn SPEC95...................................................83
Bảng 20: Hệ thống chuẩn số nguyên CPU200..........................................................84
Bảng 21: Hệ` thống chuẩn số dấu phẩy động CPU200.............................................84
Bảng 22: Kết quả chạy chương trình trên mini MIMD ............................................93

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

:

Distributed Shared Memory

IN

:

Interconnection Network

ISC

:

Inter-Stage Connection

LAN

:

Local Area Network

LCNs

:

Limited Connection Networks

MBCBMC


:

Multistage Interconnection Networks

MISD

:

Multiple Instruction Single Data

NUMA

:

NonUniform Memory Access

SEN

:

Shuffle-Exchange Network

DFS

:

Design For Scalability

SIMD


ix


Luận văn thạc sỹ

Nguyễn Đức Tiến

1 TỔNG QUAN ĐỀ TÀI
Các siêu máy tính đơn bộ xử lý hiện nay đã đạt được tốc độ và hiệu năng mạnh mẽ,
đáng kinh ngạc và đã đạt tới giới hạn về mặt phần cứng, về mặt vật lý của công
nghệ sản xuất. Điều này đã đóng lại xu thế đơn xử lý và đòi hỏi phải có một kỹ
thuật mới tiên tiến khác thay thế để nâng cao hơn nữa khả năng tính toán của hệ
thống xử lý. Hiện nay, trên thế giới, các bộ xử lý tiến tiến, các hệ thống tính toán
tích hợp, phức tạp có tốc độ cao đều áp dụng kỹ thuật xử lý song song, coi đây như
là một kỹ thuật tiên tiến, khả thi, có tính mở cao. Có thể thấy, sự phát triển mạnh mẽ
của các thế hệ bộ xử lý Dual-Core, Quad-Core, các hệ thống đa bộ xử lý như Digital
AlphaStation, Sun Sparc.. đã cho thấy khả năng ứng dụng vượt trội của kỹ thuật xử
lý song song trong.
Nắm bắt xu hướng phát triển hiện nay của các bộ xử lý, đề tài sẽ trình bày các
nghiên cứu kiến trúc máy tính nâng cao với kỹ thuật xử lý song song sử dụng nhiều
đơn vị xử lý nhằm mục đích “Tối ưu hóa trong thiết kế các bộ xử lý số song
song”. Đề tài được chia làm 4 phần chính bao gồm: cơ sở lý thuyết, phân tích hệ
thống, phát triển ứng dụng, kết luận và đánh giá.
Phần Cơ sở lý thuyết trình bày về kiến trúc máy tính cao cấp, các cách phân loại
kiến trúc máy tính, các thành phần và vai trò của chúng trong một hệ thống số xử lý
song song.
Phần Phân tích hệ thống mô tả chi tiết kiến trúc các hệ thống đa xử lý, những giải
pháp thiết kế khác nhau cho các mạng tương kết giữa các bộ xử lý, đánh giá ưu
nhược điểm của từng mạng. Tiếp theo, đề tài trình bày các công thức đánh giá và so
sánh hiệu năng, băng thông của từng mạng tương kết. Sau đó, giới hạn và ràng buộc


Nguyễn Đức Tiến

2 CƠ SỞ LÝ THUYẾT
Kiến trúc máy tính luôn luôn được thay đổi, nâng cấp để nâng cao hiệu năng xử lý
của các bộ xử lý. Hiệu năng đó có thể được cải tiến bằng cách tăng cường mật độ
tích hợp, công nghệ chế tạo, kỹ thuật gói – packaging technology và kỹ thuật song
song. Nếu chỉ sử dụng một siêu máy tính với 1 bộ xử lý duy nhất, chúng ta sẽ nhanh
chóng gặp phải những giới hạn về phần cứng, những giới hạn về mặt vật lý trong
công nghệ sản xuất chip, vì thế đã giới hạn tốc độ và sức mạnh tính toán của các bộ
xử lý.Tuy nhiên, khuynh hướng trên đã dần dần kết thúc và chuyển sang một giai
đoạn mới. Trong phần này, đề tài trình bày về cơ sở lý thuyết chung về kiến trúc
máy tính nâng cao với kỹ thuật xử lý song song sử dụng nhiều đơn vị xử lý.

2.1 Gi i thi u ki n trúc máy tính cao c p và công ngh
song song

x

lý

Các kiến trúc sư tin học luôn luôn cố gắng để nâng cao hiệu năng của các cấu trúc
máy tính của họ. Hiệu năng cao có thể đạt được từ các mạch chạy nhanh và dày đặc,
công nghệ đóng gói, và công nghệ xử lý song song. Những siêu máy tính một bộ xử
lý đã đạt được tốc độ chưa từng có và đã đẩy ngành công nghệ phần cứng đến giới
hạn vật lý của ngành sản xuất chip. Tuy nhiên, xu hướng này sẽ sớm kết thúc do
những giới hạn về mặt cấu trúc và vật lý hạn chế sức tính toán mà hệ thống xử lý
đơn có thể đạt được. Trong phần này, chúng ta sẽ nghiên cứu cấu trúc máy tính cao
cấp áp dụng công nghệ song song bằng nhiều đơn vị xử lý.
Những bộ xử lý song song là những hệ thống máy tính gồm nhiều đơn vị xử lý kết

nguyên của kỹ thuật tính toán computing, đó là : Batch, Chia sẻ thời gian, Máy tính
bàn và Mạng. Bảng 1.1 được sửa đổi từ bảng do Lawrence Tesler đề xuất. Trong
bảng này những đặc tính tiêu biểu của từng kỷ nguyên computing có mối quan hệ
với từng thập kỷ của tin học, bắt đầu từ năm 1960
2.1.2. Kỷ nguyên ‘Batch’
Đến năm 1965, chiếc máy tính lớn của IBM loại System/360 đã thống trị hầu hết
các trung tấm tin học của các công ty. Đây là loại máy xử lý BAT tiêu biểu, đặc
trưng với các thiết bị đọc card đục lỗ, các ổ tệp và các ổ đĩa nhưng không có mối
liên kết nào vượt quá phạm vi phòng máy tính. Chiếc máy tính này đã thiết lập nên
chuẩn công thức tính toán bằng các máy tính cỡ to tập trung. IBM System/360 có
một hệ hệ điều hành, lập trình đa ngôn ngữ và có ổ lưu trức tới 10 megabytes.
System/360 này chất đầy cả phòng máy tính với những hộp kim loại và những con
người điều khiển để cho chúng hoạt động. Các mạch bán dẫn của thiết bị này tương
đối nhanh. Những người sử dụng đòi hỏi tốc độ cao có thể mua thêm bộ nhớ lõi
nam châm lên tới 1 megabye của 32 bit words. Chiếc máy này đủ lớn để hỗ trợ
nhiều chương trình cùng chạy trong bộ nhớ mặc dù đơn vị xử lý trung tâm CPU
phải chuyển từ chương trình này sang chương trình khác.
2.1.3. Kỷ nguyên ‘Chia sẻ thời gian’
Những chiếc máy tính cỡ to của kỷ nguyên BAT đã có vị trí vững chắc vào nhứng
năm cuối thập niên 1960 khi những tiến bộ trong công nghệ chất bán dẫn đã tạo nên

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 13/106


Luận văn thạc sỹ

Nguyễn Đức Tiến


tr 14/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

Đến năm 1990, hệ thống mạng LAN của các máy tính cá nhân mạnh và những chiếc
workstations bắt đầu thay thế những chiếc máy tính cỡ lớn – mainframes - và những
chiếc máy tính mini. Giờ đây, sức mạnh của một chiếc máy to lớn nhất thì một
chiếc một chiếc máy tính để bàn với giá chỉ bằng 1/10 cũng có thể đạt được. Hơn
thế nữa, những chiếc máy tính để bàn đơn lẻ này đã nhanh chóng được kết nối vào
mạng liên kết máy tính rộng lớn thông qua mạng diện rộng WAN.
2.1.5. Kỷ nguyên ‘Mạng’
Kỷ nguyên thứ tư của tin học là kỷ nguyên sôi nổi nhất nhờ vào sự phát triển nhanh
chóng của công nghệ mạng. Công nghệ mạng đã nhanh chóng vượt xa so với công
nghệ xử lý trong hầu hết những năm của thập kỷ 1990s. Điều này giải thích sự phát
triển của kỷ nguyên mạng liệt kê trong bảng 1.1. Sự nhảy vọt của hiệu năng mạng
đã chuyển quan niệm từ xu hướng xử lý dựa trên các bộ xử lý trung tâm sang quan
niệm xử lý trên cơ sở mạng.
Những năm 1980s và 1990s đã chứng kiến sự ra đời của những chiếc máy tính
thương mại áp dụng công nghệ song song với đa bộ xử lý. Thông thường, chúng có
thể phân loại thành hai loại chính:
(1) Hệ thống dùng chung bộ nhớ
(2) Hệ thống bộ nhớ phân tán
Số lượng các bộ xử lý trong một chiếc máy từ một vài cái trong chiếc máy tính
dùng chung bộ nhớ đến hàng trăm nghìn cái trong một hệ thống song song khổng
lồ. Ví dụ của những chiếc máy tính song song trong kỷ nguyên này là Sequent
Symmetry, Intel iPSC, nCUBE, Intel Paragon, Thinking Machines (CM-2, CM-5),
MSPar (MP), Fujitsu (VPP500) và rất nhiều các máy tính khổng lồ khác.

data streams.
- Đa dòng lệnh đa và đơn dòng dữ liệu – MISD - multiple instruction single
data streams.
- Đa dòng lệnh và đa dòng dữ liệu – MIMD - multiple instruction multiple
data streams.
Những chiếc máy tính von Neurmann một bộ xử lý truyền thống được xếp vào kiến
trúc SISD. Những chiếc máy tính song song (áp dụng công nghệ song song, parallel
computer) được xếp vào SIMD hoặc MIMD. Khi chỉ có một khối điều khiển duy
nhất và tất cả các bộ xử lý thực hiện cùng một lệnh theo kiểu đồng bộ thì chiếc máy
song song đó được xét vào lại SIMD. Trong chiếc máy MIMD, mỗi bộ xử lý có đơn
vị điều khiển CU riêng và có thể thực hiện các lệnh khác nhau trên các dữ liệu khác
nhau. Trong MISD, cùng một dòng dữ liệu chạy qua mảng tuyến tính các bộ xử lý
thực hiện các lệnh khác nhau. Trong thực tế không thể làm được một chiếc máy
MISD nào, tuy nhiên một số tác giả đã coi những chiếc máy sử dụng kỹ thuật
pipeline và những bộ máy mảng tâm thu – systolic array computers là MISD. Các
hình 1.1, 1.2 và 1.3 lần lượt miêu tả mô hình của SISD, SIMD và MIMD.

Hình 2-1: Kiến trúc SISD

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 16/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

Hình 2-2: Kiến trúc SIMD


đơn vị thực hiện lệnh. Kiến trúc này giúp CPU có thể xử lý công việc song song bởi
các IEU khác nhau. Nó phù hợp với mô hình lập trình Multiple Instruction Multiple
Data(MIMD). Hầu hết các bộ vi xử lý cho PC và Workstation trên thị trường hiện
nay là super-scalar processor, ví dụ: Intel Pentium 4 có 6 pipelines, AMD Athlon
XP có 9 pipelines,...
Bộ vi xử lý vector (vector processor) Bộ vi xử lý này sử dụng chiến thuật song
song dữ liệu. Giống như bộ vi xử lý vô hướng tuần tự, nó cũng chỉ có một đơn vị
thực hiện lệnh IEU. Tuy nhiên thay vì chỉ xử lý được một số nguyên hay thực, IEU
này có thể xử lý một mảng các số nguyên hoặc thực mỗi lần bằng cách làm việc với
các thanh ghi vector. Thanh ghi vector là thanh ghi chứa được một mảng các số
nguyên hoặc thực. Bộ vi xử lý này phù hợp với các mô hình lập trình Single
Instruction Multiple Data (SIMD). Cấu trúc vector thường thấy trên các siêu máy
tính thương mại hiệu suất cao, được sử dụng trong các ứng dụng khoa học, ví dụ:
CRAY, NEC,..

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 18/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

2.3. Ki n trúc SIMD
Kiến trúc SIMD trong mô hình tính toán song song gồm 2 phần: phần máy tính
ngoại vi (thường là máy Von Neuman), và một mảng đơn vị xử lý như trong hình
dưới đây.

Máy Von Neumann

Nguyễn Đức Tiến

Hình 2-6: Hai mô hình kiến trúc SIMD

Có hai mô hình kiến trúc SIMD chính, được thể hiện trong Hình 2-6.
-

Mô hình Vector Computer

-

Mô hình Array Processor

Trong mô hình đầu tiên, mỗi đơn vị xử lý có một bộ nhớ riêng. Các đơn vị xử lý chỉ
có thể kết nối với nhau thông qua mạng tương kết. Nếu mạng tương kết không thể
cung cấp một kết nối trực tiếp giữa một cặp xử lý nào đó thì cặp này có thể truyền
dữ liệu thông qua một đơn vị xử lý trung gian. Máy ILLIAC IV cũng sử dụng mô
hình tương tự như vậy. Theo như cấu trúc mạng tương kết dạng ma trận vị trí 8x8

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 20/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

bên trong, ILLIAC IV cho phép mỗi đơn vị xử lý có thể kết nối trực tiếp tới 4 đơn
vị xử lý lân cận, tức là đơn vị xử lý thứ i có thể kết nối trực tiếp với đơn vị xử lý (i1), (i+1), (i-8) và (i+8).

ứng dụng. Bởi vì việc truy cập vào bộ nhớ chia sẻ là không phân biệt và như nhau

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 21/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

với mọi đơn vị xử lý, hệ thống này còn được gọi với tên khác là SMP –Symmetric
MultiProcessor – Đa bộ xử lý đối xứng.
Trong hệ thống SMP, mỗi bộ xử lý có quyền và khả năng, tốc độ đọc/ghi bộ nhớ là
như nhau. Mỗi một máy tính có tối thiểu 2 bộ xử lý giống nhau và có thể thực hiện
chức năng giống nhau. Toàn hệ thống được điều khiển bởi một hệ điều hành phân
tán. Ưu điểm của mô hình này là các công việc có thể thực hiện song song. Hơn thế
nữa, khi một bộ xử lý bị sự cố, hệ thống sẽ không bị dừng lại vì các bộ xử lý có thể
thực hiện chức năng giống nhau. Ưu điểm nữa là khả năng mở rộng dễ dàng, có thể
tăng cường hiệu năng xử lý bằng cách thêm bộ xử lý. Có thể kể tới một số ví dụ về
sản phầm thương mại theo mô hình SMP là máy chủ đa bộ xử lý của Sun
Microsystem, và máy chủ đa bộ xử lý của Silicon Graphic.
Hệ thống bộ nhớ phân tán bao gồm một mạng tương kết kết nối các điểm trong đó
mỗi điểm là một bộ xử lý và một bộ nhớ cục bộ. Ở đây, hoàn toàn không có bộ nhớ
toàn cục, vì vậy việc di chuyển dữ liệu từ bộ nhớ này sang bộ nhớ khác là nhờ vào
phương pháp truyền thông điệp. Quá trình truyền thông điệp dựa vào một cặp lệnh
chính là Send/Receive, phải được viết trước trong chương trình ứng dụng của người
lập trình. Điều đó đòi hỏi người lập trình phải học về mô hình truyền thông điệp,
bao gồm cả việc sao chép và phân phối dữ liệu được xác định cụ thể trước. Một vài
sản phẩm điển hình theo mô hình này là nCUBE, iPSC/2 và các hệ thống dựa trên

bộ nhớ toàn cục, trong đó khả năng truy xuất là tương đương nhau với mọi bộ xử lý.
Mỗi bộ xử lý có thể có các tài nguyên nhớ khác như các thanh ghi, bộ đệm, cache,
và các bank nhớ cục bộ. Tuy nhiên, có một số vấn đề phát sinh khi thiết kế theo mô
hình bộ nhớ chia sẻ cần phải cân nhắc. Đó là vấn đề điều khiển truy cập, đồng bộ
hóa, bảo vệ và bảo mật. Điều khiển truy xuất quyết định truy xuất nào được phép
với tài nguyên nào. Mô hình điều khiển truy xuất đòi hỏi phải kiểm tra mọi yêu cầu
truy xuất do các bộ xử lý đưa ra đối với bộ nhớ chia sẻ, ngược lại với nội dung của
bảng điều khiển truy xuất. Bộ xử lý cuối cùng chứa cờ báo hiệu sự hợp lệ của mỗi
lần thử truy xuất. Nếu có những yêu cầu truy xuất tài nguyên, thì trừ phi việc truy
cập kết thúc, tất cả sự truy cập không được phép và tiến trình không hợp lệ đều bị
chặn lại. Các yêu cầu của các tiến trình chia sẻ có thể làm thay đổi nội dung của
bảng điều khiển truy cập trong suốt quá trình thực hiện. Các cờ hiệu của bộ điều
khiển truy xuất với các luật đồng bộ hóa sẽ quyết định chức năng của hệ thống.
Đồng bộ hóa giới hạn thời lượng truy xuất của các tiến trình để có thể chia sẻ bộ
nhớ, bảo đảm cho thông tin lưu chuyển hợp lý và bảo đảm các chức năng của hệ
thống. Tiếp theo, vấn đề bảo vệ là một tính năng cần có của hệ thống, để ngăn chặn
các bộ xử lý cố tạo ra cảc truy xuất vào tài nguyên thuộc bộ xử lý khác. Chia sẻ và
bảo vệ là hai mặt trái ngược hẳn với nhau; chia sẻ nhằm cho phép truy cập, trong
khi đó bảo vệ nhằm để giới hạn nó.
Một hệ thống bộ nhớ đơn giản nhất bao gồm một bộ nhớ duy nhất được truy cập bởi
hai bộ xử lý. Các yêu cầu gửi tới module nhớ thông qua hai cổng giao tiếp của nó.
Một bộ trọng tài bên trong module nhớ sẽ truyền đi các yêu cầu này thông qua khối
điều khiển bộ nhớ. Nếu module nhớ đang rảnh và chỉ có một yêu cầu được gửi tới,
bộ trọng tài sẽ gửi yêu cầu đó tới khối điều khiển bộ nhớ và yêu cầu sẽ được thực
hiện. Ngay sau đó, module nhớ sẽ được đặt vào trạng thái bận khi yêu cầu đang
được đáp ứng. Nếu một yêu cầu mới lại gửi đến trong khi bộ nhớ đang bận thực
hiện một yêu cầu trước đó, bộ xử lý gửi yêu cầu mới đó sẽ phải duy trì yêu cầu đó
cho tới khi bộ nhớ được rỗi hoặc bộ xử lý có thể gửi lại yêu cầu vào một thời điểm
khác.


Các hệ thống bộ nhớ phân tán là một lớp các bộ xử lý trong đó mỗi bộ xử lý đều có
thể truy cập vào bộ nhớ cục bộ của riêng nó. Khác với những hệ thống bộ nhớ chia
sẻ, truyền thông trong hệ thống truyền thông điệp được thực hiện thông qua thao tác
Send và Receive. Mỗi một node trong một hệ thống như vậy bao gồm một bộ xử lý
và bộ nhớ cục bộ của nó. Các nốt có thể lưu trữ các thông điệp trong bộ nhớ trung
gian buffer (những vị trí bộ nhớ tạm thời nơi các thông điệp đợi cho đến khi chúng
được nhận hoặc gửi đi). Các node cũng có thể thực hiện các thao tác Send/Receive
cùng một lúc trong khi đang xử lý. Công việc xử lý thông điệp cùng một lúc và giải
quyết các vấn đề khác được thực hiện bởi hệ điều hành phía dưới. Các bộ xử lý
không chia sẻ một bộ nhớ chung mà mỗi bộ xử truy cập vào không gian địa chỉ
riêng của chúng. Các đơn vị xử lý của hệ thống truyền thông điệp có thể được kết
nối với nhau bằng nhiều cách như cấu trúc tương kết có kiến trúc chuyên dụng

Đề tài “Tối ưu hóa trong thiết kế bộ xử lý số song song”

tr 24/106


Luận văn thạc sỹ

Nguyễn Đức Tiến

(architecture specific interconnection structure) đến các mạng phân bố theo địa lý
(geographically dispersed networks). Về nguyên tắc phương thức truyền thông điệp
có thể mở rộng ở quy mô lớn. Khi nói đến mở rộng, tức là ta có thể tăng số lượng
bộ xử lý lên mà không làm giảm nhiều tính hiệu quả của hoạt động.
Hệ thống truyền thông cục bộ giữa những bộ đa xử lý truyền thông điệp sử dụng
các dạng mạng tĩnh, trong đó quan trọng là mạng hypercube đã gây được sự chú ý
rất nhiều trong nhiều năm. Các mạng lưới mesh hai và ba chiều lân cận gần nhất
cũng đã được sử dụng trong các hệ thống truyền thông điệp. Có 2 yếu tố mà chúng