Giáo Trình Xử Lý Song Song Và Phân Tán - 123doc

Tài liệu xử lý song song gồm: c1.Kiến trúc và các loại máy tính song song c2.Các thành phần của máy tính song song c3.Giới thiệu về lập trình song song c4.Các mô hình lập trình song song c5.Thuật toán song song

Chương I Kiến trúc và các loại máy tính song song

1.1 Giới thiệu chung

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 của 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

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 BXL tăng nhiều trong những năm qua, nhưng do giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được Đ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

Định nghĩa: 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ý [6].

Sự khác nhau giữa song song với tuần tự:

 Trong tính toán tuần tự với một BXL thì mỗi thời điểm chỉ thực hiện được một phép toán.

 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 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

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 và ngôn ngữ lập trình , v.v.

Định nghĩa: Một máy tính song song là tuyển tậ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 [4].

Các máy tính song song có thể phân thành nhiều loại dựa vào các đặc trưng của các kiến trúc và thể thực thao tác khác nhau Cụ thể là có

thể dựa vào các chỉ tiêu về 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 Vấn đề là chúng ta phải có nhiều BXL (các đơn vị tính toán

độc lập) cùng hoạt động Nhưng điều quan trọng là chúng 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

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.c và một đơn vị khác dịch chương trình File2.c 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.c 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 Chúng ta dễ nhận thấy

là độ phức tạp của xử lý song song sẽ lớn hơn xử lý tuần tự rất nhiều,

tập trung chủ yếu ở phương diện truyền thông và sự đồng bộ các tiến trình.

Một trong các mục đích chính của xử lý song song là nghiên cứu và 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 có thể

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 phải bổ sung thêm những tham số về số BXL, khả năng của các bộ nhớ cục bộ, sơ đồ truyền thông, và 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

1.2 Kiến trúc của máy tính

Kiến trúc máy tính (KTMT) nghiên cứu cách tổ chức để liên kết các thành phần của các hệ thống máy tính.

Máy tính được xây dựng từ các khối cơ sở:

 Bộ nhớ: để lưu trữ dữ liệu

 Các đơn vị logic và số học: thực hiện các phép toán được ký

hiệu là ALU

 Các phần tử xử lý: điều khiển CU và truyền dữ liệu vào/ra

 Đường truyền dữ liệu

Sự khác nhau chính của các máy tính là ở sự liên kết giữa các khối

đó với nhau Trong các hệ thống máy tính truyền thống có hai khối

quan trọng nhất là bộ nhớ và BXL BXL thao tác trên các dữ liệu được

lưu trữ trong bộ nhớ thông qua các chỉ thị (câu lệnh) Các câu lệnh cũng được lưu trong bộ nhớ và luôn luôn là dòng được chuyển từ bộ nhớ tới BXL để thực hiện Dữ liệu di chuyển trong hệ thống theo cả hai chiều, đọc và ghi vào bộ nhớ Hình 1-1 mô tả hoạt động của mô hình máy tính kiểu von Neumann.

Hình 1-1 Sự liên kết giữa bộ nhớ và bộ xử lý

Tuy nhiên để thực hiện được việc xử lý song song thực sự thì phải xây dựng

được những mô hình tính toán mới phù hợp với những nguyên lý song song.

Bộ nhớ

Bộ xử lýGhi dữ liệu Đọc dữ liệu Câu lệnh

Đó là các mô hình: các bộ xử lý tâm thu, mô hình luồng dữ liệu, mạng nơ-ron,

v.v

1.3 Phân loại 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) [7] đã đưa ra cách phân loại nổi tiếng đượcnhiều người chấp nhận

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-2 mô tả hoạtđộng của máy tính theo mô hình SISD

Hình 1-2 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.

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 Đây là kiểu tính toánlặp lại các đơn vị số học trong CPU, cho phép những đơn vị khác nhau thực hiệntrên những toán hạng khác nhau, nhưng thực hiện cùng một lệnh 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ìnhchủ yếu thuộc loại này Hình 1-3 mô tả hoạt động của máy tính theo mô hìnhSIMD, còn được gọi là SPMD

Đơn vị điều khiển

Bộ nhớ

BXL số họcLuồnglệnh Luồng kết quả Luồng dữ liệu

Tín hiệu điều khiển

Đơn vị điều khiển (CU) Tín hiệu

điều khiểnTín hiệu

Hình 1-3 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à Connection Machine CM-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ể chiathà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ínhnà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ứcnă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.

Mô hình của kiến trúc MISD được mô tả như hình 1-4

Hình 1-4 Mô hình của kiến trúc MISD

CU 1

Phần tử

xử lý 2Luồng lệnh 1

CU 2

CU n

Luồng lệnh 2

Luồng lệnh n

Luồng

dữ liệu

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, 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-5

Hình 1-5 Mô hình của kiến trúc MIMD

1.4 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 haimẫu đó Mẫu hình các kiến trúc xử lý song song có thể phân chia như hình 1-6

CU 1

Phần tử

xử lý 2Luồng lệnh 1

CU 2

CU n

Luồng lệnh 2

Luồng lệnh n

Luồng dữ liệu 1

Luồng dữ liệu 2

Luồng dữ liệu n

MIMD

SIMD

MISD

MultiprocessorMulticomputerData Flow MachineArray ProcessorPipelined Vector ProcessorPipelined Vector ProcessorSystolic Array

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 đốc độcực nhanh của các BXL để thực hiện xử lý song song theo nguyên lý chia sẻ thờigian 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 songthì mục đích chính là khai thác triệt để khả năng của kiến trúc song song để viếtcác chương trình song song

1.4.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 trongcá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ụ máy CDC 6600 (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ụ 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ả, v.v 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

Bằng cách thực hiện như trên thì trong quá trình thực hiện của BXL 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 Trước khimột câu lệnh kết thúc thực hiện thì câu lệnh tiếp theo đã có thể thực hiện pha giải

mã, câu lệnh khác lại có thể được nạp về, v.v

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 haynhững BXL vào/ra khác nhau

Nhiều 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ậpvào 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ình 1-6

Hình 1-6 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ệ

CPU (Registers)Cache

Main Memory

Fixed Disks, Drum

Magnetic Tapes

Tăng khả năng lưu trữ

Tăng về tốc

độ truy cập

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ứcnă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 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ý.

1.4.2 Mô hình trừu tượng của máy tính song song

Trước khi xem xét những kiến trúc máy tính song song cụ thể, chúng ta hãynghiên cứu một mô hình trừu tượng của máy song song [6] Mục đích chính làmuốn thể hiện được những khả năng tính toán của máy song song mà không quantâm đến những ràng buộc cụ thể của những máy tính có trong thực tế

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 (xem hình 1-7) 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ácBXL đề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ặcchung)

