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

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

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

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

Вместо этого происходит следующее:

(Предполагается, что НАГРУЗКИ всегда присутствуют, только 1 цикл, если в кеше)

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

За одну итерацию параллельно выполняются три операции:

• result += PREV, куда PREVравно a[i] * xwpr, который был рассчитан в предыдущей итерации , требующий сложения с плавающей запятой (3 такта).
• a[i] * xpwr, значение которого будет использоваться в следующей итерации , требующей умножения с плавающей запятой (5 тактов).
• xpwr * x, значение которого будет использоваться в следующей итерации , требующей умножения с плавающей запятой (5 тактов).

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

Они не обязательно запускаются в одном и том же тактовом цикле (и на самом деле они не могут все, потому что ЦП не имеет 3 исполнительных блоков FP), но один может начаться до завершения другого, поэтому их задержки могут перекрываться. Они находятся в полете одновременно, в конвейерных исполнительных модулях FP.

Answer 5

Критический путь - это самый длинный путь в графе, в данном случае восемь часов. Вот что говорит Книга Дракона о критических путях (10.3.3 Приоритетные топологические заказы):

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

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