Thuật toán Pipeline hóa cho hệ xử lý chuyên dụng

Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, P. T. Dũng, “Thuật toán pipeline hóa cho hệ xử lý chuyên dụng.” 80 THUẬT TOÁN PIPELINE HÓA CHO HỆ XỬ LÝ CHUYÊN DỤNG Phạm Minh Tới*, Đỗ Xuân Tiến, Phạm Trung Dũng Tóm tắt: Bài báo trình bầy một thuật toán pipeline hóa cho hệ xử lý chuyên dụng. Thuật toán đề xuất sử dụng phương pháp truyền thống về lập lịch cho graph xử lý luồng dữ liệu là phương pháp lập lịch sơ bộ để lập lịch cho từng thao tác mà chưa xét tới các giới hạn tài nguyên cho từng trạng thái. Trong giai đoạn tiếp theo, bài báo sử dụng phương pháp phát hiện sự vi phạm giới hạn tài nguyên trong từng trạng thái và hiệu chỉnh chúng bằng cách dựa vào độ linh hoạt của tập các thao tác. Tiêu chuẩn để tái lập lịch cho các thao tác là độ linh hoạt của thao tác càng thấp thì càng dễ bố trí vào các trạng thái khác với số bước giữ chậm ít nhất. Kết quả kiểm nghiệm đều trùng với các kết quả của phương pháp đồng tổng hợp nhưng nhanh hơn và tiết kiệm tài nguyên hơn. Từ khóa: Hệ xử lý song song, Graph xử lý luồng dữ liệu, Sự vi phạm giới hạn tài nguyên, Hệ xử lý chuyên dụng. 1. ĐẶT VẤN ĐỀ Trong các hệ xử lý tín hiệu số hay hệ xử lý song song đặc biệt là các khối của lõi CPU, khi xử lý luồng dữ liệu vào thường phải sử dụng các thuật toán với vòng lặp có bước lặp rất lớn như hệ thống trong các công trình [3,7]. Thời gian thực hiện thuật toán lặp thường chiếm phần lớn thời gian làm việc của cả hệ thống nên tối ưu hóa thuật toán lặp là yêu cầu cấp thiết để tăng tốc độ làm việc của hệ thống. Pipeline hóa các kiến trúc thực hiện vòng lặp là một giải pháp hiệu quả [7], song để áp dụng được phương pháp này đòi hỏi phải có các thuật toán tổng hợp hợp lý mà thuật toán tổng hợp tổng quát nhất phải kể đến là thuật toán đồng tổng hợp hệ thống (hardware/software co-synthesis system). Hình 1. Thuật toán xử lý tham số 3 luồng tín hiệu của thiết bị kiểm tra tham số tên lửa URAN-E [1]. Trên hình 1 là sơ đồ chức năng của Hệ thống tự động kiểm tra và chẩn đoán tham số tên lửa theo nhóm (tên viết tắt tiếng Nga là АКПА). Phân tích hệ thống cho biết có 3 luồng thông tin từ khối thu/phát của АКПА là thông tin về dữ liệu, thông tin điều khiển và Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 81 thông tin trạng thái của hệ thống. Để thiết kế khối chức năng nhúng, giao diện vật lý được xác định là giao diện nối tiếp IRPS, còn giao diện mềm là cấu trúc thông tin về trạng thái Status, về điều khiển Control và về dữ liệu Data. Thiết kế module xử lý tin song song trên kiến trúc pipeline [4, 8] với 3 tuyến song song với đầu vào là 3 bộ lọc để tách 3 tuyến từ luồng tín hiệu nối tiếp từ giao diện IRPS của АКПА. Sử dụng thuật toán đồng tổng hợp hệ thống, công trình [2] và đặc biệt là [1] đã khá thành công trong thiết kế các khối xử lý song song bằng kiến trúc pipeline. Bài báo lấy lại kiến trúc của khối xử lý tin trong [1, 2] để so sánh với phương pháp mới mà tác giả của bài báo này đề xuất. Trong [1, 2], “module xử lý tin song song trên kiến trúc pipeline” gồm 5 bộ cộng 2 đầu vào (ô đánh mầu) và 12 bộ cộng tích lũy (được đánh số từ Add_1 đến Add_17) để xử lý luồng dữ liệu đầu vào theo qui luật được biểu diễn bởi graph trên hình 2. Hình 2. Graph chức năng module xử lý luồng dữ liệu trong [1]. Điểm lưu ý trong phần tổng hợp “module xử lý tin “ ở hệ xử lý chuyên dụng này là giới hạn tài nguyên (bộ Adder) cho một trạng thái là ≤ 6 và phép xử lý của graph chức năng trên đòi hỏi ít nhất là 6 bước. Khi pipeline hóa bằng phương pháp đồng tổng hợp [3], với thời gian làm việc là 3 chu kỳ clock, bằng thuật toán đồng tổng hợp hệ thống, công trình [1] đã tìm được kiến trúc pipeline tối ưu cho chức năng này và được thể hiện trên hình 3. Hình 3. Graph module xử lý luồng dữ liệu trong [1] được pipeline hóa. Add_1 Add_9 Add_7 Add_3 Add_12 Add_11 Add_13 Add_14 Add_17 Add_15 Add_16 Add_10 Add_8 Add_4 Add_6 Add_5 Add_2 0 1 2 3 4 5 6 Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, P. T. Dũng, “Thuật toán pipeline hóa cho hệ xử lý chuyên dụng.” 82 Kết quả của tác giả công trình [1,2] cho thấy “module xử lý tin” khi được pipeline hóa bằng thuật toán đồng tổng hợp có những hạn chế sau: - Mặc dù cấu trúc đơn giản do không phải hồi tiếp nhưng graph sử dụng tới 9 bước để thực hiện chức năng nên gây tốn tài nguyên phần cứng. - Thuật toán đồng tổng hợp mang tính tổng quát cao nhưng khi tổng hợp một hệ thống chuyên dụng thì tỏ ra không hiệu quả do tốn nhiều khâu hiệu chỉnh trung gian mới tìm được cấu trúc tối ưu. Chính vì những hạn chế trên nên bài báo này sẽ tiếp cận nhiệm vụ pipeline hóa theo một hướng khác. 2. NỘI DUNG CẦN GIẢI QUYẾT 2.1. Đề xuất thuật toán pipeline hóa cho hệ xử lý chuyên dụng Thuật toán đề xuất dựa trên nền tảng thuật toán lập lịch [5,6,8] nhưng có bổ sung tiêu chí phát hiện vi phạm giới hạn tài nguyên và tiêu chí ưu tiên theo mức độ của độ linh hoạt các thao tác. Thuật toán này có 2 giai đoạn mà ở giai đoạn đầu-giai đoạn lập lịch sơ bộ, các giới hạn tài nguyên của trạng thái được bỏ qua mà chỉ quan tâm tới chức năng và thời gian khởi đầu lại thao tác II (initiation interval). Kết quả của giai đoạn này sẽ là một lịch trình cho các thao tác hệ thống với thời gian lặp IT (iteration time) ngắn nhất. Nếu phát hiện bất kỳ sự vi phạm nào đối với giới hạn tài nguyên trong một trạng thái nào đó, thì ở giai đoạn thứ hai, một số thao tác sẽ phải chuyển từ trạng thái vi phạm sang trạng thái khác. Việc chỉ định thao tác nào cần di chuyển phải dựa trên một tiêu chí ưu tiên mới. Thuật toán đề xuất sẽ xây dựng bộ tiêu chí cho phép phân loại theo mức độ ưu tiên độ linh hoạt của các thao tác để nhanh chóng xác định thao tác cần chuyển trong giai đoạn 2 là giai đoạn tinh chỉnh lịch trình của graph. Hình 4. Thuật toán đề xuất lập lịch cho thao tác hệ thống. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 83 Thuật toán đề xuất được thể hiện trên hình 4. Khởi đầu của thuật toán, việc lập lịch luồng dữ liệu SDFG (scheduling the dataflow graph) được xác định bởi chương trình con “Lập lịch sơ bộ” hay còn gọi là ASAPP (As Soon As Possible Pipelined Scheduling). Đây là chương trình con truyền thống với tham số graph DFG (dataflow graph) và tham số thời gian khởi đầu lại II [4, 8]. Nếu tìm được SDFG thì tham số IT của SDFG được gán vào biến IT. Vòng tìm kiếm bắt đầu bằng việc kích hoạt chương trình con ALAPP (As Late As Possible Pipelined Scheduling ) với ba tham số là DFG, II và IT. Lưu ý rằng ALAPP rất giống với thuật toán ASAPP ngoại trừ việc tìm kiếm bắt đầu từ bước cuối chứ không phải bắt đầu từ bước đầu như đối với ASAPP. 2.2. Xây dựng tiêu chí ưu tiên theo độ linh hoạt Giai đoạn hai là giai đoạn phát hiện vi phạm giới hạn tài nguyên được thực hiện bởi chương trình con ViPhamTaiNguyen (hình 5). Khi phát hiện có hiện tượng vi phạm tài nguyên thì số hiệu của trạng thái bị vi phạm tài nguyên được đưa vào biến S (state) của chương trình con. Bước tiếp theo là kiểm tra xem tập hợp thao tác ứng viên nào có thể di chuyển sang các trạng thái khác. Nếu có thì gán vào biến Co (candidate operation) của chương trình con. Hàm SL(S, Op) trả về số lượng các thao tác Op, được lập lịch vào trạng thái S cùng kiểu với thao tác Op. Sau đó, chương trình con tiến hành hai bước liên tiếp là sắp xếp các thao tác ứng viên và tái lập lịch cho thao tác ứng viên đầu tiên trong tập hợp đó. Khi trở về chương trình chính, ViPhamTaiNguyen sẽ trả về hoặc là một lịch trình tối ưu đã tìm được SDFG hoặc là kết quả rỗng “NULL” nếu không tìm được lịch trình theo yêu cầu. Khi đó, chương trình chính sẽ xử lý theo qui luật, nếu SDFG không rỗng, tức là tìm được lịch trình khả thi cho graph thì lịch trình này được coi là kết quả cuối cùng, còn trong trường hợp ngược lại thì thời gian lặp IT buộc phải giữ chậm thêm 1 bước để tiếp tục tìm kiếm lịch trình SDFG khả thi mới. Để tránh cho chương trình chính bị quẩn cần bổ sung thêm chương trình con “Hết thời gian” để khống chế thời gian tìm kiếm SDFG. Chú ý là tham số mobility thể hiện khả năng di động của thao tác từ trạng thái này sang trạng thái khác. Hình 5. Thuật toán xác định sự vi phạm tài nguyên. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, P. T. Dũng, “Thuật toán pipeline hóa cho hệ xử lý chuyên dụng.” 84 Trong thuật toán xác định vi phạm tài nguyên có một tiến trình rất quan trọng là tiến trình sắp xếp các thao tác trong Co. Nếu số lượng các thao tác ứng viên cho việc di chuyển sang trạng thái khác có từ hai trở lên thì cần sắp xếp chúng theo tiêu chí ưu tiên theo độ linh hoạt. Nhưng độ linh hoạt của thao tác được xác định như thế nào thì đó chính là nhiệm vụ mà thuật toán đề xuất phải thực hiện. Dựa trên lý thuyết xác suất, thuật toán đề xuất xây dựng mô hình xác định độ linh hoạt F (flexibility) của một thao tác Op theo quan hệ (1).  , 1 1 * rj i j j n m i j P Op w CF H     (1) Ở đây, tích P(Opi,j) * Hwj là chi phí trung bình của phần cứng cần thiết cho thao tác Op kiểu j (j=1÷m) và được lập lịch đưa vào trạng thái i (i=1÷n). Giá trị này thu được bằng cách giữ chậm Op càng ít càng tốt. Trong tích này, thành phần P(Opi,j) là xác suất lập lịch đưa thao tác Op kiểu j vào trạng thái i, còn thành phần Hwj là chi phí phần cứng của Op. Thành phần rCj (resource constraints) biểu thị giới hạn tài nguyên kiểu j. Vấn đề còn lại là xây dựng thuật toán ASAPP để tìm lịch trình sơ bộ. Hình 6 biểu diễn thuật toán lập lịch pipeline hóa ASAPP, trong đó, tập (DFG, II) xác định sự tồn tại của một lịch trình hợp thức và nếu đúng sẽ đặt toàn bộ các thao tác vào bước đầu tiên. Tiếp đó là vòng lặp xử lý từng thao tác bằng hàm “đẩy xuống” với 2 tham số SDFG và Opi như thể hiện trên hình 7. Hình 6. Thuật toán lập lịch sơ bộ. Trong thuật toán “đẩy xuống” sẽ tìm kiếm các thao tác tiếp theo Opnext dựa trên qui luật bước λ của graph (Opnext là thao tác mà đầu vào của nó chính là kết quả kết xuất từ đầu ra của Op): Đúng, đặt tất cả các thao tác Op lên bước đầu tiên Bộ đếm i=1 SDFG = đẩy xuống (SDFG, Opi) Trả kết quả các tham số tìm được của SDFG cho chương trình chính nếu (DFG, II) là hợp thức? Trả kết quả NULL cho SDFG END i=i+1 i=n? Điểm vào của chương trình con lập lịch sơ bộ Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 85 nextOp Op   (2) Nếu là bước kế tiếp của luồng dữ liệu thì λ =0 và nếu là bước hồi tiếp của luồng dữ liệu thì λ =1. Để bố trí Opnext vào bước kế tiếp, điều kiện sau phải bảo đảm: S opnext < Sop + Top - λ ×II (3) nghĩa là thời điểm của bước kế tiếp phải nhỏ hơn thời gian tiêu tốn để thực hiện thao tác hiện hành Top tính từ thời điểm của Op sau khi trừ đi tích giữa λ và thời gian tái khởi đầu của thao tác II. Nếu thỏa mãn thì bước kế tiếp Opnext sẽ được gán bằng thời gian của vế phải biểu thức (3). Cứ như thế cho tới thao tác Op cuối cùng được xử lý. Sau đó sử dụng phương pháp hồi qui để sử dụng lại hàm “đẩy xuống” cho Opnext để xử lý toàn bộ các thao tác Opnext. Khi chương trình con lập lịch sơ bộ kết thúc cũng là lúc kết thúc giai đoạn một và nó trả kết quả là một lịch trình SDFG cho chương trình chính để chương trình chính chuyển sang bước hai với điều kiện bổ sung mà nhóm tác giả đề xuất phương pháp xác định sự vi phạm giới hạn tài nguyên ở mỗi trạng thái hoạt động của hệ thống. 3. KẾT QUẢ THỰC THI VÀ THẢO LUẬN 3.1. Kiểm nghiệm thuật toán đề xuất Để kiểm nghiệm, nhóm tác giả áp dụng thuật toán đề xuất để lập lịch cho khối “module xử lý tin” trên kiến trúc pipeline với 3 tuyến song song với đầu vào là 3 bộ lọc để tách 3 tuyến từ luồng tín hiệu nối tiếp từ giao diện của hệ thống kiểm tra tham số tên lửa АКПА i=i+1 SDFG lấy tham số từ hàm “đẩy xuống” i=(B) i=i-1 B rỗng ? Biến đệm B=0; bộ đếm i=1 Thao tác Op với bước λ được chuyển thành Opnext Nếu nhỏ hơn thì S Opnext = Sop + Top - λ x II So sánh Opnext < Sop + Top - λ x II? Trả về lịnh trình tìm được SDFG END B = { Opnext } OR B Điểm vào của chương trình con “đẩy xuống” i=n? i=i+1 Hình 7. Thuật toán “đẩy xuống”. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, P. T. Dũng, “Thuật toán pipeline hóa cho hệ xử lý chuyên dụng.” 86 mà sơ đồ chức năng được thể hiện trên hình 1. Kết quả này sẽ được so sánh với lịch trình pipeline hình 2 của công trình [1, 2]. Trong hệ thống này, tuyến Status được đưa vào đầu vào của thao tác Add_1, tương tự tuyến Control được đưa vào đầu vào của thao tác Add_2 và tuyến Data được đưa vào đầu vào của thao tác Add_3. Áp dụng thuật toán đề xuất cho nhiệm vụ pipeline hóa sơ đồ chức năng trên, kết quả đã tìm được một kiến trúc pipeline tối ưu cho hệ xử lý chuyên dụng này và được thể hiện trên hình 8. 3.2. Thảo luận kết quả đạt được Hình 8 cho thấy kết quả lập lịch cho graph luồng dữ liệu hình 2 bằng thuật toán ASAPP với tham số II = 3. Khi giới hạn tài nguyên cho một trạng thái là 6 thì thuật toán phát hiện trạng thái thứ ba (state 2) của hình 8 có tới 7 bộ cộng, 3 trong CS5 (Add_15, Add_16, Add_17) và 4 trong CS2 (Add_4, Add_2, Add_11, Add_12). Điều này đã vi phạm giới hạn tài nguyên cho nên ít nhất một thao tác phải được tái lập lịch vào trạng thái khác. Vấn đề là chuyển thao tác nào đi là hợp lý nhất. Câu trả lời sẽ được giải quyết nhanh chóng và định lượng nhờ giai đoạn hai của thuật toán khi tính độ linh hoạt F của của các thao tác rồi chọn ra thao tác có độ linh hoạt nhỏ nhất (tương ứng với việc hiệu chỉnh cấu trúc graph ít nhất) để tái lập lịch vào trạng thái khác. Trong các thao tác đang nằm ở trạng thái thứ ba chỉ có Add_2, Add_4 và Add_11 là ứng viên cho bước tái lập lịch do có II=3. Theo tính toán F(Add_2) 3.7; F(Add_4) 3; F(Add_11) 3... Trong đó, độ linh hoạt ít nhất thuộc về Add_4 và Add_11 nên có thể tùy chọn Add_4 hoặc Add_11. Ở đây, Add_4 được chọn cho việc tái lập lịch. Do lịch trình hiện hành của Add_4 được xác định bởi thuật toán ASAPP, cách duy nhất có thể tái lập lịch lại Add_4 là giữ chậm nó một bước. Bằng cách đó, ta nhận được ngay một lịch trình tối ưu thể hiện trên hình 9. Hình 8. Sử dụng thuật toán lập lịch sơ bộ ASAPP. Hình 9. Sử dụng thuật toán đề xuất. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 87 Lịch trình này hoàn toàn trùng với phần lõi của hình 3 nhưng sử dụng ít phần cứng hơn: 17 adder và 3 trạng thái (hình 9) so với 34 adder và 9 trạng thái (hình 3) nên độ tin cậy cao hơn trong khi vẫn duy trì được tốc độ cao như phương pháp đồng tổng hợp. Rõ ràng đây là một phương án bổ sung tốt cho tập hợp các phương pháp tổng hợp các hệ xử lý chuyên dụng hiệu năng cao. 4. KẾT LUẬN Bài báo đề xuất một thuật toán pipeline hóa cho hệ xử lý chức năng bao gồm hai giai đoạn là (i) giai đoạn pipeline hóa bằng phương pháp lập lịch sơ bộ và (ii) giai đoạn xử lý các vi phạm giới hạn tài nguyên. Phương pháp phương pháp lập lịch sơ bộ cung cấp một kiến trúc pipeline sơ bộ, trong đó chức năng của graph xử lý luồng dữ liệu được lập lịch tới từng thao tác. Mỗi thao tác đều có vị trí xác định được biểu diễn bằng số hiệu bước và số hiệu trạng thái trong lịch trình cũng như quan hệ ràng buộc về tính trước sau của những thao tác này. Để phát hiện các vi phạm giới hạn tài nguyên, trong thuật toán đề xuất sử dụng chức năng ưu tiên là độ linh hoạt của thao tác với qui luật là độ linh hoạt càng thấp càng dễ cho việc tái lập lịch vào trạng thái khác mà thời gian giữ chậm lại thấp nhất (thường là chỉ 1 bước giữ chậm). Kết quả kiểm nghiệm cho thấy về chức năng thuật toán đề xuất cũng trùng với kết quả của công trình [1, 2] nhưng lại tiết kiệm tài nguyên hơn. Hơn thế nữa, tốc độ tính toán của thuật toán nhanh hơn so với phương pháp đồng tổng hợp đối với các hệ chuyên dụng, nơi mà các hoạt động theo vòng lặp chiếm đa số thời gian của hệ thống như các bộ lọc số 2n điểm, biến đổi cosin nhanh, bộ tạo và giải mã AES, mã Hadamard, đặc biệt là khối ALU của các bộ vi xử lý [7]. Lời cảm ơn: Nhóm tác giả cảm ơn sự giúp đỡ về phương tiện thí nghiệm của phòng thí nghiệm “Lập trình hệ thống” và phòng thí nghiệm “Kỹ thuật Vi xử lý” của HVKTQS. TÀI LIỆU THAM KHẢO [1]. Trịnh Quang Kiên, Đào Văn Lân. Đỗ Xuân Tiến. Đề tài NCKH cấp Bộ Quốc phòng: “Nghiên cứu cải tiến hệ thống kiểm tra tên lửa Х35Э (3M-24E) trong tổ hợp tên lửa đối hạm URAN-E”. Giải nhì Giải thưởng Sáng tạo KHCN Việt Nam VIFOTEC 2015. [2]. Hoàng Thị Phương. “Thiết kế khối xử lý tham số tên lửa X35E cho hệ thống tự động kiểm tra và chẩn đoán АКПА”. Tạp chí Khoa học và Kỹ thuật.-Số 156 (8-2013) - Học viện KTQS. [3]. A. Deb, J. M. Codina, and A. Gonzales. Softhv: “A hw/sw co-designed processor with horizontal and vertical fusion”. In International Conference on Computing Frontiers 2011. [4]. K. Coons, S. Kushwaha, K. S. McKinley, and D. Burger. “A Spatial Path Scheduling Algorithm for EDGE Architectures”. In ASPLOS 2006. [5]. Ryan Kastner, “Operation Scheduling: Algorithms and Applications”. Publisher Springer Netherlands. 2008.pp 231-255. [6]. Robert Klein. “Scheduling of resource constrainted projects”. Springer-Science + Business Media, LLC. 2012. Pp 73-92. [7]. S. Borkar and A. A. Chien. “The future of microprocessors”. Commun. ACM, 54(5):pp 67–77, 2011. [8]. Tony Nowatzki, Michael Sartin-Tarm. “A general constraint-centric scheduling framework for spatial architectures”. Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. Volume 48 Issue 6, June 2013. Pages 495-506. Kỹ thuật điều khiển & Điện tử P. M. Tới, Đ. X. Tiến, P. T. Dũng, “Thuật toán pipeline hóa cho hệ xử lý chuyên dụng.” 88 ABSTRACT A PIPELINING ALGORITHM FOR SPECIAL PROCESSING SYSTEMS In this article, a pipelining algorithm for special processing systems is presented. The proposed algorithm uses traditional methods of processing data flow graphs as preliminary schedule method to schedule each operation without state resource constraints. In the next phase, the method for detecting violations of resource constraints in each state and adjusting them by looking for the flexibility of an operation set will be used in the paper. A criteria for rescheduling operations is: the lower the operation flexibility, the easier to place them in other states with the least delay steps. Our experiment results are identical with the results of the co-synthesis method but they are faster and more resource-saving. Keywords: Special processing systems, Dataflow graph, Violation of the resource constraint, Pipelining algorithm. Nhận bài ngày 23 tháng 5 năm 2017 Hoàn thiện ngày 20 tháng 12 năm 2017 Chấp nhận đăng ngày 26 tháng 02 năm 2018 Địa chỉ: 1 Học viện Kỹ thuật quân sự, 236 Hoàng Quốc Việt, Q. Cầu giấy, TP. Hà Nội. * Email: phamminhtoi@gmail.com.