УДК 004.942
И.В. Бибиков, А.В. Стретович, Т.В. Михайлова
Донецкий национальный технический университет, г. Донецк
кафедра прикладной математики и информатики
ОБЗОР ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ТЕХНОЛОГИЙ ПОСТРОЕНИЯ МАРКОВСКИХ МОДЕЛЕЙ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Аннотация
Бибиков И.В., Стретович А.В., Михайлова Т.В Обзор параллельных алгоритмов и технологий построения марковских моделей вычислительных систем. Рассмотрены проблемы в построении высокопроизводительных вычислительных систем и оценке их эффективности. Определены технологии и алгоритмы для распараллеливания процесса решения задач большой размерности.
Ключевые слова: высокопроизводительные вычислительные системы, технологии распараллеливания.
Постановка проблемы. В настоящее время значительный вклад в решение проблем создания новых многопроцессорных архитектурных реализаций и оценки их эффективности вносят дискретные марковские модели, которые по сравнению с непрерывными, более точно отражают работу вычислительных систем. Подобные задачи обладают большой размерностью и не могут быть эффективно реализованы на однопроцессорных ЭВМ. Решением этой проблемы является распараллеливание алгоритма построения дискретных марковских моделей на несколько вычислительных модулей [1].
Задачи работы:
- рассмотреть существующие алгоритмы для построения модели марковских моделей вычислительных систем;
- рассмотреть пути решения сложных вычислительных задач;
- обзор параллельных алгоритмов реализации для задач большой размерности.
Анализ литературы. Забродин А.В., Левин В.К. в своем исследовании[1] изложили особенности архитектуры и системных решений в многопроцессорных вычислительных системах. Также, большой вклад в решение проблем создания новых многопроцессорных архитектурных реализаций и оценки их эффективности внесли Каляев А.В.[2], Столингс У. [3]. Были рассмотрены библиотеки методов[4-6], использующие стандарт MPI и имеющие стредства для решения СЛАУ с разреженными матрицами.
Цель статьи – провести обзор эффективности существующих параллельных алгоритмах построения аналитической модели кластерной системы.
Описание области исследования. При анализе способов построения высокопроизводительных кластерных систем и средств оценки их эффективности обнаруживается сложность решения задачи анализа, а также синтеза этих вычислительных систем. Уже существующие и, можно сказать, традиционные решения этой задачи уже не покрывают увеличивающиеся требования к подобным алгоритмам и возникает необходимость в разработке новых подходов для действенных методов решения поставленной задачи.
В разработанных подходах существуют некоторые нас сопровождают некоторые особенности:
- наличие конфликтных ситуаций при использовании общих ресурсов, а также несоответствие программ архитектуре ВС приводят к снижению производительности вычислительных систем;
- аналитические методы, в основном, используются для анализа производительности однопроцессорных ВС, преимущественно с последовательной обработкой данных;
- дискретные Марковские модели, описывающие проектируемые вычислительные сети, имеют большую размерность и в большинстве случаев не решаются на ЭВМ ввиду ограниченности вычислительных ресурсов.
При ближайшем рассмотрении данных особенностей, можно найти пути решения и обхода некоторых положений:
- для оценки и рекомендации на стадии проектирования следует использовать аналитические методы анализа, а именно, аппарат марковских цепей;
- для ВС с параллельной обработкой данных и для многопроцессорных ВС, например, многопроцессорных структур, в том числе, кластерных, аналитические методы требуют дальнейшего развития;
- распараллеливание алгоритмов дискретных Марковских моделей, описывающих проектируемые вычислительные сети, которые имеют большую размерность. Необходимо построить параллельный алгоритм, оценив параметры параллелизма.
Приведенные доводы подталкивает к разработке нового подхода в понимании представленной проблемы.
В связи с большим количеством создаваемых параллельных вычислительных систем (ВС), работы в этом направлении требуют дальнейшего развития, не утрачивают своей актуальности.
Для построения самой вычислительной системы была разработана оригинальная архитектура типа "квазиматрица", которая позволяет реализовать наращиваемые по производительности многопроцессорные вычислительные системы (МВС) без изменения топологии связей между процессорными модулями, образующими вычислительное поле. При этом важно, что максимальная длина пути передачи информации между процессорными элементами в системе МВС не превышает длину пути в системах топологии "гиперкуб", что свидетельствует о ее оптимальности. Преимуществом системы с архитектурой "квазиматрица" по сравнению с "гиперкубом" является ее наращиваемость без изменения конструкции самого модуля. (Вычислительные системы в топологии "гиперкуб", в отличие от МВС, не являются масштабируемыми).
Еще одним преимуществом МВС является реализация двухуровневого функционирования, т.е. разделение производства вычислений (верхний уровень) и осуществления межпроцессорных обменов (нижний уровень). Это дает возможность без изменения архитектуры системы производить замену типов как вычислительного процессора, так и коммуникационного на более производительные (по мере их появления) с сохранением преемственности по отношению к созданному программному и прикладному математическому обеспечению [7].
Такой подход позволяет решать сложные вычислительные задачи качественно нового уровня для различных областей применений. Также была достигнута цель эффективного распараллеливания обработки.
Целью моделирования – аналитического и имитационного – является прогноз производительности системы путем оценки характеристик использования ресурсов, длин очередей и задержек в них. Расчет проектной производительности ИВС необходим, поскольку сложность их конфигурации и функционирования в режимах реального времени и интерактивном сильно уменьшаю возможности интуитивной оценки производительности. Невозможно достичь проектной мощности в ряде реальных ВС и ИВС объясняется недостаточным понимание на этапе проектирования характеристик будущей рабочей нагрузки и ее взаимодействия с компонентами системы. Ретроспективный анализ показывает обычно наличие узкие мест, которые трудно было выявить заранее.
Аналитическая модель представляет ИВС как сеть массового обслуживания, узлами которой служат ресурсы, а заявками – задания (открытая сеть), фиксированное множество заданий (замкнутая сеть). Модель позволяет отобразить взаимодействие между рабочей нагрузкой и ресурсами ИВС и оценить как ожидаемую производительность, так и отношение «стоимость/производительность» [8].
Множество задач, решаемых на многопроцессорных системах, требуют решения больших систем линейных уравнений с разреженными матрицами:
(1)
где A – задаваемая пользователем разреженная матрица nxn; B – задаваемый пользователем вектор длины n, x – вектор длины n, который должен быть вычислен.
Причем, как правило, решение задач линейной алгебры занимает значительную часть (50 % и более) времени решения всей задачи в целом [9].
Инструментальные средства для параллельного решения СЛАУ. Библиотека ScaLAPACK включает подмножество процедур LAPACK, переработанных для использования на MPP-компьютерах, включая: решение систем линейных уравнений, обращение матриц, ортогональные преобразования, поиск собственных значений и др.
Библиотека ScaLAPACK разработана с использованием PBLAS (параллельные версии BLAS уровней 1,2,3) и коммуникационной библиотеки BLACS.
Поддерживается на платформах IBM RS/6000 SP, Intel Paragon, SGI Origin 2000, и HP Exemplar, а также на кластерах рабочих станций. Может быть портирована на любую платформу, где поддерживается PVM или MPI.
ScaLAPACK — совместный проект нескольких организаций (Oak Ridge National Laboratory, Rice University, University of California at Berkeley University of California at LA University of Illinois, University of Tennessee at Knoxville)
Пакет подпрограмм Aztec разработан в исследовательской лаборатории параллельных вычислений Сандии (США) для решения итерационными методами систем линейных уравнений. Aztec включает в себя процедуры, реализующие ряд итерационных методов Крылова:
- метод сопряженных градиентов (CG),
- обобщенный метод минимальных невязок (GMRES),
- квадратичный метод сопряженных градиентов (CGS),
- метод квазиминимальных невязок (TFQMR),
- метод бисопряженного градиента (BiCGSTAB) со стабилизацией.
Все методы используются совместно с различными переобуславливателями (полиномиальный метод и метод декомпозиции областей, использующий как прямой метод LU, так и неполное LU разложение в подобластях).
PETSc. Набор процедур и структур данных для параллельного решения научных задач с моделями, описываемыми в виде дифференциальных уравнений с частными производными. Библиотека реализована с помощью MPI. Поддерживаемые платформы: рабочие станции Sun, RS/6000 включая SP, SGI IRIX — 32-битные и 64-битные версии, HP Exemplar, Cray T3D/T3E, DEC Alpha, Linux/FreeBSD/Windows NT на Intel.
Библиотека разработана в Argonne National Laboratory/MCS division. Распространяется бесплатно.
Модуль KSP (Krylov subspace method – метод подпространств Крылова) является сердцем PETSc, поскольку он обеспечивает унифицированный и эффективный доступ ко всем средствам для решения систем линейных алгебраических уравнений (СЛАУ).
Комбинация метода подпространств Крылова (KSP) и предобуславливателя (PC – preconditioner) находится в центре самых современных программ для решения линейных систем итерационными методами.
Модуль KSP предоставляет многие популярные итерационные методы на основе подпространств Крылова: Conjugate Gradient, GMRES, CG-Squared, Bi-CG-stab и др.
Модуль РС включает разнообразные предобуславливатели: Block Jacobi, Overlapping Additive Schwarz, ICC, ILU via BlockSolve95, ILU(k), LU (прямой метод, работает только на одном процессоре), Arbitrary matrix и др.
Выводы: Выполненный в работе анализ вычислительных систем и методов их построения позволил выделить основные проблемы, связанные с решением задач большой размерности. В статье приводится перечень библиотек, позволяющих решить данную проблему, а также указаны их основные особенности.
Список литературы:
1. Забродин А.В., Левин В.К. Опыт разработки параллельных вычисли - тельных технологий. Создание и развитие семейства МВС // Высокопроизводительные вычисления и их приложения : Труды Всероссийск. науч. конф. - М .: Изд .- во МГУ , 2000.
2. Каляев А. В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. — М.: Янус-К, 2003. — 380 с.
3. Столингс У. Структурная организация и архитектура компьютерных систем. — М.: Вильямс, 2002. — 893 с.
4. ScaLAPACK Home Page [Электронный ресурс] / Интернет-ресурс. — Режим доступа: http://www.netlib.org/scalapack/scalapack_home.html
5. Аztec — a massively parallel iterative solver library for solving sparce linear systems [Электронный ресурс] / Интернет-ресурс. — Режим доступа: http://www.cs.sandia.gov/CRF/aztec1.html
6. PETSc — Portable, Extensible Toolkit for Scientific Computation [Электронный ресурс] / Интернет-ресурс. — Режим доступа: http://www.mcs.anl.gov/petsc/petsc-as/
7. Кучереносова О.В. Параллельный алгоритм построения дискретной марковской модели неоднородного кластера // Наукові праці Донецького національного технічного університету. — Донецьк, ДонНТУ, 2010.
8. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. — М.: Наука, 1989.— 336 с.
9. Химич А.Н., Попов А.В., Т.В. Чистякова, О.В. Рудич, Т.А. Герасимова. Исследование блочно-циклических алгоритмов на семействе кластеров СКИТ. // Проблеми програмування. — К., 2006. — № 2-3. — с. 177-183.