Определить критический путь в потоке данных

Question

В книге Компьютерные системы: программист Перспектива, упражнение 5.5 показывает фрагмент кода для вычисления значения полинома

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; 
} 

упражнения предполагает, что тактовые циклы, которые необходимы для сложения и умножения с плавающей запятой с двойной точностью, равны 3 и 5 соответственно. Читатель просит объяснить, почему измеренное CPE (Cycles Per Element) значение 5.

Согласно прогулочному ответу, в каждой итерации, нам необходимо обновить переменные xpwr и result, и операции, которые нам нужны является добавлением с плавающей запятой (для result) и умножением с плавающей запятой (для xpwr), поэтому последний доминирует в латентности, в результате чего конечный CPE составляет 5.

Но я думаю, что поток данных должен быть чем-то вроде это:

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

Таким образом, самый длинный путь от предыдущего значения xpwr до нового значения result, проходящий через исполнительные устройства [mul] и [add]. Поэтому самое длинное время должно быть 8 циклов.

Я хочу спросить

1. Что именно смысл критического пути? И как это определить?
2. Какой ответ (мой и книга) более разумный?

Любые объяснения относительно процессора, архитектуры, исполнительных блоков, конвейера, блока с плавающей точкой будут оценены.

Answer 1

Критический путь - это самый длинный путь через график, в этом случае восемь часов. Это то, что Dragon Book должен сказать о критических путей (10.3.3 Топологические Приоритетные Orders):

Без ограничений ресурсов, кратчайшим график задается критического пути, самый длинный путь через данных графе зависимостей , A метрикой, полезной в качестве приоритетной функции, является высота узла, которая является длиной самого длинного пути в графе, исходящим от узла .

Я думаю, вы нашли ошибку в книге. Вам следует обратиться к авторам, чтобы они могли исправить его в будущих печатных изданиях.

Answer 2

Критический путь действительно 8 циклов, но вопрос задает CPE, который похож на усредненное по времени время для вывода еще одного цикла цикла.

За исключением первого и последнего циклов, процессор может выполнять добавление от предыдущей итерации цикла и текущих умножений одновременно, поскольку операнды не зависят друг от друга. Первая итерация цикла занимает всего 8 циклов, но после всех итераций цикл занимает всего 5 циклов, что делает фактические циклы CPE 5.

P.S.Я согласен с тем, что способ публикации книги критическим путем запутан. Их определение критического пути - это не просто путь, который занимает самый длинный путь, но путь также должен иметь операции с операндами, которые зависят от предыдущих операций и поэтому должны быть в порядке. Это определение делает поиск критического пути скорее неинтуитивным.

Answer 3

Я знаю, что я немного опоздал на вечеринку, но книга абсолютно правильная. Поскольку вы можете проверить себя, указав код, CPE действительно 5, поэтому второй ответ неверен.

Но первый тоже ошибочен. В нем говорится, что MUL должны выполняться одновременно, что совсем не возможно в архитектуре Nehalem (и я подозреваю, что большинство современных процессоров). Помните, что есть только один блок FP MUL и блок отличается FP ADD (как показано в книге, изд 2011 и позже.)

Что происходит вместо этого заключается в следующем:

(Нагрузка предполагается всегда присутствует, только 1 цикл, если в кеше)

Сначала мы кормим xpwr *= x в MUL. Сразу же после этого мы кормим xpwr*a[i] (вспомним трубопровод!)

... после 5 циклов мы получим новое значение xpwr, и после 6 циклов мы будем иметь результат xpwr*a[i]. В этот момент новое вычисление xpwr *= x будет на этапе 1 MUL. Таким образом, у нас есть еще 4 цикла, в которых нужно делать остальные операции, если мы не хотим их ограничивать.

Конечно, это легко, потому что нам нужно всего 3 цикла для FP ADD, чтобы получить новый result.

Итак, становится очевидным, что предельным фактором является вычисление xpwr. Это означает, что при поиске критического пути (что бы это ни было) мы должны смотреть конкретно на путь от старых значений к новым. В этом случае путь для result состоит только из одного FP ADD! (это то, что меня тоже сбило)

Answer 4

A1: Критический путь является самым длинным в графике потока данных в соответствии с книгой, который должен быть на прямой и имеет влияние на один регистр, а чем добавить «mul» и «add», результаты которых являются только промежуточными операндами для следующих операций.

Об этом вопросе вы получите все, чтобы продолжить чтение. В частности, полезно сравнить график потока данных comb7 и comb5.

A2: Если A1 понимается, вопрос 2 ясен, ответ в книге разумный.