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

Каковы принципы организации распределенной памяти с единым адресным пространством в мультипроцессорной системе?

• все адресное пространство делится на области, соответствующие отдельным процессорам. Однако если один процессор обратился по адресу памяти другого процессора, то обмен производится с помощью специальной процедуры ОС
• единое адресное пространство означает одинаковую для всех процессоров адресацию распределенной памяти
• (Правильный ответ) единое адресное пространство делится на области; каждая область отображает адресное пространство соответствующего процессора. Если один процессор использует адрес памяти другого процессора, то автоматически инициируется обмен, который нет необходимости предусматривать программно

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

• произойдет прерывание из-за недопустимости подобной структуры
• произойдет прерывание по зацикливанию
• (Правильный ответ) базовый регистр В1 «смотрит» на область активации процедуры А. После повторного запуска рекурсивной процедуры А на ее новую область активации будет «смотреть» базовый регистр В2 и т.д. Последний, п-й, запуск процедуры А должен довершить ее выполнение. То есть, в ней запустится процедура С, на область активации которой будет «смотреть» тот же базовый регистр Вn. Далее продолжится выполнение процедуры А предыдущего запуска, на область активации которой «смотрит» базовый регистр Вn-1. В ней запустится процедура С, на область активации которой будет «смотреть» тот же базовый регистр и т.д

Для данного арифметического выражения составьте программу в безадресной системе команд и для автоматического распараллеливания переведите ее в трехадресную систему команд. Длина списка свободных регистров равна 6. A=(a+b)ЧcЧ(d+e). Какова длина программы в трехадресных командах? Приведите текст седьмой команды

• 8 команд,+ r6 r1 r2
• (Правильный ответ) 9 команд,Сч e r1
• 10 команд,Сч d r6

Пусть задан «гиперкубовый» адрес процессорного элемента ПЭ0. Сформируйте плоскую решетку из ПЭ четырехмерного гиперкуба так, чтобы между всеми соседними ПЭ существовали оперативные связи по строкам и по столбцам, а также, чтобы первый в строке и в столбце был связан с последним. «Гиперкубовый» адрес ПЭ0 равен 0010

• (Правильный ответ)

АЛУ содержит два ИУ сложения, два – умножения, два канала обмена с памятью. Сложение выполняется за 2 такта, умножение – за 3. Все элементы массива A = {a1, a2,…} находятся по одной формуле. Составьте оптимальную программу одновременного вычисления двух элементов массива. aj=bjЧc+ d

• + + Ч Ч Заn Заn

bjcbj+1c NOP NOP +d+d Заn ajЗаn aj+1

• + + Ч Ч Заn Заn

bjcbj+1c NOP NOP +d+d NOP NOP Заn ajЗаn aj+1

• (Правильный ответ)+ + Ч Ч Заn Заn

bjcbj+1c NOP NOP +d+d NOP Заn ajЗаn aj+1

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

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

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

• потому что Фон Нейман ее не разрабатывал
• потому что одно «узкое место» — счетчик команд заменено другим «узким местом» — коммуникационной сетью ВС, где проблему достижения высокой производительности обмена удается эффективно решить
• (Правильный ответ) из-за отсутствия счетчика команд, характеризующего ранние «классические» модели ЭВМ

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

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

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

1Чabv12+v1v3v23Чv2ev31+dfv12:v1Lv23Чv2kv3

• (Правильный ответ)1

Чab(1,1)2+(1,1)(3,1)(4,1)3Ч(4,1)e(3,1)1+df(2,1)2:(2,1)L(1,2)3Ч(1,2)k(2,2)

• 1

Чab(1,1)2+(1,1)(3,1)(4,1)3Ч(4,1)e(1,2)1+df(2,1)2:(2,1)L(1,2)3Ч(1,2)k(2,2)

• 1

Чab(1,1)2+(1,1)(3,1)(3,1)3Ч(4,1)e(3,1)1+df(2,1)2:(4,1)L(1,2)3Ч(1,2)k(2,2)

С помощью пятиадресной команды if-then-else составьте программу коммутации для счета значения выражения:

X = bЧif (d+ c) >a then if e >b then A else B else 0

• (Правильный ответ)1

+dc(1,1)2УСЛeb(2,1) AB 3УСЛ(1,1)a(3,1) (2,1)0 4Чb(3,1)(4,1)