CU

BXL 1

Mạng kết nối

.

Hình 1-7 Máy tính P-RAMĐây là mô hình tổng quát cho máy tính song song kiểu MIMD Về nguyêntắ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 BXLkhá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áytính song song tổng quát

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ổngquá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àngbuộc để đảm bảo chương trình thực hiện được trên những máy tính đó Về hìnhthứ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: Cho phép đọc, ghi đồng thời Tất nhiên mô hình cho loại này ít

 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

Hình 1-8 Mô hình kiến trúc SIMD

Ví dụ, xét đoạn chương trình được mô tả như sau:

(a)

(b)Hình 1-9: (a) thực hiện theo SISID, (b) thực hiện theo SIMDTrong đó, X1, X2, X3, và X4 là các khối các câu lệnh

Trong hệ thống SISD, việc thực hiện là tuần tự, sau khi thực hiện xong X1, việc thực hiện

X2 hoặc X3 là tùy thuộc vào giá trị của X có bằng ∝hay không và cuối cùng thực hiện X4

Đơn vị điều khiển

Phần tử

xử lý 2

Tín hiệu điều khiển

Bộ nhớ Kết quả

Một số PE kiểm tra X≠∝,một số khác rỗi

Tất cả PE

Trong hệ SIMD, có thể một số luồng dữ liệu thỏa mãn X = ∝, trong khi một

cả các PE hoạt động khi hệ thống thực hiện các khối X2 và X3

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 [7]:

 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.

1.4.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ự, khi thực hiện xong thì bắt đầu thực hiện của tiến trình tiếp theo Mỗi pha

thực hiện xong 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 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:

Thực hiện tuần tự hai tiến trình phải qua 8 giai đoạn:

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:

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ạnNế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:

Pha 1 Pha 2 Pha 3 Pha 4

Pha 1 Pha 2 Pha 3 Pha 4 Pha 1 Pha 2 Pha 3 Pha 4

Pha 1 Pha 2 Pha 3 Pha 4

Pha 1 Pha 2 Pha 3 Pha 4

 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))

đoạn và tổ chức theo hình ống (hình 1-11 (b))

Hình 1-11 (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU Như chúng ta đã biết, việc xử lý theo hình ống được sử dụng để thực hiện gối đầunhiề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:

Hình 1-12 Ví dụ về một hình ống vòng trònCá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ựchiện đồng thời và hỗ trợ để khai thác được khả năng của kiến trúc song song theocác mức khác nhau

thực hiện sao cho sau khi đưa các lệnh vào hình ống thì chúng sẽ thựchiện lặp lại theo từng chu kỳ

CUALUALU .ALU

Bộ nhớ

CU .CUCUALU

Mạng ghi

Read Network Mạng đọc

 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áytí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 phần cứng mà có thể ở mức phần mềm

Kết quả nguyên lý hình ống đã được ứng dụng để thiết kế nhiều hệ máy tínhnhư: CDC STAR 100, Texas Instruments ASC, Cray 1, v.v

1.4.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 ô trongmả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

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

(a)

Systolic Array

(c)

(b)

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ôngHiệ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

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:

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 đượcxây dựng từ những bộ CPU 64 bit được gắn với bộ nhớ chung

1.4.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êngcủ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ớ

 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ăm1990) 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*

Vấn đề xử lý song song cũng có thể thực hiện được trên các máy tuần tự kiểu vonNeumann bằng cách sử dụng nguyên lý xử lý hình ống hay chia sẻ thời gian, v.v.

Bài tập

1.1 Nêu đặc trưng cơ bản của kiến trúc máy tính tuần tự của von Neumann

1.2 Các kiến trúc máy tính có thể được phân loại như thế nào? dựa vào những yếu

tố nào để phân loại?

1.3 Một hệ thống như thế nào được gọi là máy tính song song?

1.4 Máy tính kiểu MIMD khác với mạng các máy tính như thế nào?

1.5 Nêu nguyên lý xử lý theo hình ống Những bài toán có những tính chất gì thìthích hợp với kiến trúc xử lý hình ống?

1.6 Cần bao nhiêu nhịp để thực hiện nhân hai ma trận 100 × 100 trên SAP có

100×100 phần tử xử lý? Nếu sử dụng hệ 1000×1000 PE thì hệ nào tốt hơn(nhanh hơn)?

1.7 Một công việc được chia thành m công việc con,mỗi công việc con đòi hỏi một

đơn vị thời gian để thưc hiện Hỏi cần bao nhiêu đơn vị thời gian để hệ hình ốnggồm m-bộ xử lý tuyến tính (gồm m-pha thực hiện) thực hiện được nhiệm vụ chotrước?

Chương IICác thành phần của máy tính song song

Xử lý song song là quá trình xử lý thông tin, trong đó các thao tác trên các phần tử dữ liệu thuộc một hoặc một số tiến trình được thực hiện đồng thời nhằm cùng giải quyết một bài toán [6].

Trong những năm vừa qua, cùng với sự tăng trưởng nhanh chóng của phầncứng, nhiều máy tính hỗ trợ xử lý song song, số lượng máy tính song song cũngtăng nhanh cùng với nhiều phương pháp, ngôn ngữ lập trình song song ra đời.Những công nghệ mới này ngày một hoàn thiện và đóng vai trò quan trọng trongcông nghệ thông tin, đáp ứng yêu cầu của nhiều lĩnh vực khoa học, công nghệ vànhiều lĩnh vực ứng dụng khác

Như trên đã phân tích, những kiến trúc kiểu SIMD, MIMD là những máy tính

