Українська   English
ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Актуальность темы

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

2. Цель и задачи исследования

Цель работы состоит в разработке эффективного параллельного алгоритма построения аналитической модели кластерной системы.

Основные задачи исследования:

  1. Обзор и анализ современных вычислительных систем.
  2. Разработка марковской модели функционирования кластерной системы
  3. Расчет основных характеристик функционирования кластерной системы, с учетом особенностей ее структуры и класса решаемых на ней задач.
  4. Исследование эффективности вычислительной системы

3. Обзор исследований и разработок по теме

Работа по исследованию и разработке вычислительных систем не прекращается: активно разрабатываются алгоритмы улучшения работы вычислительных систем, решаются проблемы балансировки нагрузки в сети, планирования, выявления узких мест. В ДонНТУ над этими вопросами работают:

В прошлом больших успехов в исследовании вычислительных систем достигли магистранты:

Данная работы является продолжением разработок этих магистрантов. Новизна работы состоит в том, что предыдущие модели вычислительных систем были рассчитаны на работу с одним классом задач. Необходимо продолжить исследования и построить дискретную Марковскую модель кластера, рассчитанного на работу с несколькими классами задач. Данная работа проводится совместно с магистром Ильей Владимировичем Бибиковым, Руководитель: Фельдман Лев Петрович. Тема работы: Оценка производительности распределенных систем Отличие моделей состоит в различном выборе ограничений, накладываемых на модель. Модель, рассмотренная в этой работе, будет иметь постоянное число заявок, обрабатываемых в системе.

4 Общие понятия

Вычислительная система:

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

Кластер – группа взаимно соединенных вычислительных систем (узлов), работающих совместно и составляющих единый вычислительный ресурс, создавая иллюзию наличия единственной ВМ. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. Примеры кластерных вычислительных систем: NT-кластер в NCSA, Beowulf-кластеры.

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


Кластерная система

Рисунок 1 – Кластерная система

В состав кластера входят:

4.1 Анализ существующих топологий многоядерных компьютеров

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

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

MIMD-компьютеры относятся к компьютерам с разделенной памятью. А персональные компьютеры и малые сервера, привычные обычному пользователю, относятся к SIMD системам с общей памятью [3].

4.2 Средства распараллеливания

Существует несколько разных подходов к программированию параллельных вычислительных систем:

Существует также немало инструментальных средств, которые упрощают проектирование параллельных программ. Например:

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

Коммуникационные библиотеки стандарта MPI (MPICH2, Open MPI, Cray MPI и др.) являются основным средством создания параллельных программ для распределенных вычислительных систем (ВС). Основу этих библиотек составляют коммуникационные функции дифференцированных (Point-to-point communications) и коллективных операций (Collective communications) обмена информацией между ветвями параллельных программ [5].

5. Методы анализа кластерных систем.Методы анализа кластерных систем. Модель однородного кластера

Для оценки качества и оптимизации параллельных вычислительных систем применяются аналитические и имитационные модели и методы экспериментального исследования.

Одним из методов оценки качества моделей ВС является теория массового обслуживания, позволяющая определить такие показатели качества, как пропускная способность, коэффициент использования, среднее время отклика и другие. Вычислительная система рассматривается как совокупность обслуживающих устройств, в качестве которых выступают различные ресурсы системы – рабочие станции, серверы, оперативная память, КЕШ-память и так далее. Задания, или процессы, предъявляют запросы на обслуживание к этим устройствам, поэтому значительная часть задач оценки качества связана с анализом очередей [6]. В теории массового обслуживания наиболее изученными и исследованными являются аналитические модели ВС, построенные на основе понятий теории цепей Маркова, использующие точные методы анализа.

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

Рассмотрим базовую дискретную модель однородного кластера с общим использованием дискового пространства(см. Рис. 2). Модель была построена с помощью методики [7]. В системе N одинаковых серверов, D дисковых накопителей и управляющий сервер УС. В сети постоянное количество заявок M. Требования, обсуживающиеся на сервере, поступают в ограниченную очередь типа FIFO (first in – first out, Первый пришел – первый обслужился).

Структурная схема Марковской модели кластера с совместным использованием дискового пространства

Рисунок 2 – Структурная схема Марковской модели однородного кластера
(анимация: 9 кадров, 10 циклов повторения, 1 сек задержка, размер – 493x323, 79.1 килобайт)

Введем такие характеристики обслуживания программ устройства:

5.1 Оценка эффективности

Алгоритм, примененный в параллельной реализации марковских моделей [8], состоит из двух частей: вычислений матрицы переходных вероятностей и вектора стационарных вероятностей.

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

Для определения вектора стационарных вероятностей состояний formula 1 необходимо решить систему линейных алгебраических уравнений (СЛАУ), formula 2, соответствующую рассмотренной модели кластера.

Расчет переходных вероятностей. За состояние системы примем размещение М заявок по N узлам formula 3, где mi  – количество задач в i-ом узле. Необходимо определить все возможные состояния. Обозначим множество состояний :

Число состояний системы для одного и того же количества задач formula 5 равно числу размещений j задач по N узлам и определяется по формуле formula 6 , общее количество состояний вычисляется так: formula 7

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

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

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

6 Планируемые практические результаты

По окончанию исследования планируется получить такие результаты:

Важное замечание При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2014г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Чекменев С. Е. Архитектура вычислительных систем. [Электронный ресурс]. – Режим доступа:http://stankin.ru/..
  2. Кластер // Словарь терминов в коллекции "Вычислительные системы" [Электронный ресурс]. – Режим доступа:http://www.nsc.ru/win/elbib/data/show_page.dhtml?77+858
  3. Чистяков А.В., Ислямова И.С. Метод и технологии параллельного программирования при решении прикладных задач / Инженерия программного обеспечения 2010 Том 3.
  4. Эффективные кластерные решения. [Электронный ресурс]. – Режим доступа:http://www.ixbt.com/cpu/clustering.shtml
  5. Курносов М.Г. MPIPerf: пакет оценки эффективности коммуникационных функций стандарта MPI // Труды международной научной конференции "Параллельные вычислительные технологии (ПаВТ-2012)". – Новосибирск, 2012. - С. 212-223.
  6. Клейнрок Л. Вычислительные системы с очередями. –М.: Мир, 1979.– 600с.
  7. Фельдман Л.П., Малинская Э.Б. Аналитическое моделирование вычислительных систем с приоритетным обслуживанием программ. //Электронное моделирование. – К., 1985. – №6.– с. 78-82.
  8. Михайлова Т.В. Параллельный алгоритм построения дискретной модели Маркова // Искусственный интеллект. Интеллектуаьные и многопроцесорные системы. Материалы Международной научно-технической конференции, 25-30 сентября 2006г., Таганрог-Донецк-Минск, 2006.
  9. Мищук Ю.К., Фельдман Л.П. Моделирование параллельной реализации марковских моделей в многопроцессорных вычислительных системах // Матеріали I всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 19-21 травня 2010р., Донецьк, ДонНТУ. – 2010. – с. 238-240Матеріали I всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 19-21 травня 2010р., Донецьк, ДонНТУ. – 2010. – с. 238-240 600с.
  10. Фельдман Л.П., Михайлова Т.В. Оценка эффективности кластерных систем с использованием моделей Маркова. //Известия ТРТУ. Тематический выпуск: Материалы Всероссийской научно-технической конференции с международным участием Компьютерные технологии в инженерной и управленческой деятельности. – Таганрог: ТРТУ, 2002. – №2 (25). – С. 50-53.