Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Программно-алгоритмический комплекс организации распределенных вычислений с учетом долгосрочного прогноза загрузки сетевых ЭВМ

Диссертация: Программно-алгоритмический комплекс организации распределенных вычислений с учетом долгосрочного прогноза загрузки сетевых ЭВМ
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Разработан исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений «Network Calculation Library», в котором применены предложенные алгоритмы. Комплекс позволяет осуществлять распределенные вычисления в корпоративных сетях ЭВМ, функционирующих под управлением ОС Microsoft Windows. Комплекс включает три программы: программу-агент, программу-координатор… Читать ещё >

Содержание

  • Условные обозначения
  • 1. Обзор методов организации распределенных вычислений
    • 1. 1. Концепция параллелизма
      • 1. 1. 1. Классификации видов параллелизма
      • 1. 1. 2. Принцип распараллеливания процесса решения вычислительных задач
      • 1. 1. 3. Обмен данными между процессами
    • 1. 2. Классификация сред организации распределенных вычислений
      • 1. 2. 1. Локально распределенные среды. 1 б
      • 1. 2. 2. Организация вычислений в распределенных средах
      • 1. 2. 3. Глобальные распределенные среды. Технология Grid
    • 1. 3. Функция планирования и балансировка загрузки
      • 1. 3. 1. Классификация и обзор алгоритмов планирования
    • 1. 4. Постановка задачи исследования
  • 2. Разработка программно-алгоритмического комплекса организации распределенных вычислений
    • 2. 1. Общая структура комплекса
    • 2. 2. Описание программы-координатора
    • 2. 3. Описание программы-диспетчера
    • 2. 4. Описание программы-агента
    • 2. 5. Описание процесса решения задачи
    • 2. 6. Выводы по главе 2
  • 3. Описание метода повышения качества алгоритма планирования вычислений
    • 3. 1. Формализация задачи
    • 3. 2. Сбор данных о функционировании вычислительных элементов
      • 3. 2. 1. Сбор данных
      • 3. 2. 2. Предварительная обработка и фильтрация данных
    • 3. 3. Оценка и прогнозирование состояния системы
    • 3. 4. Алгоритм составления плана назначения
    • 3. 5. Оценка качества функционирования алгоритма составления плана назначений
    • 3. 6. Выводы по главе 3
  • 4. Пример использования разработанного комплекса для ускорения решения практической задачи молекулярной динамики
    • 4. 1. Описание метода молекулярной динамики
    • 4. 2. Адаптация метода для применения на разработанном комплексе
    • 4. 3. Выводы по главе 4

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

Актуальность работы.

В настоящий момент наблюдается несоответствие темпов роста вычислительной мощности ЭВМ с одной стороны, и распространенности вычислительных сетей и их пропускной способности — с другой. Исследователи указывают на постепенное замедление скорости роста тактовых частот ЦП, и при этом резкое ускорение темпов роста пропускной способности и снижения стоимости эксплуатации коммуникационных сетей [39].

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

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

• корпоративные и домашние вычислительные сети (далее корпоративные сети) состоят из сравнительно небольшого числа ЭВМ (чаще всего нескольких десятков, редко до нескольких сотен), объединенных в локальные сети. Отдельные локальные сети могут быть удаленны друг от друга территориально и связанны через internet-среду.

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

• наиболее распространенной операционной системой в корпоративных сетях является Microsoft Windows.

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

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

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

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

Целью диссертационной работы является создание программно-алгоритмического комплекса организации распределенных вычислений в корпоративных сетях ЭВМ.

Для достижения этой цели необходимо решить следующие задачи:

• изучить особенности функционирования ЭВМ в целевых сетях;

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

• синтезировать специализированные алгоритмы организации распределенных вычислений;

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

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

• оценить эффективность синтезированных алгоритмов с помощью программной реализации имитационной модели;

• провести оценку качества работы разработанного программно-алгоритмического комплекса в реальных сетях ЭВМ на практических задачах.

Диссертационная работа содержит 4 главы.

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

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

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

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

Основными положениями диссертационной работы, выносимыми на защиту, являются:

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя;

• метод оценки времени решения подзадач на ЭВМ и вероятности возникновения сбоя, основанный на построенном прогнозе загрузки;

