Параллельное программирование - ответы на тесты Интуит

Главная / Программирование / Параллельное программирование

Процессоры

Комментарий

процессор 1 находит ссылку элемента 2

не найдена ссылка на элемент 2

процессор 2 ликвидирует ссылку элемента 2

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

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

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

Для ВС SPMD-архитектуры, содержащей 4 процессора, составьте таблицу параллельного логического вывода на основе языка ПРОЛОГ по сложной цели, исключающего перебор и backtracking. Мать (марья, Y)

(1)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	мать (марья, Y)	1	X=марья, Y=?
0	родитель (марья, Y)	7
0	родитель (марья, иван)	1	X=марья, Y=иван
1	не проходит унификация	1
2	родитель (марья, василий)	1	X=марья, Y=василий
3	не проходит унификация	1
0	не проходит унификация	1
1	не проходит унификация	1
2	не проходит унификация	1

(2)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	мать (марья, Y)	1	X=марья, Y=?
0	родитель (марья, Y)	7
0	родитель (марья, иван)	1	X=марья, Y=иван
1	родитель (марья, василий)	1	X=марья, Y=василий

(3)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	мать (марья, Y)	1	X=марья, Y=?
0	родитель (марья, Y)	7
1	родитель (марья, иван)	1	X=марья, Y=иван
0	родитель (марья, василий)	1	X=марья, Y=василий

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

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

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

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

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

(1) Выбор семафора С нужного сегмента БД ↓ ЗАКРЫТЬ(С) ↓ Запрос ↓ ОТКРЫТЬ(С)

(2) Выбор семафора С нужного сегмента БД ↓ ЖУЖ(С) ↓ Запрос ↓ ПРОПУСТИТЬ(С)

(3) Выбор семафора С нужного сегмента БД ↓ ЖУЖ(С) ↓ Запрос ↓ ОТКРЫТЬ(С)

Найдите оптимальное расписание выполнения алгоритма задачи, представленного информационным графом. Считая известной производительность Р₀ одного процессора однородной ВС при решении класса вычислительных задач, оцените реальную производительность ВС при решении данной задачи. n=3, G files

(1) 2,1Р₀

(2) 2,3Р₀

(3) 2,8Р₀

Охарактеризуйте отличие современной системы Интернет от Grid-системы. В чем заключается функциональное различие этих систем?

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

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

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

Обсудите возможности минимизации среднего времени обработки запроса к сетевой базе данных. Как достигается минимум среднего времени обработки запроса к БД в сети шинной архитектуры без сервера?

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

(2) реализацией обслуживания по SPMD-технологии, где копии СУБД по разным запросам выполняются независимо на рабочих станциях, а синхронизация взаимно исключающего обращения поддерживается циркуляцией сегментов

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

Определите сложность алгоритма решения задачи. Умножение матриц размерности n

(1) О(n²)

(2) О(n³)

(3) О(n⁴)

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

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

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

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

В пунктах А₁ и А₂ производится продукт в объемах а₁ и а₂ единиц. В пунктах В₁ и В₂ этот продукт потребляется в объемах b₁ и b₂. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта A_iв пункт B_j равны c_ij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны. Формальная постановка задачи: Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₂₁ x₂₁ + c₂₂ x₂₂→ min при ограничениях x₁₁+x₁₂=a₁ x₂₁+x₂₂=a₂ x₁₁+x₂₁=b₁ x₁₂+x₂₂=b₂ при условии неотрицательности решения, x_ij≥ 0, и баланса: a₁+a₂=b₁+b₂. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:

y₁	+y₂		=a₁
		y₃+y₄	=a₂
y₁		+y₃	=b₁
y₁			=0
	y₂		=0
		y₃	=0
		y₄	=0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a₁=0, a₂=100, b₁=50, b₂=50

(1) 1 вариант

(2) 3 варианта

(3) 2 варианта

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(40, 10, 12), B(0, 20, 10), C(20, 0, 16), D(50, 16, 0)

(1) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ 0≤k₁,k₂,k₃,k₄≤1

(2) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(3) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ k₁+k₂+k₃+k₄=1

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

	1	2	3	4	5	6
1		1	1
2
3		1
4		`1`	`1`		`1`	1
5		`1`	1		1
6		`1`	1		1

(1) граф ациклический

(2) третья работа следует сама себе

(3) шестая работа следует сама себе

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

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

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

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

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

(1) организацией мультипрограммной и мультипроцессорной обработки информации

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

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

