Архитектура параллельных вычислительных систем

Рассмотрите возможности оптимизации программы сортировки. Назовите основные достоинства и недостатки спекулятивных вычислений при решении задачи сортировки массивов

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

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

они позволяют избавиться от условных переходов, значительно увеличивающих время сортировки(Верный ответ)

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

динамическое выделение выполняемой ветви программы не обеспечивает преимущества во времени по сравнению с явным применением команд условного перехода

Похожие вопросы

Рассмотрите возможности оптимизации программы сортировки. Возможна ли более компактная запись программы (с минимальным количеством NOP) при одновременной сортировке двух массивов?

Рассмотрите возможности оптимизации программы сортировки. Уменьшается ли суммарное время простоя оборудования (в частности, количество NOP) при увеличении длины сортируемого массива?

Рассмотрите способы оптимизации загрузки процессоров, применение которых становится возможным в ВС SPMD-архитектуры с малыми накладными расходами на организацию параллельных вычислений. Какие возможности для оптимизации загрузки процессоров предоставляют дескрипторы массивов

Рассмотрите способы оптимизации загрузки процессоров, применение которых становится возможным в ВС SPMD-архитектуры с малыми накладными расходами на организацию параллельных вычислений. Зачем в базе знаний хранятся все промежуточные варианты построения логических цепочек?

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

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

В длинном командном слове процессора EPIC-архитектуры присутствуют инструкции четырем логическим ИУ. Инструкция имеет вид КОП А₁ А₂ α, где А₁ и А₂ – адреса операндов, α - адрес предиката – логического значения. Среди исполняемых инструкций есть команда сравнения (А₁)≤(А₂) с выработкой результата (α) и команда перестановки (А₁) => А₂, А₂ <= (А₁), выполняемая в спекулятивном режиме в зависимости от значения (a). Результат логической операции можно использовать через один такт.Разверните во времени цикл и составьте план выполнения программы модифицированной "пузырьковой" сортировки данного массива. Определите количество тактов вычислений.Пример. M = {10, 2, 8, 5, 7, 1, 3, 5}.

План выполнения программы
α₁=10≤2	α₂=8≤5	α₃=7≤1	α₄=3≤5
NOP
α₁: 2, 10	α₂: 5, 8	α₃: 1, 7	α₄: 3, 5
NOP
α₁=10≤5	α₂=8≤1	α₃=7≤3
NOP
α₁: 5, 10	α₂: 1, 8	α₃: 3, 7
NOP
α₁=2≤5	α₂=10≤1	α₃=8≤3	α₄=7≤5
NOP
α₁: 2, 5	α₂: 1, 10	α₃: 3, 8	α₃: 5, 7
NOP
α₁=5≤1	α₂=10≤3	α₃=8≤5
NOP
α₁: 1, 5	α₂: 3, 10	α₃: 5, 8
NOP
α₁=2≤1	α₂=5≤3	α₃=10≤5	α₄=8≤7
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 10	α₄: 7, 8
NOP
α₁=2≤3	α₂=5≤5	α₃=10≤7
NOP
α₁: 2, 3	α₂: 5, 5	α₃: 7, 10
NOP
α₁=1≤2	α₂=3≤5	α₃=5≤7	α₄=10≤8
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 7	α₄: 8, 10

Переносы прекратились через 27 тактов.

M = {3, 5, 3, 6, 5, 8, 6, 4}

В длинном командном слове процессора EPIC-архитектуры присутствуют инструкции четырем логическим ИУ. Инструкция имеет вид КОП А₁ А₂ α, где А₁ и А₂ – адреса операндов, α - адрес предиката – логического значения. Среди исполняемых инструкций есть команда сравнения (А₁)≤(А₂) с выработкой результата (α) и команда перестановки (А₁) => А₂, А₂<= (А₁), выполняемая в спекулятивном режиме в зависимости от значения (α). Результат логической операции можно использовать через один такт.Разверните во времени цикл и составьте план выполнения программы модифицированной "пузырьковой" сортировки данного массива. Определите количество тактов вычислений.Пример. M = {10, 2, 8, 5, 7, 1, 3, 5}.

План выполнения программы
α₁=10≤2	α₂=8≤5	α₃=7≤1	α₄=3≤5
NOP
α₁: 2, 10	α₂: 5, 8	α₃: 1, 7	α₄: 3, 5
NOP
α₁=10≤5	α₂=8≤1	α₃=7≤3
NOP
α₁: 5, 10	α₂: 1, 8	α₃: 3, 7
NOP
α₁=2≤5	α₂=10≤1	α₃=8≤3	α₄=7≤5
NOP
α₁: 2, 5	α₂: 1, 10	α₃: 3, 8	α₃: 5, 7
NOP
α₁=5≤1	α₂=10≤3	α₃=8≤5
NOP
α₁: 1, 5	α₂: 3, 10	α₃: 5, 8
NOP
α₁=2≤1	α₂=5≤3	α₃=10≤5	α₄=8≤7
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 10	α₄: 7, 8
NOP
α₁=2≤3	α₂=5≤5	α₃=10≤7
NOP
α₁: 2, 3	α₂: 5, 5	α₃: 7, 10
NOP
α₁=1≤2	α₂=3≤5	α₃=5≤7	α₄=10≤8
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 7	α₄: 8, 10

Переносы прекратились через 27 тактов

M = {3, 5, 3, 6, 5, 8, 6, 4}

План выполнения программы
α₁=10≤2	α₂=8≤5	α₃=7≤1	α₄=3≤5
NOP
α₁: 2, 10	α₂: 5, 8	α₃: 1, 7	α₄: 3, 5
NOP
α₁=10≤5	α₂=8≤1	α₃=7≤3
NOP
α₁: 5, 10	α₂: 1, 8	α₃: 3, 7
NOP
α₁=2≤5	α₂=10≤1	α₃=8≤3	α₄=7≤5
NOP
α₁: 2, 5	α₂: 1, 10	α₃: 3, 8	α₃: 5, 7
NOP
α₁=5≤1	α₂=10≤3	α₃=8≤5
NOP
α₁: 1, 5	α₂: 3, 10	α₃: 5, 8
NOP
α₁=2≤1	α₂=5≤3	α₃=10≤5	α₄=8≤7
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 10	α₄: 7, 8
NOP
α₁=2≤3	α₂=5≤5	α₃=10≤7
NOP
α₁: 2, 3	α₂: 5, 5	α₃: 7, 10
NOP
α₁=1≤2	α₂=3≤5	α₃=5≤7	α₄=10≤8
NOP
α₁: 1, 2	α₂: 3, 5	α₃: 5, 7	α₄: 8, 10

Переносы прекратились через 27 тактов.

M = {10, 1, 2, 3, 4, 6, 5, 10}

В длинном командном слове процессора EPIC-архитектуры присутствуют инструкции четырем логическим ИУ. Инструкция имеет вид КОП А₁ А₂ α, где А₁ и А₂ – адреса операндов, α - адрес предиката – логического значения. Среди исполняемых инструкций есть команда сравнения (А₁)≤(А₂) с выработкой результата (α) и команда перестановки (А₁) => А₂, А₂ <= (А₁), выполняемая в спекулятивном режиме в зависимости от значения (a). Результат логической операции можно использовать через один такт. Разверните во времени циклы и составьте план выполнения по тактам программы сортировки данного массива с помощью прямого включения. Найдите количество тактов вычислений. M = {1, 8, 2, 10}