Сортировка сетей по затратам и задержкам

Question

Из того, что я прочитал, я не мог понять, как рассчитывается стоимость и задержка.

• Стоимость: количество палочек или блоков сравнения-обмена.
• Задержка: количество сравнений-обменов в последовательности.

Я разместил свой пример ниже

Answer 1

Из того, что я вижу, ваш ответ правильный.

Стоимость - это общее количество сравнительных обменов, выполненных в сортировочной сети. Я считаю, что здесь 28.

Задержка - это количество этапов, которые должны быть выполнены последовательно, то есть иметь зависимости данных. В примере есть задержка 13.

Почему мы заботимся о разнице? Стоимость представляет собой объем работы, которую мы должны выполнить в последовательной реализации, однако преимущество использования сети сортировки состоит в том, что многие операции сравнения-обмена могут выполняться параллельно. Когда у вас есть столько параллелизма, сколько имеется сравнений-обменов на одном этапе, вы можете рассчитать этот этап одновременно.

В идеально параллельной системе задержка алгоритма будет зависеть от задержки, а не от стоимости. В полностью последовательной системе задержка будет связана с затратами, а не с задержкой.