Интеллектуальные системы. Контрольная работа 2. Контрольная работа 2 по дисциплине Вычислительные системы (по материалам лекций 711) Задание 1
 Скачать 24.14 Kb.
|
|
Промежуточная контрольная работа №2 по дисциплине: «Вычислительные системы» (по материалам лекций 7-11) Задание №1 Коротко расскажите про классификации вычислительных систем Флина, Хокни и Скилликорна. Классификация ВС Флина. Считается, что в ВС могут присутствовать одиночные (О) и множественные (М) потоки команд (К) и данных (Д). В этом случае существуют четыре класса систем, из которых три последних являются параллельными: 1. ОКОД (SISD) – одиночный поток команд, одиночный поток данных (последовательная ВС); 2. ОКМД (SIMD) – одиночный поток команд, множественный поток данных (параллельная ВС); 3. МКОД (MISD) – множественный поток команд, одиночный поток данных (параллельная ВС); 4. МКМД (MIMD) – множественный поток команд, множественный поток данных (параллельная ВС). Классификация ВС Хокни. Основная идея классификации базируется на том, что множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающим в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в МКМД системах, которые автор называет конвейерными. Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса: 1. МКМД системы, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя; 2. МКМД системы, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удалённых процессоров поддерживается специальной системой маршрутизации через процессоры посредники. Далее, среди МКМД систем с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память. Классификация ВС Скилликорна. Классификация Д. Скилликорна состоит из двух уровней. На первом уровне она проводится на основе восьми характеристик: 1. Количество процессоров команд (IP); 2. Число запоминающих устройств (модулей памяти) команд (IM); 3. Тип переключателя между IP и IM; 4. Количество процессоров данных (DP); 5. Число запоминающих устройств (модулей памяти) данных (DM); 6. Тип переключателя между DP и DM; 7. Тип переключателя между IP и DP; 8. Тип переключателя между DP и DP. На втором уровне классификации Д. Скилликорн просто уточняет описание, сделанное на первом уровне, добавляя возможность конвейерной обработки в процессорах команд и данных. Автор сформулировал три цели, которым должна служить хорошо построенная классификация: 1. Облегчать понимание того, что достигнуто на сегодняшней день в области архитектур вычислительных систем, и какие архитектуры имеют лучшие перспективы в будущем; 2. Подсказывать новые пути организации архитектур – речь идёт о тех классах, которые в настоящее время по разным причинам пусты; 3. Подсказывать, за счёт каких структурных особенностей достигается увеличение производительности различных вычислительных систем; с этой точки зрения, классификация может служить моделью для анализа производительности. Задание №2 Ответьте коротко, но развёрнуто на вопрос: Какие режимы обработки данных Вы знаете? Расскажите подробнее о пакетном режиме. Существуют два режима работы ВС – однопрограммный и мультипрограммный (многопрограммный). По режиму обслуживания данные системы можно разделить на два вида – индивидуального и коллективного пользования. По способу приёма заданий на обработку различают пакетную обработку и обработку заданий, поступающих независимо друг от друга в случайные моменты времени от разных пользователей. В пакетном режиме пользователи не имеют непосредственного доступа к ВС. Подготовленные ими программы передаются по каналам связи в систему, где они накапливаются и оформляются в виде единого пакета. В момент, когда система готова принять на обработку пакет заданий начинается процесс обработки по заранее составленному расписанию. Особенности пакетного режима: 1. Развитая система прерываний (необходимо прерывать выполнение задачи и сохранять её вектор, перейти к другой задаче, а затем снова возвращаться к выполнению этой задачи). Это приводит к значительным «накладным расходам». 2. Необходима защита памяти от доступа к данным задачи из других задач. 3. Необходимы специальные привилегированные команды (команды защиты), доступные только системе. 4. Требуется специальный датчик времени (таймер) для реализации механизма квантования. Задание №3 Расскажите про системы с UMA и NUMA организацией памяти и коротко про проблему когерентности КЭШ. Чем от этих систем отличаются системы с распределённой памятью? Мультипроцессоры можно разделить на три категории моделей с разделяемой памятью – UMA (Uniform Unix Access Access), NUMA (Uniform Un Access Access) и COMA (Доступ к Cache-only Memory). Модели различаются в зависимости от того, как распределены ресурсы памяти и оборудования. В модели UMA физическая память равномерно распределяется между процессорами, которые также имеют равную задержку для каждого слова памяти, в то время как NUMA обеспечивает переменное время доступа для процессоров для доступа к памяти. Пропускная способность, используемая в UMA для памяти, ограничена, поскольку она использует один контроллер памяти. Основным мотивом появления машин NUMA является увеличение доступной пропускной способности памяти с помощью нескольких контроллеров памяти. Система UMA (Uniform Memory Access) - это архитектура с общей памятью для многопроцессорных систем. В этой модели используется единственная память, к которой обращаются все процессоры представленной многопроцессорной системы с помощью межсоединительной сети. Каждый процессор имеет равное время доступа к памяти (задержка) и скорость доступа. Он может использовать либо одну шину, несколько шин или коммутатор. Поскольку он обеспечивает сбалансированный доступ к общей памяти, он также известен как SMP (Symmetric multiprocessor) системы. NUMA (неоднородный доступ к памяти) также является многопроцессорной моделью, в которой каждый процессор связан с выделенной памятью. Однако эти небольшие части памяти объединяются в единое адресное пространство. Главное, над чем подумать, это то, что в отличие от UMA время доступа к памяти зависит от расстояния, на котором расположен процессор, что означает изменение времени доступа к памяти. Это позволяет получить доступ к любой ячейке памяти, используя физический адрес. Ключевые различия между UMA и NUMA. Модель UMA (совместно используемая память) использует один или два контроллера памяти. В отличие от этого, NUMA может иметь несколько контроллеров памяти для доступа к памяти. В архитектуре UMA используются одиночные, множественные и перекрестные шины. И наоборот, NUMA использует иерархические и древовидные типы шин и сетевых подключений. В UMA время доступа к памяти для каждого процессора одинаково, в то время как в NUMA время доступа к памяти изменяется по мере изменения расстояния памяти от процессора. Приложения общего назначения и разделения времени подходят для машин UMA. В отличие от этого, подходящее приложение для NUMA ориентировано в режиме реального времени и критично ко времени. Параллельные системы на основе UMA работают медленнее, чем системы NUMA. Когда речь идет о пропускной способности UMA, имеют ограниченную пропускную способность. Напротив, NUMA имеет пропускную способность больше, чем UMA. Одна и та же переменная имеет разные значения в кэш-памяти и оперативной памяти. Это и есть нарушение когерентности. Если процессор один, то рано или поздно он все поправит, но если несколько процессоров и одна оперативная память, хранящая данные одной большой задачи, то налицо нарушение когерентности, причем сразу у нескольких процессоров, которым нужно сообщить об этом нарушении. Поэтому, на стадии программирования необходимо помнить об этом и предусмотреть способы смягчения этой проблемы. Распределение памяти между отдельными узлами системы имеет два главных преимущества. Во-первых, это эффективный с точки зрения стоимости способ увеличения полосы пропускания памяти, поскольку большинство обращений могут выполняться параллельно к локальной памяти в каждом узле. Во-вторых, это уменьшает задержку обращения (время доступа) к локальной памяти. Задание №4 Ответьте на вопросы (в произвольной форме своими словами): 1. В чём заключается задача назначения и что она решает? Под решением задачи назначения понимается процесс распределения узлов графа задачи (набора задач), выполняемой в МВС, между ее процессорами, при котором определяется время начала выполнения узла, его длительность и назначение процессора, который обеспечит это выполнение. 2. Из чего состоит ЯПФ представления задачи? Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга. На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции. 3. Чем характеризуются слабо, сильно и среднесвязанные задачи? Откуда берётся такое разделение? Слабосвязанная t обр.узла >> t передачи Сильносвязанная t обр.узла << t передачи Среднесвязанная t обр.узла ≈ t передачи Распределенные вычисления возникают, когда для решения задачи требуется согласованная вычислительная мощность нескольких вычислительных узлов. Для сильносвязанной модели вычислений характерны относительно небольшое время собственно фазы вычислений, невозможность для каждого из узлов запустить следующий шаг без получения информации от соседних узлов, синхронный режим исполнения. На всех узлах исполняется единая задача, какая-то из задач в зависимости от условий (например, задача под определенным номером) может быть главной, но суть остается неизменной — все задачи исполняют единый код в синхронном режиме. Если параметры дискретные или изменяются дискретно, то количество вариантов перебора будет конечным, хотя оно может быть достаточно большим. Такие задачи можно решать, разбивая их на отдельные подзадачи, которые будут исполняться на разных вычислительных узлах. Эти узлы могут находиться на разных континентах. Это — слабосвязанная модель вычислений. 4. Как найти критический путь? Для нахождения критического пути нужно определить максимально возможное и минимально возможное время начала выполнения узлов графа. При начальном проходе от начальной вершины к конечной, определяем минимально возможное время начала по формуле. Tmin i = max (T min j + t j+ T ij) (1) При повторном анализе определяем максимально возможное время. Tmax i = min (T max r - t i - T ir) При этом для начальной вершины (вершин) Tmin i = 0, а для конечной вершины минимально возможное время начала ее выполнения совпадает с максимально возможным временем начала выполнения - Tmax i = Tmin i. 5. Перечислите и кратко опишите известные Вам стратегии назначения. 1. Равновероятный выбор 2. С максимальным временем исполнения узла 3. С минимальным временем исполнения узла 4. На основе принадлежности узла критическому пути 6. Что такое ВС реального времени? Система реального времени, жесткое реальное времени, мягкое реальное время, система управленич, отказ, время отклика, время обработки, мультимедиа, программные комплекс, целевая платформа, процесс, потоки, ядрА, операционная система, синхронизация, внешние события, планирование, автоматизация, высокопроизводительные системы, архиткектура, интерфейс, аппаратно-программный комплекс, внешние события, системы автоматизации. Задание №5 Задача назначения. Стратегии назначения, их особенности, достоинства и недостатки. При ответе приведите примеры. Объект исследования – это ВС, которая в одном случае организована как система с общей памятью, а в другом как система с распределенной памятью, и прикладные задачи, которые поступают для решения на вход ВС. Предмет исследования – это способ размещения работ (например, вычислений, передач), необходимых при выполнении, поступивших на вход ВС прикладных задач, на выделенные ресурсы ВС. Выбор способа размещения работ получил название «решение задачи назначения». Стратегии назначения: 1. Равновероятный выбор; 2. С максимальным временем исполнения узла; 3. С минимальным временем исполнения узла; 4. На основе принадлежности узла критическому пути. Для автоматического решения задачи назначения граф задачи представляется в виде таблицы связности размерностью NxN, в ячейки которой заносятся признаки связи соответствующих вершин. Будем считать, что на вход многопроцессорной вычислительной системы поступают задачи, относящиеся к классу слабосвязных. Тогда временем передачи данных можно пренебречь. Задание №6 Ответьте на вопросы (в произвольной форме своими словами): 1. Чем характеризуется надёжность вычислительной системы? Время простоя процессоров можно использовать для контроля исправности оборудования за счет дублирования выполнения одних и тех же вершин на разных процессорах (во время их простоя). Ошибка – событие, заключающееся в получении результата вычислений, отличного от правильного из-за сбоев и отказов оборудования. Сбой – самоустраняющийся отказ, приводящий к кратковременному нарушению работоспособности. Отказ – событие, заключающееся в постоянном нарушении работоспособного состояния объекта. Следует помнить, что отказать может и исправляющая система, поэтому вычисления не могут быть абсолютно надёжными. 2. В чем заключается мажоритарное обнаружение ошибки? Что делает мажоритарный орган? Наиболее простым способом контроля является дублирование отдельных узлов и устройств и сравнение промежуточных или окончательных результатов, их работы. Если результаты не совпали друг с другом, то делается вывод о неверной работе аппаратуры. Данный способ контроля обладает высокой эффективностью, однако не позволяет непосредственно определить, какое из двух устройств функционирует неверно. Поэтому в ряде случаев используют несколько (три, пять) устройств, одновременно выполняющих одни и те же действия. Это позволяет при выходе из строя одного из устройств решит сразу две задачи при незначительных затратах времени 1) Выработать правильный выходной сигнал % 2) Определить место возникновения отказа. Решение о том, какой сигнал должен быть на выходе, принимается методом «голосования», т. е. по большинству выходных сигналов отдельных устройств. Выработка общего выходного сигнала осуществляется мажоритарным элементом (элементом голосования). Для определения места отказа необходимо иметь элемент анализа, который работал бы параллельно с мажоритарным элементом и указывал введение из строя устройство. 3. Как осуществляется дублирование задачи? Дублирование информации является одним из самых эффективных способов обеспечения целостности информации. Оно обеспечивает защиту информации как от случайных угроз, так и от преднамеренных воздействий. В зависимости от ценности информации, особенностей построения и режимов функционирования информационных систем могут использоваться различные методы дублирования, которые классифицируются по различным признакам, По времени восстановления информации методы дублирования могут быть разделены на: * оперативные; * неоперативные. К оперативным методам относятся методы дублирования информации, которые позволяют использовать дублирующую информацию в реальном масштабе времени. Это означает, что переход к использованию дублирующей информации осуществляется за время, которое позволяет выполнить запрос на использование информации в режиме реального времени для данной системы. Все методы, не обеспечивающие выполнения этого условия, относят к неоперативным методам дублирования. Задание №7 Расскажите про планирование многозадачного режима. Какие характеристики учитываются при планировании многозадачного режима? Какие режимы распределения вы знаете? Задачи из набора могут быть как с равным приоритетом, так и с различным. Последовательность выбора вершины, готовой к исполнению, при выполнении набора задач определяется не только выбранной стратегией назначения, но и соответствующим критерием: Т зад. наб. – заданное время решения набора задач; Т зад. пр. задач – заданный приоритет задач. Минимальное время выполнения набора задач равно длине наибольшего критического пути, а максимальное время выполнения набора задач равно сумме времени выполнения всех вершин всех задач в наборе. При поступлении в МВС, каждый набор задач снабжается паспортом. Паспорт набора задач содержит следующие данные: количество задач; приоритет задач; количество необходимых ресурсов; стратегия назначения. При решении задачи назначения, в зависимости от числа задач в наборе и их приоритетов, формируются очереди готовых к исполнению вершин задач. Сначала рассматривается задача с высшим приоритетом. Есть два режима распределения вершин (составления расписания): Статический – распределение вершин осуществляется перед выполнением задачи; Динамический – распределение вершин осуществляется по ходу выполнения задачи. |