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

Упражнение 1:

Номер 1

В длинном командном слове процессора 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

Ответ:

(1) 26 тактов

(2) 27 тактов

(3) 30 тактов

Номер 2

В длинном командном слове процессора 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}

План выполнения программы
α₁=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

Ответ:

(1) 28 тактов

(2) 27 тактов

(3) 30 тактов

Номер 3

В длинном командном слове процессора 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 = {10, 1, 2, 3, 4, 6, 5, 10}

План выполнения программы
α₁=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

Ответ:

(1) 28 тактов

(2) 27 тактов

(3) 32 такта

(4) нет верного ответа

Упражнение 2:

Номер 1

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

Ответ:

(1) 22 такта

(2) 23 такта

(3) 24 такта

Номер 2

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

Ответ:

(1) 20 тактов

(2) 23 такта

(3) 21 такт

Номер 3

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

Ответ:

(1) 23 такта

(2) 18 тактов

(3) 22 такта

Упражнение 5:

Номер 1

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

Ответ:

(1) возможна для фиксированной и одинаковой длины массивов

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

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

(4) применение модифицированной "пузырьковой" сортировки дает максимальный эффект и исключает любые поиски повышения эффективности программного кода

Номер 2

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

Ответ:

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

(2) не уменьшается, т.к. регулярность алгоритма инвариантна относительно длины массива

(3) уменьшается незначительно

Номер 3

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

Ответ:

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

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

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

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

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