Nghiên cứu thuật toán điều khiển thích nghi luồng tham chiếu để nâng cao tốc độ

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC THÁI NGUYÊN CHU ĐỨC TOÀN NGHIÊN CỨU THUẬT TOÁN ĐIỀU KHIỂN THÍCH NGHI LUỒNG THAM CHIẾU ĐỂ NÂNG CAO TỐC ĐỘ CHO CÁC HỆ XỬ LÝ SONG SONG CHUYÊN DỤNG LUẬN ÁN TIẾN SĨ KỸ THUẬT THÁI NGUYÊN - 2014 Số hóa bởi Trung tâm Học liệu http://www.vn/ THÁI NGUYÊN / 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC THÁI NGUYÊN ________________ CHU ĐỨC TOÀN NGHIÊN CỨU THUẬT TOÁN ĐIỀU KHIỂN THÍCH NGHI LUỒNG THAM CHIẾU ĐỂ NÂNG CAO TỐC ĐỘ CHO CÁC HỆ XỬ LÝ SONG SONG CHUYÊN DỤNG Chuyên ngành: Kỹ thuật Điều khiển và Tự động hóa Mã số: 62.16 LUẬN ÁN TIẾN SĨ KỸ THUẬT Cán bộ hướng dẫn khoa học 1 Cán bộ hướng dẫn khoa học 2 PGS. Đỗ Xuân Tiến PGS. Nguyễn Hữu Công THÁI NGUYÊN - 2014 Số hóa bởi Trung tâm Học liệu http://www.vn/ i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả mới nêu trong luận án là hoàn toàn trung thực và chưa từng được ai công bố trong bất kì công trình nào khác.

Ngày 05 tháng 02 năm 2014 Tác giả luận án Chu Đức Toàn Số hóa bởi Trung tâm Học liệu http://www.vn/ ii LỜI CẢM ƠN Trong quá trình làm luận án, tôi đã nhận được nhiều ý kiến đóng góp từ các thầy, cô giáo, các anh chị và các bạn đồng nghiệp. Tôi xin bày tỏ lòng biết ơn sâu sắc nhất đến tập thể hướng dẫn PGS.TS Đỗ Xuân Tiến – Học viện KTQS, PGS.TS Nguyễn Hữu Công – Đại học Thái Nguyên đã tận tình hướng dẫn tôi trong suốt quá trình làm luận án. Tôi xin cảm ơn đến ban chủ nhiệm và hội đồng khoa học của bộ môn: Tự động hóa XNCN - Khoa Điện - Trường Đại học Kỹ thuật Công nghiệp, Đại học Thái Nguyên; bộ môn Kỹ thuật Vi xử lý – Học viện Kỹ thuật Quân sự. Tôi xin chân thành cảm ơn lãnh đạo và các chuyên viên Phòng thí nghiệm Kỹ thuật Vi xử lý – Học viện Kỹ thuật Quân sự, đã tạo điều kiện về trang thiết bị thực nghiệm để tôi hoàn thành được phần thực nghiệm và mô phỏng của luận án.

Tôi xin chân thành cảm ơn Khoa Sau đại học - Trường Đại học Kỹ thuật Công nghiệp, Đại học Thái Nguyên, xin chân thành cảm ơn Ban giám hiệu Trường Đại học Kỹ thuật Công nghiệp đã tạo những điều kiện thuận lợi nhất về mọi mặt để tôi hoàn thành khóa học Nghiên cứu sinh. Tác giả luận án Chu Đức Toàn Số hóa bởi Trung tâm Học liệu http://www.vn/ iii MỤC LỤC Trang Lời cam đoan………………………………………………………. ii Mục lục…………………………………………………………………. iii Danh mục các ký hiệu và các chữ viết tắt……………………………….

vi Danh mục các bảng……………………………………………………… viii Danh mục các hình vẽ và đồ thị………………………………………. ix MỞ ĐẦU………………………………………………………………. KIẾN TRÚC HỆ XỬ LÝ SONG SONG ĐA CPU 6 1. Tài nguyên hệ thống……………………………………….

Tài nguyên phần cứng…………………………………………. Tài nguyên phần mềm…………………………………………. Định nghĩa hệ xử lý song song …………………………. Phân loại hệ xử lý song song……………………………………….

Sơ đồ phân loại của Flynn……………………………………. Sơ đồ phân loại của Handler…………………………………. Kiến trúc chung hệ xử lý song song đa CPU……………………….2 Những vấn đề liên quan đến hiệu năng………………………… 12 1. Kiến trúc chung hệ xử lý song song đa CPU chuyên dụng…….

Các đặc trưng của hệ xử lý song song chuyên dụng…………. Kiến trúc của hệ xử lý song song chuyên dụng………………… 21 1. Luận giải, định hướng nghiên cứu của đề tài………………………. Kết luận chương 1………………………………………….

