автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Модели, методы и средства представления знаний для повышения производительности MPI приложений

на правах рукописи

005013870 фе/^ ...

Дергунов Антон Владимирович

МОДЕЛИ, МЕТОДЫ И СРЕДСТВА ПРЕДСТАВЛЕНИЯ ЗНАНИЙ ДЛЯ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ MPI ПРИЛОЖЕНИЙ

Специальность 05.13.17 - «Теоретические основы информатики» по техническим наукам

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 5 [<]др 2G12

Нижний Новгород - 2012г.

005013870

Работа выполнена на кафедре математического обеспечения ЭВМ Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

Защита диссертации состоится «5» апреля 2012 г. в 13 часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан «3» марта 2012 г.

Ученый секретарь диссертационного совета,

Научный руководитель:

кандидат технических наук, доцент Карпенко Сергей Николаевич

Официальные оппоненты: Хранилов Валерий Павлович, доктор

технических наук, доцент, НГТУ им. P.E. Алексеева, профессор кафедры компьютерные технологии в проектировании и производстве;

Немнюгин Сергей Андреевич, кандидат физико-математических наук, доцент, СПбГУ, доцент кафедры вычислительной физики

Ведущая организация: Южно-Уральский государственный

университет, г. Челябинск.

кандидат технических наук

Суркова Анна Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Одним из наиболее актуальных направлений современного программирования является разработка параллельных алгоритмов и программ. Задача разработки таких программ и повышения их производительности достаточно сложна. Исследованию вопросов анализа производительности параллельных приложений в последние годы было посвящено множество публикаций. Среди них можно выделить работы J. Dongarra, Т. Sterling, М. Resch, W.D. Gropp, В. Mohr, F. Wolf, J. Vetter. В России направление анализа производительности параллельных приложений развивается в научных коллективах Вл.В. Воеводина, Л.Б. Соколинского, С.А. Немнюгина, В.П. Гергеля, В.А. Крюкова, A.B. Бухановского, Б.Н. Четверушкина, М.В. Якобовского, В.Э. Малышкина, С.М. Абрамова.

Для практического решения задачи повышения производительности разрабатываются специальные системы, позволяющие оценивать производительность параллельных приложений и выявлять наиболее «тяжелые» участки кода (проблемы производительности). На основе этих данных эксперт может принять решение по оптимизации программного кода с целью сокращения потерь на этих участках. Общий недостаток таких систем состоит в том, что задача выявления проблем производительности остается достаточно сложной ввиду большого объема обрабатываемой информации и сложности связей, порождающих отдельные проблемы. Кроме того, выявленные экспертом проблемы производительности и принятые решения по их устранению в таких системах не сохраняются тогда, как большая часть проблем имеют, как правило, достаточно типовой характер и могут проявляться в других параллельных приложениях. В этих условиях актуальной является задача разработки системы, способной накапливать знания экспертов по выявлению типовых проблем производительности параллельных приложений и способам их устранения.

Библиотека MPI (Message Passing Interface) является де-факто стандартом для разработки параллельных приложений. К настоящему времени создано достаточно большое количество MPI приложений, и выбор этого типа приложений в качестве основного объекта исследований является актуальным.

Целью диссертационной работы является разработка программной системы, обеспечивающей накопление знаний о типовых проблемах производительности MPI приложений, методах их выявления и способах их возможного разрешения.

В соответствии с целью диссертационной работы поставлены следующие задачи:

1. Предложить модели и методы представления знаний для анализа типовых проблем производительности MPI приложений.

2. Разработать алгоритмы выполнения анализа проблем производительности для предложенных моделей и методов представления знаний.

3. Разработать программную систему, реализующую предложенные модели, методы и алгоритмы.

4. Описать с помощью разработанных методов и средств ряд типовых проблем производительности MPI приложений.

5. Исследовать эффективность разработанных моделей, методов и средств для анализа производительности MPI приложений.

Методы исследования. Работа базируется на методах систем, основанных на знаниях, математической логики, объектно-ориентированного программирования.

Научная новизна работы состоит в следующем:

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

2. Предложены средства идентификации проблем производительности MPI приложений. Предложенные средства включают модели и языки описания:

• правил трассировки действий идентифицируемой проблемы производительности;

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

• правил выявления проблем производительности из множества сконструированных составных событий.

3. Разработаны алгоритм генерации трассировщика MPI приложения по заданным правилам трассировки действий отдельных проблем производительности и алгоритм конвертирования правил конструирования составных событий и правил выявления проблем производительности в правила экспертной системы CLIPS.

Практическую ценность работы составляют:

1. Программная система Performance Expert, реализующая предложенные модели, методы и алгоритмы.

2. База знаний для идентификации десяти типовых проблем производительности MPI приложений, описанная с использованием предложенных моделей и методов.

3. Результаты исследования эффективности разработанных моделей, методов и средств при анализе производительности MPI приложений.

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

Внедрение результатов работы. Результаты диссертационной работы внедрены в ЦНИИ «Буревестник», в проведение научных исследований ННГУ и в учебный процесс ННГУ, что подтверждается актами о внедрении.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих конференциях: международных конференциях «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2010-2011), международной конференции «Научный сервис в сети Интернет: экзафлопсное будущее» (Дюрсо, 2011), международной конференции «Параллельные вычислительные технологии» (Москва, 2011), международной конференции «Супервычисления и математическое моделирование» (Саров, 2010), международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 2011), всероссийской конференции «Искусственный интеллект: философия, методология, инновации» (Москва, 2011), всероссийских конференциях «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2009-2010), семинарах кафедры МО ЭВМ факультета ВМК ННГУ.

На конкурсах научных работ аспирантов V всероссийской конференции "Искусственный интеллект: философия, методология, инновации" (Москва, 2011) и всероссийской конференции "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, 2009) доклады автора были отмечены дипломами.

Публикации. По теме диссертации опубликовано 11 печатных работ, из них 2 статьи в ведущих рецензируемых журналах из списка ВАК. Список публикаций приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем работы составляет 156 страниц, включая 40 рисунков и 12 таблиц. Список литературы включает 98 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 даны общие сведения о системах, основанных на знаниях, моделях и методах представления знаний.

В разделе 1.1 рассматриваются общие принципы организации систем, основанных на знаниях, условия их применения, приводится обзор известных систем такого типа, применяемых для анализа производительность компьютерных программ.

В разделе 1.2 приведено описание структуры системы, основанной на знаниях, основных режимов ее работы и этапов конструирования базы знаний (инженерии знаний).

В разделе 13 рассматриваются общие принципы и методы представления знаний, требования к модели представления знаний. Приводится обзор известных моделей представления знаний.