đa BXL Đặc tính quan trọng của máy tính kiểu SIMD là các BXL số học đượcđồng bộ ở mức lệnh, do vậy mức độ hiệu quả của chúng phụ thuộc vào cấu trúc dữ

liệu và cách tổ chức bộ nhớ Sau đây là một số vấn đề cần quan tâm khi thiết kế kiến trúc máy tính song song.

ngắt

tăng hiệu quả trao đổi dữ liệu của hệ thống

cho từng nhiệm vụ đơn lẻ một cách động như các chương trình ứng dụngyêu cầu

truy cập đến một số hữu hạn các tài nguyên chung, ví dụ như bộ nhớ, đảm

bảo tránh được sự tắc nghẽn (deadlock)

BXL với bộ nhớ trong hệ thống Cấu hình tôpô của mạng kết nối là vấn

đề rất quan trọng trong thiết kế hệ thống song song

được các luồng xử lý đồng thời Sự phân đoạn có thể thực hiện ở nhiềumức khác nhau: mức lệnh, mức thủ tục, hoặc mức chương trình, v.v

một BXL nào đó không thực hiện được thì công việc mà nó phải đảmnhiệm sẽ được giao cho BXL khác thực hiện để đảm bảo trong mọi tìnhhuống để công việc chung vẫn được hoàn thành

2.1 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 như hình 2-1.

BXL

Bộ nhớ mức 1

Bộ nhớ mức 2

Hình 2-1 Phân cấp hệ thống bộ nhớ

Bộ nhớ mức 1 là mức bộ nhớ cao nhất có dung lượng nhỏ nhất, nhanh và đắtnhấ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ườngnhỏ 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

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

k qa

R/W m

ChọnKhoáĐối sốĐọc/ghi

Kết quảĐối sánh

Hình 2-2 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 2-3 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.

0 1 n-1

Hình 2-3 Cấu trúc của bộ nhớ kết hợp

và trả lại từ đầu tiên được tìm thấy

Giá trị (1101 1100)2 là đối số để tìm, thanh ghi đánh giấu (mặt nạ - maskregister) là 8 bit cao nhất Quá trình tìm kiếm thực hiện như sau:

1 Từ cần tìm (1101 1100)2 được nạp vào thanh ghi đối số

2 Đoạn mà chúng ta quan tâm là 8 bit cao nhất, vậy những bit này được đưavào thanh ghi mặt nạ để đánh giấu

3 Tất cả các từ trong bộ nhớ được so sánh song song với thanh ghi đối số.+ Nếu từ đó đối sánh được với đối số thì thanh ghi đối sánh nhận giá trị 1.+ Nếu nhiều hơn một bit nhận giá trị 1, mạch vòng sẽ xác định các từ tương ứng được đọc hay được ghi

0 1 .m-1Argument Register Mask Register Mặt nạ

Buffer Register

Output

So sánh với bộ nhớ truy cập ngẫu nhiên RAM thì AM đắt hơn, nhưng bù lạitốc độ tìm kiếm lại nhanh hơn.

2.1.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ý P i ghi dữ liệu vào một vùng nhớ và dữ

liệu này có thể được P j truy cập, nghĩa là P i và P j 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 đầunhau Đó là:

đọc được chính xác một vùng nhớ và mỗi vùng nhớ được đọc bởi mộtBXL

cùng một vùng nhớ

BXL ghi được vào chính xác một vùng nhớ và mỗi vùng nhớ được ghibớ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:

và khi có nhiều BXL muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên choBXL có mức ưu tiên cao nhất Các mức ưu tiên có thể gắn tĩnh hoặc độngtheo những qui tắc được xác định khi thực hiện

cùng một vùng nhớ chỉ khi chúng ghi cùng một giá trị Trong trường hợpnày, một BXL được chọn để ghi dữ liệu đó

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ựachọn BXL thực hiện

liệu là ngẫu nhiê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à đồngnhấ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 theocấ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:

+ Data Diffusion Machine (DDM) của Swedish Institute of Computer

Việc trao đổi dữ liệu trong mạng là điểm - tới điểm (point – to – point) thôngqua sự liên kết tĩng giữa các BXL

2.2 Mạng kết nối các thành phần của máy tính song song

Trong hầu hết các kiến trúc song song như: những hệ đa bộ xử lý chia sẻ bộnhớ, đa bộ xử lý đa bộ nhớ , v.v thì vấn đề quan trọng nhất trong thiết kế là xácđịnh sự liên kết giữa các BXL và bộ nhớ với nhau

Một kiến trúc lý tưởng là kiến trúc trong đó, mỗi BXL đều kết nối được với các BXL còn lại Khi đó nó tạo ra một đồ thị đầy đủ Ví dụ, nếu hệ có p BXL thì sẽ

có p * (p – 1) đường liên kết Dễ nhận thấy kiến trúc loại này sẽ rất phức tạp, nhất

là khi p đủ lớn

Nói chung có hai loại cấu hình tôpô cho mạng liên kết: liên kết tĩnh và liên

kết động

 Mạng liên kết tĩnh là mạng các thành phần của hệ thống máy tính, trong

đó các BXL, bộ nhớ được liên kết với nhau một cách cố định, không thayđổi được

 Mạng liên kết động là mạng các thành phần của hệ thống máy tính, trong

đó sự liên kết giữa các BXL, bộ nhớ là có thể thay đổi được cấu hình Lĩnh vực liên kết động được rất nhiều người tập trung nghiên cứu và đã cónhiều công trình lý thuyết được công bố Sau đây chúng ta tìm hiểu một số loại cấuhình tôpô của mạng liên kết giữa các BXL của các máy tính song song

2.2.1 Liên kết tuyến tính và vòng xuyến

Trong mạng liên kết tuyến tính các BXL được tổ chức liên kết với nhau

theo dãy và được đánh số theo thứ tự tăng dần như hình 2-4.

Hình 2-4 Mạng liên kết n bộ xử lýTrong mạng lên kết tuyến tính, trừ hai phần tử đầu và cuối, tất cả các BXLbên trong đều có hai láng giềng là BXL trước và sau nó

