Ответы на вопросы из коллекции "Параллельное программирование"

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

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

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

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

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

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

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

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

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

• сеть эффективно может реализовать только метод сеток, включая метод конечных разностей
• метод вычислений должен допускать разбиение на множество частично упорядоченных работ, объем которых значительно превышает необходимое время обмена
• метод вычислений должен предполагать возможность применения SPMD-технологии

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

• 0,35Q
• 0,43Q
• 0,23Q

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

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

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

• 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 с

• Р=0,84
• Р=0,92
• Р=0,89

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

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

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

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

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

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

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

• Обрабатывающий процессорФреймСчетчикСвязывание переменных мать (марья, Y)1 X=марья, Y=?0родитель (марья, Y)70родитель (марья, иван)1X=марья, Y=иван1родитель (марья, василий)1X=марья, Y=василий
• Обрабатывающий процессорФреймСчетчикСвязывание переменных мать (марья, Y) 1 X=марья, Y=?0родитель (марья, Y)70родитель (марья, иван)1X=марья, Y=иван1не проходит унификация12родитель (марья, василий)1X=марья, Y=василий3не проходит унификация10не проходит унификация11не проходит унификация12не проходит унификация1
• Обрабатывающий процессорФреймСчетчикСвязывание переменных мать (марья, Y)1 X=марья, Y=?0родитель (марья, Y)71родитель (марья, иван)1X=марья, Y=иван0родитель (марья, василий)1X=марья, 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

• 4 варианта
• 6 вариантов
• 10 вариантов

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

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

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

• наряду с выполнением запросов на решение задач, центр имеет выход в Интернет
• центр занимается только решением задач пользователей, существуя вне Интернет
• за счет организации Web-серверов и их включения в ассоциацию, осуществляющую циркуляцию сегментов интегрированной памяти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• x=5k1+20k3y=12k1+16k2+16k3+4k4z=8k1+12k2+16k3+18k40≤k1,k2,k3,k4≤1, k1+k2+k3+k4=1
• x=5k1+20k3y=12k1+16k2+16k3+4k4z=8k1+12k2+16k3+18k40≤k1,k2,k3,k4≤1,
• x=5k1+20k3y=12k1+16k2+16k3+4k4z=8k1+12k2+16k3+18k4k1+k2+k3+k4=1

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

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

• 3 варианта
• 2 варианта
• 1 вариант

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

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

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

• O(n2n)
• О(n22n)
• О(n3)

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

• ≈0,0705 с
• ≈0,606 с
• ≈0,08 с

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

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

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

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

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

• шестая работа следует сама себе
• граф ациклический
• третья работа следует сама себе

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

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

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

• вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0)Описание Rx=0k1+0k2+10k3+1k40≤k1,k2,k3,k4≤1y=1k1+10k2+0k3+0k4k1+k2+k3+k4=1Перебор точек RТочкиk1k2k3k4000011h001-h22h001-2h..........NNh001-NhN+10h01-hи т.д.
• вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0)Описание Rx=10k3+1k40≤k1,k2,k3,k4≤1y=1k1+10k2k1+ k2+ k3+ k4=1Перебор точек RТочкиk1k2k3k4000011h00022h000..........NNh000N+10h00и т.д.
• вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0)Описание Rx=0k1+0k2+10k3+1k40≤k1,k2,k3,k4≤1y=1k1+10k2+0k3+0k4Перебор точек RТочкиk1k2k3k4000011h001-h2hh01-2h3hhh1-3h42hhh1-4hи т.д.

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

• O(nlg2n)
• О(n)
• О(2n)

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

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

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

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

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

• один процессор основной и три резервных
• один процессор основной и два резервных
• один процессор основной и один резервных

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

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

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

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

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

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

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

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

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

• не требует, все должно оставаться на традиционном уровне, естественным образом воплощенном в Интернете
• вся мировая информация должна управляться органом, подчиняющимся ООН
• требует организации "встречного" движения информации по участвующим серверам, объединенным в ассоциацию

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

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

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