XÂY DỰNG MÔ HÌNH TOÁN HỌC THAM CHIẾU BỘ NHỚ DÙNG CHUNG TRONG HỆ XỬ LÝ SONG SONG ĐA 31 CPU CHUYÊN DỤNG 2. 31 Số hóa bởi Trung tâm Học liệu http://www. Xây dựng mô hình toán học tham chiếu bộ nhớ dùng chung trong 35 hệ xử lý song song đa CPU chuyên dụng………………………………. Mô hình truyền thống tham chiếu bộ nhớ dùng chung trong hệ xử 35 lý song song đa CPU………….

Mô hình cải tiến tham chiếu bộ nhớ dùng chung trong hệ xử lý 36 song song đa CPU…………. Xác định đại lượng P – Xác suất thanh ghi tham chiếu lối vào 37 rỗi…………. Xác định đại lượng Ep – Hiệu năng khi các hàng đợi của các 44 mô đun nhớ đầy …………. Xác định El - Hiệu năng khi thanh ghi tham chiếu lối vào băng 47 nhớ rỗi…………………………………………………………………… 2.

Kết luận chương 2…………………………………………………. XÂY DỰNG MÔ HÌNH ĐIỀU KHIỂN THÍCH NGHI 53 CHO HỆ XỬ LÝ SONG SONG ĐA CPU CHUYÊN DỤNG………. Xây dựng phần mềm khảo sát. Xây dựng mô đun chính phần mềm khảo sát.

Xây dựng mô đun phần mềm tính toán hiệu năng hệ xử lý song 55 song đa CPU trong quan hệ với chu kỳ bộ nhớ dùng chung Tc. Xây dựng mô đun phần mềm tính toán hiệu năng hệ xử lý song 57 song đa CPU trong quan hệ với số lượng luồng tham chiếu n. Xây dựng mô đun phần mềm tính toán hiệu năng hệ xử lý song song đa CPU trong quan hệ với chu kỳ bộ nhớ Tc khi khảo sát ở giá trị 59 ρ=0,5. Khảo sát, đánh giá hiệu năng mô hình điều khiển ………………….

Xây dựng mô hình điều khiển thích nghi…………………………. Công nghệ FPGA…………………………………………………… 69 3. Tái kiến trúc phần cứng bằng chương trình……………………… 69 3. Thiết kế hệ thống trên FPGA………………………………… 75 Số hóa bởi Trung tâm Học liệu http://www.

Sơ đồ nguyên lý điều khiển thích nghi theo tham số m…………… 83 3. Kết luận chương 3…………………………………………. 85 KẾT LUẬN CHUNG VÀ KIẾN NGHỊ. 86 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ.

