Третья контрольная работа (1127791), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(декомпозиция: алгоритмы + модули, объекты + интерфейс);

• Реализация: кодирование (непосредственное написание кода по описанной в спецификации функциональности и интерфейсам) + тестирование (запуск программы на некоторых входных данных с целью обнаружить дефект – несоответствие ожидаемого результата и выданного программой) + отладка (обнаружение причины дефекта и её исправление) ;

• Внедрение (перенос продукта на целевую систему с инструментальной) ;

• Сопровождение: эволюция программного продукта при его эксплуатации.

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

1) Балансировка дерева вычислений. Балансировка дерева вычислений (tree-height reduction or balancing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по умолчанию последовательность вычислений с накоплением одной частной суммы и может повлиять на результат.

2) Исключение общих подвыражений. Алгоритмы исключения общих подвыражений (common subexpession elimination) также могут изменить порядок вычислений. Если компилятор распознает в выражениях повторяющееся вычисление, то это вычисление производятся один раз, его результат сохраняется на регистре, и в дальнейшем используется этот регистр. Тем самым исключается избыточность вычислений.

3) Разворачивание циклов. Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения. Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору).

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

Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.

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

• иметь абсолютное значение, больше M (максимального числа) - машинное переполнение;

• иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине - машинный нуль;

• иметь значение в диапазоне [m:M] и тем не не менее не принадлежать множеству F (произведение двух чисел из F, как правило, записывается посредством 2t либо 2t-1 значащих цифр);

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

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

сложении или вычитании чисел с плавающей точкой операнды должны быть предварительно приведены к одному порядку, что осуществляется сдвигом вправо мантиссы числа,

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

4) Возможность сопровождения параллельной и последовательной версии программы по единому тексту.

Спецкомментарии – средство параллельного программирования (в алгоритмических языках)

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

Примерами продуктов, работающих с программами на основе спецкомментариев, но не меняющих их поведение, являются системы автоматического документирования Doxygen, Javadoc, PHPdoc.

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

Подобные спецкомментарии созданы для учёта особенностей вычислительной системы, на которой будет работать программный продукт (они могут учитывать работу кеш-памяти, архитектуру системы – NUMA, ccNUMA …, решение проблемы миграции процессов(нитей/тредов) между ядрами, даже вероятность определённого перехода в условном операторе)

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

Так например для систем MPP, чтобы программировать методом передачи сообщений были созданы специальные языки Фортран GNS, и Си GNS. Эти языки были получены из стандартных добавлением средств описания и идентификации параллельных процессов.

Самыми распространёнными языками, основанными на спецкомментариях считаются Фортран HPF (High performance Fortran), Фортран DVM и система OpenMP (open multiprocessing).

Хотя существует очень много различных параллельных расширений и диалектов как для языка Фортран, так и для языка Си, например:

1. Фортран: Fortran-DVM, Cray MPP Fortran, F--, Fortran90/95, FortranD95, FortranM, Fx, HPF, Opus, ViennaFortran

2. Си: C-DVM, A++/P++, CC++, Charm/Charm++, Cilk, HPC, HPC++,C/OpenMP, Maisie, Mentat, mpC, MPC++, Parsec, pC++, sC++, uC++

Все системы основанные на спецкомментариях работают примерно одинаково, т.е. по одной схеме. Рассмотрим подробно систему OpenMP (в основном применительно к языку СИ):

OpenMP (Open Multi-Processing) это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с единой памятью на языках C, C++ и Fortran.

Межпроцессное взаимодействие в большинстве случаев реализовано с помощью MPI – Message Passing Interface.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB). (В основном система OpenMP – это систем спецкомментариев системы SPP1000)

OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (соотношение количества процессоров и количества потоков потоков не регламентируется).

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка — pragma. Например, участок кода на языке Си, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой:

#pragma omp parallel private(x)

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

Ключевыми элементами OpenMP являются

• конструкции для создания потоков (директива parallel),

• конструкции распределения работы между потоками (директивы for и section),

• конструкции для управления работой с данными (выражения shared и private),

• конструкции для синхронизации потоков (директивы critical, atomic и barrier),

• процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),

• переменные окружения (например, OMP_NUM_THREADS).

Существует возможность скомпилировать код с игнорированием директив OpenMP, и тогда код будет выполняться последовательно.

Другая система: DVM - ориентирована на параллелизм данных. В этой модели данные распределяются по вычислительным узлам, а программа преобразуется в параллельную программу, с использованием модели передачи сообщений, либо с общей памятью. Это освобождает программиста от распределения данных между различными вычислительными узлами. Хотя безусловно эта система применима не для всех решаемых задач, а преимущественно для тех, в которых параллельно над различными данными нужно производить вычисления. Фортран HPF – как раз является одним из первых примеров подобного языка программирования, где было сделано всё для полной автоматизации задачи распараллеливания, однако на некоторых задачах он выдавал плохие показатели и в результате появился Фортран DVM – который давал некоторую настраиваемость, т.е. гибкость, и потому был более успешен для большего числа задач.

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

В этой программе на языке С два вектора (a и b) складываются параллельно десятью потоками.

#include <stdio.h>

#include <omp.h>

#define N 100

int main(int argc, char *argv[])

{

float a[N], b[N], c[N];

int i;

omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения

omp_set_num_threads(10); // установить число потоков в 10

// инициализируем векторы

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

{

a[i] = i * 1.0;

b[i] = i * 2.0;

}

// вычисляем сумму векторов

#pragma omp parallel shared(a, b, c) private(i)

{

#pragma omp for

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

c[i] = a[i] + b[i];

}

printf ("%f\n", c[10]);

return 0;

}

Характеристики

Список файлов ответов (шпаргалок)