Đồng tổng hợp kiến trúc lưới thao tác cho lõi CPU Risc

Chu Đức Toàn và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 78(02): 23 - 28<br /> <br /> ĐỒNG TỔNG HỢP KIẾN TRÖC LƢỚI THAO TÁC CHO LÕI CPU RISC<br /> Chu Đức Toàn1*, Đỗ Xuân Tiến2, Hoàng Thị Phƣơng3<br /> 1<br /> <br /> Đại học Điện lực Hà Nội, 2Học viện Kỹ thuật Quân sự<br /> 3<br /> Đại học Sư phạm Kỹ thuật Nam Định<br /> <br /> TÓM TẮT<br /> Bài báo trình bày phƣơng pháp đồng tổng hợp kiến trúc khối tính toán và xử lý trên lƣới thao tác<br /> của lõi CPU RISC cho các hệ xử lý chức năng bằng cách tổ hợp hóa cấu trúc ô lƣới thao tác, sử<br /> dụng lƣới phụ và tái cấu hình lƣới bằng phần mềm không những giúp tiết kiệm tài nguyên phần<br /> cứng mà vẫn bảo đảm chức năng xử lý cơ sử dữ liệu có kích thƣớc khác nhau.<br /> Từ khóa: Đồng tổng hợp, lõi CPU RISC<br /> <br /> KIẾN TRÚC LƢỚI THAO TÁC CỦA CPU<br /> RISC<br /> <br /> kích thƣớc mn, thanh chứa Acc và 2 luồng dữ<br /> liệu vào X, Y.<br /> <br /> Tình huống hay gặp trong lõi CPU RISC là<br /> khi phát động hai hoặc ba lệnh song song, khi<br /> đó khối thực hiện lệnh EU sẽ kiểm tra dữ liệu<br /> xem có thể chia xẻ hay phụ thuộc [3,4]. Khối<br /> điều khiển sẽ thực hiện phân luồng và khẳng<br /> định sau bao nhiêu nhịp clock sẽ thực hiện<br /> bao nhiêu tiến trình song song thật sự. Lƣới<br /> thao tác lõi CPU RISC có dạng nhƣ hình 1a<br /> và 1b. Hình 1a mô tả các thành phần của lõi,<br /> bao gồm khối chứa hệ số H, khối lƣới thao tác<br /> <br /> Các ô lƣới của thao tác chính là các khối tính<br /> toán logic/số học. Thí dụ cộng 2 số dấu phẩy<br /> động bằng hệ pipeline tuyến tính [2] với 2 số<br /> dấu phẩy động: A = a x 2p và B = b x 2q ,cần<br /> tính C = A+B = c x 2r =d x zs với r =<br /> max(p,q); 0,5  d < 1. Thuật toán cơ bản để<br /> thực hiện phép cộng này:<br /> (i) So sánh p, g theo max(p, g) = t =|p  g|.<br /> (ii) Dịch phải số có số mũ nhỏ đi t bƣớc.<br /> (iii) Cộng phần định trị của hai số.<br /> X1<br /> <br /> Y<br /> X<br /> <br /> Y1<br /> <br /> H11<br /> Lƣới<br /> mn<br /> <br /> *<br /> <br /> Ym<br /> <br /> Hm1<br /> <br /> *<br /> <br /> H<br /> <br /> +<br /> Acc<br /> <br /> +<br /> <br /> Xn<br /> BUS<br /> <br /> H1n<br /> <br /> Hmn<br /> <br /> *<br /> <br /> *<br /> <br /> *<br /> <br /> +<br /> <br /> +<br /> <br /> Z1<br /> a)<br /> <br /> Zm<br /> b)<br /> <br /> Hình 1. Cấu trúc khối thao tác lƣới của lõi CPU RISC a, b.<br /> *<br /> <br /> Tel: 0982917093; Email: toancd@epu.edu.vn<br /> <br /> 23<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Chu Đức Toàn và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> A = a x 2p<br /> <br /> 78(02): 23 - 28<br /> B = b x 2q<br /> L0<br /> <br /> trõ<br /> |p-q|<br /> <br /> chän ®Þnh trÞ<br /> TG dÞch ph¶i<br /> L1<br /> t ®Þnh trÞ<br /> L2<br /> Bé ®Õm<br /> <br /> + sè mò<br /> <br /> TG dÞch<br /> L3<br /> L4<br /> <br /> S<br /> <br /> d<br /> <br /> s<br /> <br /> C = d . 2 = A+B<br /> <br /> Hình 2. Tính cộng 2 số dấu phẩy động trên hệ pipeline tuyến tính<br /> <br /> Nhận xét: Cấu trúc pipeline hình 2 có 4 tầng<br /> (số tầng sẽ khác nhau cho các cấu trúc tính<br /> khác nhau), tức là sau 4 chu kỳ clock khối<br /> này mới hoạt động thực sự song song. Nếu<br /> chỉ một lần tính thì không có vấn đề về điều<br /> khiển, nhƣng nếu phải tính cho một chuỗi dữ<br /> liệu thì vấn đề điều khiển sẽ phức tạp do phải<br /> đồng bộ các thành phần tham gia vào quá<br /> trình xử lý nhƣ bộ điều khiển luồng, bộ đếm<br /> độ giữ chậm của các khâu, bộ điều khiển quay<br /> vòng...Nhiều khi độ phức tạp quá mức của cơ<br /> cấu điều khiển có thể dẫn tới những nguy<br /> hiểm tiềm tàng: mất đồng bộ, trễ do phải chờ<br /> tập kết đủ yếu tố.<br /> <br /> Trong các hệ xử lý chức năng, khi nhiệm vụ<br /> là cụ thể và hạn chế trong một lớp bài toán<br /> nào đấy thì việc loại trừ ảnh hƣởng trên có<br /> nhiều giải pháp. Một trong những giải pháp<br /> đó là chúng ta có thể tổ chức phần cứng của<br /> lƣới thao tác bằng hệ tổ hợp thuần túy. Căn cứ<br /> vào [1,5] các cấu trúc các chức năng cơ bản<br /> của hệ tổ hợp là rõ ràng nhƣ bộ cộng, trừ nhị<br /> phân, BCD có dấu. Còn các cơ cấu nhân chia<br /> ta sẽ sử dụng phép dịch phải (chia 2), dịch trái<br /> (nhân 2), phần dƣ và phần carry sẽ sử dụng<br /> một cấu trúc riêng. Một cấu trúc điển hình của<br /> phép nhân/chia bằng hệ tổ hợp đƣợc thể hiện<br /> trên hình 3.<br /> <br /> BUS<br /> Dn<br /> <br /> Im<br /> <br /> D1<br /> <br /> I1<br /> <br /> Im<br /> <br /> MUX<br /> <br /> MUX<br /> <br /> Im<br /> <br /> O2<br /> <br /> m<br /> <br /> I1<br /> <br /> I1<br /> <br /> O1<br /> <br /> Im<br /> <br /> O2<br /> <br /> m<br /> <br /> I1<br /> <br /> O1<br /> MUX<br /> <br /> MUX<br /> <br /> O2m<br /> <br /> Số nhân/chia<br /> <br /> O2m<br /> <br /> O1<br /> <br /> dn<br /> <br /> O1<br /> <br /> d0<br /> BUS<br /> <br /> Hình 3. Cấu trúc bộ nhân/chia của ô lƣới thao tác bằng cấu trúc NOT, AND, OR và MUX<br /> <br /> 24<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Chu Đức Toàn và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Thừa số thứ nhất Dn-D1 đƣa vào đầu data của<br /> MUX, thừa số thứ hai các bit điều khiển ghép<br /> kênh. Khi đó ta có bảng 1.<br /> Với cách dich trên, phép nhân chỉ nhân thừa<br /> số thứ hai với các số 2n, với n=1,2,3…Khi<br /> cần nhân với số bất kỳ, ta chỉ cần kết hợp một<br /> số cấu trúc trên để có kết quả đúng.<br /> Thực chất chỉ cần sử dụng 2 tầng hệ tổ hợp là<br /> ta có kết quả với mọi giá trị thừa số trong<br /> phép lấy tích (thƣơng). Nhƣ vậy trên nguyên<br /> lý tập đủ [5], kết hợp với các công nghệ<br /> đƣơng đại nhƣ công nghệ PLA, FPGA có thể<br /> tổng hợp đƣợc một lƣới thao tác với các phép<br /> tính cần thiết mà không gặp trở ngại lớn nào.<br /> Điều quan trọng là những cấu trúc đó chỉ cần<br /> một nhịp clock là chúng đã thực hiện xong<br /> thao tác của mình (về lý thuyết nhịp clock có<br /> thể có tần số bất kỳ).<br /> ĐỒNG TỔNG HỢP LƢỚI THAO TÁC CHO<br /> CPU RISC<br /> <br /> 78(02): 23 - 28<br /> <br /> Bây giờ ta xét sâu vào phân tích hoạt động<br /> của lõi CPU RISC cho trƣờng hợp dữ liệu<br /> vectơ, khi luồng dữ liệu đi vào lƣới thao tác<br /> với tốc độ lớn do chỉ cẩn quản lý thứ tự phần<br /> tử. Khi đó nếu luồng X và luồng Y đủ số<br /> lƣợng n, m phần tử và các hệ số H đã điền<br /> đầy lƣới thì cần 1 nhịp clock sẽ cho kết quả Z.<br /> Với Z đƣợc tính bằng:<br /> n<br /> <br /> Zi  Yi   XiHij ; (i= 1, m ; j= 1, n )<br /> j 1<br /> <br /> Tuy nhiên khi dung lƣợng dữ liệu cần xử lý<br /> lớn hơn khả năng xử lý một lần của cấu trúc<br /> này thì cần phải tổ chức lƣới thao tác phức<br /> tạp hơn thì mới bảo đảm hiệu năng cao.<br /> Lƣới thao tác đƣợc tổ chức nhƣ hình 4b. Bộ<br /> đệm lƣới có cấu trúc giống nhau và có đƣờng<br /> dẫn pipeline tƣơng ứng cho từng ô lƣới. Chỉ<br /> cần một nhịp clock (có thể nhịp clock này lớn<br /> hơn nhịp clock hệ thống) là copy toàn bộ nội<br /> dung bộ đệm lƣới sang lƣới thao tác.<br /> <br /> Bảng 1. Phép nhân với các số 2n<br /> Thừa số<br /> thứ nhất<br /> Thừa số<br /> thứ hai Im-I1<br /> Bƣớc dịch trái<br /> Tích<br /> <br /> 1<br /> <br /> 2<br /> <br /> 4<br /> <br /> 8<br /> <br /> 16<br /> <br /> 0..00<br /> <br /> 0..01<br /> <br /> 0..10<br /> <br /> 0..11<br /> <br /> 0..100<br /> <br /> 0<br /> =thừa số<br /> thứ nhất<br /> <br /> 1<br /> =2 lần thừa số<br /> thứ nhất<br /> <br /> 2<br /> =4 lần thừa số<br /> thứ nhất<br /> <br /> 3<br /> =8 lần thừa số<br /> thứ nhất<br /> <br /> 4<br /> =16 lần thừa số<br /> thứ nhất<br /> <br /> Bảng 2. Phép nhân với các số bất kỳ<br /> Thừa số<br /> thứ nhất<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 4<br /> <br /> 5<br /> <br /> 6<br /> <br /> 7<br /> <br /> 8<br /> <br /> Tích<br /> <br /> Cấu<br /> trúc<br /> nhân1<br /> <br /> Cấu<br /> trúc<br /> nhân2<br /> <br /> Cấu trúc<br /> nhân2 +<br /> Cấu trúc<br /> nhân1<br /> <br /> Cấu<br /> trúc<br /> nhân4<br /> <br /> Cấu trúc<br /> nhân4 +<br /> Cấu trúc<br /> nhân1<br /> <br /> Cấu trúc<br /> nhân4 +<br /> Cấu trúc<br /> nhân2<br /> <br /> Cấu trúc nhân4 +<br /> Cấu trúc nhân2 +<br /> Cấu trúc nhân1<br /> <br /> Cấu trúc<br /> nhân8<br /> <br /> Y<br /> <br /> Bộ<br /> <br /> hfifo<br /> Lƣới<br /> mn<br /> <br /> đệm<br /> <br /> Bộ đệm<br /> lƣới<br /> <br /> X<br /> <br /> Lƣới<br /> nm<br /> <br /> Acc<br /> fifo<br /> BUS<br /> <br /> a)<br /> <br /> b)<br /> <br /> Copy trong 1<br /> nhịp clock<br /> <br /> Hình 4. Cấu trúc khối thao tác lƣới của lõi CPU RISC khi kích thƣớc ô nhớ trong FIFO x  (m,n)<br /> <br /> 25<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Chu Đức Toàn và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 78(02): 23 - 28<br /> <br /> Đây chính là phhƣơng pháp tổng hợp cả phần<br /> cứng và cả phần mềm trên cùng trên một bƣớc :<br /> Phần cứng là tổ chức lƣới thao tác trên công<br /> nghệ FPGA, nơi mỗi ô lƣới là một hệ tổ hợp<br /> phức tạp gồm các cấu trúc tính toán cùng các<br /> mạch phụ trợ NOT AND OR và MUX sao<br /> cho đầu vào là tập hợp bit địa chỉ có số lƣợng<br /> là k (2k  max M ) cho chia cột và có số<br /> lƣợng q (2q  max N )cho chia hàng.<br /> Cú pháp của lệnh chia cột và hàng có thể thiết<br /> kế nhƣ: lệnh MOV Colreg, DivX hoặc MOV<br /> Rowreg, DivX với X=1 đến maxM (maxN) sẽ<br /> thực hiện gán số chia lƣới thành các phần.<br /> Lập tức các thanh ghi điều khiển sẽ ánh xạ<br /> vào phần cứng của lƣới để tái tổ chức lại cấu<br /> hình lƣới thao tác theo yêu cầu. Nếu<br /> maxM=maxN=64 bit thì lệnh chia cột (hàng)<br /> đƣợc thể hiện trên bảng 3.<br /> Nếu dung lƣợng dữ liệu cần xử lý vƣợt dung<br /> lƣợng các bộ đệm FIFO thì cần cơ cấu lặp để<br /> vẫn sử dụng thuật toán cũ. Khi đó cần cơ cấu<br /> điều khiển vòng lặp. Bằng cách này ta có thuật<br /> toán lặp mà phần thực hiện chính lại bằng phần<br /> cứng nên tốc độ sẽ vƣợt trội so với thuật toán<br /> lặp thuần túy bằng phần mềm (hình 5).<br /> <br /> Cấu trúc này bảm đảm là hệ số H đƣợc nạp<br /> vào ô lƣới trƣớc khi dữ liệu cần xử lý tới ô<br /> lƣới. Bộ đệm chứa hệ số H và Acc có cơ cấu<br /> FIFO giúp tăng dung lƣợng xử lý. Nếu kích<br /> thƣớc ô nhớ trong FIFO x  (m,n) và dung<br /> lƣợng dữ liệu cần xử lý bằng x*X thì chỉ cần=<br /> x+1 chu kỳ nhịp clock sẽ hoàn tất thao tác.<br /> Trƣờng hợp dữ liệu khác nhau về kích thƣớc<br /> (kích thƣớc phần tử có thể là 8 bit, 16 bit, 32<br /> bit...) thì thay vì sử dụng nhiều lƣới thao tác,<br /> có thể tổng hợp một cấu trúc kết hợp cả khâu<br /> tổ chức phần cứng và khâu xây dựng lệnh<br /> nhằm tái cấu hình lƣới thao tác theo kích<br /> thƣớc dữ liệu. Làm đƣợc điều này giúp giảm<br /> thiểu tài nguyên phần cứng của hệ thống đi<br /> rất nhiều. Cơ cấu điều khiển chia lƣới theo<br /> phƣơng án này bao gồm thanh ghi điều khiển<br /> chia lƣới thành m cột n hàng và đƣợc dùng<br /> nhƣ một lệnh mà khối EU của CPU thực hiện<br /> nhƣ những lệnh khác. Điều này giúp mềm hóa<br /> cấu hình của lƣới thao tác. Số lƣợng cột sẽ<br /> nằm trong khoảng 1  m  max M còn số<br /> lƣợng hàng trong khoảng 1  n  max N .<br /> <br /> Bảng 3. Phân chia lƣới thao tác<br /> <br /> Số chia<br /> Số lƣợng bit/ô lƣới<br /> thao tác (bit/ô)<br /> Số dƣ (bit)<br /> <br /> Div1<br /> <br /> Div2<br /> <br /> Div3<br /> <br /> Div4<br /> <br /> Div5<br /> <br /> -------<br /> <br /> Div64<br /> <br /> 64<br /> <br /> 32<br /> <br /> 21<br /> <br /> 16<br /> <br /> 12<br /> <br /> ------<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 1<br /> <br /> 0<br /> <br /> 2<br /> <br /> ------<br /> <br /> 0<br /> <br /> hfifo<br /> <br /> Y<br /> <br /> Bộ đệm lƣới<br /> <br /> Bộ điều khiển dịch vòng<br /> <br /> X<br /> <br /> Lƣới<br /> mn<br /> <br /> Acc<br /> fifo<br /> <br /> BUS<br /> <br /> Hình 5. Cấu trúc khối thao tác lƣới của lõi CPU RISC khi kích thƣớc ô nhớ trong fifo x  (m,n)<br /> <br /> 26<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Chu Đức Toàn và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Toàn bộ cấu trúc đƣợc tổng hợp nhƣ trên cho<br /> phép phát động các tiến trình song song ngay<br /> trong lõi CPU RISC bằng 1 dòng lệnh. Nếu<br /> đƣa dòng lệnh dạng:<br /> repeat 16 hfifo = [r0++], fth, hth<br /> vào cấu trúc phần cứng đƣợc tổ chức nhƣ trên<br /> ta có vế trái repeat 16 hfifo = [r0++] là tiến<br /> trình lặp 16 vòng, mỗi vòng là một lần tải<br /> data từ bộ nhớ hệ thống vào bộ đệm hfifo còn<br /> vế phải là 2 tiến trình: (i) fth là tiến trình copy<br /> hệ số từ hfifo vào ô lƣới thao tác phụ; (ii) hth<br /> là tiến trình copy hệ số từ ô lƣới thao tác phụ<br /> vào ô lƣới thao tác chính. Phân tích quá trình<br /> thực hiện lệnh trên bằng đồ thị thời gian dễ<br /> dàng nhận thấy chúng là 3 tiến trình song<br /> song do các bƣớc thực hiện đƣợc xếp chồng<br /> về mặt thời gian (hình 6).<br /> Nhƣ vậy, trừ 2 nhịp clock đầu tiên là t0 và t1<br /> thì từ t2 trở đi 3 tiến trình hfifo = [r0++]; fth;<br /> hth là thực hiện song song thật sự giúp tăng<br /> tốc độ tính toán đáng kể (trƣờng hợp cực đại<br /> sẽ là 3 lần).<br /> <br /> KẾT LUẬN<br /> Nếu cấu trúc ô lƣới thao tác đƣợc tổ chức<br /> dƣới dạng hệ tổ hợp thì thời gian thực hiện<br /> Nhịp<br /> clock<br /> hfifo<br /> ô lƣới<br /> phụ<br /> ô lƣới<br /> chính<br /> <br /> t0<br /> <br /> H1<br /> <br /> 78(02): 23 - 28<br /> <br /> tính toán toàn bộ n hàng của lƣới chỉ tiêu tốn<br /> đúng 1 chu kỳ clock.<br /> Nếu sử dụng công nghệ FPGA thì tính khả thi<br /> của thiết kế ô lƣới thao tác, nhất là đối với hệ<br /> chức năng, khi mà các phép tính là hạn chế<br /> trong một lớp bài toán cụ thể.<br /> Đồng tổng hợp giúp bổ xung vào tập lệnh<br /> những lệnh mới nhằm đạt hiệu năng cao nhất<br /> mà không phá vỡ kiến trúc Harvart của CPU<br /> RISC.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Lê Xuân Bằng.Kỹ thuật số.Nxb Khoa học kỹ<br /> thuật, 2009, Tr131-148.<br /> [2]. Đỗ Xuân Tiến. Kỹ thuật vi xử lý và lập trình<br /> Assembly cho hệ vi xử lý. Nxb Khoa học kỹ thuật,<br /> 2009.<br /> [3]. Kai Hwang, Faye A.Briggs. Computer<br /> architecture and parallel processing. McGrawHill Book Company<br /> [4]. Richard Cloutier, Synthesis of Pipelined<br /> Instruction Set Processors, Ph.D. dissertation,<br /> Dept. of Electrical and Computer Engineering,<br /> Carnegie Mellon University, 1993. Alsoavailable<br /> as a Research Report No. CMUCAD-93-03.<br /> [5]. Raymond E.Miller.Swiching theory. John<br /> Wiley & Sons, Inc.<br /> <br /> t1<br /> <br /> t2<br /> <br /> t3<br /> <br /> t4<br /> <br /> H2<br /> <br /> H3<br /> <br /> H4<br /> <br /> H5<br /> <br /> H1<br /> <br /> H2<br /> <br /> H3<br /> <br /> H4<br /> <br /> H2<br /> <br /> H3<br /> <br /> H1<br /> <br /> pipeline pipeline pipeline pipeline<br /> Hình 6. Hoạt động của lƣới thao tác gồm 3 tiến trình song song (hệ số H có giá trị từ h 11 đến hnm)<br /> <br /> 27<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br />