The problem of the Smart Ant-3
The problem of the Smart Ant-3

4.3. Автоматы и параллельные вычисления

automata-and-parallel-computing

В настоящее время, когда быстродействие процессоров традиционной архитектуры уже почти достигло своего максимума, все более важную роль играют параллельные и распределенные вычисления. Для того чтобы иметь возможность оптимальным образом увеличить быстродействие программной системы за счет наличия нескольких вычислителей, необходимо тщательно спроектировать архитектуру системы с учетом параллелизма. Разработка простых и эффективных методов «распараллеливания» программ является в настоящее время одной из самых актуальных проблем программной инженерии.
Существует целый ряд моделей параллельных и распределенных вычислений, а также стандартов, языков и инструментальных средств, их поддерживающих: классическая модель «ветвление/слияние» потоков для параллельных вычислений с общей памятью, реализованная, например, в программном интерфейсе OpenMP модель, основанная на процессах и обмене сообщениями между ними (наприyyмер, стандарт MPI); активные объекты, присутствующие в большинстве распространенных объектно-ориентированных языков программирования; объектно-ориентированная модель SCOOP (Simple Concurrent Object-Oriented Programming) Параллельная автоматная декомпозиция, которая была рассмотрена в параграфе 2.1, порождает еще одну модель параллельных вычислений: параллельно работающие автоматы, взаимодействие которых может осуществляться путем обмена номерами состояний, событиями или сообщениями. В чем же преимущество этой модели перед перечисленными выше? В автоматном программировании управляющие автоматы и объекты управления всегда выделяются в явном виде. Если объекты управления двух автоматов не пересекаются (или область их пересечения невелика), то такие автоматы с большой вероятностью смогут эффективно работать параллельно. В результате при применении автоматного подхода параллелизм часто возникает естественно, без дополнительных преобразований. В качестве примера рассмотрим задачу декодирования файлов формата GIF (сравнение автоматного и традиционного подходов к решению этой задачи подробно обсуждается в работе). Задача состоит в том, чтобы преобразовать GIF-файл в матрицу цветов пикселей, составляющих изображение. При декодировании таких файлов сначала декодируется заголовок изображения, а затем оставшаяся часть файла разбирается на блоки. Каждый блок, в свою очередь, состоит из заголовка и тела, представляющего собой LZW-код искомой последовательности цветов пикселей. В работе описано решение этой задачи с использованием программирования с явным выделением состояний. При этом автоматная декомпозиция приводит к выделению трех автоматов: первый отвечает за декодирование заголовка, второй разбивает основную часть файла на блоки, а третий расшифровывает LZW-коды. В результате такой декомпозиции оказывается, что второй и третий автоматы могут работать параллельно: каждый раз, когда второй автомат выделяет тело очередного блока, ему необязательно дожидаться, пока третий автомат преобразует это тело в последовательность цветов пикселей. Ему достаточно отправить выделенный LZW-код третьему автомату в качестве сообщения или передать его через очередь с параллельным доступом.

4.4. Автоматы и генетическое программирование

1.8.1.2.Пропорции экрана монитора

Программирование логических контроллеров ПЛК-автоматов