Парадигмы программирования

Языки параллельного программирования

Разбить на страницы
Показывать лекцию целиком

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

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

Независимая разработка специализированных языков параллельного программирования и языков управления процессами дала ряд интересных идей по представлению и масштабированию параллельных вычислений, с которыми можно ознакомиться по материалам о языках APL, Symula-67, Sisal, БАРС, Occam, Поляр и др. [,,,,,]

Весьма перспективно применение универсальных языков сверх высокого уровня, таких как SETL, Planner, Eiffel, Haskel, Python, Cw и т.п., абстрагирование данных и процессов в которых нацеливает на активное использование математических и функциональных моделей, приспособленных к гибкому и строгому структурированию, удобному для доказательных построений [,,,,].

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

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

Развитие суперкомпьютеров обусловлено существованием особо важных задач, главным требованием к решению которых является скорость вычислений в реальном времени. Нужная скорость достигается ценой весьма сложной организации связей между синхронизованными на уровне аппаратуры процессорами. Активно используется локальная память процессоров, приспособленная к быстрым матричным вычислениям и вообще однородной обработке информации. При программировании целенаправленно выделяются конвейерные процессы, приспособленные к минимизации хранения промежуточных результатов. Разработаны специальные архитектуры сверхдлинных команд с внутренним совмещением микроопераций. Исследованы асинхронные конфигурации и модели управления на метауровне организации параллельных процессов. Специфику языков параллельного программирования для высокопроизводительных вычислений на базе суперкомпьютеров и многоядерных архитектур рассмотрим на примере языков APL, Sisal и БАРС [,,].

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

Заметное место среди языков функционального программирования занимают языки параллельного программирования. Довольно известен язык функционального программирования Sisal.

Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка Sisal следует отметить наиболее характерные, связанные с функциональным стилем программирования [].

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

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

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

    Начнем с примера программы:

    For                            % инициирование цикла
        Approx := 1.0; 
             Sign := 1.0; 
        Denom := 1.0; 
                   i := 1

     while i <= Cycles do      % предусловие завершения цикла

        Sign := -Sign;                       %   однократные
        Denom := Denom + 2.0;                %   присваивания
        Approx := Approx + Sign / Denom;     %   образуют
        i := i + 1                           %   тело цикла

     returns Approx * 4.0              
 % выбор и вычисление результата цикла 
     end for
    for i in [1..Cycles/2] do         
% пространство параллельно исполнимых итераций

         val := 1.0/real(4*i-3) - 1.0/real(4*i-1);      
% тело цикла, для каждого i исполняемое независимо

     returns sum( val )                   
% выбор и свертка результатов всех итераций цикла

     end for * 4.0                           
% вычисление результата выражения

    Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.

    for i in [1..2] dot j in [3..4] do          
% для пар индексов [1,3] и [2,4]

     returns  product (i+j)                   
% произведение сумм 

     end for                    %  = 24
    for i in [1..2] cross  j in [3..4] do       
% для пар [1,3],  [1,4],  [2,3] и [2,4]

     returns product (i+j)                     
% произведение сумм

     end for                         %  = 600
    for
        I := 1
     while I < S do
        K := I;
        I := old I + 2;     
% значение из предыдущей итерации

        J := K + I;
     returns product(I+J)
     end for

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

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

    function Sum (N); % Сумма квадратов
  result (+ ( sqw (1 .. N)));

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

    Основные идеи языков параллельного программирования APL и VAL, предшественника языка Sisal, были интересно обогащены в языке БАРС [] в трех направлениях:

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

    Синхросети позволяют независимые описания процессов синхронизовать в терминах разметки. Узлы с одинаковой разметкой срабатывают одновременно. Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри [].

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

    Страницы:

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

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

    Независимая разработка специализированных языков параллельного программирования и языков управления процессами дала ряд интересных идей по представлению и масштабированию параллельных вычислений, с которыми можно ознакомиться по материалам о языках APL, Symula-67, Sisal, БАРС, Occam, Поляр и др. [,,,,,]

    Весьма перспективно применение универсальных языков сверх высокого уровня, таких как SETL, Planner, Eiffel, Haskel, Python, Cw и т.п., абстрагирование данных и процессов в которых нацеливает на активное использование математических и функциональных моделей, приспособленных к гибкому и строгому структурированию, удобному для доказательных построений [,,,,].

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

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

    Развитие суперкомпьютеров обусловлено существованием особо важных задач, главным требованием к решению которых является скорость вычислений в реальном времени. Нужная скорость достигается ценой весьма сложной организации связей между синхронизованными на уровне аппаратуры процессорами. Активно используется локальная память процессоров, приспособленная к быстрым матричным вычислениям и вообще однородной обработке информации. При программировании целенаправленно выделяются конвейерные процессы, приспособленные к минимизации хранения промежуточных результатов. Разработаны специальные архитектуры сверхдлинных команд с внутренним совмещением микроопераций. Исследованы асинхронные конфигурации и модели управления на метауровне организации параллельных процессов. Специфику языков параллельного программирования для высокопроизводительных вычислений на базе суперкомпьютеров и многоядерных архитектур рассмотрим на примере языков APL, Sisal и БАРС [,,].

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

    Заметное место среди языков функционального программирования занимают языки параллельного программирования. Довольно известен язык функционального программирования Sisal.

    Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка Sisal следует отметить наиболее характерные, связанные с функциональным стилем программирования [].

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

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

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

    Начнем с примера программы:

    For                            % инициирование цикла
        Approx := 1.0; 
             Sign := 1.0; 
        Denom := 1.0; 
                   i := 1

     while i <= Cycles do      % предусловие завершения цикла

        Sign := -Sign;                       %   однократные
        Denom := Denom + 2.0;                %   присваивания
        Approx := Approx + Sign / Denom;     %   образуют
        i := i + 1                           %   тело цикла

     returns Approx * 4.0              
 % выбор и вычисление результата цикла 
     end for
    for i in [1..Cycles/2] do         
% пространство параллельно исполнимых итераций

         val := 1.0/real(4*i-3) - 1.0/real(4*i-1);      
% тело цикла, для каждого i исполняемое независимо

     returns sum( val )                   
% выбор и свертка результатов всех итераций цикла

     end for * 4.0                           
% вычисление результата выражения

    Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.

    for i in [1..2] dot j in [3..4] do          
% для пар индексов [1,3] и [2,4]

     returns  product (i+j)                   
% произведение сумм 

     end for                    %  = 24
    for i in [1..2] cross  j in [3..4] do       
% для пар [1,3],  [1,4],  [2,3] и [2,4]

     returns product (i+j)                     
% произведение сумм

     end for                         %  = 600
    for
        I := 1
     while I < S do
        K := I;
        I := old I + 2;     
% значение из предыдущей итерации

        J := K + I;
     returns product(I+J)
     end for

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

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

    function Sum (N); % Сумма квадратов
  result (+ ( sqw (1 .. N)));

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

    Основные идеи языков параллельного программирования APL и VAL, предшественника языка Sisal, были интересно обогащены в языке БАРС [] в трех направлениях:

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

    Синхросети позволяют независимые описания процессов синхронизовать в терминах разметки. Узлы с одинаковой разметкой срабатывают одновременно. Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри [].

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^