Распараллеливание вычислительных алгоритмов

 

Введение  3

1 Теоретические предпосылки поставленной  проблемы 4

2 Разработка программного средства 16

Заключение 24

Список использованных источников 25

Приложение А – Текст программы 26

Приложение Б – Контрольный  пример 31

 

 

 

Введение

 

 

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

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

Данная задача решена с помощью пакета программного средства Delphi 2007. 
 1 Теоретические предпосылки поставленной проблемы

 

 

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

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

Задача состоит в составлении  в соответствии со своим вариантом схемы алгоритма предложенной задачи: W=5(M+O²)-(3L+4K)*N/2, где

   , разбив ее на неделимые атомы.

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

 

 

На схеме отражены два типа операторов: логические (отмечены ромбом) и арифметические (отмечены прямоугольниками). Логические операторы определяют связи между операторами по управлению, задавая состав и порядок выполнения операторов. А именно, после выполнения логического оператора получает право выполнения лишь один из тех операторов, которые связаны стрелками, исходящими из данного. Другими словами, преемственность операторов после выполнения логических операторов осуществляется по схеме ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

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

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

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

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

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

Условимся исследовать возможности распараллеливания данного алгоритма, не изменяя состава и содержания отраженных на схеме операторов i=1, ..., m. Но обратим внимание на ресурс времени, в котором они нуждаются для своего выполнения. Это необходимо в связи с тем, что решение задач распараллеливания связано с составлением расписания выполнения операторов (задач) в ВС исходя из анализа объема работ, заключенных в каждом операторе, т. е. исходя из временных характеристик их реализации. Таким образом, каждый оператор обретает вес t_i, i=1, ..., т.

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

При оценке веса оператора необходимо учитывать состав и структуру ВС. Если ВС однородная, то достаточно оценить время t_i (целое) выполнения каждого оператора  на одном процессоре.

В данном случае будем  говорить, что U - скалярный вес оператора i. Если ВС неоднородная, то процессор каждого типа j = 1, ..., k в общем случае выполняет оператор i за разное время. Иными словами, вес U являетcя вектором t_i ={t_i1,..., t_ik}, t_ij - целое, где k - число типов процессоров ВС; t_ij = ¥, если процессор j-го типа в силу своей специализации не выполняет оператор i. В частности, в предположении, что ВС неоднородная, каждый вектор-вес может содержать по единственной компоненте, отличной от ¥. В этом случае каждый оператор закреплен только за тем типом процессоров, которыми он может выполняться.

Введем понятие информационно-логической граф-схемы алгоритма.

Определение 1. Информационно-логическая граф-схема алгоритма есть граф вида:

G=(X, P, Г),                       (1)

где X={i} = {1, 2, ...., т} - множество вершин графа, соответствующее множеству операторов алгоритма при тех же обозначениях;

P={t_i}, i=1, ..., т - множество весов вершин, определяющих время выполнения каждого оператора, соответствующего вершине;

Г=Г₁ÈГ₂ - множество дуг, состоящее из дуг двух типов: Г₁ - множество дуг, определяющих связи между операторами по управлению (обозначаются двойной линией); Г₂ - множество дуг, определяющих связи между операторами по информации.

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

Граф схема исходного  алгоритма показана на рисунке 2.

Рисунок 2 – Граф G с информационно–логическими связями

 

 

 

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

Определение 2. Будем говорить, что между операторами и существует связь по управлению (обозначается: => ), если в графе G существует дуга u Г₁, исходящая из вершины Х и входящая в вершину Х.

Определение 3. Будем говорить, что между операторами и существует связь по информации (обозначатся: ), если в графе G существует дуга u Г₂, исходящая из вершины Х и входящая в вершину Х.

Определение 4. Назовем все связи по управлению и по информации между операторами, обусловленные исходным видом графа G, задающими связями.

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

Определение 5. Путями в графе G будем называть последовательности вершин вида k₁, k₂, ..., k_s такие, что для любой пары соседних вершин k_i и k_i+1 существует дуга u Г₁ Г₂, исходящая из вершины k_i и входящая в вершину k_i+1.

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

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

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

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

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

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

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

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