Средства автоматизации распараллеливания программ (курсовая), страница 2

Было бы правильно заменить ее программой, в основекоторой стандартный алгоритм перемножения матриц, который затем с успехомраспараллелить. Проблема в том, чтобы по тексту программы компилятор могпонять, что эта программа перемножает матрицы.6Средства автоматическогораспараллеливанияНесмотря на препятствия, стоящие на пути исследователей проблемавтоматического распараллеливания программ, активно ведутся работы в этомнаправлении как зарубежными учеными, так и отечественными.

Средисуществующих средств автоматического и полуавтоматического распараллеливанияпрограмм наиболее известны следующие комплексы.BERT–77BERT 77 (или BERT) – программный инструмент, автоматически конвертирующийпоследовательные FORTRAN программы в параллельные для вычислительныхсистем с распределенной памятью. BERT производит программный код,совместимый со стандартной моделью передачи сообщений, и поддерживает PVM иMPI.

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

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

BERT-планировщиктребует, чтобы любая распараллеливаемая часть выполнялась эффективно. Вслучае, если какой-либо последовательный фрагмент не удается преобразовать кпараллельной форме, выполняющейся эффективно, BERT-планировщикпреобразования по умолчанию не производит.7Большинство средствраспараллеливанияпрограммПоследовательнаяFORTRAN-77программаBERT-77Определение участков,допускающих распараллеливаниеОпределение участков,допускающих распараллеливаниеАнализ эффективностираспараллеливанияучастка (планировщик)Генерация кода впараллельной формеГенерация кода впараллельной формеПараллельная FORTRAN-77программа (эффективностьраспараллеливанияне гарантируется)Параллельная FORTRAN-77программа (эффективностьраспараллеливаниягарантируется)Рис.

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

BERT обеспечивает решение этойпроблемы посредством быстрого и эффективного метода анализа и преобразованияпоследовательных FORTRAN-77 программ к параллельному представлению.Ниже приведены особенности и преимущества BERT:••••распараллеливание циклов с процедурой вызовов – с помощью мощногомежпроцедурного анализа;анализ эффективности распараллеливания всех циклов;поддержка параллельных задач;предварительная оценка производительности.8Эффект, который можно ожидать после применения BERT в течение несколькихчасов:••••можно узнать, работает ли параллельная программа эффективно и что нужносделать для увеличения эффективности;можно определить, какие циклы можно распараллелить, а какие нельзя;можно выяснить, какой вклад вносит каждый цикл в общее время расчета;ликвидация проигрышных стратегий распараллеливания;Использование программы в течение нескольких дней, по заверению разработчиков,способно:•••дать твердое понимание «параллельного характера» программы;определить, возможно ли преобразование циклов с зависимостями кпараллельной форме;запустить эффективные преобразования программы в параллельную форму.К очевидным недостаткам BERT-77 можно отнести:••поддержка одного языка (FORTRAN-77) в то время как чаще используютC/C++;BERT – коммерческий продукт (компания Paralogic), бесплатно доступна Liteверсия.FORGExplorerFORGExplorer – графический браузер Fortran-программ.FORGExplorer SMP и FORGExplorer DMP – средства распараллеливания Fortranпрограмм для SMP и MPP-платформ, работающие на основе базы данныхFORGExplorer.

Является коммерческой разработкой компании Applied ParallelResearch. [7]Kuck Accelerator PackageKAP (Kuck Accelerator Package) – оптимизирующий препроцессор Fortran/C-программс обнаружением параллелизма. Коммерческий продукт, разработка компании Kuck &Associates.Visual KAP, Visual KAP for OpenMP - визуальные средства автоматическогораспараллеливания Fortran-программ. [8]ДВОРДВОР – это диалоговый оптимизирующий распараллеливатель программ,разработанный на мехмате Южного федерального университета.

Этараспараллеливающая система вобрала в себя опыт исследовательской Открытойраспараллеливающей системы [4] и предназначена для распараллеливания9программ с процедурных языков (C, Forttan). В основе ДВОР лежит высокоуровневоепредставление, позволяющее генерировать код на различные вычислительныеархитектуры.

Высокий уровень внутреннего представления также удобен длядиалоговых преобразований программ. Одновременно с с распараллеливателемразрабатываются «приложения»: библиотеки программ по финансовой математике,криптографии и ACELAN (по механике и пьезокерамике).ДВОР находится в открытом доступе, любой желающий может посетить сайт,загрузить файл с последовательной программой и получить сгенерированнуюпараллельную модификацию программы.В качестве эксперимента была загружена элементарная программа на C –перемножение двух матриц.#define N 1000int main(){int A[N][N], B[N][N], C[N][N];int i, j, k;for (i=0; i<N; i++)for (j=0; j<N; j++){A[i][j] = i+j;B[i][j] = i*j;C[i][j] = 0;}for (i=0; i<N; i++)for(j=0; j<N; j++)for (k=0; k<N; k++)C[i][j] += A[i][k] * B[k][j];}return 0;Системе было указано сгенерировать параллельную OpenMP-модификацию этойпрограммы.