Mặc dù đây là dạng liên kết đơn giản, nhưng dữ liệu cũng cần phải chuyểnqua nhiều BXL, kết quả là sự truyền thông dữ liệu giữa các BXL, đặc biệt là giữaBXL đầu và cuối sẽ bị chậm lại khi số BXL khá lớn

Mạng liên kết vòng được tổ chức tương tự như liên kết tuyến tính nhưng

BXL đầu và cuối được nối vòng với nhau như hình 2-5.

Hình 2-5 Mạng liên kết vòng của 6 BXLTrong mạng liên kết vòng, sự trao đổi giữa các BXL có thể thực hiện theo

một chiều, gọi màng mạng đơn, hoặc theo cả hai chiều được gọi là mạng kép Tất

nhiên sự truyền thông trong mạng liên kết vòng, nhất là giữa những BXL ở xa nhauthì cũng vẫn bị trễ

2.2.3 Mạng liên kết lưới hai chiều

Mạng liên kết mắt lưới hai chiều được sử dụng để thiết kế các máy tính

ILLIAC IV, MPP (Massively Parallel Processor), DAP (ICL Distributed Array

Processor), v.v Trong mạng liên kết loại này, mỗi BXL được liên kết với bốn lánggiềng: trên, dưới, bên trái và bên phải

Có hai dạng liên kết lưới như hình 2-7

(a) Lưới không quay vòng (b) Lưới quay vòng tròn

j =

Hình 2-7 Mạng liên kết mắt lưới hai chiều

2.2.4 Mạng liên kết siêu khối hoặc hình khối n-chiều

Giả sử có n bộ xử lý: P0, P1, …, Pn, với n = 2q, q ≥ 0 Nếu mỗi BXL cần liên

kết với đúng q bộ xử lý lân cận thì có thể dùng mạng liên kết theo hình siêu khối n

chiều

Trong mạng liên kết hình khối, các chỉ số của các BXL được chuyển

thành nhị phân và hai BXL được gọi là láng giềng với nhau nếu nhãn chỉ

số của chúng sai khác nhau đúng một bit Ví dụ với n = 8 chúng ta có mạngliên kết hình khối như hình 2-8

Hình 2-8 Mạng liên kết hình khối

2.2.5 Mạng liên kết hình sao

Trong mạng liên kết hình sao với n là số nguyên, bộ xử lý sẽ tương ứng với một hoán vị của n ký hiệu Mạng hình sao ký hiệu là Sn sẽ có n! = 1*2*…*n bộ

xử lý, trong đó nhãn chỉ số của mỗi BXL là một hoán vị của n ký hiệu

Pi được liên kết với Pj⇔ j nhận được từ i bằng cách thay ký hiệu thứ k, với

2≤k≤n

nhận được từ 2134 bằng cách đổi chỗ vị trí đầu (số 2) với vị trí thứ ba (số 3).Tương tự suy ra P2134 và P4132 là có liên kết với nhau Vậy S4 có 4! = 24 bộ xử lýđược mô tả như hình 2-9

2

P0000

514

76

Hình 2-9 Mạng liên kết hình sao với 24 bộ xử lýBảng dưới đây liệt kê một số loại kiến trúc máy tính song song phổ biến trênthị trường.

Kiến trúc

song song

Năm sản xuất

Loại máy tính

Số BXL và cấu hình tôpô

450

2.3 Chương trình dịch và các hệ điều hành

2.3.1 Chương trình dịch

Đối với các hệ thống song song thì một thành phần rất quan trọng là chương trình dịch song song Chương trình dịch làm giảm được thời gian thực hiện chương trình (song song) bằng cách chia nhỏ bài toán thành các khối công việc và những khối này được xử lý đồng thời bởi nhiều đơn vị xử lý Một số

chương trình chỉ làm nhiệm vụ phát hiện những khối công việc thực hiện đượcsong song và thực hiện phân chia các đơn vị chức năng, một số khác tinh tế hơn,

có thể lập lịch cho cả bài toán [9]

Một câu hỏi đặt ra trong kiến trúc song song là "một chương trình có thể chia thành các khối nhỏ như thế nào? và sau đó kết hợp lại chúng ra sao?"

Nói chung, những câu hỏi trên đề cập đến những vấn đề hạt nhân của xử lýsong song, cần phải phân tích sự phụ thuộc về chức năng, dữ liệu của các khốicông việc, sự liên kết giữa các thành phần của hệ thống và sự lập lịch thời gianthực hiện của hệ thống nói chung

Có ba cách tiếp cận để xây dựng chương trình dịch cho các máy tính songsong:

1 Run Time Partitioning and Run Time Scheduling Cách tiếp cận này khá

phù hợp với một số ứng dụng thực tế Tuy nhiên, nó có hạn chế là việc lậplịch và phân hoạch được thực hiện lúc chạy chương trình sẽ làm giảm hiệuxuất của hệ thống

2 Compile Time Partitioning and Run Time Scheduling Đây là mô hình

chung để xây dựng chương trình dịch cho những đa bộ xử lý Lập lịchphân việc được thực hiện lúc chương trình chạy, nhưng việc phân hoạchcông việc thành các khối được thực hiện bởi người lập trình và chương

trình dịch Theo cách tiếp cận này, sự đồng bộ hóa các tiến trình và truyềnthông phải được xác định rõ trong hệ thống.

3 Compile Time Partitioning and Compile Time Scheduling Phân hoạch

công việc và lập lịch được thực hiện ở giai đoạn dịch chương trình Dovậy, chương trình dịch loại này đòi hỏi phải rất hoàn hảo Nhưng điều nàykhá khó, bởi vì rất khó đánh giá được thời gian thực hiện chương trình, đặcbiệt là vấn đề lập lịch trước sẽ không thể thực hiện tối ưu được

Nói chung, cho đến hiện nay khá nhiều chương trình dịch cho các máy tínhsong song được xây dựng là cho ngôn ngữ lập trình Fortran [7]

Ví dụ 1, chương trình dịch Paraphrase (do Kuck viết năm 1984) cho máy

tính Cedar Multiprocessor được phát triển ở Đại học Illinois, sử dụng đồ thị độc lập

dữ liệu để biến đổi chương trình Fortran từ dạng tuần tự sang dạng thích hợp đểthực hiện song song Chương trình dịch này thực hiện theo hai giai đoạn:

