Luận văn Xử lý song song
1
MỞ ĐẦU
Hiện nay, với sự xuất hiện ngày càng nhiều các hệ thống điện tử đã làm cho lượng
thông tin trong mọi lĩnh vực phát triển nhanh chóng, có cấu trúc đa dạng và phức tạp.
Đặc biệt, trong lĩnh vực xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh, dự báo thời tiết,
v.v. đòi hỏi máy tính phải xử lý một lượng dữ liệu rất lớn, với tốc độ cao. Có thể nói
rằng những máy tính xử lý tuần tự kiểu Von Neumann khó có thể đáp ứng được yêu
cầu về thời gian và khối lượng công việc thực hiện. Điều này dẫn tới là muốn tăng được
khả năng tính toán của các hệ thống máy tính thì đích cuối cùng là phải khai thác được
khả năng xử lý song song của chúng.
Xử lý song song liên quan trực tiếp đến kiến trúc song song và giải thuật song
song. Gần đây, với sự phát triển của máy tính song song và nhờ các giải thuật song
song hợp lý đã làm thay đổi nhiều quan niệm về khả năng giải được trong thực tế của
những bài toán khác nhau. Nhiều thuật toán trước đây không thể chấp nhận vì khối
lượng tính toán quá lớn thì ngày nay lại hoàn toàn khả thi và có hiệu lực lớn. Các bài
toán phức tạp trong lĩnh vực toán học đã có thuật toán hữu hiệu để giải nó.
Với yêu cầu trên, mục đích của luận văn là nghiên cứu các kiến trúc của máy tính
song song, các mô hình và các thuật toán trong xử lý song song. Trên cơ sở đó đề tài sẽ
khai thác và áp dụng các giải thuật song song cho việc tìm nghiệm một số bài toán phi
tuyến nhằm cải thiện đáng kể thời gian và tốc độ tính toán.
Nội dung của đề tài được phân thành 3 chương. Chương 1, sẽ giới thiệu tổng quan
về máy tính song song nhằm đưa ra cấu trúc và phân loại, đánh giá các kiến trúc song
song đang sử dụng trong thực tế. Chương 2, áp dụng các kiến trúc song song để đưa ra
các mô hình lập trình và các nguyên lý thiết kế giải thuật song song. Chương cuối cùng,
là phần trọng tâm của đề tài, áp dụng các kiến trúc, mô hình lập trình và giải thuật song
song để phân tích và cài đặt một số lớp giải bài toán phi tuyến.
2
CHƯƠNG I
TỔNG QUAN VỀ MÁY TÍNH SONG SONG
I.1 Giới thiệu chung
Tại sao phải xử lý song song?
Nhiều lĩnh vực mới như đồ họa máy tính, trí tuệ nhận tạo, phân tích số, v.v. đòi hỏi
phải xử lý một khối lượng dữ liệu rất lớn do đó cần phải có những hệ thống máy tính
thật mạnh mới thực hiện được những yêu cầu trong thực tế. Những vấn đề về xử lý
ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều (3-D), dự báo thời tiết, mô hình và
mô phỏng những hệ thống lớn, v.v. đều đòi hỏi phải xử lý dữ liệu với tốc độc rất cao,
với khối lượng dữ liệu rất lớn. Hầu hết những bài toán này, những máy tính xử lý tuần
tự kiểu Von Neumann là không đáp ứng yêu cầu.
Mặc dù tốc độ xử lý của các bộ xử lý (BXL) tăng nhưng khả năng tính toán của
chúng không thể tăng mãi được do giới hạn về vật lý. Điều này dẫn tới là muốn tăng
được khả năng tính toán của các hệ thống máy tính thì đích cuối cùng là phải khai thác
được khả năng xử lý song song của chúng.
Ngày càng xuất hiện nhiều bài toán mà những hệ thống đơn một bộ xử lý (BXL)
không đáp ứng được yêu cầu xử lý về thời gian, do đó đòi hỏi phải sử dụng những hệ
thống đa bộ xử lý và đòi hỏi phải xử lý song song.
Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và
cùng tham gia giải quyết một vấn đề, nói chung là thực hiện trên những hệ thống đa bộ
xử lý [14].
Khái niệm xử lý song song khác với tuần tự:
1. Trong tính toán tuần tự với một BXL thì mỗi thời điểm thực hiện được một phép toán.
2. Trong tính toán song song thì một số BXL cùng kết hợp với nhau để giải quyết
3
cùng một vấn đề cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể có nhiều
phép toán được thực hiện đồng thời.
Câu hỏi đặt ra là vấn đề xử lý song song hiện nay có hiện thực hay không? Câu trả
lời là khẳng định. Ba yếu tố chính dẫn đến việc xử lý song song:
1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây dựng
những hệ thống có nhiều BXL với giá thành hợp lý.
2. Sự phát triển của công nghệ mạch tích hợp VLSI cho phép tạo ra những hệ phức
hợp có hàng triệu transistor trên một chip.
3. Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới hạn,
không thể cải tiến thêm được do vậy dẫn tới đòi hỏi phải thực hiện xử lý song song.
Những yếu tố trên thúc đẩy các nhà nghiên cứu phải tập trung khai thác công nghệ
xử lý song song và tận dụng chúng để giải quyết những bài toán ứng dụng quan trọng
của thực tế.
Vấn đề xử lý song song liên quan trực tiếp đến:
Kiến trúc máy tính,
Phần mềm hệ thống (hệ điều hành),
Thuật toán,
Ngôn ngữ lập trình, v.v.
Một máy tính song song là tập hợp các BXL, thường là cùng một loại, kết nối với
nhau theo một cách nào đó để có thể hợp tác với nhau trong hoạt động và trao đổi dữ
liệu được với nhau [12].
Các máy tính song song có thể phân thành nhiều loại dựa vào kiểu và số lượng các
BXL, sự kết nối giữa chúng, dựa vào sơ đồ truyền thông và các thao tác vào/ra, v.v.
Phần lớn các hệ điều hành ngày nay đều đã hỗ trợ đa xử lý / đa nhiệm và cho phép
nghiên cứu, khai thác các phương pháp lập trình song song. Nhưng điều quan trọng là
nhiều BXL phải tham gia "cùng giải một bài toán". Nói cách khác, những tiến trình
thực hiện trên mỗi BXL phải kết hợp, trao đổi với nhau để giải quyết một bài toán cho trước.
4
Trường hợp ngược lại không phải là xử lý song song. Ví dụ, nếu một đơn vị dịch
chương trình File1.a và một đơn vị khác dịch chương trình File2.a thì không được
xem là xử lý song song vì hai công việc đó hoàn toàn độc lập với nhau. Nhưng nếu một
đơn vị đang dịch một phần của chương trình File.a và một đơn vị khác lại dịch một
phần khác của cùng chương trình thì đó là sự xử lý song song.
Một trong các mục đích chính của xử lý song song là nghiên cứu, xây dựng những
thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa là phát triển các thuật
toán song song. Câu hỏi tự nhiên là đánh giá một thuật toán song song như thế nào
được gọi là thích hợp cho xử lý song song? Đối với thuật toán tuần tự thì chúng ta
thống nhất cách đánh giá dựa vào thời gian thực hiện thuật toán, không gian bộ nhớ và
khả năng lập trình, v.v. Đánh giá thuật toán song song thì phức tạp hơn nhiều, ngoài
những tiêu chuẩn trên còn bổ sung thêm những tham số về số bộ xử lý, khả năng của
các bộ nhớ cục bộ, sơ đồ truyền thông, các giao thức đồng bộ hoá, v.v.
Để cài đặt các thuật toán song song trên các máy tính song song chúng ta phải sử
dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình song song đang
được sử dụng như: Fortran 90, nCUBE C, Occam, C-Linda, PVM với C/C++, CDC
6600, v.v.
I.2 Phân loại các kiến trúc máy tính
Dựa vào các đặc tính về số lượng BXL, số chương trình thực hiện, cấu trúc bộ nhớ,
v.v., Michael Flynn (1966) [20] đã đưa ra cách phân loại nổi tiếng được nhiều người
chấp nhận.
I.2.1 Mô hình SISD: Đơn luồng lệnh, đơn luồng dữ liệu
Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ
đọc, ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi register được gọi là
bộ đếm chương trình (program counter) được sử dụng để nạp địa chỉ của lệnh tiếp theo khi
xử lý tuần tự và kết quả là thực hiện theo một thứ tự xác định của các câu lệnh. Hình 1-1 mô
tả hoạt động của máy tính theo mô hình SISD.
5
Tín hiệu
điều khiển
Đơn vị
BXL số
điều khiển
học
Luồng
dữ liệu
Luồng
kết quả
Luồng lệnh
Bộ nhớ
Hình 1-1 Mô hình của kiến trúc SISD
Mô hình SISD còn được gọi là SPSD, đơn chương trình và đơn luồng dữ liệu. Đây
chính là mô hình máy tính truyền thống kiểu Von Neumann.
I.2.2 Mô hình SIMD: Đơn luồng lệnh, đa luồng dữ liệu
Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý
(nhiều hơn một đơn vị) thực hiện theo một luồng các câu lệnh. CPU phát sinh tín hiệu
điều khiển tới tất cả các phần tử xử lý, những BXL này cùng thực hiện một phép toán
trên các mục dữ liệu khác nhau, nghĩa là mỗi BXL có luồng dữ liệu riêng. Máy tính
SIMD có thể hỗ trợ xử lý kiểu vector, trong đó có thể gán các phần tử của vector cho
các phần tử xử lý để tính toán đồng thời. Máy tính vector và các BXL mảng là mô hình
chủ yếu thuộc loại này. Hình 1-2 mô tả hoạt động của máy tính theo mô hình SIMD,
còn được gọi là SPMD.
Đơn vị điều khiển (CU)
Tín hiệu
Tín hiệu
điều khiển
điều khiển
Phần tử
xử lý 1
Phần tử
xử lý 2
Phần tử
xử lý n
. . .
Hình 1-2 Mô hình của kiến trúc SIMD
Mô hình SIMD còn được gọi là SPMD, đơn chương trình và đa luồng dữ liệu. Đây
chính là mô hình máy tính phổ biến có trên thị trường như: ILLIAC IV, DAP và Conn-
ection Machine CM-2.
6
I.2.3 Mô hình MISD: Đa luồng lệnh, đơn luồng dữ liệu
Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện nhiều
chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn được gọi là MPSD (đa
chương trình, đơn luồng dữ liệu). Kiến trúc kiểu này có thể chia thành hai nhóm:
▪
Lớp các máy tính yêu cầu những đơn vị xử lý (PU) khác nhau có thể nhận được
những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến trúc
khó và hiện nay chưa có loại máy tính nào được sản xuất theo loại này.
▪ Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU liên
tiếp. Đây là loại kiến trúc hình ống thực hiện xử lý theo vector thông qua một dãy các
bước, trong đó mỗi bước thực hiện một chức năng và sau đó chuyển kết quả cho PU
thực hiện bước tiếp theo. Hoạt động của máy tính theo kiến trúc loại này giống như hệ
tuần hoàn nên còn được gọi là hệ tâm thu. Hình 1-3 mô tả hoạt động của máy tính theo
Luồng lệnh 1
mô hình MISD
Phần tử
xử lý 1
Phần tử
xử lý 2
Luồng lệnh 2
Luồng
dữ liệu
.
.
.
.
Luồng lệnh n
Phần tử
xử lý n
Hình 1-3 Mô hình của kiến trúc MISD
I.2.4 Mô hình MIMD: Đa luồng lệnh, đa luồng dữ liệu
Máy tính loại MIMD còn gọi là đa BXL, trong đó mỗi BXL có thể thực hiện những
luồng lệnh (chương trình) khác nhau trên các luồng dữ liệu riêng.
Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào được
bộ nhớ chung (global) khi cần, do vậy giảm thiểu được sự trao đổi giữa các BXL trong hệ thống.
Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao
nhất và đã có nhiều máy tính được sản xuất theo kiến trúc này, ví dụ: BBN Butterfly,
7
Alliant FX, iSPC của Intel, v.v. Mô hình của kiến trúc MIMD được mô tả như hình 1-4.
Luồng dữ
liệu 1
Luồng lệnh 1
Luồng lệnh 2
Phần tử
xử lý 1
CU 1
CU 2
Luồng dữ
liệu 2
Phần tử
xử lý 2
.
.
.
.
Luồng dữ
liệu n
Luồng lệnh n
Phần tử
CU n
xử lý n
Hình 1-4 Mô hình của kiến trúc MIMD
I.3 Kiến trúc máy tính song song
Theo sự phân loại của Flynn thì có hai họ kiến trúc quan trọng cho các máy tính
song song đó là SIMD và MIMD. Những kiến trúc khác có thể xếp theo hai mẫu đó.
Mẫu hình các kiến trúc xử lý song song có thể phân chia như hình 1-5.
Multiprocessor
MIMD
Multicomputer
Data Flow Machine
Array Processor
SIMD
MISD
Pipelined Vector Processor
Pipelined Vector Processor
Systolic Array
SIMD-MIMD
MIMD-SIMD
Hybrid
Hình 1-5 Các mẫu hình kiến trúc xử lý song song
Những kiến trúc khác nhau có thể tạo ra những khả năng khác nhau cho việc xử lý
song song. Ngay trong kiến trúc tuần tự chúng ta cũng có thể tận dụng tốc độ cực nhanh
của các bộ xử lý để thực hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia
sẻ tài nguyên. Tất nhiên đối với những kiến trúc máy tính song song thì mục đích chính
8
là khai thác triệt để khả năng của kiến trúc song song để viết các chương trình song song.
I.3.1 Song song hóa trong máy tính tuần tự
Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của
các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế.
Nhưng cấu trúc phần cứng thường là trong suốt đối với những người lập trình. Sau đây
chúng ta tìm hiểu về kỹ thuật song song áp dụng trong các máy tính có một BXL.
Đa đơn vị chức năng
Hầu hết các máy tính truyền thống chỉ có một đơn vị số học và logic (ALU) trong
BXL. Ở mỗi thời điểm nó chỉ có thể thực hiện một chức năng.
Nhiều máy tính thực tế hiện nay có thể có nhiều đơn vị chức năng (nhất là những
chức năng chuyên biệt) và những đơn vị này có thể thực hiện song song được. Ví dụ
như trong họ vi xử lý Intel 80XXX có bộ đồng xử lý 80387 làm việc với 80386 hay
80486.
Bộ vi xử
lý 80386
Bộ đồng
vi xử lý
Bộ nhớ
chính
Các cổng
vào / ra
Bus hệ thống (dữ liệu, địa chỉ, điều khiển)
Hình 1-6 Kết nối bộ đồng xử lý.
Bộ đồng xử lý chỉ thực hiện các chức năng riêng biệt ví dụ như khối đồ hoạ
(Graphics Unit), khối xử lý tín hiệu (Signal processing Unit), khối xư lý ảnh (Image
processing Unit), khối xử lý ma trận, vectơ (Vector and Matrix processor), khối xử lý
dấu phẩy động (FPU: Floating Point Unit).v.v. Các khối này có thể thực hiện đồng thời
và có tốc độ nhanh hơn rất nhiều so với bộ xử lý chính. Các bộ vi xử lý công nghệ cao
hiện nay có thể cấy một vài khối chức năng đặc biệt (SFU: Special Function Unit ) này
vào bên trong chip bộ xử lý nhằm giảm tối thiểu thời gian trễ do giao tiếp với SFU và
như vậy sẽ làm tăng tốc độ thực hiện các phép xử lý trên chúng. Hoặc máy CDC 6600
9
(thiết kế năm 1964) có 10 đơn vị chức năng được tổ chức trong một BXL. Những đơn
vị chức năng này độc lập với nhau và do vậy có thể thực hiện đồng thời. Thường đó là
các đơn vị thực hiện các phép toán rất cơ bản như: phép cộng, nhân, chia, tăng giảm,
các phép logic và các phép dịch chuyển (shift). Với 10 đơn vị chức năng và 24 thanh
ghi (register), máy tính CDC 6600 có thể thực hiện tính toán với tốc độ tăng lên đáng
kể, đáp ứng được nhiều bài toán xử lý song song.
Vấn đề chính đối với những máy tính loại này là cần phải xây dựng bộ lập lịch tối
ưu để phân chia các câu lệnh thực hiện sao cho tận dụng được tối đa các đơn vị chức
năng cũng như các tài nguyên mà máy tính cung cấp.
Xử lý theo nguyên lý hình ống trong CPU
Nhiều pha thực hiện khác nhau của các câu lệnh có thể thực hiện theo nguyên lý
hình ống, ví dụ như một đường ống lệnh được tổ chức gồm 5 phân đoạn: nạp câu lệnh
về từ bộ nhớ, giải mã (decode), xác định các toán hạng, thực hiện các phép số học/logic
và lưu trữ kết quả. Khi lệnh thứ nhất bắt đầu bước vào thực hiện ở giai đoạn thứ hai thì
mã lệnh của lệnh tiếp theo được đọc từ bộ nhớ ra để thực hiện bước một. Bằng cách
thực hiện như trên thì trong quá trình thực hiện của bộ xử lý có thể thực hiện được
nhiều câu lệnh gối đầu nhau trong cùng một thời gian giống như dòng nước chảy trong
đường ống.
Những câu lệnh trong chương trình có thể thực hiện gối đầu nhau theo nguyên lý
hình ống và nó sẽ hiệu quả hơn khi dựa vào kỹ thuật tạo ra vùng đệm dữ liệu.
Sự gối đầu CPU và các thao tác vào/ra (I/O)
Nhiều phép vào/ra có thể thực hiện đồng thời đối với nhiều nhiệm vụ tính toán
khác nhau bằng cách sử dụng những bộ điều khiển vào/ra, các kênh hay những BXL
vào/ra khác nhau.
Trong các máy tính hiện nay có nhiều bộ điều khiển thiết bị vào/ra, cho phép đa xử
lý vào/ra do vậy tăng được tốc độ trao đổi dữ liệu giữa các thiết bị ngoài với CPU.
Các hệ thống bộ nhớ phân cấp
Tốc độ các phép toán thực hiện trong BXL nhanh hơn rất nhiều việc truy cập vào
10
bộ nhớ và tốc độ truy cập vào bộ nhớ nguyên thủy (bộ nhớ trong) nhanh hơn đối với
bộ nhớ phụ (bộ nhớ ngoài).Hệ thống bộ nhớ phân cấp như thế có thể mô tả như hình1-7
CPU (Registers)
Tăng về tốc độ
Cache
truy cập
Main Memory
Fixed Disks, Drum
Tăng khả năng
lưu trữ
Magnetic Tapes
Hình 1-7 Hệ thống bộ nhớ phân cấp
Các thanh ghi được sử dụng trực tiếp cho ALU. Bộ nhớ cache được xem như vùng
đệm giữa BXL và bộ nhớ chính. Sự song song hóa trong sự trao đổi dữ liệu theo cấu
trúc phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ thống. Ví dụ,
trong khi dữ liệu được chuyển từ bộ nhớ phụ vào bộ nhớ chính thì đồng thời có thể
chuyển dữ liệu từ cache vào cho CPU.
Đa chương trình và chia sẻ thời gian
Các hệ điều hành của máy tính đơn bộ xử lý cho phép thực hiện song song dựa vào
cách tiếp cận phần mềm.
Trong cùng một khoảng thời gian, có nhiều tiến trình cùng truy cập vào dữ liệu từ
những thiết bị vào/ra chung. Chúng ta biết rằng phần lớn các chương trình đều có hai
phần: phần vào/ra và các thành phần tính toán trong quá trình xử lý. Các hệ điều hành
đa chương trình xáo trộn sự thực hiện của nhiều chương trình các loại khác nhau nhằm
cân bằng giải băng thông thực hiện của các đơn vị chức năng.
Trong một hệ đa chương trình, một tiến trình tính toán với cường độ cao có thể cắt
ngang để tạm thời chiếm dụng CPU trong khi một tiến trình trước đó không đòi hỏi
11
phải kết thúc công việc. Để tránh việc bị chặn lại (blocking) của các thiết bị thì khái
niệm chia sẻ thời gian (Time-sharing) được sử dụng. Bộ lập lịch chia sẻ thời gian làm
nhiệm vụ phân chia (gán) CPU cho mỗi tiến trình một khoảng thời gian cố định theo
phương pháp quay vòng tròn. Bằng cách đó, tất cả các tiến trình đều được sẵn sàng để
thực hiện trên cơ sở được phép sử dụng CPU và những tài nguyên khác một cách có cạnh tranh.
Vấn đề chia sẻ thời gian cho nhiều tiến trình làm nảy sinh khái niệm các BXL ảo.
Nghĩa là, mỗi tiến trình được cung cấp một môi trường được xem như một BXL ảo để
thực hiện riêng cho tiến trình đó.
Do vậy, về nguyên tắc việc phát triển những chương trình song song trên máy đơn
BXL thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực hiện, nghĩa là
có thể xem hệ thống như là đa bộ xử lý.
I.3.2 Mô hình trừu tượng của máy tính song song
Thông thường khi xây dựng các thuật toán song song, chúng ta qui ước là phát triển
thuật toán cho mô hình trừu tượng này, sau đó ánh xạ sang những máy tính cụ thể với
một số các ràng buộc nào đó.
Máy tính truy cập ngẫu nhiên song song P-RAM chứa một đơn vị điều khiển, bộ
nhớ chung và một tập không giới hạn các BXL, mỗi BXL lại có bộ nhớ riêng (hình 1-8).
CU
BXL n
BXL 2
BXL 1
. . .
Mạng kết nối
Bộ nhớ chung chia sẻ
hoặc kênh truyền thông
Hình 1-8 Máy tính P-RAM
12
Mỗi BXL có một chỉ số duy nhất được sử dụng để xác định địa chỉ trong quá trình
trao đổi các tín hiệu và quản lý các ngắt. Tất cả các BXL đều chia sẻ bộ nhớ chung với
yêu cầu không bị giới hạn. Các câu lệnh có thể bắt đầu thực hiện ở bất kỳ thời điểm
nào, ở bất kỳ vị trí nào của bộ nhớ (riêng hoặc chung).
Đây là mô hình tổng quát cho máy tính song song kiểu MIMD. Về nguyên tắc, mô
hình này cho phép thực hiện nhiều luồng lệnh đồng thời trên nhiều BXL khác nhau.
Sau đây là một số điểm cần lưu ý khi phát triển những thuật toán cho các máy tính
song song tổng quát.
▪ Không bị giới hạn về số lượng BXL
▪ Mọi vị trí của bộ nhớ đều truy cập được bởi bất kỳ BXL nào
▪ Không giới hạn về dung lượng bộ nhớ chia sẻ trong hệ thống
▪ Các BXL có thể đọc bất kỳ một vị trí nào của bộ nhớ, nghĩa là không cần phải
chờ để những BXL khác kết thúc công việc truy cập vào bộ nhớ.
Khi chuyển những thuật toán được xây dựng cho máy tính song song tổng quát
sang máy tính cụ thể (lập trình song song) thì phải áp dụng một số các ràng buộc để
đảm bảo chương trình thực hiện được trên những máy tính đó. Về hình thức, chúng ta
thực hiện một trong những điều kiện sau:
▪ EREW: loại trừ vấn đề xung đột đọc / ghi
▪ CREW: cho phép đọc đồng thời, nhưng không cho phép xung đột khi ghi
▪ CRCW:Chophépđọc,ghiđồngthời.Tấtnhiênmôhìnhcholoạinàyítcógiátrịthựctiễn.
Tiếp theo, chúng ta nghiên cứu một số kiến trúc máy tính song song đã có trên thị
trường làm cơ sở để thực hiện lập trình sau này.
I.3.3 Kiến trúc SIMD
Trong máy tính SIMD, tất cả các phần tử xử lý đều được điều hành bởi một đơn vị
điều khiển (CU). Tất cả các đơn vị xử lý nhận được cùng một lệnh từ CU nhưng hoạt
động trên những tập dữ liệu khác nhau. Mô hình máy tính SIMD được chỉ ra như hình
1-9 có những đặc tính sau:
13
▪ Phân tán việc xử lý trên nhiều phần cứng
▪ Thao tác đồng thời trên nhiều phần tử dữ liệu
▪ Thực hiện cùng một tính toán trên tất cả các phần tử dữ liệu.
Luồng dữ
liệu 1
Phần tử
xử lý 1
Tín hiệu
điều khiển
Đơn vị
điều khiển
Luồng dữ
liệu 2
Phần tử
xử lý 2
.
.
Luồng lệnh
Luồng dữ
liệu n
Phần tử
xử lý n
Kết quả
Bộ nhớ
Hình 1-9 Mô hình kiến trúc SIMD
Xử lý theo mảng là dạng xử lý song song đầu tiên được nghiên cứu và cài đặt ứng
dụng. Có hai loại máy tính xử lý theo mảng [20]:
▪ Những máy tính thực hiện các phép toán trên các bit, ví dụ MPP (Massively
Parallel Processor), CM-1, CM-2, v.v.
▪ Những máy tính thực hiện các phép toán trên các từ (word), ví dụ ILLIAC IV, DAP, v.v.
I.3.4 Kiến trúc MISD
BXL hình ống chính là BXL kiểu MISD làm việc theo nguyên lý hình ống.
Nguyên lý hình ống (pipelined) dựa vào phương pháp phân đoạn hoặc chia nhỏ một
tiến trình tính toán thành một số đoạn nhỏ hơn để thực hiện trong các pha liên tiếp. Tất
cả các giai đoạn của một tiến trình được thực hiện tuần tự, sẽ truyền kết quả cho pha
tiếp theo. Như vậy, trong cách thực hiện theo nguyên lý hình ống, khi một giai đoạn
công việc đang thực hiện thì một giai đoạn khác có thể nạp dữ liệu vào, và dữ liệu vào
của giai đoạn này có thể là kết quả của giai đoạn trước nó.
Ví dụ, hình 1-10 mô tả một tiến trình được phân thành 4 giai đoạn thực hiện tuần
14
tự, nhưng có thể thực hiện song song theo nguyên lý hình ống để tăng tốc độ tính toán
khi phải thực hiện nhiều tiến trình như thế.
Một tiến trình được chia thành 4 giai đoạn:
Pha 1
Pha 2
Pha 3
Pha 4
Thực hiện tuần tự hai tiến trình phải qua 8 giai đoạn:
Pha 1
Pha 2
Pha1
Pha 3
Pha 4
Pha2
Pha3
Pha4
Thực hiện theo hình ống hai tiến trình trên chỉ cần trải qua 5 giai đoạn:
Pha 1
Pha 2
Pha 1
Pha 3
Pha 2
Pha 4
Pha 3
Pha 4
Hình 1-10 Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai đoạn
Nếu ký hiệu Si là thời gian cần thiết để thực hiện giai đoạn thứ i thì:
Tổng thời gian tính toán tuần tự là: 2 * (S1 + S2 + S3+ S4)
Tổng thời gian tính toán hình ống là: S1 + S2 + S3+ S4 + S4
Nguyên lý hình ống có thể áp dụng theo hai mức:
▪ Hình ống theo đơn vị số học: Các đơn vị số học và logic ALU được tổ chức thành
mảng, các phép toán bên trong được thực hiện theo nguyên lý hình ống (hình 1-11 (a)).
▪ Hình ống theo đơn vị câu lệnh: Các đơn vị điều khiển CU được phân đoạn và tổ
chức theo hình ống (hình 1-11 (b)).
CU
CU
. . .
ALU
CU
ALU
. . .
CU
ALU
ALU
Bộ nhớ
Bộ nhớ
Hình 1-11 (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU
15
Như chúng ta đã biết, việc xử lý theo hình ống được sử dụng để thực hiện gối đầu
nhiều pha thực hiện các câu lệnh liên tiếp và sự truyền thông dữ liệu. Do vậy có thể xây
dựng hình ống vòng tròn giữa các BXL, bộ nhớ và mạng liên kết như sau:
Read
Network
Shared
Memory
Shared
Memory
Write
Network
Hình 1-12 Ví dụ về một hình ống vòng tròn
Các phép toán thực hiện bởi CU theo kiến trúc này có thể chia thành 5 giai đoạn:
Giai đoạn 1. Đọc dữ liệu: đọc dữ liệu từ bộ nhớ chia sẻ.
Giai đoạn 2. Chuyển tải dữ liệu: chuyển dữ liệu từ bộ nhớ tới các phần tử xử lý PE
thông qua mạng đọc (Read Network).
Giai đoạn 3. Thực hiện câu lệnh: sử dụng PE để thực hiện các câu lệnh.
Giai đoạn 4. Chuyển tải dữ liệu: chuyển các kết quả từ các PE tới bộ nhớ thông qua
mạng ghi (Write Network).
Giai đoạn 5. Lưu trữ dữ liệu : ghi lại các kết quả vào bộ nhớ chia sẻ.
Nói chung, nguyên lý hình ống cho phép nhiều thao tác gối đầu nhau thực hiện
đồng thời và hỗ trợ để khai thác được khả năng của kiến trúc song song theo các mức
khác nhau.
▪ Mức câu lệnh. Từng câu lệnh chuyển vào cho một đoạn trong chu trình thực hiện
sao cho sau khi đưa các lệnh vào hình ống thì chúng sẽ thực hiện lặp lại theo từng chu kỳ.
▪ Mức hệ thống con. Nhiều phép toán có thể thực hiện theo hình ống như ADD,
MUL, DIV, và SORT thường có trong nhiều kiến trúc của máy tính. Những phép toán
này được sử dụng theo hình ống rất thường xuyên.
▪ Mức hệ thống. Nhiều đoạn trong hình ống không cần phải thực hiện ở mức phần
cứng mà có thể ở mức phần mềm.
16
Kết quả nguyên lý hình ống đã được ứng dụng để thiết kế nhiều hệ máy tính như:
CDC STAR 100, Texas Instruments ASC, Cray 1, v.v.
I.3.5 Các bộ xử lý mảng tâm thu SAP
Năm 1978 Kung và Leiserson đề xuất một loại kiến trúc được gọi là mảng tâm thu
(Systolic Array) cho những tính toán đặc biệt. Đây là kết quả của dự án thực hiện ở
Carnegie-Mellon University và nó được ứng dụng nhiều trong thiết kế các mạch tích
hợp VLSI phục vụ chủ yếu cho việc xử lý tín hiệu và xử lý ảnh.
Mảng tâm thu viết tắt là SA, là một mảng các đơn vị xử lý được kết nối cục bộ với nhau.
Trong mảng tâm thu SA, mỗi PE được xem như một tế bào, một ô trong mảng, bao gồm:
▪ Một số thanh ghi (register)
▪ Một bộ cộng (adder)
▪ Các mạch điều khiển
▪ Đơn vị logic-số học ALU.
Dựa vào SA người ta xây dựng kiến trúc SAP
Dữ liệu vào
Systolic
Array
Host
Processor
Tín hiệu
Controller
Kết quả
Hình 1-13 Kiến trúc bộ xử lý mảng tâm thu
Dữ liệu được xử lý trong mỗi ô và được truyền sang cho ô các lân cận.
Trong kiến trúc SAP nêu trên, bộ điều khiển (Controller) làm nhiệm vụ giao diện
cho BXL chính (Host Processor) và gửi các tín hiệu điều khiển quá trình vào/ra dữ liệu
cho SA. Hoạt động của hệ thống theo từng nhịp và lặp lại một cách đều đặn để tận dụng
được khả năng song song của tất cả các phần tử xử lý.
SA có thể tổ chức theo nhiều cấu hình tôpô khác nhau. Hình 1-14 mô tả một số cấu
hình phổ biến của SA.
17
(a)
(b)
(c)
Hình 1-14 Một số cấu hình phổ biến của mảng tâm thu:
(a) mảng tuyến tính, (b) mảng hình tam giác, (c) mảng hai chiều hình vuông
Hiệu quả của SA phụ thuộc rất nhiều vào các đặc tính vào/ra của dữ liệu. Nó sẽ rất hiệu
quả đối với những bài toán mà số liệu đọc/ghi thực hiện với nhịp độ cao, đều đều và
liên tục như các bài toán xử lý ảnh, qui hoạch tuyến tính, v.v.
Ví dụ, xét bài toán nhân hai ma trận cỡ 2 2: A * B = C.
a11 a12
a21 a22
b11 b12
b21 b22
c11 c12
c21 c22
=
*
Hiển nhiên Cị = aik*bkj
Chúng ta có thể thiết kế SA có 9 PE để thực hiện nhân hai ma trận trên như sau:
a
a21
a
a
Nhập theo hàng
1
b
3
2
bb
4
5
8
6
Nhập theo cột
b
c
7
9
c
c
c11
Hình 1-15 Kiến trúc SA để thực hiện nhân hai ma trận
Hệ thống SAP thực hiện như sau:
18
Nhịp 1. Nhập b11, a11 vào ô số 1 và tính b11 * a11
Nhập b21 vào ô số 4 và a12 vào ô số 2
Nhịp 2. Truyền b11 từ ô 1 sang ô 2
Truyền a11 từ ô 1 sang ô 4 và tính a11 * b21
Truyền b11 từ ô 1 sang ô 2 và tính a12 * b11
Truyền b12 từ ô 4 sang ô 5 và a12 từ ô 2 sang ô 5 và
tính a12 * b21, đồng thời ở ô số 5 tính c11 = a12 * b11 + a12 * b21
Nhập tiếp b12 vào ô số 4 và a21 vào ô số 2
Nhịp 3. Truyền c11 từ ô 5 sang ô 9
Truyền a21*b11 từ ô 2 sang ô 6
Truyền b12 từ ô 5 sang ô 6
Nhập a22 vào ô 3, và nhập b22 vào ô 7
Nhịp 4: Truyền a22 từ ô 3 sang ô 6 và tính a22 * b21
cộng dồn với kết quả được chuyển từ ố số 2 sẽ cho
c21 = a21 * b11 + a22 * b21
Chuyển c11 từ ô 9 ra và gán cho c11
Tương tự đối với các trường hợp còn lại.
Năm 1986 Intel kết hợp với Kung đã xây dựng một hệ máy tính kiểu SAP đặt tên là
iWrap System, version sau được cải tiến vào năm 1990. Trong những năm 1990 còn có
seri máy tính loại mini-super của Convex Computer Corporation được xây dựng từ
những bộ CPU 64 bit được gắn với bộ nhớ chung.
I.3.6 Kiến trúc máy tính kiểu MIMD
Máy tính kiểu MIMD là loại đa BXL hoặc còn gọi là hệ thống đa máy tính, trong
đó mỗi BXL có đơn vị điều khiển (CU) riêng và thực hiện chương trình riêng của mình.
MIMD có những đặc trưng sau:
▪ Xử lý phân tán trên một số BXL độc lập
▪ Chia sẻ với nhau một số tài nguyên, trong đó có hệ thống bộ nhớ
19
▪ Mỗi BXL thao tác độc lập và có thể thực hiện đồng thời với nhau
▪ Mỗi BXL chạy một chương trình riêng.
Đã có những máy tính kiểu MIMD được sản xuất như:
(i) Intel iPSC Machine. Đây là những máy tính song song đầu tiên được tung ra thị
trường từ 1985 với ver. 1.0, ver. 2.0 (1987), sau đó là iPSC/860 (năm 1990). Hệ thống
có khoảng 64 nút và mỗi nút có các BXL 80386 /80387 với bộ nhớ từ 4 MB đến 16 MB.
(ii) Carnegie-Mellon Multi-Mini Processor. Hệ C.mmp được xây dựng từ 1971 ở
đại học Carnegie-Mellon gồm: 16 minicomputer được kết nối với 16 bộ nhớ thông qua
bộ nhớ liên kết chéo nhiều giai đoạn để tạo ra hệ MIMD chia sẻ bộ nhớ. Thế hệ tiếp
theo là Cm*.
I.4 Bộ nhớ
Một trong các thành phần quan trọng nhất của kiến trúc máy tính là bộ nhớ. Bộ nhớ
thường được chia thành n mức.
Bộ nhớ mức 1 là mức bộ nhớ cao nhất có dung lượng nhỏ nhất, nhanh và đắt nhất,
thường gắn chặt với mỗi BXL thành bộ nhớ cục bộ. Bộ nhớ mức 2 thường nhỏ hơn,
chậm hơn và rẻ hơn mức 1, v.v.
Về nguyên tắc, dữ liệu được chuyển đổi giữa các mức lân cận của các bộ nhớ và
hoàn toàn được điều khiển bởi bộ nhớ mức 1. Về lý thuyết, trong cấu trúc phân cấp bộ
nhớ, tốc độ truy cập bộ nhớ trung bình gần bằng tốc độ truy cập ở mức cao (mức 1),
nhưng chi phí của các đơn vị nhớ trung bình lại gần với giá của bộ nhớ ở mức thấp nhất (mức n).
Sau đây chúng ta xét một số mô hình bộ nhớ của các máy tính song song.
I.4.1 Bộ nhớ kết hợp
Bộ nhớ kết hợp (AM – Associative Memory) bao gồm các ô nhớ (cell) và logic kết
hợp. Mỗi ô nhớ của AM có 4 đầu vào và hai đầu ra như hình 1-16.
Các đầu vào (input) của mỗi ô nhớ bao gồm:
- Bit đối số a
- Bit đọc/ghi R/W xác định thao tác tương ứng cần thực hiện
20
- Bit khoá k
- Bit lựa chọn s để xác định ô nhớ thích hợp cho việc thực hiện đọc/ghi.
Hai kết quả ở đầu ra:
- Bit đối sánh m chỉ ra dữ liệu được lưu trong bộ nhớ có sánh được với bit đối số a.
- Bit kết quả ra q.
s
Chọn
k
q
Khoá
Kết quả
a
Đối số
Đọc/ghi
R/W
m
Đối sánh
Hình 1-16 Cấu trúc của ô nhớ AM
Tất cả các bộ nhớ AM được tổ chức thành các từ (word) và được xây dựng thành
mảng các ô giống nhau. Hình 1-17 mô tả một khối bộ nhớ AM có n từ và mỗi từ có m
bit. Mỗi ô trong số m * n ô nhớ và nó có một mạch vòng để so sánh đối số với giá trị
được lưu trữ trong các ô nhớ, đồng thời chỉ ra kết quả khi đối sánh thành công. Hệ
thống có thanh ghi lưu trữ đối số, một thanh ghi đánh dấu những trường của mỗi từ mà
bộ nhớ cần so sánh và thanh ghi đối sánh (các bít đối sánh) chỉ ra những từ tìm thấy.
Input
Input
Mask Register
Argument Register
Match Register
Tags
0
1
n-1
0
1
.
.
.
m-1
Buffer Register
Output
Hình 1-17 Cấu trúc của bộ nhớ kết hợp
21
I.4.2 Mô hình bộ nhớ truy cập ngẫu nhiên song song
Mô hình tính toán song song được biết dưới tên gọi PRAM bao gồm bộ nhớ chung
RAM với m vùng bộ nhớ đủ lớn để chia sẻ cho p bộ xử lý.
Bộ nhớ chung được sử dụng để lưu trữ dữ liệu và là vùng để trao đổi giữa các
BXL. Nó cho phép các BXL truy cập vào bộ nhớ đồng thời và có thể hoạt động một
cách dị bộ. Ví dụ, bộ xử lý Pi ghi dữ liệu vào một vùng nhớ và dữ liệu này có thể được
Pj truy cập, nghĩa là Pi và Pj có thể dùng bộ nhớ chia sẻ để trao đổi với nhau.
Mô hình loại này có các dạng sau:
1. Các phương thức truy cập bộ nhớ (Access Memory Primitives)
Có một số cách khác nhau để các BXL có thể đọc / ghi một số dữ liệu gối đầu
nhau. Đó là:
▪ Concurrent Read (CR): nhiều BXL có thể đọc đồng thời cùng một ô nhớ.
▪ Exlusive Read (ER): p BXL đọc được p vùng nhớ khác nhau. Mỗi BXL đọc
được chính xác một vùng nhớ và mỗi vùng nhớ được đọc bởi một BXL.
▪ Concurrent Write (CW): cùng một thời điểm cho phép nhiều BXL ghi vào
cùng một vùng nhớ.
▪ Exlusive Write (EW): p BXL ghi được vào p vùng nhớ khác nhau. Mỗi BXL
ghi được vào chính xác một vùng nhớ và mỗi vùng nhớ được ghi bởi một BXL.
Dễ nhận thấy rằng: ER, EW là trường hợp đăc biệt của CR và CW. Trong đó, CW là
cần phải chú ý nhất và người ta phân nó thành các loại như sau:
▪ Ghi đồng thời có ưu tiên (Priority CW): các BXL được gắn mức ưu tiên và khi
có nhiều BXL muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên cho BXL có mức ưu tiên
cao nhất. Các mức ưu tiên có thể gắn tĩnh hoặc động theo những qui tắc được xác định
khi thực hiện.
▪ Ghi chung đồng thời (Common CW): tất cả các BXL được phép ghi vào cùng
một vùng nhớ chỉ khi chúng ghi cùng một giá trị. Trong trường hợp này, một BXL
được chọn để ghi dữ liệu đó.
22
▪ Ghi tự do đồng thời (Arbitrary CW): một số BXL muốn ghi dữ liệu đồng thời
vào một vùng nhớ, nhưng chỉ một BXL được phép thay đổi giá trị của vùng nhớ đó.
Trong trường hợp này, chúng ta phải chỉ ra cách để lựa chọn BXL thực hiện.
▪ Ghingẫunhiênđồngthời(RandomCW):BXLđượclựachọnđểghidữliệulàngẫunhiên.
▪ Ghi tổ hợp đồng thời (Combining CW): tất cả các dữ liệu mà các BXL định ghi
đồng thời vào bộ nhớ được tổ hợp lại thành một giá trị. Giá trị này sẽ được ghi vào bộ nhớ đó.
2. Mô hình UMA của bộ nhớ chia sẻ
Trong mô hình này, tất cả các BXL làm việc nhờ cơ chế chuyển mạch tập trung
(Central switching) để điều khiển việc truy cập tới bộ nhớ chia sẻ. Thời gian truy cập
vào bộ nhớ là như nhau đối với mọi BXL, nghĩa là bộ nhớ là đồng nhất.
Có một số cách cài đặt cơ chế chuyển mạch như sau:
▪ Sử dụng đường dẫn chung (Common Bus)
▪ Lựa chọn chuyển mạch chéo (Crossbar Switch)
▪ Mạng nhiều giai đoạn (Multistage Network)
3. Mô hình NUMA của bộ nhớ chia sẻ
Ngược lại với cách tổ chức trên, ở đây bộ nhớ phân tán và được chia thành các đơn
thể độc lập. Bộ nhớ chia sẻ được phân tán cho tất cả các BXL thành bộ nhớ cục bộ
(local) và tuyển tập tất cả các đơn thể bộ nhớ tạo ra bộ nhớ chung cho các BXL. Các
BXL được phép truy cập đồng thời tới một hay nhiều đơn thể bộ nhớ và có thể hoạt
động ít nhiều độc lập với nhau.
Máy tính TC 2000 của BBN System và Technologies of Cambrige, Massachusett,
và máy tính Cedar System của đại học Illinois được xây dựng theo cấu trúc bộ nhớ
NUMA. TC 2000 có 128 BXL, mỗi BXL có 19 MB bộ nhớ nguyên thuỷ.
4. Kiến trúc bộ nhớ Cache-Only (COMA)
Bộ nhớ chính được phân tán và được chuyển thành bộ nhớ cache (cất giữ), tất cả
các bộ nhớ cache tạo ra không gian địa chỉ tổng thể.
Có một số máy tính đã được xây dựng theo kiến trúc này:
23
+ Data Diffusion Machine (DDM) của Swedish Institute of Computer Science (1990).
+ KSR-1 Machine của Kendall Square Research (1992).
5. Bộ nhớ đa máy tính
Mỗi nút trong hệ thống đa máy tính cũng chính là một máy tính có bộ nhớ riêng
không chia sẻ với những BXL khác. Các BXL trao đổi với nhau thông qua việc gửi và
nhận các thông điệp (message).
Việc trao đổi dữ liệu trong mạng là điểm - tới điểm (point – to – point) thông qua
sự liên kết tĩnh giữa các BXL.
Vậy, với sự phát triển của công nghệ phần cứng dẫn tới xu thế xử lý song song để
đáp ứng các yêu cầu tính toán của nhiều bài toán phức tạp trong thực tế. Nhiều máy
tính có kiến trúc song song ra đời như các loại máy tính kiểu SIMD, MISD, MIMD đã
tạo điều kiện cho công nghệ xử lý song song phát triển cả về mặt công nghệ lẫn triển
khai ứng dụng. Xử lý song song cũng có thể thực hiện được trên các máy tuần tự kiểu Von
Neumann bằng cách sử dụng nguyên lý xử lý hình ống hay chia sẻ thời gian, v.v.
Trọng tâm của chương này là tìm hiểu các kiến trúc, thành phần và mối quan hệ
của máy tính song song để tận dụng được hết khả năng xử lý song song của chúng. Các
bộ nhớ được tổ chức thành bộ nhớ kết hợp, bộ nhớ truy cập ngẫu nhiên, bộ nhớ chia sẻ,
v.v. là các mô hình chính cho máy tính song song. Vấn đề quan trọng trong thiết kế
kiến trúc của máy tính song song là xác định cách để kết nối các bộ xử lý với nhau sao
cho hoạt động hiệu quả nhất.
24
CHƯƠNG II
THUẬT TOÁN SONG SONG & LẬP TRÌNH SONG SONG
II.1 Thuật toán song song
II.1.1 Nguyên lý thiết kế thuật toán song song.
Như trên đã nêu, nói đến xử lý song song là phải xét cả kiến trúc máy tính lẫn các
thuật toán song song.
Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi
là thuật toán song song. Tổng quát hơn, thuật toán song song là một tập các tiến trình
hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết
hợp cùng giải một bài toán đặt ra.
Thuật toán song song có thể xem như là một tập hợp các đơn thể độc lập, một số
trong số chúng có thể thực hiện tương tranh trên máy tính song song.
Để thiết kế được các thuật toán song song cần phải trả lời các câu hỏi sau:
▪ Việc phân chia dữ liệu cho các tác vụ như thế nào?
▪ Dữ liệu được truy cập như thế nào, những dữ liệu nào cần phải chia sẻ?
▪ Phân các tác vụ cho các tiến trình (bộ xử lý) như thế nào?
▪ Các tiến trình được đồng bộ ra sao?
Có năm nguyên lý chính trong thiết kế thuật toán song song:
1. Các nguyên lý lập lịch: Tạo lịch trình để giảm tối thiểu các bộ xử lý sử dụng
trong thuật toán sao cho thời gian tính toán là không tăng (xét theo khía cạnh độ phức tạp).
2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một
dãy các thao tác {T1, T2, . . ., Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc.
3. Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối độc
lập với nhau và giải quyết chúng một cách song song.
4. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính
toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song.
25
5. Nguyên lý điều kiện tương tranh : Nếu hai tiến trình cùng muốn truy cập vào
cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có
thể cản trở lẫn nhau.
Ngoài những nguyên lý nêu trên, khi thiết kế thuật toán song song còn một số điểm
cần quan tâm.
▪
Tương tự như kiến trúc, hiệu quả thực hiện của thuật toán song song có thể rất
khác nhau, mà yếu tố quan trọng nhất ảnh hưởng tới độ phức tạp tính toán là cấu hình
tô pô liên kết mạng. Ví dụ: DAP là máy tính kiểu SIMD với 64 * 64 bộ xử lý, thời gian
nhân ma trận là tuyến tính theo kích cỡ của ma trận và phụ thuộc vào đường truyền dữ
liệu giữa các hàng với cột.
▪
Thuật toán song song phải được thiết kế dựa trên những kiến thức về kiến trúc
máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán.
II.1.2 Các cách tiếp cận trong thiết kế
Có ba cách tiếp cận để thiết kế thuật toán song song:
1. Thực hiện song song hoá những thuật toán tuần tự, biến đổi những cấu trúc
tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần
trong hệ thống xử lý.
2. Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song.
3. Xây dựng những thuật toán song song từ những thuật toán song song đã được
xây dựng cho phù hợp với cấu hình tôpô mạng và môi trường song song thực tế.
Như vậy, cách làm khá thông dụng là biến đổi các thuật toán tuần tự về song song,
hay chuyển từ một dạng song song về dạng song song phù hợp hơn sao vẫn bảo toàn
được tính tương đương trong tính toán. Do đó, khi biến đổi chúng ta cần trả lời hai câu hỏi:
1. Kiến trúc nào phù hợp cho bài toán?
2. Những bài toán loại nào sẽ xử lý hiệu quả trong kiến trúc song song cho trước?
26
Ví dụ: Những máy tính kiểu SIMD không thích hợp để giải các bài toán, trong đó
có nhiều tiến trình dị bộ. Ngược lại, máy tính kiểu MIMD lại không hiệu quả để giải
quyết những bài toán trong đó có nhiều tiến trình cần phải đồng bộ.
II.1.3 Một số phương pháp chuyển đổi từ chương trình tuần tự về song song
II.1.3.1 Sự phụ thuộc dữ liệu giữa các tiến trình trong chương trình
Như chúng ta đã biết, có rất nhiều phương pháp để chuyển đổi từ chương trình tuần
tự sang chương trình song song. Thế nhưng không phải bất kỳ chương trình tuần tự nào
chúng ta cũng có thể chuyển đổi sang chương trình song song một cách dễ dàng. Để
thực hiện được các khối lệnh song song chúng ta phải hiểu rõ và xác định được tất cả
các phụ thuộc dữ liệu của chúng trong chương trình, sau đó mô tả chúng thông qua đồ
thị phụ thuộc dữ liệu.
Đồ thị phụ thuộc dữ liệu là một đồ thị định hướng G=(V,E), trong đó V là tập các
lệnh trong chương trình, E là các phụ thuộc dữ liệu.
Ví dụ: Cho dãy lệnh S1, S2, S3 sau:
S1: A := B + C
S2: B := A + E
S3: A := A + B
Phân tích kỹ các câu lệnh trên chúng ta phát hiện ra một số sự phụ thuộc của chúng:
1. Lệnh S1 tính giá trị của biến A và biến này được sử dụng trong S2 và S3. Do vậy,
có sự phụ thuộc của S2, S3 vào S1 (ký hiệu là d1, d2).
2. Lệnh S2 tính giá trị của biến B và biến này được sử dụng trong S3. Do vậy, có
sự phụ thuộc của S3 vào S2 (ký hiệu là d3).
3. GiátrịtrướcđócủabiếnBđượcsửdụngởS1. Dovậy, cósựphụthuộcvàoS2 (kýhiệud4).
4. Cả hai lệnh S1 và S3 cùng tính giá trị của biến A và do vậy, có sự phụ thuộc (ký hiệu d5).
5. Lệnh S3 tính giá trị của biến A và biến này được sử dụng trong S2 và S3. Do
vậy, có sự phụ thuộc của S2, S3 vào S3 (ký hiệu là d6, d7).
27
Sự phụ thuộc dữ liệu giữa các câu lệnh S1, S2, S3 có thể được biểu diễn qua đồ thị
phụ thuộc dữ liệu như sau:
d6
d4
d5
d1
d3
S1
S2
d2
S3
d7
Hình 2-1 Đồ thị phụ thuộc dữ liệu giữa S1, S2, S3.
Trong chương trình chúng ta chỉ xét những sự phụ thuộc giữa các câu lệnh đơn. Có
5 loại phụ thuộc về mặt dữ liệu trong chương trình:
Xét dãy lệnh gồm 2 câu lệnh S1, S2.
Gọi: - DEF(S1) - tập tất cả các biến có giá trị bị thay đổi khi thực hiện câu lệnh S1.
- USE(S1) - tập tất cả các biến được truy cập (được sử dụng) khi thực hiện câu lệnh S1.
- DEF(S2) - tập tất cả các biến có giá trị bị thay đổi khi thực hiện câu lệnh S2.
- USE(S2) - tập tất cả các biến được truy cập (được sử dụng) khi thực hiện câu lệnh S2.
a. Phụ thuộc dòng dữ liệu (Data Flow Dependency): là sự phụ thuộc dữ liệu giữa S1
và S2 khi DEF(S1) ∩ USE(S2) ≠ . Đây là loại phụ thuộc rất chung và rất khó loại bỏ
bởi vì lệnh S2 yêu cầu giá trị của một biến và giá trị này phải được tính ở S1. Nghĩa là
khi xuất hiện phụ thuộc dòng dữ liệu giữa các câu lệnh thì chúng không thực hiện song
song được. Ví dụ: các phụ thuộc d1, d2, d3 là loại phụ thuộc dòng dữ liệu.
Quan hệ phụ thuộc dòng dữ liệu được ký hiệu là:
b. Phản phụ thuộc dữ liệu (Data Anti-Dependency): là sự phụ thuộc dữ liệu giữa S1
và S2 khi DEF(S2) ∩ USE(S1) ≠ . Đây là loại phụ thuộc ngược với loại phụ thuộc nêu
trên. Sự phụ thuộc này xuất hiện khi chúng ta sử dụng lại tên gọi của các biến, một biến
đã được sử dụng trong S1 và sau đó được định nghĩa lại ở S2. Nghĩa là khi xuất hiện
phản phụ thuộc dữ liệu giữa các câu lệnh thì chúng cũng không thực hiện song song
được. Ví dụ: các phụ thuộc d4, d6, d7 là loại phản phụ thuộc dữ liệu.
Quan hệ phản phụ thuộc dữ liệu được ký hiệu là:
28
c. Phụ thuộc dữ liệu ra (Data Output Dependency): là sự phụ thuộc dữ liệu giữa S1
và S2 khi DEF(S2) ∩ DEF(S1) ≠ . Sự phụ thuộc này xuất hiện do hai nguyên nhân: thứ
nhất sử dụng lại tên của các biến (dùng chung), thứ hai tính tăng giá trị của cùng một
biến. Nếu những lệnh này thực hiện đồng thời thì chúng sẽ ghi đè các giá trị vào cùng
một ô nhớ. Do vậy, cần phải xác định chính xác thứ tự thực hiện để ngăn ngừa việc sử
dụng những giá trị không đúng. Ví dụ: các phụ thuộc d5 là loại phụ thuộc dữ liệu ra.
Quan hệ phụ thuộc dữ liệu ra được ký hiệu là:
d. Phụ thuộc dữ liệu vào (Data Input Dependency): là sự phụ thuộc dữ liệu giữa S1
và S2 khi USE(S2) ∩ USE(S1) ≠ . Bởi vì các lệnh này chỉ truy cập (đọc) và không làm
thay đổi giá trị của các biến đó, do vậy các lệnh này có thể thực hiện theo bất kỳ thứ tự
nào cũng được, nghĩa là có thể thực hiện song song.
Quan hệ phụ thuộc dữ liệu vào được ký hiệu là:
e. Phụ thuộc điều khiển dữ liệu ( (Data Control Dependency): là sự phụ thuộc dữ
liệu giữa S1 và S2 khi sự thực hiện của lệnh này phụ thuộc vào giá trị của các biến được
tính ở lệnh kia.
Quan hệ phụ thuộc điều khiển dữ liệu được ký hiệu là:
II.1.3.2 Một số phương pháp để loại bỏ sự phụ thuộc dữ liệu giữa các tiến trình
Sự phụ thuộc giữa các câu lệnh đơn trong dãy lệnh có khả năng làm cho dãy lệnh
không thể thực hiện song song được. Mặc dù vậy chúng ta có một số cách để loại bỏ sự
phụ thuộc này.
- Loại bỏ sự phụ thuộc dữ liệu bằng cách đặt lại tên của các biến để tránh việc
chia sẻ các biến và từ đó tăng được mức độ song song của chương trình.
Ví dụ: (S1):
A = B + X
C = A + D
S1
S2
(S2):
Để loại bỏ sự phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể thay biến A của câu lệnh
(S2) bằng A1 như sau:
(S1): A = B + X
(S2): C = A1 + D
29
- Loại bỏ sự phụ thuộc dữ liệu ra bằng cách sử dụng các biến khác nhau.
Ví dụ: (S1): A = B + C + D
S1
S2
(S2): A = D * X
Để loại bỏ sự phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể thay biến A của câu lệnh
(S2) bằng A1 như sau:
(S1): A = B + C + D
(S2): A1 = D * X
- Loại bỏ sự phản phụ thuộc dữ liệu bằng cách sử dụng các biến khác nhau hoặc
thực hiện các phép biến đổi (phép thế).
Ví dụ 1:(S1): A = C + D
S1
S2
(S2): C = D * X
Để loại bỏ sự phản phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể sử dụng biến khác
cho câu lệnh (S2) như sau:
(S1): A = C + D
(S2): C1 = D * X
Ngoài ra ta có thể sử dụng một số cách biến đổi để loại bỏ các mối quan hệ về dữ
liệu giữa các tiến trình.
Ví dụ 2: Xét dãy các câu lệnh sau:
(S1): A = B + C
(S2): B = A * 3
(S3): A = 2 * C
(S4): P = B >= 0
if (P is true)
(S5): then D = 1
(S6): else D = 2
endif
Đồ thị phụ thuộc dữ liệu của đoạn chương trình trên được mô tả như hình vẽ:
30
S1
S2
S3
S4
S6
S5
Hình 2-2 Đồ thị phụ thuộc dữ liệu
Để xử lý được song song, thì cần thiết phải loại bỏ đi một số những loại phụ thuộc
dữ liệu có thể. Ví dụ loại bỏ những quan hệ phản phụ thuộc dữ liệu và phụ thuộc dữ
liệu kết quả bằng cách thay biểu thức tính B ở S1 vào S2, ta thu được đoạn chương trình
sau:
S2’: B = (B + C) * 3
S3: A = 2 * C
S4: P = B >= 0
if (P is true)
S5: then D = 1
S6: else D = 2
endif
Đồ thị phụ thuộc dữ liệu rút gọn của đoạn chương trình trên
S3
S2’
S4
S5
S6
Hình 2-3 Đồ thị phụ thuộc dữ liệu rút gọn
Tải về để xem bản đầy đủ
95 trang
20/07/2025
750
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Xử lý song song", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_xu_ly_song_song.doc