В разделе 1.4 более подробно рассматривается продукционная модель представления знаний, принципы и стратегии логического вывода, особенности реализации продукционной модели в системе CLIPS.

В главе 2 рассматривается современное состояние проблемы анализа производительности MPI приложений.

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

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

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

В разделе 2.4 приведен список и краткая характеристика задач повышения производительности, возникающих при использовании метода прямого измерения производительности:

1. Выбор метрик оценки производительности.

2. Сбор данных производительности.

3. Визуализация данных производительности.

4. Выявление проблем производительности на основе данных.

5. Поиск способов устранения проблем производительности.

6. Устранение проблем производительности.

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

В главе 3 представлено описание предлагаемых в работе моделей и методов представления знаний для анализа производительности MPI приложений.

В разделе 3.1 предложена модель MPI приложения. MPI приложение рассматривается как множество взаимодействующих процессов PR = {prt,pr2,...,prN}. Взаимодействие процессов осуществляется с помощью действий, инициируемых процессами в определенной последовательности: PR, => Л,. = (at);i = 1,2.....NJ = 1,2,..., M !

Каждое действие процесса состоит в вызове функций библиотеки MPI F-{fi}>k = \,2,...,K. Функция fk характеризуется входными и выходными аргументами:

WA,n - ! fJN \. ГГАОЧТ _ / r„OUT fOVT \

