2. Параллельная обработка как основа высокопроизводительных вычислений. Уровни организации параллелизма: уровень заданий, программ и команд. Системы (языки) параллельного программирования.

Организация параллельной обработки информации -. одновременное решение задач или совмещение во времени этапов решения одной задачи.

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

1)      совмещение во времени различных этапов разных задач;

2)      одновременное решение различных задач пли частей одной задачи;

3)      конвейерная обработка информации.

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

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

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

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

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

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

обе ветви должны выполняться по разным блокам программы (программная независимость).

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

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

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

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

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

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

К сожалению, выигрыш по производительности в l раз практически невозможен, так как может быть получен только при выполнении программы без условных переходов. Наличие условных переходов сразу нарушает работу конвейера и приводит к «холостым» пробегам конвейера, когда по выработанному в команде K_i признаку результата надо перейти к выполнению не K_i+1-й команды, а совершенно другой, что вызывает необходимость очистки всех блоков и загрузки их другой операцией. В реальных ЭВМ и системах применяются различные приемы, позволяющие определять признак перехода возможно раньше, однако совсем исключить влияние условных переходов не удается. Тем не менее для определенных задач, где имеют место цепочки команд без таких переходов, выигрыш в производительности конвейерного процессора команд получается значительным. Как и в конвейере арифметических операций, выигрыш в производительности получается тем больше, чем длиннее участки программы без условных переходов и чем больше предусматривается независимость этапов (и, следовательно, блоков устройства управления) при выполнении команды.

Языки параллельного программирования: параллельный ФОРТРАН и параллельный PASCAL.

3. Шаблоны. Шаблоны функций С++. Шаблоны классов С++. Определение шаблоны класса. Явная реализация некоторых методов для специфических типов. Полное переопределение шаблона класса для работы с некоторым особым типом. Шаблоны и дружественные функции. Шаблоны и наследование. Шаблоны и конфигурация компилятора. Достоинства и недостатки шаблонов.

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

Параметрическое программирование в языке C++ реализовано с помощью шаблонов (template). В C++ определено два вида шаблонов: шаблоны-классы и шаблоны-функции.

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

#define min(a,b) ((a)<(b)?(a):(b))

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

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

Шаблоны-классы. Зачем программисту может понадобиться определить такой тип, как вектор целых чисел? Как правило, ему нужен вектор из элементов, тип которых неизвестен создателю класса Vector следовательно, надо суметь определить тип вектора так, чтобы тип элементов в этом определении участвовал как параметр, обозначающий "реальные" типы элементов:

Таково определение шаблона типа. Он задает способ получения семейства сходных классов. В нашем примере шаблон типа Vector показывает, как можно получить класс вектор для заданного типа его элементов Это описание отличается от обычного описания класса наличием начальной конструкции template<class T>, которая и показывает, что описывается не класс, а шаблон типа с заданным параметром-типом (здесь он используется как тип элементов) Возможности, которые реализует шаблон типа иногда называются параметрическими типами. Использование шаблона типа не влечет за собой каких-либо дополнительных расходов времени по сравнению с использованием класса, в котором все типы указаны непосредственно.

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

Функция-друг для шаблона типа не является неявной шаблонной функцией. Например:

template<class T> class task

{ friend void next_time();

friend task<T>* preempt(task<T>*);

friend task* prmt(task*); // ошибка

};

Здесь функция next_time() становится другом всех классов task, а каждый класс task имеет в качестве друга ф-ю рreempt() с соответствующими типами параметров. Функцию preempt() можно определить как шаблон типа:

template<class T> task<T>* preempt(task<T>* t) {/*... */}

Описание функции prmt() является ошибочным, поскольку типа task не существует, а есть только специальные шаблонные типы task<int>, task<record>, и т.д.

Шаблоны и наследование. Классы, порождаемые расширением шаблонов, совершенно обычным образом можно использовать в построении иерархий наследования.

Шаблоны и конфигурация компилятора. В связи с тем, что стандарт языка C++ не ограничивает свободу реализации конкретных элементов языка, существуют различные параметры конфигурации компиляторов, влияющие на тонкие и двусмысленные моменты в поведении шаблонов, но не выводящие компилятор за рамки стандарта ISO C++.

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

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

Недостатки:

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

2. Непереносимость программ на другие объектно-ориентированные языки. Например, библиотека STL, входящая в стандарт языка C++, не может быть перенесена в среду Delphi, так как язык Object Pascal не поддерживает шаблоны.

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

Билет 24