Главная / Аппаратное обеспечение / Архитектура параллельных вычислительных систем

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

Правильные ответы выделены зелёным цветом.
Все ответы: Излагаются основные структурные решения, воплощённые в параллельных вычислительных системах и способствующие их высокой производительности. Изучаются основные популярные архитектуры. Исследуются принципы оптимизации выполнения параллельных программ.

Смотрите также:

Программирование

Суперкомпьютерные технологии

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

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

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

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

Пользуясь записью выражения в ПОЛИЗ, составьте программу коммутации счета его значения. Произведите предварительное преобразование записи для оптимизации программы. Решающее поле содержит 4 ПЭ. Определите длину программы. Сколько регистров буферов ПЭ используется? A = ((a + b)×(b + c))×((c + d)×(d+ e))

(1) 7 команд; используются по два регистра буферов ПЭ1, ПЭ2, ПЭ3 и один регистр буфера ПЭ4

(2) 6 команд; используются по два регистра буферов ПЭ1, ПЭ2, по одному регистру буферов ПЭ3, ПЭ4

(3) 8 команд; используются по два регистра каждого буфера

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

(1) 3 такта

(2) 2 такта

(3) 4 такта

Систематизируйте предпосылки, которые легли в основу ВС SPMD-архитектуры. Какие общие черты решаемых задач определили требования к SPMD-архитектуре?

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

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

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

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

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α} логических высказываний на базе системы аксиом {α}={α₀,α₁,b₂,b₃,c₄,c₅}. Система аксиом α₀→b₂,α₀→b₃,α₁→b₃,b₂→c₄,b₃→c₅

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			0
2	`α₀→b₃`			1
3	`α₁→b₃`			0
4	`α₀→b₂→с₄`	1	0	1
5	`α₀→b₃→с₅`	2	1	0
6	`α₁→b₃→с₅`	3	0	1

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			1
2	`α₀→b₃`			0
3	`α₁→b₃`			1
4	`α₀→b₂→с₄`	1	1	1
5	`α₀→b₃→с₅`	2	1	0
6	`α₁→b₃→с₅`	3	0	1

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			0
2	`α₀→b₃`			1
3	`α₁→b₃`			0
4	`α₀→b₂→с₄`	1	0	1
5	`α₁→b₃→с₅`	2	1	0
6	`α₀→b₃→с₅`	3	0	1

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

(1) превращение ПК в систему сверхвысокой производительности

(2) расширение диапазона эффективного решения задач: оптимизационных, транспортных, нейросетевых и др

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

Построить принципиальную схему трехуровневого конвейера выполнения операции сложения 16-разрядных кодов с помощью 8-разрядных сумматоров, запоминающих признак переполнения для переноса

(1) принципиальная схема имеет вид: files

(2) принципиальная схема имеет вид: files

(3) принципиальная схема имеет вид: files

Произведите распараллеливание выполнения на стеке программы в безадресной системе команд. Разное время начальной загрузки подстеков и время обмена между ними не учитывать. За сколько тактов выполнится параллельная программа, не считая записи результатов? Сколько процессорных элементов будет использовано? abc×+ de: f+ × ЗпА

(1) 4 такта, 2 ПЭ

(2) 3 такта, 3 ПЭ

(3) 2 такта, 4 ПЭ

Что произойдет, если в программе встретится запись данного вида?x := 0,5 "Считать Процедура sin(x)"

(1) текст процедуры запишется в буфер команд

(2) текст процедуры выводится на дисплей

(3) процедура выполнится, ее значение готово для дальнейшего использования в программе

Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта, деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:if a-b>0 then(c×d):f else c+e×f; B:=if(a>b∨c>b) then A×a else c+d

(1)

(2)

(3)

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

(1)

+	+	×	×	Заn	Заn
		b_jc	b_j+1c
		NOP
		NOP
+d	+d
		NOP
				Заn a_j	Заn a_j+1

(2)

+	+	×	×	Заn	Заn
		b_jc	b_j+1c
		NOP
		NOP
+d	+d
				Заn a_j	Заn a_j+1

(3)

+	+	×	×	Заn	Заn
		b_jc	b_j+1c
		NOP
		NOP
+d	+d
		NOP
		NOP
				Заn a_j	Заn a_j+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}

(1) 26 тактов

(2) 27 тактов

(3) 30 тактов

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

(1) задержка 7 тактов

(2) задержка 5 тактов

(3) задержка 3 такта

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

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

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

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

Для выражения A = ((a + b)×(b + c))×((c + d)×(d+ e)) изобразите схему коммутации решающего поля, включая ОЗП. При возможном лишь последовательном считывании данных составьте временную диаграмму загрузки каждого ПЭ, учитывающую задержку поступления данных. Время считывания и время сложения равны одной условной единице, время умножения - двум, время деления - трем единицам. Найдите время решения

(1)

Сч а → 1,1	Сч b → 2,1	Сч c → 3,1	Сч d → 4,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1	Сч e → 4,1

ПЭ1	a	b
ПЭ2			b	c
ПЭ3					c	d
ПЭ4							d	e

Время решения - 13 условных единиц

(2)

Сч а → 1,1	Сч b → 2,1	Сч c → 3,1	Сч d → 4,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1	Сч e → 4,1

ПЭ1	a	b
ПЭ2			b	c
ПЭ3					c	d
ПЭ4							d	e

Время решения - 14 условных единиц

(3)

Сч а → 1,1	Сч b → 2,1	Сч c → 3,1	Сч d → 4,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1	Сч e → 4,1

ПЭ1	a	b
ПЭ2			b	c
ПЭ3					c	d
ПЭ4							d	e

Время решения - 13 условных единиц

Определите количество скоммутированных операций для нахождения скалярного произведения массивов длины n, если решающее поле содержит 4 ПЭ. Считывание и организацию цикла не рассматривать. За сколько тактов выполнятся операции? n = 8

(1) 15 операций, 4 такта

(2) 16 операций, 5 тактов

(3) 14 операций, 4 такта

Правильно ли (без тупиков) выполнится общая для всех процессоров монопрограмма на четырех процессорах с номерами 0, 1, … ВС SPMD-архитектуры?

КОП	А₁	А₂	А₃
СИНХ
ЗАКРА	<i+1>
×	<i>	2	A[i]

(1) процессор i закрывает адрес, по которому хранится номер процессора i+1. Предполагается, что счет номера процессора в данном случае производится по mod4, (3+1)_mod4= 0

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

(3) процессор i=0 беспрепятственно закончит выполнение программы

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

(1) так легче использовать возможности системы команд

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

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

(4) закреплять за процессорами отдельные логические цепочки нецелесообразно из-за различной трудоемкости их обработки

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

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

(2) с помощью аппаратной реализации механизма синхронизации обращения к общим данным

(3) с помощью микропрограммной реализации команд синхронизации в процессоре RISC-архитектуры

Построить временную диаграмму выполнения операции D = (A+ B)xC над векторами А, В, С, содержащими по 3 элемента, если конвейер сложения содержит 2 уровня, конвейер умножения – 3. Возможно выполнение операции "зацепления" векторов.

(1)

(2)

(3)

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

(1) 3 такта по двум ветвям

(2) 2 такта по ветви "+", 3 такта по ветви "-"

(3) 4 такта по двум ветвям

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

(1) базовый регистр В₁ будет "смотреть" на область активации процедуры А. Затем, на втором лексикографическом уровне, запустится процедура В. На ее область активации будет "смотреть" базовый регистр В₂. После запуска процедуры С на ее область активации будет "смотреть" регистр В₃. Этот же регистр будет затем "смотреть" на новую область активации повторно запущенной рекурсивной процедуры В. После нового запуска процедуры В на ее область активации будет "смотреть" следующий базовый регистр В₄. Так – до начала обратного выхода из процедуры В. При возврате в процедуру А базовые регистры В₂, … готовы к переиспользованию в том же порядке

(2) произойдет прерывание при повторном обращении к процедуре В

(3) программа зациклится

Для задачи A:if a-b>0 then(c×d):f else c+e×f; B:=if(a>b∨c>b) then A×a else c+d представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

(1) if ab-0> then cd×f:else cef×+3nA; if ab>cd>∨ then Aa×else cd+3nB→ if r1 0> then r2f:else c r3+3nA; if r4r5∨ then r6 then r7 3nB→ if r8 then r9 else r10 3nA; if r11 then r6 else r7 3nB Требуется 11 быстрых регистров

