Xử lý song song

	TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
Xử lý song song
Giáo viên hướng dẫn : Bùi Thị Thủy
	Sinh viên thực hiện : Nguyễn Đức Mạnh
	 Hoàng Vũ Quân
 Phạm Thu Phượng
Hà Nội - 2015
I. Bộ xử lí từ lệnh rất dài
Kỹ thuật đó được tính toán song song xem xét từ các thuật toán song song ở từng cấp lệnh, đó là cách cụ thể hóa tốt nhất mà người ta có thể hy vọng sẽ chia nhỏ một thuật toán. Một VLIW nghĩa là một số lệnh hoặc mã vận hành được gửi đến các CPU được thực hiện đồng thời. Chọn các lệnh được ban hành trong một VLIW được thực hiện bởi trình biên dịch. Trình biên dịch phải đảm bảo rằng không có sự phụ thuộc giữa các lệnh trong một VLIW và các phần cứng phải có thể hỗ trợ thực hiện tất cả các lệnh. Một lợi thế tiềm năng hiện nay hơn kênh tương tác kể từ khi trình lập lịch lệnh được thực hiện trước khi mã thực thi chạy.
Hình 2.16 minh họa một bộ vi xử lý sử dụng VLIW để kiểm soát các hoạt động của hai đơn vị đường dữ liệu. Hình 2.16a cho thấy cấu trúc của bộ xử lý nơi VLIW chứa 2 lệnh. Mỗi lệnh được sử dụng để kiểm soát một đơn vị đường dữ liệu. Hình 2.16b cho thấy nội dung của VLIW tại mỗi chu kỳ xử lý khác nhau.Con số này được dựa trên những trình bày trong tài liệu tham khảo 18 và 24. Mỗi dòng thể hiện cho một kết quả của VLIW. Mỗi cột dọc biểu diễn cho chu kỳ máy. Một hộp màu xám cho một lệnh trong vòng từ VLIW và một hộp trống rỗng chỉ ra một noop. Một lệnh noop được sử dụng khi biên dịch là không thể giải quyết sự phụ thuộc giữa các lệnh hoặc các đường dữ liệu sẵn có	
II.Song song cấp lệnh và bộ xử lý siêu vô hướng
	Một bộ xử lý siêu vô hướng có thể đồng thời thực hiện một số lệnh từ các luồng lệnh độc lập [18]. Bộ vi xử lý siêu vô hướng có một trình lập lịch động kiểm tra các lệnh nằm trong bộ nhớ đệm / bộ nhớ và quyết định lệnh sẽ được đưa vào các luồng lệnh tương ứng.Sự lập lịch động chấp nhận các lệnh lệch khỏi trật tự và thực thi. Hình 2. 17 cho thấy một cấu tạo chung của một bộ xử lý ba chiều siêu vô hướng nơi bộ vi xử lý có chứa ba chỉ thị luồng dữ liệu hoạt động trên ba luồng đợn vị dữ liệu độc lập. Một máy tính siêu vô hướng có một số luồng lệnh và các đơn vị luồng dữ liệu mà có thể làm việc song song để thực thi các lệnh được đưa đến cho chúng từ CPU. Sử dụng kỹ thuật này, các tốc độ thực thi lệnh sẽ lớn hơn tốc độ đồng hồ. Đối với một kiến trúc siêu vô hướng ba chiều với một luồng lệnh, có thể có tới ba lệnh được thực thi mỗi chu kỳ đồng hồ.
Hình 2.17 Tổng hợp cấu trúc bộ xử lý siêu vô hướng ba chiều 
Hình 2.18 Liên lệnh của bộ xử lý siêu vô hướng hai chiều
	Các luồng lệnh cho một bộ xử lý siêu vô hướng hai chiều hình. 2.18,đó là sự thay đổi của hình. 2.14, cho thấy một thực tế là hiện nay chúng ta có hai chỉ thị cho hai luồng lệnh.
