Сравнение возможностей OpenMP и TPL

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

Основным языком программирования в данной работе мы выберем C# т.к. в настоящее время этот язык один из самых продвинутых и современных языков программирования. К тому же этот язык позволяет использовать возможности библиотеки TPL.

Важные факторы языка C#:

· C# создавался и развивается параллельно с каркасом Framework .Net и в полной мере учитывает все его возможности;

· C# является полностью объектно-ориентированным языком;

· C# является мощным объектным языком с возможностями наследования и универсализации;

· C# является наследником языка C++. Общий синтаксис, общие операторы языка облегчают переход от языка С++ к C#;

· Сохранив основные черты своего родителя, язык стал проще и надежнее;

· Благодаря каркасу Framework .Net, ставшему надстройкой над операционной системой, программисты C# получают преимущества работы с виртуальной машиной;

· Framework .Net поддерживает разнообразие типов приложений на C#;

· Реализация, сочетающая построение надежного и эффективного кода.

Вторым языком программирования мы выбрали C++/CLI т. к. он позволяет использовать возможности OpenMP и платформы .Net.

C++/CLI - привязка языка C++ к среде программирования .NET фирмы Microsoft. Она интегрирует C++ стандарта ISO с Объединенной системой типов (Unified Type System - UTS), рассматриваемой как часть общей языковой Инфраструктуры (Common Language Infrastructure - CLI). В ней предусмотрена поддержка исходных программ и функциональная совместимость исполнимых файлов, скомпилированных с родного и управляемого C++.

Язык C++/CLI -- некоторое надмножество языка C++: если из языка удалить всю поддержку CLI, то останется C++. Это означает, что автоматически почти любая программа на C++ является программой на C++/CLI, просто как программа, которая не обращается ни к одной дополнительной функциональной возможности, предоставляемой CLI.

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

На практике существуют несколько технологических подходов к программированию для параллельных вычислительных систем:

· Программирование на стандартных и широко распространённых языках программирования с использованием высокоуровневых коммуникационных библиотек(В нашей работы мы будем использовать библиотеки OpenMP и средства разработки Visual Studio, а в частности библиотеки TPL) и интерфейсов для организации межпроцессного взаимодействия;

