автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Организация конвейерной связи модулей в пакете программ

ЛЕНИНГРАДСКИЙ ОРДЕНА. ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ВЕРШИГОРА Руслан Владимирович

УДК 681.3

ОРГАНИЗАЦИЯ КОНВЕЙЕРНОЙ СВЯЗИ МОДУЛЕЙ В ПАКЕТЕ ПРОГРАММ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

/ > . ) / ^ ~

Ленинград . 1991

Работа выполнена на кафедре исследования операций ыатематико-механического факультета Ленинградского ордена Ленина и ордена. Трудового Красного Знамени государственного университета

Научный руководитель: доктор ©юнко-математических наук,

профессор

Романовский Иосиф Владимирович

Официальные оппоненты: доктор технических наук,

профессор

Ыухачева Элита Александровна

кандидат физико-математических наук, старший научный сотрудник Даугавет Ольга Карловна

Ведущая организация: Вычислительный Центр АН СССР

Защита состоится "24" _1991 г. в

часов на заседании специализированного, совета К 063.57.54 по присуждению ученой степени кандидата физико-математических наук в Ленинградском государственном университете по адресу: 198904, г.Ленинград, Петродворец, Библиотечная площадь, 2, математико-механический факультет ЛГУ, зал заседаний Ученого Совета.

С диссертацией можно ознакомиться в научной библиотеке университета (г.Ленинград, Университетская набережная, д. 7/9).

Автореферат разослан "22? _1991 г.

Ученый се1фетарь специализированного Совета

А.А. Кубанский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теыы. Для повышения производительности универсальных ЭВМ наряду с непосредственным использованием многофункциональной аппаратной части необходимо предусмотреть параллельность обработки. В то же время использование при программировании алгоритмических языков и последовательных математических алгоритмов затрудняет внедрение идеи параллелизма.

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

- проектирование метода управления параллельно-конвейерными моделями вычислений и его апробация на сложных системах типа пакета программ;

- создание языковых конструкций для реализации сопрограммного механизма на компьютерах совместимых с PDP-11 или IBM PC и программного канала обмена информацией меццу сопрограммными модулями;

- изучение вопроса интеграции задач в пакете с добавлением режима интерактивной обработки;

- построение пакета программ линейного программирования с использованием новых инструментальных средств;

- определение эффективности различных методов оценки столбцов в алгоритме симплекс-метода.

Научная новизна. Расширена конструкция вызова функции в языках программирования до сопрограммной схемы. Созданы средства моделирования параллельно-конвейерных программ. Разработан параллельно-конвейерный алгоритм симплекс-метода и его различных этапов. Изучен вопрос проектирования диалога для пакетной организации программ .

Методика, выполнения исследования. При разработке языковых средств рассматривались различные подхода к организации сопрограмм, которые предлагались ранее в работах Д.Е.Кнута, Т.Пратта, П.А.Байл-са, Б.А.Новикова. Аппарат для построения параллельно-конвейерных алгоритмов опирается на метода проектирования операционных систем UNIX и RSX-11, изложенных в работах С.Кейслера, П.Кейлингерта, А.Шоу, М.Белякова и-других. Значительный опыт разработчиков пакета ЯП ЛГУ Л.М.Брэгмана и С.С.Сурина

был использован при создании настоящего пакета программ. Идеи И.В.Романрвского были положены в основу комплексирования модулей в пакете. Исследование^математических алгоритмов данного пакета проводились на базе известных работ Д.Гольдфарба, Дж.Рида, М.Хар-рис, П.Толла.

Практическая ценность. Предлагается вариант реализации таких программных средств как сопрограммы и каналы, а также метод управления этими объектами. На полученной инструментальной базе можно моделировать параллельно-конвейерную обработку, примером чему и является пакет программ "ЬР га1п!/зШйу". Пакет содержит оригинальный метод оценки столбцов в известном алгоритме симплекс-метода и может применяться как для обучения, так для решения практических задач линейного программирования.