• (Правильный ответ)1

УСЛeb(1,1) AB 2+dc(2,1)3УСЛ(2,1)a(3,1) (2,1)0 4Чb(3,1)(4,1)

• (Правильный ответ)1

+dc(1,1)2УСЛ(1,1)a(3,1) (2,1)0 3УСЛeb(2,1) AB 4Чb(3,1)(4,1)

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

• (Правильный ответ) самому с собой через коммутатор соединяться не следует
• это ошибка
• так устраняется перегрузка шин

Составьте схему программы умножения n чисел массива методом «пирамиды». Сколько тактов, без формирования цикла, потребуется на ее выполнение после начального считывания данных? n = 7

• (Правильный ответ) 3 такта
• 5 такта
• 4 такта

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

• (Правильный ответ) по предварительной команде с адреса перехода запускается второй конвейер выполнения команд. Оба конвейера работают в спекулятивном режиме до формирования значения условия перехода. Затем ненужный конвейер отвергается
• (Правильный ответ) буфер команд выполнен в ассоциативной памяти, что обеспечивает быстрое переключение на анализ команд, начиная с адреса перехода. Это позволяет быстро запустить второй конвейер по предварительной команде условного перехода
• используется условный переход по предпочтению
• вычислительный процесс прерывается до формирования значения условия перехода

Предполагая механизм использования бита значимости регистров r СОЗУ, уплотните код фрагмента программы счета арифметического оператора на процессоре с программным управлением каждым тактом. Программа составлена в трехадресных командах. b= a+ c

• (Правильный ответ) Сч a r1Сч с r2+ r1r2
• Сч a r1Сч с r2{пропуск тактов в ожидании считывания}+ r1r2b
• Сч a r1 {пропуск тактов в ожидании считывания}Сч с r2{пропуск тактов в ожидании считывания}+ r1 r2b

Предполагая механизм использования бита значимости регистров r СОЗУ, уплотните код фрагмента программы счета арифметического оператора на процессоре с программным управлением каждым тактом. Программа составлена в трехадресных командах. a = a+ b

• (Правильный ответ) Сч a r1Сч b r2+ r1 r2 a
• Сч a r1 {пропуск тактов в ожидании считывания}Сч b r2{пропуск тактов в ожидании считывания}+ r1r2 a
• Сч a r1Сч b r2{пропуск тактов в ожидании считывания}+ r1 r2 a

Составьте граф-схемы выполнения операций свертки массива длины m и сделайте разметку: какому из n процессоров какая операция достанется при выполнении монопрограммы. Рассмотрите операцию нахождения максимального элемента массива при m=4, n=6

• (Правильный ответ)

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {?} логических высказываний на базе системы аксиом {?}={?0,?1,b2,b3,c4,c5}. Система аксиом ?0??b2,?0??b3,?1??b3,b2??c4,b3??c5

• №

Логические цепочкиПродленная цепочкаФормирующий процессорОбрабатывающий процессор1?0??b2 02?0??b3 13?1??b3 04?0??b2??с41015?1??b3??с52106?0??b3??с5301

• (Правильный ответ)№

Логические цепочкиПродленная цепочкаФормирующий процессорОбрабатывающий процессор1?0??b2 02?0??b3 13?1??b3 04?0??b2??с41015?0??b3??с52106?1??b3??с5301

• №

Логические цепочкиПродленная цепочкаФормирующий процессорОбрабатывающий процессор1?0??b2 12?0??b3 03?1??b3 14?0??b2??с41115?0??b3??с52106?1??b3??с5301

Ответьте на вопросы обоснования методов компоновки «длинных» командных слов (широкой команды — по другой терминологии) в архитектурах ВС, управляемых в каждом такте. Проведите обоснование выполнения компоновки «длинных» командных слов внутри непрерываемых участков программы

• глобальную компоновку всей программы целесообразно разбить на элементарные шаги, результаты выполнения которых остаются неизменными, т.к. «логика» вносит значительный элемент неопределенности
• задача глобальной оптимизации программ столь сложна, что требует разбиения на частные задачи по принципу «разделяй и властвуй»
• (Правильный ответ) в современном суперскаллере альтернативное выполнение частных работ в составе арифметических операторов, благодаря операциям if-then-else и памяти предикатов, оказывается погруженным в линейные (непрерываемые) участки программы. Условные и процедурные переходы в таком случае в большей степени характеризуют структуру программы и требуют других уровней и средств оптимизации
• компоновка «длинных» командных слов в составе линейного участка программы требует столь специфических средств распараллеливания, что выдвигается в отдельную трудно решаемую проблему