ВС SPMD-архитектуры, содержащей n= 2 процессоров, найдите ссылку на последний элемент списка N элементов. Воспользуйтесь методом параллельной подстановки ссылок, дающим решение за lg₂N шагов. Непосредственный поиск "нулевой" ссылки производится за ]N/n[ шагов, что может быть значительно дольше. N=8 files

(1)

	Процессор 0	Процессор 1
Цикл 1	1→4	2→3
Цикл 2	3→7	4→5
Цикл 3	5→8	6 нет ссылки

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

(3)

	Процессор 0	Процессор 1
Цикл 1	1→3	2→4
Цикл 2	3→5	4→6
Цикл 3	5→7	6 нет ссылки

В матричных и векторных ВС по "быстрым" связям между топологически соседними процессорами, а также между первым и последним в строке и столбце, приводят к конфликтам. Они возникают в случае, когда необходимо одному процессору передать соседям результаты, уточненные методом сеток. Это - типичная задача "обедающие философы". Закрепите за связями семафоры и составьте схему критического интервала общей для всех процессоров программы взаимного обмена. Проверьте ситуации и убедитесь в отсутствии тупиков. Выделите возможную неординарную ситуацию. Система содержит 4 процессора, связанных в "кольцо". Каждый четный процессор пытается в первую очередь захватить левую связь, а, захватив ее, во вторую очередь пытается захватить правую связь. Нечетные процессоры захватывают правую связь, а затем левую files

(1)

тупиковые и неординарные ситуации отсутствуют

(2)

тупиковые и неординарные ситуации отсутствуют

(3)

тупиковые и неординарные ситуации отсутствуют

Задан коэффициент готовности К_Г процессора ВС. Подберите необходимое число процессоров для обеспечения надежности в "четыре девятки". К_Г=0,95

(1) один процессор основной и три резервных

(2) один процессор основной и четыре резервных

(3) один процессор основной и два резервных

Охарактеризуйте проблемы, возникающие при организации Grid-вычислений. Какие типы запросов определяют функции этой системы?

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

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

(3) запрос на решение произвольной задачи в формальной и неформальной постановке

Каждая РС локальной вычислительной сети располагает копией СУБД. Организован циклический обмен сегментами БД с тактом Т₀ и с количеством т циркулирующих сегментов. Определите целесообразность построения БД с циркулирующей между РС информацией. Т₀ = 0,001 с, m = 100, λ =100(запросов в сек.), μ = 500(запросов в сек.)

(1) неравенство, определяющее целесообразность, не выполняется

(2) целесообразно, т.к. определяющее неравенство выполняется

(3) определилось равенство двух вариантов построения БД

Рассмотрите способы управления обменом в сети типа "шина". Возможно ли централизованное управление обменом?

(1) возможно, тогда физически сеть имеет "шинную" топологию, но логически – "звезда"

(2) централизованное управление обменом невозможно

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

Опишите прямоугольник сетки, включающий данную фигуру files

(1) 1≤x≤11 1≤y≤7

(2) 1≤x≤11 1≤y≤11

(3) 1≤x≤7 1≤y≤11

Пусть Т=8 files

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

(1) n_нижн=2

(2) n_нижн=3

(3) n_нижн=1

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G₁, задачи второго этапа - графом G₂. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности 2δс меньшим приоритетом решаются фоновые задачи, отображенные графом G₃. files

Составьте временную диаграмму решения задач двумя процессорами при децентрализованном управлении вычислительным процессом. Назначение работ выполняйте по решающему правилу: Из тех работ, которые могут выполняться с данного момента времени, в первую очередь назначать более трудоемкие. На первом этапе обслуживания находятся два объекта, на втором этапе - один объект

(1)

(2)

(3)

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

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

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

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

ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 6 элементов, k = 3 files

(1)

	Процессоры						Комментарий
Цикл 1	0	1	2	3			процессор 2 находит ссылку элемента 3
Цикл 2					0	1	процессор 1 находит ссылку на элемент 3
Цикл 3	2	3	0	1
Цикл 4					2	3	процессор3 меняет ссылку на 3 ссылкой на 5

(2)

	Процессоры						Комментарий
Цикл 1	0	1	2	3			процессор 2 находит ссылку элемента 3
Цикл 2					0	1	процессор 1 находит ссылку на элемент 3
Цикл 3	2	3	0	1	2	3	процессор3 меняет ссылку на 3 ссылкой на 5

(3)

	Процессоры						Комментарий
Цикл 1	0	1	2	3			процессор 2 находит ссылку элемента 3 и ссылку на элемент 3
Цикл 2					0	1	процессор 1 меняет ссылку на 3 ссылкой на 5

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

(1)

(2)

(3)

Проанализируйте операции над семафорами. Можно ли двоичный семафор закрывать дважды?

(1) можно, это подтверждает его значение

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

(3) повторное закрытие семафора приводит к прерыванию

Исследуйте проблему надежности ВС в составе сложной управляющей системы. Что понимается под надежностью ВС?

(1) вероятность решения поставленной перед ней задачи

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

(3) значение коэффициента готовности

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

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

(2) многопроцессорными вычислительными системами

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

Локальная сеть содержит два сервера, между которыми поровну распределены рабочие станции. Организована циркуляция сегментов БД между серверами так, что среднее значение t_обсл СУБД одного сервера находится по формуле

\begin{align*}
t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.
\end{align*}

Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т₀ - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, t_обсл - "чистого" времени обслуживания одного запроса в сети. Т₀ = 0,01 с, m= 10сегментов, t_обсл= 0,05 с

(1) ≈0,1 с

(2) ≈0,055 с

(3) ≈0,09 с

Рассмотрите используемый в сети Ethernet метод Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). Что собой представляет Контроль Несущей?

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

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

(3) проверяется возможность обмена при незанятой среде передачи

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

(1) 15 систем, решение определяется системой files

(2) 10 систем, решение определяется системой files

(3) 5 систем, решение определяется системой files

Пусть Т=8 files

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

(1) Т_нижн=7

(2) Т_нижн=6

(3) Т_нижн=8

Исследуйте работу диспетчера. В каком режиме работает диспетчер?

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

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

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

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

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

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

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

С помощью диспетчера последовательного назначения распределите работы, заданные графом G, в неоднородной ВС с известным количеством n₁ и n₂ процессоров разной специализации. Представьте временные диаграммы выполнения работ. n₁=1, n₂=2 files

(1)

T=5

(2)

T=6

(3)

T=6

Рассмотрите возможную альтернативу механизму семафоров. Является ли матрица следования универсальным средством синхронизации, подобным семафорам?

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

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

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

Испытания ВС по пятисуточному прогону контрольной задачи позволили рассчитать основные характеристики надежности: Т₀ - время безотказной работы, Т_восст - время восстановления, P₁(t) - вероятность безотказной работы на протяжении цикла управления, P₂(t) - вероятность сбоя в этом же цикле, P₃(t) - вероятность отказа в этом же цикле, Р_восст - вероятность восстановления вычислительного процесса после сбоя, Р_рез - вероятность перехода на резерв после отказа. Рассчитайте надежность вычислительного процесса. Т₀=8 ч., Т_восст=0,3 ч., λ₁=0,002 (частота сбоев), λ₂=0,0005 (частота отказов), Р_восст=0,5, Р_рез0,99, t=100 с

(1) Р=0,89

(2) Р=0,92

(3) Р=0,84

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

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

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

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

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

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

(2) возможность реализации SPMD-технологии

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

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

Найдите визуально минимальное сечение (максимальную пропускную способность) сети files

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

(2) максимальная пропускная способность сети равна 8

(3) максимальная пропускная способность сети равна 12

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

(1) 5 семафоров

(2) 4 семафора

(3) 3 семафора

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

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

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

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

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 2, 8, 16, 3, 5, 8, 12, 12, 10, 2, 8

(1) время загрузки 29, 29, 30 условных единиц

(2) время загрузки 28, 30, 30 условных единиц

(3) время загрузки 29, 30, 29 условных единиц

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

(1)

(2)

(3)

В многофункциональном АЛУ в решении задачи сортировки участвуют только логические исполнительные устройства, производящие сравнения и пересылки. Определите реальную производительность процессора, если его пиковая производительность составляет Q. Пусть 2 логических ИУ дают коэффициент загрузки 0,8, а 2 ИУ сложения, 2 ИУ умножения и одно ИУ деления простаивают

(1) 0,23Q

(2) 0,43Q

(3) 0,35Q

Охарактеризуйте проблемы, возникающие при решении информационных задач по Grid-технологии. Какую роль при решении информационных задач играет Интернет?

(1) Grid-технология поглощает функции Интернета и расширяет его возможности с помощью мер по расширению области доступности информации при сокращении времени поиска

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

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

