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

Количество вопросов - 201

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

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

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

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

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

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

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

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

Локальная сеть содержит два сервера, между которыми поровну распределены рабочие станции. Организована циркуляция сегментов БД между серверами так, что среднее значение tобсл СУБД одного сервера находится по формуле
\begin{align*}t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.\end{align*}
Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т0 - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, tобсл - "чистого" времени обслуживания одного запроса в сети. Т0 = 0,02 с, m= 5сегментов,tобсл= 0,1 с

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Локальная сеть содержит два сервера, между которыми поровну распределены рабочие станции. Организована циркуляция сегментов БД между серверами так, что среднее значение tобсл СУБД одного сервера находится по формуле
\begin{align*}t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.\end{align*}
Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т0 - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, tобсл - "чистого" времени обслуживания одного запроса в сети. Т0 = 0,001 с, m= 50сегментов,tобсл= 0,06 с

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

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

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

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

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

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

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

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

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

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

В пунктах А1 и А2 производится продукт в объемах а1 и а2 единиц. В пунктах В1 и В2 этот продукт потребляется в объемах b1 и b2. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj равны cij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.Формальная постановка задачи:
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 
при ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2
при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1+y2=a1
y3+y4=a2
y1+y3=b1
y1=0
y2=0
y3=0
y4=0
Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a1=0, a2=100, b1=50, b2=50

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

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

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

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

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

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

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

123456
1111
211
31111
41
5111/1
61111

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

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

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

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

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

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

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G1, задачи второго этапа - графом G2. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности с меньшим приоритетом решаются фоновые задачи, отображенные графом G3. Составьте временную диаграмму решения задач двумя процессорами при децентрализованном управлении вычислительным процессом. Назначение работ выполняйте по решающему правилу: Из тех работ, которые могут выполняться с данного момента времени, в первую очередь назначать более трудоемкие. На первом и втором этапах обслуживания находится по одному объекту

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

123456
111
211111
3111111
4111
5111111
6111111

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Локальная сеть содержит два сервера, между которыми поровну распределены рабочие станции. Организована циркуляция сегментов БД между серверами так, что среднее значение tобсл СУБД одного сервера находится по формуле
\begin{align*}t^*_{\text{обсл}} = \frac{T_0(m-1)}{2} + t_{\text{обсл}}.\end{align*}
Рассчитайте значение среднего времени обслуживания запроса с учетом циркуляции сегментов между серверами для заданных значений Т0 - времени такта системы, при котором происходит обмен одним сегментом, m - числа сегментов БД, tобсл - "чистого" времени обслуживания одного запроса в сети. Т0 = 0,01 с, m= 10сегментов, tобсл= 0,05 с

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

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

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

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

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

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

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

123456
111
2
31
41111
5111
611

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

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

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

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

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

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

В пунктах А1 и А2 производится продукт в объемах а1 и а2 единиц. В пунктах В1 и В2 этот продукт потребляется в объемах b1 и b2. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj равны cij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.Формальная постановка задачи:
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 
при ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2
при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1+y2=a1
y3+y4=a2
y1+y3=b1
y1=0
y2=0
y3=0
y4=0
Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a1=012, a2=0, b1=70, b2=50

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G1, задачи второго этапа - графом G2. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности с меньшим приоритетом решаются фоновые задачи, отображенные графом G3.Составьте временную диаграмму решения задач двумя процессорами при децентрализованном управлении вычислительным процессом. Назначение работ выполняйте по решающему правилу: Из тех работ, которые могут выполняться с данного момента времени, в первую очередь назначать более трудоемкие. На первом этапе обслуживания находятся два объекта, на втором этапе - один объект

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

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

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

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

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

В пунктах А1 и А2 производится продукт в объемах а1 и а2 единиц. В пунктах В1 и В2 этот продукт потребляется в объемах b1 и b2. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj равны cij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.Формальная постановка задачи:
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 
при ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2
при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1+y2=a1
y3+y4=a2
y1+y3=b1
y1=0
y2=0
y3=0
y4=0
Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a1=60, a2=40, b1=50, b2=50

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

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

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

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

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

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G1, задачи второго этапа - графом G2. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности с меньшим приоритетом решаются фоновые задачи, отображенные графом G3. Составьте временную диаграмму решения задач двумя процессорами при децентрализованном управлении вычислительным процессом. Назначение работ выполняйте по решающему правилу: Из тех работ, которые могут выполняться с данного момента времени, в первую очередь назначать более трудоемкие. На первом этапе обслуживания находится один объект, на втором – два объекта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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