На основе систолической матрицы операцию умножения двух 16-разрядных кодов можно свести к четырем умножениям 8-разрядных кодов по схеме, показанной на примере: А692 ВС34 = (А600ВС00) + (А500 34) + (92 ВС00) + (92 34). Загружая конвейер четыре такта подряд (в процессе умножения векторов с длиной, равной четырем), необходимо на его выходе обеспечить накопление результата в соответствии с относительным смещением промежуточных результатов. Составьте проект универсального параллельного конвейера АЛУ, реализующего операции сложения и умножения 16-разрядных кодов на систолической матрице процессорных элементов, основной операцией которых является сложение 8-разрядных чисел. Каковы должны быть размеры систолической матрицы для выполнения этих двух операций? Составьте временную диаграмму выполнения последовательности двух операций и определите задержку начала выполнения второй операции. Последовательно выполняются операции:

1. a b = c2. c + d = f

• задержка 5 тактов
• задержка 3 такта
• (Правильный ответ) задержка 7 тактов

Составьте матрицу следования для информационного графа. Каким значением времени ограничена минимальная длина расписания при распределении работ между тремя процессорами?

• (Правильный ответ) 7 единиц времени
• 6 единиц времени
• 9 единиц времени

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

1+abv12—ecv23Чv2v1v31+dfv12:kLv23Чv2v1v3

• 1

Чab(1,1)2—ec(2,1)3Ч(3,1)(1,1)(1,2)1+df(1,2)2:kL(2,2)3Ч(3,1)(2,1)(2,2)

• 1

Чab(1,1)2—(1,1)c(3,1)3Ч(3,1)e(1,2)1+df(2,1)2:(2,1)L(3,1)3Ч(3,1)k(2,2)

• (Правильный ответ)1

+ab(1,1)2—ec(3,1)3Ч(3,1)(1,1)(1,2)1+df(2,1)2:kL(4,1)3Ч(4,1)(2,1)(2,2)

Произведите распараллеливание счета арифметических операторов, содержащих конструкции if-then-else, убедившись в правильной начальной загрузке и связывания подстеков. Сдвиг во времени загрузки подстеков не учитывать. Продолжите вычисления и определите количество тактов счета по разным ветвям программы. a+ if b+c > 0 then d: 5 else d: 20

• 2 такта по ветви «+», 3 такта по ветви «-«
• (Правильный ответ) 3 такта по двум ветвям
• 4 такта по двум ветвям

Задан трехмерный массив A[0:10; 0:10; 0:10]. Адрес начала равен 10 (в десятичной системе счисления). Найдите адрес элемента a[5, 5, 5].

• 612
• (Правильный ответ) 675
• 565

Составьте план сложения способом «пирамиды» всех т элементов массива с помощью заданного количества п процессоров. Требуется ли синхронизация процессоров, чтобы не использовать еще не полученные данные? m = 8, n = 5

• (Правильный ответ) да, пятому процессору в первом цикле, второму во втором цикле
• нет
• да, пятому процессору в первом цикле

Для выражения

Z:=c+bx+ax2 составьте матрицу следования работ и укажите значения времени их выполнения, поздних сроков начала их выполнения (для Т = 6), а также объема последующих работ

• Операция

Матрицаt??bx 214ax 225c+bx11 142ax2 1 233Z 11151

• Операция

Матрицаt??bx 224ax 225c+bx1 132ax2 1 233Z 11151

• (Правильный ответ)Операция

Матрицаt??bx 224ax 215c+bx1 142ax2 1 233Z 11151

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

• (Правильный ответ) по команде «закрыть адрес» запрещается считывание по этому адресу и запись того процессора, который этот адрес не закрывал. При обращении к закрытому адресу процессор работает в режиме «жужжания» до записи по этому адресу процессором, закрывшим его
• по закрытому адресу запрещается запись, но разрешается считывание. Запись любого процессора по этому адресу открывает его
• по закрытому адресу запрещается считывание, пока какой-либо процессор не произведет запись