СУБД сервера обладает интенсивностью потока обслуживания μ. Суммарный поток запросов к БД в сети, состоящей из 10 РС, составляет λ Определите среднее время выполнения одного запроса.λ =10 (запросов в сек.), μ=20(запросов в сек.)

(1) ≈0,1 с

(2) ≈0,6 с

(3) ≈0,5 с

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

(1) достоинства: отказоустойчивость, бесконфликтное централизованное управление обменом. Недостатки: малое количество РС (до 16), дополнительные затраты на центральный компьютер или сервер от которого зависит мощность всей сети

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

(3) достоинства: отказоустойчивость, бесконфликтное централизованное управление обменом. Недостатки: малое количество РС (до 16), дополнительные затраты на центральный компьютер или сервер от которого зависит мощность всей сети, малая удаленность РС от центрального компьютера

Даны линейные уравнения прямых - граней выпуклого многогранника R допустимых решений, на котором алгоритмически определена некоторая функция f(x, y). Составьте план расчета таблицы значений этой функции методом сеток. Сетку с шагом h формируйте с помощью параметрического описания R -x+2y-10=0 x+y-8=0

(1) вершины многогранника R допустимых решений:О(0, 0),A(0,5),B(2,5),C(7,0). Описание R

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂, k₃, k₄≤1`
`y=0k₁+5k₂+6k₃+0k₄`				`k₁+ k₂= k₃+ k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`h`	`h`	0	`1-2h`
3	`h`	`h`	`h`	`1-3h`
4	`2h`	`h`	`h`	`1-4h`
и т.д.

(2) вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0) Описание R:

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=0k₁+5k₂+6k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	0
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N=1`	0	`h`	0	0
и т.д.

(3) вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0) Описание R:

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`x=0k₁+5k₂+6k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

Найдите ранние и поздние сроки окончания выполнения работ при заданном ограничении времени Т, а также длину критического пути в графе. Т=8 files

(1)

τ₁=2, τ₂=1, τ₃=6, τ₄=4, τ₅=4, τ₆=7, τ₁(8)=3, τ₂(8)=4, τ₃(8)=7, τ₄(8)=7, τ₅(8)=7, τ₆(8)=8, T_кр=7

(2)

τ₁=2, τ₂=1, τ₃=5, τ₄=4, τ₅=4, τ₆=6,  τ₁(8)=3,  τ₂(8)=4,  τ₃(8)=7,  τ₄(8)=7,  τ₂(8)=7,  τ₆(8)=8, T_кр=6

(3)

τ₁=2, τ₂=1, τ₃=6, τ₄=4, τ₅=4, τ₆=7, τ₁(8)=3, τ₂(8)=4, τ₃(8)=7, τ₄(8)=8, τ₅(8)=8, τ₆(8)=8, T_кр=8

ВС содержит 2 процессора. Задачи в реальном времени решаются в циклах длительности δ и 2δ. δ=10 условным единицам времени. Учитывая накладные расходы на управление в одну условную единицу, а также используя принцип мультипрограммирования при решении задач различного относительного приоритета, составьте план загрузки процессоров по графам, отображающим упорядоченность и время выполнения работ в циклах двух длительностей. Рассчитайте коэффициенты загрузки k₁ и k₂ каждого процессора files

(1) k₁=0,8, k₂=0,85

(2) k₁=0,9, k₂=0,8

(3) k₁=0,84, k₂=0,8

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

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

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

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

(4) программные методы контроля правильности вычислений

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

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

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

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

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

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

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

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

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

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

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

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

(3) по результатам системы аппаратного контроля ВС

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

(1) совпадает

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

(3) не совпадает из-за специфичности целей и задач