(2) if ab- 0> then cd×f: else cef×+ ЗnA; if ab> cd>∨ then Aa× else cd+ЗnВ → if r1 0>then r2 f: else c r3+Зnr4; if r5 r6∨ then r7 else r8 ЗnВ → if r9 then r10 else r11 Зnr4; if r12 then r7 else r8 ЗnВ. Требуется 12 быстрых регистров

(3) if ab- 0> then cd×f: else cef×+ ЗnА; if ab>cd>∨ then Aa× else cd+ЗnВ → if r1 0>then r2 f: else c r3+Зnr4; if r5 r6∨ then r7 else r8 Зnr9 → if r10 then r11 else r12 Зnr4; if r13 then r7 else r8 ЗnВ. Требуется 13 быстрых регистров

АЛУ содержит два ИУ сложения, два – умножения, логическое ИУ выполняет и функции обмена с памятью. Сложение выполняется за 1 такт, умножение – за 2. Составьте план оптимальной программы параллельного вычисления величины возбуждения нейрона, если количество дендритов (входов) равно К. К = 8, передаточная функция имеет вид: files

(1)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁	ω₇V₇+Σ₂
Σ₁+Σ₂
-h				V_j

(2)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁	ω₇V₇+Σ₂
Σ₁+Σ₂	-h			V_j

(3)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₂V₂	ω₃V₃
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₄V₄	ω₅V₅
ω₄V₄+Σ₁	ω₅V₅+Σ₂	ω₆V₆	ω₇V₇
ω₆V₆+Σ₁	ω₇V₇+Σ₂
Σ₁+Σ₂
-h
				V_j

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

(1) 22 такта

(2) 23 такта

(3) 24 такта

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

(1)

(2)

