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



Авторы специализируются на тестах по любым дисциплинам! Средний балл по тестам 4,6.
 
Любые вопросы по дистанционному обучению. Тесты, письменные работы, сессия под ключ.
 
Известный интернет сайт, помощь по любым учебным вопросам - от теста до дипломной работы. Личный менеджер.
 
Крупная биржа студенческих работ. Закажи напрямую у преподавателя. Низкие цены, стена заказов.
 

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

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

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

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