Параллельное програмирование
Федеральное агентство по образованию
Московский государственный открытый университет
Чебоксарский
институт
Кафедра
Информационных технологий и программирования
специальность 230105
Курсовой проект
по дисциплине Параллельное программирование
Вариант 35
Дата проверки Выполнил студент
Падукова А.Ю.
Результат проверки учебный шифр
608135, курс 4, з/о
Проверил Малов А.А.
2011г.
Содержание
Введение…………………………………………………………
Разбиение программы
на подзадачи…………..………………………………………
Доступ к объектам из других адресных
пространств………………………………………………9
Заключение……………………………………………………
Список использованной
литературы……………………………………………………
Введение
Два события называют одновременными, если они происходят в течение одного и того же временного интервала. Если несколько задач выполняются в течение одного и того же временного интервала, то говорят, что они выполняются параллельно. Для нас термин параллельно необязательно означает «точно в один момент». Например, две задачи могут выполняться параллельно в течение одной и той же секунды, но при этом каждая из них выполняется в различные доли этой секунды. Так, первая задача может отработать в первую десятую часть секунды и приостановиться, затем вторая может отработать в следующую десятую часть секунды и приостановиться, после чего первая задача может возобновить выполнение в течение третьей доли секунды, и т.д. Таким образом, эти задачи могут выполняться по очереди, но поскольку продолжительность секунды с точки зрения человека весьма коротка, то кажется, что они выполняются одновременно. Понятие одновременности (параллельности) можно распространить и на более длинные интервалы времени. Так, две программы, выполняющие некоторую задачу в течение одного и того же часа, постепенно приближаясь к своей конечной цели в течение этого часа, могут (или могут не) работать точно в одни и те же моменты времени. Мы говорим, что данные две программы для этого часа выполняются параллельно, или одновременно. Другими словами, задачи, которые существуют в одно и то же время и выполняются в течение одного и того же интервала времени, являются параллельными. Параллельные задачи могут выполняться в одно- или многопроцессорной среде. В однопроцессорной среде параллельные задачи существуют в одно и то же время и выполняются в течение одного и того же интервала времени за счет контекстного переключения. В многопроцессорной среде, если свободно достаточное количество процессоров, параллельные задачи могут выполняться в одни и те же моменты времени в течение одного и того же периода времени.
Цель технологий параллелизма — обеспечить условия, позволяющие компьютерным программам делать больший объем работы за тот же интервал времени. Поэтому проектирование программ должно ориентироваться не на выполнение одной задачи в некоторый промежуток времени, а на одновременное выполнение нескольких задач, на которые предварительно должна быть разбита программа. Возможны ситуации, когда целью является не выполнение большего объема работы в течение того же интервала времени, а упрощение решения с точки зрения программирования. Иногда имеет смысл думать о решении проблемы как о множестве параллельно выполняемых задач. Например (если взять для сравнения вполне житейскую ситуацию), проблему снижения веса лучше всего представить в виде двух параллельно выполняемых задач: диета и физическая нагрузка. Иначе говоря, для решения этой проблемы предполагается применение строгой диеты и физических упражнений в один и тот же интервал времени (необязательно точно в одни и те же моменты времени). Иногда к параллельности прибегают, чтобы увеличить быстродействие программы или приблизить момент ее завершения. В других случаях параллельность используется для увеличения продуктивности программы (объема выполняемой ею работы) за тот же период времени при вторичности скорости ее работы. Например, для некоторых Web-сайтов важно как можно дольше удерживать пользователей. Поэтому здесь имеет значение не то, насколько быстро будет происходить подключение (регистрация) и отключение пользователей, а сколько пользователей сможет этот сайт обслуживать одновременно. Следовательно, цель проектирования программного обеспечения такого сайта — обрабатывать максимальное количество подключений за как можно больший промежуток времени. Наконец, параллельность упрощает само программное обеспечение. Зачастую сложную последовательность операций можно упростить, организовав ее в виде ряда небольших параллельно выполняемых операций.
Разбиение программы на подзадачи
Рассматривая разбиение программы на несколько задач, вы делаете первый шаг к внесению параллелизма в свою программу. В однопроцессорной среде параллелизм реализуется посредством многозадачности. Это достигается путем переключения процессов. Каждый процесс выполняется в течение некоторого короткого интервала времени, после чего процессор «передается» другому процессу. Это происходит настолько быстро, что создается иллюзия одновременного выполнения процессов. В многопроцессорной среде процессы, принадлежащие одной программе, могут быть назначены одному или различным процессорам. Процессы, назначенные различным процессорам, выполняются параллельно.
Различают два уровня параллельной обработки в приложении или системе: уровень процессов и уровень потоков. Параллельная обработка на уровне потоков носит название многопоточности (она рассматривается в следующей главе). Чтобы разумно разделить программу на параллельные задачи, необходимо определить, где «гнездится» параллелизм и где можно воспользоваться преимуществами от его реализации. Иногда в параллелизме нет насущной необходимости. Программа может интерпретироваться с учетом параллелизма, но и при последовательном выполнении действий она прекрасно работает. Безусловно, внесение параллелизма может повысить ее быстродействие и понизить уровень сложности. Одни программы обладают естественным параллелизмом, а другим больше подходит последовательное выполнение действий. Программы также могут иметь двойственную интерпретацию.
При декомпозиции программы на функции обычно используется нисходящий принцип, а при разделении на объекты — восходящий. При этом необходимо определить, какие функции или объекты лучше реализовать в виде отдельных программ или подпрограмм, а какие — в виде потоков. Подпрограммы должны выполняться операционной системой как процессы. Отдельные подпрограммы, или процессы, выполняют задачи, порученные проектировщиком ПО.
Задачи,
на которые будет разделена
1. Выделение в программе одной основной задачи, которая создает некоторое количество подзадач.
2. Разделение программы на множество отдельных выполняемых файлов.
3. Разделение программы на несколько задач разного типа, отвечающих за создание других подзадач только определенного типа.
Например,
эти методы реализации параллелизма
можно применить к программе
визуализации. Под визуализацией
будем понимать процесс перехода
от представления трехмерного
1. Установить структуру данных для сеточных моделей многоугольников.
2. Применить линейные преобразования.
3. Отбраковать многоугольники, относящиеся к невидимой поверхности.
4. Выполнить растеризацию.
5. Применить алгоритм удаления скрытых поверхностей.
6. Затушевать отдельные пиксели.
Первая задача состоит в представлении объекта в виде массива многоугольников, в котором каждая вершина многоугольника описывается в трехмерной мировой системе координат. Вторая задача — применить линейные преобразования к сеточной модели многоугольников. Эти преобразования используются для позиционирования объектов на сцене и создания точки обзора или поверхности отображения (области, которая видима наблюдателю с его точки обзора). Третья задача — отбраковать невидимые поверхности объектов на сцене. Это означает удаление линий, принадлежащих тем частям объектов, которые невидимы с точки обзора. Четвертая задача — преобразовать модель вершин в набор координат пикселей. Пятая задача — удалить любые скрытые поверхности. Если сцена содержит взаимодействующие объекты, например, когда одни объекты заслоняют другие, то скрытые (передними объектами) поверхности должны быть удалены. Шестая задача - наложить на поверхности изображения тень.
Рис. 1.1. Способы разбиения программы на отдельные задачи
Рис. 3.14. Этапы визуализации
Решение каждой задачи представляется в виде отдельного выполняемого файла. Первые три задачи (Taskl, Task2 и Task3) выполняются последовательно, а остальные три (Task4, Task5 и Task6)— параллельно.
Используя второй способ, программу визуализации можно запустить из сценария командной оболочки. Преимущество этого сценария состоит в том, что он позволяет использовать все команды и операторы оболочки.
При использовании третьего способа задачи делятся по категориям. При декомпозиции программы следует разобраться, можно ли в ней выделить различные категории задач. Например, одни задачи могут «отвечать» за интерфейс пользователя, т.е. его создание, ввод данных, вывод данных и пр. Другим задачам поручаются вычисления, управление данными и пр. Такой подход весьма полезен не только при проектировании программы, но и при ее реализации. В нашей программе визуализации мы можем разделить задачи по следующим категориям:
• задачи, которые выполняют линейные преобразованиях преобразования изображения на экране при изменении точки обзора; преобразования сцены;
• задачи, которые выполняют растеризацию: вычерчивание линий; заливка участков сплошного фона; растеризация многоугольников;
• задачи, которые выполняют удаление поверхностей: удаление скрытых поверхностей; удаление невидимых поверхностей;
• задачи, которые выполняют наложение теней: затенение отдельных пикселей; затенение изображения в целом.
Разбиение задач по категориям позволяет нашей программе приобрести более общий характер. Процессы при необходимости создают другие процессы, предназначенные для выполнения действий только определенной категории. Например, если нашей программе предстоит визуализировать лишь один объект, а не всю сцену, то нет никакой необходимости порождать процесс, который выполняет удаление скрытых поверхностей; вполне достаточно будет удаления невидимых поверхностей (одного объекта). Если объект не нужно затенять, то нет необходимости порождать задачу, выполняющую наложение тени; обязательным остается лишь линейное преобразование при решении задачи растеризации. Для запуска программы с использованием третьего способа можно использовать родительский процесс или сценарий оболочки. Родительский процесс может определить, какой нужен тип визуализации, и передать соответствующую информацию каждому из специализированных процессов, чтобы они «знали», какие процессы им следует порождать. Эта информация может быть также перенаправлена каждому из специализированных процессов из сценария оболочки
Доступ к объектам из других адресных пространств
Объекты, разделяющие одну область действия (видимости), могут взаимодействовать, получал доступ друг к другу по именам, псевдонимам или с помощью указателей. Объект доступен только в случае, если «видимо» его имя или указатель на него. Видимость имен объектов определяется областью действия. С++ различает четыре основных уровня областей действия:
• блока;
• функции;
• файла;
• класса.
Вспомните, что блок в С++ определяется фигурными скобками {}, поэтому присваивание значения Y переменной X в листинге 8.1 недопустимо, так как переменная Y видима только внутри блока. Функции main() неизвестно имя переменной Y за пределами блока, конец которого обозначен закрывающейся фигурной скобкой.
// Листинг 1. Простой пример области действия блока
int main(int argc, char argv[]) {
int X; int Z; {
int Y;
Z = Y; // Вполне правомочное присваивание.
//.. .
}
X = Y ; // Неверно, поскольку имя Y уже не определено.
}
Однако имя Y видимо для любого другого кода из того же блока, в котором определена переменная Y. Имя, объявляемое внутри функции или ее объявления, получает область видимости этой функции. В листинге 8.1 переменные X и Z видимы только для функции main (), и к ним нельзя получить доступ из других функций. Понятие области видимости файла относится к исходным файлам. Поскольку С++-программа может состоять из нескольких файлов, мы можем создавать объекты, которые видимы в одном файле и невидимы в другом. Имена, обладающие областью видимости файла, видимы, начиная с местоположения их объявления и заканчивая концом исходного файла. Имена с областью видимости файла не должны объявляться ни в одной из функций. Обычно их называют глобальными переменными. Имена, которые характеризуются областью видимости объекта, видимы для любой функции-члена, объявленной как часть этого объекта. Мы используем область видимости объекта в качестве первого уровня доступа к членам объекта. Закрытый, защищенный и открытый интерфейсы объекта определяют второй уровень. И хотя само имя объекта может быть видимым, закрытые и защищенные его члены тем не менее имеют ограниченный доступ. Область действия просто сообщает нам, видимо ли имя объекта. В нераспределенной программе область действия ассоциируется с единым адресным пространством. Два объекта в одном и том же адресном пространстве могут получать доступ друг к другу по имени или указателю и взаимодействовать, просто вызывал методы друг друга.
// Листинг 2. Использование объектов, которые вызывают
// методы других объектов из того же
// адресного пространства
//.. .
some_object А; another_object В;
dynamic_object *C;
C = new dynamic_object;
//...
B.doSomething(A.doSomething() );
A.doSomething(B.doSomething() );
C->doMore (A.doSomething () ) ;
//...
В листинге 1. объекты А и В находятся в одной области видимости, т.е. объект В видим для объекта А, а объект А видим для объекта В. Объект А может вызывать функции-члены объекта В, и наоборот. А В листинге 1 объекты А и В создаются во время компиляции, а объект С — во время выполнения. Все они являются частями одной и той же программы, обладают одной областью видимости, а их адреса принадлежат адресному пространству одного и того же процесса. Чтобы процесс мог выполнить инструкцию, ему нужно знать ее адрес. При компиляции программы, представленной в листинге 1, адреса объектов А и В хранятся в выполняемом файле. Следовательно, процесс, который выполняет программу из листинга 1, будет знать местоположение объектов А и В. Адрес объекту С присваивается во время выполнени я программы, т.е. его точный адрес станет известен только тог д а, когда будет вызвана функция new (). Однако указатель на объект С бу д ет содержать адрес в пределах того же пространства, в котором размещаются объекты А и В, и, следовательно, процесс для получения доступа к объекту С воспользуется этим указателем. Таким образом, доступ к каждому объекту осуществляется на основе доступа к их адресам (прямого или косвенного). Имя переменной объекта — это просто псевдоним для его адреса. Если имя объекта попадает в рамки нашей области видимости, то мы можем получить к нему доступ. Проблема в том, как связать удаленный объект с нашей локальной областью видимости. Для того чтобы получить доступ к объекту D, который находится в другом адресном пространстве, нам необходим некоторый способ ввода адреса удаленного объекта в наш выполняющийся процесс, т.е. нужно научиться связывать удаленный объект с нашей локальной областью видимости. Нам требуется видимое имя, которое бы служило псевдонимом для адреса в другом процессе, причем этот процесс может выполняться даже на другом компьютере. В некоторых случалх этот самый «другой» компьютер может быть подключен к другой сети! Было бы весьма удобно запросить удаленный объект с помощью некоторого согласованного описания и получить ссылку для адреса удаленного объекта. Имея ссылку, мы могли бы взаимодействовать с этим объектом из нашей локальной области действия. Именно для таких нужд распределенного программирования и можно использовать CORBA-реализацию.
Заключение
Программы,
надлежащее качество проектирования которых
позволяет воспользоваться
Применение
более совершенных технологий параллельного
программирования открывает двери
к архитектурам ПО, которые специально
разрабатываются для
Список
использованной литературы
- Хьюз К., Хьюз Т. Параллельное и распределенное программирование на C++. – М.: Издательский дом «Вильямс», 2004. – 672 с.
- http://f1-delphi.ru/