(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 Приведите текст пятой команды

(1)

<Q>

(2)

Сч

5,2

(3)

5,1

Определите общее число закоммутированных операций при умножении квадратных матриц размера n. За сколько тактов рассчитывается один элемент? n = 7

(1) для счета одного элемента матрицы - результата закоммутируется выполнение 13 операций. Организуется двойной цикл их выполнения 49 раз. Для счета одного элемента требуется 4 такта

(2) 14 операций, 4 такта

(3) 15 операций, 5 тактов

Составьте граф-схемы выполнения операций свертки (преобразование "вектор - скаляр") массивов, содержащих m элементов, методом "пирамиды", реализующей операцию m=7

(1)

(2)

(3)

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

(1) 7 единиц времени

(2) 8 единиц времени

(3) 9 единиц времени

Составьте программу в безадресной форме и представьте ее выполнение на стеке. Сколько команд содержит программа и как выглядит стек после выполнения четвертой команды? A:=(a+b)×c-(d:e)

(1) 10 команд, стек имеет вид

a+b

(2) 9 команд, стек имеет вид

(a+b)×c

(3) 11 команд, стек имеет вид

a+b

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

(1) Сч a r₁ Сч с r₂ + r₁r₂

(2) Сч a r₁ Сч с r₂ {пропуск тактов в ожидании считывания} + r₁r₂b

(3) Сч a r₁ {пропуск тактов в ожидании считывания} Сч с r₂ {пропуск тактов в ожидании считывания} + r₁ r₂b

Сформируйте статические и динамические цепочки выполнения процедур в соответствии с иерархией их описания и с порядком обращения. files

(1) статическая цепочка для процедуры С , как самого высокого лексико-графического уровня, имеет вид С→ В→ А; динамическая цепочка при ее выполнении в составе процедуры В имеет вид С → В → D. При следующем обращении - С → D

(2) статическая цепочка имеет вид С → В → А. Динамическая цепочка при запуске С в составе В, запущенной в D, имеет вид С→ В → А. При следующем обращении – С → А

(3) статическая цепочка имеет вид С → В → А. Динамическая цепочка при выполнении С в составе В при обращении в D имеет вид C → B→ D. При следующем обращении – С → А

Переведите выражение арифметического оператора в ПОЛИЗ и, используя неограниченное количество регистров для хранения промежуточных результатов, составьте программу счета в трехадресной системе команд. X := (a+ b)× (a: c – d)

(1)

1	+	a	b	r₁
2	:	a	c	r₂
3	-	r₂	d	r₃
4	×	r₁	r₃	X

(2)

1	:	a	c	r₁
2	-	r₁	d	r₂
3	+	a	b	r₃
4	×	R₂	r₃	X

(3)

1	+	a	b	r₁
2	:	a	c	r₂
3	×	r₁	r₂	r₃
4	-	r₃	d	X

АЛУ содержит два ИУ сложения, два – умножения, логическое ИУ выполняет и функции обмена с памятью. Сложение выполняется за 1 такт, умножение – за 2. Количество дендритов (входов) К = 8, передаточная функция имеет вид: files

Составьте планы программ для процессора с синхронными ИУ.

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V_j

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
				-	Σ	h	V_j

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7					+	r7	r8	Σ
+	r5	r6	r8	-	Σ	h	V_j

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

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

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

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

С помощью пятиадресной команды if-then-else составьте программу коммутации для счета значения выражения: X = a ×if (b+ c) > d then if e >0 then A+ B else A else 0

(1)

1	+	b	c	(1,1)
2	+	A	B	(2,1)
3	УСЛ	e	0	(3,1)
		(2,1)	A
4	УСЛ	(1,1)	d	(4,1)
		(3,1)	0
5	×	a	(4,1)	(1,2)

(2)

1	+	b	c	(1,1)
2	УСЛ	(1,1)	d	(2,1)
3		(3,1)	A
	+	A	B	(3,1)
4	УСЛ	(3,1)	e	(4,1)
		A	0
5	×	a	(4,1)	(1,2)

(3)

1	+	A	B	(1,1)
2	УСЛ	e	0	(2,1)
3		(1,1)	A
	+	b	c	(3,1)
4	УСЛ	(3,1)	d	(4,1)
		(2,1)	0
5	×	a	(4,1)	(1,2)

Какие операторы из приведенных последовательностей могут быть выполнены одновременно? 1. a := x²+ c 2. b := ay 3. a : y²

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

(2) операторы 1 и 2

(3) структура строго последовательная

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

(1)

(2)

(3)

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

(1) локальные данные процедур, выполняющихся параллельно

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

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

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

1	+	a	b	c
2	-	d	e	f
3	×	c	g	h
4	+	a	f	c
5	:	d	e	h

(1) 7 единиц времени

(2) 6 единиц времени

(3) 5 единиц времени

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

(1) 12 команд :r₆r₂r₃

(2) 11 команд Сч d r₇

(3) 13 команд +r₁r₂r₆

Составьте программу для процессора VlIW-архитектуры задачи abc×+ de: f+ × ЗпА при условии: данные находятся в регистровой (сверхоперативной) памяти; результат сложения можно использовать через 1 такт, результат умножения – через 2 такта, деления – через 3 такта; в составе АЛУ (в числе других) содержится 2 ИУ сложения, 2 умножения, одно деления. За сколько тактов, не считая записи, выполняется программа?

(1) программа имеет вид

1.		×b c r1;	:d e r2
2.	NOP
3.	NOP
4.	+a r1 r3
5.	NOP
6.	+ r2 r4
7.	NOP
8.		×r3 r4 A

программа выполняется за 10 тактов

(2) программа имеет вид

1.		×b c r1;	:d e r2
2.	NOP
3.	+a r1 r3
4.	NOP
5.	+ r2 f r4
6.	NOP
7.		×r3 r4 A

программа выполняется за 9 тактов

(3) программа имеет вид

1.		×b c r1;	:d e r2
2.	NOP
3.	NOP
4.	+ a r1 r3
5.	NOP
6.	NOP
7.	+r2 f r4
8.	NOP
9.		× r3 r4 A

программа выполняется за 11 тактов

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

(1) 522

(2) 463

(3) 499

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

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	a	x	r1	×	b	x	r2
×	r1	x	r3	+	r2	c	r4	+	r3	r4	Y

Минимальная длина расписания равна 5

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	a	x	r1	×	b	x	r2	×	r1	x	r1
+	r1	r2	r3	+	r3	c	Y

Минимальная длина расписания равна 6

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	x	x	r1	×	b	x	r2
×	a	r1	r1	+	r1	r2	r3	+	c	r3	Y

Минимальная длина расписания равна 6

Научите нейросеть "узнавать" букву, изображенную на экране, связав клетки экрана, - входного слоя нейросети, с соответствующим букве нейроном выходного слоя, как показано на примере files

Используемая передаточная функция имеет вид: files

где j - индекс точки, засвеченной эталоном, V_j - величина засветки (можно принимать равным единице), h - порог (выбрать экспериментально). Веса связей - единичные. Определите основные требования к нейрокомпьютеру. Научите нейросеть (схематично) распознавать букву А, увеличив число клеток экрана (увеличив разрешающую способность) и добавив к засвеченным эталоном клеткам клетки, принадлежащие некоторой окрестности засвеченного эталона - для захвата искаженной или "зашумленной" буквы. Сколько клеток экрана необходимо связать с решением, на которое указывает нейрон выходного слоя? files

(1) около 75 клеток

(2) около 60 клеток

(3) около 40 клеток

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

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

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

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

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

1	×	a	b	v₁
2	+	v₁	c	v₂
3	×	v₂	e	v₃

1	+	d	f	v₁
2	:	v₁	L	v₂
3	×	v₂	k	v₃

(1)

1	×	a	b	(1,1)
2	+	(1,1)	c	(3,1)
3	×	(3,1)	e	(1,2)

1	+	d	f	(2,1)
2	:	(2,1)	L	(4,1)
3	×	(4,1)	k	(2,2)

(2)

1	×	a	b	(1,1)
2	+	(1,1)	c	(3,1)
3	×	(3,1)	e	(1,2)

1	+	d	f	(2,1)
2	:	(2,1)	L	(3,1)
3	×	(3,1)	k	(2,2)

(3)

1	×	a	b	(1,1)
2	+	(1,1)	c	(2,1)
3	×	(3,1)	e	(1,2)

1	+	d	f	(1,2)
2	:	(2,1)	L	(2,2)
3	×	(3,1)	k	(2,2)

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

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

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

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

(4) минимизация количества используемых имен непосредственно влияет на минимальный объем используемой памяти

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

(1)

(2)

(3)

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

(1) да, третьему и четвертому процессорам во втором цикле

(2) нет

(3) да, четвертому процессору во втором цикле

Используя команду if-then-else и трехадресную систему команд, составьте программу счета значения выражения a+ if b+c > 0 then d: 5 else d: 20 Задержки выполнения команд из-за связности данных выполняются автоматически

(1)

+b	c	r1
:d	5	r2
:d	20	r3
>r1		s
if...s	r2	r4
	r3
+a	r4	<результат>

(2)

;d	20	r3
;d	5	r2
+b	c	r1
>		s
if...s	r2	r4
	r3
+a	r4	<результат>

(3)

;d	20	r3
+b	c	r1
;d	5	r2
>r1		s
if...s	r2	r4
	r3
+a	r4	<результат>

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

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

(2) благодаря тегам сокращается набор команд процессора

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

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

(1)

Операция	Матрица			t	τ	θ
ax				2	1	5
bx				2	2	4
bx+c	1			1	3	2
ax²	1			2	3	3
Y		1	1	1	5	1

(2)

Операция	Матрица				t	τ	θ
ax					2	1	5
bx					2	2	4
bx+c		1			1	4	2
ax²	1				2	3	3
Y			1	1	1	5	1

(3)

Операция	Матрица			t	τ	θ
ax				2	1	5
bx				2	2	3
bx+c	1			1	4	2
ax²	1			2	3	3
Y		1	1	1	4	1

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

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

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

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

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

Рассмотрите совместное обучение нейросети двум буквам, расположенным в центре экрана. Если количество засвеченных эталонами клеток экрана различно, нормируйте величины возбуждения нейронов выходного слоя, например, разделив их на число засвеченных эталоном клеток. Пришлось ли вам и как нормировать сигналы на выходе? Научите нейросеть распознаванию букв А и Ш files

(1) возбуждение нейрона выходного слоя, "отвечающего" за букву А, нормируется с коэффициентом 1/60, а возбуждение нейрона, "отвечающего" за букву Ш, - с коэффициентом 1/90

(2) возбуждение нейрона выходного слоя, "отвечающего" за букву А, нормируется с коэффициентом 1/40, а возбуждение нейрона, "отвечающего" за букву Ш, - с коэффициентом 1/60

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

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

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

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

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

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

1	Сч	3760	→ (1,1)
2	Зп		3762
3	Сч	3740	→ (3,2)
4	Сч	3761	→ (1,2)

(1) заявки 1 и 4 выполняются одновременно. Заявка 3 выполняется вслед за заявкой 1. Заявка 2 выполнится после поступления кода в ее текст

(2) заявки 1 и 4 выполняются одновременно. По заявке 2 в 3762 запишется 0. Затем выполнится заявка 3

(3) заявки 1 и 2 выполняются одновременно. Затем выполнится заявка 4. Заявка 3 выполняется после всех считываний по указанному адресу, засылая по нему 0

Рассмотрите принципы параллельных вычислений, лежащие в основе асинхронной вычислительной системы. В чем заключается компромисс между "Фон-Неймановской" и "не-Фон-Неймановской" архитектурами, осуществленный в ПВС?

(1) традиционная программа, использующая счетчик команд, распределяет задания между исполнительными устройствами и устанавливает связи между ними для согласованного выполнения. Исполнительные устройства работают по принципу data flow, выполняя те задания, для которых поступила исходная информация, и направляя результаты для дальнейшего использования в соответствии с установленными связями

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

(3) асинхронная ВС отображает компромисс между параллельным выполнением команд и последовательным обменом по общей шине для совместного использования данных

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

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

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

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

Перечислите преимущества и недостатки общих и распределенных однородных и неоднородных решающих полей в многопроцессорных вычислительных системах.

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

(2) распределенный вычислительный ресурс в составе многофункциональных (неоднородных) решающих полей в составе АЛУ процессоров представляет значительно меньше технологических трудностей, реализуемость на современном уровне, хотя выдвигает проблемы плотной рабочей нагрузки

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

Используя механизм предикатов и считая, что адрес предиката указывается перед кодом операции, составьте программу счета значения выражения a+ if b+c > 0 then d: 5 else d: 20

(1)

1.	+b	c	r1
2.	>r1		s
3.	s:	d 5	r2
4.	s:	d 20	r2
5.	+	a r2	<результат?>

(2)

1.	+b	c	r1
2.	> r1		s
3.	s:	d 5	r2
4.	s:	20	r2
5.	+ a	r2	<результат?>

(3)

1.	+ b	c	r1
2.	> r1		s
3.	s :	d 5	r2
4.	s +	a r2	<результат?>
5.	s :	d 20	r3
6.	s +	a r3	<результат>

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

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

(2) вычислительный процесс прерывается до формирования значения условия перехода

(3) используется условный переход по предпочтению

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

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

(1) статический режим компоновки командных слов сокращает объем и функции оборудования

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

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

(4) динамическое распределение вычислительного ресурса никогда не достигает той степени оптимизации, что единственно возможна при статическом распределении

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

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

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

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

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

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

(2) для построения отдельных операционных устройств компьютера на основе методов распараллеливания

(3) в специальных системах обработки информации, имитирующих мышечное сокращение

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

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

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

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

(1) 4 команды; используются по одному регистру каждого буфера

(2) 5 команд; используются два регистра буфера ПЭ1 и по одному регистру буферов других ПЭ

(3) 6 команд; используются по два регистра буферов ПЭ1, ПЭ2 и по одному регистру буферов других ПЭ

(1) 3 такта

(2) 2 такта

(3) 4 такта

Систематизируйте предпосылки, которые легли в основу ВС SPMD-архитектуры. Какие требования предъявляются к SPMD-архитектуре?

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

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

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

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

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α}логических высказываний на базе системы аксиом {α}={α₀,α₁,α₂,b₃,c₄,c₅}. Система аксиом α₀→c₄,α₁→b₃,α₂→b₄,b₃→c₅,b₄→c₆

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₁→b₃→c₅`	2	1	1
5	`α₂→b₄→c₆`	3	0	0

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₁→b₃→c₅`	2	0	1
5	`α₂→b₄→c₆`	3	1	0

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₂→b₄→c₆`	2	1	1
5	`α₁→b₃→c₅`	3	0	0

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

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

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

(3) единое адресное пространство означает одинаковую для всех процессоров адресацию распределенной памяти

Построить схему двухуровневого конвейера выполнения операции сложения 16-разрядных кодов с помощью 8-разрядных сумматоров.

(1) принципиальная схема имеет вид: files

(2) принципиальная схема имеет вид: files

(3) принципиальная схема имеет вид: files

(1) 3 такта, 4 ПЭ

(2) 4 такта, 3 ПЭ

(3) 2 такта, 5 ПЭ

Что произойдет, если в программе встретится запись данного вида?x := 0,6 z := y × cos(x)

(1) величине z присвоится значение y × cos(x)

(2) будет скомпилирована программа расчета cos(x) и его умножения на y

(3) значение cos(x) найдется в режиме интерпретации для дальнейшего умножения

Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта, деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:=x×if a>b then(c+d):f else c+(a×f); B:=ifA>0 then a×b:f else A×(c+f)

(1)

(2)

(3)

(1)

+	+	×	Заn	Заn
b_j+c	a_j+d
b_j+1+c	a_j+1+d
		(b_j+c)×(a_j+d)
		(b_j+1+c)×(a_j+1+d)
		NOP
			Заn a_j
				Заn a_j+1

(2)

+	+	×	Заn	Заn
b_j+c	a_j+d
b_j+1+c	a_j+1+d
		(b_j+c)×(a_j+d)
		(b_j+1+c)×(a_j+1+d)
		NOP
			Заn a_j	Заn a_j+1

(3)

+	+	×	Заn	Заn
b_j+c	a_j+d
b_j+1+c	a_j+1+d	(b_j+c)×(a_j+d)
		(b_j+1+c)×(a_j+1+d)
		NOP
			Заn a_j
				Заn a_j+1

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

(1) 28 тактов

(2) 27 тактов

(3) 30 тактов

(1) задержка 7 тактов

(2) задержка 5 тактов

(3) задержка 3 такта

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

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

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

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

Для выражения A = a×b×c× (a+ e) изобразите схему коммутации решающего поля, включая ОЗП. При возможном лишь последовательном считывании данных составьте временную диаграмму загрузки каждого ПЭ, учитывающую задержку поступления данных. Время считывания и время сложения равны одной условной единице, время умножения - двум, время деления - трем единицам. Найдите время решения

(1)

Сч b → 1,1	Сч a → 2,1	Сч a → 3,1
Сч c → 1,1	Сч e → 2,1

ПЭ1	b	c
ПЭ2			a	e
ПЭ3					a
ПЭ4

Время решения - 9 условных единиц

(2)

Сч b → 1,1	Сч a → 2,1	Сч a → 3,1
Сч c → 1,1	Сч e → 2,1

ПЭ1	b	c
ПЭ2			a	e
ПЭ3					a
ПЭ4

Время решения - 10 условных единиц

(3)

Сч b → 1,1	Сч a → 2,1	Сч a → 3,1
Сч c → 1,1	Сч e → 2,1

ПЭ1	b	c
ПЭ2			a	e
ПЭ3					a
ПЭ4

Время решения - 9 условных единиц

(1) 19 операций, 5 тактов

(2) 20 операций, 5 тактов

(3) 18 операций, 4 такта

КОП	А₁	А₂	А₃
СИНХ
ЗАКРА	<i-1>
×	<i>	2	A[i]

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

(2) все процессоры беспрепятственно выполняют умножение

(3) процессор i=3 беспрепятственно закончит выполнение программы

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

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

(2) чтобы контролировать формирование дедуктивного ряда

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

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

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

(2) команда, при которой указано имя предиката, выполняется. Однако результат не направляется в память, пока не найдено единичное значение предиката. При нулевом значении результат пропадает

(3) запускаются две ветви программы (формируется второй конвейер), выполняемые в спекулятивном режиме – в режиме, не разрушающем информацию. После расчета значения предиката признаются правильными результаты выполнения одной из ветвей

Построить временную диаграмму выполнения операции D = (AxB)+C над векторами А, В, С, содержащими по 3 элемента, если конвейер сложения содержит 2 уровня, конвейер умножения – 3. Возможно выполнение операции "зацепления" векторов.

(1)

(2)

(3)

Укажите число тактов счета при заданном значении b ( b= 5, b = -7).

(1) 3 такта по ветви "+", 2 такта по ветви "-"

(2) 3 такта по двум ветвям

(3) 2 такта по ветви "+", 3 такта по ветви "-"

(1) программа зациклится

(2) произойдет прерывание при повторном запуске процедуры А

(3) базовый регистр В₁ "смотрит" на область активации процедуры А. При запуске процедуры В на ее область активации "смотрит" базовый регистр В₂. Этот же регистр затем "смотрит" и на область новой активации процедуры А. Затем регистр В₃ станет "смотреть" на новые области активации процедур В и А и т.д. – до обратного выхода из рекурсивной процедуры А

Для задачи A:x×if a>b then(c+d):f else c+(a×f); B:=ifA>0 then a×b:f else A×(c+f) представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

(1) x if ab> then cd+ f: else caf×+× ЗnА; if A0>then ab× f: else Acf+× ЗnВ → x if r1 then r2 f: else cr3+× ЗnА; if r4 then r5 f: else Ar6×ЗnВ → x if r1 then r7 else r8× Зnr9; if r4 then r10 else r11 ЗпВ → xr12×ЗnА; ЗпВ. Требуется 12 быстрых регистров

(2) x if ab>then cd+ f: else caf×+× ЗnА; if A0> then ab× f: else Acf+× ЗnВ → x if r1 then r2 f: else cr3+× ЗnА; if r4 then r5 f: else Ar6× ЗnВ → x if r1 then r7 else r8×ЗnА; if r4 then r9 else r10 ЗnВ → xr11× ЗnА; ЗnВ. Требуется 11 быстрых регистров

(3) x if ab> then cd+ f: else caf×+× ЗnА; if A0> then ab× f: else Acf+× ЗnВ → x if r1 then r2 f: else cr3+× Зnr4; if r5 then r6 f: else Ar7× Зnr8 → x if r1 then r9 else r10× Зnr4; if r5 then r11 else r12 Зnr8 → xr13×ЗnА; ЗnВ Требуется 13 быстрых регистров

V_j:= if V≥ h then V else 0

(1)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁	ω₇V₇+Σ₂
V=Σ₁+Σ₂
				Σ:=V≥h
				if ΣthenV else 0

(2)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁	ω₇V₇+Σ₂
V=Σ₁+Σ₂				Σ:=V≥h
				if ΣthenV else 0

(3)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁	ω₇V₇+Σ₂
V=Σ₁+Σ₂
Σ:=V-h				if ΣthenV else 0

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

(1) 20 тактов

(2) 23 такта

(3) 21 такт

(1)

(2)

(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)

Сч

7,2

(2)

6,1

(3)

<Q>

Определите общее число закоммутированных операций при умножении квадратных матриц размера n. За сколько тактов рассчитывается один элемент? n = 8

(1) 15 операций, 4 такта

(2) 16 операций, 5 тактов

(3) 15 операций, 5 тактов

Составьте граф-схемы выполнения операций свертки (преобразование "вектор - скаляр") массивов, содержащих m элементов, методом "пирамиды", реализующей операцию m=6

(1)

(2)

(3)

(1) 9 единиц времени

(2) 8 единиц времени

(3) 7 единиц времени

(1) 10 команд, стек имеет вид

b×c

(2) 11 команд, стек имеет вид

(3) 9 команд, стек имеет вид

a-b×c

(1) Сч b r₁ Сч с r₂ × r₁ r₂ r₃. × r₂ r₃ a

(2) Сч b r₁ {пропуск тактов в ожидании считывания} Сч с r₂ {пропуск тактов в ожидании считывания} × r₁ r₂ r₃. × r₂ r₃ a

(3) Сч b r₁ Сч с r₂ {пропуск тактов в ожидании считывания} × r₁ r₂ r₃. × r₂ r₃ a

(1) статическая цепочка для процедуры С , как самого высокого лексико-графического уровня, имеет вид С→ В→ А; динамическая цепочка при ее выполнении в составе процедуры А имеет вид С → В → А→ D. При следующем обращении - С → D

(2) статическая цепочка имеет вид С → В → А. Динамическая цепочка при запуске С в составе В, запущенной в А, а затем - в D, имеет вид С→ В → А. При следующем обращении – С → А

(3) статическая цепочка имеет вид С → В → А. Динамическая цепочка при выполнении С в составе В и А при обращении в D имеет вид C → B→ А. При следующем обращении – С → А

(1)

1	+	a	b	r₁
2	:	c	d	r₂
3	×	r₁	r₃	X

(2)

1	:	c	d	r₁
2	+	a	b	r₂
3	×	r₁	r₃	X

(3)

1	+	a	b	r₁
2	×	r₁	c	r₂
3	:	r₂	d	X

V_j:= if V≥ h then V else 0 Составьте планы программ для процессора с синхронными ИУ.

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V	N+2
Зп	V		V_j	B
Зп			V_j	B

(N+2 – адрес перехода для пропуска следующей команды, В – адрес выхода)

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V	УЗп	V		V_j	УЗп			V_j

(УЗп – запись по условию, выработанному в первом слоге командного слова)

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1	×	ω₇	V₇	r2	+	r1	r2	r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V
УЗп	V		V_j	УЗп			V_j

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

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

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

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

С помощью пятиадресной команды if-then-else составьте программу коммутации для счета значения выражения: X = a×b× if (d+ c) >0 then if e>0 then A else A+B else 0

(1)

1	×	a	b	(1,1)
2	+	d	c	(2,1)
3	+	A	B	(3,1)
4	УСЛ	e	0	(4,1)
		A	(3,1)
5	УСЛ	(2,1)	0	(1,2)
		(4,1)	0
6	×	(1,1)	(1,2)	(2,2)

(2)

1	×	a	b	(1,1)
2	+	d	c	(2,1)
3	+	A	B	(3,1)
4	УСЛ	e	0	(4,1)
		A	(3,1)
5	УСЛ	(2,1)	0	(1,2)
		(4,1)	0
6	×	(1,2)	(4,1)	(1,3)

(3)

1	+	A	B	(1,1)
2	УСЛ	e	0	(2,1)
		A	(3,1)
3	×	a	b	(3,1)
4	+	d	c	(4,1)
5	УСЛ	(4,1)	0	(1,2)
		(2,1)	0
6	×	(3,1)	(1,2)	(2,2)

Какие операторы из приведенных последовательностей могут быть выполнены одновременно? 1. a := x² 2. b := y² 3. a : a+b

(1) операторы 1 и 2

(2) операторы 1 и 3

(3) структура строго последовательная

(1)

(2)

(3)

Рассмотрите проблемы когерентности кэшей. Какие способы обеспечения когерентности кэшей следует считать эффективными?

(1) периодический обмен кэшами по общей шине

(2) снабжение каждого "глобала" значением времени последнего изменения при обновлении состояния кэша процессора в памяти других процессоров

(3) cинхронизация изменения "глобалов", закрытых другими процессорами с помощью механизма закрытия адресов (в ВС SPMD-архитектуры). Списки закрытых адресов доступны каждому процессору

(4) периодический "сброс" всех кэшей для их естественного заполнения вновь из ОП

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

1	×	a	b	c
2	-	c	d	a
3	:	e	f	c
4	-	a	b	f
5	+	e	c	e

(1) 8 единиц времени

(2) 7 единиц времени

(3) 6 единиц времени

Составьте программу для процессора VlIW-архитектуры задачи ab+ c× de- × f× ЗпА при условии: данные находятся в регистровой (сверхоперативной) памяти; результат сложения можно использовать через 1 такт, результат умножения – через 2 такта, деления – через 3 такта; в составе АЛУ (в числе других) содержится 2 ИУ сложения, 2 умножения, одно деления. За сколько тактов, не считая записи, выполняется программа?

(1) программа имеет вид

1.	+ a b r1;	-d е r2
2.	NOP
3.			× r1 c r3
4.	NOP
5.	NOP
6.			× r3 r2 r4
7.	NOP
8.	NOP
9.			× r4 f A

программа выполняется за 11 тактов

(2) программа имеет вид

1.	+ a b r1;	-d е r2
2.	NOP
3.			× r1 c r3
4.	NOP
5.	NOP
6.			× r3 r2 r4
7.	NOP
8.			× r4 f A

программа выполняется за 10 тактов

(3) программа имеет вид

1.	+ a b r1;	-d е r2
2.	NOP
3.			×r1 c r3
4.	NOP
5.			×r3 r2 r4
6.	NOP
7.			×r4 f A

программа выполняется за 9 тактов

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

(1) 565

(2) 675

(3) 612

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	b	x	r1	×	a	x	r2
+	r2	x	r2	+	r1	c	r1	+	r1	r2	Z

Минимальная длина расписания равна 5

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	B	x	r1	+	c	r1	r1	×	a	x	r2
×	r2	x	r2	+	r1	r2	Z

Минимальная длина расписания равна 7

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	B	x	r1	×	a	x	r2	×	r2	x	r2
+	r1	c	r1	+	r1	r2	Z

Минимальная длина расписания равна 6

Используемая передаточная функция имеет вид: files

где j - индекс точки, засвеченной эталоном, V_j - величина засветки (можно принимать равным единице), h - порог (выбрать экспериментально). Веса связей - единичные. Определите основные требования к нейрокомпьютеру. Научите нейросеть (схематично) распознавать букву О, увеличив число клеток экрана (увеличив разрешающую способность) и добавив к засвеченным эталоном клеткам клетки, принадлежащие некоторой окрестности засвеченного эталона - для захвата искаженной или "зашумленной" буквы. Сколько клеток экрана необходимо связать с решением, на которое указывает нейрон выходного слоя? files

(1) около 70 клеток

(2) около 85 клеток

(3) около 50 клеток

Пусть метод сеток использует рекуррентное отношение, связывающее значения функции-решения в соседних узлах: 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 узла

1	Сч	3760	→ (1,1)
2	Зп		3761
3	Сч	3743	→ (1,2)
4	Сч	3761	→ (2,1)

(1) заявки 1 и 3 выполняются одновременно. Заявка 4 выполняется после заявок 1 и 2. Заявка 2 выполнится после поступления кода в ее текст

(2) заявки 1, 3 и 4 выполняются одновременно. Заявка 2 выполнится после поступления записываемого кода

(3) заявки 1 и 3 выполняются одновременно. Заявка 4 выполнится после заявки 2, записывающей 0 по указанному адресу

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

(1) используется традиционный условный переход. Однако его вес снижается за счет использования команды if-then-else в составе арифметических операторов. Возможно применение механизма предикатов

(2) ветвление осуществляется с помощью запуска второго конвейера коммутации

(3) условный переход прерывает процесс коммутации до выявления направления ветвления

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

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

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

(3) предикаты используются для организации режима data flow

Как производится загрузка исполнительных устройств распределенного вычислительного ресурса в процессоре "Эльбрус-2"?

(1) безадресная система команд позволяет параллельно использовать несколько подстеков

(2) безадресные команды аппаратно переводятся в трехадресные (с использованием адресов регистровой памяти); с помощью анализа совпадения адресов решается вопрос о назначении команд для параллельного выполнения

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

Используя механизм предикатов и считая, что адрес предиката указывается перед кодом операции, составьте программу счета значения выражения a× if b > 0 then (c+ d)× x else (e+ f)

(1)

1.		>b		s
2.	s	+c	d	r1
3.	s	+e	f	r1
4.	s	× r1	x	r1
5.		× a	r1	<результат>

(2)

1.		>b		s
2.	s	+c	d	r1
3.		+e	f	r1
4.	s	× r1	x	r1
5.		× a	r1	<результат>

(3)

1.		> b		s
2.	s	+c	d	r1
3.	s	+ e	f	r1
4.	s	× r1	x	r1
5.		× a	r1	<результат>

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

(1) с помощью команды if-then-else, позволяющей параллельно рассчитывать значения условия и альтернативных операторов, или памяти предикатов, позволяющей планировать вычисление арифметических операторов в спекулятивном режиме

(2) оптимальным включением условных операторов в программу на этапе трансляции

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

Ответьте на вопросы обоснования методов компоновки "длинных" командных слов (широкой команды - по другой терминологии) в архитектурах ВС, управляемых в каждом такте. Каково соотношение между элементами статики и динамики в алгоритме составления оптимального потактового расписания для многофункционального АЛУ?

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

(2) компоновка "длинных" командных слов производится в статическом режиме, как и вся трансляция. Однако в основе составления расписания лежит диспетчер динамического распараллеливания

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

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

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

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

(2) в составе команд обязательно должна присутствовать команда вида if-then-else, по которой выбирается необходимый вариант счета, соответствующий значению проверяемого условия

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

(1) в возможности оптимального планирования его использования на основе распределения адресного пространства

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

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

1	+	a	b	v₁
2	-	e	c	v₂
3	×	v₂	v₁	v₃

1	+	d	f	v₁
2	:	k	L	v₂
3	×	v₂	v₁	v₃

(1)

1	+	a	b	(1,1)
2	-	e	c	(3,1)
3	×	(3,1)	(1,1)	(1,2)

1	+	d	f	(2,1)
2	:	k	L	(4,1)
3	×	(4,1)	(2,1)	(2,2)

(2)

1	×	a	b	(1,1)
2	-	(1,1)	c	(3,1)
3	×	(3,1)	e	(1,2)

1	+	d	f	(2,1)
2	:	(2,1)	L	(3,1)
3	×	(3,1)	k	(2,2)

(3)

1	×	a	b	(1,1)
2	-	e	c	(2,1)
3	×	(3,1)	(1,1)	(1,2)

1	+	d	f	(1,2)
2	:	k	L	(2,2)
3	×	(3,1)	(2,1)	(2,2)

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

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

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

(3) при коммутации не следует обращать внимание на условные и безусловные переходы

(1)

(2)

(3)

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

(1) да, пятому процессору в первом цикле, второму во втором цикле

(2) нет

(3) да, пятому процессору в первом цикле

Используя команду if-then-else и трехадресную систему команд, составьте программу счета значения выражения a× if b > 0 then (c+ d)× x else (e+ f) Задержки выполнения команд из-за связности данных выполняются автоматически

(1)

>b	s
+c	d	r1
+e	f	r2
×r1	x	r3
if...s	r2	r4
	r3
×a	r4	<результат>

(2)

+c	d	r1
>b		s
+e	f	r2
×r1	x	r3
if...s	r2	r4
	r3
×a	r4	<результат>

(3)

+e	f	r2
+c	d	r1
>b		s
×r1	x	r3
if...s	r2	r4
	r3
×a	r4	<результат>

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

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

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

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

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

(1)

Операция	Матрица				t	τ	θ
bx					2	2	4
ax					2	1	5
c+bx	1				1	4	2
ax²		1			2	3	3
Z			1	1	1	5	1

(2)

Операция	Матрица				t	τ	θ
bx					2	1	4
ax					2	2	5
c+bx	1	1			1	4	2
ax²		1			2	3	3
Z			1	1	1	5	1

(3)

Операция	Матрица				t	τ	θ
bx					2	2	4
ax					2	2	5
c+bx	1				1	3	2
ax²		1			2	3	3
Z			1	1	1	5	1

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

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

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

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

(1) возбуждение нейрона выходного слоя, "отвечающего" за букву О, нормируется с коэффициентом 1/70, а возбуждение нейрона, "отвечающего" за букву Ш, - с коэффициентом 1/90

(2) возбуждение нейрона выходного слоя, "отвечающего" за букву О, нормируется с коэффициентом 1/50, а возбуждение нейрона, "отвечающего" за букву Ш, - с коэффициентом 1/70

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

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

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

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

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

(1) 5 команд; используются два регистра буфера ПЭ1 и по одному регистру буферов других ПЭ

(2) 6 команд; используются по два регистра буферов ПЭ1 и ПЭ2 и по одному других буферов

(3) 8 команд; используются по два регистра буферов всех ПЭ

(1) 3 такта

(2) 4 такта

(3) 5 такта

Систематизируйте предпосылки, которые легли в основу ВС SPMD-архитектуры. Чем SPMD-архитектура отличается от обычной ВС MIMD-архитектуры?

(1) специальной системой команд, поддерживающей распараллеливание по информации с синхронизацией при использовании общих данных

(2) приспособленностью к параллельной обработке массивов, инвариантностью программ относительно количества процессоров и длины массивов

(3) возможностью обработки элементов массивов как параллельно, так и последовательно

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

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

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α} логических высказываний на базе системы аксиом {α}={α₀,α₁,α₂,b₃,b₄,b₅,c₆,c₇}. Система аксиом α₀→b₃,α₀→b₄,α₁→b₄,α₂→c₇,b₃→c₆,b₄→c₇

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₃→c₆`	1	0	0
6	`α₀→b₄→c₇`	2	1	1
7	`α₁→b₄→c₇`	3	0	0

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₃→c₆`	1	1	0
6	`α₀→b₄→c₇`	2	0	1
7	`α₁→b₄→c₇`	3	1	0

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₄→c₇`	1	0	0
6	`α₀→b₃→c₆`	2	1	1
7	`α₁→b₄→c₇`	3	0	0

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