· Введение специальных "распараллеливающих" конструкций в язык программирования. При этом могут создаваться оригинальные параллельные языки(C/C++/C#) или параллельные расширения существующих языков;

· Использование средств автоматического распараллеливания последовательных программ;

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

· Использование инструментальных систем, облегчающих создание и проектирование параллельных программ;

· Использование специализированных прикладных пакетов;

Для решения одной и той же задачи на различных вычислительных архитектурах могут быть эффективны различные алгоритмы. Рассмотрим, например, задачу перемножения матриц размерности порядка 100-1000. Для процессора, у которого время выполнения умножения чисел дольше времени обращения к памяти (70-ые годы) эффективен алгоритм Штрассена. Для нынешних процессоров стандартный алгоритм перемножения матриц значительно эффективней.

Таким образом, возникает проблема для одной и той же задачи разрабатывать различные алгоритмы для различных вычислительных архитектур: MIMD, SIMD, Reconfigurable pipeline…; и с различными способами организации памяти: общая, распределенная, многоуровневая…; с различными коммуникационными системами: кольцо, решетка, гиперкуб, дерево и т.д..

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

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

· все ресурсы отдаются для выполнения одной программы, и тогда мы вправе ожидать n-кратного ускорения работы программы по сравнению с однопроцессорной системой;

· одновременно выполняется n обычных однопроцессорных программ, при этом пользователь вправе рассчитывать, что на скорость выполнения его программы не будут оказывать влияния другие программы.

2.3 Математические методы и специальные алгоритмы решения задачи. Оценка сложности алгоритма решения задачи

В данной дипломной работе мы рассмотрим основные задачи линейной алгебры:

· Умножение матриц;

· Возведение в степень;

· Решение систем линейных уравнений;

· Решение систем с n правыми частями;

· Детерминант матриц;

· Работа со слабо заполненными матрицами.

2.3.1 Решение систем линейных уравнений

Метод Гаусса довольно прост и широко применим для решения систем линейных уравнений. Рассмотрим систему уравнений:

Суть работы алгоритма очень проста. Она заключается в последовательности удаления элементов. Умножаем элементы первой строки на элемент A21, а элементы второй строки на элемент A11. Вычитая из первой строки вторую, получим следующее уравнение 0x1+(A21*A12-A11*A22)x2 +(A21*A13-A11*A23)x3+...+(A21*A1n-A11*A2n)xn=A21*b1-A11*b2 второй строки. Обнулив переменную x1 во второй строке, аналогично делаем в третьей 0x1+(A31*A12-A11*A32)x2+(A31*A13-A11*A33)x3+...+(A31*A1n-A11*A3n)xn=A31*b1-A11*b3. Для n-ой строки 0x1+(An1*A12-A11*An2)x2+(An1*A13-A11*An3)x3+...+(An1*A1n-A11*Ann)xn=An1*b1-A11*bn. Заменим выражение (A21*A12-A11*A22) на A22^(1),(A21*A13-A11*A23) на A23^(1),(A21*A1n-A11*A2n) на A2n^(1), (A21*b1-A11*b2) на b2^(1) и т.д.

После преобразования системы переменная x1 осталась только в первом уравнении. На втором шаге проделываем аналогичные операции. Умножаем элементы второй строки на элемент A32^1, а элементы третьей строки на элемент A22^1. Вычитая из второй строки третью, получим следующее уравнение 0x2+(A32^1*A23^1-A22^1*A33^1)x3+(A32^1*A24^1-A22^1*A34^1)x3+...+(A32^1*A2n^1-A22^1*A3n^1)x3=A32^1*b2^1- A22^1*b3^1 третьей строки. Удалив переменную x2 из всех уравнений кроме второго, мы получим следующую систему уравнений.

Продолжаем данный процесс (n-1) раз. В результате получим треугольную матрицу. Данное преобразование называется «прямой ход».

Решение систем уравнений методом Гаусса «прямой ход»:

int gaus(int cnt_str,double **mass,double *&x)

{

int i,j,k;

x=new double [cnt_str];//выделение памяти для неизвестных

//прямой ход

for(i=0;i<cnt_str;i++)

{

double a=mass[i][i];

for(j=i+1;j<cnt_str;j++)

{

double b=mass[j][i];

for(k=i;k<cnt_str+1;k++)

mass[j][k]=mass[i][k]*b-mass[j][k]*a;

}

}

Do 0 to count

A=mass[i][j]

Do I + 1 to count

B=mass[i][j]

Do I to count

Mass[j][k]=mass[i][k]*b-mass[j][k]*a

Enddo

enddo

enddo

Сложность данного алгоритма по определению составляет O(n^3). Рассчитаем параметры ускорения и эффективности. Для данного случая ускорение Sp = (n^3)/p эффективность Ep= 1.

Используя треугольную систему уравнений, легко получаем значения неизвестных x, начиная с последнего уравнения. Данный процесс называется «обратный ход» решения систем уравнений методом Гаусса.

Решение систем уравнений методом Гаусса «обратный ход»:

//обратный ход

Do i=cnt_str-1;i>=0;i--

{

double summ=0.;

do j=i+1;j<cnt_str;j++

summ+=mass[i][j]*x[j];

summ=mass[i][cnt_str]-summ;

if(mass[i][i]==0)

x[i]=summ/mass[i][i];

enddo

}

Enddo

Сложность данного алгоритма составляет Olog(n). Рассчитаем параметры ускорения и эффективности. Для данного случая ускорение Sp =log(n)/p, где p это количество процессов. Эффективность Ep= 1.

2.3.2 Вычисление детерминанта

Используя метод Гаусса «прямой ход», приведём матрицу к треугольному виду. Перемножая элементы главной диагонали, получим определитель матрицы.

Вычисление определителя матрицы методом Гаусса:

Do i=0;i<cnt_str;i++

{

Do j=i+1;j<cnt_str;j++

{

If (mass[i][i]==0)

double b=mass[j][i]/mass[i][i];

do k=i;k<cnt_str;k++

mass[j][k]=mass[j][k]-mass[i][k]*b;

}

det*=mass[i][i]; //вычисление определителя

}

Enddo

Enddo

enddo

Сложность данного алгоритма составляет Olog(n). Рассчитаем параметры ускорения и эффективности. Для данного случая ускорение Sp = log(n)/p. Эффективность Ep= 1.

2.3.3 Возведение матрицы в степень

Возведение в степень -- это приём, позволяющий возводить любое число в n-ую степень за O(log n) умножений или вместо n умножений при обычном подходе.

Так же описываемый здесь приём применим к любой операции, не только к умножению чисел, но и к матрицам тоже. Ассоциативной операцией для любых a,b,c называется, если выполняется:

Алгоритм. Для любого числа a и чётного числа n выполнимо очевидное тождество которое следует из ассоциативности операции умножения:

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

Если степень n нечётна, то мы переходим к степени n - 1, которая будет уже чётной:

Дальше мы находим рекуррентную формулу: от степени n мы переходим, если она чётна то n/2, иначе n - 1. Всего будет не более 2*log(n) переходов, прежде чем мы придём к n = 0 на базе рекуррентной формулы. Таким образом, мы получилим алгоритм, работающий за Olog(n) умножений.

Реализация

Простейший алгоритм рекурсивной реализации:

binpow (matrix a, matrix n)

if (n % 2 == 1)

return binpow (a, n-1) * a;

else {

b = binpow (a, n/2);

Эту реализацию можно ещё несколько упростить, заметив, что возведение a в квадрат осуществляется всегда, независимо от того, сработало условие нечётности n или нет:

int binpow (int a, int n) {

int res = 1;

while (n) {

if (n & 1)

res *= a;

a *= a;

n >>= 1;

Сложность данного алгоритма составляет Olog(n). Рассчитаем параметры ускорения и эффективности. Для данного случая ускорение Sp = log(n)/p, где p это количество процессов. эффективность Ep= 1.

вычислительный алгоритм линейный алгебра

Заключение

В ходе практики были подробно изучены инструментарии OpenMP и .Net TPL. Так же был проведен их сравнительный анализ на примерах задач линейной алгебры.

Размещено на Allbest.ru