Применение параллельных алгоритмов — КиберПедия 

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

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Применение параллельных алгоритмов

2020-04-01 236
Применение параллельных алгоритмов 0.00 из 5.00 0 оценок
Заказать работу

 

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

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

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

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

 


Рис. 5. Общая схема разработки параллельных алгоритмов

 

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

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

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

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

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

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

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

 

Рис. 6. Модель параллельной программы в виде графа «процессы - каналы»

 

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

Дадим дополнительные пояснения для используемых понятий в модели «процессы - каналы»:

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

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

В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема / передачи с каналом. По степени общности канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично, при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами - источниками сообщений.

Следует отметить важное достоинство рассмотренной модели «процессы - каналы» - в ней проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ.

 

CASE -системы

В последние годы на мировом рынке программных продуктов появилось много программных средств, называемых CASE-системами или CASE-средствами. Слово CASE представляет собой сокращение от Computer Aided Software Engineering. В русскоязычной литературе нет соответствующего общепринятого термина. С нашей точки зрения есть два наиболее соответствующих оригиналу и назначению CASE-систем перевода: ``Программная инженерия, поддерживаемая компьютером'' и менее буквальный, но более отвечающий сути перевод ``Средства разработки программ с помощью компьютера''. Теоретическое осмысливание этого явления и его места в технологии программирования находится на очень ранних стадиях.

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

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

Приведенная технология базируется в основном на стандартах IEEE [10,11] (IEEE - Institute of Electrical and Electronics Engineers - Институт инженеров по электротехнике и электронике). Термин «внедрение» используется в широком смысле и включает все действия от оценки первоначальных потребностей до полномасштабного использования CASE-средств в различных подразделениях организации-пользователя. Процесс внедрения CASE-средств состоит из следующих этапов:

    определение потребностей в CASE-средствах;

    оценка и выбор CASE-средств;

    выполнение пилотного проекта;

    практическое внедрение CASE-средств.

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

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

Приведем краткий обзор некоторых CASE-средств.

- Power Designer компании Sybase. В состав Power Designer входят следующие модули:Analyst - средство для функционального моделирования, поддерживает нотацию Йордона - ДеМарко, Гейна - Сарсона и несколько других.Analyst - инструмент для построения модели «сущность-связь» и автоматической генерации на ее основе реляционной структуры.Modeler - инструмент для автоматической генерации прототипов программ обработки данных на основе реляционных моделей, построенных в Data Analyst.

- Silverrun компании Silverrun Technologies Ltd. CASE-система Silverrun состоит из следующих инструментов:- построение DFD-диаграмм. Поддерживает нотации Йордона-ДеМарко, Гейна - Сарсона, Уорда-Меллора и многие другие. Данный инструмент позволяет автоматически проверить целостность построенной модели, причем список критериев проверки определяется пользователем (например: отсутствие имен у элементов модели, потоки данных типа «хранилище - хранилище» или «внешняя сущность - внешняя сущность» и т.д.)- построение диаграмм «сущность-связь». Поддерживаются не только бинарные связи, но и связи более высоких порядков, имеется возможность определения атрибутов у связей. Построенные ER-модели с помощью внешней утилиты могут быть сконвертированы в реляционный структуры (в той версии, с которой я работал, при этом, к сожалению, терялись атрибуты связей).- инструмент реляционного моделирования, позволяет генерировать SQL-скрипты для создания таблиц и индексов примерно для 25 целевых СУБД.

- BPWin и ERWin компании LogicWorks. LogickWorks выпускает два взаимнодополняющих инструмента проектирования информационных систем:- функциональное моделирование на основе методологии IDEF0. Допускается также использовние нотации IDEF3 и DFD в нотации Йордона - ДеМарко. Имеется возможность экспорта построенных моделей в системы функционально-стоимостного анализа (ABC - Activity Based Costing) и информационного моделирования ERWin.- средство информационного моделирования, используется нотация IDEF1X. Поддерживаются свыше 20 целевых СУБД, имеется возможность генерации прототипов прикладных программ для Visual Basic, Delphi и т.д.