(1) отделение проблемы разработки микропроцессоров от проблемы разработки средств их комплексирования

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

(3) масспроцессорные системы с "быстрыми" линиями связи специальной топологии

Построить принципиальную схему двухуровневого конвейера умножения двух 4-разрядных кодов.

(1) принципиальная схема имеет вид: files

(2) принципиальная схема имеет вид: files

(3) принципиальная схема имеет вид: files

(1) 3 такта, 3 ПЭ

(2) 2 такта, 4 ПЭ

(3) 4 такта, 3 ПЭ

Что произойдет, если в программе встретится запись данного вида? n := N Считать "Факториал (n)"

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

(2) текст процедуры поступит в буфер команд

(3) текст процедуры выведется на дисплей

Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта, деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:if a>0then ifb>c thena↑2else d×a×b else (d-e)×f B:=if a×b>0 then A×x else 0

(1)

(2)

(3)

(1)

+	+	×	×	Зап	Зап
a_j+d	a_j+1+d	b_j×c	b_j+1×c
		NOP
		NOP
		(b_j×c)×(a_j+d)	(b_j+1×c)×(a_j+1+d)
		NOP
		NOP
				Заn a_j	Заn a_j+1

(2)

+	+	×	×	Зап	Зап
a_j+d	a_j+1+d	b_j×c	b_j+1×c
		NOP
		(b_j×c)×(a_j+d)	(b_j+1×c)×(a_j+1+d)
		NOP
		NOP		Заn a_j
					Заn a_j+1