1 Giai đoạn 1: thực hiện biến đổi độc lập với máy tính, chuyển chương

trình sang dạng trung gian thể hiện được dạng song song của mã chương trình.

2 Giai đoạn 2: thực hiện ánh xạ để chuyển từ dạng trung gian sang kiến

trúc song song của máy tính

Chương trình dịch Paraphrase được sử dụng khá thành công trên máy tính máy tính các bộ xử lý vector như Cray X/MP, khai thác tốt các khả năng song

song của chương trình Fortran

Ví dụ 2, chúng ta xét tiếp một chương trình dịch song song khác là Fortran D

(Fox xây dựng năm 1991, Hiranandani cải tiến 1992, 1993) Fortran D mở rộng củaFortran, trong đó cho phép người lập trình xác định được sự phân rã dữ liệu củachương trình song song Hai vấn đề: ánh xạ sử dụng phương pháp gán mảng và ánh

xạ sử dụng phân rã, phân tán dữ liệu đã được giải quyết hiệu quả trong Fortran D

2.3.2 Hệ điều hành

Hệ điều hành là một chương trình làm nhiệm vụ phối hợp các hoạt động của máy tính Hệ điều hành thực hiện các chức chính sau:

 Khởi động hệ thống

 Phân đoạn chương trình và lập lịch cho các tiến trình

 Trao đổi và đồng bộ hóa các tiến trình

 Quản lý và điều hành hệ thống, v.v

Về mặt khái niệm, mục đích chính của hệ điều hành cho máy tính đơn bộ xử

lý có một chút khác với những hệ cho máy tính đa bộ xử lý Trong hệ điều hành

tập trung (đơn bộ xử lý), mọi quyết định được thực hiện dựa trên sự hiểu biết về

trạng thái tổng thể và tức thời của cả hệ thống Ngược lại, hệ điều hành đa bộ xử lý

có thể thực hiện mà không cần thiết phải biết trước về trạng thái của hệ thống phântán

Nhiệm vụ chính của hệ điều hành đa bộ xử lý là tích hợp các tài nguyên tính toán và các bộ xử lý trao đổi với nhau thông qua mạng liên kết để tạo thành một hệ thống nhất làm việc cho hiệu quả.

Nói chung, hệ điều hành đa bộ xử lý cũng giống như hệ điều hành tập trung,phải chứa các thành phần quản trị hệ thống như: quản trị các tiến trình, quản trị bộ

nhớ, quản trị tài nguyên và quản trị các tệp (file) Người ta phân các hệ điều hành cho các máy tính song song thành ba loại:

1 Những hệ điều hành mở rộng và phát triển từ những hệ đơn bộ xử lý để

chạy được trên những kiến trúc song song, như VMS, UNIX.

2 Những hệ điều hành được thiết kế riêng cho những kiến trúc song song,

như: hệ Hydra cho C.mmp, Medusa cho Cm*, cả hai đều được phat triển ở Carnegie-Mellon University.

3 Những hệ điều hành tổng hợp được thiết kế để cài đặt được trên những kiến trúc song song khác nhau, ví dụ MACH Multiprocessor

Hầu hết các version mới của hệ điều hành UNIX đều thực hiện trên các hệ

đa bộ xử lý Trong số đó có thể kể ra như Solaris của Sun, HP UNIX của HP,Digital UNIX của Digital, AIX của IBM, v.v Những hệ điều hành mới nhất nhưWindow NT của Microsoft cũng được thiết kế để chạy trên những hệ thống đa bộ

2.5 Nêu những đặc trưng cơ bản của chương trình dịch song song?

2.6 Nếu mục đích chính của hệ điều hành cho máy tính song song?

2.7 Xây dựng mạng liên kết theo mô hình xáo trộn hoàn hảo cho 16 phần tử

Chương III

Giới thiệu về lập trình song song

3.1 Giới thiệu chung

Trước tiên, thuật ngữ tiến trình được sử dụng để mô tả một dãy các câu lệnh của chương trình có thể thực hiện một cách tuần tự hoặc song song với

những câu lệnh khác của chương trình [7] Do vậy, một chương trình có thể

được xem là một tập các tiến trình có thể thực hiện tuần tự hoặc đồng thời có tươngtranh

Trong môi trường lập trình tuần tự, một chương trình thực hiện trên cùng một tập dữ liệu thì luôn cho cùng một kết quả Mỗi chương trình thực hiện sẽ tạo ra một tiến trình bên trong hệ thống mà NSD không quan sát được và mỗi câu lệnh thực hiện cũng không gây trở ngại cho các câu lệnh khác trong chương trình

Trong môi trường đa chương trình, đơn vị xử lý bị chuyển để xử lý từ một

chương trình sang cho chương trình khác làm cho các câu lệnh của chúng có thể thực hiện đan xen nhau.

Do vậy, trong môi trường đa bộ xử lý, đa chương trình, ở cùng một thời

điểm có thể có nhiều hơn một chương trình được thực hiện, nghĩa là mỗi chương trình sẽ tự chủ thực hiện các tiến trình của mình Trong những hệ

thống như thế, các chương trình phải tương tác với nhau và việc thực hiện củachúng ảnh hưởng tới nhịp độ thực hiện của nhau

Trong môi trường lập trình song song, người lập trình không chỉ viết

chương trình, dữ liệu như trong môi trường tuần tự mà còn phải cung cấp các công cụ để đồng bộ hoá và điều khiển sự tương tác giữa các tiến trình Do vậy, người lập trình cần tạo ra và lập lịch cho các tiến trình, nghĩa là sự thực hiện chương trình có thể nhìn thấy được bởi người lập trình

Vấn đề quan trọng trong lập trình song song là phải tận dụng được khả năngtính toán của các bộ xử lý Có hai cách tiếp cận để tận dụng khai thác các bộ xử lý:

1 Phát triển những ngôn ngữ lập trình cho phép thể hiện được việc thực hiện song song ở mức thuật toán, ví dụ như Fortran, C, v.v.

2 Xây dựng những chương trình dịch đủ mạnh để nhận dạng được các phân đoạn chương trình có thể thực hiện song song hay tuần tự.