Апробация работы. Результаты работы докладывались и обсувда-. лись на 10 и 11 Всесоюзных симпозиумах "Системы программного обеспечения решения задач оптимального планирования" (Нарва-Иыэсуу, 20-27 марта 1988 г. и Кострома, 21-29 мая 1990г.), на Всесоюзной школе-семинаре "Проблемы социально-экономического развития крупных городов" (Репино, сентябрь 1988г.), на 6 научной конференции "Метода математического программирования и программное обеспечение" (Свердловск, 27 фев. - 3 марта 1989г.), а также на научных семинарах лаборатории исследования операций института математики и механики ЛГУ им. В.И.Смирнова. Проведено тестирование программного • пакета, результаты которого приводятся в §5.1ч Составлено подробное руководство (Приложения 1 и 2) пользователя пакета, которое служит документом к программному обеспечению. .

Публикации. Основные результаты диссертации отражены в статье [2] и тезисах конференций И], [3-6].

Структура и объем работы. Работа изложена на 138 страницах и состоит из шести глав (первая глава - "Введение"),"списка литературы , включающего в себя 77 названий, и двух приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В-третьих, изменения в организации связи модулей обуславливают новую структуру управления. Для ее анализа конвейерный процесс рассматривается как последовательность событий обмена данными через каналы (в т.ч. и параллельных событий .над разными каналами). Признаки событий отракают текущее состояние объекта управления -сопрограммы с подключенными к ней каналами. Изменение зтих признаков и составляет суть системы управления, так как характеризует переход задачи из одного состояния в другое.

Введенные инструментальные средства служат системной базой для построения пакета программ. Автор использовал опыт проектирования пакета ЛП ЛГУ при формировании набора сопрограммных модулей, решающих задачу линейного программирования (ЛП).

Последняя часть "Введения" посвящена различным характеристикам оригинального пакета программ "1Р пйМ/зШйу" и рассмотрению интерактивного реяжма управления решением задачи ЛП.

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

Сопрограммный механизм обеспечивает две новые возможности управления - частичное выполнение тела процедуры и деление на подпрограммы без их подчиненности одной из другой.

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

данными и координации логических событий.

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

Функции сопрограммного механизма - инициализации, возобновления и возврата - удобно представить как действия над записями активаций (в литературе для таких записей применяются также термины кадр или фрейх вызова). -Запись активации формируется на стеке при вызове процедур! и полностью описывает ее текущее состояние. Она включает в себя пакет фактических параметров,- адрес возврата, сохраняемые регистра и локальные переменные. Подробно структура записей и преобразования их связей при переходе к сопрограммному механизму описываются в §2.1.

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

В §2.2 сравнивается несколько подходов к настройке сопрограммного механизма в современных языках программирования. В варианте автора для языка Си удалось провести стратегию независимости и равноправия сопрограмм по отношению к создателю и друг другу.

Любое новое средство в языке должно иметь преемственность в стиле языка и базироваться на его стандартных возможностях. В §2.3 подробно рассматривается семантика вызовов служебных функций и их влияние на фреймы активных сопрограмм. Для иллюстрации техники-использования сопрограмм приводится пример программы на языке Си.

Эффективность предлагаемой версии заключается в минимальном использовании дополнительной памяти на организацию сопрограммной связи (только для указателей на запись активации) и возможности управления локальными областями, расположенными на- стеке. Время возобновления сопрограммы - по длине кода и набору команд - эквивалентно времени затрачиваемому на вызов стандартной функции в языке Си, которое, по мнению авторов языка, весьма мало. Мобильность схемы реализации состоит в возможности построения дерева сопрограмм произвольной структур« с возобновлением на любом уровне.

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

Для- пользователя данная версия реализации программных каналов позволяет:

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

- проектировать объем канала и заголовки сообщений, исходя из специфики задачи;

- реализовать конвейер программ над каналом обмена;

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

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

Механизм выделения/освобождения сообщений из общей области при записи/чтении подобен управлению динамической памятью (heap). Этот механизм управления необходим в тех случаях,, когда выделение и освобождение памяти может потребоваться в произвольные моменты времени выполнения. Применительно к каналу можно сказать, что размер области для записи или чтения действительно произвольный по отношению к фиксированным точкам взода/вывода. Управление сообщениями канала просто сводится к отметке занятых сообщений (при записи) и стирании маркеров при чтении. Появляется и дополнительная возможность - добавить сообщения в канал для следующего активного модуля, используя память "свободных" сообщений.

Система функций управления каналом (в §§3.2-3) реализует апробированные схемы: постраничное распределение памяти (здесь: сообщений), прямой доступ к сообщениям через их индексы и управление heap с помощью маркеров.

