Моделирование программ

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

операций. Узлами информационного графа являются операции, а однонаправленными дугами - каналы обмена данными.

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

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

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

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

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

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