Hai cách tiếp cận trên là bổ sung cho nhau, nếu chỉ áp dụng một cách thì dĩ

nhiên là không hiệu quả

Như vậy, lập trình song song không phải chỉ là mở rộng và phát triển củaphương pháp lập trình tuần tự Để khai thác được các khả năng song song của máytính thì người lập trình phải xem xét bài toán dưới nhiều góc độ khác nhau và tạo rađược các tiến trình thực hiện đồng thời Có một số cách tiếp cận trong lập trìnhsong song như sau:

 Lập trình song song kiểu SIMD với bộ nhớ chia sẻ, trong đó truy cập bộ

3.2 Các ngôn ngữ lập trình cho xử lý song song

Ngôn ngữ lập trình cũng giống như hệ điều hành, nó phải cung cấp cho ngườilập trình những cơ chế để khởi tạo, đồng bộ và trao đổi giữa các tiến trình Hơn thếnữa đối với ngôn ngữ lập trình còn đòi hỏi phải tạo ra được những chương trìnhđộc lập với máy tính, phải hỗ trợ để tạo ra được những chương trình dễ đọc, dễviết, dễ chuyển đổi, v.v Đặc biệt đối với những kiến trúc song song thì ngôn ngữlập trình phải là mô hình được sử dụng để thực hiện song song

Nói chung, hiện nay các ngôn ngữ lập trình song song vẫn còn thiếu những cấu trúc thực sự cho các bộ xử lý song song như: vấn đề đồng bộ các tiến trình, các giao thức truyền tin, điều khiển mạng, v.v [7].

Trong lập trình song song, các hoạt động song song của chương trình cần

phải được xác định Những hoạt động đó thường được xem như là tiến trình hay là

tác vụ Ngôn ngữ lập trình song song phải có khả năng điều chỉnh các tình

huống mà ở đó các tiến trình đòi hỏi phải trao đổi, tương tác với nhau Trong

những tình huống như thế, một tiến trình có thể tương tác với tiến trình khác khi:

1 Khi cùng một thời điểm có một số tiến trình muốn cập nhật vào một biến chia sẻ hoặc truy cập vào một tài nguyên chung Mà những tài

nguyên đó chỉ cho phép một tiến trình truy cập tại mỗi thời điểm Khi mộttiến trình được quyền truy cập vào tài nguyên yêu cầu thì nó phải sử dụngtài nguyên đó và không ngăn cản hoạt động của những tiến trình khác

2 Khi một số tiến trình cùng kết hợp để thực hiện một số phép toán trên

cơ sở quan sát hành động của nhau Trường hợp này ta phải lập lịch cho

những tiến trình đó

Có hai cách để giải quyết vấn đề trên:

1 Tất cả các tiến trình sử dụng cấu trúc chung để cập nhật và trao đổi với

nhau.

2 Tất cả các tiến trình thực hiện đồng bộ bằng cách sử dụng hai hàm

wait() và pass() Khi trao đổi với nhau, một tiến trình chờ để nhận được

một tín hiệu của tiến trình đối tác và khi nhận được thì hai tiến trình đótrao đổi trực tiếp với nhau

Nói một cách tổng quát, có hai cách phát triển chương trình song song:

 Mở rộng những ngôn ngữ lập trình hiện có, bổ sung thêm những cấu trúc mới để thực hiện được song song và giải quyết được sự xung đột trong truy cập dữ liệu.

 Xây dựng một ngôn ngữ mới hỗ trợ cho xử lý song song

Sau đây chúng ta xét một số số ngôn ngữ lập trình song song điển hình

3.2.1 Fortran 90

Fortran 90 được xem như là ngôn ngữ lập trình chuẩn ANSI Fortran 90 là

ngôn ngữ lập trình song song theo dữ liệu được nâng cấp từ Fortran 77 bằng cách

bổ sung thêm một số đặc tính như các con trỏ, nhiều kiểu dữ liệu được định nghĩa bởi NSD, cấp phát bộ nhớ động, kiểu dữ liệu trừu tượng, v.v Ngoài ra nó cũng hỗ

trợ để mở rộng khả năng tính toán mảng, ví dụ, tính toán ma trận

Người lập trình Fortran 90 dựa vào mô hình song song tương tự như P-RAMgồm có những thành phần:

 Một CPU

 Một đơn vị xử lý logic, số học ALU

 Một đơn vị logic số học vector

 Bộ nhớ chia sẻ

Trong đó CPU thực hiện các câu lệnh tuần tự bằng cách truy cập vào các biếnđược lưu trữ trong bộ nhớ chia sẻ Đơn vị vector lưu trữ, đọc, ghi dữ liệu vào bộnhớ chia sẻ và được CPU điều khiển để thực hiện song song

Fortran 90 có các kiểu cơ sở: REAL, INTEGER, CHARACTER, LOGICAL, v.v.Dạng khai báo tổng quát có dạng

Type [(kind)] [, attribute] … :: Variable-List

Trong đó,

+ Type là kiểu cơ sở hoặc kiểu được định nghĩa bởi NSD

+ kind là phần tuỳ chọn cùng một số kiểu được sử dụng để định nghĩa về

kiểu cụ thể, ví dụ

CHARACTER (LEN = 10) :: s1

Định nghĩa biến s1 kiểu CHARACTER có thể chứa 10 ký tự.

+ [, attribute] là danh sách các thuộc tính của Fortran được sử dụng để định

nghĩa các đặc tính riêng của danh sách các biến

+ :: phần tử phân cách giữa phần mô tả kiểu và danh sách các biến.

Ví dụ:

INTEGER, DIMENSION (1 : 10) :: SA

Thuộc tính DIMENSION (1 : 10) chỉ ra rằng SA là biến mảng, trong đó(1:10) xác định chỉ số của mảng từ 1 đến 10 và nó có 10 phần tử

Fortran 90 cho phép áp dụng các phép toán số học cho các biến mảng, nghĩa

là toán hạng của các phép toán số học (+, -, *, /) có thể là biến đơn hoặc biến mảng

3.2.2 Lập trình song song với OCCAM

Occam ([7], [3]) là ngôn ngữ lập trình song song được Inmos Company pháttriển năm 1988, mục đích chính là để thiết kế và cài đặt các chip được gọi là