(Требует творческих размышлений и критического отношения к ответам). Рассмотрите примеры возможных сетевых баз данных с циркулирующей информацией и с простыми запросами (при отсутствии запросов к другим сегментам внутри запроса к одному сегменту. Как может быть реализована БД продажи железнодорожных билетов в виде системы массового обслуживания?

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

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

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

Представьте схему распределения области интегрирования системы дифференциальных уравнений между РС0 и РC1 локальной сети, если в счете решения в каждом узле участвуют решения в соседних узлах. Размер "сетки" - 6×5. Выделите узлы рассчитываемые, общие, узлы, в которых заданы граничные или начальные условия. f_ij=F(f_i-1,j, f_ij, f_i+1,j)

(1)

(2)

(3)

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 5, b = 4 (см. Вариант 1 на рисунке ниже) files

(1) x=7, y=7

(2) x=2, y=8

(3) x=8, y=6

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

(1)

(2)

(3)

Обсудите метод нахождения опорного плана решения задачи линейного программирования. Какое основное предположение лежит в основе метода?

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

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

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

Пусть Т=8 files

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

(1) Т_min=7, дополнительная связь 5 →4

(2) Т_min=8, дополнительная связь 4 →5

(3) Т_min=8, дополнительная связь 5 →3

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

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

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

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

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

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

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

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

(1)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (Х,иван)	1	X=?, Y=иван
0	мужчина (Х), родитель (Х, иван)	5
0	не проходит унификация	1
1	не проходит унификация	1
2	родитель (петр, иван)	1	X=петр, Y=иван
3	не проходит унификация	1
0	не проходит унификация	1
0	не проходит унификация	1

(2)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (Х,иван)	1	X=?, Y=иван
0	мужчина (Х),родитель (Х, иван)	5
1	родитель (петр, иван)	1	X=петр, Y=иван

(3)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (Х,иван)	1	X=?, Y=иван
0	мужчина (Х),родитель (Х, иван)	5
0	родитель (петр, иван)	1	X=петр, Y=иван

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

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

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

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

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

(1)

(2)

(3)

(1) 3,28Р₀

(2) 3,5Р₀

(3) 3,42Р₀

Охарактеризуйте отличие современной системы Интернет от Grid-системы. Какая из этих систем является "надстройкой" для другой?

(1) Grid-система является "надстройкой" Интернет, так как развивает его функции

(2) Grid-система и Интернет - две независимые, параллельно развиваемые системы, использующие общие средства

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

Обсудите возможности минимизации среднего времени обработки запроса к сетевой базе данных. Как достигается минимум среднего времени обращения к БД в сети топологии "звезда" с сервером?

(1) с помощью встречной циклической коммутации сегментов БД с рабочим станциям сети при расположении СУБД на каждой рабочей станции

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

(3) при реализации SPMD-технологии в среде рабочих станций, когда копии СУБД находятся на всех рабочих станциях и выполняются независимо по разным запросам, а сервер обеспечивает поочередное предложение сегментов

(4) с помощью параллельной и независимой (по разным запросам) работой копий СУБД на рабочих станциях при координации и синхронизации запросов к сегментам БД

Определите сложность алгоритма решения задачи. Сложение n элементов массива способом "пирамиды"

(1) О(nlg₂n)

(2) О(n²)

(3) О(n)

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

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

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

В пунктах А₁ и А₂ производится продукт в объемах а₁ и а₂ единиц. В пунктах В₁ и В₂ этот продукт потребляется в объемах b₁ и b₂. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта A_iв пункт B_j равны c_ij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны. Формальная постановка задачи: Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₂₁ x₂₁ + c₂₂ x₂₂→ min при ограничениях x₁₁+x₁₂=a₁ x₂₁+x₂₂=a₂ x₁₁+x₂₁=b₁ x₁₂+x₂₂=b₂ при условии неотрицательности решения, x_ij≥ 0, и баланса: a₁+a₂=b₁+b₂. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:

y₁	+y₂		=a₁
		y₃+y₄	=a₂
y₁		+y₃	=b₁
y₁			=0
	y₂		=0
		y₃	=0
		y₄	=0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a₁=012, a₂=0, b₁=70, b₂=50

(1) 3 варианта

(2) 1 вариант

(3) 2 варианта

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(0, 12, 20), B(0, 20, 10), C(12, 16, 3), D(20, 0, 10)

(1) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(2) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ 0≤k₁,k₂,k₃,k₄≤1,

(3) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ k₁+k₂+k₃+k₄=1

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

	1	2	3	4	5	6
1				1		`1`
2	1		`1`	`1`	1	`1`
3	`1`	1	`1`	`1`	`1`	`1`
4			`1`		`1`	1
5	`1`	`1`	1	`1`	`1`	`1`
6	`1`	`1`	`1`	`1`	1	`1`

(1) граф содержит циклы

(2) граф ациклический

(3) граф содержит единственный цикл

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

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

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

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

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

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

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

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

(1)

	Процессор 0	Процессор 1
Цикл 1	1→2	2→5
Цикл 2	3→4	4→6
Цикл 3	5→8	6→7
Цикл 4	7→10, нет ссылки	8→9

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

(3)

	Процессор 0	Процессор 1
Цикл 1	1→2	2→4
Цикл 2	3→5	4→6
Цикл 3	5→8	6→7
Цикл 4	7→10, нет ссылки	8→9

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

(1)

тупиковые и неординарные ситуации отсутствуют

(2)

тупиковые и неординарные ситуации отсутствуют

(3)

тупиковые и неординарные ситуации отсутствуют

Задан коэффициент готовности К_Г процессора ВС. Подберите необходимое число процессоров для обеспечения надежности в "четыре девятки". К_Г=0,98

(1) один процессор основной и два резервных

(2) один процессор основной и один резервных

(3) один процессор основной и три резервных

Охарактеризуйте проблемы, возникающие при организации Grid-вычислений. В какой степени требуется централизация управления системой Grid-вычислений?

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

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

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

Каждая РС локальной вычислительной сети располагает копией СУБД. Организован циклический обмен сегментами БД с тактом Т₀ и с количеством т циркулирующих сегментов. Определите целесообразность построения БД с циркулирующей между РС информацией. Т₀= 0,001 с, m = 40, λ=180(запросов в сек.), μ = 200 (запросов в сек.)

(1) неравенство, определяющее целесообразность, выполняется

(2) нецелесообразно

(3) одинаково

Рассмотрите способы управления обменом в сети типа "шина". Какими особенностями обладает децентрализованный кодовый приоритетный арбитраж?

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

(2) приоритет назначается динамически в зависимости от объема передаваемой информации

(3) при малой интенсивности обмена все абоненты равноправны, и вероятность конфликтов мала

Опишите прямоугольник сетки, включающий данную фигуру files

(1) 2≤x≤11 2≤y≤9

(2) 2≤x≤10 2≤y≤8

(3) 2≤x≤11 2≤y≤8,5

Пусть Т=8 files

(1) n_нижн=2

(2) n_нижн=1

(3) n_нижн=3

Составьте временную диаграмму решения задач двумя процессорами при децентрализованном управлении вычислительным процессом. Назначение работ выполняйте по решающему правилу: Из тех работ, которые могут выполняться с данного момента времени, в первую очередь назначать более трудоемкие. На первом этапе обслуживания находится один объект, на втором – два объекта

(1)

(2)

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

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

(1) с помощью двух вариантов программы реконфигурации: для головного процессора и для ведомых

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

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

ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 7 элементов, k = 6 files

(1)

	Процессоры							Комментарий
Цикл 1	0	1	2	3				процессор 3 находит ссылку на элемент 6
Цикл 2					0	1	2	процессор 1 находит ссылку элемента 6
Цикл 3	3	0	1	2	3	0	1	процессор 2 находит ссылку на 6 ссылкой на 5

(2)

	Процессоры							Комментарий
Цикл 1	0	1	2	3				процессор 3 находит ссылку на элемент 6
Цикл 2					0	1	2	процессор 1 находит ссылку элемента 6 и меняет ссылку на 6 ссылкой на 5

(3)

	Процессоры							Комментарий
Цикл 1	0	1	2	3	0	1	2	процессор 3 находит ссылку на элемент 6, процессор 1 находит ссылку элемента 6
Цикл 2	3	0	1	2	3	0	1	процессор 2 меняет ссылку на 6 ссылкой на 5

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

(1)

(2)

(3)

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

(1) операция ОТКРЫТЬ, кроме открытия семафора, заставляет все процессы, ранее пытавшиеся закрыть его или выполнить операцию ЖДАТЬ и "висящие" на этом семафоре, повторить эту операцию – закрытия или ожидания. Это необходимо для решения задачи взаимного исключения. Операция ПРОПУСТИТЬ только открывает семафор, что достаточно для соблюдения частичной упорядоченности выполняемых работ

(2) операция ОТКРЫТЬ, кроме открытия семафора, заставляет все процессы, ранее пытавшиеся закрыть его и "висящие" на этом семафоре, повторить эту операцию закрытия. Это необходимо для решения задачи взаимного исключения. Операция ПРОПУСТИТЬ только открывает семафор, что достаточно для соблюдения частичной упорядоченности выполняемых работ

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

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

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

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

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

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

(1) за счет организации Web-серверов и их включения в ассоциацию, осуществляющую циркуляцию сегментов интегрированной памяти

(2) наряду с выполнением запросов на решение задач, центр имеет выход в Интернет

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

\begin{align*}
t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.
\end{align*}

Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т₀ - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, t_обсл - "чистого" времени обслуживания одного запроса в сети. Т₀ = 0,02 с, m= 5сегментов,t_обсл= 0,1 с

(1) ≈0,5 с

(2) ≈0,6 с

(3) ≈0,4 с

Рассмотрите используемый в сети Ethernet метод Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). Что понимается под Множественным Доступом?

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

