Ответы к контрольной работе: Параллельное программирование

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

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

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

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

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

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

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

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

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

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

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

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

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

В пунктах А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=a1y3+y4=a2y1+y3=b1y1=0y2=0y3=0y4=0Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a1=60, a2=40, b1=50, b2=50

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В пунктах А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=a1y3+y4=a2y1+y3=b1y1=0y2=0y3=0y4=0Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? a1=012, a2=0, b1=70, b2=50

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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