Blog

Tóm tắt — Bài viết này nằm trong loạt bài viết về việc đề xuất một kiến trúc phần cứng có thể tái cấu hình động lõi thô CGRA (Coarse-grained Reconfigurable Architecture) ứng dụng trong lĩnh vực xử lý đa phương tiện và truyền thông có tên viết tắt là MUSRA (Multimedia Specific Reconfigurable Architecture). Để giải quyết vấn đề về yêu cầu băng thông dữ liệu lớn trong các mảng xử lý song song, kiến trúc MUSRA được đề xuất tập trung vào việc khai thác tính cục bộ của dữ liệu nhằm giảm băng thông dữ liệu và tăng hiệu quả sử dụng tài nguyên tính toán. Kiến trúc được đề xuất đã được mô hình hóa bằng ngôn ngữ C nhằm mục đích mô phỏng và phân tích các tham số khác nhau của kiến trúc hệ thống mục tiêu, cũng như hỗ trợ khả năng đồng kiểm chứng phần cứng – phần mềm khi ánh xạ một ứng dụng lên hệ thống. Một số ứng dụng đã được ánh xạ và chạy trên mô hình C của kiến trúc nhằm kiểm chứng khả năng ứng dụng linh hoạt của kiến trúc được đề xuất cho một dải các ứng dụng xử lý đa phương tiện và truyền thông.

Nghiên cứu của các tác giả trong [2] chỉ ra rằng các cấu trúc vòng lặp chỉ chiếm 10% tổng độ dài mã chương trình nhưng tiêu thụ tới khoảng 90% thời gian thực thi của một chương trình máy tính. Phần lớn các vòng lặp này đều có các đặc trưng như cơ chế song song mức dữ liệu cao, tính phức tạp tính toán cao,… vì vậy các vòng lặp này đòi hỏi phải được tăng tốc tính toán bằng phần cứng. Như đã trình bày ở trên, kiến trúc RCA được thiết kế để hỗ trợ hiệu quả việc thực hiện các vòng lặp lõi trong ứng dụng. Bằng việc ánh xạ tính toán trong thân của một vòng lặp lõi lên RCA, RCA chỉ cần thực hiện cấu hình một lần cho việc thực hiện nhiều lần cả vòng lặp, vì vậy nó có thể giảm một cách hiệu quả thời gian thực thi của vòng lặp. Kiến trúc của RCA được thiết kế nhằm tăng tốc tính toán của các vòng lặp lõi trong các thuật toán. Mô hình thực thi của nó là mô hình đa lệnh-đa dữ liệu được đường ống hóa (pipelined Multi-Instruction-Multi-Data model). Trong mô hình này mỗi RC có thể được cấu hình riêng biệt để thực thi một thao tác độc lập, mỗi hàng RC tương ứng với một tầng của đường ống. Nhiều lần lặp của một vòng lặp có thể được lập lịch để thực thi đồng thời trong đường ống.

 Để ánh xạ một vòng lặp lõi lên RCA, đầu tiên vòng lặp cần được phân tích và biến đổi (bằng các kỹ thuật như mở vòng lặp (loop unrolling), đường ống hóa (loop pipelining), phân khối (loop blocking), v.v) nhằm làm lộ ra các cơ chế song song và tính cục bộ dữ liệu nội tại của thuật toán sao cho chúng có thể được khai thác để tăng hiệu năng tính toán trên kiến trúc đích. Tiếp theo thân của vòng lặp sẽ được biểu diễn bằng đồ họa luồng dữ liệu DFG (Data-Flow Graph [5]) như được chỉ ra trong Hình 3. Các DFG này sau đó sẽ được ánh xạ lên RCA bằng việc tạo ra các thông tin cấu hình về việc gán một nốt của DFG tới RC nào của RCA, và sườn nào của DFG tới các kết nối trên mảng RCA. Cuối cùng, DFG được lập lịch để thực thi tự động trên RCA bằng việc tạo ra các tham số điều khiển tương ứng cho bộ điều khiển RCA. Ngay khi đã được cấu hình cho một vòng lặp nhất định, RCA sẽ hoạt động giống như một phần cứng chuyên dụng cho vòng lặp đó. Khi tất cả vòng lặp đã được hoàn thành, vòng lặp sẽ được loại bỏ khỏi RCA và một vòng lặp mới sẽ được ánh xạ lên RCA.

Trong mô hình kiến trúc của RCA, năm tham số được định nghĩa cho việc điều khiển sự thực thi của vòng lặp như sau:

• Số lần nhập dữ liệu cho một lần lặp, N_I, được định nghĩa là số chu kỳ để nhập toàn bộ dữ liệu cho một lần lặp từ INPUT_FIFO.
• Số lần xuất dữ liệu cho một lần lặp, N_O, được định nghĩa là số chu kỳ để viết toàn bộ kết quả của một lần lặp tới OUTPUT-FIFO.
• Số lần lặp, N_L, số lần lặp lại tính toán của một vòng lặp.
• Khoảng lặp, II, được định nghĩa như số chu kỳ được tính từ lần nhập dữ liệu đầu tiên của lần lặp thứ i tới lần nhập dữ liệu đầu tiên của lần lặp thứ (i+1). II chỉ ra khi nào lần lặp tiếp theo có thể bắt đầu thực thi trên RCA. Rõ ràng rằng II càng nhỏ thì lần lặp tiếp theo sẽ càng sớm được bắt đầu, do đó sẽ có càng nhiều các lần lặp được xếp chồng lên nhau để thực hiện đồng thời trên đường ống. Vì vậy đạt được một giá trị II nhỏ nhất là mục tiêu của việc tối ưu để cải thiện hiệu năng thực thi vòng lặp trên RCA.
• Thời điếm bắt đầu xuất dữ liệu tới OUTPUT_FIFO, N­­_W­, được định nghĩa bằng số chu kỳ xung nhịp tính từ lần nhập dữ liệu đầu tiên đến lần xuất dữ liệu đầu tiên trong cùng một lần lặp. Đây chính là khoảng thời gian tương ứng với trễ lan truyền tín hiệu (latency) trong đường ống.