(3)

+	+	×	×	Зап	Зап
a_j+d	a_j+1+d	b_j×c	b_j+1×c
		NOP
		NOP
		(b_j×c)×(a_j+d)	(b_j+1×c)×(a_j+1+d)
		NOP
				Заn a_j	Заn a_j+1

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

(1) 28 тактов

(2) 27 тактов

(3) 32 такта

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

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

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

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

Для выражения A = (a×b+ a: c)× (c+ d) изобразите схему коммутации решающего поля, включая ОЗП. При возможном лишь последовательном считывании данных составьте временную диаграмму загрузки каждого ПЭ, учитывающую задержку поступления данных. Время считывания и время сложения равны одной условной единице, время умножения - двум, время деления - трем единицам. Найдите время решения

(1)

Сч a → 1,1	Сч a → 2,1	Сч c → 3,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1

ПЭ1	a	b
ПЭ2			a	c
ПЭ3					c	d
ПЭ4

Время решения - 10 условных единиц

(2)

Сч a → 1,1	Сч a → 2,1	Сч c → 3,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1

ПЭ1	a	b
ПЭ2			a	c
ПЭ3					c	d
ПЭ4

Время решения - 11 условных единиц

(3)

Сч a → 1,1	Сч a → 2,1	Сч c → 3,1
Сч b → 1,1	Сч c → 2,1	Сч d → 3,1