87 126 TÀI LIỆU THAM KHẢO. 88 Số hóa bởi Trung tâm Học liệu http://www.vn/ vi DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa  Là tốc độ tới của hệ thống  Là tốc độ phục vụ của hệ thống Ta Thời gian truy nhập bộ nhớ  Thời gian trễ mạch chốt E Hiệu năng của bộ nhớ song song dùng chung Hiệu năng của một tham chiếu khi thanh ghi tham chiếu lối vào EP bận El Hiệu năng khi thanh ghi tham chiếu lối vào rỗi Tl Chu kỳ của băng logic Tp Chu kỳ hiệu quả của bộ nhớ Độ trễ nhỏ nhất để truyền một tham chiếu từ hàng chờ vào môđun Td nhớ Tc Chu kỳ vật lý của môđun nhớ P Xác suất thanh ghi lối vào rỗi k Số môđun nhớ trong mỗi băng logic l Số lượng băng logic trong hệ thống m Kích thước hàng chờ của mỗi môđun nhớ Tốc độ khởi tạo tham chiếu trung bình của mỗi CPU (Xác suất q một luồng tham chiếu đang ở trạng thái tự do sẽ khởi tạo một tham chiếu)  Xác suất mà một luồng tham chiếu ở trạng thái tự do Xác suất một luồng tham chiếu đang thực hiện một tham chiếu thành  công Xác suất một luồng tham chiếu đang thực hiện một tham chiếu  không thành công  Xác suất để một tham chiếu thành công Số hóa bởi Trung tâm Học liệu http://www.vn/ vii DANH MỤC CÁC TỪ VIẾT TẮT ALU Arithmetic Logic Unit đơn vị logic số học CISC Bộ VXL với tập lệnh đầy đủ CU Control Unit – đơn vị điều khiển; DS Data stream – luồng dữ liệu EX Execution - Thực hiện lệnh FIFO First In First Out - Vào trước ra trước FPGA Field Programmable Gate Array mảng cổng logic lập trình được ID Instruction decoder – giải mã lệnh IF Instruction fetch – nạp lệnh IS Instruction stream – luồng lệnh MIMD Multiple Instruction Multiple Data - Đa dòng lệnh đa dòng dữ liệu MM Memory Module – Mô đun nhớ; OF Operate Fetch – nạp toán hạng PE Processing Element – Phần tử xử lý PU Processing Unit – Đơn vị xử lý. RISC Bộ vi xử lý với tập lệnh rút gọn TGBL Thanh ghi băng logic KGNDC Không gian nhớ dùng chung Số hóa bởi Trung tâm Học liệu http://www.vn/ viii DANH MỤC CÁC BẢNG Danh mục Nội dung Trang Bảng 1.1: Phân loại kiến trúc của Flynn 8 Bảng 1.2: Sơ đồ phân loại của Erlanger 10 So sánh một số tính năng của hệ xử lý song Bảng 1.3: 21 song đa dụng và chuyên dụng Bảng 1.4: Thống kê khả năng xuất hiện các loại lệnh 24 Xác suất một yêu cầu đến khi hàng đợi chưa Bảng 3.1: 63 đầy theo m và ρ với qui tắc hàng đợi M/D/1/m Bảng 3.2: Bảng điều khiển 84 Số hóa bởi Trung tâm Học liệu http://www.vn/ ix DANH MỤC CÁC HÌNH VẼ Danh mục Nội dung Trang Hình 1.1: Mô hình kiến trúc SISD 8 Hình 1.2: Mô hình kiến trúc SIMD 8 Hình 1.3: Mô hình kiến trúc MISD 9 Hình 1.4: Mô hình kiến trúc MIMD 9 Hình 1.5: Mô hình kiến trúc chung của hệ xử lý song song 11 Hình 1.6: Cấu trúc của khối xử lý lệnh trong máy CRAY-1 12 Hình 1.7: Kiến trúc đường ống 4 tầng 13 Hình 1.8: Hiệu ứng đường ống 14 Hình 1.9: Cấu trúc của bộ nhớ phân cấp trong các hệ xử lý 19 Hình 1.10: Kiến trúc của hệ xử lý song song đa CPU chuyên dụng 21 Hình 1.11: Mô hình kiến trúc: a) Hệ xử lý CISC, b) Hệ xử lý RISC 23 Hình 1.12: Tác động của lệnh rẽ nhánh (I3B) đến đường ống 4 tầng 24 Hình 1.13: Tổ hợp tên lửa S-300 PMU1 của Việt nam 27 Hình 1.14: Cự ly quan sát của hệ 28 Tham chiếu bộ nhớ dùng chung trong hệ xử lý song Hình 2. Sơ đồ hàng đợi tổng quát; Hình 2.

Sơ đồ hàng đợi cho hệ xử lý song song đa CPU Tổ chức băng băng nhớ đan xen cho KGNDC trong hệ Hình 2.3: xử lý song song đa CPU. 39 Giao diện phần mềm tính toán hiệu năng hệ xử lý song Hình 3.1: song đa CPU 55 Giao diện phần mềm tính toán hiệu năng hệ xử lý song Hình 3.2: song đa CPU trong quan hệ với chu kỳ bộ nhớ dùng 57 chung Tc Số hóa bởi Trung tâm Học liệu http://www.vn/ x Giao diện phần mềm tính toán hiệu năng hệ xử lý song Hình 3.3: song đa CPU trong quan hệ với số lượng luồng tham 59 chiếu n. Giao diện phần mềm tính toán hiệu năng hệ xử lý song Hình 3.4: song đa CPU trong quan hệ với chu kỳ bộ nhớ Tc khi 61 khảo sát ở giá trị ρ=0.5 Hiệu quả tham chiếu ngẫu nhiên băng nhớ logic theo T Hình 3.5: được so sánh trong hai trường hợp khi m =2 và trường 62 hợp không có băng nhớ logic (m=0, Tl=Td=0) Sự phụ thuộc của E theo chu kỳ vật lý của mô đun nhớ Hình 3.6: 64 Tc khi m thay đổi Đồ thị của E theo số luồng tham chiếu n.7: 64 Tc=5 Đồ thị của E theo chu kỳ vật lý mô đun nhớ Tc khi giữ Hình 3.8: 65 cố định ρ= 0,5 Hình 3.9: Sơ đồ khối hệ thống điều khiển thích nghi cơ bản 67 Sơ đồ khối điều khiển thích nghi luồng tham chiếu cho hệ xử Hình 3.10: 68 lý song song đa CPU chuyên dụng Hình 3.11: a) Cấu trúc của PLA b) Cấu trúc của PAL 71 Hình 3.12: Mô tả mô hình của một FPGA 72 Hình 3.13: Cấu trúc logic Cell trong FPGA 74 Hình 3.