Như vậy, một lần lặp của RCA được bắt đầu bằng pha LOAD-EXECUTION và sau đó là pha EXECUTION, cuối cùng được kết thúc bằng pha STORE-EXECUTION (Hình 3). Pha LOAD-EXECUTION và STORE-EXECUTION bao hàm rằng sự thực thi xảy ra song song với việc nạp và lưu dữ liệu một cách tương ứng, trong khi pha EXECUTION không có bất cứ thao tác đọc hoặc xuất dữ liệu nào diễn ra. Sự thực thi của một vòng lặp trên RCA được lập lịch sao cho các pha khác nhau của các lần lặp liên tiếp được xếp chồng lên nhau ở mức nhiều nhất có thể như chỉ ra trong Hình 4. Lập lịch cũng cần đảm bảo không có bất cứ xung đột nào xảy ra giữa các tài nguyên khi nhiều pha diễn ra đồng thời.

Từ các tham số được định nghĩa ở trên, nó là dễ dàng để suy ra số chu kỳ thực thi cho mỗi lần lặp, N_CPI, được xác định như sau:

Bằng phương thức thực thi theo kiểu đường ống, các lần lặp liên tiếp có thể xếp chồng lên nhau, do đó số chu kỳ được đòi hỏi để hoàn thành cả vòng lặp được xác định bởi:

Một vấn đề quan trọng trong mô hình tính toán song song như RCA là giải quyết băng thông dữ liệu. Băng thông dữ liệu của hệ thống phải đảm bảo dữ liệu luôn sẵn sàng cho cho tất cả các phần tử xử lý của hệ thống chạy đồng thời mà không có trạng thái treo (IDLE). Một cách để tăng tính sẵn sàng của dữ liệu là khai thác tính cục bộ dữ liệu (Data locality) hay khả năng sử dụng lại dữ liệu [4]. Dữ liệu được sử dụng lại giữa nhiều lần tính toán có thể được đệm trong bộ nhớ trong (cache) của RCA do đó giảm được thời gian đợi do phải truy xuất bộ nhớ bên ngoài. Hơn thế bằng việc giảm lượng truy xuất bộ nhớ bên ngoài, nó có tiềm năng để giảm một lượng lớn công suất tiêu thụ [7]. So với mô hình thực thi của RCA trong [8] và [9], mô hình thực thi của RCA được đề xuất để khai thác tối đa dữ liệu dùng lại giữa các lần lặp liên tiếp, vì vậy nó có thể cải thiện hiệu năng và giảm đi thông lượng dữ liệu lối vào. Trong mô hình này, RCA có thể bắt đầu tính toán ngay khi dữ liệu của lần nhập dữ liệu đầu tiên xuất hiện ở lối vào của RCA, vì vậy ba pha LOAD, EXECUTION, STORE được thực hiện gối lên nhau theo phương thức đường ống ở mức cao nhất. Ở khía cạnh khác, nó cũng cho phép dữ liệu của lần lặp tiếp theo được nạp đồng thời với dữ liệu của lần lặp hiện tại, vì vậy mô hình này có thể không chỉ tối đa hóa mức độ xếp chồng giữa các lần lặp liên tiếp mà còn cải thiện cả khả năng để khai thác dữ liệu có thể dùng lại giữa các lần lặp.

TÀI LIỆU THAM KHẢO

1. Christophe Bobda, “Introduction to Reconfigurable Computing – Architectures, Algorithms, and Applications”. Springer, 2007.
2. Shoa and S. Shirani, “Run-Time Reconfigurable Systems for Digital Signal Processing Applications: A Survey”, Journal of VLSI Signal Processing, Vol. 39, pp.213–235, 2005, Springer Science.
3. Theodoridis, D. Soudris and S. Vassiliadis: “A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools Basic Definitions, Critical Design Issues and Existing Coarse-grain Reconfigurable Systems”, Springer 2008, p89-149.
4. Kathryn S. McKinley, Steve Carr, Chau-Wen Tseng: “Improving Data Locality with Loop Transformations”, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 18, Issue 4, July 1996, Pages 424 – 453.
5. Gajski D., Dutt N., Wu A., Lin, S.: “High-Level Synthesis, Introduction to Chip and System Design”, Kluwer Academic Pub. (1992).
6. Shuvra S. Bhattacharyya, Ed F. Deprettere, Rainer Leupers, Jarmo Takala: “Handbook of signal processing systems”, p449-p485, 1st Edition, September 1, 2010, Springer; ISBN-10:
7. Sohoni, and R. Min, et al. “A study of memory system performance of multimedia applications”. SIGMETRICS Performance 2001, pages 206–215.
8. Zhu, L. Liu, S. Yin, et al.: “A Cycle-Accurate Simulator for a Reconfigurable Multi-Media System,” IEICE Transactions on Information and Systems, vol. 93, pp. 3202-3210, 2010.
9. Hung K. Nguyen, Peng Cao, Xuexiang Wang, Jun Yang, Longxing Shi, Min Zhu, Leibo Liu, Shaojun Wei: Hardware Software Co-design of H.264 Baseline  Encoder on Coarse-Grained Dynamically  Reconfigurable Computing System-on-Chip, IEICE TRANSACTIONS on Information and Systems (SCI index), Vol.E96-D,3,  pp.601-615, 2013.
10. Iain E. Richardson: “The H.264 advanced video compression standard”, second edition, 2010, John Wiley & Sons, Ltd.