Tài liệu 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

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 - 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.52.02.16 LUẬN ÁN TIẾN SĨ KỸ THUẬT Cán bộ hướng dẫn khoa học 1 PGS. TS. Đỗ Xuân Tiến Cán bộ hướng dẫn khoa học 2 PGS.TS. Nguyễn Hữu Công THÁI NGUYÊN - 2013 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 21 tháng 6 năm 2013 Tác giả luận án Chu Đức Toàn 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 iii MỤC LỤC Trang Lời cam đoan i Lời cảm ơn 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………………………………………………………………... 1 Chương 1. KIẾN TRÚC HỆ XỬ LÝ SONG SONG ĐA CPU 6 1.1. Tài nguyên hệ thống………………………………………............... 6 1.1.1. Tài nguyên phần cứng…………………………………………. 6 1.1.2. Tài nguyên phần mềm………………………………………….. 6 1.2. Định nghĩa hệ xử lý song song ………………………….................. 7 1.3. Phân loại hệ xử lý song song………………………………………. 7 1.3.1. Sơ đồ phân loại của Flynn……………………………………. 8 1.3.2. Sơ đồ phân loại của Handler…………………………………. 9 1.4. Kiến trúc chung hệ xử lý song song đa CPU………………………. 10 1.4.1 Mô hình…………………………………………………………. 11 1.4.2 Những vấn đề liên quan đến hiệu năng………………………… 12 1.5. Kiến trúc chung hệ xử lý song song đa CPU chuyên dụng……........ 19 1.5.1. Các đặc trưng của hệ xử lý song song chuyên dụng………….... 19 1.5.2. Kiến trúc của hệ xử lý song song chuyên dụng………………… 21 1.6. Luận giải, định hướng nghiên cứu của đề tài………………………. 25 1.7. Kết luận chương 1………………………………………….............. 30 Chương 2. 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 CPU 31 CHUYÊN DỤNG 2.1. Cơ sở lý thuyết............................................................................................... 31 iv 2.2. 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 CPU chuyên dụng……………………………….. 2.2.1. Mô hình truyền thống tham chiếu bộ nhớ dùng chung trong hệ xử lý song song đa CPU…………................................................................. 2.2.2. Mô hình cải tiến tham chiếu bộ nhớ dùng chung trong hệ xử lý song song đa CPU…………................................................................... 2.2.2.1. Xác định đại lượng P – Xác suất thanh ghi tham chiếu lối vào rỗi………….............................................................................................. 2.2.2.2. Xác định đại lượng Ep – Hiệu năng khi các hàng đợi của các mô đun nhớ đầy …………........................................................................ 35 35 36 37 44 2.2.2.3. Xác định El - Hiệu năng khi thanh ghi tham chiếu lối vào băng nhớ 47 rỗi…………………………………………………………………………… 2.3. Kết luận chương 2…………………………………………………. 51 Chương 3. XÂY DỰNG MÔ HÌNH ĐIỀU KHIỂN THÍCH NGHI CHO HỆ XỬ LÝ SONG SONG ĐA CPU CHUYÊN DỤNG………. 53 3.1. Xây dựng phần mềm khảo sát ................................................................ 53 3.1.1. Xây dựng mô đun chính phần mềm khảo sát ............................................ 53 3.1.2. 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 .............................. 3.1.3. 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 ............................... 3.1.4. 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.……………………………………………….................................. 3.2. Khảo sát, đánh giá hiệu năng mô hình điều khiển …………………. 61 3.3. Xây dựng mô hình điều khiển thích nghi…………………………... 65 3.4. Công nghệ FPGA 68 3.4.1. Tái kiến trúc phần cứng bằng chương trình 68 v 3.4.2. Thiết kế hệ thống trên FPGA 73 3.5. Sơ đồ nguyên lý điều khiển thích nghi theo tham số m 81 3.6. Kết luận chương 3…………………………………………............... 83 KẾT LUẬN CHUNG VÀ KIẾN NGHỊ ................................................................ 84 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ ............................................. 85 TÀI LIỆU THAM KHẢO..................................................................................... 86 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 EP Hiệu năng của một tham chiếu khi thanh ghi tham chiếu lối vào 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ớ Td Độ trễ nhỏ nhất để truyền một tham chiếu từ hàng chờ vào môđun 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 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 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 Bảng 1.3: Bảng 1.4: Bảng 3.1: Bảng 3.2: So sánh một số tính năng của hệ xử lý song song đa dụng và chuyên dụng Thống kê khả năng xuất hiện các loại lệnh Xác suất một yêu cầu đến khi hàng đợi chưa đầy theo m và ρ với qui tắc hàng đợi M/D/1/m Bảng điều khiển 21 24 63 83 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 Hình 2.1: Hình 2.2: Hình 2.3: Hình 3.1: Tham chiếu bộ nhớ dùng chung trong hệ xử lý song song. a. Sơ đồ hàng đợi tổng quát; b. Sơ đồ hàng đợi cho hệ xử lý song song đa CPU 35 38 Tổ chức băng băng nhớ đan xen cho KGNDC trong hệ 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 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 chung Tc 57 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 hợp không có băng nhớ logic (m=0, Tl=Td=0) Hình 3.6: Hình 3.7: Hình 3.8: Hình 3.9: Hình 3.10: Sự phụ thuộc của E theo chu kỳ vật lý của mô đun nhớ Tc khi m thay đổi Đồ thị của E theo số luồng tham chiếu n. a) Tc=10; b) Tc=5 Đồ thị của E theo chu kỳ vật lý mô đun nhớ Tc khi giữ cố định ρ= 0,5 Sơ đồ khối hệ thống điều khiển thích nghi cơ bản Sơ đồ khối điều khiển thích nghi luồng tham chiếu cho hệ xử lý song song đa CPU chuyên dụng b) Cấu trúc của PAL 62 64 64 65 67 68 Hình 3.11: a) Cấu trúc của PLA Hình 3.12: Mô tả mô hình của một FPGA 71 Hình 3.13: Cấu trúc logic Cell trong FPGA 72 Hình 3.14: Cấu trúc của một FPGA 73 Hình 3.15: Quá trình thiết kế trên FPGA 74 Hình 3.16: Mô hình điều khiển kích thước hàng đợi m 82 69 1 MỞ ĐẦU 1. Tính cấp thiết đề tài Lý thuyết về xử lý song song (parallel processing) bắt đầu vào những năm 1940 khi J.Von Neumann giới thiệu một số mô hình hạn chế của tính toán song song, chủ yếu là một mảng hai chiều các bộ xử lý trạng thái hữu hạn được tương kết theo dạng hình lưới. Ngày nay lý thuyết về xử lý song song trở thành lĩnh vực nghiên cứu quan trọng và ngày càng đem lại những dấu hiệu khả quan trong việc xây dựng mô hình lập trình mới có những tính năng vượt trội so với mô hình lập trình tuần tự truyền thống. Nhiều lĩnh vực mới như đồ họa máy tính, trí tuệ nhân tạo, phân tích số, tính toán song song trong công nghiệp dầu khí, các thiết bị không người lái, thiết bị nhận dạng bám sát đa mục tiêu di động..., đòi hỏi phải xử lý một khối lượng dữ liệu rất lớn với tốc độ rất cao. Hầu hết những bài toán này, những máy tính tuần tự là không đáp ứng được yêu cầu thực tế. Mặc dù tốc độ xử lý của các bộ xử lý tăng nhiều trong những năm qua, nhưng do giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. Ngày càng xuất hiện nhiều bài toán mà hệ thống đơn bộ xử lý không đáp ứng được yêu cầu xử lý về mặt thời gian. Sự ra đời và phát triển nhanh của công nghệ vi điện tử đã tạo ra bước đột phá mạnh mẽ trong lĩnh vực khoa học tính toán và xử lý thông tin. Với sự phát triển ứng dụng các công nghệ này đã làm cho ranh giới các ngành không còn rõ rệt nữa (như Công nghệ thông tin, Điện tử viễn thông và Tự động điều khiển). Các hệ thống từ quy mô nhỏ tới quy mô lớn và siêu lớn trong lĩnh vực quân sự, cũng như dân dụng đều chứng kiến sự hiện hữu của các hệ vi xử lý chức năng đóng vai trò trung tâm 2 điều khiển hệ thống thực hiện các nhiệm vụ đã ấn định. Những hệ thống này đáp ứng được các yêu cầu khắt khe nhất như đòi hỏi phải xử lý dữ liệu với tốc độ rất cao, khối lượng dữ liệu và số lượng phép tính rất lớn. Để đáp ứng các yêu cầu trên, giải pháp thiết kế hệ thống theo hướng xử lý song song là hướng nghiên cứu được ưu tiên ngày nay. Để tăng tốc độ cho các hệ xử lý, các nhà thiết kế chế tạo đã áp dụng các công nghệ tiên tiến, từng bước nâng cấp hoàn thiện cho các bộ vi xử lý. Điển hình là cấu trúc bộ vi xử lý với tập lệnh đầy đủ (CISC), bộ vi xử lý với tập lệnh rút gọn RISC..[10], [12]. Những nghiên cứu về kiến trúc hệ thống số đã khẳng định được ưu thế nổi bật của hệ thống xử lý song song. Tuy nhiên, xử lý song song là vấn đề phức tạp, liên quan tới nhiều cơ cấu như: phần cứng của hệ xử lý, phần mềm hệ thống (hệ điều hành), thuật toán tính toán, ngôn ngữ lập trình… Ý tưởng nghiên cứu kỹ thuật xử lý song song theo hướng chuyên dụng cho từng lớp bài toán để đạt được tiêu chí về tốc độ, về độ tin cậy được đặt ra là có ý nghĩa thực tế, đáp ứng nhu cầu phát triển ứng dụng. Nghiên cứu về hệ xử lý song song hiện nay tập chung hai hướng nghiên cứu chính như sau: Một là nghiên cứu các hệ xử lý đa năng như siêu máy tính (Suppercomputer) [47], [56], máy tính lớn (Mainframe), máy tính mini (Minicomputer), mặc dù có khả năng thực hiện một tập hợp các lớp bài toán phong phú, nhưng để đưa vào sử dụng cho các ứng dụng chuyên dụng là không phù hợp. Điều này cũng dễ hiểu bởi vì để thực hiện đa năng: cấu trúc phần cứng và chức năng phần mềm của máy tính cần phải được tổ chức đa chức năng rất phức tạp. Mô hình toán cũng rất phức tạp, vượt qua khỏi cơ cấu tính toán thông thường. Do vậy, khi áp dụng cho các ứng dụng chuyên dụng, tốc độ xử lý của chúng thường chậm hơn so với khả năng của bộ vi xử lý, thông số thời gian thực khó kiểm soát một cách chính xác... Các hệ xử lý đa năng mặc dù tốc độ cao, tốc độ của nó có thể sử dụng mô phỏng các vụ nổ hạt nhân...Hệ xử lý song song đa năng quy mô rất lớn kèm theo cơ cấu phần mềm vận hành cấu trúc này rất phức tạp. Vì vậy các hệ máy tính này có 3 giá thành rất đắt. Đây là vấn đề khó khăn khi giải quyết các bài toán đặc thù có yêu cầu tốc độ nhanh, giá thành rẻ phù hợp với điều kiện nền kinh tế Việt Nam. Hai là nghiên cứu các hệ xử lý song song đa CPU chuyên dụng đó là: Hệ xử lý song song chuyên dụng phục vụ một hay một lớp bài toán cụ thể, gần nhau về chức năng. Do đó, phương thức thao tác, cấu trúc tập hợp dữ liệu cần xử lý, cấu trúc dữ liệu kết quả đều xác định trước, nên dễ phân rã chức năng hơn; dễ lựa chọn cách tổ chức dữ liệu và phương pháp xử lý thích hợp với yêu cầu tốc độ. Với nhiệm vụ cụ thể và cấu trúc dữ liệu xác định, có thể xây dựng thuật toán xử lý tối ưu, cấu trúc phần cứng thích hợp, tận dụng tài nguyên hệ thống hợp lý. Do chức năng của hệ xử lý song song chuyên dụng là hữu hạn và tường minh, nên chương trình Monitor được xây dựng ở mức tối ưu nhất, dễ hiệu chỉnh và quan trọng hơn là đáp ứng nhanh yêu cầu của các tiến trình vận hành trong hệ thống. Xu hướng các nhà thiết kế ứng dụng công nghệ mới FPGA kết hợp với bộ xử lý lõi phát triển các hệ xử lý theo hướng các hệ thống này có khả năng thay đổi cấu hình (tái cấu hình) và các hệ thống có tính chuyên dụng [52], [54]. Đặc biệt, trong nước đã có một số cơ sở nghiên cứu về hệ xử lý song song trên cơ sở công nghệ RISC với kiến trúc Harvard. Với kỹ thuật tiên tiến hiện nay, việc sử dụng công nghệ đương đại FPGA cho phép thực hiện tái kiến trúc nhanh hệ thống nhằm tối ưu hóa chức năng. Chính vì vậy mà hệ có tốc độ xử lý cao, trong khi từng thành phần của hệ làm việc ở dưới mức tới hạn nên đảm bảo độ tin cậy cao. Qua phân tích ở trên đề tài luận án lựa chọn theo hướng nghiên cứu thứ hai là hệ xử lý song song đa CPU chuyên dụng. Trong hệ xử lý song song đa CPU chuyên dụng, không gian nhớ dùng chung (KGNDC) rất quan trọng: là nơi lưu trữ các cơ sở dữ liệu cần xử lý, chứa chương trình điều hành...Khi nhiều luồng tham chiếu truy cập vào bộ nhớ dùng chung cùng một thời điểm có thể dẫn đến xung đột, hệ thống lúc đó có thể bị treo hoặc tốc độ truy cập thấp, hiệu năng của bộ nhớ dùng chung giảm không đáp ứng được yêu cầu tốc độ của bài toán đặt ra. Phần quan trọng của KGNDC là các bộ điều khiển luồng tham chiếu. Trên cơ sở đó vấn đề cần giải quyết là tổng hợp cơ cấu điều khiển thích nghi luồng tham chiếu tới KGNDC nhằm giảm thiểu tối đa xác suất xung đột khi truy cập tài nguyên dùng chung, nâng cao tốc độ 4 tính toán có ý nghĩa rất quan trọng. Từ những phân tích trên, việc đặt ra bài toán nghiên cứu hệ xử lý song song đa CPU chuyên dụng đáp ứng tốc độ xử lý nhanh và có độ tin cậy cao, giá thành hợp lý là cần thiết và là cơ sở hình thành đề tài của luận á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 ”. 2. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu luận án là KGNDC trong hệ xử lý song song đa CPU chuyên dụng. - Phạm vi nghiên cứu của luận án là giới hạn trong việc xây dựng mô hình toán học tham chiếu tới KGNDC trong hệ xử lý song song đa CPU chuyên dụng, chỉ rõ các điều kiện ràng buộc giữa các thông số và các thông số có thể thay đổi điều khiển được để tổng hợp hệ điều khiển thích nghi luồng tham chiếu tới KGNDC nhằm nâng cao hiệu năng giảm thiểu xác suất xung đột khi truy cập tài nguyên dùng chung. 3. Phương pháp nghiên cứu của luận án - Dựa trên lý thuyết kinh điển là lý thuyết hàng đợi, lý thuyết xác suất cụ thể là quá trình Morkov dừng, phân bố Poát - xông để xây dựng và tính toán hiệu năng cho mô hình toán học tham chiếu tới KGNDC trong hệ xử lý song song đa CPU chuyên dụng. - Mô tả toán học mô hình bộ nhớ dùng chung trong hệ xử lý song song đa CPU chuyên dụng. - Nghiên cứu xây dựng hệ thống điều khiển thích nghi luồng tham chiếu sử dụng công nghệ đương đại FPGA. 4. Ý nghĩa khoa học và thực tiễn luận án 4.1. Về mặt khoa học Ý nghĩa khoa học là nghiên cứu triển khai ứng dụng các bộ điều khiển thích nghi luồng tham chiếu tới KGNDC cho hệ xử lý song song đa CPU chuyên dụng nhằm nâng cao hiệu năng, nâng cao tốc độ, giảm thiểu tối đa xác suất xung đột khi truy cập tài nguyên dùng chung. 5 4.2. Về thực tiễn Kết quả nghiên cứu sẽ làm tài liệu tham khảo cho sinh viên và học viên cao học cũng như các nhà nghiên cứu quan tâm nghiên cứu về hệ xử lý song song đa CPU chuyên dụng. Từ kết quả nghiên cứu của đề tài này làm cơ sở cho nhiều nghiên cứu tiếp theo nhằm đưa ứng dụng rỗng rãi các hệ xử lý song song đa CPU chuyên dụng vào hệ thống thực tế ở Việt Nam, nhất là các hệ thống có yêu cầu cao về tốc độ. 5. Cấu trúc luận án Luận án bao gồm phần mở đầu, ba chương thuyết minh, phần kết luận, các công trình công bố của NCS, tài liệu tham khảo. Chương 1: Trình bày, tập trung giới thiệu tổng quan về xử lý song song đa CPU, các đặc trưng kiến trúc của hệ thống xử lý song song đa CPU chuyên dụng. Phân tích các kết quả nghiên cứu trong và ngoài nước với các hướng nghiên cứu về hệ xử lý song song đa CPU chuyên dụng như mở rộng phạm vi ứng dụng, ứng dụng các phương pháp điều khiển hiện đại. Đề xuất phương pháp và các nội dung cần nghiên cứu là phương pháp điều khiển thích nghi luồng tham chiếu tới KGNDC dựa trên lý thuyết hàng đợi nhằm nâng cao hiệu năng giảm thiểu xác suất xung đột khi truy cập tài nguyên dùng chung. Chương 2: Trình bày cơ sở xây dựng mô hình toán học tham chiếu tới KGNDC cho hệ xử lý song song đa CPU chuyên dụng. Phân tích mô hình, các thông số ràng buộc, chỉ ra các thông số có thể điều khiển được. Trên cơ sở tham khảo các tài liệu [10], [15], [33], [39], [18] và sử dụng lý thuyết hàng đợi [48]. Chương 3: Dựa trên mô hình toán học được xây dựng ở chương 2, tiến hành xây dựng chương trình thuật toán khảo sát và tính toán. Thiết kế tổng hợp hệ thống điều khiển thích nghi luồng tham chiếu KGNDC bằng cách sử dụng công nghệ đương đại FPGA. Kết luận chung và kiến nghị 6 Chương 1 KIẾN TRÚC HỆ XỬ LÝ SONG SONG ĐA CPU 1.1. Tài nguyên hệ thống 1.1.1. Tài nguyên phần cứng - Các bộ xử lý trung tâm CPU đóng vai trò là đơn vị điều khiển, tính toán, xử lý, gia công thông tin dưới sự điều khiển của các chương trình có trong hệ thống. - Không gian nhớ bao gồm cả bộ nhớ thực và bộ nhớ ảo. Đây là môi trường lưu trữ các cơ sở dữ liệu cần xử lý, chứa kết quả trung gian và kết quả cuối cùng. Quan trọng nhất là nó chứa hệ điều hành hoặc chương trình Monitor để vận hành hệ thống cùng với các tài nguyên phần mềm chứa ở đây. Không gian nhớ của hệ xử lý song song gồm: bộ nhớ cục bộ và bộ nhớ dùng chung. Bộ nhớ cục bộ dành riêng cho một hệ vi xử lý trong hệ xử lý song song. Bộ nhớ dùng chung là nơi chứa các dữ liệu dùng chung cho các hệ đơn xử lý thành phần: như các thông báo của các tiến trình, các kết quả trung gian đầu ra của tiến trình này nhưng lại là số liệu đầu vào cho các tiến trình khác trong quá trình hoạt động của hệ thống. - Hệ thống bus thể hiện năng lực truyền tải thông tin bên trong và với bên ngoài hệ thống. 1.1.2. Tài nguyên phần mềm - Hệ điều hành hoặc ở quy mô nhỏ hơn là chương trình Monitor có nhiệm vụ điều phối các tiến trình vận hành trong môi trường hệ xử lý song song một cách hiệu quả nhất. Khi chạy ở chế độ bảo vệ (chế độ địa chỉ ảo), hệ điều hành phải phối hợp đồng bộ các cơ cấu từ lớp vật lý đến lớp ứng dụng sao cho việc truy nhập vào các tài nguyên hệ thống phải nhanh nhất và lại phải ít xung đột nhất. - Các dịch vụ hệ thống cung cấp các chương trình kiểm tra, thông báo hỏng hóc, các cơ cấu điều khiển mức hệ thống như vào/ra, điều khiển các giao diện nối tiếp, song song, các driver cho các phần cứng chức năng. - Các thư viện chức năng cung cấp các hàm các thủ tục chuẩn trong tính toán với các thao tác toán học phức tạp như khai triển chuỗi, xử lý dấu phẩy động ... 7 - Bảng véc tơ ngắt chứa các điểm vào tài nguyên phần mềm hệ thống, đặc biệt là các tài nguyên nằm ở lớp vật lý (tài nguyên lõi), nơi mà các ánh xạ của chúng thường là ánh xạ trực tiếp tới phần cứng của hệ xử lý song song. 1.2. Các định nghĩa về hệ xử lý song song - Xử lý song song là quá trình xử lý nhiều tiến trình được phát động đồng thời và cùng tham gia giải quyết một nhiệm vụ. - Hệ xử lý song song là một kiến trúc hệ thống bao gồm nhiều hệ xử lý có khả năng xử lý song song. - Hiệu năng của xử lý song song có nhiều cách định nghĩa phụ thuộc vào phương thức tiếp cận với kiến trúc của hệ xử lý song song. Do luận án tiếp cận với kiến trúc của hệ xử lý song song ở mức thấp (mức cấu trúc phần cứng) nên hiệu năng của hệ được hiểu như là tỷ số của khả năng thực thi thao tác giữa điều kiện thực tế và điều kiện lý tưởng (bao gồm: tốc độ tính toán của CPU, thông lượng của bộ nhớ cục bộ, xác suất xung đột các luồng tham chiếu ở bộ nhớ dùng chung ...). 1.3. Phân loại hệ xử lý song song đa CPU Phân loại tổng quát nhất đối với các hệ xử lý song song là hệ xử lý song song đa dụng và hệ xử lý song song chuyên dụng. Hệ xử lý song song đa dụng về bản chất là các hệ máy tính từ siêu máy tính, máy tính lớn, máy tính mini đến kiến trúc song song kết chùm (cluster) các máy tính PC. Những máy tính này đều có khả năng thực hiện một tập hợp các lớp bài toán phong phú. Chính vì vậy, chúng có tổ chức phần cứng và hệ điều hành phức tạp đáp ứng đầy đủ các chức năng thao tác và điều khiển cần thiết. Trong khi đó, hệ xử lý song song chuyên dụng cũng là hệ xử lý song song, đối tượng xử lý là một lớp bài toán có chức năng xác định; nên rõ ràng là kiến trúc của chúng sẽ ít phức tạp hơn nhiều so với hệ xử lý song song đa dụng. Michael J. Flynn, Handler... đã đưa ra cách phân loại các hệ xử lý song song. Theo các tác giả này, các hệ xử lý song song có thể phân loại dựa vào các đặc trưng về cấu trúc luồng lệnh/dữ liệu, về mức độ song song và mức độ xử lý theo cơ chế đường ống cũng như dựa vào chỉ tiêu về kiểu và số lượng CPU, cấu trúc bộ nhớ, sự kết nối giữa chúng ... 8 1.3.1 Sơ đồ phân loại của Flynn Michael J. Flynn đã đưa ra cách phân loại dựa vào cách thao tác của dòng lệnh và dòng dữ liệu trong hệ xử lý mà phân thành bốn lớp kiến trúc chính như bảng 1.1. Bảng 1.1: Phân loại kiến trúc của Flynn Dòng lệnh Dòng dữ liệu Tên gọi SISD 1 1 đơn dòng lệnh, đơn dòng dữ liệu SIMD 1 >1 đơn dòng lệnh, đa dòng dữ liệu MISD >1 1 đa dòng lệnh, đơn dòng dữ liệu MIMD >1 >1 đa dòng lệnh, đa dòng dữ liệu a. Kiến trúc SISD: được chỉ ra trong hình 1.1, đó là những hệ xử lý truyền thống chỉ có một CPU, ở mỗi thời điểm chỉ thực hiện một lệnh. Các lệnh có thể được thực hiện tuần tự, nhưng cũng có thể được xếp chồng theo cơ chế đường ống. IS (luồng lệnh) CU PU MM (Đơn vị điều IS (Đơn vị xử lý) (Mô đun nhớ) khiển) DS (luồng dữ liệu) Hình 1.1: Mô hình kiến trúc SISD b. Kiến trúc SIMD: được chỉ ra trong hình 1.2, đó là những hệ xử có một đơn vị điều khiển để điều khiển nhiều phần tử xử lý PE. CU điều khiển chung cho tất cả PE cùng thực hiện thao tác trên những tập dữ liệu của các luồng dữ liệu khác nhau. IS CU (Đơn vị điều khiển ) IS PE 1 DS1 MM1 PE 2 DS2 PE n DSn MM2 Các mô đun nhớ cục bộ MMn Hình 1.2: Mô hình kiến trúc SIMD