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

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

Номер 1

На каких уровнях практически реализуется распараллеливание вычислений в сверхпроизводительных ВС?

Ответ:

(1) на первом уровне программы распределяются между процессорами для параллельного выполнения. На втором уровне команды программы распределяются между исполнительными устройствами процессора

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

(3) на первом уровне по выполняемой программе загружаются процессорные элементы. На втором уровне специализированные процессорные элементы выполняют скалярные и векторные операции

Номер 2

Сколько и в каких комбинациях фигурируют потоки команд и потоки данных при классификации архитектур ВС?

Ответ:

(1) используются все 4 возможные комбинации: ОКОД, характеризующая традиционные "скалярные" процессоры; ОКМД, характеризующая векторные, матричные и другие процессоры с многими исполнительными устройствами; МКОД, характеризующая векторно-конвейерный способ выполнения операций или конвейерный способ выполнения программ; МКМД, характеризующая многопроцессорные ВС

(2) используются все 4 возможные комбинации: SISD, характеризующая микропроцессоры INTEL; SIMD, характеризующая матричные ВС; MISD, характеризующая векторные и векторно-конвейерные системы; MIMD, характеризующая мультимикропроцессорные системы

(3) используются 4 возможные комбинации: ОКОД (SISD), характеризующая "скалярные" процессоры; ОКМД (SIMD), характеризующая векторные, матричные и векторно-конвейерные ВС; МКОД (MISD), характеризующая потоковую (data flow) архитектуру; МКМД (MIMD), характеризующая многопроцессорные ВС на общей оперативной памяти

Номер 3

 Чем отличаются векторные вычислительные системы от векторно-конвейерных?

Ответ:

(1) и те, и другие обрабатывают массивы данных, но первые – параллельно, а вторые – последовательно

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

(3) векторные системы относятся к типу ОКМД, а векторно-конвейерные - к типу МКОД

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

Номер 1

Пусть в трехадресной системе команд КОП А₁ А₂ А₃   КОП – код операции, А₁ и А₂ - адреса операндов, А₃ – адрес результата. Каждая операция выполняется за одну условную единицу времени, допуская использование результата в следующей команде. Написать программу и определить  время ее параллельного выполнения для данного выражения, считая, что команды выполняются по схеме data flow, т.е. тотчас же, как только для них окажется рассчитанной информация, и при условии, что для их выполнения всегда есть свободные процессоры. P=(x+y)×z+(p+q):l

Ответ:

(1) 2 единицы времени

(2) 3 единицы времени

(3) 4 единицы времени

Номер 2

Пусть в трехадресной системе команд КОП А₁ А₂ А₃ КОП – код операции, А₁ и А₂ – адреса операндов, А₃ – адрес результата. Каждая операция выполняется за одну условную единицу времени, допуская использование результата в следующей команде. Написать программу и определить  время ее параллельного выполнения для данного выражения, считая, что команды выполняются по схеме data flow, т.е. тотчас же, как только для них окажется рассчитанной информация, и при условии, что для их выполнения всегда есть свободные процессоры.  P=(x+y+z)×p+(q+l)×m

Ответ:

(1) 2 единицы времени

(2) 3 единицы времени

(3) 4 единицы времени

Номер 3

Пусть в трехадресной системе команд КОП А₁ А₂ А₃ КОП – код операции, А₁ и А₂ – адреса операндов, А₃ – адрес результата. Каждая операция выполняется за одну условную единицу времени, допуская использование результата в следующей команде. Написать программу и определить  время ее параллельного выполнения для данного выражения, считая, что команды выполняются по схеме data flow, т.е. тотчас же, как только для них окажется рассчитанной информация, и при условии, что для их выполнения всегда есть свободные процессоры.  P= (x×y+z)+(p+q)×(l+m)

Ответ:

(1) 2 единицы времени

(2) 3 единицы времени

(3) 4 единицы времени

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

Номер 1

Проанализируйте пример программы счета значения Q=ab+cd  и напишите программу для ВС типа data flow. Пример.
        Команды Пояснение
1 Сч a   5,1 Считать а, послать в команду 5 первым операндом
2 Сч b 5,2 Считать b, послать в команду 5 вторым операндом
3 Сч c 6,1 
4 Сч d 6,2 
5 × 7,1 Умножить после поступления операндов
6 × 7,2 
7 + <Q> 
Q=(a+b)×c
Приведите текст пятой команды

	Команды	Пояснение
1	Сч	a	5,1	Считать а, послать в команду 5 первым операндом
2	Сч	b	5,2	Считать b, послать в команду 5 вторым операндом
3	Сч	c	6,1
4	Сч	d	6,2
5	×		7,1	Умножить после поступления операндов
6	×		7,2
7	+		<Q>