tAt =(Jan,...,JaiL,„y,FAk = (Jatl ,...Jati;,,l,)

Таким образом, каждое действие процесса характеризуется вызываемой функцией библиотеки и значениями входных и выходных аргументов:

a^{ft,FAvairFAvair)

Где:

FAvaC=(aV^,...,aV^y,FAr =(av™ ,.,av™).

В разделе 3.2 формулируется задача повышения производительности MPI приложения. Каждому действию a:j процесса соответствует время

начала его выполнения и длительность d°. Под производительностью MPI

приложения понимается суммарная длительность выполнения действий всеми процессами:

Л' м,

'=1 M

Повышение производительности взаимодействия процессов определяется как D" min.

Отмечается, что в силу сложности сформулированной задачи в работе экспертный подход, основанный на выявлении и накоплении знаний по отдельным (типовым) проблемам производительности MPI приложений.

В разделе 3.3 предложена модель типовой проблемы производительности MPI приложения. Проблема производительности представляется как:

рЪ = ( pd, dur, TRR ULES, A NR ULES, REC( A,SF0 )}

где:

pd - вербальное описание проблемы; dur — длительность проявления данной проблемы; TRRULES - правила трассировки действий проблемы; ANRULES - правила распознавания проблемы; ЛЕС - рекомендации по ее устранению;

AmFO ={(fl,tl,di,pri,csj)} - описание действий, приведших к проблеме (где ft - функция действия, t, - время вызова функции, di - длительность работы функции, prt - процесс, который инициировал вызов функции, a csi -место в исходном коде, из которого осуществлялся вызов);

В разделе 3.4 приводится описание общей схемы работы системы Performance Expert.

Рис. 1. Схема работы системы Работа с системой состоит из двух этапов (см. рис. 1):

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

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

В разделе 3.5 предложены модель трассировки MPI приложения и язык описания правил трассировки TRRULES модели проблемы производительности. Результатом работы трассировщика является трасса работы MPI приложения, в которой зарегистрированы простые события, вызванные действиями процессов.

Простое событие представляется как:

е = (f,et,EPval,t,d,pr,cs)

где:

/ е F - функция действия;

et - тип события, который задает набор параметров события ЕР = (ер{,...,ерк)\

EPval = (v,,...,v^) - значения параметров события; t - время наступления события; d — длительность события;

pre PR - процесс, на котором произошло событие;

cs - место в исходном коде, из которого осуществлялся вызов функции.

Правило трассировки представляется как:

a = (f,FAval'\FAval0UT)-^-+e = (f,et,EPval,t,d,pr,cs) trrule = (f,et, EPtemp)

где:

/ 6 F - функция, при выполнении которой трассировщиком создается событие, определяемое правилом;

et - тип события, задаваемый правилом трассировки;

EPtemp = {(epl,Expri,kindi)};i=l,...,N - описание параметров события и

способа получения их значений, где: ept - параметр события;

Expr{: FAvalm х FAval0UT v( - функция для вычисления значения v, параметра на основе аргументов вызванной функции; kind, е. {in,out) - характер параметра (in - входной, т.е. вычисляемый только на основе входных аргументов функции; out - выходной, т.е. формируемый на основе выходных аргументов функции или входных и выходных). Значения параметров t,d,pr и cs события формируются трассировщиком.

В разделе также предложен язык описания правил трассировки. Функции действия проблемы задаются с помощью деклараций, имеющих синтаксис:

<function пате="имя функции">

«argument type="MMH типа" пате="имя аргумента" />

<retVal type="HMfl типа" /> «/function? где:

function описание функции, задающее ее имя и аргументы feF; argument аргументы функции (FA,S ,FAOUT); retval тип возвращаемого функцией значения.

Правила трассировки описываются в виде последовательности деклараций, имеющих синтаксис:

<functionPoint пате="имя типа события"

ра^егп="шаблон имени функции"»

<event>

<param паше="имя параметра" format="™n значений" kind="in/out"> <Боигсе>выражение для вычисления значения</зоигсе> </param>

</event> </functionPoint> где:

functionPoint описание правила, задающее имя типа события et и множество функций F™*"" çF, для которых правила trrule задают одинаковый тип события; param описание параметров события и способов получения

их значений ЕР temp ; В разделе 3.6 предложена модель анализа производительности MPI приложения и языки описания правила конструирования составных событий и правила выявления проблем производительности. Схема выполнения анализа представлена на рис. 2.

Исходными данными для анализа является трасса MPI приложения, сформированная в результате трассировки и содержащая простые события, а результатом анализа - множество выявленных проблем производительности. Анализ осуществляется на основе правил распознавания проблем производительности ANRULES и осуществляется в два этапа:

1. Конструирование составных событий как претендентов на отдельные типы проблем производительности.

2. Выявление проблем производительности из множества сконструированных составных событий.

РП - Р')

сш

MPI пр«(|яммя С^

Тржся

С'«гтавны* («»итм

СЕ

Прмлемы

ПЫ»0ДНТ«ЛЫ10СТ11

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

се = {cet, CEPval, ME)

где:

cet — тип составного события, который задает набор параметров события СЕР = (cept,...,серк);

CEPval = (ceviy...,cevK) - значения параметров составного события; ME = {el}yj{ceJ}\i = \,...,N\j = \,...,M - множество простых и составных событий-членов.

Правило конструирования составного события представляется как: E-Z-+E*

СЕ-

СЕТ

*CER

> се = (cet,CEPval, me)

cerule = (ET,CET, a, cet, CEPtemp, ETS)

где:

ЕТ = = - множество типов простых событий для выборки из множества простых событий трассы Е подмножества событий Е" = с £;/ = , релевантных анализируемой

проблеме производительности;

СЕТ = {се^};/ = 1,..., М — множество типов составных событий для выборки из множества составных событий СЕ подмножества релевантных событий СЕ" = {([cetJ,CEPvalJ,MEJ^} с С£;у = 1,...,М указанных типов;

Обозначим с помощью EPVl={f„EPvali,tf,dl,prl,cs^\i = \,...1N и Р = EPVX х... х EPVn х С ЕР val{ х... х CEPvalu.

ст:Р->{0,1} - условие конструирования составного события (если значение функции а = 1, то составное событие может быть сконструировано для множества релевантных событий Е" и СЕ* и нет в противном случае); cet - тип составного события, конструируемого правилом; CEPtemp-{(cepk,Exprk}}\k = \,...,K - описание параметров конструируемого события и способов получения их значений, где: серк - параметр составного события;

Ехргк : Р —> cevk - функция для вычисления значения cevl параметра составного события; При выполнении условий правила (т.е. существовании подмножества релевантных событий ЕК и СЕ" и выполнении условия а) конструируется событие се указанного типа cet, где:

CEPval = (cevv...,cevK) - значения параметров событий, вычисляемые с помощью описания параметров CEPtemp ;

ME = Eru CEr - множество событий-членов;

Параметр правила ETS ç ET указывает типы событий, которые являются общими для конструируемого события и других составных событий. Остальные простые события, релевантные данному правилу, принадлежат только конструируемому составному событию.

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

declare composite event <имя типа составного события> member(

[<shared>] <тип события-члена> as <имя события>,

)

when

Слогическое выражение> parameters{

спараметр события> = <выражение для вычисления значения;»,

) ; где:

declare composite event описание правила конструирования

составного события типа cet ; member список типов простых ET и составных СЕТ событий для выборки подмножества релевантных событий; флаг shared указывается подмножества типов ETS çET; имя события используется для ссылки на его параметры в логическом выражении и выражениях для вычисления значений параметров события; when условие конструирования составного события с;

13

parameters описание параметров конструируемого события и способов получения их значений CEPtemp (с указанием параметров серк и выражений для вычисления их значений Ехргк );

Правило выявления проблемы производительности представляется как: се = (cet,CEPval,ME) <"""" > pb = {pd,dur,REC(AMFO)) pbrule = {cet, (p, pd, RECtemp, Ldur )

где:

cet - тип составного события как претендента на определяемую проблему производительности;

ç : CEPval {1,0} - условие возникновения проблемы (если значение функции <р = 1, то проблема существует и нет в противном случае);

pd - вербальное описание проблемы, определяемой правилом;

RECtemp : CEPval -> REC - шаблон рекомендации по устранению проблемы;

Ал-г -CEPval-* dur - функция вычисления длительности проблемы производительности;

При выполнении условий правила (т.е. выполнении для составного события се типа cet условия (р ) делается вывод о наличии проблемы производительности рЪ . Описание действий приложения, приведших к этой проблеме, формируется на основе функции интерпретатора Frec , т.е. AWF0 = Frec(ME) . Функция Frec осуществляет рекурсивное извлечение простых событий из ME и формирования на их основе информации о множестве действий.

Правила выявления проблемы производительности задаются в виде последовательности деклараций, имеющих синтаксис:

déclaré problem for <имя типа составного события> when

<логическое выражение> parameters(

name = "<название проблемы>", description = "сописание проблемы:»", advice = <шаблон рекомендации;»,

duration = <выражение для вычисления длительности;») ;

где:

déclaré problem for описание правила выявления проблемы

производительности для составного события-претендента типа cet ; условие возникновения проблемы (р ; название проблемы; вербальное описание проблемы pd ; шаблон рекомендации RECtemp ; функция вычисления длительности L,ur ;

when name

description

advice

duration

В разделе 3.7 описаны разработанные алгоритм генерации трассировщика по заданным правилам трассировки действий MPI приложения и алгоритм конвертирования правил конструирования составных событий и правил выявления проблем производительности в правила экспертной системы CLIPS.

Для каждой функции / е F, трассируемой в соответствии с правилом

трассировки, генератором трассировщика создается функция-обертка fWMP, определенная на тех же аргументах FAm ,FA0UT, что и исходная функция /. При выполнении MPI приложением действия а = (f,FAvalIN tFAval0UT)

вместо исходной функции / трассировщик выполняет функцию fWRAP , которая формирует событие, определенное правилом, и вызывает исходную функцию /.

Как отмечалось, конструирование составных событий и выявление проблем производительности выполняется с помощью экспертной системы CLIPS. В работе применяется следующая схема использования экспертной системы CLIPS.

Для представления простых и составных событий, а также выявленных проблем производительности используются факты CLIPS, динамически создаваемые в рабочей памяти CLIPS и удаляемые из нее.

На начальном этапе правила конструирования составных событий и выявления проблем производительности конвертируются в правила CLIPS.

На этапе анализа трассы интерпретатор системы Performance Expert выполняет следующий алгоритм:

Пока не достигнут конец трассы:

1. Считать очередное простое событие из трассы.

2. Конвертировать его в факт CLIPS.

3. Запустить CLIPS. Для нового факта-простого события машина вывода CLIPS последовательно выполняет правила конструирования составных событий, для конструируемых составных событий-фактов - правила выявления проблем производительности. Результатом срабатывания CLIPS может быть:

a. добавление нового факта-простого события в некоторые из конструируемых фактов-составных событий;

b. идентификация фактов-составных событий рабочей памяти на соответствие или несоответствие проблеме производительности;

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

4. Извлечь из рабочей памяти факты-составные события, идентифицированные на соответствие проблеме производительности; идентифицированные на несоответствие удалить.

В разделе приводятся описания алгоритмов и правил генерации (конвертирования) правил и фактов CLIPS.

В главе 4 представлено описание разработанной программной системы Performance Expert.

В разделе 4.1 описана общая организация системы Performance Expert, схемы реализации модуля трассировки MPI приложения и модуля анализа трассы; рассмотрен состав и назначение отдельных компонент модулей; приведено описание пользовательских интерфейсов.

В разделе 4.2 приведен краткий обзор состава базы знаний системы Performance Expert по описанию десяти типовых проблем производительности MPI приложений.

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

В разделе 4.4 по аналогичной схеме приведено описание проблем коллективных операций обмена: ранний прием данных при операции «от многих к одному», поздняя посылка данных при операции «от одного ко многим», задержка перед операцией «от многих ко многим» и задержка перед барьерной синхронизацией.

В разделе 4.5 по аналогичной схеме приведено описание проблем операций удаленного доступа к памяти: задержка при создании «окна» для удаленного доступа к памяти, конкуренция за блокировку «окна» для удаленного доступа к памяти, позднее начало периода предоставления доступа к «окну» и раннее завершение периода предоставления доступа к «окну».

В главе 5 приведено описание вычислительных экспериментов по анализу и повышению производительности MPI программ с использованием разработанной системы.

В разделе 5.1 описывается общая схема и условия проведения вычислительных экспериментов, характеристики кластера, на котором проводились вычислительные эксперименты. Вычислительные эксперименты проводились с MPI программами решения трех задач: решения задачи Дирихле методом Якоби и методом Гаусса-Зейделя и решения задачи моделирования сердечной активности. MPI алгоритмы решения первых двух задач были заимствованы в литературных источниках.

В разделе 5.2 приведено описание и результаты эксперимента по анализу и повышению производительности MPI программы решения задачи Дирихле методом Якоби. Проведенный с помощью системы Performance Expert анализ выявил две проблемы производительности. Использование полученных рекомендаций позволило в среднем повысить

производительность в 1,64 раза; максимальное повышение производительности (в 2,4 раза) было достигнуто при 64 процессорах.

В разделе 5.3 приведено описание и результаты эксперимента по анализу и повышению производительности MPI программы решения задачи Дирихле методом Гаусса-Зейделя. Эксперимент проводился с двумя известными вариантами параллельной схемы решения этой задачи: «наивной» и «красное-черное».

Проведенный с помощью системы Performance Expert анализ программной реализации «наивной» схемы выявил две проблемы производительности. Полученные при этом рекомендации полностью соответствовали переходу от «наивной» схемы к схеме «красное-черное». Использование полученных рекомендаций позволило в среднем повысить производительность в 10 раз; максимальное повышение производительности (в 19 раз) было достигнуто при 128 процессах.

Проведенный с помощью системы Performance Expert анализ программной реализации схемы «красное-черное» выявил две проблемы производительности. Но длительность проблем была очень мала, и поэтому дальнейшее повышение производительности не выполнялось.

В разделе 5.4 приведено описание и результаты эксперимента по анализу и повышению производительности MPI программы моделирования сердечной активности. Проведенный с помощью системы Performance Expert анализ выявил две проблемы производительности. Использование полученных рекомендаций позволило в среднем повысить производительность в 1,34 раза; максимальное повышение производительности (в 1,62 раза) было достигнуто при 101 процессе.

В заключении изложены основные научные и практические результаты диссертационной работы.

В приложениях приведены акты внедрения результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В работе получены следующие основные научные и практические результаты, выносимые на защиту:

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

2. Модели и методы идентификации проблем производительности MPI приложений:

a. Модели и язык описания правил трассировки действий проблемы производительности.

b. Модели и язык описания правил анализа трассы с целью конструирования составных событий как претендентов на отдельные типы проблем производительности.

c. Модели и язык описания правил выявления проблем производительности из множества сконструированных составных событий.

3. Алгоритмы идентификации проблем производительности для предложенных моделей и методов представления знаний:

a. Алгоритм генерации трассировщика MPI приложения по заданным правилам трассировки действий отдельных проблем производительности;

b. Алгоритм конвертирования правил конструирования составных событий и правил выявления проблем производительности в правила экспертной системы CLIPS;

4. Программная система Performance Expert, реализующая предложенные модели, методы и алгоритмы.

5. База знаний для идентификации десяти типовых проблем производительности MPI приложений, описанная с использованием предложенных моделей и методов.

6. Результаты исследования эффективности разработанных моделей, методов и средств при анализе производительности MPI приложений.

ПУБЛИКАЦИИ ПО ТЕМЕ Д ИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК

1. Дергунов, А. В. Обзор исследований в области автоматизации диагностики производительности MPI-приложений / А. В. Дергунов, С. Н. Карпенко // Вестник Нижегор. ун-та им. Н. И. Лобачевского. Сер., Информационные технологии. - 2011. - № 3(2). - С. 212-218.

2. Карпенко, С. Н. Язык описания типов проблем производительности при взаимодействии процессов в MPI-приложениях / С. Й. Карпенко, А. В. Дергунов // Вестник Нижегор. ун-та им. Н. И. Лобачевского. Сер., Информационные технологии. - 2011. - № 3(2). - С. 219-226.

Публикации в других изданиях

3. Карпенко, С. Н. Модели и программные средства повышения производительности MPI-приложений (с использованием системы CLIPS) / С. Н. Карпенко, А. В. Дергунов // Технологии Microsoft в теории и практике

программирования: материалы конф. - Н. Новгород: Изд-во Нижегор. гос. ун-та, 2009.-С. 188-192.

4. Дергунов, А. В. Модели и программные средства повышения производительности MPI-приложений (описание типов проблем производительности) / А. В. Дергунов, С. Н. Карпенко // Технологии Microsoft в теории и практике программирования: материалы конф. - Н. Новгород: Изд-во Нижегор. гос. ун-та, 2010. - С. 116-118.

5. Карпенко, С. Н. Автоматизация повышения производительности MPI-приложений / С. Н. Карпенко, А. В. Дергунов // Высокопроизводительные параллельные вычисления на кластерных системах: материалы конф. - Пермь: Изд-во Перм. гос. техн. ун-та, 2010. - Т. 1.-С. 307-312.

6. Карпенко, С. Н. Программные средства повышения производительности MPI-приложений / С. Н. Карпенко, А. В. Дер|унов // Супервычисления и математическое моделирование: тр. XII междунар. семинара. - Саров: РФЯЦ-ВНИИЭФ, 2011. - С. 195-202.

7. Дергунов, А. В. Автоматизация выявления причин потери производительности MPI программ на экзафлопсных и других больших суперкомпьютерах / А. В. Дергунов // Научный сервис в сети Интернет: экзафлопсное будущее: труды Междунар. суперкомпьютерной конф. - М.: Изд-во МГУ, 2011. - С. 491-496.

8. Дергунов, А. В. Декларативный подход к автоматизации выявления причин потери производительности MPI-приложений / А. В. Дергунов// Высокопроизводительные параллельные вычисления на кластерных системах: материалы XI Всерос. конф. - Н. Новгород: Изд-во Нижегор. гос. ун-та, 2011.-С. 108-112.

9. Дергунов, А. В. Обзор и сравнение подходов к автоматизации анализа производительности MPI-приложений / А. В. Дергунов // Высокопроизводительные параллельные вычисления на кластерных системах: материалы XI Всерос. конф. - Н. Новгород: Изд-во Нижегор. гос. ун-та, 2011.-С. 113-117.

10. Дергунов, А. В. База знаний причин недостаточной производительности MPI-программ / А. В. Дергунов // Искусственный интеллект: философия, методология, инновации: материалы V Всерос. конф. студентов, аспирантов и молодых ученых. - М.: МГТУ МИРЭА, 2011. - С. 153-156.

11. Дергунов, А. В. База знаний повышения производительности MPI-приложений / А. В. Дергунов // Интеллектуальные системы и компьютерные науки: материалы X Междунар. конф. - М.: Изд-во МГУ, 2011. - С. 43-46.

Подписано в печать 28.02.2012. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 119._

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

ВВЕДЕНИЕ.

1. МОДЕЛИРОВАНИЕ ЗНАНИЙ.

1.1. Системы, основанные на знаниях.

1.2. Структура систем, основанных на знаниях.

1.3. Принципы и модели представления знаний.

1.4. Продукционная модель представления знаний.

Выводы.

2. АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ MPI ПРИЛОЖЕНИЙ.

2.1. Многопроцессорные вычислительные архитектуры и MPI приложения.

2.2. Анализ производительности параллельных программ.

2.3. Методы анализа и измерения производительности параллельных программ.

2.4. Задачи повышения производительности MPI приложений.

2.5. Обзор существующих систем повышения производительности MPI приложений.

2.5.1. Системы Intel Trace Collector and Analyzer и Jumpshot.

2.5.2. Система Aksum.

2.5.3. Система Hercule.

2.5.4. Система KOJAK.

2.5.5. Система KappaPI.

2.5.6. Сравнительный анализ рассмотренных систем.

Выводы.

3. МОДЕЛИ И МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ MPI ПРИЛОЖЕНИЙ.

3.1. Модель MPI приложения.

3.2. Повышение производительности MPI приложения.

3.3. Модель проблемы производительности.

3.4. Общая схема работы системы.

3.5. Модель трассировки MPI приложения.

3.5.1. Обучение трассировщика.

3.5.2. Модель простого события.

3.5.3. Модель правила трассировки.

3.5.4. Язык описания правил трассировки.

3.6. Модель анализа производительности MPI приложения.

3.6.1. Схема выполнения анализа.

3.6.2. Модель составного события.

3.6.3. Модель правила конструирования составного события.

3.6.4. Язык описания правил конструирования составного события.

3.6.5. Правила выявления проблем производительности.

3.6.6. Язык описания правил выявления проблем производительности.

3.7. Алгоритмы идентификации проблем производительности.

3.7.1. Алгоритм генерации трассировщика MPI приложения.

3.7.2. Алгоритм конвертирования правил распознавания проблем производительности в правила CLIPS.

Выводы.

4. ПРОГРАММНЫЕ СРЕДСТВА АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ MPI ПРИЛОЖЕНИЙ.

4.1. Реализация программной системы Performance Expert.

4.1.1. Генератор трассировщика MPI приложений.

4.1.2. Анализатор трассы MPI приложений.

4.2. Состав базы знаний проблем производительности MPI программ.

4.3. Проблемы производительности MPI приложений при использовании двухточечных операций обмена.

4.3.1. Анализ двухточечной модели обмена сообщениями в MPI.

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

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

4.3.4. Описание проблемы поздней посылки сообщения.

4.3.5. Описание проблемы позднего приема сообщения.

4.4. Проблемы производительности MPI приложений при использовании коллективных операций обмена сообщениями.

4.4.1. Анализ коллективной модели обмена сообщениями.

4.4.2. Описание проблемы задержки перед барьерной синхронизацией.

4.4.3. Описание проблемы раннего приема данных при операции «от многих к одному».

4.4.4. Описание проблемы поздней посылки данных при операции «от одного ко многим».

4.4.5. Описание проблемы задержки перед операцией «от многих ко многим».

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

4.5.1. Анализ модели удаленного доступа к памяти.

4.5.2. Описание проблемы задержки при создании «окна» для удаленного доступа к памяти.

4.5.3. Описание проблемы конкуренции за блокировку «окна» для удаленного доступа к памяти.

4.5.4. Описание проблемы позднего начала периода предоставления доступа к «окну».

4.5.5. Описание проблемы раннего завершения периода предоставления доступа к «окну».

Выводы.

5. ПРИМЕНЕНИЕ ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ MPI ПРИЛОЖЕНИЙ.

5.1. Общая схема и условия проведения вычислительных экспериментов.

5.2. Анализ и повышение производительности программы решения задачи Дирихле методом Якоби.

5.3. Анализ и повышение производительности программы решения задачи Дирихле методом Гаусса-Зейделя.

5.4. Анализ и повышение производительности программы моделирования сердечной активности.

Выводы.

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

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

Одним из наиболее актуальных направлений современного программирования является разработка параллельных алгоритмов и программ. Задача разработки таких программ и повышения их производительности достаточно сложна. Исследованию вопросов анализа производительности параллельных приложений в последние годы было посвящено множество публикаций. Среди них можно выделить работы J. Dongarra, Т. Sterling, М. Resch, W. Gropp, В. Mohr, F. Wolf, J. Vetter. В России направление анализа производительности параллельных приложений развивается в научных коллективах Вл.В. Воеводина, Л.Б. Соколинского, С. А. Немнюгина, В.П. Гер геля, В.А. Крюкова, A.B. Бухановского, Б.Н. Четверушкина, М.В. Якобовского, В.Э. Малышкина, С.М. Абрамова.

Для практического решения задачи повышения производительности разрабатываются специальные системы, позволяющие оценивать производительность параллельных приложений и выявлять наиболее «тяжелые» участки кода (проблемы производительности). На основе этих данных эксперт может принять решение по оптимизации программного кода с целью сокращения потерь на этих участках. Общий недостаток таких систем состоит в том, что задача выявления проблем производительности остается достаточно сложной ввиду большого объема обрабатываемой информации и сложности связей, порождающих отдельные проблемы. Кроме того, выявленные экспертом проблемы производительности и принятые решения по их устранению в таких системах не сохраняются тогда, как большая часть проблем имеют, как правило, достаточно типовой характер и могут проявляться в других параллельных приложениях. В этих условиях актуальной является задача разработки системы, способной накапливать знания экспертов по выявлению типовых проблем производительности параллельных приложений и способам их устранения.

Библиотека MPI (Message Passing Interface) является де-факто стандартом для разработки параллельных приложений. К настоящему времени создано достаточно большое количество MPI приложений, и выбор этого типа приложений в качестве основного объекта исследований является актуальным.

Целью диссертационной работы является разработка программной системы, обеспечивающей накопление знаний о типовых проблемах производительности MPI приложений, методах их выявления и способах их возможного разрешения.

В соответствии с целью диссертационной работы поставлены следующие задачи:

1. Предложить модели и методы представления знаний для анализа типовых проблем производительности MPI приложений.

2. Разработать алгоритмы выполнения анализа проблем производительности для предложенных моделей и методов представления знаний.

3. Разработать программную систему, реализующую предложенные модели, методы и алгоритмы.

4. Описать с помощью разработанных моделей, методов и средств ряд типовых проблем производительности MPI приложений.

5. Исследовать эффективность разработанных моделей, методов и средств для анализа производительности MPI приложений.

Методы исследования. Работа базируется на методах систем, основанных на знаниях, математической логики, объектно-ориентированного программирования.

Научная новизна работы состоит в следующем:

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

2. Предложены средства идентификации проблем производительности MPI приложений. Предложенные средства включают модели и языки описания:

• правил трассировки действий идентифицируемой проблемы производительности;

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

• правил выявления проблем производительности из множества сконструированных составных событий.

3. Разработаны алгоритм генерации трассировщика MPI приложения по заданным правилам трассировки действий отдельных проблем производительности и алгоритм конвертирования правил конструирования составных событий и правил выявления проблем производительности в правила ЭС CLIPS.

Практическую ценность работы составляют:

1. Программная система Performance Expert, реализующая предложенные модели, методы и алгоритмы.

2. База знаний для идентификации десяти типовых проблем производительности MPI приложений, описанная с использованием предложенных моделей и методов.

3. Результаты исследования эффективности разработанных моделей, методов и средств при анализе производительности MPI приложений.

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

Результаты диссертационной работы внедрены в ЦНИИ «Буревестник», в проведение научных исследований ННГУ и в учебный процесс ННГУ, что подтверждается актами о внедрении.

Основные результаты диссертации докладывались и обсуждались на следующих конференциях: международных конференциях

Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2010-2011), международной конференции «Научный сервис в сети Интернет: экзафлопсное будущее» (Дюрсо, 2011), международной конференции «Параллельные вычислительные технологии» (Москва, 2011), международной конференции «Супервычисления и математическое моделирование» (Саров, 2010), международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 2011), всероссийской конференции «Искусственный интеллект: философия, методология, инновации» (Москва, 2011), всероссийских конференциях «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2009-2010), семинарах кафедры МО ЭВМ факультета ВМК ННГУ.

На конкурсах научных работ аспирантов V всероссийской конференции "Искусственный интеллект: философия, методология, инновации" (Москва, 2011) и всероссийской конференции "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, 2009) доклады автора были отмечены дипломами.

По теме диссертации опубликовано 11 печатных работ [6, 7, 8, 9, 10, 11, 12, 16, 17, 18, 19], из них две статьи [12, 18] в ведущих рецензируемых журналах из списка ВАК.

Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем работы составляет 156 страниц, включая 40 рисунков и 12 таблиц. Список литературы включает 98 наименований.

6. Результаты исследования эффективности разработанных моделей, методов и средств при анализе производительности MPI приложений.

ЗАКЛЮЧЕНИЕ

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

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

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

2. Модели и методы идентификации проблем производительности MPI приложений: a. Модели и язык описания правил трассировки действий проблемы производительности. b. Модели и язык описания правил анализа трассы с целью конструирования составных событий как претендентов на отдельные типы проблем производительности. c. Модели и язык описания правил выявления проблем производительности из множества сконструированных составных событий.

3. Алгоритмы идентификации проблем производительности для предложенных моделей и методов представления знаний: а. Алгоритм генерации трассировщика MPI приложения по заданным правилам трассировки действий отдельных проблем производительности; b. Алгоритм конвертирования правил конструирования составных событий и правил выявления проблем производительности в правила ЭС CLIPS;

4. Программная система Performance Expert, реализующая предложенные модели, методы и алгоритмы.

5. База знаний для идентификации десяти типовых проблем производительности MPI приложений, описанная с использованием предложенных моделей и методов.

1. Андреев, H. Е. Исследование и реализация эффективных методов анализа производительности параллельных программ: автореф. дис. . канд. техн. наук: 05.13.Ц / Андреев Никита Евгеньевич; Место защиты: Том. гос. ун-т. -Томск, 2011,- 18 с.

2. Вагин, В. Н. Дедукция и обобщение в системах принятия решений / В. Н. Вагин. М.: Наука, 1988. - 383 е.: ил. - (Пробл. искусств, интеллекта; Вып. 11).

3. Воеводин, В. В. Параллельные вычисления: учеб. пособие для студентов вузов, обучающихся по направлению 510200 «Прикладная математика и информатика» / В. В. Воеводин, Вл. В. Воеводин. Науч. изд. - СПб.: БХВ-Петербург, 2002. - 599 е.: ил., табл.

4. Гергель, В. П. Теория и практика параллельных вычислений: учеб. пособие / В. П. Гергель. М.: Интернет-Университет, 2007. - 423 е.: ил., табл. -(Основы информационных технологий).

5. Дергунов, А. В. База знаний повышения производительности MPI-приложений / А. В. Дергунов // Интеллектуальные системы и компьютерные науки: материалы X Междунар. конф. М.: Изд-во МГУ, 2011. - С. 43-46.

6. Дергунов, А. В. Обзор исследований в области автоматизации диагностики производительности MPI-приложений / А. В. Дергунов, С. Н. Карпенко // Вестник Нижегор. ун-та им. Н. И. Лобачевского. Сер., Информационные технологии. 2011. - № 3(2). - С. 212-218.

7. Дергунов, А. В. Разработка экспертных систем в CTIPS: практикум / А. В. Дергунов. Н. Новгород: Изд-во Нижегор. гос. ун-та, 2010. - 30 с.

8. Джарратано, Дж. Экспертные системы: принципы разработки и программирование / Дж. Джарратано, Г. Райли; пер. с англ. К. А. Птицына. -4-е изд. М.: Вильяме, 2007. - 1152 с.

9. Джексон, П. Введение в экспертные системы / П. Джексон ; пер. с англ. В. Т. Тертышного. М.: Вильяме, 2001. - 624 с.

10. Карпенко, С. Н. Программные средства повышения производительности MPI-приложений / С. Н. Карпенко, А. В. Дергунов // Супервычисления и математическое моделирование: тр. XII междунар. семинара. Саров: РФЯЦ-ВНИИЭФ, 2011. - С. 195-202.

11. Клини, С. Математическая логика / С. Клини; пер. с англ. Ю. А. Гостева; под ред. Г. Е. Минца. М.: Мир, 1973. - 480 с.

12. Люгер, Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем / Д. Ф. Люгер; пер. с англ. Н. И. Галагана, К. Д. Протасовой. 4-е изд. - М.: Вильяме, 2003. - 864 с.

13. Минский, М. Структура для представления знания / М. Минский // Психология машинного зрения: пер. с англ. / Хорн Б. и др.; пер. с англ. под ред. В. Л. Стефанюк. М., 1978. - С. 249-338.

14. Моделирование сердечной активности / Г. В. Осипов и др. // Суперкомпьютерные технологии в науке, образовании и промышленности. -М.: Изд-во Моск. ун-та, 2010. С. 35-40.

15. Немнюгин, С. А. Параллельное программирование для многопроцессорных вычислительных систем / Сергей Немнюгин, Ольга Стесик. СПб.: БХВ-Петербург, 2002. - 396 е.: ил., табл. - (Мастер программ).

16. Рассел, С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг; пер. с англ. К. А. Птицына. 2-е изд. - М.: Вильяме, 2007. - 1408 с.

17. Смолин, Д. В. Введение в искусственный интеллект: конспект лекций / Д. В. Смолин. М.: Физматлит, 2004. - 208 с.

18. Топорков, В. В. Модели распределенных вычислений / В. В. Топорков. М.: Физматлит, 2004. - 315, 4. е.: ил., табл.

19. Фридл, Дж. Регулярные выражения / Дж. Фридл; пер. с англ. Е. Матвеев. -СПб.: Питер, 2001. 352 с. - (Библитека программиста).

20. Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования / Г. Р. Эндрюс; пер. с англ. А. С. Подосельника, Г. И. Сингаевской, А. Б. Ставровского. М.: Вильяме, 2003. - 512 с.

21. An Expert Assistant for Computer Aided Parallelization / G. Jost et al. // Proceedings of PARA. 2004. - P. 665-674.

22. Automatic parallel I/O performance optimization in Panda / Y. Chen et al. // Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures. New York, 1998. - P. 108-118.

23. Barney, B. MPI Performance Topics Электронный ресурс. / В. Barney. URL: https://computing.llnl.gov/tutorials/mpiperformance/ (дата обращения: 28.08.2011).

24. Benoit, D. G. Automatic Diagnosis of Performance Problems in Database Management Systems / D. G. Benoit // Proceedings of the Second International Conference on Autonomic Computing, Seattle, WA, USA. P. 326-327.

25. Bhatia, N. Automatic Experimental Analysis of Communication Patterns in Virtual Topologies / N. Bhatia, F. Song, F. Wolf // Proceedings of the International Conference on Parallel Processing, 2005. P. 465-472.

26. Browne P. JBoss Drools Business Rules / P. Browne. Packt Publishing, 2009. -304 p.

27. Davis, R. What Is a Knowledge Representation? / R. Davis, H. Shrobe, P. Szolovits // Al Magazine. 1993. - Vol. 14, № 1. - P. 17-33.

28. Delgrande, J. P. Knowledge representation: features of knowledge / J. P. Delgrande, J. Mylopoulos // Fundamentals of artificial intelligence. 1986. - Vol. 232.-P. 2-36.

29. Dvorak, J. J. Using Clips in the domain of knowledge-based massively parallel programming / J. J. Dvorak // Third CLIPS Conference Proceedings. Houston, Texas, 1994.-P. 195-202.

30. Efficient Pattern Search in Large Traces through Successive Refinement / F. Wolf et al. // Proceedings of the European Conference on Parallel Computing, 2004. -P. 47-54.

31. Espinosa, A. Automatic Detection of Parallel Program Performance Problems / A. Espinosa, T. Margalef, E. Luque // Vector and Parallel Processing. 1999. - Vol. 1573.-P. 365-377.

32. Espinosa, A. Automatic detection of PVM program performance problems / A. Espinosa, T. Margalef, E. Luque // Recent Advances in Parallel Virtual Machine and Message Passing Interface. 1998. - Vol. 1497. - P. 19-26.

33. Espinosa, A. Automatic Performance Analysis of Master/Worker PVM Applications with Kpi / A. Espinosa, T. Margalef, E. Luque // Recent Advances in Parallel Virtual Machine and Message Passing Interface. 2000. - Vol. 1908. - P. 47-55.

34. Fahringer, T. Aksum: a performance analysis tool for parallel and distributed applications / T. Fahringer, C. Seragiotto // Performance analysis and grid computing. 2004. - №. 2. - P. 189-208.

35. Fahringer, T. Modeling and Detecting Performance Problems for Distributed and Parallel Programs with JavaPSL / T. Fahringer, C. Seragiotto // Proceedings of the 2001 ACM/IEEE conference on Supercomputing, 2001. P. 38-54.

36. Forgy, C. L. Rete: A Fast Algorithm for the Many Pattern: Many Object Pattern Match Problem / C. L. Forgy // Artificial Intelligence. 1982. - Vol. 19. - P. 1737.

37. Foster, I. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering /1. Foster. Boston: Addison-Wesley, 1995. - 430 P

38. Friedman-Hill, E. Jess in Action. Rule-Based System in Java / E. Friedman-Hill. -Manning Publications, 2003. 480 p.

39. Goettge, R. T. PEDAS: An Expert System for Performance Engineering of Time-Critical Software / R. T. Goettge // Proceedings of the 16th International Computer Management Group Conference. Orlando, 1990. - P. 313-320.

40. Grama, A. Introduction to Parallel Computing / A. Grama, A. Gupta, G. Karypis et al. 2nd edition. - Boston: Addison-Wesley, 2003. - 656 p.

41. Gropp, W. Revealing the Performance of MPIRMA Implementations / W. Gropp, R. Thakur // Proceedings of the 14th European PVM/MPI Users'Group Meeting. -Paris, 2007. P. 272-280.

42. Hermanns, M. Event-Based Measurement and Analysis of One-Sided Communication / M. Hermanns, B. Mohr, F. Wolf // Proceedings of the European Conference on Parallel Computing, 2005. P. 156-166.

43. Hermanns, M. Verifying Causal Connections between Distant Performance Phenomena in Large-Scale Message-Passing Applications / M. Hermanns //

44. Proceedings of the 2009 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing, 2009. P. 78-84.

45. Hoogenboom, P. J. System Performance Advisor: An Expert System for Unix System Performance Management: Master's Thesis / P. J. Hoogenboom. Salt Lake City, 1992.- 144 p.

46. Intel Trace Analyzer: Reference Guide Электронный ресурс. URL: http://software.intel.com/en-us/articles/intel-trace-analyzer-and-collector-documentation (дата обращения: 01.09.2011).

47. Intel Trace Collector: Reference Guide Электронный ресурс. URL: http://software.intel.com/en-us/articles/intel-trace-analyzer-and-collector-documentation (дата обращения: 01.09.2011).

48. Jain, R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling / R. Jain. New York: Wiley-Interscience, 1991. - 685 p.

49. Kim, S. W. A performance advisor tool for novice programmers in parallel programming / S. W. Kim, I. Park, R. Eigenmann // Proceedings of the 13th annual Workshop on Languages and Compilers for Parallel Computing, 2000. P. 274-288.

50. Knowledge Specification for Automatic Performance Analysis / T. Fahringer et al. // Technical Report, FZJ-ZAM-IB-2001-08, Germany, 2001. 83 p.

51. Lakemeyer, G. Foundations of Knowledge Representation and Reasoning / G. Lakemeyer, B. Nebel // Foundations of Knowledge Representation and Reasoning.- 1994.-Vol. 810.-P. 1-12.

52. Li, K. A knowledge-based performance tuning tool for parallel programs / K. Li, K. Zhang // Second International Conference on Algorithms and Architectures for Parallel Processing, 1996. P. 287-294.

53. Li, L. Automatic Performance Diagnosis of Parallel Computations with Compositional Models / L. Li, A. D. Malony // Proceedings of the IEEE International Parallel and Distributed Processing Symposium, Long Beach, CA, USA, 2007.-P. 1-8.

54. LÍ, L. Knowledge engineering for automatic parallel performance diagnosis / L. Li, A. D. Malony // Concurrency and Computation: Practice and Experience. -2007.-Vol. 19, № 11. P. 1497-1515.

55. Li, L. Model-Based Performance Diagnosis of Master-Worker Parallel Computations / L. Li, A. D. Malony // Proceedings of Parallel Processing Conference, 2006. P. 35-46.

56. Li, L. Model-Based Relative Performance Diagnosis of Wavefront Parallel Computations / L. Li, A. D. Malony, K. Huck // Proceedings of High Performance Computing and Communications, 2006. P. 200-209.

57. Lilja, D. J. Measuring computer performance: A Practitioner's Guide / D. J. Lilja.- Cambridge: Cambridge University Press, 2000. 278 p.

58. Liu, P. Applying Expert System Technology to Enhance Sort Performance / P. Liu // Proceedings of the 20th International Computer Management Group Conference. Orlando, 1994 - P. 85-91.

59. Moore, S. Improving Time to Solution with Automated Performance Analysis / S. Moore, F. Wolf, J. Dongarra // Proceedings of the Second Workshop on Productivity and Performance in High-End Computing. San Francisco, 2005. -P. 20-26.

60. MPI: A Message-Passing Interface Standard Электронный ресурс. URL: http://www.mpi-forum.org/docs/mpi-l 1-html/mpi-report.html (дата обращения: 28.08.2011).

61. MPI-2: Extensions to the Message-Passing Interface Электронный ресурс. -URL: http://www.parallel.ru/docs/mpi2/mpi2-report.html (дата обращения: 28.08.2011).

62. Mylopoulos, J. An overview of knowledge representation / J. Mylopoulos // Proceedings of the 1980 workshop on Data abstraction, databases and conceptual modeling, 1980.-P. 5-12.

63. Nethercote, N. Dynamic Binary Analysis and Instrumentation: PhD thesis / N. Nethercote. Cambridge, 2004. - 190 p.81 .Northover, S. SWT: The Standard Widget Toolkit, Volume 1 / S. Northover, M. Wilson. Boston: Addison-Wesley, 2004. - 592 p.

64. Parr, T. The Definitive ANTLR Reference: Building Domain-Specific Languages / T. Parr. Pragmatic Bookshelf, 2007 - 376 p.

65. Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation / C.-K. Luk et al. // Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, Chicago, IL, 2005. P. 190200.

66. Preece, A. D. Foundation and application of knowledge base verification / A. D. Preece, R. Shinghal // International Journal of Intelligent Systems. 1994. - Vol. 9, №8. -P. 683-701.

67. PYTHIA-II: a knowledge/database system for managing performance data and recommending scientific software / E. N. Houstis et al. // ACM Transactions on Mathematical Software. 2000. - Vol. 26, № 2. - P. 227-253.

68. Rabenseifner, R. Opitmization of MPI Applications Электронный ресурс. / R-Rabenseifiier. URL: httpsy/fe.hte.de^jects/par/pa^ (дата обращения: 28.082011).

69. Relating the Execution Behavior with the Structure of the Application / A. Espinosa et al. // Recent Advances in Parallel Virtual Machine and Message Passing Interface. 1999. - Vol. 1697. - P. 91-98.

70. Samadi, B. TUNEX: A Knowledge-Based System for Performance Tuning of the UNIX Operating System / B. Samadi // IEEE Transactions on Software Engineering. 1989. - Vol. 15, № 7. - P. 861-874.

71. Seragiotto, C. Performance Analysis for Distributed and Parallel Java Programs with Aksum / C. Seragiotto, T. Fahringer // Proceedings of the IEEE International Symposium on Cluster Computing and the Grid, 2005. P. 1024-1031.

72. Toward Scalable Performance Visualization with Jumpshot / O. Zaki et al. // High-Performance Computing Applications. 1999. - Vol. 13, № 2. - P. 277-288.

73. UPC: Distributed Shared Memory Programming / T. El-Ghazawi et al.. -Willey-Interscience, 2003. 300 p.

74. Velez, R. An intelligent tool for UNIX performance tuning / R. Velez, D. Zhang, J. Kho // Fifth International Conference on Tools with Artificial Intelligence. -Boston, 1993.-P. 118-122.

75. Wolf, F. Automatic performance analysis of hybrid MPI/OpenMP applications / F. Wolf, B. Möhr // Journal of Systems Architecture: the EUROMICRO Journal. -2003. Vol. 49, № 10/11. - P. 421-439.

76. Wolf, F. EARL A Programmable and Extensible Toolkit for Analyzing Event Traces of Message Passing Programs / F. Wolf, B. Möhr // Proceedings of the 7th International Conference on High-Performance Computing and Networking. - P. 503-512.

77. Xu, J. Rule-based automatic software performance diagnosis and improvement / J. Xu // Performance Evaluation. 2008. - Vol. 67, № 8 - P. 585-611.