Презентация на тему Информационная структура программ. Граф алгоритма. Графовые модели программ.

Информационная структура программ (1) Три «кита» высокопроизводительных вычислений:Архитектура вычислительных системТехнологии параллельных вычисленийАлгоритмыВ последние десятилетия увеличение быстродействия компьютеров определяется не только (и не столько) уменьшением тактового периода элементной базы, но и принятием новых решений в архитектуре, в том числе – за счет параллелизма.Создается программное обеспечение, помогающее эффективно осваивать вычислительные системы с параллельной архитектурой С быстрым развитием многопроцессорных компьютеров задача создания эффективных параллельных программ существенно усложнилась из-за нехватки должной поддержки со стороны языков программирования, компиляторов, ОС и др., существенно отстающего по сравнению с аппаратными средствами. Фактически, забота об эффективной организации параллельных процессов ложится, в основном, на пользователя. Информационная структура программ (2)  Задача адаптации большого числа существующих программ под новые компьютеры является сложной и актуальной проблемой.При адаптации последовательных программ для параллельных компьютеров необходимо определять целое множество свойств, которые указывают на имеющийся потенциальный параллелизм исследуемых программ и возможные способы их преобразования.Выявление этих свойств обычно возлагается на пользователя, поскольку методы, использующиеся в штатных компиляторах параллельных систем, как правило, не в состоянии обеспечить достижение нужного уровня производительности.Для помощи пользователям создаются специальные технологии параллельного программирования и разрабатываются автономные системы анализа структуры программ. Данное направление исследований активно развивается и у нас в стране, и за рубежом для анализа последовательных пользовательских пакетов с точки зрения выявления параллелизма и возможностей эффективного преобразова-ния под требования конкретных параллельных систем. Информационная структура программ (3) На таких системах могут быть реализованы самые передовые идеи исследования и эквивалентного преобразования программ. К таким инструментам относятся системы КАР, Forge, V-Ray (НИВЦ).С помощью таких систем можно значительно уменьшить время работы программ на параллельных системах по сравнению со временем, которое показывают те же программы, пропущенные через штатный компилятор. Ускорение в несколько раз удается получить, даже если программы предварительно оптимизируются вручную.Для достижения предельно возможного ускорения требуется применять существенно более сложные методы преобразования программ, чем те, которые включаются в традиционные компиляторы. Для успешного освоения параллельных вычислительных систем пользователям необходимо иметь возможность получать подробные сведения о деталях структуры своих алгоритмов и программ. Под информационной структурой программы подразумевается совокупность сведений о том, как отдельные элементы программы связаны между собой. Информационная структура программ (4) Для исследования тонкой информационной структуры программ используются графовые модели, формализующие отдельные срабатывания операторов и точное описание информационных связей. Автоматизированный разбор исследуемой программы состоит в анализе каждого оператора и представлении информации об его информационных связях с другими фрагментами программы в виде совокупности графовых структур. Далее, уже в терминах теории графов, проводится компьютерный анализ независимости отдельных фрагментов программы. Методы анализа программ основаны на проверке некоторого набора достаточных условий информационной независимости друг от друга отдельных фрагментов исследуемого кода. Найденные свойства используются для адаптации (автоматического преобразования) программ с ориентацией на конкретную архитектуру. НО:Нет гарантии, что программа действительно не обладает нужным свойством, если проверяемое достаточное условие не выполнено. Новые архитектуры существенно опережают выпуск систем анализа Информационная структура программ (5) В системе V-Ray (разработка лаборатории Параллельных информацион-ных технологий НИВЦ МГУ) реализован более общий подход к анализу программ. В работах В.В.Воеводина и Вл.В.Воеводина сформулированы и доказаны необходимые и достаточные условия существования информационной зависимости в программах. Эти критерии применимы к широкому классу программ, называемому линейным классом (к каноническому линейному виду может быть приведено на практике большинство программ): Любое число переменныхУправление при использовании условных операторов и т.п. всегда передается вниз по тексту. Нет побочных выходов из циклов.Шаг в цикле всегда +1Условие передачи управления всегда задается линейными формами по параметрам циклов и входным даннымВходные данные известны в момент запуска программы. Граф алгоритма (1) Любой компьютерный код описывает семейство алгоритмов, которое определяется входными данными. Фиксированный набор входных данных однозначно определяет конкретный алгоритм даже при наличии условных операторов, т.к. выбор конкретной реализации определяется тем, как срабатывают условные операторы, а это, в свою очередь, строго зависит от входных данных. Поэтому последовательный компьютер всегда выполняет некоторую последовательность действий, которая однозначно определена программой и входными данными. Тем самым, однозначно определен результат. На параллельных системах возможны варианты. В каждый момент времени может выполняться целый набор операций, не зависящих друг от друга. На любой конкретной параллельной системе программа и входные данные однозначно определяют как набор, так и последо-вательность их выполнения. Но сами наборы и порядок их выполнения на разных системах могут быть разными. Чтобы гарантировать получение однозначного результата, порядок выполнения всей совокупности операций должен подчиняться некоторому условию. Граф алгоритма (2) Решение любой задачи (и на последовательном, и на параллельном компьютере) сводится к выполнению последовательности мелких операций с конечным числом аргументов. Аргументами выступают:входные данные,результаты выполнения предшествующих операций. В этом случае операция не может начаться раньше, чем будут готовы ее аргументыЗначит, для любых двух операций определена одна из двух возможностейзафиксирована последовательность операцийконстатируется факт, что операции могут быть выполнены независимо, т.е. в любой последовательности либо одновременно.В последнем случае имеем неоднозначность реализации, т.е. порядка выполнения операций, но при этом любая реализация должна обеспечивать однозначный конечный результат.Графовая трактовка. Строим ориентированный граф, в вершины которого взаимно-однозначно отображается множество операций программы. Ребра со стрелками соединяют вершины, если одна операция поставляет другой операции свои результаты в качестве аргументов. Граф алгоритма (3) Входные данные представлены как начальные операции ввода, в виде вершин (узлов), не имеющих входных дуг (входные вершины графа)Каждой операции кода соответствует узел (вершина) графа,Дуги (ребра) со стрелками - пересылка аргументов и результатов,Результаты – вершины графа без выходных стрелок Это граф информационной зависимости реализации алгоритма при фиксированных входных данных. ИЛИ граф алгоритмаГраф алгоритма всегда:параметризованный (имеет место зависимость от входных данных, размерности массивов и т.д.). детерминированный (если нет условных операторов) или недетерминированный (если условные операторы присутствуют). ациклический (в программах реализуются только явные вычисления, т.е. вход никогда не совпадает с выходом). мультиграф (вершины могут быть связаны несколькими дугами), ориентированный (стрелки) Граф алгоритма (4) Итак, каждое описание алгоритма порождает ориентированный ациклический мультиграф. Верно и обратное. Если задан ориентированный ациклический мультиграф, то его всегда можно рассматривать как граф некоторого алгоритма. Для этого каждой вершине нужно поставить в соответствие любую однозначную операцию, имеющую столько аргументов, сколько дуг входит в вершину графа.Можно написать программы, реализующие один и тот же алгоритм по-разному – и, соответственно, построить разные графы. Параллельная форма графа: каждой вершине соответствует индекс j=1,2,..s