(2) РС, обнаружив, что передающая среда свободна, запрашивает "центр" на начало обмена

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

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

(1) 10 систем, решение определяется системой files

(2) 5 систем, решение определяется системой files

(3) 10 систем, решение определяется системой files

Пусть Т=8 files

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

(1) Т_нижн=8

(2) Т_нижн=9

(3) Т_нижн=10

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

(1) запуск диспетчера на каждом процессоре обеспечивает его автономную загрузку работами

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

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

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

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

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

(3) время поиска сокращается незначительно

С помощью диспетчера последовательного назначения распределите работы, заданные графом G, в неоднородной ВС с известным количеством п1 и п2 процессоров разной специализации. Представьте временные диаграммы выполнения работ.n₁=2, n₂=1 files

(1)

T=4

(2)

T=6

(3)

T=6

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

(1) являются

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

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

Испытания ВС по пятисуточному прогону контрольной задачи позволили рассчитать основные характеристики надежности: Т₀ - время безотказной работы, Т_восст - время восстановления, P₁(t) - вероятность безотказной работы на протяжении цикла управления, P₂(t) - вероятность сбоя в этом же цикле, P₃(t) - вероятность отказа в этом же цикле, Р_восст - вероятность восстановления вычислительного процесса после сбоя, Р_рез - вероятность перехода на резерв после отказа. Рассчитайте надежность вычислительного процесса. Т₀=8 ч., Т_восст=0,2 ч., λ₁=0,001 (частота сбоев), λ₂=0,0006 (частота отказов), Р_восст=0,7, Р_рез0,98, t=100 с

(1) Р=0,9504

(2) Р=0,9807

(3) Р=0,9702

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

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

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

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

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

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

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

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

Найдите визуально минимальное сечение (максимальную пропускную способность) сети files

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

(2) максимальная пропускная способность сети равна 10

(3) максимальная пропускная способность сети равна 11

(1) 4 семафора

(2) 6 семафоров

(3) 5 семафоров

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

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

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

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

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 6, 4, 3, 5, 8, 5, 4, 7, 8, 3, 5, 6

(1) время загрузки 22, 21, 21 условных единиц

(2) время загрузки 21, 22, 21 условных единиц

(3) время загрузки 21, 20, 22 условных единиц

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

(1)

(2)

(3)

В многофункциональном АЛУ в решении задачи сортировки участвуют только логические исполнительные устройства, производящие сравнения и пересылки. Определите реальную производительность процессора, если его пиковая производительность составляет Q. Пусть 4 логических ИУ дают коэффициент загрузки 0,8, а 2 ИУ сложения, одно ИУ умножения и одно ИУ деления простаивают

(1) 0,4Q

(2) 0,44Q

(3) 0,38Q

Охарактеризуйте проблемы, возникающие при решении информационных задач по Grid-технологии. Требует ли Grid-технология централизации управления мировой информационной системой?

(1) требует организации "встречного" движения информации по участвующим серверам, объединенным в ассоциацию

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

(3) вся мировая информация должна управляться органом, подчиняющимся ООН

СУБД сервера обладает интенсивностью потока обслуживания μ. Суммарный поток запросов к БД в сети, состоящей из 10 РС, составляет λ Определите среднее время выполнения одного запроса. λ =5 (запросов в сек.), μ=20(запросов в сек.)

(1) ≈0,606 с

(2) ≈0,08 с

(3) ≈0,0705 с

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

(1) достоинства: количество РС может превышать 1000, сочетание централизованного обмена с децентрализованным, значительная протяженность линий связи. Недостатки: отказ одной РС может вывести из строя всю сеть, сложность подключения РС, обменом связаны только соседние РС

(2) достоинства: сочетание централизованного обмена с децентрализованным, значительная протяженность линий связи. Недостатки: отказ одной РС может вывести из строя всю сеть, количество РС не превышает 32, сложность подключения РС, обменом связаны только соседние РС

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

В "плоской" задаче линейного программирования многогранник допустимых решений имеет вид, представленный на рисунке. Его ребра обусловлены ограничениями и условиями. Ограничения, при замене указанных в них неравенств на равенство, порождают границы q, обозначающие уравнения прямой. Показана прямая - возможный график целевой функции при заданном или испытываемом еезначении. Параллельное перемещение графика целевой функции в сторону еевозрастания показано стрелкой. Найдите графически решение задачи линейного программирования files

(1) решение (максимум значения целевой функции) достигается в точке С

(2) решение - в точке А

(3) решение достигается на всем отрезке [C, D]

Даны линейные уравнения прямых - граней выпуклого многогранника R допустимых решений, на котором алгоритмически определена некоторая функция f(x, y). Составьте план расчета таблицы значений этой функции методом сеток. Сетку с шагом h формируйте с помощью параметрического описания R -x+3y-14=0 x=y-6=0

(1) вершины многогранника R допустимых решений: О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=0k₁+0k₂+1k₃+6k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y = 0k₁+6k₂+5k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

(2) вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=0k₁+0k₂+1k₃+6k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y = 0k₁+ 6k₂+ 5k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	0
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N+1`	0	`h`	0	0
и т.д.

(3) вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=1k₃+6k₄`				`0≤k₂,k₃,k₄≤1`
`y=6k₂+5k₃+0k₄`	`k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₂`	`k₃`	`k₄`
0	0	0	1
1	`h`	0	`1-h`
2	`2h`	0	`1-2h`
..........
`N`	`Nh`	0	`1-Nh`
`N+1`	0	`h`	`1-h`
и т.д.

(1)

τ₁=2, τ₂=5, τ₃=3, τ₄=5, τ₅=5, τ₆=6, τ₁(8)=4, τ₂(8)=8, τ₃(8)=6, τ₄(8)=7, τ₅(8)=8, τ₆(8)=6, T_кр=6

(2)

τ₁=2, τ₂=4, τ₃=4, τ₄=4, τ₅=4, τ₆=6, τ₁(8)=4, τ₂(8)=7, τ₃(8)=6, τ₄(8)=7, τ₅(8)=7, τ₆(8)=6, T_кр=7

(3)