Проанализируйте способы ускорения выполнения операций управления в процессорах высокопроизводительных вычислительных систем. Как минимизируется время выполнения циклов?

• (Правильный ответ) время выполнения цикла типа арифметической прогрессии сокращается при использовании элемента цикла. Он содержит счетчик цикла, граничное значение и адрес начала. Цикл также отмечается командой «конец цикла». Цикл типа пересчет поддерживается средствами организации условного перехода
• средства поддержки условного перехода обеспечивают и возможный минимум времени выполнения цикла
• время выполнения цикла минимизируется с помощью элемента цикла и средств поддержки условного перехода

Задан трехмерный массив A[0:10; 0:10; 0:10]. Адрес начала равен 10 (в десятичной системе счисления). Найдите адрес элемента a[4, 3, 4].

• 444
• 492
• (Правильный ответ) 531

Какие операторы из приведенных последовательностей могут быть выполнены одновременно?

1. a := x22. b := a+b3. a : =aЧc

• операторы 1 и 3
• (Правильный ответ) операторы 2 и 3, после изменения имени присваивания а в третьем операторе
• операторы 1 и 2

Для архитектуры с синхронными ИУ составить оптимальную программу счета значения выражения и составить временную диаграмму выполнения работ, считая время умножения вдвое большим времени сложения. Определить минимальную длину расписания.

Y:=ax2+bx+c

• КОП

R1R2R3/AКОПR1R2R3/AКОПR1R2R3/AЧaxr1Чbxr2Чr1xr1+r1r2r3+r3cY Минимальная длина расписания равна 6

• (Правильный ответ)КОП

R1R2R3/AКОПR1R2R3/AКОПR1R2R3/AЧaxr1Чbxr2 Чr1xr3+r2cr4+r3r4Y Минимальная длина расписания равна 5

• КОП

R1R2R3/AКОПR1R2R3/AКОПR1R2R3/AЧxxr1Чbxr2 Чar1r1+r1r2r3+cr3Y Минимальная длина расписания равна 6  

Составьте схему программы умножения n чисел массива методом «пирамиды». Сколько тактов, без формирования цикла, потребуется на ее выполнение после начального считывания данных? n = 5

 

• 4 такта
• (Правильный ответ) 3 такта
• 2 такта

 

Предполагая механизм использования бита значимости регистров r СОЗУ, уплотните код фрагмента программы счета арифметического оператора на процессоре с программным управлением каждым тактом. Программа составлена в трехадресных командах. a= b2c

 

• Сч b r1 Сч с r2 {пропуск тактов в ожидании считывания}Ч r1 r2 r3.Ч r2 r3 a
• Сч b r1 {пропуск тактов в ожидании считывания}Сч с r2 {пропуск тактов в ожидании считывания}Ч r1 r2 r3.Ч r2 r3 a
• (Правильный ответ) Сч b r1Сч с r2 Ч r1 r2 r3.Ч r2 r3 a

 

Не пользуясь индексными регистрами, схематично, на уровне блок-схемы, где блок отображает одну команду, составьте план монопрограммы сложения m элементов массива на ВС SPMD-архитектуры, содержащей 4 процессора. m=6

 

• (Правильный ответ)

 

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

 

• (Правильный ответ) включение команды в состав «длинного» командного слова определяется предпочтительным рядом критериев: максимум времени выполнения, минимум максимального времени начала выполнения, максимум объема последующих работ
• полное отсутствие подобных критериев (назначение в порядке следования при анализе потока команд) сокращает время трансляции, не приводя на практике к значительному снижению качества программы
• в большинстве случаев достаточно пользоваться критерием назначения по максимальному времени выполнения операций
• включение команды в состав «длинного» командного слова определяется предпочтительным рядом критериев: минимум максимального времени начала выполнения, максимум времени выполнения, максимум объема последующих работ

 

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

План выполнения программы     ?1=10?2?2=8?5?3=7?1?4=3?5NOP?1: 2, 10?2: 5, 8?3: 1, 7?4: 3, 5NOP?1=10?5?2=8?1?3=7?3 NOP?1: 5, 10?2: 1, 8?3: 3, 7 NOP?1=2?5?2=10?1?3=8?3?4=7?5NOP?1: 2, 5?2: 1, 10?3: 3, 8?3: 5, 7NOP?1=5?1?2=10?3?3=8?5 NOP?1: 1, 5?2: 3, 10 <t