Защо програмата постига ограничението за пропускателна способност, като се има предвид коефициент на разгръщане k›C*L?

Чета Computer Systems: A Programmer's Perspective, 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