Tiểu luận Advanced Techniques for Instruction Delivery and Speculation - Phương pháp kỹ thuật nâng cao cho cấp phát chỉ lệnh và dự đoán

Tr­êng ®¹i häc b¸ch khoa hµ néi ******
***** TIỂU LUẬN MÔN HỌC KIẾN TRÚC MÁY TÍNH Nội dung: Advanced Techniques for Instruction Delivery and Speculation PHÚ THỌ 11-2010 MỤC LỤC MỞ ĐẦU 3 Phương pháp kỹ thuật nâng cao cho cấp phát chỉ lệnh và dự đoán 4 1. Tìm nạp chỉ lệnh tăng băng thông 4 1.1. Bộ đệm chỉ mục nhánh 4 1.2. Dự báo địa chỉ trả về 7 1.3. Tích hợp tìm nạp chỉ lệnh 8 2. Tích trữ lệnh thi hành và mở rộng 9 2.1. Đăng ký đổi tên so với sắp xếp lại 9 2.2. Tích trữ qua các nhánh đa bội……….…………………………………………11 2.3. Dự đoán giá trị 11 MỞ ĐẦU Sự phát triển của máy tính được mô tả dựa trên sự tiến bộ của các công nghệ chế tạo các linh kiện cơ bản của máy tính như: bộ xử lý, bộ nhớ, các thiết bị ngoại vi,…Máy tính điện tử số đã trải qua bốn thế hệ liên tiếp. Việc chuyển từ thế hệ trước sang thế hệ sau được đặc trưng bằng một sự thay đổi cơ bản về công nghệ. Thế hệ thứ tư được đánh dấu bằng các IC có mật độ tích hợp cao (LSI: Large Scale Integration) có thể chứa hàng ngàn linh kiện. Các IC mật độ tích hợp rất cao (VLSI: Very Large Scale Integration) có thể chứa hơn 10 ngàn linh kiện trên mạch. Các tiến bộ liên tục về mật độ tích hợp trong VLSI đã cho phép thực hiện các mạch vi xử lý ngày càng mạnh (8 bit, 16 bit, 32 bit và 64 bit với việc xuất hiện các bộ xử lý RISC năm 1986 và các bộ xử lý siêu vô hướng năm 1990). Chính các bộ xử lý này giúp thực hiện các máy tính song song với từ vài bộ xử lý đến vài ngàn bộ xử lý Các kỹ thuật cải tiến tốc độ xử lý của máy tính không ngừng được phát triển: kỹ thuật ống dẫn (pipeline), kỹ thuật vô hướng, xử lý song song mức độ cao,…Pipelining là một phương pháp xử lý lệnh trên một pipeline lệnh, có thể xử lý nhiều lệnh đồng thời trong cùng một khoảng thời gian. Trong khi lệnh này đang được xử lý thì lệnh tiếp sau nó đã được nhận vào Trên lí thuyết, việc sử dụng kĩ thuật pipeline sẽ làm tăng tốc độ lên gần 400% nhưng thực tế,việc tăng tốc độ được bao nhiêu còn phụ thuộc vào các kiểu xung đột khác nhau. Control Hazard là xung đột xảy ra khi có lệnh rẽ nhánh, do đó còn gọi là Branch Hazard. Khi có nhánh thì phương pháp đơn giản nhất để khắc phục control hazard là gây trễ kịp thời trên pipeline để phát hiện nhánh cho đến khâu MEM mới sử dụng giá trị mới của PC. Tuy vậy ba chu kỳ bỏ phí ở mỗi nhánh là hao phí có nghĩa với tần số rẽ nhánh là 30% và 1 CPI lý tưởng là 1, máy tính có trễ rẽ nhánh sẽ đạt khoảng ½ lượng tăng tốc lý tưởng của pipeline. Trong tiểu luận này sẽ trình bày vấn đề “Advanced Techniques for Instruction Delivery and Speculation” (Phương pháp kỹ thuật nâng cao cho cấp phát chỉ lệnh và dự đoán). Với thời gian và kiến thức còn hạn chế, báo cáo này không tránh khỏi những thiếu sót, rất mong được sự quan tâm định hướng của các thầy cô giáo, sự góp ý của của các bạn học viên để báo cáo hoàn thiện hơn. Em xin trân thành cảm ơn thầy giáo TS. Nguyễn Hồng Quang và các bạn trong lớp đã ủng hộ, giúp đỡ trong suốt quá trình thực hiện. Học viên Nguyễn Trung Kiên Advanced Techniques for Instruction Delivery and Speculation (Phương pháp kỹ thuật nâng cao cho cấp phát chỉ lệnh và dự đoán) Trong một pipeline dẫn hiệu suất cao, đặc biệt là một với nhiều vấn đề, dự đoán Nhánh cũng là không đủ, chúng ta thực sự có để có thể cung cấp một highbandwidth chỉ lệnh dòng. Trong gần đây nhiều bộ xử lý-vấn đề, điều này có nghĩa là cung cấp chỉ lệnh 4-8 mỗi chu kỳ đồng hồ. Chúng tôi nhìn vào các phương pháp để gia tăng chỉ lệnh phân phối băng thông đầu tiên. Chúng tôi sau đó chuyển sang một tập hợp các vấn đề then chốt trong việc thực hiện nâng cao kỹ thuật tích trữ, bao gồm cả việc sử dụng đổi tên đăng ký so với bộ đệm sắp xếp lại, những gây hấn của tích trữ, và kỹ thuật được gọi là giá trị dự báo, có thêm có thể tăng cường ILP. 1. Tìm nạp chỉ lệnh tăng băng thông Một bộ đa xử lý sẽ yêu cầu thông lượng trung bình ở mỗi chu kỳ đồng hồ lớn hơn thông trung bình của mô hình pipeline lý tưởng. Tất nhiên, thông lượng còn phụ thuộc vào băng thông có đủ rộng hay không khi truy cập bộ nhớ cache, nhưng các vấn đề khó khăn nhất là xử lý các lệnh điều khiển rẽ nhánh. Trong phần này chúng ta nhìn tại hai phương pháp cho việc xử lý phân phát các nhánh và sau đó thảo luận về bộ vi xử lý thế nào là hiện đại tích hợp các dự đoán chỉ lệnh và tìm nạp trước các hàm. 1.1. Bộ đệm chỉ mục nhánh Để giảm bớt hao phí do độ trễ rẽ nhánh của pipeline trong năm khâu riêng biệt của một lệnh, cũng như cho pipeline dẫn sâu hơn, chúng ta phải biết tiên đoán các lệnh chưa được giải mã của một nhánh và những gì các con trỏ PC kế tiếp sẽ được. Nếu chỉ lệnh này là một nhánh và chúng ta biết những gì các con trỏ PC kế tiếp sẽ được, chúng ta có thể có một hao phí do độ trễ rẽ nhánh là 0. Dự đoán trước bộ nhớ cache nhánh để lưu địa chỉ dự đoán cho các chỉ lệnh kế tiếp sau khi nhánh được gọi là một bộ đệm chỉ mục nhánh hoặc chỉ mục bộ nhớ cache nhánh. (Hình 1 cho thấy một bộ đệm chỉ mục nhánh) Bởi vì một bộ đệm chỉ mục nhánh dự đoán địa chỉ lệnh kế tiếp và sẽ gửi nó đi trước khi giải mã chỉ lệnh, nên chúng ta phải biết tìm nạp chỉ lệnh được dự đoán có là một nhánh được thực hiện hay không. Nếu con trỏ PC đã tải chỉ lệnh phù hợp với một con trỏ PC trong bộ đệm dự báo, sau đó các con trỏ PC tương ứng dự đoán được sử dụng như các con trỏ PC tiếp theo. Các phần cứng cho bộ đệm chỉ mục nhánh là cơ bản giống với các phần cứng cho một bộ nhớ cache. Nếu một mục phù hợp được tìm thấy trong bộ đệm chỉ mục nhánh, quá trình tìm nạp bắt đầu ngay lập tức tại các con trỏ PC dự đoán. Lưu ý rằng không giống như một bộ đệm chỉ mục nhánh dự báo, các mục nhập tiên đoán phải được kết hợp với chỉ lệnh này, vì các con trỏ PC dự đoán sẽ được gửi ra trước khi nó được biết đến dù chỉ thị này là cả một nhánh. Nếu bộ vi xử lý không kiểm tra xem các mục nhập thì con trỏ PC sẽ gửi ra các chỉ lệnh sai dẫn đến xử lý chậm hơn. Chỉ cần lưu trữ các dự đoán nhánh thực hiện trong các bộ đệm chỉ mục nhánh, nếu nhánh không được sử dụng đơn giản chỉ cần tìm nạp tiếp theo tuần tự chỉ lệnh, như thể nó là không phải là một nhánh.
Hình 1: Bộ đệm chỉ mục nhánh Các con trỏ PC của lệnh được lấy bản chất là quá trình tìm nạp qua một tập hợp các chỉ lệnh địa chỉ được lưu trữ trong cột đầu tiên, đó là những địa chỉ của nhánh được biết đến. Nếu con trỏ PC phù hợp với một trong những mục này thì sau đó các chỉ dẫn được tải là một nhánh được thực hiện. Cột thứ hai là địa chỉ dự đoán của con trỏ PC, bao gồm các dự đoán cho các con trỏ PC tiếp theo sau khi rẽ nhánh và sử dụng ngay tại địa chỉ đó. Cột thứ ba là tùy chọn, có thể được sử dụng thêm cho bit dự báo điều kiện.
Hình 2: Sơ đồ xử lý một lệnh với chỉ mục vùng đệm nhánh Hình 2 cho thấy các bước chi tiết khi sử dụng một bộ đệm chỉ mục nhánh cho năm khâu của một lệnh trong pipeline. Có thể thấy rằng sẽ không có chu kỳ trễ nếu một mục nhánh dự đoán được tìm thấy trong bộ đệm và dự đoán là chính xác. Nếu không, sẽ có độ trễ ít nhất là 2 chu kỳ đồng hồ (1 chu kỳ đồng hồ để cập nhật các bộ đệm với các thông tin chính xác và 1 đồng hồ chu kỳ để khởi động lại quá trình lấy đúng chỉ lệnh tiếp theo cho các nhánh). Việc quản lý các dự đoán và lưu trữ là một thách thức lớn. Để đánh giá một bộ đệm chỉ mục nhánh làm việc như thế nào, đầu tiên phải xác định các chu kỳ trễ trong mọi trường hợp có thể (Bảng 3 chứa thông tin này cho một lệnh trong pipeline) Instruction in buffer  Prediction  Actual Branch  Penalty Cycles   Yes  Taken  Taken  0   Yes  Taken  Not Taken  2   No   Taken  2   No   Not Taken  0   Bảng 3: Đánh giá chu kỳ trễ trong các trường hợp sử dụng bộ đệm chỉ mục nhánh Một thay đổi của bộ đệm chỉ mục nhánh là để lưu trữ một hoặc nhiều mục tiêu chỉ lệnh thay vì chỉ thêm vào các địa chỉ mục tiêu dự đoán. Điều thay đổi này có hai ưu điểm. Đầu tiên, nó cho phép truy cập vào bộ đệm chỉ mục nhánh lâu hơn thời gian giữa hai lần nạp kế tiếp vì thế có thể cho phép một bộ đệm chỉ mục nhánh lớn hơn. Thứ hai, bộ đệm chỉ lệnh mục tiêu thực tế cho phép được thực hiện tối ưu hoá được gọi là branch folding (nhánh gấp), nhánh gấp có thể được sử dụng để có được 0 chu kỳ trễ khi nhánh không điều kiện, và đôi khi 0 chu kỳ chễ khi nhánh có điều kiện. Xem xét một bộ đệm chỉ mục nhánh mà bộ đệm chỉ lệnh từ đường dẫn dự đoán và đang được truy cập bằng địa chỉ của một vô điều kiện nhánh. Các chức năng duy nhất của nhánh không điều kiện là để thay đổi con trỏ PC. Do đó, khi bộ đệm chỉ mục nhánh báo hiệu một hit và chỉ ra rằng nhánh vô điều kiện, các pipeline có thể chỉ cần thay thế các chỉ dẫn từ các bộ đệm chỉ mục nhánh tại chỗ của lệnh đó được trả về từ bộ nhớ cache (đó là các nhánh không điều kiện). Nếu có nhiều chỉ lệnh trên chu kỳ thì bộ đệm cần cung cấp nhiều chỉ lệnh để có được tối đa hiệu suốt. Trong một số trường hợp, có thể loại bỏ được các chu kỳ trễ của một điều kiện nhánh khi các mã điều kiện được cài sẵn. 1.2. Dự báo địa chỉ trả về Để tăng độ chính xác của dự đoán, ta phải tăng độ chính xác trong việc dự đoán nhảy gián tiếp. Nhảy gián tiếp có nghĩa là nhảy có địa chỉ đích thay đổi trong thời gian chạy. Mặc dù các chương trình ngôn ngữ bậc cao sẽ tạo ra các thủ tục nhảy gián tiếp như câu lệnh select – case hay câu lệnh Goto, đại đa số các lệnh nhảy gián tiếp đến từ thủ tục trả về. Ví dụ với các tiêu chí chuẩn của SPEC95, các thủ tục trả lại chiếm khoảng hơn 15% của các lệnh rẽ nhánh và đa số là nhảy gián tiếp. Đối với các ngôn ngữ hướng đối tượng như C++ và Java, thủ tục thậm chí nhiều hơn. Mặc dù có thể được dự đoán các địa chỉ đích trong các lệnh nhảy gián tiếp với một bộ đệm chỉ mục nhánh, tuy nhiên tính chính xác của dự đoán sẽ thấp nếu thủ tục được gọi từ nhiều chương trình hoặc gọi từ một chương trình nhưng trong thời gian khác nhau. Ví dụ trong SPEC CPU95 dự báo đạt được độ chính xác ít hơn 60% cho các câu lệnh nhánh gọi trở lại như vậy. Để khắc phục vấn đề này, một số mẫu thiết kế sử dụng một bộ đệm lưu trữ các địa chỉ trả về gần đây nhất và sau đó lấy ra khi cần đến. Nếu bộ nhớ cache đủ lớn thì dự đoán đạt được trở nên chính xác hơn.
Hình 3: SPEC CPU95 đánh giá hiệu suất bộ đệm lưu trữ các địa chỉ trả về (dữ liệu từ Skadron et al. 1999) 1.3. Tích hợp tìm nạp chỉ lệnh Để đáp ứng nhu cầu của bộ vi xử lý đa cấp, nhiều nhà thiết kế gần đây đã thiết kế thực hiện một chỉ dẫn tìm nạp chỉ lệnh tích hợp, nó như là một phần riêng biệt có nguồn cấp dữ liệu. Về cơ bản, điều này để nhận ra rằng đặc trưng chức năng đơn lẻ trong từng giai đoạn trong pipeline phức tạp là không phù hợp. Thay vào đó, thiết kế gần đây đã sử dụng một chỉ dẫn tích hợp, trong một giai đoạn có thể tích hợp một số chức năng: 1. Tích hợp dự báo nhánh: dự báo nhánh như là một thành một phần của tìm nạp chỉ lệnh và được liên tục dự đoán để cung cấp các chỉ dẫn trong quá trình tìm nạp chỉ lệnh trong pipeline. 2. Tìm nạp chỉ lệnh: để cung cấp nhiều chỉ lệnh cho mỗi chu kỳ đồng hồ, các chỉ lệnh lấy cần phải tìm nạp trước. Các bộ phận quản lý việc tìm nạp trước các chỉ lệnh phải được tích với dự báo nhánh. 3. Truy cập bộ nhớ và bộ đệm: khi lấy nhiều chỉ lệnh trong mỗi chu kỳ sẽ gặp nhiều phức tạp, khó khăn. Việc lấy nhiều chỉ lệnh sẽ phải truy cập nhiều vào bộ nhớ cache. Điều này đã được giải quyết nhờ sử dụng kỹ thuật “trace caches (lưu trữ dấu vết)” đã được sử dụng trong Pentium 4 2. Tích trữ lệnh thi hành và mở rộng Có ba vấn đề liên quan đến việc thực hiện tích trữ là: việc sử dụng đổi tên đăng ký đây là phương pháp thay thế việc sử dụng một bộ đệm sắp xếp lại; mở rộng tích trữ trên các nhánh đa bội và dự đoán giá trị. 2.1. Đăng ký đổi tên so với sắp xếp lại Một thay thế cho việc sử dụng một bộ đệm sắp xếp lại (ROB) là việc sử dụng hàng lọat những lệnh đăng ký cùng với lệnh đặt lại tên đăng ký. Cách tiếp cận này được xây dựng trên khái niệm về đổi tên được sử dụng trong thuật toán Tomasulo và mở rộng nó. Ý tưởng của thuật toán là sử dụng địa chỉ Tag và bit trạng thái để đánh dấu các thanh ghi, qua đó biết được thanh ghi đó đang bận hay rỗi để sử dụng cho phù hợp. Trong thuật toán của Tomasulo, các giá trị của kiến trúc đăng ký xuất hiện trong các thanh ghi (R0,.., R31 và F0,.. , F31) được chứa tại bất kỳ điểm nào trong việc thi hành, kết hợp một số của đăng ký thiết lập ở các trạm dự trữ. Cùng với việc tích trữ các giá trị đăng ký tập trung tạm thời ở ROB. Trong trường hợp nếu bộ xử lý không đưa ra các hướng dẫn mời trong một khoảng thời gian thì hầu hết những hướng dẫn tồn tại sẽ xác nhận, các giá trị đăng ký sẽ xuất hiện trong tệp đăng ký mà tương ứng với lệnh đăng ký xuất hiện. Trong phương pháp đặt lại tên đăng ký một bộ đăng ký vật lý mở rộng được sử dụng để giữ cả hai kiến trúc đăng ký có thể nhìn thấy cũng như các giá trị tạm thời. Như vậy, đăng ký mở rộng thay thế các chức năng của cả ROB và trạm dự trữ. Khi phát hiện ra lệnh dẫn, quá trình lặp lại tên sẽ lập lại sơ đồ các tên đăng ký kiến trúc tới các con số đăng ký vật lý trong bộ đăng ký mở rộng, đồng thời phân phối một lệnh đăng ký mời tới điểm đến. Khi đó, một bản đồ quá trình đổi tên kiến trúc đăng ký để đăng ký số vật lý vào sổ đăng ký gia hạn, bố trí một đăng ký mới chưa sử dụng cho các điểm đến. Lợi thế của phương pháp đặt lại tên sơ với phương pháp ROB là chỉ lệnh thực hiện đơn giản hóa, vì nó chỉ yêu cầu hai hành động đơn giản + Việc ghi lại: ghi lại là ánh xạ giữa một số kiến trúc đăng ký và đăng ký vật lý không được tích trữ + Xóa bớt: xóa những lệnh đăng ký vật lý được sử dụng để duy trì giá trị cũ của việc đăng ký kiến trúc Trong thiết kế trạm dữ trữ được hủy khi các chỉ lệnh sử dụng nó thực hiện hoàn thành và ROB được hủy khi các chỉ dẫn là tương ứng. Cùng với việc đặt lại tên đăng ký, viêc phân phối lại lệnh đăng ký cũng phức tạp hơn vì trước khi chúng xóa lệnh đăng ký vật lý chúng ta nó không còn được tương ứng với một lệnh đăng ký kiến trúc nữa mà lệnh đăng ký vật lý tương ứng với lệnh đăng ký kiến trúc cho tới khi lệnh đăng ký kiến trúc được viết lại đồng thời làm cho biểu đồ đặt tên chỉ điểm ở nơi khác. Nếu một lệnh đăng ký vật lý cho sẵn không xuất hiện như là một nguồn hay không đóng vai trò là lệnh đăng ký kiến trúc nó sẽ bị sửa lại. Giả xử bộ xử lý không đưa ra lệnh dẫn, chúng ta sẽ hiểu được khả năng này được hỗ trợ như thế . Dần dần thì hầu hết các lệnh sẽ được xác nhận và việc lập biểu biểu đồ giữa các lệnh đăng ký kiến trúc hiện và các lệnh đăng ký vật lý sẽ ổn định Ưu thế của việc tích trữ là khả năng khám phá ra những sự kiện nằm ở đường dẫn. Tuy nhiên lợi thế này cũng có một bất lợi. Việc tích trữ không miên phí, nó mất thời gian và năng lượng. Sự phục hồi việc tích trữ không chính xác làm giảm việc thi hành lệnh. Để hỗ trợ tỷ lệ thi hành hướng dẫn cao hơn cần lợi thế của việc tích trữ, bộ xử lý phải có thêm nguồn, các nguồn này chứa vùng silicon và năng lượng. Cuối cùng nếu như việc tích trữ gây ra một sự kiện khác thì khả năng thi hành lệnh sẽ giảm đi. 2.2. Tích trữ qua các nhánh đa bội a. Tích trữ dữ liệu như thế nào. Để duy trì những thuật lợi, hầu hết đường dẫn với sự tích trữ sẽ cho phép thi hành chỉ những sự kiện chi phí thấp ở phương thức tích trữ. Nếu có thêm một sự kiện nào nữa thì bộ xử lý phải đợi cho đến khi hướng dẫn không tích trữ sự kiện này nữa trước khi thi hành giải quyết sự kiện này. b. Tích trữ qua các nhánh đa bội Việc phân tích một nhánh trước khi tích trữ lên một nhánh khác là có thể thực hiện. Việc tích trữ lên các nhánh đa bội đồng loạt có thể đem lại 3 lợi thế: - Tần xuất nhánh rất cao - Việc phân nhánh cần thiết - Sự trì hoãn lâu dài trong các đơn vị chức năng Trong 2 lợi thế đầu, việc thi hành có hiệu quả, có nghĩa là nhánh đa bội được tích trữ và nó có thể thi hành hơn một nhánh theo chu kỳ thời gian. Việc tích trữ lên các nhành đa bội làm cho quá trình phục hồi tích trữ phức tạp nhưng liền mạch. Một kỹ thuật phức tạp hơn là việc dự đoán và tích trữ trong một nhánh theo chu kỳ. 2.3. Dự đoán giá trị Một kỹ thuật để tăng ILP có trong dự đoán giá trị tìm ra những giá trị được tìm thấy bởi một lệnh dẫn. Hầu hết các hướng dẫn đều sản xuất một giá trị khác vào lúc chúng đang được thi hành. Nhưng chúng có nhưng giới hạn. Tuy nhiên cũng có những lời dẫn rất dễ đoán kết quả. Thêm nữa khi một lời dẫn đưa ra giá trị được chọn từ bộ giá trị tiềm năng nó có thể đoán giá trị kết quả bằng cách làm tương quan mà không cần ví dụ Việc dự đoán giá trị rất có ích nếu nó tăng số lượng ILP có sẵn. Khả năng này xảy ra khi một giá trị được sử dụng để là nguồn cho chuỗi tính toán phụ thuộc. Bởi vì dự đoán giá trị tăng phần tích trữ và việc tích trữ không đúng có ảnh hưởng bất lợi đến việc thi hành của máy tính nên tính chính xác mang tính giới hạn. Chúng ta có thể tính toán sự chính xác tối đa của việc dự đoán giá trị nhập vào bằng cách kiểm tra xem việc nhập vào trả về một giá trị phù hợp với giá trị được trả lại khi nhập dự liệu có thường xuyên không. Một trường hợp đơn giản đề kiêm tra là khi lệnh nhập trả về một giá trị phù hợp với giá trị ở lần nhập cuối cùng. Nếu chúng ta cho phép sự nhập vào này ứng với 16 giá trị trả về gần nhất thì sự thiếu hụt 5% ở SPEC CPU2000 tăng lên. Một ý đơn giả có liên qua đến việc dự đoán là việc dự đoán dạng răng của các địa chỉ. Việc này là kỹ thuật đơn giả để dự đoán 2 ngăn cất dữ liệu hoặc một ngăn nhập, một ngăn cất dữ liệu có liên quan tới địa chỉ bộ nhớ ngoài cùng loại. Nếu 2 giá trị tham chiếu không liên quan tới địa chỉ cùng một địa chỉ, chúng có thể bị hoán đổi. Mặt khác chúng ta phải đợi tới khi địa chỉi bộ nhớ được xác định trong các hướng dẫn rõ ràng. Bời vì chúng ta không cần đoán trước các giá trị địa chỉ, thường chỉ khác các giá trị tương khắc thì việc dự đoán sẽ ổn định và đơn giản hơn. Vì thế hình thức giới hạn của việc tích trữ các giá trị địa chỉ cũng được xử dụng trong một và bộ vi xử lý.