τ₁=2, τ₂=5, τ₃=5, τ₄=4, τ₅=5, τ₆=6, τ₁(8)=4, τ₂(8)=8, τ₃(8)=7, τ₄(8)=7, τ₅(8)=8, τ₆(8)=7, T_кр=7

ВС содержит 2 процессора. Задачи в реальном времени решаются в циклах длительности δ и 2δ. δ = 10 условным единицам времени. Учитывая накладные расходы на управление в одну условную единицу, а также используя принцип мультипрограммирования при решении задач различного относительного приоритета, составьте план загрузки процессоров по графам, отображающим упорядоченность и время выполнения работ в циклах двух длительностей. Рассчитайте коэффициенты загрузки k₁ и k₂ каждого процессора files

(1) k₁=0,7, k₂=0,9

(2) k₁=0,75, k₂=0,85

(3) k₁=0,8, k₂=0,9

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

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

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

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

Какие элементы точного решения задач распараллеливания целесообразно применять при построении диспетчеров для однородных ВС?

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

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

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

Исследуйте некоторые приемы, применяющиеся при решении задач синхронизации. Чем и почему отличаются версии критического интервала "писателя" в задачах ЧП1 и ЧП2?

(1) в задаче ЧП1 процесс "писатель" начинается с команды ЖДАТЬ ПО СЧИТЫВАНИЮ, что позволяет процессам - "читателям" не только успешно завершиться, но допускает поступление новых "читателей", пока семафор-счетчик не стал равен нулю. В задаче ЧП2 процесс "писатель" начинается с команды ЗАКРЫТЬ ПО ЗАПИСИ, что разрешает только успешное завершение процессов "читатель"

(2) в задаче ЧП2 процесс "писатель" начинается с команды ЖДАТЬ ПО СЧИТЫВАНИЮ, что позволяет процессам - "читателям" не только успешно завершиться, но допускает поступление новых "читателей", пока семафор-счетчик не стал равен нулю. В задаче ЧП1 процесс "писатель" начинается с команды ЗАКРЫТЬ ПО ЗАПИСИ, что разрешает только успешное завершение процессов "читатель"

(3) в задаче ЧП1 процесс "писатель" начинается с команды ЖДАТЬ ПО СЧИТЫВАНИЮ, что позволяет процессам - "читателям" успешно завершиться, не допуская поступление новых "читателей" , пока семафор-счетчик не стал равен нулю. В задаче ЧП2 процесс "писатель" начинается с команды ЗАКРЫТЬ ПО ЗАПИСИ, что разрешает не только успешное завершение процессов "читатель" , но допускает поступление новых " читателей" , пока семафор-счетчик не стал равен нулю

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

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

(2) он устраняет все последствия сбоя с помощью большого рестарта

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

Рассмотрите возможности применения параллельных информационных технологий в Grid-технологиях. Применимы ли диспетчеры динамического распараллеливания работ в системе Grid-вычислений?

(1) применимы

(2) неприменимы

(3) применимы частично