• алгоритм составления плана назначения подзадач на ЭВМ.

Апробация работы и публикации.

Результаты работы были представлены на III Международной научно-технической конференции «Информационные технологии в науке, образовании и производстве», Орел, 24−25 апреля 2008.

По материалам диссертации опубликовано 3 печатные работы, размещенные в журналах, рецензируемых ВАК, 1 тезис доклада, получено два патента и один акт о внедрении.

• Халимон В. И. Смирнов А.В. Механизм децентрализованного распределения задач между вычислительными элементами. // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии». — 2007. — № 42/268 (535).

• Халимон В. И. Смирнов А.В. Прогнозирование загрузки ЭВМ, входящих в корпоративные вычислительные сети. // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии». — 2008. — № 14/269 (544).

• Халимон В. И. Смирнов А.В. Алгоритм долгосрочного прогноза ЭВМ задачами пользователя. // Вестник компьютерных и информационных технологий № 12, М.: Машиностроение, 2008, сс. 34−38.

• Халимон В. И. Смирнов А.В. Оптимизация распределенных вычислительных процессов в корпоративных сетях. // Математические методы в технике и технологиях — ММТТ-22, сб. трудов XXII между народ, науч. копф.

• Свидетельство об официальной регистрации программы для ЭВМ № 2 009 610 805 «Network Calculation Library». / Халимон В. И., Смирнов А. В., Проститенко О.В.// Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Реестр программ для ЭВМ.-04.03.09.

• Свидетельство об официальной регистрации программы для ЭВМ № 2 009 610 806 «Graf, PetriNet, SMO. (3 Tools Solution)». / Халимон В. И., Рогов А. Ю., Проститенко О. В., Смирнов А.В.// Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Реестр программ для ЭВМ. — 04.03.09.

ВЫВОДЫ ПО РАБОТЕ.

По результатам выполненной работы можно сделать следующие выводы.

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

2. Разработаны алгоритмы и методы управления распределенными вычислениями в корпоративных сетях:

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя, основанный на выявлении типовых паттернов использования ЭВМ и закономерности их чередования;

• метод вычисления оценки времени решения фрагмента вычислительной задачи и вероятности наступления сбоя на конкретной ЭВМ;

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

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

3. Разработан исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений «Network Calculation Library», в котором применены предложенные алгоритмы. Комплекс позволяет осуществлять распределенные вычисления в корпоративных сетях ЭВМ, функционирующих под управлением ОС Microsoft Windows. Комплекс включает три программы: программу-агент, программу-координатор и программу-диспетчер. Также в комплекс входит исходный код модуля, представляющего вычислительную задачу, что позволяет быстро и эффективно реализовывать модули решения различных прикладных вычислительных задач. 4. Комплекс применен для распределенного решения практической задачи молекулярной динамики.

Показать весь текст

