Содержание к диссертации
Введение
Глава 1. Анализ моделей вычислений, вычислительных систем и способов повышения их эффективности 12
1.1. Классификация вычислительных систем 12
1.1.1. Классификация Флинна 12
1.1.2. Классификация Хокни 13
1.1.3. Классификация SMP/MPP 14
1.2. Кластеры рабочих станций 15
1.2.1. Технология построения кластерных вычислительных систем 18
1.2.2. Организация параллельных вычислений 21
1.3. Распараллеливание программ 24
1.4. Модели параллельных вычислительных процессов 25
1.4.1. Использование модели на основе теории сетей Петри 26
1.4.2. Использование логической модели параллельных программ 26
1.4.3. Использование модели конечных недетерминированных цифровых автоматов ...28
1.4.4. Использование модели марковских процессов 30
1.5. Эффективность параллельных вычислений 33
1.6. Выводы по главе 39
Глава 2, Модели параллельного вычислительного процесса ...41
2.1. Основные понятия 41
2.2. Алгоритм параллельной программы 42
2.3. Автоматная модель параллельной программы 43
2.4. Марковская модель параллельного алгоритма на основе цифрового
автомата 54
2.4.1. Применимость марковской модели для описания параллельного алгоритма 54
2.4.2. Переход от модели недетерминированного цифрового автомата к модели марковских процессов 55
2.5. Марковская модель работы параллельного алгоритма 60
2.5.1. Анализ непараллельной (основной) части программы. 61
2.5.2. Анализ параллельных ветвей 63
2.5.3. Анализ трудоемкости 64
2.6. Выводы по главе 66
Глава 3. Повышение эффективности параллельных вычислений и параллельное программирование 68
3.1. Эффективность параллельных вычислений 68
3.1.1. Методики построения моделей параллельного алгоритма 68
3.1.2. Эффективность параллельного алгоритма 71
3.1.3. Эффективная организация вычислительной системы 75
3.1.4. Повышение эффективности параллельных вычислений 78
3.2. Построение высокопроизводительной вычислительной системы на основе кластерной технологии 82
3.2.1. Программный комплекс «Распределенная вычислительная система «MathNet» 83
3.2.2. Организация доступа к кластеру 85
3.3. Технология параллельного программирования 87
3.3.1. Технология написания параллельной программы для ПК «РВС «MathNet» 90
3.3.2. Алгоритм параллельной программы для ПК «РВС «MathNet» 92
3.4. Выводы по главе 94
Глава 4. Анализ параллельных алгоритмов 96
4.1. Аналитический анализ алгоритмов 96
4.1.1. Анализ алгоритма программы вычисления интеграла методом Симпсона для MPI 96
4.1.2. Анализ алгоритма программы вычисления интеграла методом Симпсона для ПК «РВС «MathNet» 97
4.1.3. Анализ алгоритм программы умножения матриц для MPI 99
4.1.4. Анализ алгоритма программы умножения матриц для ПК «РВС «MathNet» 100
4.2. Анализ полученных результатов 102
4.2.1. Результаты тестирования программы вычисления интеграла методом Симпсона 102
4.2.2. Результаты тестирования программы умножение матриц 109
4.3. Выводы по главе 117
Заключение 118
Литература 120
Приложения 127
- Основные понятия
- Алгоритм параллельной программы
- Автоматная модель параллельной программы
- Построение высокопроизводительной вычислительной системы на основе кластерной технологии
Введение к работе
Параллельное программирование возникло в 1962 г. с изобретением каналов - независимых аппаратных контроллеров, позволяющих центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других (приостановленных) программ. Слово «параллельное» в данном случае означает «происходящее одновременно». В конце 60-х годов были созданы многопроцессорные машины, что поставило новые задачи и дало новые возможности программистам.
Первой важной задачей параллельного программирования стало решение проблемы, связанной с так называемой «критической секцией». Для решения этой и сопутствующих ей задач («обедающих философов», «читателей и писателей» и т.д.) были разработаны такие элементы синхронизации, как семафоры и мониторы.
К середине 70-х годов стало ясно, что для преодоления сложности, присущей параллельным программам, необходимо использовать формальные методы их анализа и оценки по различным параметрам [15]. На рубеже 70-х и 80-х годов появились компьютерные сети. Для глобальных сетей стандартом стала сеть Arpanet, а для локальных - Ethernet. Сети привели к росту распределенного программирования, которое стало основным направлением работ в 80-х и, особенно, в 90-х годах. Суть распределенного программирования состоит в организации взаимодействия процессов путем передачи сообщений, а не записи и чтения разделяемых переменных.
Разрабатываемые подходы использования компьютеров основаны на
тезисе: компьютер — это инструмент познания, с помощью которого добывают
новую информацию об исследуемом объекте или явлении [16]. Следовательно,
квалифицированный пользователь должен владеть современной методологией
познания — моделированием. Моделирование - это не только конструирование
объекта познания, но и метод познания. Моделирование есть методология
работы, эффективность которой раскрывается лишь при высокой
квалификации специалистов и при их свободном владении современными
средствами формализации - логикой и математикой.
При разработке современного программного обеспечения необходимо не только учитывать нелинейные (с обратным влиянием) связи между всеми звеньями вычислительной цепочки, но и реализовывать возможность сегментации программы на высоком, среднем и низшем уровнях параллелизации вычислительного процесса. Сегментация необходима для более эффективного использования многопроцессорных систем. Кроме этого, при разработке численного алгоритма следует увязывать между собой вопросы точности и надежности конечного программного обеспечения, а также вопросы его эффективности и переносимости под конкретную архитектуру вычислительной системы. Таким образом, параллельное программирование существенно отличается от традиционного — последовательного.
Принимая во внимание, что разработка параллельного программного обеспечения на сегодняшний день представляется достаточно сложной, проблема создания теоретических основ его проектирования стоит еще более остро. Моделирование может позволить описать все особенности взаимодействия параллельных процессов на уровне имитационной модели, а также провести анализ структуры и свойств разрабатываемых программ на всех этапах проектирования. Благодаря этому на раннем этапе проектирования программного обеспечения можно выбрать наиболее эффективные и простые в реализации алгоритмические решения.
В настоящее время во всем мире идет активная работа по совершенствованию теоретических и практических основ параллельного программирования. Это отражено в работах В. Воеводина, Вл. Воеводина, В. Гергеля, Р. Стронгина (в России), Г. Эндрюса, И. Фостера, Д. Астона (за пределами нашей страны). Разработано множество моделей вычислений, но наиболее развиты модели для последовательных алгоритмов и не все из них можно применить к параллельным напрямую. Существующие параллельные модели и методики не позволяют провести комплексный анализ параллельных алгоритмов. Особенно с учетом архитектурных особенностей вычислительных
7 систем. В частности, нет методик анализа вычислительного процесса на гетерогенных (неоднородных) вычислительных системах и способов получения наиболее эффективных его реализаций,
В работе В. Гергеля и Р. Стронгина (Нижегородский государственный университет им. Лобачевского) предлагается использовать модель программы в виде сетей Петри; в работе С. Востокина (Самарский государственный аэрокосмический университет) предлагается логическая модель, позволяющая описывать функционирование параллельных процессов. Данные модели не обладают такими широкими возможностями, как, например, модель марковских процессов. А марковские цепи не допускают наличия совместных состояний. Один из возможных вариантов - использование модели недетерминированных цифровых автоматов, которая подробно рассмотрена в работах Н.П. Вашкевича (Пензенский государственный университет). Применение их более перспективно совместно с другими моделями, например с моделью марковских процессов.
Целью данной диссертационной работы являются оценка и повышение эффективности параллельных распределенных вычислений за счет реорганизации параллельных алгоритмов и эффективной организации неоднородной вычислительной системы.
Поставленная цель достигается решением следующих задач:
Анализ вариантов классификации распределенных вычислительных систем и вариантов распараллеливания алгоритмов.
Исследование существующих моделей алгоритмов, выбор математических моделей и их применение для анализа параллельных алгоритмов.
Анализ вариантов организации распределенных вычислительных систем и существующих технологий параллельного программирования с выявлением присущих им преимуществ и недостатков.
Разработка способа оценки трудоемкости параллельных алгоритмов и параллельного вычислительного процесса на гетерогенных вычислительных системах.
Повышение эффективности параллельных вычислений за счет
8 эффективной организации вычислительного процесса на гетерогенной вычислительной системе.
6. Разработка параллельной гетерогенной вычислительной системы для эффективной реализации параллельных алгоритмов.
Объектом исследования диссертационной работы является параллельная распределенная вычислительная система и организация на ее базе вычислительного процесса.
Предметом исследования являются эффективная организация параллельных распределенных вычислений, оценка и повышение их эффективности.
Методологическая основа работы включает в себя методы теории марковских процессов и теории цифровых автоматов, а также элементы теории графов.
Научная новизна состоит в развитии научных основ и теоретическом анализе способов и методов организации и функционирования распределенных вычислительных систем и параллельных алгоритмов,
В результате проведенных исследований было предложено следующее:
Методики построения моделей параллельных вычислительных процессов гетерогенных кластерных систем на основе теории цифровых автоматов и теории марковских цепей, позволяющие производить анализ и оценку трудоемкости.
Методика анализа трудоемкости параллельных алгоритмов, позволяющая выбирать наиболее эффективную реализацию программы.
Способ повышения эффективности параллельного вычислительного процесса, позволяющий сократить время вычислений за счет изменения трудоемкости подзадач в соответствии с производительностью вычислительных узлов.
Способ организации эффективной вычислительной системы, позволяющий осуществлять динамическую балансировку вычислений на узлах вычислительной системы за счет разделения программы на заведомо большое число ветвей и асинхронного запуска параллельных процессов.
Практическая ценность заключается в разработке организации параллельной гетерогенной вычислительной системы, позволяющей повысить эффективность параллельных вычислений. Достоверность полученных результатов подтверждается экспериментальными исследованиями и математическими расчетами.
Реализация и внедрение результатов работы. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в Пензенском государственном университете. Данная диссертационная работа проводилась по гранту для поддержки научно-исследовательской работы аспирантов высших учебных заведений Минобразования России по теме «Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов» (шифр АОЗ-3.16-361). Результаты диссертации использовались также для проведения работ по гранту Минобразования России на тему «Теория и методы организации управления распределенными вычислительными процессами в многопроцессорных вычислительных системах и метакомпьютерных сетях» (шифр Т02-03.3-2476). Результаты работы были использованы в рамках создания «Регионального центра суперкомпьютерных вычислений и телекоммуникационных баз данных коллективного пользования». Результаты диссертационной работы применялись при организации учебного процесса на кафедре «Вычислительная техника» Пензенского государственного университета.
Апробация работы. Основные результаты работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях и семинарах, в том числе:
XII и XIII международная школы-семинары «Синтез и сложность управляющих систем» (Пенза, октябрь 2001 и 2000гг);
XIII научно-технической конференция студентов и профессорско-преподавательского состава Пензенского государственного университета. (Пенза, 2002г.);
V и VI международные научно-технические конференции «Новые
10 информационные технологии и системы» (Пенза, 2002 и 2004 гг.);
Международный юбилейный симпозиум «Актуальные проблемы науки и образования» (Пенза, 2003 г.);
V и VI всероссийские научно-практические молодежные конференции «Антикризисное управление в России в современных условиях» (Москва, МГТУ им. Н.Э. Баумана, 2003 и 2004гг).
Публикации. По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей и 9 тезисов докладов.
Структура и объем работы. Данная диссертационная работа состоит из четырех глав, заключения, списка использованной литературы, включающего 71 наименование, и шести приложений.
В первой главе проводится обзор существующих классификаций вычислительных систем, в частности распределенных вычислительных систем. Анализируются варианты построения высокопроизводительных систем с параллельной обработкой данных. Анализируются существующие модели вычислительных процессов и возможности, предоставляемые ими для анализа. Также проводится анализ существующих методик оценки и повышения эффективности параллельных распределенных вычислений. На основании проведенного анализа формулируются задачи дальнейшего исследования.
Во второй главе предлагаются модели для описания параллельного вычислительного процесса. Данные модели основаны на теории цифровых автоматов и марковских процессов. Полученные во второе главе результаты дают возможность оценивать параллельные алгоритмы по трудоемкости.
Третья глава посвящена организации эффективных параллельных вычислений за счет выбора наиболее эффективного алгоритма путем оценки трудоемкости различных реализаций его программ, реорганизации вычислительного алгоритма с учетом конкретной вычислительной системы и организации вычислительной системы наиболее эффективным способом с учетом алгоритма, который необходимо реализовать. В данной главе описывается разработанная распределенная высокопроизводительная
11 вычислительная система MathNet и технология программирования для нее.
Четвертая глава посвящена разработке программных средств для проверки полученных теоретических результатов. В ней приводится разработка, оценка и усовершенствование алгоритма вычисления интеграла методом Симпсона и умножения матриц. Даны результаты замеров временных характеристик работы данных алгоритмов и их графическое отображение.
В заключении перечислены основные результаты работы.
В приложениях приведены примеры анализов алгоритмов по трудоемкости и тексты разработанных по ним программ.
Основные положения, выносимые на защиту:
Методика построения модели параллельных алгоритмов на основе теории недетерминированных цифровых автоматов, позволяющая проводить функциональный анализ алгоритмов, и с использованием детерминизации перейти к модели на основе марковских процессов.
Методика построения модели параллельных алгоритмов на основе теории марковских процессов, позволяющая проводить оценки алгоритмов по трудоемкости.
Методика оценки эффективности параллельного вычислительного процесса, позволяющая оценить его эффективность с учетом особенностей вычислительной системы и выбрать наиболее эффективную его реализацию.
Способ повышения эффективности параллельного алгоритма и способ организации эффективных параллельных вычислений, позволяющий сократить время вычислений за счет равномерной загрузки вычислительных узлов гетерогенной вычислительной системы.
Методика построения эффективной гетерогенной параллельной вычислительной системы, позволяющая наиболее оптимальным образом организовать параллельные вычисления за счет динамической балансировки загрузки вычислительных узлов.
Основные понятия
Процесс - последовательная смена явлений, состояний в развитии чего-либо; совокупность последовательных действий для достижения какого-либо результата [66]. Процессы выполняются по соответствующим алгоритмам. Параллельные процессы — процессы, выполняющиеся в одно время.
Параллельная обработка - модель выполнения прикладного процесса одновременно группой процессоров, обеспечивающая исключительно высокую производительность системы. Осуществляется обработка в многопроцессорных комплексах. Задача, в данном случае, — математический вопрос, требующий разрешения, то, что задано для решения, [67]. В данной работе под задачей понимается некоторый математический вопрос или задание, для разрешения которой требуется путем вычислений найти какие-нибудь величины.
Подзадача, в данной работе, - это часть задачи, выделяемая по определенным признакам (по совокупности данных). Каждая задача состоит из набора подзадач, решение задачи есть решение всех ее подзадач. С точки зрения реализации они представляют собой блоки кода задач, работающие параллельно на разных машинах. Программа - последовательность действий (операций), предложенная в целях достижения конкретного результата. Программа описывает операции, которые нужно выполнить для решения поставленной задачи. Для вычислительной машины программа - описание алгоритма решения задачи, заданное на языке программирования (на машинный язык конкретной ЭВМ переводится автоматически с помощью транслятора). Процесс составления программ называют программированием.
Как отмечалось выше, класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рис. 1.1. Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством.
Как видно из данной классификации, параллельная программа в зависимости от алгоритма работы будет лучше реализовываться на той или иной архитектуре. Данная работа в основном ориентирована на программы для неконвейерных архитектур, т.е. для переключаемых и представленных сетью, в частности на кластеры рабочих станций. Еще одним вариантом детализации класса MIMD является классификация SMP/MPP. Данная классификация рассмотрена в [17, 22].
Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая - на использовании общей памяти.
Существующие MIMD-системы распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти, и методику их межсоединений.
К первому классу относятся системы с разделяемой (общей) основной памятью (Shared Memory multiprocessing, SMP), объединяющие до нескольких (2-16) процессоров, число которых зависит от типа применяемой коммуникационной среды. Сравнительно небольшое количество процессоров в таких системах позволяет иметь одну централизованную общую память и зачастую объединить процессоры и память с помощью лишь одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров [23],
Второй класс составляют крупномасштабные вычислительные системы с распределенной памятью. Подобные ВС получили название систем с массовым параллелизмом (Mass-Parallel Processing, МРР). Для того чтобы подключать в систему большое количество процессоров, необходимо физически разделять основную память и распределять её между ними. В противном случае пропускной способности памяти просто может не хватить для удовлетворения запросов, поступающих от очень большого числа процессоров. Естественно при таком подходе также требуется реализовать связь процессоров между собой [23].
Алгоритм параллельной программы
Для анализа параллельного вычислительного процесса надо знать, что собой представляет параллельная программа и ее алгоритм. Пример схемы общего алгоритма работы параллельной программы представлен на рис. 2.1. На нем показана схема решения задачи, включающей в себя и параллельных подзадач. Подзадачи, в данном случае, это части программы, выполняющиеся в один момент времени на разных вычислительных узлах (процессорах).
В общем данная схема алгоритма является типовой для параллельной программы. Если рассматривать ее применительно к конкретным системам типа Beowulf-кластеров или метакомпьютеров, то при более подробном описании возникнут отличия, связанные со спецификой работы данных систем. Также стоит отметить, что части «разбиение на подзадачи», «параллельное решение подзадач» и «сборка результата» могут повторяться несколько раз. При всех отличиях в технологиях параллельных программ и построении кластерных систем есть общие части: начальная непараллельная обработка (загрузка исходных данных и разбиение на подзадачи - параллельные процессы), некоторая параллельная часть и общая завершающая часть — получение и вывод конечного результата.
Таким образом, алгоритм представленный на рис. 2.1, в общем случае соответствует любой параллельной программе, с тем лишь допущением, что «решение подзадач» может включать в себя синхронизацию между параллельными частями программы и/или переход (слияние) к одному процессу с последующим новым разделением. Кроме алгоритма программы и его характеристик необходимо знать характеристики параллельной ВС, такие как производительность ее узлов, быстродействие каналов связи между узлами и т.п. Из-за сложности описания всех характеристик системы и параллельного алгоритма необходимо применение формальных методов анализа путем использования математических моделей.
Путем проведения детерминизации НДА, задав веса состояний в виде вероятностей, установив вероятности переходов из состояния в состояние, можно получить марковскую модель. Но при этом она будет очень громоздка, так как детерминизация влечет за собой увеличение количества состояний, причем их будет тем больше, чем количество параллельных ветвей, поэтому применение такой модели будет ограничено алгоритмами с небольшим числом параллельных состояний. Конкретно определить данное число невозможно, так как оно связано с субъективными понятиями человека, строящего данную модель. Методика построения моделей параллельного алгоритма на основе теории цифровых автоматов выглядит следующим образом: 1. Необходимо синтезировать недетерминированный ЦА из алгоритма программы по методике, описанной в работах [48] и [49]. 2.
Определить степень детализации анализа: анализировать только серверный процесс или всю программу, включая параллельные ветви. 3. Построить граф серверного процесса аналогично рис. 2.3 с учетом реального алгоритма работы программы. 4. Произвести запуск программы с тестовыми данными. Для этого по результатам запуска определяются переходные вероятности (вероятности перехода из одного состояния в другое). 5. Составить систему уравнений Кронекера, по ней определить трудоемкость алгоритма серверного процесса. 6. При необходимости более детального анализа с учетом всех параллельных ветвей надо провести детерминизацию полного алгоритма и для него составить матрицу переходных вероятностей. 7. Составить систему Кронекера и по ней определить трудоемкость алгоритма. Марковская модель, описанная в разд. 2.5, более удобна для анализа сложных алгоритмов, так как рассматривает по отдельности его части. При этом нет необходимости проводить анализ всех параллельных частей, а нужно рассмотреть только различные по набору состояний (действий) части. Таким образом, методика построения такой модели будет выглядеть следующим образом: 1. Необходимо представить алгоритм в виде графа, аналогично графу на рис. 2.8. Для этого необходимо представить программу конечным числом состояний.
Одним состоянием может быть как отдельная элементарная операция, так и набор операции или арифметических действий. Степень детализации выбирается в зависимости от ветвления программы, наличия в ней циклов, повторяющихся частей (подпрограмм) и задач анализа. 2. Просчитать количество условных операций в каждой уникальной вершине. Вершины могут повторяться в разных ветвях, но количество операций в них одинаково и нет необходимости просчитывать их повторно. Условной операцией может быть простейшая элементарная операция или набор операций, повторяющийся во всех уникальных вершинах некоторое число раз; также условной операцией можно считать единицу времени, тогда рассчитывается, сколько времени выполняется каждая вершина. 3. Выделить в графе параллельную и непараллельную части. 4. Заменить параллельную часть одним состоянием «Р». 5. Провести анализ непараллельной части по трудоемкости в соответствии с разд. 2.5.3: составить матрицу вероятностей переходов, составить систему уравнений Кронекера, записать формулу трудоемкости. 6. Провести анализ параллельной части алгоритма в соответствии с разд. 2.5.2: выбрать различные ветви для проведения анализа, составить матрицы вероятностей переходов, составить систему уравнений Кронекера, записать формулы трудоемкости и рассчитать трудоемкости для различных ветвей (нет необходимости анализировать одинаковые по алгоритму ветви). 7. Выбрать одну из параллельных ветвей для полного анализа в зависимости от его условий (по минимальной, средней или максимальной трудоемкости).
Автоматная модель параллельной программы
В качестве модели работы параллельной программы удобно использовать автоматную модель, точнее модель в виде конечного недетерминированного цифрового автомата.
Наиболее простое определение НДА основывается на языке графов. Каждая вершина графа представляет некоторое событие S, из множества событий S системы, указывающее на изменение состояния модели, а связи между ними, отмеченные входными сигналами, представляют переходы системы от одного или нескольких событий к одному или нескольким другим. Одновременно может существовать одно или несколько событий. Переход по сигналу может быть как в другое, так и в текущее то же самое событие. Переходы осуществляются мгновенно в момент поступления сигнала.
Такая модель подходит наиболее оптимально, так как удовлетворяет всем условиям работы параллельной программы. На основе рассмотренного выше алгоритма можно составить автоматную модель работы некоторой параллельной программы. Она представляется в виде направленного графа, каждая вершина которого представляет собой состояние программы, отмеченное выходным сигналом, а ребра помечены входными сигналами
Каждая вершина графа, описывающего цифровой автомат, является некоторым событием в системе из некоторого алфавита. Поэтому можно считать, что в данном случае каждая вершина - это, используя терминологию принятую для НДА в [49], событие, которое соответствует наступлению определенного состояния программы. Каждое состояние это некоторая часть программы (подпрограмма) — элементарная операция или набор элементарных операций программы. В данном случае можно считать автомат асинхронным.
Полученный автомат будет недетерминированным, так как в нем будут присутствовать совместные состояния, т.е. программа будет находиться в одно время в нескольких состояниях. Таковыми являются состояния № 4, 5, 6, действия, выполняемые программой, в них будут производится параллельно, т.е. будут производиться в разных процессах. Соответственно количество одинаковых (по типу) состояний определяется количеством параллельных частей программы. Таким образом, получаем недетерминированный автомат.
Из данной модели видно, что в общем случае у некоторой параллельной программы есть общая непараллельная часть. В нее входит начальная инициализация - задание исходного состояния и исходных данных и распараллеливание - запуск параллельных процессов. Также общей частью является завершающая часть программы - получение конечного результата (это может быть сбор решения и его вывод). Входные сигналы, которыми отмечены переходы из /-го состояния ву-е, могут быть абстрактными (zy) или частными (х,у) входными сигналами. Можно считать, что данные сигналы выдаются по завершении подпрограммы выполняющейся в -ом состоянии. Данные сигналы и время, когда они будут существовать, определяются алгоритмом, по которому будет работать программа. Конкретное время наступления событий программы будет зависеть от реализации алгоритма на ВС.
Более просто работу данной программы можно описать графом, не имеющим параллельных частей. Для этого можно рассматривать работу алгоритма серверного процесса, включающего в себя непараллельные части программы.
Полученная модель позволяет проследить функционирования основной — серверной части программы. Так как она основная и в ней происходят основные действия — инициализация и получение результата, то по ней можно оценить временные характеристики программы. После проведения анализа серверного процесса можно попробовать проанализировать весь параллельный алгоритм в целом. Для этого надо рассмотреть цифровой автомат, включающий в себя параллельные части. Для простоты рассуждений можно принять число параллельных ветвей равное двум («=2). При этом получится цифровой недетерминированный автомат, показанный на рис. 2.4.
Кодировку сигналов надо делать с условием, что сигналы должны позволять различить переход из одной вершины в другую конкретную вершину. Они должны показывать, что осуществляется переход в некоторый момент времени. Хотя эти сигналы и определяют направление перехода, нет необходимости вводить большое количество сигналов, они должны различаться только на пересечении состояний, т.е., например, в случае совместных состояний 531 и 532 необходимо разделить переходы в состояния 541 и 542.
Для этого вводятся два различных сигнала хЗ\ и JC32, по одному из них осуществляется переход из 31 в 41, а по другому из 532 в 42, причем независимо друг от друга. В общем случае количество различных входных сигналов равно количеству переходов, а время их существования определяется алгоритмом программы.
Построение высокопроизводительной вычислительной системы на основе кластерной технологии
Такие кластеры применяют для параллельных вычислений, причем такая система может обладать неплохими характеристиками по быстродействию, сравнимыми с показателями специализированных суперкомпьютеров, но стоимость такой системы относительно невелика. Еще одним из преимуществ такой гетерогенной вычислительной системы может быть то, что отдельные части программы могут выполняться на наиболее подходящих для этого компьютерах.
В общем случае по данной технологии можно строить высокопроизводительные вычислительные системы и с использованием специализированных мощных вычислительных машин или специально закупаемых рабочих станций. Построение кластерной высокопроизводительной вычислительной системы сложнее, чем покупка мощного многопроцессорного сервера, но она будет существенно дешевле. Использование серверов средней мощности (2- или 4-процессорных) в качестве рабочих станций кластера позволяет получить достаточно высокопроизводительную систему, причем их можно объединить с обычными персональными компьютерами и тем самым расширить возможности применения системы.
Как отмечено в [24], для того чтобы построить кластер, необходимо решить ряд проблем. Прежде всего, следует иметь в виду, что довольно часто в сеть объединяют компьютеры разных фирм-производителей, имеющие разную архитектуру, работающие под управлением разных операционных систем, с разными файловыми системами, при этом, возникает проблема совместимости. Имеется и проблема доступа, так как для входа в любой компьютер может потребоваться разрешение работать на нем. Может быть и так, что время счета измеряется днями, а то и неделями, а некоторые из рабочих станций кластера время от времени должны быть загружены своей собственной работой. То есть особенно важным оказывается управление такой вычислительной системой — очень динамичной и специфической. Некоторые из перечисленных проблем могут быть решены административным путем, для решения других требуется специальное программное обеспечение, реже специальная аппаратура, так как оборудование уже есть, включая процессоры и сети. В качестве примера можно привести систему управления гетерогенными кластерами рабочих станций CONDOR [26]. Эта система позволяет пользователю сохранить за собой полный контроль над своей собственной рабочей станцией и не требует от него наличия прав доступа к другим станциям. Она также не требует создания специальных файловых систем и обеспечивает достаточно гибкое управление процессом выполнения программ. Важно еще и то, что эта система бесплатная. Другие примеры бесплатных систем такого рода — DQS и PBS (разработка НАСА). Коммерческие системы - CODINE [27], LoadLeveler (IBM) [28] и пр. Данная работа ориентирована на архитектуры MIMD с переключением или сетью, SMP и МРР, в частности на кластеры рабочих станций, как на самую доступную в настоящее время возможность реализации параллельного суперкомпьютера.
Для анализа работы параллельной программы необходимо выбрать математическую модель, позволяющую описывать и оценивать процессы, происходящие в системе параллельных вычислений при выполнении на ней некоторой программы. Это необходимо для наиболее эффективного использования вычислительных ресурсов и осознания необходимости использования параллельных вычислений, а также для сравнения различных алгоритмов решения одной и той же задачи с точки зрения выбора наиболее эффективного и минимизации затрат на его реализацию.
Производители традиционных коммерческих суперкомпьютеров (SMP, МРР, параллельных векторных) стремятся улучшить производительность, надежность и простоту использования своих продуктов. Однако у этих компьютеров есть один большой недостаток - цена, подчас недоступная для многих образовательных и научно-исследовательских организаций. Однако потребность в вычислительных ресурсах у этих организаций велика.
Следует иметь в виду, что производительность персональных компьютеров за последние годы также значительно выросла. Одновременно стала приобретать все большую популярность ОС Linux - бесплатно распространяемая версия UNIX. При этом в научных организациях и университетах, как правило, имеются энтузиасты бесплатно распространяемого ПО и специалисты по ОС Linux.
Возникла идея создавать параллельные вычислительные системы (кластеры) из общедоступных компьютеров и недорогих Ethernet-сетей, устанавливая на эти компьютеры Linux и одну из бесплатно распространяемых коммуникационных библиотек (PVM или MPI). Оказалось, что на многих классах задач и при достаточном числе узлов такие системы дают производительность, сравнимую с суперкомпьютерной.
Проект разрабатывался в научно-космическом центре NASA - Goddard Space Flight Center (GSFC), точнее в созданном на его основе CESDIS (Center of Excellence in Space Data and Information Sciences).
