Ответы к экзамену (2), страница 5

Основным средствомкоммуникации между процессами в MPI является передача сообщений друг другу. СтандартизациейMPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который долженподдерживаться как на платформе, так и в приложениях пользователя. В настоящее время существуетбольшое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языковФортран 77/90, Си и Си++.В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затратына передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью(многоядерные с общим кэшем). Обе технологии могут использоваться совместно, дабы оптимальноиспользовать в кластере многоядерные системы.В MPI 1.1 (опубликован 12 июня 1995 года, первая реализация появилась в 2002 году) поддерживаютсяследующие функции:● передача и получение сообщений между отдельными процессами;● коллективные взаимодействия процессов;● взаимодействия в группах процессов;● реализация топологий процессов;В MPI 2.0 (опубликован 18 июля 1997 года) дополнительно поддерживаются следующие функции:● динамическое порождение процессов и управление процессами;● односторонние коммуникации (Get/Put);● параллельный ввод и вывод;● расширенные коллективные операции (процессы могут выполнять коллективные операции не тольковнутри одного коммуникатора, но и в рамках нескольких коммуникаторов).азовым механизмом связи между MPI процессами является передача и приём сообщений.

Сообщениенесёт в себе передаваемые данные и информацию, позволяющую принимающей стороне осуществлять ихвыборочный приём:● отправитель — ранг (номер в группе) отправителя сообщения;● получатель — ранг получателя;● признак — может использоваться для разделения различных видов сообщений;● коммуникатор — код группы процессов.Операции приёма и передачи могут быть блокирующимися и не блокирующимися. Для не блокирующихсяопераций определены функции проверки готовности и ожидания выполнения операции.Другим способом связи является удалённый доступ к памяти (RMA), позволяющий читать и изменятьобласть памяти удалённого процесса. Локальный процесс может переносить область памяти удалённогопроцесса (внутри указанного процессами окна) в свою память и обратно, а также комбинироватьданные, передаваемые в удалённый процесс с имеющимися в его памяти данными (например, путёмсуммирования).

Все операции удалённого доступа к памяти не блокирующиеся, однако, до и после ихвыполнения необходимо вызывать блокирующиеся функции синхронизации.218. Язык FPTL: синтаксис (операция композиции функций, заданиеданных), семантика. Модели параллельного вычисления значенийфункций.Программы на традиционных языках программирования, таких как Си, Паскаль, Java и т.п. состоятих последовательности модификаций значений некоторого набора переменных, который называетсясостоянием. До начала выполнения программы состояние имеет некоторое начальное значение σ0, вкотором представлены входные значения программы.

После завершения программы состояние имеет новоезначение σ’,включающее в себя то, что можно рассматривать как «результат» работы программы. Во времяисполнения каждая команда изменяет состояние; следовательно, состояние проходит через некоторуюконечную последовательность значений: σ = σ0 → σ1 → σ2 → · ·· → σn = σ’Состояние модифицируется с помощью команд присваивания. Эти команды следуют одна задругой; операторы, такие как if и while, позволяют изменить порядок выполнения этих командв зависимости от текущего значения состояния.

Такой стиль программирования называютимперативным или процедурным.Функциональная программа представляет собой некоторое выражение (в математическомсмысле); выполнение программы означает вычисление значения этого выражения. можно сказать,что финальное состояние (или любое промежуточное) представляет собой некоторую функцию (вматематическом смысле) от начального состояния, т.е. σ’= f(σ). В функциональном программировании используется именно эта точка зрения: программа представляет собой выражение,соответствующее функции f.Функциональные языки программирования поддерживают построение таких выражений,предоставляющие широкий выбор соответствующих языковых конструкций.При сравнении функционального и императивного подхода к программированию можно заметитьследующие свойства функциональных программ:· Функциональные программы не используют переменные в том смысле, в котором это словоупотребляется в императивном программировании.

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

Прежде всего,функциональные программы более непосредственно соответствуют математическим объектам, иследовательно, позволяют проводить строгие рассуждения. Установить значение императивнойпрограммы, т.е. той функции, вычисление которой она реализует, может оказаться довольнотрудно. Напротив, значение функциональной программы может быть выведено практическинепосредственно.Рассмотрим следующую программу на языке Haskell: factorial n = if n == 0 then 1 else n * factorial (n-1)Язык FPTL (Functional Parallel Typified Language) – язык функционального композиционногопараллельного программирования. Его отличительные особенности:· композиционный стиль программирования, в основе которого лежит универсальный наборопераций композиции функций и их определение через системы функциональных уравнений;· схемный характер задания функций, структурированность определений;22· возможность определения различных типов данных, строгая типизация и статическийконтроль типов;· полиязычность, заключающаяся в возможности использования в нем функций, определяемыхна других языках программирования;· асинхронная вычислительная семантика, основанная на формальной модели свертывания иразвертывания деревьев – состояний вычислительного процесса, индуцируемого при применениифункции к аргументам.Теоретическую базу языка FPTL составляют исследования по функциональной схемотологиии функциональным системам, которые обобщены в теории направленных отношений,объединяющей функциональный и логический стили программирования.Основными семантическими объектами, представляемыми в языке, являются данные, функции,функционалы и реляционалы – параметризованные функции и типы данных соответственно.Функции в FPTL рассматриваются как типизированные соответствия между множествами(данными).

В общем случае, в качестве аргументов и значений функций в языке FPTL выступаюткортежи произвольной длины m0, элементами которых могут быть синтаксически определенныеобъекты различной структуры.Данные и функции в языке FPTL определяются в общем случае посредством системыреляционных или функциональных уравнений, которые трактуются как операторы "взятия"минимальной фиксированной точки или минимального решения (для соответствующихинтерпретаций) для этих систем реляционных и функциональных уравнений.В языке FPTL для построения функций используются следующие четыре простые операциикомпозиции (интерпретация операции композиции задается как график функции, определяемойчерез эту операцию):Все операции композиции являются бинарными, и их определение дается в инфиксной форме.Для того чтобы сохранялось свойство функциональности для f операция Å должна применятьсятолько к совместным или ортогональным функциям.Функции f1 и f2 совместны тогда и только тогда, когда;функции f1 и f2 ортогональны, если они совместны и не существует кортежей b1 и b2 таких, что (a,b1)Îf1 и (a, b2)Îf2 для всякого a.Далее мы покажем, как использование конструкторов (функций), вводимых при задании данных,позволяет (через понятие деструктора) строить ортогональные функции.Аппликация функции f, определенной посредством операции Å, теперь имеет следующуюсемантику: f(x) = f1(x) или f(x) = f2(x), т.е.

одному из значений f1(x) или f2(x), которое определено;если значение f1(x) и f2(x) оба не определены, f(x) также не определено.4) Условие (->)23, если значение f1(x)определено.Заметим, что первые две операции композиции позволяют выразить известный операторподстановки, используемый в языке рекурсивных функций и в обычной математической нотации:Через две другие операции композиции легко представляется условный оператор языковпрограммирования или задание функции путем разбора случаев, используемое в обычнойматематической практике:причем это неопределенное значение является вычислимым и в описываемом далее языкепредставляется явно в виде обозначения w.