ПЭ1	a	b
ПЭ2			a	c
ПЭ3					c	d
ПЭ4

Время решения - 9 условных единиц

(1) 20 операций, 5 тактов

(2) 23 операции, 5 тактов

(3) 22 операции, 6 тактов

КОП	А₁	А₂	А₃
ЗАКРА	<i+1>
×	<i>	2	A[i]

(1) отсутствие команды СИНХ не гарантирует одновременность выполнения команды ЗАКРА, а, следовательно, результат выполнения программы процессорами непредсказуем

(2) все процессоры будут заблокированы в тупиковой ситуации

(3) процессор i=0 успешно выполнит программу

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

(1) они являются основным средством взаимодействия с элементами массивов, их контроля и преобразования. Это основной механизм представления данных, на который ориентирована система команд

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

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

(4) дескрипторы массивов хранят и модифицируют шаги переадресации

Как на уровне команд производится синхронизация процессоров при обращении к общим данным?

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

(2) с помощью команды "СИНХ", позволяющей одновременное продолжение выполнения программы с одной и той же команды для всех процессоров

(3) с помощью совместного применения команд "СИНХ" и "Закрыть Адрес"

Построить временную диаграмму выполнения операции D = Ax(B+C) над векторами А, В, С, содержащими по 3 элемента, если конвейер сложения содержит 2 уровня, конвейер умножения – 3. Возможно выполнение операции "зацепления" векторов.

(1)

(2)

(3)

(1) 2 такта по ветви "+", 3 такта по ветви "-"

(2) 3 такта по двум ветвям

(3) 3 такта по ветви "+", 2такта по ветви "-"

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