• один процессор основной и четыре резервных
• один процессор основной и три резервных
• один процессор основной и два резервных

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

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

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

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

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

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

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

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

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

• вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0)Описание Rx=1k3+6k40≤k2,k3,k4≤1y=6k2+5k3+0k4k2+k3+k4=1Перебор точек RТочкиk2k3k400011h01-h22h01-2h..........NNh01-NhN+10h1-hи т.д.
• вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0)Описание Rx=0k1+0k2+1k3+6k40≤k1,k2,k3,k4≤1y = 0k1+ 6k2+ 5k3+0k4Перебор точек RТочкиk1k2k3k4000001h00022h000..........NNh000N+10h00и т.д.
• вершины многогранника R допустимых решений: О(0, 0), A(0, 6), B(1, 5), C(6, 0)Описание Rx=0k1+0k2+1k3+6k40≤k1,k2,k3,k4≤1y = 0k1+6k2+5k3+0k4k1+k2+k3+k4=1Перебор точек RТочкиk1k2k3k4000011h001-h22h001-2h..........NNh001-NhN+10h01-hи т.д.

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

• x=40k1+20k3+50k4y=10k1+20k2+16k4z=12k1+10k2+16k3k1+k2+k3+k4=1
• x=40k1+20k3+50k4y=10k1+20k2+16k4z=12k1+10k2+16k30≤k1,k2,k3,k4≤1, k1+k2+k3+k4=1
• x=40k1+20k3+50k4y=10k1+20k2+16k4z=12k1+10k2+16k30≤k1,k2,k3,k4≤1

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

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

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

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

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

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

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

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

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

• О(n2)
• О(nlg2n)
• О(n)

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

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

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

• нецелесообразно
• одинаково
• целесообразно

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

• ≈0,06 с
• ≈0,056 с
• ≈0,046 с

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

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

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

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

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

• 0,39Q
• 0,45Q
• 0,47Q

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

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

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

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

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

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

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

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

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

• граф содержит единственный цикл
• граф ациклический
• граф содержит циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Охарактеризуйте проблемы, возникающие при решении информационных задач по 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,832
• Р=0,899
• Р=0,843

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

• значение коэффициента готовности
• вероятность решения поставленной перед ней задачи
• вероятность отсутствия сбоев и отказов в течение цикла управления

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

• один процессор основной и два резервных
• один процессор основной и три резервных
• один процессор основной и один резервных

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

• 0,44Q
• 0,38Q
• 0,4Q

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

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

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

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

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

• повторное закрытие семафора приводит к прерыванию
• можно, это подтверждает его значение
• повторное закрытие семафора приводит к прерыванию процесса и к его постановке в очередь к этому семафору

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• граф ациклический
• граф содержит циклы
• третья работа следует сама себе

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

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

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

• вершины многогранника R допустимых решений:О(0, 0),A(0,5),B(2,5),C(7,0). Описание Rx=0k1+0k2+2k3+7k40≤k1,k2, k3, k4≤1y=0k1+5k2+6k3+0k4k1+ k2= k3+ k4=1Перебор точек RТочкиk1k2k3k4000011h001-h2hh01-2h3hhh1-3h42hhh1-4hи т.д.
• вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0)Описание R: x=0k1+0k2+2k3+7k40≤k1,k2,k3,k4≤1y=0k1+5k2+6k3+0k4Перебор точек RТочкиk1k2k3k4000001h00022h000..........NNh000N=10h00и т.д.
• вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0)Описание R:x=0k1+0k2+2k3+7k40≤k1,k2,k3,k4≤1x=0k1+5k2+6k3+0k4k1+k2+k3+k4=1Перебор точек RТочкиk1k2k3k4000011h001-h22h001-2h..........NNh001-NhN+10h01-hи т.д.