transputer

Transputer là một máy tính một chip đơn với một bộ xử lý, bộ nhớ riêng và bốn kênh vào/ra Transputer có hai loại 16 bit hoặc 32 bit với tốc độ 10 triệu phép

tính /giây và mỗi kênh có khả năng truyền tải 10 megabit/giây

Chương trình Occam thường nhiều tiến trình và chúng có thể được ánh xạsang một số các transputer bất kỳ để thực hiện song song và trao đổi dữ liệu với

thể tăng, hoặc giảm và chương trình có thể thực hiện mà không cần có sự thay đổinào cả.

Occam là ngôn ngữ lập trình bậc cao, được sử dụng để lập trình cho những hệ thống gồm nhiều máy tính kết nối với nhau, hoặc các hệ phân tán Tuy nhiên, so với các ngôn ngữ lập trình bậc cao khác thì Occam còn thiếu một số đặc tính như hỗ trợ cơ chế đệ qui, định nghĩa kiểu dữ liệu hay con trỏ.

Trong Occam, một hành động có thể thực hiện song song được gọi là một

tiến trình và mỗi câu lệnh cần phải khai báo như một tiến trình Khi lập trình

chúng ta phải chỉ rõ là các tiến trình sẽ kết hợp với nhau một cách tuần tự hay song

song Có thể nói, Occam là tập con của Ada

Các tiến trình trong Occam

Có ba tiến trình nguyên thuỷ trong Occam:

 Tiến trình gán: thay đổi giá trị của các biến

 Tiến trình Input: nhận dữ liệu vào từ các kênh vào (cổng vào)

 Tiến trình Output: gửi dữ liệu ra các kênh ra.

Ví dụ: Giả sử hai tiến trình A và B nhận các dữ liệu vào, tính bình phương của

chúng và gửi cho tiến trình C

user ? x Tiến trình A đọc dữ liệu vào cho x từ kênh user

C ! x * x Tiến trình A gửi x2 cho C

user ? y Tiến trình A đọc dữ liệu vào cho y từ kênh user

C ! y * y Tiến trình A gửi y2 cho C

Các cấu trúc điều khiển

Tiến trình trong Occam còn được xây dựng từ tổ hợp ba cấu trúc điều khiểnsau để tạo ra những tiến trình phức hợp hơn

 SEQ: cấu trúc tuần tự, các thành phần của các tiến trình trong đó thực

hiện lần lượt theo thứ tự và tiến trình này kết thúc khi thành phần cuốicùng kết thúc

 PAR: cấu trúc song song, các thành phần của các tiến trình trong đó thực

hiện đồng thời và tiến trình này kết thúc khi tất cả các thành phần của nókết thúc

 ALT: cấu trúc tuyển chọn, chọn một trong các thành phần của các tiến

trình để thực hiện nếu nó thoả mãn điều kiện lựa chọn và tiến trình này kếtthúc khi thành phần được lựa chọn kết thúc

Ngoài ra, còn có những cấu trúc điều khiển IF, gọi là tiến trình điều kiện để chọn một tiến trình thành phần khi biểu thức Boolean có giá trị true và cấu trúc lặp

WHILE, gọi là tiến trình lặp để thực hiện lặp lại tiến trình thành phần cho đến khi

biểu thức điều kiện Boolean nhận giá trị true.

Ví dụ: Giả sử có hai tiến trình giống nhau cùng nhận dữ liệu vào và cộng dồn vào

tổng

CHAN In1, In2:

CHAN Out1, Out2:

VAR Sum1, Sum2:

VAR Item1:

SEQIn1 ? Item1Sum1 := Sum1 + Item1Out1 ! Item1

Tiến trình thứ haiWhile TRUE

VAR Item1:

SEQIn2 ? Item2Sum2 := Sum2 + Item2Out2 ! Item2

Sự trao đổi giữa các tiến trình

Trong ví dụ trên, các tiến trình không cần trao đổi với nhau vì mỗi tiến trìnhđều sử dụng các biến cục bộ của riêng mình Khi có nhiều tiến trình muốn trao đổi

dữ liệu với nhau thì phải trao đổi với nhau trên cùng một kênh truyền dữ liệu Mộttiến trình gửi dữ liệu ra một kênh truyền và tiến trình kia nhận dữ liệu từ kênh đó.Trong chương trình Occam, mỗi tiến trình thực hiện trên một bộ xử lý và truyềnthông điệp tới những bộ xử lý lân cận theo kiến trúc hình khối (hình 2-8)

Ví dụ: chương trình đơn giản trong Occam để tính số π sử dụng tích phân củađường cong 4/(1+x2) trong khoảng 0 và 1 Các dòng 1-3 định nghĩa các hằng N là

số các đoạn con tối đa để tính tích phân, PROCESS là số các tiến trình được tạo ra

và CHUNK lá số đoạn giao cho mỗi tiến trình Trong các dòng 6-17 thì các tiếntrình thực hiện song song và sau đó, tiến trình cuối cùng thực hiện các lệnh từ 18-

6 PAR i = [0 FOR PROCESS]

7 REAL64x, localsum, width:

9 localsum := 0.0

10 width := 1.0 / N

11 x := ((i * CHUNK) + 0.5) * width

12 SEQ i = [0 FOR CHUNK]

27 ALT i = [0 FOR PROCESS]

28 (got[i] = FALSE) & sum’i]? Y

30 pi := pi + y

31.output ! “So Pi gần đúng là: “; pi

3.2.3 Lập trình song song với PVM

Phần này chúng ta giới thiệu tóm tắt cách phát triển các chương trình songsong thực hiện trên những máy tính nối mạng trong môi trường UNIX, hoặc mạng

LAN PVM là hệ thống cho phép một tuyển tập các trạm máy tính không thuần nhất và các máy tính kết nối với nhau để xử lý song song ([1], [7]) Nó có

những đặc tính chính:

 Thực hiện theo mô hình truyền thông điệp tường minh

 Hỗ trợ sự kết nối không thuần nhất: PVM hỗ trợ sự kết hợp của các máy

tính, mạng máy tính và nhiều loại chương trình ứng dụng

 Hỗ trợ đa bộ xử lý: PVM sử dụng những khả năng truyền thông điệp trong