(Требует творческих размышлений и критического отношения к ответам). Рассмотрите примеры возможных сетевых баз данных с циркулирующей информацией и с простыми запросами (при отсутствии запросов к другим сегментам внутри запроса к одному сегменту. Как может быть организована БД обслуживания читателей в университетской библиотеке?

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

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

(3) общая база данных библиотеки разбивается на частные базы данных по режимам обслуживания и типам запросов: на БД каталогов, фондов, учебно-методической литературы, периодики, новостей и т.д. Способ функционирования каждой БД в сети, для минимизации среднего времени обращения, выбирается на основе моделирования потока запросов

(1)

(2)

(3)

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 9, b = 2 (см. Вариант 2 на рисунке ниже) files

(1) x=7, y=7

(2) x=8, y=5

(3) x=8, y=4

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

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

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

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

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

(1) в n-мерном пространстве (n>3) не определено понятие угла, а косинус, определяемый с помощью скалярного произведения, не является монотонно возрастающей функцией меры

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

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

Пусть Т=8 files

(1) Т_min=8, дополнительные связи 3 →2, 4 →2

(2) Т_min=7, дополнительные связи 3 →4, 5 →2

(3) Т_min=8, дополнительные связи 3 →4, 2 →5

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

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

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

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

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

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

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

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

(1)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (иван, Y)	1	X= иван, Y=?
0	родитель (иван, Y)	7
0	не проходит унификация	1
1	родитель (иван, елена)	1	X= иван, Y= елена
2	не проходит унификация	1
3	не проходит унификация	1
0	не проходит унификация	1
1	не проходит унификация	1
2	не проходит унификация	1

(2)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (иван, Y)	1	X= иван, Y=?
0	родитель (иван, Y)	7
1	родитель (иван, елена)	1	X= иван, Y= елена

(3)

Обрабатывающий процессор	Фрейм	Счетчик	Связывание переменных
	отец (иван, Y)	1	X= иван, Y=?
0	родитель (иван, Y)	7
0	родитель (иван, елена)	1	X= иван, Y= елена

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

(1) 2,33Р₀

(2) 3,55Р₀

(3) 3,12Р₀

Охарактеризуйте отличие современной системы Интернет от Grid-системы. Требует ли Grid-технология централизованных планирующих органов обслуживания?

(1) обслуживание запросов на выполнение Grid-вычислений может быть реализовано по принципу работы поисковой системы в Интернете

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

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

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

(1) "клиенты" разбиваются на равные группы, связанные со своим сервером. Копии СУБД имеются на каждой РС. Сервера циклически обмениваются сегментами БД, обеспечивая непосредственный доступ (с возможным ожиданием) всех РС ко всем сегментам и синхронизацию при взаимно исключающем обращении к сегментам

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

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

Определите сложность алгоритма решения задачи. Перебор и решение комбинаций по т линейных уравнений из множества n таких уравнений, если известно, что функция C_n^m растет быстрее, чем 2ⁿ, которая принимается за нижнюю оценку

(1) О(n²2ⁿ)

(2) О(n³)

(3) O(n2ⁿ)

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

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

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

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

y₁	+y₂		=a₁
		y₃+y₄	=a₂
y₁		+y₃	=b₁
y₁			=0
	y₂		=0
		y₃	=0
		y₄	=0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a₁=60, a₂=40, b₁=50, b₂=50

(1) 4 варианта

(2) 6 вариантов

(3) 10 вариантов

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(5, 12, 8), B(0, 16, 12), C(20, 16, 7), D(0, 4, 18)

(1) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(2) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ 0≤k₁,k₂,k₃,k₄≤1,

(3) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ k₁+k₂+k₃+k₄=1

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

	1	2	3	4	5	6
1		`1`	1	`1`
2			`1`		1
3		1	`1`	1	`1`
4						1
5		`1`	1	`1`/	1
6		1	`1`	1	`1`

(1) граф содержит циклы

(2) граф ациклический

(3) третья работа следует сама себе

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

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

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

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

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

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

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

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

(1)

	Процессор 0	Процессор 1
Цикл 1	1→4	2→5
Цикл 2	3→2	4→6
Цикл 3	5→7	6→8
Цикл 4	7→9	8→11
Цикл 5	9→12	10, нет ссылки

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

(3)

	Процессор 0	Процессор 1
Цикл 1	1→4	2→5
Цикл 2	3→2	4→6
Цикл 3	5→7	6→8
Цикл 4	7→9	8→10, "пустая ссылка"

В матричных и векторных ВС по "быстрым" связям между топологически соседними процессорами, а также между первым и последним в строке и столбце, приводят к конфликтам. Они возникают в случае, когда необходимо одному процессору передать соседям результаты, уточненные методом сеток. Это - типичная задача "обедающие философы". Закрепите за связями семафоры и составьте схему критического интервала общей для всех процессоров программы взаимного обмена. Проверьте ситуации и убедитесь в отсутствии тупиков. Выделите возможную неординарную ситуацию. ВС содержит 5 процессоров, связанных в "кольцо". Четные процессоры пытаются в первую очередь захватить левую связь, затем правую. Нечетные процессоры сначала захватывают правую связь, затем левую files

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

(2)

тупиковые ситуации отсутствуют. Время обмена между четными соседями отличается от времени обмена между четными и нечетными соседями

(3)

Задан коэффициент готовности К_Г процессора ВС. Подберите необходимое число процессоров для обеспечения надежности в "четыре девятки". К_Г=0,99

(1) один процессор основной и два резервных

(2) один процессор основной и один резервных

(3) один процессор основной и три резервных

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

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

(2) локальные вычислительные сети

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

Каждая РС локальной вычислительной сети располагает копией СУБД. Организован циклический обмен сегментами БД с тактом Т₀ и с количеством т циркулирующих сегментов. Определите целесообразность построения БД с циркулирующей между РС информацией. Т₀ = 0,0005 с, m = 50, λ=350(запросов в сек.), μ = 400 (запросов в сек.)

(1) целесообразно

(2) нецелесообразно

(3) одинаково

Рассмотрите способы управления обменом в сети типа "шина". Какими особенностями обладает децентрализованный временной приоритетный арбитраж (метод доступа)?

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

(2) квант времени доступа к шине распределяется в соответствии с плавающим приоритетом абонентов

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

Опишите прямоугольник сетки, включающий данную фигуру files

(1) 1≤x≤9 1≤y≤8

(2) 1,5≤x≤9 1,3≤y≤7,6

(3) 1,2≤x≤9 1,4≤y≤7,5

Пусть Т=7 files

(1) n_нижн=2

(2) n_нижн=1

(3) n_нижн=3

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

(1)

(2)

(3)

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

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

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

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

ВС SPMD-архитектура содержит 4 процессора. Изобразите схему параллельного поиска и исключения из списка элемента с номером k. Список содержит 5 элементов, k = 2 files

(1)

(2)

	Процессоры					Комментарий
Цикл 1	0	1	2	3	0	процессор 1 находит ссылку элемента 2
Цикл 2	1	2	3			процессор 2 ликвидирует ссылку элемента 2

(3)

	Процессоры					Комментарий
Цикл 1	0	1	2	3		процессор 1 находит ссылку элемента 2, но, не найдя ссылку на элемент 2, ликвидирует ссылку этого элемента

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

(1)

(2)

(3)

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

(1) в вычислительном комплексе на базе локальной сети

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

(3) при решении геодезических, метеорологических задач, при моделировании диффузных сред и др.

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

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

(2) вероятностью обнаружения сбоев и достоверностью результатов счета

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

Рассмотрите функции, выполняемые типовым центром Grid-технологий. Какие запросы пользователей он выполняет?

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

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

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

\begin{align*}
t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.
\end{align*}

Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т₀ - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, t_обсл - "чистого" времени обслуживания одного запроса в сети. Т₀ = 0,001 с, m= 50сегментов,t_обсл= 0,06 с

(1) ≈0,085 с

(2) ≈0,156 с

(3) ≈0,001 с

Рассмотрите используемый в сети Ethernet метод Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). В чем суть Обнаружения Столкновений (Коллизий)?

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

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

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

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

(1) 15 систем, решение определяется системой files

(2) 10 систем, решение определяется системой files

(3) 5 систем, решение определяется системой files

Пусть Т=7 files

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

(1) Т_нижн=6

(2) Т_нижн=5

(3) Т_нижн=7

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

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

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

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

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

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

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

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

(1)

T=5

(2)

T=6

(3)

T=6

Рассмотрите возможную альтернативу механизму семафоров. Является ли механизм закрытия адресов универсальным средством синхронизации, способным заменить семафоры?

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

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

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

Испытания ВС по пятисуточному прогону контрольной задачи позволили рассчитать основные характеристики надежности: Т₀ - время безотказной работы, Т_восст - время восстановления, P₁(t) - вероятность безотказной работы на протяжении цикла управления, P₂(t) - вероятность сбоя в этом же цикле, P₃(t) - вероятность отказа в этом же цикле, Р_восст - вероятность восстановления вычислительного процесса после сбоя, Р_рез - вероятность перехода на резерв после отказа. Рассчитайте надежность вычислительного процесса. Т₀=100 ч., Т_восст=1 ч., λ₁=0,002 (частота сбоев), λ₂=0,0004 (частота отказов), Р_восст=0,6, Р_рез0,999, t=100 с

(1) Р=0,832

(2) Р=0,843

(3) Р=0,899

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

(1) программы сортировки, поиска, логического вывода, оболочки параллельного ПРОЛОГа, оболочки расчета величины возбуждения нейронов нейросети

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

(3) программы сортировки, поиска, логического вывода, параллельного ПРОЛОГа, расчета величины возбуждения нейронов нейросети

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

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

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

(3) предпочтительно формировать на базе РС регулярные решетки, подобно матричным. Это позволяет организовать бесконфликтный обмен по направлениям

Найдите визуально минимальное сечение (максимальную пропускную способность) сети files

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

(2) максимальная пропускная способность сети равна 12

(3) максимальная пропускная способность сети равна 13

(1) 6 семафоров

(2) 10 семафоров

(3) 5 семафоров

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

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

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

