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