Xác định con đường quan trọng trong các dữ liệu chảy

Question

Trong cuốn sách Computer Systems: A Programmer Perspective, các Tập thể dục 5,5 cho thấy một đoạn mã để tính giá trị của một đa thức

double poly(double a[], double x, int degree) 
{ 
    long int i; 
    double result = a[0]; 
    double xpwr = x; 
    for (i = 1; i <= degree; i++) { 
     result += a[i] * xpwr; 
     xpwr = x * xpwr; 
    } 
    return result; 
} 

Cuộc diễn tập giả định rằng các chu kỳ đồng hồ cần thiết cho phép cộng thêm dấu chấm động và phép nhân là 3 và 5 tương ứng. Người đọc được yêu cầu giải thích lý do tại sao CPE đo (Cycles Per Element) giá trị là 5.

Theo câu trả lời tập thể dục, trong mỗi lần lặp, chúng ta cần phải cập nhật các biến xpwr và result, và các hoạt động chúng ta cần là một bổ sung dấu chấm động (cho result) và một phép nhân dấu phẩy động (cho xpwr), do đó sau này chiếm ưu thế độ trễ, khiến CPE tối hậu là 5.

Nhưng tôi nghĩ luồng dữ liệu phải giống như này:

xpwr    result 
    |     | 
    +-----+ +--[load] | 
    |  | |   | 
[mul] [mul]   | 
    |  |   | 
    |  +---+ +-----+ 
    |   | | 
    |   [add] 
    |   | 
    |   +------+ 
    |     | 
xpwr    result 

Vì vậy, đường dẫn dài nhất là từ giá trị trước đó của xpwr đến giá trị mới của result, đi qua các đơn vị thực hiện [mul] và [add]. Do đó thời gian dài nhất nên là 8 chu kỳ.

Tôi muốn hỏi

1. gì chính xác là ý nghĩa của một con đường quan trọng? Và làm thế nào để xác định nó?
2. Câu trả lời (mỏ và sách) nào hợp lý hơn?

Bất kỳ giải thích nào về CPU, kiến ​​trúc, đơn vị thực thi, đường ống, đơn vị dấu chấm động sẽ được đánh giá cao.

Answer 1

Đường dẫn quan trọng là con đường dài nhất thông qua biểu đồ, trong trường hợp này là 8 đồng hồ. Đây là những gì Dragon Book đã nói về những con đường quan trọng (10.3.3 Orders tôpô ưu tiên):

Nếu không có những hạn chế tài nguyên, lịch trình ngắn nhất được đưa ra bởi con đường quan trọng , con đường dài nhất thông qua đồ thị dữ liệu phụ thuộc . Số liệu hữu ích làm chức năng ưu tiên là chiều cao của nút, trong đó là độ dài của đường đi dài nhất trong biểu đồ bắt nguồn từ nút .

Tôi nghĩ bạn đã tìm thấy lỗi trong sách. Bạn nên xem xét liên hệ với các tác giả, để họ có thể sửa nó trong các bản in sau này.

Answer 2

Đường dẫn tới hạn thực sự là 8 chu kỳ, nhưng câu hỏi yêu cầu CPE, giống như thời gian trung bình thời gian để xuất thêm một chu kỳ vòng lặp.

Khác với chu kỳ đầu tiên và cuối cùng, bộ xử lý có thể thực hiện việc bổ sung từ phép lặp trước đó của vòng lặp và phép nhân hiện tại cùng một lúc, vì các toán hạng không phụ thuộc lẫn nhau. Vòng lặp đầu tiên của vòng lặp mất 8 chu kỳ đầy đủ, nhưng tất cả các lần lặp lại sau đó, vòng lặp chỉ mất 5 chu trình để chạy, tạo ra các chu kỳ CPE 5 thực tế.

P.S.Tôi đồng ý rằng cách trình bày con đường quan trọng của cuốn sách là khó hiểu. Định nghĩa của họ về con đường quan trọng không chỉ đơn giản là con đường có con đường dài nhất, nhưng con đường cũng phải có các hoạt động có toán hạng phụ thuộc vào các hoạt động trước đó và do đó phải theo thứ tự. Định nghĩa này làm cho việc tìm kiếm con đường quan trọng thay vì không trực quan.

Answer 3

Tôi biết tôi hơi muộn với bữa tiệc, nhưng cuốn sách hoàn toàn đúng. Như bạn có thể xác minh cho mình bằng cách định thời gian mã, CPE thực sự là 5, vì vậy câu trả lời thứ hai là sai.

Nhưng điều đầu tiên cũng sai. Nó nói rằng các MUL phải được thực hiện cùng một lúc mà không phải là tất cả có thể có trong kiến ​​trúc Nehalem (và tôi nghi ngờ, hầu hết các bộ vi xử lý hiện đại). Hãy nhớ rằng chỉ có một đơn vị FP MUL và một đơn vị khác nhau FP Thanh (như thể hiện trong cuốn sách, ed năm 2011 và sau đó.)

gì sẽ xảy ra thay vì đây là:

(tải được giả luôn luôn hiện diện, chỉ cần 1 chu kỳ nếu trong bộ nhớ cache)

Đầu tiên chúng tôi cấp xpwr *= x trong MUL. Ngay sau đó chúng tôi cho ăn xpwr*a[i] (nhớ đường ống!)

... sau 5 chu kỳ, chúng tôi sẽ nhận được giá trị mới xpwr và sau 6 chu kỳ, chúng tôi sẽ có kết quả là xpwr*a[i]. Tại thời điểm đó, một tính toán mới của xpwr *= x sẽ ở giai đoạn 1 của MUL. Vì vậy, chúng tôi chỉ có thêm 4 chu kỳ để thực hiện các hoạt động còn lại nếu chúng tôi không muốn bị hạn chế bởi chúng.

Tất nhiên, điều đó thật dễ dàng vì chúng tôi chỉ cần 3 chu kỳ cho FP ADD để có được result mới.

Vì vậy, nó trở nên rõ ràng rằng yếu tố giới hạn là tính toán của xpwr. Điều đó có nghĩa rằng trong việc tìm kiếm con đường quan trọng (bất kể đó là gì) chúng ta phải nhìn cụ thể vào con đường từ các giá trị cũ đến cái mới. Trong trường hợp này, đường dẫn cho result chỉ bao gồm một phần bổ sung FP! (đó là những gì đã ném tôi ra đầu tiên quá)

Answer 4

A1: Đường dẫn quan trọng là đường dài nhất trong biểu đồ lưu lượng dữ liệu theo sách, phải nằm trên đường thẳng và có hiệu lực trên một thanh ghi đơn hơn là thêm 'mul' và 'add', kết quả của nó chỉ là các toán hạng trung gian cho các phép toán tiếp theo.

Về câu hỏi này, bạn sẽ hoàn thành tất cả nếu tiếp tục đọc phần còn lại. Đặc biệt, so sánh biểu đồ luồng dữ liệu của kết hợp 7 và kết hợp của một trong 5 có thể hữu ích.

A2: Nếu A1 được hiểu, Question2 là rõ ràng, câu trả lời trong cuốn sách là hợp lý.