(2) произойдет прерывание из-за недопустимости подобной структуры

(3) произойдет прерывание по зацикливанию

Для задачи A:if a>0then ifb>c thena↑2else d×a×b else (d-e)×f B:=if a×b>0 then A×x else 0 представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

(1) if a0 then if bc> then a↑2 else dab×× else de- f× ЗnА; if ab×0> then Ax×else 0 → if r1 then if r2 then r3 else dr4× else r5 f× ЗnА; if r6 0>then r7 else 0 ЗnВ → if r1 then if r2 then r3 else r8 else r9 ЗnА; if r10 then r7 else 0 ЗпВ → if r1 then r11 else r9 ЗnА; ЗnВ. Требуется 11 быстрых регистров

(2) if a0 then if bc> then a2 else dab××else de- f×ЗnА; if ab×0> then Ax×else 0 → if r1 then if r2 then r3 else dr4×else r5 f×Зnr6; if r7 0>then r8 else 0 ЗnВ → if r1 then if r2 then r3 else r9 else r10 Зnr6; if r11 then r8 else 0 ЗпВ → if r1 then r12 else r10 ЗnА; ЗпВ. Требуется 12 быстрых регистров

(3) if a0 then if bc> then a↑2 else dab×× else de- f× ЗnА; if ab×0> then Ax×else 0 → if r1 then if r2 then r3 else dr4× else r5 f×ЗnА; if r6 0>then r7 else 0 ЗnВ → if r1 then if r2 then r3 else r8 else r2 ЗnА; if r9 then r7 else 0 ЗnВ → if r1 then r10 else r9 ЗnА; ЗnВ. Требуется 10 быстрых регистров

АЛУ содержит два ИУ сложения, два – умножения, логическое ИУ выполняет и функции обмена с памятью. Сложение выполняется за 1 такт, умножение – за 2. Составьте план оптимальной программы параллельного вычисления величины возбуждения нейрона, если количество дендритов (входов) равно К. К = 7, передаточная функция имеет вид: files

V_j:= if V≥ h then 1 else 0

(1)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁
V=Σ₁+Σ₂
				Σ:=V≥h
				if Σthen1 else 0

(2)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆	ω₇V₇
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁
V=Σ₁+Σ₂				Σ:=V≥h
				if ΣthenV else 0

(3)

+	+	×	×	ЛОГ
		ω₀V₀	ω₁V₁
		ω₂V₂	ω₃V₃
ω₀V₀+Σ₁	ω₁V₁+Σ₂	ω₄V₄	ω₅V₅
ω₂V₂+Σ₁	ω₃V₃+Σ₂	ω₆V₆
ω₄V₄+Σ₁	ω₅V₅+Σ₂
ω₆V₆+Σ₁
V=Σ₁+Σ₂
Σ:=V-h				if ΣthenV else 0

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

(1) 23 такта

(2) 18 тактов

(3) 22 такта

(1)

(2)

(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)

Сч

6,2

(2)

7,2

(3)

<Q>

Определите общее число закоммутированных операций при умножении квадратных матриц размера n. За сколько тактов рассчитывается один элемент? n = 9, используется 4 ПЭ

(1) 17 операций, 5 тактов

(2) 17 операций, 4 такта

(3) 16 операций, 5 тактов

Составьте граф-схемы выполнения операций свертки (преобразование "вектор - скаляр") массивов, содержащих m элементов, методом "пирамиды", реализующей операцию m=5

(1)

(2)

(3)

(1) 6 единиц времени

(2) 7 единиц времени

(3) 9 единиц времени

(1) 10 команд, стек имеет вид

a×b

(2) 11 команд, стек имеет вид

a×b

(3) 10 команд, стек имеет вид

с-a×b

(1) Сч a r₁ Сч b r₂ + r₁ r₂ a

(2) Сч a r₁ Сч b r₂ {пропуск тактов в ожидании считывания} + r₁ r₂ a

(3) Сч a r₁ {пропуск тактов в ожидании считывания} Сч b r₂ {пропуск тактов в ожидании считывания} + r₁r₂ a

(1) статическая цепочка для процедуры С , как самого высокого лексико-графического уровня, имеет вид С→ В→ А; динамическая цепочка при ее выполнении первый раз в составе процедуры D имеет вид С → D. При следующем запуске в составе процедуры В - С → В→ D

(3) статическая цепочка имеет вид С → В → А. Динамическая цепочка при выполнении С в составе D имеет вид С → А. При обращении в D к В динамическая цепочка имеет вид C → B→ А

(1)

1	+	b	c	r₁
2	×	d	d	r₂
3	×	a	r₁	r₃
4	+	r₃	r₂	X

(2)

1	×	d	d	r₁
2	+	b	c	r₂
3	×	a	r₂	r₃
4	+	r₃	r₁	X

(3)

1	×	d	d	r₁
2	+	b	c	r₂
3	+	r₁	r₂	r₃
4	×	a	r₃	X

АЛУ содержит два ИУ сложения, два – умножения, логическое ИУ выполняет и функции обмена с памятью. Сложение выполняется за 1 такт, умножение – за 2. Количество дендритов (входов) К = 7, передаточная функция имеет вид: files

V_j:= if V≥ h then 1 else 0 Составьте планы программ для процессора с синхронными ИУ.

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1					+	r1		r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V	УЗп	1		V_j	УЗп			V_j

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
-	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V
УЗп	1		V_j
УЗп			V_j

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	ω₀	V₀	r1	×	ω₁	V₁	r2	+	r1	r2	r3
×	ω₂	V₂	r1	×	ω₃	V₃	r2	+	r1	r2	r4
×	ω₄	V₄	r1	×	ω₅	V₅	r2	+	r1	r2	r5
×	ω₆	V₆	r1					+	r1		r6
+	r3	r4	r7	+	r5	r6	r8	+	r7	r8	Σ
-	Σ	h	V	N+2
УЗп	1		V_j	B
УЗп			V_j	B

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

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

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

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

С помощью пятиадресной команды if-then-else составьте программу коммутации для счета значения выражения: X = b×if (d+ c) >a then if e >b then A else B else 0

(1)

1	УСЛ	e	b	(1,1)
		A	B
2	+	d	c	(2,1)
3	УСЛ	(2,1)	a	(3,1)
		(2,1)	0
4	×	b	(3,1)	(4,1)

(2)

1	+	d	c	(1,1)
2	УСЛ	e	b	(2,1)
		A	B
3	УСЛ	(1,1)	a	(3,1)
		(2,1)	0
4	×	b	(3,1)	(4,1)

(3)

1	+	d	c	(1,1)
2	УСЛ	(1,1)	a	(3,1)
		(2,1)	0
3	УСЛ	e	b	(2,1)
		A	B
4	×	b	(3,1)	(4,1)

Какие операторы из приведенных последовательностей могут быть выполнены одновременно? 1. a := x² 2. b := a+b 3. a : =a×c

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

(2) операторы 1 и 2

(3) операторы 1 и 3

(1)

(2)

(3)

Рассмотрите проблемы когерентности кэшей. Как реализуется когерентность кэшей на основе принципа data flow?

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

(2) с помощью комплексного алгоритмического анализа необходимости поддержки когерентности кэшей

(3) периодическим обменом состояния кэшей по общей шине

1	+	a	b	c
2	+	d	e	f
3	:	f	c	h
4	×	a	f	c
5	-	h	l	h

(1) 7 единиц времени

(2) 6 единиц времени

(3) 5 единиц времени

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

(1) 10 команд, Сч d r₆

(2) 9 команд, Сч e r₁

(3) 8 команд, + r₆ r₁ r₂

Составьте программу для процессора VlIW-архитектуры задачи ab+ c× de+× ЗпА при условии: данные находятся в регистровой (сверхоперативной) памяти; результат сложения можно использовать через 1 такт, результат умножения – через 2 такта, деления – через 3 такта; в составе АЛУ (в числе других) содержится 2 ИУ сложения, 2 умножения, одно деления. За сколько тактов, не считая записи, выполняется программа?

(1) программа имеет вид

1.	+ a b r1;	+d е r2
2.	NOP
3.			× r1 c r3
4.	NOP
5.	NOP
6.			× r3 r2 A

программа выполняется за 8 тактов

(2) программа имеет вид

1.	+ a b r1;	+d е r2
2.	NOP
3.	NOP
4.	NOP
5.			×r3 r2 A

программа выполняется за 7 тактов

(3) программа имеет вид