hệ đa bộ xử lý để khai thác hết khả năng của phần cứng

 Tính toán dựa trên tiến trình: Đơn vị điều khiển thực hiện song song trong PVM là một tác vụ, đó là một luồng (Thread) làm nhiệm vụ điều khiển sự

truyền thông và tính toán

 Thay đổi cấu hình theo yêu cầu: Các chương trình có thể thực hiện trên tập các máy được lựa chọn theo yêu cầu của NSD

PVM xử lý tất cả các vấn đề định tuyến truyền thông điệp, chuyển đổi dữliệu, lập lịch trong mạng máy tính Hệ thống PVM gồm hai thành phần chính:

 Khối pvmd hoặc pvm3 đặt thường trú trên tất cả các máy tính để tạo ra

máy ảo

 Thư viện các chương trình con giao diện của pvm: chứa các chương trình

con để truyền thông điệp, quản lý các tiến trình, phối hợp các tác vụ vàthay đổi các máy ảo

Mô hình tính toán của PVM được xác định như hình 3-1 và một dạng kiếntrúc có thể thiết lập như hình 3-2

Hình 3-1 Mô hình tính toán của PVMCụm 1

Cụm 2

Cụm 3Hình 3-2 Một kiến trúc của PVM

Phương thức thực hiện chương trình trong PVM như sau:

 Những chương trình viết bằng C/C++, Fortran 77 có thể chứa những lờigọi các hàm thự viện của PVM Đây là những ngôn ngữ lập trình đượcPVM hỗ trợ

 Các chương trình được dịch theo kiến trúc của hệ thống (host pool), các

tệp mã đích (object file) được đặt vào những nơi mà mọi máy tính đều truycập được

 NSD tạo ra một bản sao của tác vụ chủ (master) hoặc khởi động một tác

vụ Một tiến trình được bởi động bởi một tiến trình khác được gọi là tiến

Nhập dữ liệu và phân đoạn

Xuất dữ liệu và hiển thị kết quả

MPPBridge

SIMD

trình tớ (slave) Những tiến trình này thực hiện một số tính toán cục bộ và

trao đổi với nhau để giải quyết bài toán đặt ra

Ví dụ: Chương trình in ra màn hình định danh của tác vụ (số nguyên) nhận được từ pvm_myid(), sau đó sử dụng:

pvm_spawn() để tạo ra một bản sao và gọi chương trình hello_other

pvm_recv() để nhận thông điệp

pvm_exit() để kết thúc chương trình trong PVM

pvm_parent() nhận một tác vụ của tiến trình tớ từ tiến trình chủ

pvm_initsend() khởi tạo buffer để gửi

pvm_pkstr() đặt một xâu vào buffer để gửi đi

pvm_upkstr() đọc một xâu vào buffer

pvm_send() chuyển dữ liệu ở buffer tới tiến trình nhận được xác định bởi ptid.

/* Chương trình chủ có tên Hello.c */

#include “pvm3.h”

main(){

int cc, tid, msg;

char buf[100];

printf(“Master ID number %x\n”, pvm_mytid());

cc = pvm_spawn(“Hello_other”, (char**)0, 0, “”, 1, &tid); if(cc== 1){

msg = 1;

pvm_recv(tid, msg);

pvm_upkstr(buf);

printf(“From master %x: %s\n”, tid, buf);

} else printf(“Cannot start hello_other\n”);

5MP, HP-9000 PA-RISC, Intel Paragon, Silicon Graphics IRIS, Sun 4, DEC MicroVAX, v.v.

3.3 Sự phụ thuộc dữ liệu và đồ thị ưu tiên của các tiến trình

Nghiên cứu quan hệ ưu tiên tính toán trong xử lý song song là rất quan

trọng Quyền ưu tiên được thể hiện ở mức độ phụ thuộc tính toán của các câu

lệnh Độ phụ thuộc tính toán có thể xét ở nhiều mức độ tính toán khác nhau, như ở mức khối lệnh, mức câu lệnh, mức biến và mức các bit Quan hệ thứ tự

thực hiện tính toán cần phải được xác định để đảm bảo quá trình tính toán làchính xác

Ví dụ: Xét sự thực hiện của dãy các lệnh sau:

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ủa biến B được sử dụng ở S1 Do vậy, có sự phụ thuộc d4

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 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 Dovậy, có sự phụ thuộc của S2, S3 vào S3 (ký hiệu là d6, d7)

Sự thực hiện song song của ba câu lệnh trên là một phương án để thực hiện

tuần tự Chúng ta có thể sử dụng đồ thị phụ thuộc dữ liệu để biểu diễn các phụ

thuộc dữ liệu của các câu lệnh nêu trên

Đồ thị phụ thuộc dữ liệu có thể định nghĩa như một đồ thị định hướngG=(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.Cần phải xác định tất cả các sự phụ thuộc khi xử lý song song Thông thường,

chúng ta chỉ xét những sự phụ thuộc giữa các câu lệnh đơn Một cách hình thức,

chúng ta ký hiệu:

DEF(S) - tập tất cả các biến có giá trị bị thay đổi khi thực hiện câu lệnh S USE(S) - 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 S

Ví dụ: S: B = A + C – 2.0

DEF(S) = {B}, USE(S) = {A, C}

Hãy xét hai câu lệnh S1, S2 và dựa vào tập các biến nêu trên, chúng ta phânloại các phụ thuộc trong chương trình thành các loại như sau

1 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) ≠ φ (rỗng) Đâ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ộtbiến và giá trị này phải được tính ở S1 Nghĩa là khi xuất hiện phụ thuộcdò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 d 1 , d 2 , d 3 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à:

2 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) ≠ φ (rỗng) Đâ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 khichú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 d 4 , d 6 , d 7 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à:

3 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) ≠ φ (rỗng) 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ớ Dovậ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 d 5 là loại phụ thuộc

dữ liệu ra

Quan hệ phụ thuộc dữ liệu ra được ký hiệu là:

4 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) ≠ φ (rỗng) Bởi vì các lệnhnày chỉ truy cập (đọc) và không làm thay đổi giá trị của các biến đó, dovậ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