- Designer/2000 компании Oracle. Данный продукт компании Oracle, возможно, наиболее полно поддерживает все этапы создания приложений обработки данных. Однако, следует оговориться, что, в отличие от других средств, он поддерживает практически одну целевую СУБД - Oracle Server (имеется еще возможность генерации скриптов на ANSI SQL). То же самое касается и средств создания пользовательсокго интерфейса. Хотя возможна генерация прототипов программ для языков Visual Basic, C, Java, полностью все возможности Designer/2000 реализуются только при использовании его вместе со средством разработки Oracle Developer/2000. В состав Oracle Designer/2000 включены модули: инструментарий анализа предметной области, генераторы структур, инструментарий проектирования приложения, генераторы данных и кода.

- Rational Rose. Это CASE-система для визуального моделирования объектно-ориентированных программных продуктов. Визуальное моделирование - процесс графического описания разрабатываемого программного обеспечения. В его составе выделяют шесть элементов: строку инструментов, панель «инструменты диаграммы», окно диаграммы, браузер, окно спецификации, окно документации. В процессе генерации Rational Rose отображает логическое описание класса в каркас программного кода - в коде появляются языковые описания имени класса, свойств класса и заголовки методов. Кроме того, для описания тела каждого метода формируется программная заготовка. Появляются и программные связи классов. Автоматическая генерация была задана настройкой среды - свойствами генерации. Система обеспечивает настройку параметров генерации для уровней класса, роли, свойства (атрибута) и проекта в целом.

 


Заключение

 

Современная программная инженерия (Software Engineering) - молодая и быстро развивающаяся область знаний и практики. Она ориентирована на комплексное решение задач, связанных с разработкой особой разновидности сложных систем - программных систем.

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

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

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

1. Уважительные отношения с клиентами и пользователями программ, выполнение взятых на себя обязательств качественно и в срок.

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

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

.   Разработка должна быть дружественной пользователю. Она должна быть для пользователя, а не пользователь для нее. Из этого следует несколько выводов:

    Программа не должна по возможности задавать вопросы пользователю, наоборот она должна отвечать на них.

    Документация нужна любой разработке, но пользователь имеет ПРАВО не пользоваться ей. Документация не должна служить «затычкой» неправильных решений в области структуры данных и пользовательских интерфейсов.

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

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

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

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

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

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

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

Базис современной программной инженерии образуют следующие составляющие:

процессы конструирования ПО;

метрический аппарат, обеспечивающий измерения процессов и продуктов;

аппарат формирования исходных требований к разработкам;

аппарат анализа и проектирования ПО;

аппарат визуального моделирования ПО;

аппарат тестирования программных продуктов.

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

Хотелось бы обратить внимание на новейшие постобъектные методологии - аспектно-ориентированное и многомерное проектирование и программирование. Они представляют собой новую высоту в стремительном полете в компьютерный космос. Но это - тема другой отдельной работы.

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

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

 


Список литературы

 

1. Технологии разработки программного обеспечения. 2002. Орлов С А

2. Материалы сайта www.intel.com/software/products/

3. Приемы объектно-ориентированного проектирования. Паттерны проектирования. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Д. 2003.

.   Экстремальное программирование. Бек К. 2004.

.   Язык программирования C++. Страуструп Б. 1996.

.   Рефакторинг: улучшение существующего кода. Фаулер М., Бек К., Брант Д., Робертс Д., Апдайк У. 1999.

.   Автоматизированные библиотечно-информационные системы России: состояние, выбор, внедрение, развитие. Шрайберг Я.Л., Воройский Ф.С. - М.: Либерея, 1996

.   Проектирование баз данных информационных систем. 2-ое изд. - М.: Финансы и статистика, Бойко В.В., Савинков В.М. 1989.

.   Введение в АСУ. Глушков В.М., 1974.

10. IEEE Std 1348-1995. IEEE Recommended Practice for the Adoption of CASE Tools.

.   IEEE Std 1209-1992. IEEE Recommended Practice for the Evaluation and Selection of CASE Tools.

12. Один из подходов к выбору средств проектирования баз данных и приложений. Вендров А.М. 1995.

.   Бизнес-реинжиниринг и технологии системного проектирования. Зиндер Е.З. 1996

.   CASE. Структурный системный анализ (автоматизация и применение). Калянов Г.Н. 1996.

.   Методология структурного анализа и проектирования. Марка Д.А., МакГоуэн К. 1993.


Поделиться с друзьями:

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...

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

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.015 с.