Список литературы

  1. СЛ., Кафаров В. В. Методы оптимизации эксперимента в химической технологии. Учеб. пособие для хим.-технолог, спец. вузов. — 2-е изд., перераб. и и доп. М.: Высш. шк., 1985. — 327 с.
  2. А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. — 256 с.
  3. Боровиков В. Statistical искусство анализа данных на компьютере. Питер, 2003 г.-688 стр.
  4. Д., Ватте Д. Анализ временных рядов. Прогноз и управление. Выпуск 1, М.: Мир, 1974. 409 с.
  5. Д., Ватте Д. Анализ временных рядов. Прогноз и управление. Выпуск 2, М.: Мир, 1974. 198 с.
  6. Е.Н., Пиотровская Е. М. Метод молекулярной динамики в физической и коллоидной химии. СПбГУ, 1999. 27 с.
  7. Д. Временные ряды. Обработка данных и теория: Пер. с англ. М.:Мир, 1980.-536 с.
  8. А.Д. Курс теории случайных процессов. М.: Наука. Физматлит 1996.-399 с.
  9. Ю.Витязев В. В. Спектрально-корреляционный анализ равномерных временных рядов. Учеб. пособие. СПб.: Изд.-во С.-Петерб. Ун-та, 2001. -48 с.
  10. В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 с.
  11. Вл.В., Жуматий С. А. «Вычислительное дело и кластерные системы».-М.: Изд-во МГУ, 2007. 150 с.
  12. З.Головкин Б. А, Расчет характеристик и планирование параллельных вычислительных процессов. — М.: Радио и связь, 1983. —- 272 с.
  13. А.К., Рябов Ю. Ф. Введение в технологию Грид: Учебное пособие. Гатчина: ПИЯФ РАН, 2006. — 39 е.
  14. В.Н., Корягин Д. А. Организация ресурсов грид. Препринт ИПМ им. М. В. Келдыша РАН № 63, Москва, 2004.
  15. , Р.В.- Максвелл, B.JT.- Миллер, JI.B. Теория расписаний. М: Наука., 1975 г.-360 с.
  16. Теория расписаний и вычислительные машины / Под ред.Э. Г. Коффмана.-М.: Наука, 1984.-335 с.
  17. В.К. Вероятностный машинный эксперимент в приборостроении. JT.: Машиностроение, Ленингр. Отд-ние, 1985. — 247 с.
  18. Л. Вычислительные системы с очередями. Пер. с англ.- М.: Мир, 1979.-600 с.
  19. А. М., Майоров С. А., Новиков Г. И. Вычислительные комплексы, системы и сети. Л.: Энергоатомиздат, 1987 г. 288 с.
  20. Лут Р. Распределенные вычисления в малом и среднем офисе Электронный ресурс. Режим доступа: http://www.dtf.ru/articles/read.php?id=46 196, свободный. — Загл. с экрана.
  21. , В.К.- Долганов, А.В. Основы теории информационных сетей. М.: Высшая школа, 1987 г. 271 с.
  22. .Я., Яковлев С. А. Моделирование систем. Издание 3-е, переработанное и дополненное. М.: Высш. шк., 2001. 343 с.
  23. Э., Стеен М. Распределенные системы. Принципы и парадигмы. Питер, 2003 г. 880 с.
  24. В. Модели распределенных вычислений М.: 2004 г. 320 с.
  25. Ю.Н., Макаров А. А. Анализ данных на компьютере. М.: Инфра-М, 2003.-544 с.
  26. Д.А. Вероятностные автоматы. М.: Энергия, 1970. 88 с.
  27. С. П. Компьютерное моделирование молекулярных систем. Екатеринбург: УрГУ, 1995. 92 с.
  28. Д. Оценка производительности вычислительных систем. М.: Мир, 1981.- 573с.
  29. ЗО.Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования. Издательство: Вильяме, 2003 г. 512 с.
  30. В.И., Комаров П. И., Жуковец Ю. Э. Автоматизированный выбор программного фильтра. Метод. Указания / СПб.технол.ин-т. — СПб., 1999.-35с.
  31. , В.И. Алгоритм долгосрочного прогноза ЭВМ задачами пользователя. / В. И. Халимон, А. В. Смирнов // Вестник компьютерных и информационных технологий № 12, М.: Машиностроение, 2008, С. 34−38.
  32. , В.И. Оптимизация распределенных вычислительных процессов в корпоративных сетях. / В. И. Халимон, А. В. Смирнов // Математические методы в технике и технологиях ММТТ-22.
  33. М.В. Распределенные системы и сети. Учебное пособие. М.: МГТУ «Станкин», 2000. — 118 с.
  34. Berman, F., Wolski, R. Scheduling from the perspective of the application. In Proceedings of the Fifth IEEE Symposium on High Performance Distributed Computing FIPDC96, August 1996, pp. 100−111.
  35. David J. Farber- K. Larson (Sept 1970). «The Architecture of a Distributed Computer System—An Informal Description». Technical Report Number 11, University of California, Irvine.
  36. Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing, Second Edition., Addison Wesley, 2003. 656 pp.
  37. Basney, J. Livny, M, Deploying a High Throughput Computing Cluster // High Performance Cluster Computing, Rajkumar Buyya, Editor, Vol. 1, Chapter 5, Prentice-Hall, Upper Saddle River, NJ, USA, 1999, pp. 116−134.
  38. Beaumont O., Legrand A. and Robert Y. The master-slave paradigm with heterogeneous processors. In Daniel S. Katz, T. Sterling, M. Baker, L. Bergman, M. Paprzycki and Rajkumar Buyya editors, Cluster'2001, IEEE Computer Society Press, 2001, pp 419−426.
  39. Bryant, M., Finkel, R. A. «A stable distributed scheduling algorithm,» inProc. 2nd Int. Conf. Distrib. Comput., Apr. 1981, pp. 314−323.
  40. Buyya R., Fligh Performance Cluster Computing: Architectures and Systems, Volume 1, ISBN 0−13−13 784−7, Prentice Hall, NJ, USA, 1999. 855 p.
  41. Casavant, T. L, and Kuhl, J.D.: A communicating finite automata approach to modeling distributed computation and its application to distributed decision making, IEEE trans. Comput., may 1990, 39 (5), pp. 628−639.
  42. Casavant, T. L., Kuhl, J. G. A taxonomy of scheduling-in general-purpose distributed computing systems. IEEE Trans. Software Eng., vol. SE-14, Feb. 1988, pp. 141−154.
  43. , P. A. «A Prediction-based Real-time Scheduling Advisor,» presented at Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002, pp. 10 17.
  44. Dinda, P. A., O’Hallaron D. R. «An Evaluation of Linear Models for Host Load Prediction,» presented at Proceedings of the 8th IEEE International Symposium on High-Performance Distributed Computing (HPDC-8), Redondo Beach, CA, 1999, pp. 87−96.
  45. Dinda, P. A., O’Hallaron D. R. Host load prediction using linear models. Cluster Computing, 3(4), 2000, pp. 87 96.
  46. Eager, D., Lazowska, E, and Zahorjan, K.: Adaptive load sharing in homogeneous distributed systems, IEEE trans. Software eng., may 1986, se-12, (5), pp. 662−675.
  47. Efe, K. Heuristic models of task assignment scheduling in distributed systems. IEEE Computer, June 1982, pp. 50−56.
  48. Hansen P. B. Model programs for computational science: a programming methodology for multicomputers //Concurrency: Practice and Experience. — 1993, —V. 5, pp. 407−423.
  49. Haynos, M.: Perspectives on grid: Grid computing next-generation distributed computing, http://www.ibm.com/developerworks/grid/library/gr-heritage.
  50. Jackson, D.B., Snell, Q., Clement, M.J.: Core Algorithms of the Maui Scheduler. JSSPP 2001. pp. 87−102, Cambridge, MA, USA.
  51. Foster I., Kesselman C., Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International J. Supercomputer Applications, vol 15 n. 3, August, 2001, pp. 200−222.
  52. Foster I., Kesselman C., Tuecke S., Nick J. M. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. Morgan Kaufmann Publishers, 2002.
  53. Foster I. What is the Grid? A Three Point Checklist. GRIDToday, July 20, 2002.
  54. Limin Fu, Enzo Medico. FLAME, a novel fuzzy clustering method. BMC Bioinformatics, England, 2007- vol 8: pp. 3−3.
  55. Mullender, s., van Rossum, g., Tannenbaum, a.s., van Renesse, г., and van Staveren, h.: 'amoeba: a distributed operating system for the 1990s', ieee. Computer, may 1990, 23, (5), pp. 44−53.
  56. Patton J.J. and Brickell C. Second Evaluation of Job Queuing/Scheduling Software: Phase 1 Report. NASA Technical Report NAS-97−013 June 1997.
  57. Shao G., Wolski Rn Berman F. Performance effects of scheduling strategies for master/slave distributed applications // UCSD CSE Technical Report W CS98A598. University of California, San Diego. 1998. — 13 p.
  58. Stockinger H. Defining the grid: a snapshot on the current view. // The Journal of Supercomputing, Springer Netherlands ISSN 0920−8542 (Print) 1573−0484 (Online), Volume 42, Number 1 / 2007.
  59. Shivaratri, N.G., Krueger, P., and Singhal, M.: Load distributing for locally distributed systems, IEEE Computer, dec. 1992, 25 (12), pp. 33−44.
  60. Yang, L., Foster, I., Schopf, J.M. Homeostatic and Tendency-based CPU Load Predictions. Proc. IEEE Press, 2003, pp. 42 50.
Заполнить форму текущей работой

На отлично!