Параллельные алгоритмы
Транспьютерные схемы распараллеливани
«Пропускная» схема распараллеливания на процессорах i860
Резервы повышения производительности для процессоров i860
«Пускач удаленных заданий» в клиент-серверных системах, построенный на сокетах
Применение «нитевых» технологий для алгоритмов с большой вычислительной трудоемкостью
Введение
Применение многопроцессорных систем требует учета и освоения определенной специфики параллельных вычислений. В настоящей статье описываются особенности параллельного программирования для обширного класса аппаратных платформ, имеющих между собой много общего.
Многопроцессорные вычислительные системы (вычислительные кластеры) находят в последнее время широкое применение — это и многопроцессорные серверы с масштабируемыми СУБД, и суперкомпьютеры, используемые для организации трудоемких вычислительных экспериментов, и Intranet-сети масштаба предприятия, позволяющие разделять информационные и вычислительные ресурсы. У вычислительных кластеров — различные архитектура и операционное окружение, но при программировании в них часто возникают одинаковые проблемы. Все это требует по-новому осмыслить использование распределенных вычислительных средств как общего коллективного ресурса. Мы попытаемся описать хотя бы малую часть этого «айсберга».
Если считать, что тактовая частота работы процессоров приблизительно соответствует их производительности, то в настоящее время около 103 млн. операций в секунду (МОПС) — это максимально возможная производительность, которая достижима на одном процессоре. Поскольку ежегодно тактовая частота выпускаемых процессоров возрастает, можно надеяться на увеличение максимальной производительности примерно до 106–108 МОПС. Однако эти процессы не имеют линейной экстраполяции во времени в силу молекулярных ограничений. Процессоры с производительностью более 108 МОПС либо будут иметь принципиально иную архитектуру по сравнению с современными процессорами, либо вообще невозможны. Из этого следует, что единственной стратегией развития вычислительной техники является создание многопроцессорных вычислителей. Получается, что параллельные алгоритмы — единственный перспективный способ повышения производительности при решении будущих задач.
 |
