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



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

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

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

  • произойдет прерывание из-за недопустимости подобной структуры
  • произойдет прерывание по зацикливанию
  • (Правильный ответ) базовый регистр В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