Почему программа достигает предела пропускной способности при коэффициенте развертывания k›C*L?

Я читаю «Компьютерные системы: взгляд программиста», 3/E (CS:APP3e), Рэндал Э. Брайант и Дэвид Р. О'Халларон.

Автор говорит:

«В общем, программа может достичь пропускной способности, связанной с операцией, только тогда, когда она может поддерживать заполнение конвейеров для всех функциональных блоков, способных выполнять эту операцию. Для операции с задержкой L и емкостью C требуется коэффициент развертывания k ≥ C · L. Например, умножение с плавающей запятой имеет C = 2 и L = 5, что требует коэффициента развертывания k ≥ 10. Сложение с плавающей запятой имеет C = 1 и L = 3, максимальная производительность достигается при k ≥ 3 ."

Почему это работает? Несмотря на то, что пропускная способность равна 1,00, это указывает только на то, что каждый цикл начинается новая операция. (Задержка 3,00, проблема 1,00.)

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

3 цикла - 1 сложение, но каждый цикл начинается новая операция, через 3 цикла завершается только первое сложение, через 4 цикла второе, через 5 циклов третье. Итак, мы получаем 3 операции за 5 тактов для полностью конвейерной обработки вместо 3 операций за 9 тактов (не полностью конвейерной). Является ли мое понимание полностью конвейерной единицы неправильным?

В чем причина k=10? Даже если есть 2 единицы, каждая итерация должна ждать, пока не будут вычислены самые последние 2 операции (т.е. 10 умножений, но итерация должна ждать до завершения последних 2 операций), поэтому нет причин для развертывания.

Возможно, программа выполняется не в последовательном порядке (я имею в виду, что процессор не дожидается окончания каждой итерации из-за предсказания ветвлений?)

/* разворачивание цикла 2 x 2 */

void combine6(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }

    /* Finish any remaining elements */
    for (;i < length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;
}

person Igor    schedule 22.08.2019    source источник
comment
Вы не имеете в виду 5 циклов для третьего? Для 3-этапного конвейера вы можете выполнять N операций за N+2 тактов.   -  person stark    schedule 22.08.2019
comment
@stark Да, ты прав!   -  person Igor    schedule 22.08.2019


Ответы (1)


По мере увеличения длины вектора все эти утверждения становятся все ближе и ближе к истине. Теоретически границы достигаются для вектора бесконечной длины, когда время запуска и остановки конвейера, деленное на общее время обработки, равно нулю. Авторы для простоты предполагают, что это время незначительно по сравнению с общим временем обработки в их тестах.

person Anton    schedule 24.08.2019