1.	+ a b r1;	+d е r2
2.	NOP
3.			× r1 c r3
4.	NOP
5.	NOP
6.			× r3 r2 A

программа выполняется за 7 тактов

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

(1) 444

(2) 531

(3) 492

(1)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	A	x	r1	+	r1	b	r1	×	r1	x	r2
+	r2	c	X

Минимальная длина расписания равна 6

(2)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	A	x	r1	×	r1	x	r1	×	b	x	r2
+	r1	r2	r3	+	r3	c	X

Минимальная длина расписания равна 6

(3)

КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A	КОП	R₁	R₂	R₃/A
×	A	x	r1	×	b	x	r2	+	r2	c	r2
×	r1	x	r1	+	r1	r2	X

Минимальная длина расписания равна 6

Используемая передаточная функция имеет вид: files

где j - индекс точки, засвеченной эталоном, V_j - величина засветки (можно принимать равным единице), h - порог (выбрать экспериментально). Веса связей - единичные. Определите основные требования к нейрокомпьютеру. Научите нейросеть (схематично) распознавать букву Ш, увеличив число клеток экрана (увеличив разрешающую способность) и добавив к засвеченным эталоном клеткам клетки, принадлежащие некоторой окрестности засвеченного эталона - для захвата искаженной или "зашумленной" буквы. Сколько клеток экрана необходимо связать с решением, на которое указывает нейрон выходного слоя? files

(1) около 90 клеток

(2) около 70 клеток

(3) около 60 клеток

Пусть метод сеток использует рекуррентное отношение, связывающее значения функции-решения в соседних узлах: 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	Сч	3760	→ (1,2)
2	Cч	3741	→ (3,2)
3	Зп		3741
4	Сч	3741	→ (3,1)

(1) заявки 1 и 2 выполняются одновременно. Заявка 3 задерживается до поступления кода, а также до выполнения заявки 2. Заявка 4 выполнится после выполнения заявки 3

(2) заявки 1, 2 и 4 выполняются одновременно. Заявка 3 выполняется после поступления кода

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

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

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

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

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

(1) команда СИНХ заставляет все копии монопрограммы одновременно начать или продолжить выполнение с общей точки

(2) синхронно начать или продолжить выполнение копий монопрограммы можно с помощью команды "закрыть адрес"

(3) синхронизация во времени выполняется с помощью таймера

(4) синхронизация во времени выполняется с помощью механизма предикатов

Как производится загрузка исполнительных устройств распределенного вычислительного ресурса в процессорах VLIW- и EPIC-архитектуры?

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

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

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

Используя механизм предикатов и считая, что адрес предиката указывается перед кодом операции, составьте программу счета значения выражения (a+ b)× if c > 0 then B else (d+ e)× f

(1)

1.		+ a	b	r1
2.		> c		s
3.	s	× r1	B	<результат>
4.	s	+ d	e	r2
5.	s	× r2	f	r2
6.	s	× r1	r2	<результат>

(2)

1.		+ a	b	r1
2.		> c		s
3.	s	Зn B		r2
4.	s	+ d	e	r2
5.	s	× r2	f	r2
6.		× r1	r2	<результат>

(3)

1.		+ a	b	r1
2.		> c		s
3.	s	3n B		r2
4.	s	+ d	e	r2
5.		× r2	f	r2
6.		× r1	r2	<результат>

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

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

(2) время выполнения цикла минимизируется с помощью элемента цикла и средств поддержки условного перехода

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

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

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

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

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

(4) задача глобальной оптимизации программ столь сложна, что требует разбиения на частные задачи по принципу "разделяй и властвуй"

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

(1) опыт показывает, что передача всех функций управления на жесткий программный уровень при полной ликвидации элементов самоуправления, приводит к неэффективности и сложности программного кода, к необходимости в значительно большей степени отслеживать во времени частичную упорядоченность работ. Автоматическое соблюдение частичной упорядоченности работ снижает необходимость этого отслеживания. Тем более, что алгоритмы синхронизации на основе используемых адресов весьма просты

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

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

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

Рассмотрите перспективы применения высокопараллельных архитектур вычислительных систем со специальной топологией связей, исключающей оперативный обмен "каждый с каждым". Каковы перспективы применения высокопараллельных вычислительных систем со специальной топологией оперативных связей для решения задач моделирования нейронных сетей, в частности, - распознавания зрительных образов?

(1) это не параллельная система. При малых параметрах экрана такая модель реализуется на ПК

(2) параллельная структура мозга говорит о необходимости применения параллельных ВС для больших нейросетей. Каждая из рассмотренных архитектур пригодна для эффективного моделирования

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

1	×	a	b	v₁
2	+	v₁	v₃	v₂
3	×	v₂	e	v₃

1	+	d	f	v₁
2	:	v₁	L	v₂
3	×	v₂	k	v₃

(1)

1	×	a	b	(1,1)
2	+	(1,1)	(3,1)	(4,1)
3	×	(4,1)	e	(3,1)

1	+	d	f	(2,1)
2	:	(2,1)	L	(1,2)
3	×	(1,2)	k	(2,2)

(2)

1	×	a	b	(1,1)
2	+	(1,1)	(3,1)	(4,1)
3	×	(4,1)	e	(1,2)

1	+	d	f	(2,1)
2	:	(2,1)	L	(1,2)
3	×	(1,2)	k	(2,2)

(3)

1	×	a	b	(1,1)
2	+	(1,1)	(3,1)	(3,1)
3	×	(4,1)	e	(3,1)

1	+	d	f	(2,1)
2	:	(4,1)	L	(1,2)
3	×	(1,2)	k	(2,2)

Процессор, выполняя программу коммутации, встречает цикл. Воспроизводит он этот цикл, многократно повторяя анализ его тела, или ограничивается однократным анализом?

(1) универсальный способ коммутации циклов предполагает их "раскрутку". Должно быть максимально устранено использование одних и тех же имен переменных во всех итерациях

(2) процессор производит однократный анализ тела цикла

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

(1)

(2)

(3)

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

(1) да, третьему и четвертому процессорам в первом цикле, пятый – восьмой процессоры простаивают

(2) нет

(3) да, пятому процессору в первом цикле

Используя команду if-then-else и трехадресную систему команд, составьте программу счета значения выражения (a+ b)× if c > 0 then B else (d+ e)× f Задержки выполнения команд из-за связности данных выполняются автоматически

(1)

+a	b	r1
>c		s
+d	e	r2
×r2	f	r3
if...s	B	r4
	r3
×r1	r4	<результат>

(2)

>c		s
+a	b	r1
+d	e	r2
×r2	f	r3
if...s	B	r4
	r3
×r1	r4	<результат>

(3)

+d	e	r2
>		s
+a	b	r1
×r2	f	r3
if...s	B	r4
	r3
×r1	r4	<результат>

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

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

(2) индексация производится с помощью процедуры ОС, рассчитывающей новое значение адреса по измененным значениям индексов

(3) паспорт массива устанавливает максимальную размерность, обслуживаемую с помощью процедуры ОС

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

(1)

Операция	Матрица			t	τ	θ
ax				2	1	5
ax+b	1			1	2	4
(ax+b)x		1		2	3	3
X		1	1	1	5	1

(2)

Операция	Матрица			t	τ	θ
ax				2	0	5
ax+b	1			1	2	4
(ax+b)x	1	1		2	2	3
X	1	1	1	1	5	1

(3)

Операция	Матрица			t	τ	θ
ax				2	0	6
ax+b	1			1	2	4
(ax+b)x		1		2	3	3
X			1	1	5	1

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

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

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

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

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

(1) возбуждение нейрона выходного слоя, "отвечающего" за букву О, нормируется с коэффициентом 1/70, а возбуждение нейрона, "отвечающего" за букву А, - с коэффициентом 1/60

(2) возбуждение нейрона выходного слоя, " отвечающего" за букву О, нормируется с коэффициентом 1/50, а возбуждение нейрона, " отвечающего" за букву А, - с коэффициентом 1/70

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

Рассмотрите принципы параллельных вычислений, лежащие в основе асинхронной вычислительной системы. Как обеспечивается виртуальный вычислительный ресурс при много процессорной комплектации системы?

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

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

(3) вычислительный ресурс жестко закреплен за исполнительными устройствами

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

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

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

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

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

Рассмотрите проблемы когерентности кэшей. Как механизм закрытия адресов влияет на механизм когерентности кэшей?

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

(2) c помощью оперативного обмена текущим состоянием всех кэшей

(3) c помощью сравнения времени формирования данных