Tiến Sĩ 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ý son

LUẬN ÁN TIẾN SĨ KỸ THUẬT
NĂM 2013

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
CHUYÊN DỤNG 31


2.1. Cơ sở lý thuyết 31 .
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 35
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 35
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 36
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 .37
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 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ớ rỗi 47
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 song đa CPU trong quan hệ với chu kỳ bộ nhớ dùng chung Tc 55
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 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ị ρ=0,5. 59
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
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Ả .8 5
TÀI LIỆU THAM KHẢO .8 6

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 đ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ó 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ứcdữ 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 hầ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 độ 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.