Отметим, что представляемая система функций доступа - cheqch (чтение), ínvch ("добавление), set eft. (запись) - непротиворечива и полна. Рассмотрим различные их сочетания: 1. итерация CtTEQOH*, ШСБ*, SETCH*,

2. фильтрация СНЕООН-БЕТСН и ИГ/СН-БЕТСН,

3. очистка СИЕОРН-ШСН,

4. пустая операция ШСН-СНЕОРН,

5. запись БЕТСН-СНЕОСН,

6. добавление БЕТСН-ШУСЗ.

Заголовки операций 1 - 6 частично поясняют порядок вызова функций доступа в программе. Итерация чтения из канала необходима, если канал в программе служит входным для нескольких модулей, которые могут выполняться в параллельном режиме. Операция подключения к каналу используется для выходного канала в случае, когда модуль добавляет свою информацию в канал. Одйако, в параллельном режиме свободный остаток канала, который выдает 1Н7СН, является критическим для одновременно птнущщ процессов. В критическом интервале запись сообщения с одним и тем же индексом ведет к ошибке. Вызов БЕТСН для записи в режиме добавления применяется очень часто, так как за один вызов в канал заносится только одно сообщение.

Операция 2 является также стандартной для конвейера: модуль читает данные из канала, преобразует их или оценивает, а затем передает преемнику. Повторение в 3 двух различных способов подключения к каналу ведет к его очистке после Ш7СН, поэтому в систему функций не введена специальная операция для освобождения канала.

Пустая операция, хотя формально и выподнима, но чревата потерей введенных до вызова ШЧСЕ сообщений, поэтому функция СНЕОСН выдает как результат (-1), не выполняя никаких действий. Операции 5 и 6 дополняют 2 в конвейерном режиме -- это возможный порядок при переходе от модуля к модулю.

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

В главе 4 вводятся характеристики состояния процесса, которые объединяются в объект типа связь. Данный объект является статическим носителем управления, а операции над ним (изменение состояния) отражают собственно процесс управления. Проектируемая связь должна удовлетворять следующим требованиям:

- определять текущее состояние активного процесса (подзадачи);

- отражать в целом ход выполнения алгоритма;

- согласовывать переход от одного процесса к другому;

- адаптироваться к форме представления модулей и интерфейса между ними.

Компонента current в структуре связи служит в качестве характеристики текущего активного процесса. Она принимает значения из множества ссылок (идентификаторов) готовых к исполнению процессов. Изменение current определим как логическое событие перехода от одного процесса к другому. Программная операция resume, которая возобновляет дремлющую сопрограмму, является операцией над current с точки зрения управления всем процессом вычислений.

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

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

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

Для разрешения подобных конфликтов введем дополнительную управляющую переменную signal, значения которой трактуем как ответ не запрос, (сигнал на входе режима). Такими простыми по смыслу значениями могут быть сигналы типа READY или ERROR. Анализируя прохождение сигнала по цепи (передачу этого значения от процедуры к про цедуре), можно успешно контролировать завершение каждого режима.

Метод управления объектом связи иллюстрируется в данной главе на примере алгоритма симплекс-метода. Значения компонент приведены в таблицах, а на рисунках изображаются различные схемы объединения в конвейер режимов отдельных модулей. В §4 .3 данный подход к vnps влению процессами сравнивается с известными моделями типа сетей Петри, схем HIPO и других, которые приняты для описания параллель но-конвейерных связей.

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

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

В пятой главе предлагается метод оценки небазисных столбцов, основанный на вычислении веса столбца с учетом текущих базисных значений. Он представляется перспективным при использовании блочных итераций, так как формулы пересчета веса столбца не зависят от индекса ведущего элемента, получаемого на предыдущей итерации (индекс ведущей строки необходим в известных методах оценки Steepest-edge и Devex).

Реализация метода состоит в следующем:

а. вместе с вычислением базиса двойственной задачи - вектора

zT=Cg-B~1, мы вычислим и вектор веса :

wgT= хт В-\ где х ="( Vе >0

I О, ■ иначе

б. при оценке J-то небазисного "столбца вычисляем, как обычно, относительную оценку dj и дополнительно вес столбца:

I. = i > 0]