Ответ:

(1)

×

<Q>

(2)

Сч

5,2

(3)

+

5,1

Номер 2

Проанализируйте пример программы счета значения Q=ab+cd  и напишите программу для ВС типа data flow. Пример.
        Команды Пояснение
1 Сч a   5,1 Считать а, послать в команду 5 первым операндом
2 Сч b 5,2 Считать b, послать в команду 5 вторым операндом
3 Сч c 6,1 
4 Сч d 6,2 
5 × 7,1 Умножить после поступления операндов
6 × 7,2 
7 + <Q> 
Q=(a+b+c)×d
Приведите текст четвертой команды

	Команды	Пояснение
1	Сч	a	5,1	Считать а, послать в команду 5 первым операндом
2	Сч	b	5,2	Считать b, послать в команду 5 вторым операндом
3	Сч	c	6,1
4	Сч	d	6,2
5	×		7,1	Умножить после поступления операндов
6	×		7,2
7	+		<Q>

Ответ:

(1)

Сч

d

7,2

(2)

+

6,1

(3)

×

<Q>

Номер 3

Проанализируйте пример программы счета значения Q=ab+cd  и напишите программу для ВС типа data flow. Пример.
        Команды Пояснение
1 Сч a   5,1 Считать а, послать в команду 5 первым операндом
2 Сч b 5,2 Считать b, послать в команду 5 вторым операндом
3 Сч c 6,1 
4 Сч d 6,2 
5 × 7,1 Умножить после поступления операндов
6 × 7,2 
7 + <Q> 
Q=(a+b)×(c+d)Приведите текст шестой команды

	Команды	Пояснение
1	Сч	a	5,1	Считать а, послать в команду 5 первым операндом
2	Сч	b	5,2	Считать b, послать в команду 5 вторым операндом
3	Сч	c	6,1
4	Сч	d	6,2
5	×		7,1	Умножить после поступления операндов
6	×		7,2
7	+		<Q>

Ответ:

(1)

Сч

d

6,2

(2)

+

7,2

(3)

×

<Q>

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

Номер 1

Какое основное положение легло в основу принципа data flow?

Ответ:

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

(2) следует эффективно динамически загружать работами все исполнительные устройства системы

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

Номер 2

Почему идеальная схема data flow не нашла практического воплощения?

Ответ:

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

(2) из-за сложности программирования

(3) из-за сложности организации циклов, ветвления, индексации массивов и повторной входимости

Номер 3

 Почему схема data flow относится к "не-фон-Неймановским" архитектурам?

Ответ:

(1) из-за отсутствия счетчика команд, характеризующего ранние "классические" модели ЭВМ

(2) потому что Фон Нейман ее не разрабатывал

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

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

Номер 1

Почему в схеме матричного коммутатора для ВС с распределенной памятью отсутствуют ключи на некоторых пересечениях шин?

Ответ:

(1) это ошибка

(2) самому с собой через коммутатор соединяться не следует

(3) так устраняется перегрузка шин

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

Номер 1

Рассмотрите схему обработки области матрицей процессоров и объясните, почему, организуя регулярные оперативные связи, целесообразно соединить первые и последние процессоры в строках и столбцах?

Ответ:

(1) при счете методом сеток единичное перемещение матрицы процессоров вдоль строк области приводит к тому, что последний обработанный узел становится левым соседом левого процессора матрицы. Это позволяет сохранить регулярный порядок обработки узлов. Аналогично – при перемещении матрицы процессоров вдоль столбцов

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

(3) чтобы сохранить постоянное число связей каждого процессора

Номер 2

Пусть метод сеток использует рекуррентное отношение, связывающее значения функции-решения в соседних узлах:
f_ij = F(f_i,j-1, f_i,j+1, f_i-1,j, f_i+1,j)
Размер области 10 × 6 (m×n) узлов. Размер матрицы процессоров 4 × 4. Представьте схему двукратного обхода области процессорами, исключая границы, где функция задана.
Сколько узлов пришлось обработать каждому процессору?

Ответ:

(1) 4 узла

(2) 12 процессоров обработали 4 узла, а 4 – только 2

(3) 3 узла

Номер 3

Пусть метод сеток использует рекуррентное отношение, связывающее значения функции-решения в соседних узлах:
f_ij = F(f_i,j-1, f_i,j+1, f_i-1,j, f_i+1,j)Размер области 12 × 6 (m×n) узлов. Размер матрицы процессоров 4 × 4. Сколько узлов пришлось обработать каждому процессору матрицы при двукратном обходе области, считая, что по узлам производится циклическая переадресация по mod m и по mod n

Ответ:

(1) 5 узлов

(2) 4 узла

(3) 12 процессоров обработают 5 узлов, остальные – по 4

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