Hình 2.19 So sánh chương trình thực hiện trên VLIW và Bộ xử lý siêu vô hướng như bộ vi xử lý. (a) Bộ xử lý VLIW. (b) Bộ xử lý siêu vô hướng
Tại điểm này, nó dễ dàng giải thích sự khác biệt giữa VLIW và bộ vi xử lý siêu vô hướng. Cả hai kỹ thuật dựa trên sự hiện diện của một số ALU thực hiện một số hoạt động song song. Sự khác biệt chính nằm ở cách thức các lệnh được ban hành. Hình 2.19 cho thấy chuỗi lệnh của chương trình bắt đầu từ giai đoạn biên dịch để thực hiện chỉ đạo của ALU song song cho VLIW và bộ vi xử lý siêu vô hướng. Ý tưởng chủ chốt trong bộ xử lý siêu vô hướng là khả năng thực hiện nhiều chỉ thị song song. Trình biên dịch và phần cứng kỹ thuật được sử dụng để tối đa hóa số lượng kết quả của các lệnh được sử dụng song song. Tuy nhiên, có sự giới hạn để đạt được mức độ tăng tốc [3, 18, 20, 25]:
 • Phụ thuộc dữ liệu
 • Phụ thuộc thủ tục
 • Phụ thuộc xung đột tài nguyên
 • Phụ thuộc đầu ra
 • Chống phụ thuộc.
1. Phụ thuộc dữ liệu thực: đọc sau viết (RAW)
RAW ngụ ý rằng lệnh i nên đọc một giá trị mới từ một thanh ghi sau khi lệnh j đã thực hiện xong hoạt động viết. Giả sử lệnh I0 sản xuất một số kết quả và lệnh I1 sử dụng kết quả đó. Chúng ta nói rằng I1 có sự phụ thuộc dữ liệu thực vào I0 và thực hiện các I1 nhưng nó phải trì hoãn cho đến khi I0 làm xong. Sự phụ thuộc dữ liệu thực này hay phụ thuộc như thể hiện trong hình. 2.20a. Số liệu này cho thấy I0 đọc đối số đầu vào của nó từ thanh ghi.
Hình 2.20 
Hình 2.21 Phụ thuộc thủ Tục.
Ro và R1 và kết quả đầu ra được lưu trữ trong R2. Nếu I0 là được tải từ lệnh bộ nhớ thì nó có thể có một độ trễ lớn hoặc thời gian chờ. Trong trường hợp đó, các giai đoạn thực hiện của I1 sẽ phải được trì hoãn bởi nhiều hơn một chu kỳ đồng hồ.

