giáo trình vi xử lý tiên tiến

Nguyễn Trung Đồng Tel. 0983 410 866 11 Trong máy tuần tự, sau N phép cộng, tổng sẽ là kết quả ở biến SUM. Nếu mỗi phép cộng được thực hiện trong khoảng thời gian là Tadd thì tổng thời gian là xấp xỉ NTadd . Giả sử có một máy tính có n bộ xử lý P1, P2, …, Pn giống nhau được kết nối theo cấu trúc mảng 2 chiều, mỗi bộ đồng thời tiếp nhận (receive) và gửi (send) dữ liệu cho bộ xử lý kề cận. P1 P2 P3 PN Hình I.8. Mảng tuyến tính 2 chiều gồm n bộ Vi xử lý Nếu thực hiện xử lý song song để tính tổng SUM trên hệ thống này, ta có thể chia cho mỗi bộ xử lý tính tổng của k số hạng, tổng SUM được tính qua k tổng của N/n số hạng, mà các tổng con này được tiến hành tính đồng thời. Bộ xử lý Pi chuyển kết quả phép cộng của nó cho bộ xử lý Pi+1, Kết quả của bộ xử lý Pi+1 chuyển sang cho bộ xử lý Pi+2, v.v…Như vậy, kết quả tống N số hạng sẽ nằm ở bộ xử lý Pn. Đoạn chương trình thực hiện phép tính tổng N số hạng sẽ như sau: SUM = 0; for i = 1 to k do SUM = SUM + b(i); if INDEX = 1 then begin if n > 1 then send (RIGHT, SUM) end else Hệ Vi xử lý tiên tiến 12 begin receive (LEFT, LEFTSUM); if INDEX < n then send (RIGHT,SUM); end; Từ chương trình thực hiện, thấy rằng thời gian T(n) cần để tính tổng SUM theo xử lý song song trên n bộ xử lý có 2 thành phần chính: a) N phép cộng n N đồng thời trên n bộ xử lý. TL = K1 trong đó K1 n TL thời gian tính cục bộ để tính k = là hằng số phụ thuộc vào thời gian cộng và lưu giữ trên 1 bộ Vi xử lý. b) TC là thời gian truyền thông để gửi dữ liệu trung gian qua n – 1 phép cộng. TC = K2(n-1) trong đó K2 phụ thuộc vào độ trễ truyền thông giữa các bộ Vi xử lý. T(n) = TL + TC = K1 N + K2(n-1) n Thời gian truyền dữ liệu giữa các bộ Vi xử lý lớn hơn rất nhiều so với thời gian tính toán, K2 » K1 và nếu n càng lớn thì TC càng lớn. Rõ ràng nếu n = 1 thì T(n) = K1N. I.3.Phân loại các bộ Vi xử lý song song Các bộ Vi xử lý song song có thể phân loại theo hành vi hoặc theo cấu trúc. Theo hành vi, chúng được phân loại Nguyễn Trung Đồng Tel. 0983 410 866 13 dựa trên số lượng các lệnh và các toán hạng được xử lý đồng thời, còn theo cấu trúc chúng được phân loại theo cách kết nối các bộ Vi xử lý trong hệ thống. Tuy nhiên cả hai cách phân loại này cũng chỉ là tương đối. I.3.1. Phân loại theo Flynn a) Khái niệm chuỗi lệnh và chuỗi dữ liệu Chuỗi lệnh Bộ xử lý P Chuỗi dữ liệu Bộ nhớ M Hình I.9. Trao đổi chuỗi lệnh và chuỗi dữ liệu Đơn vị xử lý P đọc các lệnh (Fetching Instructions) và các dữ liệu (Operands) từ bộ nhớ, thực hiện lệnh (Executing Instructions) và chuyển kết quả vào bộ nhớ chính. Các bước thực hiện này gộp thành 1 chu kỳ lệnh (Instruction Cycle). Các lệnh có thể hình thành một chuỗi lệnh liên tiếp nhau (Instruction Stream) được đọc từ bộ nhớ vào bộ xử lý, các toán hạng cũng hình thành 1 chuỗi dữ liệu theo sau đó tới bộ xử lý. IS CU I/O IS PU DS MU a) Kiến trúc 1 processor SISD Chương trình từ bộ nhớ chính PE1 DS LM1 DS IS CU IS PEn DS LMn DS b) Kiến trúc multiprocessor SIMD với bộ nhớ phân tán Dữ liệu được lấy từ bộ nhớ chính Hệ Vi xử lý tiên tiến 14 b) Phân loại theo Flynn là phân loại theo chuỗi lệnh và chuỗi dữ liệu. Hình a, b, c, d dưới đây mô tả các hệ xử lý song song theo cách phân loại của Flynn IS CU1 IS PU1 DS I/O Bộ nhớ chia sẻ I/O CUn IS PUn DS IS c) Kiến trúc MIMD với bộ nhớ chia sẻ IS IS IS CU1 Bộ nhớ (chương trình & dữ liệu) CU2 IS IS DS PU1 DS CUn IS PU2 DS DS I/O d) Kiến trúc MISD Các ký hiệu viết tắt: CU (Control Unit) Đơn vị điều khiển PUn Nguyễn Trung Đồng Tel. 0983 410 866 15 PU (Processing Unit) Đơn vị xử lý MU (Memory Unit) Đơn vị nhớ IS (Instruction Stream) Chuỗi lệnh DS (Data Stream) Chuỗi dữ liệu PE (Processing Element) Phần tử xử lý LM (Local Memory) Bộ nhớ cục bộ Như vậy, theo Flynn, các hệ thống xử lý song song được chia thành 4 loại theo số lượng chuỗi lệnh và chuỗi dữ liệu: a) SISD (Single Instruction Stream over Single Data Stream) Máy tính với chuỗi lệnh đơn xử lý chuỗi dữ liệu đơn. b) SIMD (Single Instruction Stream over Multiple Data Stream) Máy tính với chuỗi lệnh đơn xử lý chuỗi đa dữ liệu c) MISD (Multiple Instruction Stream over Single Data Stream) Máy tính với chuỗi đa lệnh xử lý chuỗi dữ liệu đơn d) MIMD (Multiple Instruction Stream over Multiple Data Stream) Máy tính với chuỗi đa lệnh xử lý chuỗi đa dữ liệu. Với cách phân loại như trên, trong thực tế máy tính MIMD thường được sử dụng như máy tính đa năng, còn các hệ thống SIMD và MISD là những hệ thống máy tính chuyên dụng. Trong thực tế, máy tính MIMD được sử dụng nhiều nhất, tiếp theo là các máy loại MISD rồi đến loại máy tính SIMD. 16 Hệ Vi xử lý tiên tiến I.3.2. Phân loại theo kiến trúc Theo quan điểm kiến trúc, máy tính xử lý song song được phân thành 2 loại chủ yếu là máy tính đa xử lý (Multiprocessors) và kiến trúc đa máy tính (Multicomputers). Thực tế, các máy tính này khác nhau cơ bản ở tổ chức bộ nhớ chia sẻ dùng chung và tổ chức bộ nhớ phân tán. a) Đa xử lý với bộ nhớ chia sẻ được phân ra làm 3 loại: Mô hình với bộ nhớ truy xuất đồng nhất (UMA – Uniform Memory-Access), bộ nhớ truy xuất không đồng nhất (NUMA – Nonuniform Memory-Access) và cuối cùng là loại kiến trúc chỉ-có-bộ-nhớ-cache (COMA – Cache-Only Memory Architecture).  Với mô hình đa xử lý với bộ nhớ truy xuất bộ nhớ đồng nhất (UMA), bộ nhớ vật lý được chia sẻ đồng nhất cho tất cả các đơn vị xử lý. Tất cả các bộ xử lý đều có tốc độ truy xuất bằng nhau đối với tất cả các từ nhớ. Mỗi đơn vị xử lý có thể có cache riêng, nhưng các thiết bị ngoại vi thì cũng được chia sẻ đồng nhất. Đa xử lý được gọi là hệ thống gắn kết chặt chẽ (tightly coupled systems) vì hình thức chia sẻ nguồn tài nguyên chung. Liên kết giữa các đơn vị xử lý được thực hiện dưới dạng BUS chung thông qua các chuyển mạch chéo, hoặc thông qua các mạng nhiều tầng. Các hệ thống loại này rất thích hợp với các ứng dụng đa năng và ứng dụng nhiều người dùng thông qua việc chia sẻ theo thời gian. Đặc biệt hơn, loại hệ thống này được sử dụng cho những chương trình ứng dụng lớn cần được thực thi trong khoảng thời gian bị hạn chế. Việc tổ chức đồng bộ và liên kết xử lý các sự