ĐẠ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 K2010
( 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?

Bài làm :
+ Một hệ thống như thế nào được gọi là máy tính song song ?
- Một hệ thống có thể phân rã các bài toán ban đầu thành các bài toán con nhỏ hơn để thực hiện (giải quyết) đồng thời các bài toán con đó, sau đó tổng hợp các kết quả ở các bài toán con để thu được kết quả của bài toán ban đầu. Hệ thống như vậy được gọi là máy tính song song. Với khái niệm như vậy thì ta thấy hai loại kiến trúc máy tính SIMD và MIMD có thể được xem như là máy tính song song.
- Máy tính song song là một tập các bộ xử lý 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 là kiểu đa luồng lệnh, đa luồng dữ liệu nên có những đặc điểm khác so với mạng các máy tính khác như sau :
- Mỗi bộ xử lý có thể thực hiện những luồng lệnh khác nhau trên các luồng dữ liệu riêng.
- Và 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 khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý trong hệ thống.
+ 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 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.

Bài làm :
- Mục đích và ý nghĩa của đồ thị phụ thuộc dữ liệu :
+ Mục đích của đồ thị phụ thuộc dữ liệu : là nhằm xác định mức độ phụ thuộc dữ liệu giữa các tiến trình.
+ Ý nghĩa của đồ thị phụ thuộc dữ liệu : là làm tăng mức độ song song của chương trình và đảm bảo quá trình tính toán là chính xác.
- Một đoạn chương trình 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 và phụ thuộc dữ liệu ra :
X := Y * C (S1)
Y :=X * C+E (S2)
X :=X+Y – E (S3)
Với DEF(S1) ={X}; USE(S1) ={Y, C}
DEF(S2) ={Y}; USE(S2) ={X, C, E}
DEF(S3) ={X}; USE(S3) ={X, Y, E}
Vì DEF(S1)(USE(S2)={X}≠ф nên S1, S2 loại phụ thuộc dòng dữ liệu
Vì DEF(S1)(USE(S3)={X}≠ф nên S1, S3 loại phụ thuộc dòng dữ liệu
Vì DEF(S2)(USE(S3)={Y}≠ф nên S2, S3 loại phụ thuộc dòng dữ liệu
Vì DEF(S2)(USE(S1)={Y}≠ф nên S1, S2 loại phản phụ thuộc dữ liệu
Vì DEF(S3)(USE(S2)={X}≠ф nên S2, S3 loại phản phụ thuộc dữ liệu
Vì DEF(S3)(DEF(S1)={X}≠ф nên S1, S3 loại phụ thuộc dữ liệu ra
Vì USE(S2)(USE