|
Транспьютерные схемы распараллеливани
Идея работающих параллельно вычислителей не нова. Начнем описание программирования параллельных алгоритмов с транспьютерных вычислительных кластеров фирмы Inmos, количество узлов которых могло измеряться сотнями. Транспьютер — это многозадачный процессор с четырьмя портами, выполненными на аппаратном уровне. Унитарный узел транспьютерной сети может не иметь операционной системы.
Приложение для транспьютерных вычислительных кластеров всегда состоит из двух задач: мастер(master)-задачи, выполняющейся на корневом транспьютере и рабочих (worker) задач, выполняющихся на всех остальных транспьютерах. При этом мастер служит в основном для управляющих функций, а рабочие задачи несут на себе вычислительную нагрузку. Мастер-задача может общаться при помощи стандартных операторов ввода-вывода (например, операторы read/write в Pascal) с host-машиной, которой является персональный компьютер. В примерах, входящих в комплект поставки транспьютеров, предлагается клиент-серверная синхронизация между задачами. В главной программе, выполняющейся на корневом транспьютере, порождаются два процесса — Send и Receive, отвечающие за посылку и прием сообщений от рабочих транспьютеров. Эти процессы находятся в бесконечных циклах (листинг 1). Решение о прекращении задачи принимается порождающим Main-процессом (листинг 2). Данные передаются через глобальные переменные. Рабочие программы выполняют аналогичный цикл, начинающийся командой приема и заканчивающийся командой отсылки вычисленных данных (листинг 3). Такая организация вычислений на транспьютерной сети в зависимости от количества узлов в сети и ее топологии, от времени работы одного узла над порцией данных и скорости обмена между i-м и j-м узлами — могла приводить к неполной загрузке сети. Предположим, количество узлов равно 32. Send-процесс загрузил работой 16 из них и готовит данные для 17-го. В это время Receive-процесс получает обработанные данные от 2-го сетевого транспьютера. Поскольку в Send-процессе никак не контролируется, какому узлу следует послать данные, то они могут быть посланы освободившемуся 2-му узлу вместо 17-го. Поэтому значительная часть транспьютеров останется без работы. Кроме того, сам принцип выделения в отдельные процессы процедур Send и Receive из Main кажется неоправданным.
Проблему можно преодолеть, принудительно отсылая данные каждому транспьютеру
в сети. Модуль IO_Net 
предназначен для размещения и выполнения одной и той же рабочей задачи (Worker-задачи)
во всех сетевых транспьютерах. Процедуры модуля организуют взаимодействие управляющей,
или главной, задачи (master-задачи), размещенной в корневом транспьютере,
с рабочими задачами. Конкретное направление пересылки данных определяется используемыми
процедурами: от главной задачи — к свободной в данный момент рабочей задаче.
От рабочей задачи — к главной. Модуль состоит из двух типов процедур. Для первого
типа процедур на длину пересылаемых данных накладывается ограничение, поэтому
сообщение может состоять из одной или нескольких порций. Вызов одной из процедур
осуществляет передачу только одной порции. Пpи этом необходимо указать, является
ли эта порция последней. Гарантируется, что разные порции одного сообщения попадут
в одну и ту же рабочую задачу. Для второго типа процедур передаваемые сообщения
могут быть неограниченного размера. Все доступные сетевые транспьютеры имеют
адреса от 1 до N. Передачу сообщений из master-задачи в сеть можно
осуществлять в двух режимах. В первом режиме, когда параметр addr=0,
используется механизм внутренней адресации транспьютеров. Это означает, что
адрес очередного транспьютера A[i+1] определяется по формуле: A[i+1]
= A[i] mod (N-1)+1, где N — общее количество доступных сетевых транспьютеров.
Во втором режиме, когда параметр addr=1..N, осуществляется передача данных
по указанному адресу. Следует отметить, что в любом случае становится известным
адрес освободившегося от вычислений сетевого транспьютера. Для обеспечения выполнения
указанных функций, помимо пакета стандартных процедур, используется системная
задача router .
Механизм внутренней адресации рекомендуется использовать тогда, когда время
работы worker-задач в разных транспьютерах приблизительно одинаковое.
В противном случае вероятны значительные простои сетевых транспьютеров. Схема
работы с модулем в режиме использования механизма внутренней адресации может
быть следующей:
- Определить количество доступных сетевых транспьютеров N.
- Передать исходные данные для n транспьютеров (n меньше или равно N).
- Принять от всех n транспьютеров результаты вычислений.
- При необходимости продолжить вычисления следует перейти к пункту 2.
Пример использования процедур и функций из модуля IO_Net.pas приведен в листинге 4.
При повторной передаче данных, когда количество используемых транспьютеров n меньше общего числа транспьютеров N, могут быть загружены обработкой другие, ранее не работавшие транспьютеры. Об этом следует помнить в том случае, когда worker-задача может менять хаpактеp обработки в зависимости от количества обращений к ней. Режим непосредственной адресации позволяет осуществлять повторную загрузку освободившегося транспьютера сpазу после завершения в нем обработки предыдущей порции информации, не дожидаясь окончания работ во всех остальных загруженных ранее транспьютерах. Таким образом, данный режим можно с успехом использовать в том случае, когда время работы worker-задачи в разных транспьютерах сильно отличается. В результате можно свести к минимуму простои сетевых транспьютеров. Схема работы с модулем в режиме непосредственной адресации может быть следующей:
- Определить количество доступных сетевых транспьютеров N.
- Передать исходные данные для n транспьютеров (n меньше или равно N).
- В отсутствие необходимости повторной загрузки транспьютеров перейти к пункту 7.
- Принять от одного сетевого транспьютера результаты вычислений.
- Передать следующую порцию исходных данных в освободившийся транспьютер.
- Если имеются необработанные данные, то перейти к пункту 4.
- Принять от всех n транспьютеров результаты вычислений.
Производительность одного транспьютера 
5
МОПС. Сеть из 110 транспьютеров давала такую же производительность, как один
процессор Pentium с тактовой частотой 550 МГц. Во всех вышеприведенных
программах используется стратегия организации параллельных вычислений, которая
называется SIMD (single instruction multi data). В случае SIMD
алгоритм выполняется тем быстрее, чем на большее число частей удается «разрезать»
данные. При этом желательно, чтобы каждая порция данных была обеспечена индивидуальным
вычислительным ресурсом, то есть процессором.
|
|
«Пропускная» схема распараллеливания на процессорах i860
Производительность процессоров Intel 80860XP и 80860XR (далее — i860) декларировались равной 80 и 100 МОПС соответственно. Задумывались они в качестве ускорителей для графических станций, но затем использовались как вычислители в сетях, аналогичных транспьютерным. Эти процессоры по сравнению с транспьютерами более производительные, но они не являются многозадачными.
Решение проблемы «проталкивания» данных по сети невозможно было унифицировать на системном уровне — приходилось каждый раз решать ее в Worker-задачах. Пример параллельной программы реализовал следующую стратегию работы с сетью:
Однократная подготовка данных для сети и рассылка по всем элементам.
В «корне» ожидаем возврата данных от элементов, установив интервал 1с. Если интервал исчерпан, то посылается сообщение об ошибке; в противном случае производится обработка результата и ожидание следующей порции данных.
Окончательная обработка результата в листинге 5.
|
|
Резервы повышения производительности для процессоров i860
Процессоры i860 обладают системой команд, ставшей прототипом для MMX- и SSE-команд современных процессоров. К сожалению, наивысшую производительность на такой архитектуре можно достичь, программируя на ассемблере.
Архитектура процессоров сбалансирована для задач с целочисленной арифметикой, с плавающей точкой и для графических приложений. Его составляющими являются все характерные для RISC-процессоров элементы: возможность организации конвейерных вычислений, модули, поддерживающие параллельные процессы, большая кэш-память для данных и кода. Одной из наиболее важных характеристик является размер внутреннего кэша для данных. Он составляет 8 Кбайт для процессора 80860XR и 16 Кбайт для 80860XP. Если в самом внутреннем цикле алгоритма идет обращение больше чем к 2048 элементам данных формата слова (4 байт), то происходит резкое увеличение скорости работы алгоритма в случае процессора 80860ХR. Для процессора 80860ХР количество «разрешенных» элементов будет в два раза больше.
В i860 для некоторых команд есть возможность работать с 32, 64 или 128 бит данных. Если вы хотите ускорить вычисления, выберите формат команд с как можно большим количеством битов одновременно обрабатываемых данных. Если алгоритм позволяет, необходимо использовать конвейерную организацию вычислений. В процессорах имеется двойная операция (dual operation instruction), которая позволяет за один такт выполнять операции сложения и умножения, а также сдвоенный режим (dual — instruction mode) выполнения операции с плавающей точкой и операции с целочисленной арифметикой.
В листинге 6 с подробными комментариями приведена ассемблерная подпрограмма, показывающая, как надо умножать две матрицы, чтобы получать максимально возможную на процессорах i860 производительность — 100 МОПС. В этой подпрограмме применены все известные способы повышения производительности для расчетов с плавающей точкой: конвейеризация, сдвоенные операции, операции умножения и сложения за один такт процессора.
Пример вызова подпрограммы … m_ab(a, b, c, 2, 1024, 2);…, где а и в — двухмерные массивы, с — одномерный массив.
|
|
«Пускач удаленных заданий» в клиент-серверных системах, построенный на сокетах
В связи с широким распространением локальных вычислительных сетей (ЛВС) задача создания параллельных вычислительных кластеров и разработка параллельных алгоритмов для них обрела «второе дыхание». Появилась возможность создания вычислительных кластеров, основанных на ЛВС. Для организации параллельных вычислений на кластерах используются системы пакетной обработки. Идеология пакетной обработки предусматривает разбиение задачи на части, работающие в течение небольшого периода времени, причем каждое задание выполняется независимо от других. Системы пакетной обработки обычно состоят из двух частей: «сервера запуска» (по одному на каждый компьютер или процессор) и диспетчера (один на сеть). «Сервер запуска» должен уметь запускать и завершать процесс по команде от диспетчера и уведомлять диспетчера о завершении процессов. Диспетчер занимается распределением задач по компьютерам (процессорам). Данные и программы хранятся на файловом сервере или могут копироваться на время работы программы на обрабатывающий компьютер. При использовании пакетной обработки изменения в программе минимальны — обычно это вынесение границ внешнего цикла в параметры программы. При этом не нужно использовать какую-либо библиотеку. Следовательно, программа может быть написана практически на любом языке программирования высокого уровня. Другим достоинством пакетной обработки является большая надежность: для работы системы достаточно надежной работы одного диспетчера. Система пакетной обработки позволяет производить выключение или добавление произвольного числа компьютеров во время работы. Еще одним достоинством системы является возможность одновременного выполнения нескольких заданий от разных пользователей.
Однако системы пакетной обработки позволяют получить значительное преимущество лишь при наличии в программе внешнего цикла с большим числом итераций — чтобы можно было равномерно загрузить все доступные вычислители. К недостаткам относится и сложность синхронизации между различными частями задания. Наиболее распространенные системы позволяют осуществлять планирование только на основе приоритетов, и при этом невозможно задать зависимости между заданиями, например: задание A можно выполнять после завершение задания B; при успешном завершении задания C не нужно выполнять задание D .
Далее рассмотрим реально существующую систему «Пускач удаленных заданий» — комплекс, состоящий из двух EXE-файлов, предназначенных для организации параллельной пакетной обработки на ЛВС под управлением операционных систем Windows 95/98/NT/2000 с протоколом TCP/IP и WinSock (вся обработка осуществляется в рамках стандартных протоколов). Комплекс свободен для использования (freeware), распространяется с исходным текстом. Предполагается, что обмен данными между EXE-файлами и вывод результатов работы сетевой программы осуществляются стандартными сетевыми средствами, например на сетевой диск.
Программу-сервер следует запустить на каждой ПЭВМ, где намереваются вести обработку. Эта программа обязательно должна иметь один параметр — уникальный номер порта (целое число, начиная от 500). Второй параметр (необязательный) — это время искусственной задержки в миллисекундах для обеспечения синхронизации между EXE-файлами (по умолчанию 2000). При постоянной эксплуатации данного комплекса рекомендуется внести запуск сервера (или серверов) в меню Start каждой ПЭВМ или оформить их как сервисы Windows NT/2000:
server.exe Н омерПорта[, ВремяИскусственнойЗадержки]
Программа-клиент должна находиться на ПЭВМ, с которой будет осуществляться управление пакетом. Она имеет следующие параметры:
- Имя файла со списком программ для запуска (может отсутствовать, по умолчанию "adr_best.cfg").
- Имя файла со списком IP-адресов ЛВС (может отсутствовать, по умолчанию "prm_best.cfg").
- IP-адрес ПЭВМ, на которой запускается клиент.
- Уникальный номер WinSock-порта для клиента.
- Время искусственной задержки (необязательный параметр).
Программа-клиент (диспетчер) управляется при помощи меню или кнопок, находящихся в верхней части окна. При помощи кнопки Запустить программу в сети или опции меню Начать обработку сетевая программа запускается на выполнение. Посредством кнопки или опции меню Сохранить параметры можно записать в файлы изменения, произведенные в списках программ с параметрами для запуска и адресов с номерами портов.
Строка списка программ для запуска состоит из имени EXE-файла с сетевым путем и параметрами через разделитель. Строка списка IP-адресов состоит из IP-адреса вычислительного узла сети и номера WinSock-порта, уникального в рамках одной ПЭВМ. Списки можно редактировать из программы клиент: клавиша Ins — вставить новый элемент в список; клавиша Del — удалить элемент. Допускается редактирование списков любым автономным средством как текстового файла. На рис. 1 приведена форма программы-клиента с заданием на запуск трех одинаковых стандартных программ калькулятор на двухпроцессорной ПЭВМ с IP-адресом 128.4.5.121 и портами 501 и 502.
Выход из программы-клиента осуществляется нажатием соответствующей кнопки или выбором опции меню.
Программа-сервер стартует в минимизированном виде. Для завершения работы необходимо, находясь в ее окне, нажать правую клавишу мыши и выбрать опцию всплывающего окна close или нажать Alt-F4. Фрагменты кода клиента и сервера для Borland Delphi 5.0 Enterprise представлены в листинге 7.
Приложения строятся на сообщениях Windows, которые они направляют сами себе при помощи функции PostMessage, а также на компонентах TClientSocket и TServerSocket — для общения друг c другом. К достоинствам данной системы можно отнести небольшой размер и простоту кода. Недостатков у нее намного больше. Во-первых, не поддерживается возможность удаления запущенных заданий. Во-вторых, при одновременном обращении нескольких серверов к клиенту (диспетчеру) нарушается его функциональность, что в некоторых случаях приводит к ненадежности работы системы. В-третьих, если время обработки одного узла было меньше времени загрузки вычислительной ЛВС, происходит потеря вычислительных узлов, так как работают только компьютеры с IP-адресами, которые стоят первыми в списке. И наконец, в-четвертых, безопасность (в смысле доступа к ресурсам) ничем не обеспечивается.
|
|
Применение «нитевых» технологий для алгоритмов с большой вычислительной трудоемкостью
Если вы создаете интерактивное приложение с повышенными требованиями к вычислительным ресурсам и хотите, чтобы его формы не зависали и перерисовывались в реальном режиме времени, или если на вашей ПЭВМ несколько процессоров, или если вы создаете клиент-серверное приложение (все в операционных системах Windows), то рекомендуется делать приложение многопоточным, или многонитевым (терминология еще не устоялась). В случае средства разработки Borland Delphi 3.0 и его более поздних версий подобная функциональность достигается при помощи класса TThread. В этом пакете в опции меню File/New имеется мастер Thread Object, который облегчит вам создание многопоточных приложений.
Для операционных систем Windows 95/98 многопоточные приложения лишь эмулируют параллельное выполнение, а системы Windows NT и Windows 2000 поддерживают истинную параллельность выполнения. Если на вашей ПЭВМ два процессора и установлена операционная система Windows NT или 2000, то вполне вероятно, что приложение, использующее многопоточность, будет выполняться в два раза быстрее (и так далее).
Техника использования класса TThread проста: вы должны породить наследника от него (возможно, при помощи эксперта из репозитария Delphi):
type M1 = class(TThread) … g: byte; … protected procedure Execute; override; end;
Метод Execute этого класса является базовым для присоединения какой-либо функциональности, необходимой для вашего объекта. Если при создании экземпляра объекта в методе Create используется параметр false, метод Execute немедленно получает управление:
… var М1: М1; … М1:=ТМ1.Create(false); …
Если при создании экземпляра объекта в методе Create используется параметр True, вы можете сначала переопределить какие-то поля вашего объекта, а затем при помощи метода Resume передать управление методу Execute и ждать окончания выполнения действий при помощи метода WaitFor:
… M1:=M1.Create(True); … М1.g:=5; … M1.Resume; … M1.WaitFor; …
Вот, собственно, и все, что необходимо знать для начала работы с многопоточными приложениями.
Класс TThread имеет ограниченную функциональность — в основном ограниченную взаимодействием с VCL-компонентами, которые не являются потокобезопасными. Если вы попытаетесь обращаться к одним VCL-компонентам из разных потоков (например, к компоненту ProgressBar), то скорее всего возникнут проблемы, так как синхронизация обращения к таким компонентам не поддерживается. TThread не дает никаких методов взаимодействия с другими параллельными процессами (потоками). Этот класс удобно использовать, когда в программе малое количество статически создаваемых потоков, взаимодействующих с основным VCL-потоком и не взаимодействующих между собой. Если же задача раскладывается на достаточно большое число динамически создаваемых, уничтожаемых и взаимодействующих между собой потоков, то использование TThread становится сложным и ненадежным. Непосредственное же использование разнообразных низкоуровневых средств синхронизации Win32 трудоемко, громоздко и чревато ошибками (хотя и более эффективно). Низкоуровневые возможности параллельного программирования, предоставляемые платформой Win32 (операционные системы Windows 95/98/NT/2000), — это потоки, сигналы, мьютексы, семафоры, критические секции, сообщения. Рекомендуется также использовать вспомогательные библиотеки, например библиотеки классов Gala (gurin@mail.tomsknet.ru) для Delphi, которая позволяет программировать в терминах асинхронных параллельных процессов и их взаимодействий почти столь же удобно, как в языках Оккам [1] и Ада [2], используя асимметричное «рандеву» в качестве принципа синхронизации. Библиотека свободна для использования (freeware), распространяется с исходным текстом (см. http://www.dps.aeed.tpu.edu.ru/gurin/gala/index.htm).
Для иллюстрации применения библиотеки предположим, что перед нами стоит задача выделения сигнала на фоне помехи. На рис. 1 в качестве примера приведены три функции. Истинная функция обозначена красной линией, помеха, наложенная на истинную функцию, — черным пунктиром, а наблюдаемый сигнал, полученный в результате суммирования помехи и истинного сигнала, — сплошной синей линией. Задача состоит в том, чтобы по наблюдаемому сигналу и на основании априорных знаний об истинном сигнале (а именно на основе статистической информации об истинных сигналах) определить возможные значения истинного сигнала либо уменьшить количество допустимых значений истинного сигнала, если диапазон возможных значений известен заранее.
Иными словами, рекуррентная
процедура вычисления
апостериорной (условной)
вероятности, то есть полученной в
результате расчетов, появления цепочки
значений
в
полосе 
является
реальным примером сложного
вычислительного алгоритма [3] и позволяет
показать механизм распараллеливания,
называемый MIMD (multi
instruction multi data).
Пусть имеется полоса «сигнал/шум» 
,
где 
, 
,
которая представляет собой целочисленную решетку 
,
, 
,
где А – множество, А = {0,1,...n-1}, и каждому элементу 
приписана априорная вероятность 
,
то есть для каждого 
задано априорное
распределение {, k=0,1,...n-1}.
В качестве модели Mr
будем
рассматривать r-граммную
цепь Маркова. Метод заключается в
рекуррентном подсчете вероятностей всех (r-1)-грамм
значений для каждой точки приложения, где r
— граммность
фильтра. Далее от вероятностей (r-1)-грамм
происходит переход к вероятностям
отдельных значений. В результате работы
получаются упорядоченные по убыванию
вероятностей колонки значений. Затем
производится собственно фильтрация, в ходе
которой на основании колонок 
строятся колонки 
меньшей глубины,
являющиеся результатом работы алгоритма.
Введем наборы прямых переменных 
и обратных
переменных 
(
), где
l — длина
обрабатываемого участка. Через l0
обозначим начало
участка. Числа i0,...,ir-2
пробегают все
множество возможных значений. Таким
образом, общее число введенных переменных (емкостная
сложность алгоритма) составляет 2(l-r)×
zr, где z
— количество
возможных значений. Алгоритм состоит из
двух этапов — прямого хода и обратного хода.
Полагаем 
для каждого набора (i0,...,ir-2),
где 
пробегают все
возможные значения из соответствующих
колонок. По совокупности значений 
вычислим
совокупность значений 
по формуле
, (1)
где 
.
Полагаем 
для каждого набора (i0,...,ir-2),
где 
.
По совокупности
значений 
вычислим
совокупность значений 
по формуле
, (2)
где 
.
Как только значения прямых и обратных переменных вычислены, вычисляем для
всех 
и всех значений наборов (i0,...,ir-2)
вычисляем значения переменных
, (3)
где 
.
Затем для каждого 
нормируем
полученные значения их суммой по всем
наборам (i0,...,ir-2)
. (4)
Из совокупности формул (1-4) видно,
что алгоритмы прямого и обратного хода
могут выполняться параллельно, так как
переменные, входящие в формулы
и ,
не пересекаются.
Кроме того, до середины участков,
параллельно вычислив
и
и организовав
обмен данными между параллельными
процессами, можно вычислять не только
и ,
но и
непосредственно 
для прямого и 
для обратного хода
соответственно. Эта присущая алгоритму
параллельность позволяет надеяться на
сокращение времени обработки участка
максимум в четыре и минимум в два раза.
В программе может быть только один объект, порожденный от класса TGalaTheater, который позволяет объединить процессы в группы-кластеры. Предполагается взаимодействие процессов внутри группы. Процессы могут взаимодействовать при помощи класса «сигнал» TGalaSignal, класса «сообщение» TGalaEvent — наследника класса TGalaSignal, вспомогательных классов, таких как «замок» TGalaLatch, инкапсулирующий понятие критической секции, и TGalaLog — наследника TGalaLatch с расширенной функциональностью, мьютексов TGalaMutex, семафоров TGalaSemaphore, нотификационного класса TGalaChangeNotification, классов организации очередей TGalaDeque, класса «контейнер» TGalaContainer и канала между контейнерами TGalaContainerChannel, а также класса каналов между процессами TGalaProcessChannel:
… TGalaTheater.Create; //создание экземпляра объекта TGalaheater.NotificationWindow := Handle; //предоставление ему // дисплейного контекста …
Параллельный процесс должен быть наследником класса TGalaProcess, который имеет абстрактный виртуальный метод Execute (аналогично классу TThread). В нем описывается алгоритм функционирования процесса. TGalaProcess инкапсулирует поток (thread) Win32 без использования Delphi-класса TThread и имеет следующие методы: для завершения процесса; для реализации действий при нормальном и принудительном завершении; для изменения приоритета процесса; для приостановки, запуска и приостановки на заданный промежуток времени; для взаимодействия с основным VCL-потоком, с другими параллельными процессами и с разделяемыми ресурсами; для отладочной трассировки:
…
TprocessML=class(TgalaProcess)
…
procedure Execute; override;
end;
…
MoveOnLeft: TProcessML; //создание экземпляра процесса
EventEndHalfRight, EventEndHalfLeft: TGalaSignal; //создание
//экземпляров объекта TGalaSinal для уведомления о факте
//выполнения половины работы
…
procedure TProcessML.Execute;
begin
…
{ Ждет сигнала от процесса TProcessMR }
Wait(EventEndHalfRight, TimeWaitInput);
…
end;
Для ускорения решения задачи
вычисления апостериорной (условной)
вероятности появления цепочки
значений
в
полосе ,
необходимо, чтобы
процедуры прямого и обратного хода
выполнялись параллельно, являясь, возможно,
наследниками TGalaProcess.
Кроме того, метод Execute
для
каждого
наследника должен состоять из двух
функциональных частей — независимого
вычисления переменных прямого и обратного
хода до середины обрабатываемого участка,
затем ожидания завершения выполнения
конкурирующего процесса, обмена с ним
данными, продолжения независимых
вычислений переменных
и
с одновременным
вычислением переменных
и .
Синхронизация
работы между процессами прямого и
обратного хода осуществляется при помощи
следующих классов: TGalaSignal,
который позволяет
дождаться окончания выполнения половины
работы конкурирующим процессом, и класса TGalaProcessChannel,
отвечающего за
обмен данными между процессами:
procedure TProcessMR.Execute;
begin
…
{ Сигнал "левому" }
with MF do
(EventEndHalfRight as TGalaEvent).SetState(True);
…
end;
Способ построения обмена таков. Процесс TProcessML в методе Execute после обработки половины участка ожидает сигнала от процесса TProcessMR. Процесс TProcessMR в методе Execute после обработки половины участка посылает сигнал процессу Process. При асинхронных вычислениях потенциально существует два способа обмена данными между конкурирующими процессами — объявление данных как глобальных переменных или обмен вычисленными данными посредством каких-либо каналов. Первый способ — более простой для программирования, но необходимо соблюдать осторожность, поскольку обращение к одним и тем же данным из разных процессов может вызвать коллизии. Второй способ требует дополнительного программирования. Способ определения канала, при использовании пакета Gala, состоит в следующем: в передающем процессе определяется переменная типа «канал»:
… ChannelCT: TGalaProcessChannel; …
и реализуются два метода: один — для проверки возможности передачи (необязательный), другой — для организации передачи данных:
procedure TProcessreadInputFile.GetCT(d: Pointer); var i, j, k: integer; begin SetLength(PText(d)^, Length(CT), HowManyCharsInSector); for i:=Low(PText(d)^) to High(PText(d)^) do begin k:=OffInCT; for j:=Low(PText(d)^[i]) to High(PText(d)^[i]) do begin PText(d)^[i, j]:=CT[i, k]; Inc(k); end; end; end; function TProcessreadInputFile.CanCT: boolean; begin Result:=(OffInCT+HowManyCharsInSector)<=MinLineCT; end;
В принимающем процессе определяется метод приема данных:
procedure TProcessML.GetData;
var
p: TGalaProcess;
User: TProcessReadInputFile;
begin
with MF do
p := TProcessReadInputFile(InputFile);
if Assigned(p) then
begin
User := p as TProcessReadInputFile;
try
CT:=nil;
while CT=nil do
User.ChannelCT.Send(Self, @CT, TimeWaitInput);
{ Обработка вариантного массива }
VG:=nil;
while VG=nil do
User.ChannelVariantsG.Send(Self, @VG, TimeWaitInput);
except
on E: EGalaProcessWasTerminated do
Terminate;
end;
end;
end;
В качестве дополнительных компонентов в проекте используется библиотека RXLib 2.75, дистрибутив которой можно найти на сайте http://www.rxlib.com/.
Необходимо отметить, что если мы откажемся от распараллеливания задачи вычисления апостериорной вероятности до середины участка, то проект значительно упростится. В этом случае можно обойтись стандартными средствами многопоточной обработки, предлагаемыми в Delphi. Увеличит ли такое решение время решения всей задачи? Это зависит от взаимосвязанных решений параллельного программирования. Если, например, применить SIMD-стратегию построения алгоритма (параллельная обработка участков) и увеличить в два раза количество вычислительных узлов, то время решения простой и сложной задачи будет одинаковым.
|
|
Заключение
Рассмотрев спектр программ для различных аппаратных платформ, можно увидеть, что при организации параллельного выполнения алгоритмов выделяется унифицированная часть, связанная с параллельным программированием и присущая всем платформам. Например, клиент-серверная технология применяется как для транспьютерных вычислительных кластеров, так и для различных распределенных вычислений в ЛВС. Однако недостатки клиент-серверных приложений, показанные для транспьютерных сетевых программ, по-видимому, будут свойственны и другим вычислительным кластерам.
При проектировании параллельных алгоритмов, выборе стратегии распараллеливания (например, SIMD или MIMD), надо стремиться не только к минимально возможному времени выполнения задачи, но и к максимальной технологичности (простоте кода с точки зрения кодирования, отладки и эксплуатации) и к надежности параллельного алгоритма. Для достижения этих целей значительную роль играет выбор аппаратной платформы, так как не все архитектурные и системные решения позволяют строить простые и надежные параллельные приложения.
Без сомнения, программирование параллельных алгоритмов теперь и особенно в будущем является важной составной частью искусства программирования, наряду с вопросами организации интерфейсов, баз данных и т.п. Разработка международных стандартов для взаимодействия между параллельными процессами остается актуальной. Среди имеющихся прототипов, таких как PVM (parallel virtual mashine), MPI (message passing interface) и OpenMP (общая память) и др., до сих пор продолжается острая конкурентная борьба. Короче говоря, стандарты организации параллельных алгоритмов не устоялись — это, возможно, станет темой для следующей статьи.
|
|
Литература
Джоунз Г. Программирование на языке Оккам. М., Мир, 1989.
Вегнер П. Программирование на языке АДА. М., Мир, 1983.
Рабинер Л.Р. Скрытые марковские модели и их применение в избранных приложениях при распознавании речи. Обзор-ТИИЭР, т. 77, № 2, 1989.
КомпьютерПресс 3'2001