Заметим, что при вычислении веса учитываются только положительные компоненты скалярного произведения wgT • а^.

в. е оазис вводится допустимый столбец а^, на котором достигаете? максимум отношения \dj\/Tj (ясно, что 2' > 0).

Анализ результатов тестовых задач по проверке эффективности данного метода оценки позволяет сделать следующие выводы: - число замен при блочном подходе несколько выше, чем если вводит! в базис по одному вектору за просмотр (при том же, разумеется, методе оценки). Это, однако, с избытком компенсируется числом просмотров;

- по числу замен в базисе предлагаемый метод оценки эквивалентен методу Steepest-edge (±10%), как в блочном варианте, так и при размере блока 1;

- предлагаемый метод требует меньших затрат на вычисление и хранение весовых коэффициентов столбцов, что предпочтительнее при "блочном" варианте;

- особенно эффективен отбор по вышеприведенным формулам при замене в базисе искусственных переменных. Отметим, что решалась не отдельная задача минимизации числа искусственных переменных, а только масштабировалась целевая функция с положительным коэффициентом меньше 1;

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

Отдельной задачей в состав пакета входит.процедура перепостроения базисной матрицы. Она вводится для уменьшения ошибок округ ления при операциях умножения матрица-вектор и сокращения числа ненулевых элементов в той или иной форме представления. Алгоритм из §5.2 работает со "скелетом" базисной матрицы, то есть учитываются только позиции ненулевых элементов, но не их численные •величины. Однако, подобный недостаток компенсируется, во-первых, сохранением диагонали при перестановках, г, во-вторых, небольшим объемом исходной информации. Действительно, так как строки и столбцы переставляются симметрично, то сохраняются ведущие элементы на диагонали из исходного порядка. В свою очередь, этот порядок можно предопределять до входа в алгоритм, исходя из критерия устойчивости.

В главе б подробно рассматриваются принцип выделения подзадач к их интеграция в пакете.В ней на примере подзадачи подготовки данных PPD раскрывается взаимодействие задач в пакете через специальные двоичные файлы. Подзадача PPD производит преобразование исходных данных к двоичному формату. Такой подход эффективен по следующим причинам:

- отпадает необходимость в преобразованиях данных при операциях чтения или записи;

- это решение ведет к сокращению объема основной задачи за счет процедур обслуживания текстовых файлов;

- добавляется возможность адаптировать стандартное внешнее представление к форме, принятой в конкретном пакете и легко варьировать формы внешнего представления;

- предварительная обработка входных данных может включать в себя

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

В пакете "LP mini" используются две формы упаковки столбцов исходной матрицы - с одним и двумя уровнями индексов (их формат подробно описан в §6.1). Кроме того, файл во внутренней двоичной форме применяется для сохранения промежуточных состояний задачи после каждого перепостроения или по требованию пользователя пакета.

Диалоговая часть пакета имеет свои особенности сопряжения с исполняемой задачей, которые рассматриваются в §§6.2-3. Кроме того, интерактивная обработка данных дает пользователю средства для наблюдения за ходом вычислений и оперативного изменения алгоритма в исключительных ситуациях. Диалоговые средства основной задачи пакета включают следующий набор операций:

- получение таблицы результатов итерации или задачи и сохранение их в файле вывода;

- управление каждым из этапов итерации;

- сохранение и восстановление решения с текущей точки;

- изменение небазисных столбцов матрицы задачи и набора констант-ограничителей (например, порогов для проверки вещественных значений с плавающей точкой на 0) без прерывания вычислений.

Каждая операция диалога - от вызова нужной команды до реакции задачи на запрос - строится на трех взаимосвязанных компонентах:

1. системных функций поддержки связи с основной задачей;

2. функций запросов, на которых строится сеанс диалога;

3. программных реакций на выставленные ключи.

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

В заключении главы рассматривается пример команды диалога "Итерация" и ключи ее управления. На данном примере проектировщик диалога может проследить процесс формирования компонент 1 - 3 и определить требования к ним.

Для пользователя пакета работа включает в себя сравнительные характеристики данного пакета и известного программного продукта LPX88. Приложения 1 и 2 к диссертации являются практическим руководством к пакету "LP mini/study" и содержат отдельно формы таблиц ввода/вывода.