(3) по прошествии контрольного времени формируется повторный запрос пользователя

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 1, 2, 2, 8, 5, 8, 6, 2, 3, 4, 7, 3

(1) время загрузки 17, 17, 17 условных единиц

(2) время загрузки 16, 18, 17 условных единиц

(3) время загрузки 17, 16, 18 условных единиц

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

(1)

(2)

(3)

В многофункциональном АЛУ в решении задачи сортировки участвуют только логические исполнительные устройства, производящие сравнения и пересылки. Определите реальную производительность процессора, если его пиковая производительность составляет Q. Пусть 3 логических ИУ дают коэффициент загрузки 0,9, а одно ИУ сложения, одно ИУ умножения и одно ИУ деления простаивают

(1) 0,45Q

(2) 0,47Q

(3) 0,39Q

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

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

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

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

СУБД сервера обладает интенсивностью потока обслуживания μ. Суммарный поток запросов к БД в сети, состоящей из 10 РС, составляет λ Определите среднее время выполнения одного запроса. λ =12 (запросов в сек.), μ=120(запросов в сек.)

(1) ≈0,056 с

(2) ≈0,06 с

(3) ≈0,046 с

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

(1) достоинства: отказоустойчивость, комплектация превышает 1000 РС, количество абонентов легко изменяется, дешевая среда передачи данных, децентрализованное управление обменом. Недостатки: значительные объемы трафика уменьшают пропускную способность обмена, затруднена локализация отказов

(2) достоинства: отказоустойчивость, комплектация превышает 1000 РС, количество абонентов легко изменяется, дешевая среда передачи данных, централизованное управление обменом. Недостатки: значительные объемы трафика уменьшают пропускную способность обмена, затруднена локализация отказов

(3) достоинства: отказоустойчивость, комплектация превышает 1000 РС, количесво абонентов легко изменяется, дешевая среда передачи данных, децентрализованное управление обменом, эффективная диагностика отказов. Недостатки: значительные объемы трафика уменьшают пропускную способность обмена

(1) решение достигается в точке А

(2) решение достигается в точке Е

(3) решение достигается на отрезке [A, E]

(1) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=0k₁+0k₂+10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂+0k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

(2) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=0k₁+0k₂+10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂+0k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`h`	`h`	0	`1-2h`
3	`h`	`h`	`h`	`1-3h`
`4`	`2h`	`h`	`h`	`1-4h`
и т.д.

(3) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂`				`k₁+ k₂+ k₃+ k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N+1`	0	`h`	0	0
и т.д.

Найдите ранние и поздние сроки окончания выполнения работ при заданном ограничении времени Т, а также длину критического пути в графе. Т=7 files

(1)

τ₁=2, τ₂=1, τ₃=4, τ₄=4, τ₅=5, τ₆=4, τ₁(7)=3, τ₂(7)=4, τ₃(7)=5, τ₄(7)=6, τ₅(7)=7, τ₆(7)=7, T_кр=5

(2)

τ₁=2, τ₂=1, τ₃=5, τ₄=4, τ₅=4, τ₆=5, τ₁(7)=3, τ₂(7)=4, τ₃(7)=5, τ₄(7)=7, τ₅(7)=7, τ₆(7)=7, T_кр=6

(3)

τ₁=2, τ₂=1, τ₃=6, τ₄=4, τ₅=4, τ₆=5, τ₁(7)=3, τ₂(7)=4, τ₃(7)=7, τ₄(7)=8, τ₅(7)=8, τ₆(7)=8, T_кр=6

(1) k₁=0,85, k₂=0,75

(2) k₁=0,95, k₂=0,8

(3) k₁=0,85, k₂=0,85

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

(1) поочередное выполнение процессорами функций головного

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

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

Какие элементы точного решения задач распараллеливания целесообразно применять при построении диспетчеров для неоднородных ВС?

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

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

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

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

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

(2) при каждом изменении индикатора заполнения проверяется: достиг ли он значения индикатора считывания? Если достиг, запись не производится

(3) при каждом изменении индикатора считывания проверяется: достиг ли он значения индикатора заполнения? Если достиг, считывание не производится

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

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

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

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

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

(1) минимум времени выполнения запроса

(2) предоставление минимума стоимости необходимого ресурса

(3) максимальное качество сервисного обслуживания

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

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

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

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

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

(1)

(2)

(3)

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 1, b = 2 (см. Вариант 3 на рисунке ниже) files

(1) x=7, y=7

(2) x=8, y=7

(3) x=7, y=8

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

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

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

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

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

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

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

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

Пусть Т=7 files

(1) Т_min=6, дополнительная связь 3 →6

(2) Т_min=7, дополнительная связь 4 →3

(3) Т_min=6, дополнительная связь 4 →6

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(1) решение достигается в точке D

(2) решение достигается на отрезке [A, B]

(3) решение достигается в точке С

Рассмотрите возможную альтернативу механизму семафоров. Является ли механизм активного ожидания универсальным средством синхронизации, способным заменить семафоры?

(1) да, является, т.к. полная реализация механизма семафоров в МВК "Эльбрус" полностью опирается на использование этого механизма

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

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

Определите сложность алгоритма решения задачи. Цикл заполнения двоичного счетчика времени на регистре, содержащем n разрядов

(1) О(2ⁿ)

(2) О(n)

(3) O(nlg₂n)

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

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

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

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

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

Обсудите метод нахождения опорного плана решения задачи линейного программирования. Что является основой алгоритма нахождения вершины многогранника допустимых решений?

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

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

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

Исследуйте возможную организацию параллельных вычислений. Могут ли предложенные в лекции 20 методы точного решения задач распараллеливания быть основой построения диспетчеров в составе ОС ВС?

(1) могут

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

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

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

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

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

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

	1	2	3	4	5	6
1				1		`1`
2	1		`1`	`1`	1	`1`
3	`1`	1	`1`	`1`	`1`	`1`
4			`1`		`1`	1
5	`1`	`1`	1	`1`	`1`	`1`
6	`1`	`1`	`1`	`1`	1	`1`

	1	2	3	4	5	6
1				1		`1`
2	1		`1`	`1`	1	`1`
3	`1`	1	`1`	`1`	`1`	`1`
4			`1`		`1`	1
5	`1`	`1`	1	`1`	`1`	`1`
6	`1`	`1`	`1`	`1`	1	`1`

	1	2	3	4	5	6
1				1		`1`
2	1		`1`	`1`	1	`1`
3	`1`	1	`1`	`1`	`1`	`1`
4			`1`		`1`	1
5	`1`	`1`	1	`1`	`1`	`1`
6	`1`	`1`	`1`	`1`	1	`1`