2. Phụ thuộc thủ tục
Một vấn đề chính với lệnh máy tính là sự hiện diện của lệnh rẽ nhánh. Hình 2.21 cho thấy các luồng lệnh có hai lệnh I0 và I1. Tuy nhiên, I1 là một lệnh rẽ nhánh và nó không thể xác định lênh nào sẽ được thi hành cho đến khi I1 sản xuất đầu ra của nó. Do đó, giai đoạn lấy lệnh tiếp theo phải được trì hoãn như thể hiện trong hình. 2.21.
3. Xung đột tài nguyên
Một cuộc xung đột tài nguyên tạo ra khi hai hay nhiều lệnh yêu cầu các tài nguyên tương tự từ bộ xử lý. Ví dụ về các nguồn tài nguyên bộ xử lý dùng chung là bộ nhớ, bộ nhớ đệm, hệ thống phụ chuyển dữ liệu giữa các thành phần bên trong máy tính, tập tin thanh ghi, v..v. Một cuộc xung đột tài nguyên được giải quyết khi thực hiện các lệnh thực thi bị trì hoãn. Hình 2.20 có thể được sử dụng để hình dung ảnh hưởng của xung đột tài nguyên trên các luồng lệnh. Một lưu ý rằng, không giống như các phụ thuộc dữ liệu thực, một cuộc xung đột tài nguyên có thể được loại bỏ bằng cách sao chép các tài nguyên được chia sẻ. Đây có thể là một giải pháp đắt tiền hoặc không thực tế. Ví dụ, loại bỏ
Hình 2.22 Phụ thuộc đầu ra.
xung đột đơn vị dấu phẩy động có thể liên quan đến việc thiết kế hai đơn vị dấu phẩy động lien lạc với mỗi ALU. Điều này có thể đòi hỏi một lượng nhỏ silicon tài sản thực. Xung đột bộ nhớ đệm có thể được loại bỏ bằng cách thiết kế một bộ nhớ đệm dual-ported hoặc sao chép các bộ nhớ đệm. Cả hai lựa chọn có thể không được thực tế.
4. Phụ thuộc đầu ra: Viết sau khi viết (WAW)
WAW hiểu rằng lệnh i viết một toán hạng sau khi lệnh j đã viết một toán hạng khác trong thanh ghi. Trình tự là quan trọng bởi vì từ khi mà thanh ghi gồm có giá trị được viết bởi lệnh j sau khi cả hai lệnh i và j đã hoàn thành một thực thi. Một sự phụ thuộc đầu ra xảy ra khi hai lệnh, I0 và I1, lưu kết quả đầu ra của nó trong cùng một thanh ghi. Trong trường hợp đó, các nội dung trong thanh ghi tại một thời gian nhất định phụ thuộc vào lệnh hoàn thành cuối cùng, I0 và I1. Chúng tôi chứng minh điều này bằng cách sử dụng ngôn ngữ dịch chuyển thanh ghi (RTL) đoạn mã chỉ ra bất kỳ sự hoạt động nhị phân [18] đòi hỏi hai đầu vào của thanh ghi:
I0: R0<- R0 op R1
I1: R2<- R0 op R2
I2: R0<- R3 op R4
I3: R5<- R0 op R5
Hình 2.22 cho thấy biểu đồ sự phụ thuộc của các lệnh.Số liệu này cho thấy hai trường hợp của phụ thuộc dữ liệu thực: I1 phụ thuộc vào I0 và I3 phụ thuộc vào I2. Lệnh I0 và I2 chương trình phụ thuộc đầu ra từ khi kết quả lưu trữ của nó trong thanh ghi R0. Trình tự các lệnh khi chúng được viết bằng đoạn mã RTL ở bên trên chỉ ra rằng ý định của chúng tôi là I1 sử dụng các nội dung của R0 sau khi I0 hoàn tất. Tương tự như vậy I3 sử dụng các nội dung của R0 sau khi I2 được hoàn thành. Chúng ta phải đảm bảo rằng I2 bắt đầu giai đoạn thực thi sau khi đã hoàn thành giai đoạn I0 thực thi xong.
5. Chống phụ thuộc: Viết sau khi đọc (WAR)
WAR hiểu rằng i viết một toán hạng sau khi j đã đọc nội dung trong thanh ghi. Chống phụ thuộc được minh họa với sự giúp đỡ của các đoạn mã RTL dùng để giải thích sự phụ thuộc đầu ra như hình. 2.22. Chúng tôi lưu ý ở đây là lệnh I1sử dụng nội dung của thanh ghi R0 như một toán hạng đầu vào. Chúng ta phải đảm bảo rằng I1 đã thực hiện xong trước khi I2 bắt đầu thực hiện để các nội dung của R0 không bị xáo trộn trong khi I1 đang sử dụng nó.
III. Bộ xử lý đa luồng
 	Theo định nghĩa ở đầu chương này, một luồng là một phần của một chương trình chia sẻ tài nguyên của bộ xử lý với các luồng khác. Một bộ xử lý đa luồng là một bộ xử lý có khả năng chạy một số phần mềm cùng một lúc. Tất nhiên, một bộ xử lý đơn giản chỉ có một ALU(một bộ số học và logic) và có thể quản lý để chạy một luồng tại một thời điểm. Tài liệu tham khảo [24] cung cấp một cuộc thảo luận toàn diện về các luồng.
 	Hình 2.23a cho thấy trường hợp của một bộ xử lý đơn giản chạy một hệ điều hành cho phép chạy chỉ có một luồng. Chúng tôi thấy trong hình, tình hình khi các ngăn luồng T0, chẳng hạn như do chờ đợi một bộ nhớ truy cập hoặc cache miss(dữ liệu không có sẵn trong bộ nhớ đêm mà phải chờ cập nhật từ bộ nhớ chính). Tất nhiên, việc thực hiện chương trình tạm dừng cho đến khi truy cập bộ nhớ đã được hoàn thành.
Hình 2.23b cho thấy trường hợp của một bộ xử lý đơn chạy một hệ điều hành có hỗ trợ xử lý đa luồng. Hai luồng T0 và T1có sẵn.Hệ điều hành lập lịch trình để thực thi và khi ngăn T1, luồng T1ngay lập tức được nạp và chạy cho đến khi T0 là sẵn sàng nối lại. Trong một trường hợp như vậy, một hệ điều hành lập lịch trước được giả định nơi thực hiện, T1 được dừng lại khi T0 là đã sẵn sàng để tiếp tục hoạt động.
Hình 2.23c cho thấy trường hợp của một bộ xử lý siêu vô hướng hai chiều chạy một hệ điều hành cho phép chạy chỉ có một luồng. Chúng tôi nhìn thấy trong hình này luồng hiện đang chạy trên hai ALU giả phụ thuộc dữ liệu đã được giải quyết.
Hình 2.23d cho thấy trường hợp của một bộ xử lý siêu vô hướng hai chiều chạy một hoạt động đa luồng. Chúng tôi nhìn thấy trong hình này luồng hiện tại đang chạy trên hai ALU giả phụ thuộc dữ liệu đã được giải quyết. Khi để các quầy hàng, luồng T1 được bật và bắt đầu chạy cho đến khi sẵn sàng để quay lại lần nữa.