Результат генерации:int main(){int A[1000][1000];int B[1000][1000];int C[1000][1000];int i;int j;int k;#pragma omp parallel forfor (i = 0; i < 1000; i = i + 1){#pragma omp parallel forfor (j = 0; j < 1000; j = j + 1){A[i][j] = i + j;B[i][j] = i * j;C[i][j] = 0;}10}}#pragma omp parallel forfor (i = 0; i < 1000; i = i + 1){#pragma omp parallel forfor (j = 0; j < 1000; j = j + 1){for (k = 0; k < 1000; k = k + 1){C[i][j] = C[i][j] + A[i][k] * B[k][j];}}}return 0;С распараллеливанием простой программы на OpenMP ДВОР справился (см.

табл. 1).Однако при встрече с более трудной последовательной программой система выдаеттрудночитаемый параллельный алгоритм большого объема (особенно, еслитребуется MPI-модификация).Таблица 1. Сравнения временных характеристик исходной и сгенерированной программРазмерностьматриц,участвующих вперемножении(матрицыквадратные)10002000300040005000Время решенияOpenMP –алгоритмом (2потока)Времяпоследовательногорешения20.886157.407575.5361320.9482641.89314.917109.979396.521872.0491744.83711Ускорение,получаемое прииспользованиитехнологииOpenMP1.401.431.451.511.51Отладка параллельных программДля отладки программ в состав современных библиотек обычно включаютспециальные отладочные вызовы.

Например, в состав LAM (реализация MPI) входитцелый набор дополнительных модулей-отладчиков. Так как подобные вызовы неопределяются стандартом MPI, то они работоспособны только с данной реализациейкоммуникационной библиотеки. Существуют и специальные отладчики, например,TotalView (разработка фирмы Pallas) – много платформенный графический отладчикдля программ, написанных на C, C++, Fortran (77 и 90), PGI HPF с простыминтерфейсом. Отладчик позволяет отлаживать сложные многопроцессные,многопоточные и распределенные программы, оптимизирован длявысокопроизводительных вычислений, позволяет управлять и контролироватьодин или много потоков или процессов (вместе или индивидуально), создавать ииспользовать скрипты, тестировать фрагменты кода и выполнять специальный коддо того, как будет изменен исходный код, управлять данными программы,просматривать структуры и объекты в программе.Интерес представляют так же интегрированные решения, которые представляютсобой пакет, в состав которого входят компиляторы для различных языков,отладчики, графические анализаторы и так далее.Например, компания Portland Group, Inc.

предлагает пакет PGI Workstation 1.7, вкоторый входят средства разработки прорамм для кластеров, набороптимизирующих/распараллеливающих компиляторов и средств для разработки иподдержки вычислительных приложений под рабочие станции, серверы и кластерына базе процессоров Intel.Система Grade (A Graphical Parallel Programming Environment) включает наборсредств разработки приложений для гетерогенных кластеров: графический языкпараллельного программирования GRAPNEL, графический редактор для построенияGRAPNEL-программ, препроцессор для генерации программ на PVM/C, средствогенерации трасс, распределенный отладчик, средство визуализации трасс.12Литература1. Штейнберг Б. Я.

Автоматизация разработки программ для параллельныхвычислительных систем с распределенной памятью2. Нис З. Я. «Обеспечение статической семантической корректности программпри проведении распараллеливающих и оптимизирующих преобразований».PACO’2008, Труды четвертой международной конференции «Параллельныевычисления и задачи управления», Москва.: 27-29 октября 2008 г.3. Воеводин В. В., Воеводин Вл. В. «Параллельные вычисления», С-Петербург«БХВ-Петербург», 2002, 599 с.4.

Открытая распараллеливающая система – [Электронный ресурс] –http://www.ops.rsu.ru5. Автоматический распараллеливатель ДВОР – [Электронный ресурс] –http://ops.opsgroup.ru/index.html6. Бахтин В.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В. «Автоматическоераспараллеливание последовательных программ для многоядерныхкластеров»7. Клинов М.С. «Автоматическое распараллеливание некоторого классафортран-программ. Отображение на кластер» - автореферат диссертации насоискание ученой степени к.

ф.-м. н.8. Белогурский А.И., Васин Л.А., Вашкевич Н.П., Князьков В.С., Шашков Б.Д.«Инструментальные средства разработки параллельных программ длякластерных вычислений», Пенза, Пензенский государственный университет13.