ĐẠI HỌC KHOA HỌC HUẾ ĐỀ KIỂM TRA HỌC PHẦN XỬ LÝ SONG SONG
KHOA CÔNG NGHỆ THÔNG TIN LỚP: CAO HỌC KHMT K2011-Phú yên
( gian: 90 phút




Câu 1: Một hệ thống như thế nào được gọi là máy tính song song? Máy tính kiểu MIMD khác với mạng các máy tính như thế nào?

Câu 2: Mục đích, ý nghĩa của đồ thị phụ thuộc dữ liệu. Hãy viết một đoạn chương trình trong đó có: Phụ thuộc dòng dữ liệu, phản phụ thuộc dữ liệu, phụ thuộc dữ liệu vào, phụ thuộc dữ liệu ra. Sau đó vẽ đồ thị phụ thuộc dữ liệu và đồ thị phụ thuộc dữ liệu rút gọn (nếu có) của đoạn chương trình trên.

Câu 3: Hai chu trình sau có tương đương về nội dung tính toán hay không? Hãy bình luận về khả năng thực hiện song song của các chu trình đó.
Do i = 1 to N
a[i] = a[i+1] + i ( I )
end
Do i = N downto 1
a[i] = a[i+1] + i ( II )
end
Câu 4:
a. Viết chương trình song song để tìm phần tử lớn nhất của một mảng số nguyên cho trước.
b. Viết chương trình song song để tìm ra tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên N cho trước.


Người ra đề


TS. Nguyễn Mậu Hân

Ghi chú: Học viên có thể sử dụng tài liệu





Câu 1 :
MTSS là một tập các BXL (thường là cùng một loại) kết nối với nhau theo một kiểu nào đó để có thể hợp tác với nhau cùng hoạt động và trao đổi dữ liệu với nhau
+ Máy tính kiểu MIMD khác với mạng các máy tính như thế nào?
MIMD
Mạng các máy tính

+ Đa bộ xử lý, trong đó mỗi bộ xử lý 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.
+ Đa máy tính nối lại với nhau




+ 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.
+ Bộ nhớ riêng

+ Có không gian địa chỉ ảo chung
+ Mỗi máy có không gian địa chỉ riêng

+ Xử lý phân tán trên một số BXL độc lập
+ Xử lý phân tán trên các máy

+Mỗi BXL thao tác độc lập và có thể thực hiện đồng thời với nhau.
+ Mỗi máy trong mạng 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
+ Mỗi máy chạy một chương trình riêng.


Câu 3 :
Hai chu trình sau có tương đương về nội dung tính toán hay không? Hãy bình luận về khả năng thực hiện song song của các chu trình đó
1. Do i = 1 to N
a[i] = a[i + 1] + i
end
2. Do i = N downto 1
a[i] = a[i + 1] + i
end

- Hai chu trình trên không tương đương về nội dung tính toán vì
Chu trình 1 : giá trị phần tử mảng thứ i bằng giá trị phần tử mảng thứ i + 1 cộng với chỉ số i.( trong đó giá trị phần tử mảng thứ i + 1 không bị thây đổi trong chu trình trước đó).
Chu trình 2 : Giá trị phần tử mảng thứ i bằng giá trị phần tử mảng thứ i + 1 cộng với chỉ số i ( trong đó giá trị phần tử mảng thứ i + 1 đã bị thây đổi trong chu trình trước đó).

- Chu trình 1 có thể thực hiện song song được vì
Chu trình 1 làm nhiệm vụ sao tất cả các phần tử của một mảng sang chính mảng đó với chỉ số giảm đi một và giá trị của mảng được cộng thêm giá trị chính bằng chỉ số mảng, do đó nó phải thực hiện tuần tự.
Nếu hai mảng đích và mảng nguồn của chu trình trên là khác nhau thì bằng cách tạo ra một bản sao của mảng gốc, chúng ta có đoạn chương trình sau:
1.1. Do i = 1 to N
a1[i] = a[i];
end
Do i = 1 to N
a[i] = a1[i + 1] + i ;
end
cả hai chu trình trên là khả song song. Nếu chúng ta có N bộ xử lý thì chỉ cần hai đơn vị thời gian của CPU là thực hiện được chu trình trên.

- Chu trình 2 không thể thực hiện song song vì
Chu