авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ

ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

И ТЕЛЕКОММУНИКАЦИЙ

МЕЖДУНАРОДНАЯ АКАДЕМИЯ ИНФОРМАТИЗАЦИИ

АКАДЕМИЯ ИНФОРМАТИЗАЦИИ ОБРАЗОВАНИЯ

ОАО «ВОЛГАТЕЛЕКОМ»

ПРИВОЛЖСКИЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ

ИНСТИТУТ ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ

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

НОВЫЕ ИНФОРМАЦИОННЫЕ

ТЕХНОЛОГИИ И СИСТЕМЫ Труды VI Международной научно-технической конференции Часть 2 Proceedings of the Sixth International Conference of Science and Technology NEW INFORMATION TECHNOLOGIES AND SYSTEMS (NITS’2004) Penza, Russia, June, 17 - 19, 2004 ПЕНЗА 2004 УДК 681.3.002: 32.973.233: 658.5 Н 76 Новые информационные технологии и системы: Труды VI Международной научно-технической конференции – Ч. 2. – Пенза, ПГУ, 2004 г. – 213 с., ил. – 82, табл. – 17, библиогр. – 98 назв.

В сборнике представлены материалы докладов, сделанных на VI Международной научно-технической конференции «Новые информационные технологии и системы» («НИТиС-2004»), проводимой Международной академией информатизации, Академией информатизации образования и Пензенским государственным университетом совместно с ОАО «ВолгаТелеком». Доклады охватывают широкий спектр проблем в области новых информационных технологий в производстве, управлении и образовании, теории и практики использования современных информационных технологий для построения высокопроизводительных вычислительных комплексов, систем и сетей различного назначения. В докладах рассмотрены современные технологии и системы хранения и обработки данных, приведены результаты работ по созданию аппаратно-программного обеспечения информационно-вычислительных систем, систем управления и интеллектуальных систем. Изложен опыт работ в области моделирования информационно-вычислительных систем и применения математических методов в информатике.

Редакционная коллегия:

В.И. Волчихин, Н.П. Вашкевич, А.В. Никишин, И.В. Огнев, О.М. Брехов, В.П. Кулагин, Э.К. Шахов, П.П. Макарычев @ Издательство Пензенского государственного университета, МОДЕЛИРОВАНИЕ ИНФОРМАЦИОННО ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ, ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ В ИНФОРМАТИКЕ М.Ю. Бабич Россия, Пенза, ОАО «НПП «Рубин»



ТЕХНОЛОГИЯ МОДЕЛИРОВАНИЯ ИНФОРМАЦИОННОЙ СРЕДЫ СЛОЖНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ При разработке сложного программного обеспечения (ПО) многих автоматизированных систем возникает необходимость в проведении тщательной проверки их функциональных возможностей на имитационных моделирующих стендах задолго до установки программного и технического обеспечения систем на объектах автоматизации. Однако в процессе создания такого ПО часто возникают следующие проблемы: входная информация программ не является статичной, а зависит от времени;

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

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

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

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

Одним из подходов к решению подобных проблем является технология создания модели информационной среды ПО и имитации возникновения информации в созданной модели[1].

Под информационной средой ПО будем понимать =X, R, F, где X – информация, циркулирующая на объектах автоматизации;

R – множество отношений и ограничений, определенных на X;

F – множество функциональных зависимостей. F={fi}, fi : XX. ПО воспринимает информацию X через множество атрибутов ATR={aj}. Тогда X=Aj, где Aj – множество значений атрибута aj. Параметры информационной среды зависят от времени, то есть X=X(t), R=R(t), F=F(t) и, следовательно, =(t).

Моделью информационной среды будем называть /=X/, R/, F/, P, где X/, R/, F/ - некоторые подмножества множеств X, R, F. Р является множеством вероятностей возникновения значений входной информации ПО. Каждый элемент P определяется вероятностью возникновения (генерации) атрибута aj, и вероятностью генерации значения атрибута aj, то есть вероятностью генерации элемента из Aj. Первую вероятность обозначим через paj, а вторую через px, где xAj. Следовательно, P(t) есть множество пар{paj(t), px(t)}, где ajATR и xAj.

ПО определяет программные функции Prog: XY, где Y – выходная информация, хранимая в базе данных информационной системы, выдаваемая операторам либо техническим устройствам, подключенным к компьютерам.

Так как время для ПО всегда дискретно, то для любых tn, tm, где tn tm, можно построить цепочку логических зависимостей:





/ (t0).../ (tn).../ (tm). (1) Здесь t0 – начало работы ПО. Для проверки работоспособности ПО идеально, если существует такое время t**, для которого строится цепочка логической зависимости /(t0).../ (t**) и выполняются тождества:

X=Xti, R=Rti, F=Fti. Здесь Xti, Rti, Fti - подмножества X,R,F на интервале [ti, ti+1]. Обозначим Xt=Xti, где [ti, ti+1]=[t0, t]. Однако такая проверка невозможна. Практически проверка функционирования ПО завершается для некоторого времени t* t**, для которого Xt*X.

Под имитацией возникновения информации в модели информационной среды понимается построение на имитирующем стенде цепочек (1) некоторым технологическим программным обеспечением. На каждом интервале [ti,ti+1], учитывая R(ti), F(ti) и исходя из значения P(ti), с помощью генерации случайных чисел определяется множество входных значений ПО Xti. Заметим, что результат генерации атрибутов на [ti,ti+1] может определить множества R(ti+1), F(ti+1), P(ti+1) на интервале [ti+1,ti+2] и, тем самым, задать или ограничить множество Xti+1, то есть задать или ограничить входные значения ПО на следующем интервале. Разбивая множество атрибутов на несколько подмножеств, можно имитировать информационные процессы несколькими логическими цепочками. Например, процесс распространения пожара можно имитировать двумя логическими цепочками: цепочкой, соответствующей процессу изменению площади огня и цепочкой, соответствующей изменению площади районов эвакуации населения.

Атрибуты a и b будем называть взаимно несовместимыми атрибутами на интервале [ti, ti+1], если на этом интервале p(a|b)=p(b|a)=0, где p(a|b) – это вероятность генерации атрибута a, то есть вероятность pa(ti), но после генерации атрибута b. Атрибуты a и b будем называть взаимно независимыми атрибутами на интервале [ti, ti+1], если на этом интервале p(a|b)=p(a) и p(b|a)=p(b) Обозначим через ATRti подмножество множества атрибутов ATR на интервале [ti, ti+1]. Причем, в ATRti входят все атрибуты, у которых pa(ti)0.

Приведем без доказательства два утверждения.

Утверждение 1. Пусть / (ti)/ (ti+1) и существует такое подмножество атрибутов Bti+1 множества ATRti+1, что ATRti Bti+1 ATRti+1. Тогда, если для каждого атрибута b из Bti+1, выполняется равенство pb(ti+1)=1 и множества ATRti, Bti+1 не содержат взаимно несовместимых атрибутов, то генерация атрибутов продолжается либо бесконечно, либо существует такое множество CATR\Bti+1, что pc(ti+1)0 для каждого c из C и pa(ti+1)=0 для каждого a из ATRti\C.

Будем рассматривать логические зависимости /(ti) /(ti+1), предполагая, что множество атрибутов ATRti состоит из независимых атрибутов и для каждого из них pa( ti+1)=1, где a ATRti.

Утверждение 2. Если для двух множеств атрибутов ATR1 и ATR /(ti)/(ti+1).../(tm) существуют две логические цепочки и / / / (ti) (ti+1)... (tm), такие, что множества ATR1ti и ATR2ti не содержат взаимно несовместимых атрибутов, то множества ATR1tm и ATR2tm не содержат взаимно несовместимых атрибутов.

Практическая реализация на имитирующем стенде алгоритма имитации возникновения информации требует наличие некоторого технологического программного обеспечения. Утверждения 1 и 2 учитываются в процессе создания такого алгоритма.

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

Такое подмножество можно получить, если алгоритм имитации возникновения информации учитывает некоторую стратегию тестирования. Например, получение наиболее возможной, наименее возможной, граничной входной информации и т.д. Выбор стратегии достигается изменением значений пар{paj(t), px(t)}в процессе имитации информации. Например, при p/aj(t) = paj(t)+, где 0, достигается генерация наиболее возможной входной информации, при p/aj(t) =1-paj(t) – наименее возможной, при p/x(t)= px(t)+, где x – граничное значение, достигается более частое получение граничной входной информации.

Таким образом, из всевозможных алгоритмов имитации возникновения информации отбираются только те, которые учитывают выбранную стратегию тестирования и удовлетворяют условию: при t алгоритм генерации обеспечивает стремление Xt X.

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

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

Рассмотрим следующие технологические модули и программы.

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

Программы взаимодействуют посредством сокетов.

tSetY, tSetN – модули, устанавливающие или снимающие флажки наступлений некоторых событий в информационной системе.

tStart – модуль начала работы прикладной программы.

tInfоrm – модуль, передающий и принимающий данные от модуля tModel в процессе имитации возникновения информации. Он находится в прикладных программах.

tDistribute – модуль, распределяющий в прикладных программах данные, полученные от модуля tModel, между переменными программ. Текст модуля изменяется при изменении типа и структур переменных, которым присваиваются генерируемые входные данные. Модуль создается группой, занимающейся тестированием ПО. Другие прикладные программисты лишь информируют группу о наименованиях, типах и структурах входных переменных своих программ.

tGenerator – вспомогательный модуль в прикладных программах.

Модули tSetY, tSetN, tStart, tInfоrm, tGenerator в отличие от tModel и tDistribute являются неизменными для всех разработок ПО информационных систем.

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

присвоение им входной информации должно осуществляться сразу после ее ввода через вызов модуля tGenerator. Третье:

части программы, сканирующие входные директории, таблицы базы данных или устройства, должны быть организованы следующим циклом. Начало цикла. If (установлен ли флажок начала имитации и (логическое) пришли ли данные от программы tModel) then выход из цикла;

else операторы сканирования. Переход на начало цикла. Конец цикла.

Алгоритм взаимодействия модулей в процессе имитации возникновения входной информации протекает следующим образом.

Программа tModel запускается первой и устанавливает флажок начала имитации. Программа в определенное время генерирует входную информацию и передает ее посредством сокетов модулям tInfоrm. Программа модулем tSetY устанавливает флажки наступления события генерации данных для заданной программы и после приема сообщения от прикладной программы о завершении этих событий модулем tSetN снимает флажки.

Прикладные программы начинают свою работу модулем tStart, который определяет, происходит имитация возникновения входных данных или необходимо работать в обычном режиме. Посредством модуля tInfоrm происходит периодический запрос к программе tModel. В случае получения от нее входных данных, модуль tInfоrm моделирует нажатие соответствующих клавиш клавиатуры или информирует прикладную программу о пришедших данных от программы tModel. Прикладная программа выполняет присваивание входной информации посредством вызова модуля tGenerator, который проверяет, установлен ли флажок имитации данных. Если он установлен, то вызывает модуль tDistribute. Модуль tDistribute выполняет присваивание входной информации, полученной от программы tModel, переменным прикладной программы и посылает сообщение программе tModel о завершении события генерации данных.

Таким образом, рассмотренная технология позволяет при соблюдении правил технологии отделить прикладных программистов от процесса непосредственной имитации возникновения входной информации и, вместе с тем, эффективно проводить моделирование информационной среды объектов автоматизации.

Литература 1. Бабич М.Ю. Использование картографической информации при моделировании информационной среды сложного программного обеспечения Труды международной научно-технической конференции «Проблемы автоматизации и управления в технических системах». – Пенза: ПГУ. 2004.

Р.А. Бикташев, И.О. Кошкин, И.А. Тюрин Пензенская государственная технологическая академия, Россия, Пенза.

ВИЗУАЛЬНАЯ СИСТЕМА АНАЛИТИЧЕСКОГО МОДЕЛИРОВАНИЯ СТОХАСТИЧЕСКИХ СЕТЕЙ Моделирование вычислительных систем является важной составной частью системного этапа проектирования. Поскольку по полученным характеристикам различных моделей можно осуществлять сравнение различных вычислительных систем, анализировать их производительность при изменяющейся нагрузке и т.д.[3,4] Кроме того важна познавательная ценность моделирования. Именно это обстоятельство приводит к широкому внедрению средств моделирования в учебный процесс. В работе предлагается программная система аналитического моделирования вычислительных систем с использованием стохастических сетей массового обслуживания, отличающаяся удобным визуальным интерфейсом пользователя, что позволяет упростить процедуру задания параметров объекта моделирования и получать большее число экспериментальных данных за единицу времени.

Существуют программы, выполняющие аналитическое моделирование сетей массового обслуживания и работающие в текстовом режиме[1,3]. Все программы имеют сходные возможности расчета и похожий пользовательский интерфейс. В них модель задается путем ввода матрицы вероятностей передач и параметров отдельных СМО в соответствующие поля, а результаты расчета выводятся в текстовый файл. Эти программы имеют возможность осуществлять расчет с одним или двумя одновременно изменяющимся параметрами. Кроме этого существуют инструментальные средства для визуального имитационного моделирования[2], которые разработаны для систем автоматики и мало приспособлены для моделирования сложных процессов в вычислительных системах.

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

Кроме этого в программе расширены функциональные возможности. Так наряду с обычным выводом результатов работы программы в виде таблицы на экран и в текстовый файл, существует возможность вывода в виде диаграмм изменения различных характеристик сети и составляющих её систем массового обслуживания (СМО) при множестве одновременно изменяющихся параметров. Также имеется функция сохранения моделей в виде файлов, а также сохранения диаграмм, полученных в результате моделирования. Расчет производится как по фиксированным параметрам так и по варьируемым, причем число варьируемых параметров может быть любым. Кроме этого расчёт может производиться для трех типов систем массового обслуживания: с неограниченной длиной очереди, с ограничением длины очереди и систем с приоритетным обслуживанием.

Модель задается либо посредством ввода матрицы вероятностей передач и параметров каждой СМО, либо с помощью визуального интерфейса. При втором способе задания модель представляется в виде графа стохастической сети на экране компьютера (рис.1), на котором размещаются условные изображения систем массового обслуживания, и соединения между ними в соответствии с передачами между СМО. Количество СМО в сети может достигать до 150.

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

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

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

Результаты расчета по фиксированным параметрам выводятся на экран и могут быть сохранены в виде текстового файла. По результатам расчета сети с варьируемыми параметрами формируется текстовый файл, а также могут быть построены диаграммы характеристик сети или отдельных СМО (рис. 2) Полученные диаграммы можно сохранить на диске в формате растровой или векторной графики. При расчете контролируется правильность заполнения матрицы вероятностей передач (сумма строки должна быть равна 1), значения коэффициентов загрузки каждой СМО (он должен быть меньше 1), распределение потока заявок по уровням приоритета.

Рис.1. Общий вид окна программы с построенной моделью.

Рис.2. Представление результатов расчета в виде графика.

Литература 1. Исследования систем оперативной обработки: Методические указания к учебно- исследовательским работам. /Под ред. С.А.

Майорова, Л.: ЛИТМО, 1979.

2. Гультяев А. Визуальное моделирование в среде МАТЛАВ: учебный курс – СПб: Питер, 2000.

3. Бикташев Р.А. и др. Разработка и исследование мультимикропроцессорной системы с общей шиной: Методические указания к курсовому проекту. – Пенза: Пенз. политехн. ин-т, 1991.

4. Бикташев Р. А. Моделирование мультимикропроцессорных вычислительных систем: Учеб. пособие. - Пенза: Пенз. политехн. ин т, 1987.

Н.П. Вашкевич, Е.И. Калиниченко Россия, Пенза, Пензенский государственный университет МОДЕЛЬ РАСПРЕДЕЛЕННОЙ СИСТЕМЫ УПРАВЛЕНИЯ БАЗОЙ ДАННЫХ Использование формальных методов для описания и анализа алгоритмов работы распределенных вычислительных систем (РВС) позволяет улучшить их качество, и как следствие, улучшить производительность и надежность работы системы.

Формальные методы позволяют представить программные компоненты РВС (логические процессы в узлах, коммуникационные сообщения в каналах) как формальные объекты. И, как следствие, обеспечивается возможность построения формальных моделей, для того чтобы изучить поведение системы и получить характеристики её работы. Кроме того, использование формальных методов для описания и анализа систем дает следующие преимущества. Первое – раннее обнаружение неопределенности, несогласованности, незавершенности в неформальных описаниях алгоритма работы системы. Второе – обеспечение автоматического, машинно-связанного анализа правильности формального описания по отношению к исходным требованиям. Третье – обеспечение возможности оценки альтернативных вариантов без дорогостоящего создания прототипа системы.

Рассмотрим пример использования такой модели при разработке алгоритма управления распределенной вычислительной системой. Система представляет собой простую распределенную базу данных (БД). Пример взят из описания цветных сетей Петри (Sect. 1.3 of Vol. 1 of the CPN book).

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

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

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

Представим вышеописанный алгоритм работы РВС на языке графов, как наиболее наглядном. Алгоритм работы каждого узла представляется графом.

Графы всех трех автоматов приведены соответственно на рис.1, 2 и 3.

Рис.1 Граф алгоритма работы узла Каждое состояние автомата имеет метку, которая указывается внутри кружка. Если состояние автомата отмечено выходными сигналами, они указываются под разделительной линией. Рядом с дугами указан входной сигнал, по которому осуществляется переход из состояния.

Рис.2 Граф алгоритма работы узла Сделаем пояснения графа, описывающего работу 1-го узла. Для совместимости с системой моделирования обозначения состояний, входных и выходных сигналов используют латиницу. Используются следующие обозначения: u, up (update - обновление);

h (host - узел);

s (send - послать);

r (receive - получить);

w (wait - ожидать);

rp (replication - репликация).

Сигнал "start1" является внешним (задается внешней средой) и приводит 1 ый узел в начальное состояние. Сигнал "u1" внутренний сигнал автомата (генерируется в произвольный момент времени) по которому узел производит обновление своей БД. Сигнал "h2.s1" это сообщение от 2-го узла 1-ому, что на 2-ом узле обновлена БД. Аналогичное значение имеет сигнал "h3.s1" сообщение от 3-го узла к 1-ому. Сигнал "h2.r1" и "h3.r1" соответственно сообщения от 2-го и 3-го узлов, что они привели свои БД в соответствие с изменением в БД 1-го узла.

По сигналу start1 узел 1 устанавливается в состоянии h1.i и остается в нем до тех пор, пока не поступит сигнал u (u=1). В этом случае узел переходит в состояние h1.up (изменение БД). Затем узел переходит в состояние h1.s1, в котором выдает сообщения 2-му и 3-ему узлу об обновлении своей БД.

Следующее состояние узла - состояние ожидания (h1.w). В этом состоянии узел находится, пока не придут сигналы подтверждения завершения репликации от 2-го и 3-го узлов, т.е. что они обновили свои БД до состояния БД 1-го узла.

После получения этих сигналов узел 1 переходит в начальное состояние. Если же в состоянии h1.i поступил сигнал "h2.s1" или "h3.s1" (напомним, что оба сигнала одновременно поступить не могут), то узел переходит в одно из состояний обновления своей БД до БД 2-го или БД 3-го узлов соответственно.

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

Рис.3 Граф алгоритма работы узла Алгоритм работы РВС будет представлен объединением всех трех графов, т.е. системой из трех взаимосвязанных автоматов, каждый из которых описывает работу одного узла. Взаимодействие автоматов с внешней средой и между собой производится через входные сигналы. Такой подход обеспечивает полную прозрачность модели по отношения к реальной распределенной системе.

Проведем проверку работоспособности предложенного алгоритма с использованием моделирования. Для этого построим СКУ и СВФ каждого автомата (для экономии места не будем приводить их здесь, т.к. это начальный вариант алгоритма, а приведем их потом для конечного варианта этого этапа проектирования). Объединяя СКУ и СВФ каждого автомата в одну систему, получим описание алгоритма распределенной системы. Для моделирования будем использовать специализированную систему СОМПА. После ввода СКУ и СВФ в окне редактора система позволяет автоматически построить прямую таблицу переходов и выходов (ПТПиВ). С использованием этой таблицы выполняется моделирование алгоритма работы системы.

Результаты моделирования позволили обнаружить следующие недостатки в алгоритме работы системы. Во-первых, неправильно определено состояние ожидания узла системы (w). Поскольку по условию узел имеет только один коммуникационный вход (адаптер), то получение сигналов "h2.r1" и "h3.r1" возможно только в разные моменты времени и для ожидания сообщения от 2-го и 3-го узлов нужно ввести три состояния вместо одного. Во-вторых, имеется неоднозначность переходов из состояний i и w (попарная конъюнкция не равна нулю). Эту некорректность можно было обнаружить и до начала моделирования, используя известные формальные методы анализа автоматов.

Здесь это приведено для примера.

Исправив указанные недостатки, получим алгоритм работы узла представленный на рис.4. Теперь узел, находясь в состоянии ожидания, при получении сообщения от какого-либо узла, переходит в новое состояние и ждет получения сообщения обновления от оставшегося узла. При его получении происходит переход в начальное состояние.

Обратим внимание, что для узла i не соблюдается условие полноты переходов, а именно, не определен переход под действием сигнала ^u&h2.s1&h3.s1. Это происходит потому, что такое сочетание событий не может возникнуть в системе (есть только один адаптер). Аналогичное замечание имеет место и для состояния w и входного сигнала h3.r1&h2.r1.

Для скорректированного алгоритма системы получим СКУ и СВФ:

СКУ:

//Узел h1.i=start1^u1&^h2.s1&^h3.s1&h1.ih3.r1&h1.w13h2.r1&h1.w12h1.a2h 1.a h1.up=u1&h1.i h1.rp21=^u1&h2.s1&^h3.s1&h1.i Рис.4 Скорректированный алгоритм работы узла h1.rp31=^u1&h3.s1&^h2.s1&h1.i h1.s=h1.up h1.w=h1.s^h2.r1&^h3.r1&h1.w h1.w13=h2.r1&^h3.r1&h1.w^h3.r1&h1.w h1.w12=h3.r1&^h2.r1&h1.w^h2.r1&h1.w h1.a2=h1.rp h1.a3=h1.rp //Узел h2.i=start2^u2&^h1.s2&^h3.s2&h2.ih3.r2&h2.w23h1.r2&h2.w21h3.a1h 3.a h2.up=u2&h2.i h2.rp12=^u2&h1.s2&^h3.s2&h2.i h2.rp32=^u2&h3.s2&^h1.s2&h2.i h2.s=h2.up h2.w=h2.s^h1.r2&^h3.r2&h2.w h2.w23=h1.r2&^h3.r2&h2.w^h3.r2&h2.w h2.w21=h3.r2&^h1.r2&h2.w^h1.r2&h2.w h2.a1=h2.rp h2.a3=h2.rp //Узел h3.i=start3^u3&^h1.s3&^h2.s3&h3.ih1.r3&h3.w31h2.r3&h1.w32h3.a1h 3.a h3.up=u3&h3.i h3.rp13=^u3&h1.s3&^h2.s3&h3.i h3.rp23=^u3&h3.s3&^h2.s3&h3.i h3.s=h3.up h3.w=h3.s^h1.r2&^h3.r2&h3.w h3.w31=h2.r3&^h1.r3&h3.w^h1.r3&h3.w h3.w32=h1.r3&^h2.r3&h3.w^h2.r3&h3.w h3.a2=h3.rp h3.a3=h3.rp СФВ:

h1.s2=h1.s h1.s3=h1.s h1.r2=h1.a h1.r3=h1.a h2.s1=h2.s h2.s3=h2.s h2.r1=h2.a h2.r3=h2.a h3.s1=h3.s h3.s2=h3.s h3.r1=h3.a h3.r2=h3.a Отметим, что описание алгоритма работы всей системы также может быть легко декомпозировано на три алгоритма работы каждого её узла. Так для моделирования алгоритма узла 1 достаточно вычислять уравнения СКУ и СВФ начинающиеся с h1. Это позволяет проверить правильности алгоритма работы отдельных узлов автономно, прежде чем выполнить моделирование всей системы в целом. Такой подход позволяет быстрее получить конечный результат – работоспособный алгоритм всей системы. Результаты моделирования алгоритма работы узла 1 приведенные на рис.5 подтверждают его работоспособность. Аналогично проверены алгоритмы работы узлов 2 и 3.

Рис.5 Моделирование работы узла Рис.6 Моделирование работы системы Теперь выполняем моделирование всей системы для случая, когда произведено обновление БД узла 1. Результаты моделирования представлены на рис.6.

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

Поэтому для полного анализа поведения системы можно использовать формальный метод определения всех возможных её состояний. Этот метод [1] основан на преобразовании параллельного алгоритма работы системы к последовательному алгоритму. Каждое состояние последовательного алгоритма будет представлять собой одно из всех возможных состояний системы.

Литература 1. Вашкевич Н. П., Вашкевич С. Н. Недетерминированные автоматы и их использование для синтеза систем управления: Учеб. пособие. Пенза: Пенз. государст. техн. ун-т, 1996. - 88 с.

Е.И. Калиниченко, М.Е. Калиниченко Россия, Пенза, Пензенский государственный университет АВТОМАТНАЯ МОДЕЛЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Производительность и надежность проектируемых алгоритмов работы распределенных вычислительных систем (РВС) может быть улучшена посредством использования формальных методов для их описания и анализа.

Использование формальных методов позволяет представить программные компоненты РВС (логические процессы в узлах, коммуникационные сообщения в каналах) как формальные объекты. И, как следствие, обеспечивается возможность построения формальных моделей, для того чтобы изучить поведение системы и получить характеристики её работы. Кроме того, использование формальных методов для описания и анализа систем дает следующие преимущества. Первое – раннее обнаружение неопределенности, несогласованности, незавершенности в неформальных описаниях алгоритма работы системы. Второе – обеспечение автоматического, машинно-связанного анализа правильности формального описания по отношению к исходным требованиям. Третье – обеспечение возможности оценки альтернативных вариантов без дорогостоящего создания прототипа системы.

Формальное описание РВС обязательно должно учитывать поведение системы во времени. При этом временное поведение зависит:

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

- от доступности общих ресурсов;

- от надежности коммуникаций, т.е. деления и воссоединения сетей;

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

Вот почему необходима формальная модель, как инструмент для разработки и анализа, которая комбинирует математический аппарат и учет временных соотношений. Используя её можно будет определить работоспособность алгоритмов РВС по срокам их завершения, взаимодействиям процессов ("узкие" места, взаимоблокировки ), доступность ресурсов.

Так как по своей сути моделирование алгоритмов работы РВС есть моделирование параллельных процессов на событийном уровне, то наиболее подходящей математической моделью будет модель недетерминированных конечных автоматов (НКА) [1]. Почему? Во-первых, в модели НКА на уровне входов/выходов имеется естественный параллелизм. Во-вторых, получаемый естественным образом, структурированный подход к построению модели. Для описания работы каждого узла и канала сообщения на уровне логических процессов используется отдельный автомат. Затем, объединяя эти автоматы в систему взаимосвязанных автоматов, получаем модель всей распределенной системы. В-третьих, получаемая возможность иерархичной детализации алгоритма работы любого узла или канала, и, как следствие, всей системы в целом. Т.е. при необходимости поведение любого автомата из системы может быть детализировано до нужного уровня. Таким образом, получается возможность описывать алгоритмы работы РВС любой степени сложности и с любой степенью детализации.

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

Поэтому, предлагаемая модель может быть использована для описания как синхронных, так и асинхронных систем.

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

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

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

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

Каждая итерация моделирования системы состоит из двух фаз:

1 фаза (асинхронная работа каждого узла и канала) – выполнение очередного перехода в каждом автомате независимо друг от друга;

2 фаза (синхронизация работы всех узлов и каналов) – когда временные метки каждого автомата синхронизируются относительно времени работы всей системы в целом.

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

При программной реализации модели используется задание автомата на языке систем канонических уравнений и систем функций выхода (СКУ и СВФ) [2]. Автором предлагается простой и эффективный способ перехода от графа автомата к СКУ и СВФ. Т.к. автомат относится к классу недетерминированных, то будет использоваться язык недетерминированных систем канонических уравнений и систем функций выхода (НДСКУ и СВФ) [1]. Эта связка двух языков позволяет легко формализовать логику работы узлов системы и каналов передачи сообщений. Основным достоинством языка НДСКУ и СВФ является то, что записанный на этом языке алгоритм представляет, готовое решение для программной реализации.

Предлагаемый авторами метод минимизации числа состояний автомата путем выполнения формальных преобразований НДСКУ и СВФ позволяет выявить и исключить избыточные состояния как в отдельных узлах и каналах, так и в целом в системе.

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

Для поддержки такой модели разработана система моделирования. Она построена по модульному принципу и включает в себя шесть модулей (рис.1).

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

Синтаксис описания узлов и каналов приведен на рис.2. Назначение полей ясно из их названия. Поясним только назначение полей "список состояний" и "поведение" в описании узла. В первом поле перечисляется список всех возможных состояний автомата. Во втором описываются переходы автомата на языке СКУ и СВФ. Сопоставление этих полей при синтаксическом анализе позволяет выявить возможные ошибки.

Рис.2 Описание узлов и каналов Работа с системой моделирования приведена на рис.3. Вначале описываются компоненты системы, и проверяется правильность их описания.

Затем производится создание модели системы и задание начальных установок.

Рис 3. Работа в системе моделирования Выполняется моделирование, интерпретация и анализ полученных результатов. Затем изменяются значения начальных условий вручную, или автоматически, и повторяется моделирование. Накопленные результаты в дальнейшем могут быть обработаны каким-либо математическим пакетом.

Рассмотрим пример модели протокола репликации, для однородной (т.е.

на всех узлах данные хранятся в формате одной базы данных и на всех узлах функционирует одна и та же СУБД, например Oracle) распределенной системы управления базой данных. Для репликации данных используется протокол двухфазовой фиксации транзакций (2PC - 2 Phase Commit). Первая фаза 2PC подготовка к фиксации транзакции (голосование), а вторая фаза 2PC глобальные фиксация или откат транзакции (принятие решения). В упрощенном варианте работа 2PC состоит из трех шагов и выглядит следующим образом:

Шаг 1. На узле, где инициируется транзакция, создается процесс координатор;

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

Участники, которые готовы завершить транзакцию, посылают координатору сообщение READY TO COMMIT. Участники, не имеющие возможности зафиксировать свою часть транзакции, возвращают сообщение READY TO ROLLBACK.

Шаг 2. Если все участники проголосовали за завершение транзакции, координатор принимает решение фиксировать транзакцию - все участники подтвердили согласие. Координатор рассылает всем участникам сообщение GLOBAL_COMMIT. Затем координатор ожидает в пределах установленного тайм-аута. Если хотя бы один участник высказался за прерывание транзакции, координатор прерывает транзакцию, и всем участникам, высказавшимся за транзакцию, посылается сообщение GLOBAL_ABORT.

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

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

Эта ситуация известна под названием опции одностороннего прерывания.

Если время ожидания исчерпано, то ждущий процесс (координатор или участник) следует протоколу "терминирования" (как следует завершить транзакцию в условиях, когда нельзя взаимодействовать с другими участвующими в данной транзакции узлами). Из-за ограниченного объёма статьи не будем рассматривать действия по протоколу "терминирования".

Представим алгоритм репликации для распределенной системы содержащей три узла (без учета каналов), и в которой каждый узел связан с каждым. Модель системы (для координатора транзакции и первого участника) приведена на рис.4 и 5. На рисунках в вершинах графа вверху показывается выходной сигнал, вырабатываемый в этом состоянии, а внизу идентификатор состояния. Дуги отмечены входными сигналами, а с символов "//" начинается комментарий.

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

Предлагается формализация этого анализа, основанная на следующем.

Так как распределенная система представляет единое целое, используя модификацию алгоритма детерминизации, предложенного в [1] можно преобразовать модель состоящую из системы автоматов в модель соответствующую одному детерминированному автомату. Эта модель и позволит анализировать работу всей системы в целом.

Кроме того, такой подход имеет еще одно существенное достоинство.

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

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

использование формализованного подхода для описания;

возможность последовательной иерархичной детализации;

относительная простота программной реализации модели.

Литература 1. Вашкевич Н. П., Вашкевич С. Н. Недетерминированные автоматы и их использование для синтеза систем управления: Учеб.

пособие. - Пенза: Пенз. государст. техн. ун-т, 1996. - 88 с.

2. Вашкевич Н. П. Синтез микропрограммных управляющих автоматов: Учеб. пособие. - Пенза: Пенз. политехн. ун-т, 1990. - с.

Ю.Д. Пальченков Россия, Пенза, Пензенский государственный университет СОПОСТАВЛЕНИЕ АНАЛОГОВЫХ И ДИСКРЕТНЫХ ВЫЧИСЛИМЫХ ФУНКЦИЙ Теория аналоговых вычислений начинается с работ К. Шеннона [1].

На рисунке 1 представлен универсальный аналоговый компьютер (УАК) Шеннона.

Рисунок 1. УАК К. Шеннон, который вычисляет Sint. Ее начальные условия (состояния) – sin(0) = 0 и cos(0) = 1. Вывод модуля интегратора подчиняется d = ud, где u и – его верхний и нижний вводы.

На рисунке 2 представлено разбиение стандартной теории рекурсивных функций на три основные части.

Рисунок 2. Разбиение стандартной теории рекурсивных функций на три основные части Слева на рисунке 2 изображена аналоговая часть теории рекурсивных функций, а справа дискретная (цифровая) часть рекурсивных функций.

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

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

С другой стороны аналогово-цифровую часть вычислимых функций можно рассматривать как интерфейс между аналоговой и дискретной частью рекурсивных функций.

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

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

В отличии от классической вычислительной теории на натуральных числах N. На рисунке 3 приведена УАК схема для определения интегрирования (дифференциальной рекурсии).

Рисунок 3. УАК – схема для определения интегрирования, используемая К.

Муром, где ( ) h( x,0) = f ( x ), d y h ( x, y ) = g x, y, h ( x, y ) % % % % %.

y h ( x, y ) = f ( x ) + g ( x, y, h ) dy % % На рисунке 4 представлены суммарные результаты доклада.

Рисунок 4. Суммарные результаты определяющие соотношения рекурсивных функций Слева на рисунке 4 представлена стандартная (классическая) вычислительная теория на N, в середине – аналоговые вычислимые функции класса R (впервые представленные К. Муром (C. Moore)), а справа вычислимые функции динамических и нейронных систем.

В заключении доклада приведены выводы по сопоставлению аналоговых и дискретных вычислимых функций.

Литература 1. Ю. Д. Пальченков. Вычислимые функции действительных переменных в проектировании аналоговых нейронных сетей.

Вычислительные системы и технологии обработки информации.

Международный сборник наградных трудов, выпуск 1 (27). Пенза 2002 г., с. 17-22.

А.С. Зуев Россия, Москва, Московская государственная академия приборостроения и информатики О ДОПОЛНИТЕЛЬНЫХ СВОЙСТВАХ ДЛЯ КОМОПОНЕНТОВ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ Интерфейс пользовательской программы (ПП) является системой управления ее функциональными возможностями, а каждое воздействие пользователя на элементы интерфейса связано с определенными трудозатратами. В процессе работы с ПП пользователю требуется выполнять определенные операции, каждой из которых соответствует маршрут выполнения [1], – последовательность воздействий на элементы интерфейса. С ростом сложности и количества воздействий нагрузка на пользователя значительно увеличивается, что влияет на эффективность производственного процесса, в котором применяется ПП. Для снижения нагрузки требуется сократить трудозатраты на как можно большее количество воздействий на элементы интерфейса. Наиболее распространенным средством взаимодействия с интерфейсом является компьютерная “мышь”, поэтому следует сокращать трудозатраты при работе с этим средством управления. При работе с клавиатурой нажатия на комбинации клавиш эквивалентны воздействиям “мышью” на определенные элементы интерфейса. Каждое воздействие на элемент интерфейса при помощи “мыши” включает три этапа:

1. Окончание воздействия на предыдущий элемент интерфейса.

2. Передвижение “мыши” (перемещение курсора).

3. Воздействие на требующийся элемент интерфейса.

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

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

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

Рассмотрим пример структуры интерфейса, рисунок 1.

Рисунок 1.

Основное окно программы является родительским для всех элементов. В рассмотренной модели владеющими по отношению к дополнительному окну являются главное меню и выпадающий список, которые ограничивают область, в которой оно может располагаться. В общем случае одновременно отражаемые на экране элементы уровня владения n не должны накладываться на элементы уровней от 1 до n. Рассмотрим пример оптимизации воздействий по средством оптимизации расположения элементов интерфейса относительно друг друга. На рисунках 1.1 и 1.2 цифрами I, II, III отмечены воздействия пользователя, которые требуется оптимизировать.

Рисунок 1.1. Рисунок 1.2.

Опишем представленные интерфейсы с помощью ориентированных графов, вершины которых – элементы интерфейса, а дуги – воздействия пользователя [2]. Длины дуг равны расстояниям в пикселях между элементами интерфейса. Оптимизация положения элементов интерфейса заключается в том, чтобы вершинам предшествовали дуги как можно меньшей длины. На рисунках 2 и 3 представлены графы, характеризующие соответственно интерфейсы, представленные на рисунках 1.1 и 1.2.

Рисунок 2. Рисунок 3.

На рисунке 4 представлена модернизация интерфейса с рисунка 1.1, на рисунке 5 – характеризующий его граф.

Рисунок 4. Рисунок 5.

/ / / / / / S1=S 1;

S2=S 2;

S3=S 3;

S4S 4;

S5S 5;

S6S 6;

Представленный интерфейс получен перемещением дополнительного окна по минимизации расстояний I, II и III. На рисунке 6 представлена модернизация интерфейса, полученная при оптимизации интерфейсов, представленных на рисунках 1.1 и 1.2., на рисунке 7 представлен характеризующий его граф.

Рисунок 6. Рисунок 7.

S1=S 1=S 1;

S2=S 2S 2;

S3=S 3S 3;

S4S 4S 4;

S5S 5S*5;

S6S/6S* / * / * / * / * / S11S*1;

S12S*2;

S13S*3;

S14=S*4;

S15=S*5;

S16=S* Оптимизация положения элементов интерфейса значительно сократит нагрузку на пользователя. Для реализации представленных модернизаций для компонентов объектно-ориентированных языков программирования следует предусмотреть возможность привязки компонентов друг к другу с помощью специальных узлов, рисунок 8.

Рисунок 8.

Пусть в вершинах и на ребрах каждого компонента располагаются узлы привязки, обладающие специальными свойствами [3], которые доступны, при разработке программы, и могут изменяться пользователем в процессе работы с ней. Это позволит создать специальный режим настройки интерфейса. Пусть для всех узлов привязки предусмотрена возможность их перемещения и прикрепления друг к другу в произвольном порядке, что позволит изменять форму элемента и создавать нетиповые элементы путем комбинирования типовых элементов. На рисунках 9, 10 и 11 представлены варианты модернизации проводника данных в операционной системе Windows.

Рисунок 9. Рисунок 10. Рисунок 11.

Представленные модели снижают нагрузку на проводник данных и облегчают работу пользователя. На рисунке 12 представлен вариант нетипового размещения элементов интерфейса, представленного ранее на рисунке 8.

Рисунок 12.

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

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

Рисунок 13. Рисунок 14.

Координаты узлов привязки определяются относительно родительского компонента, что позволяет сохранить положение узлов и форму компонента.

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

Рисунок 15. Рисунок 16.

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

Литература 1. Зуев А.С. Применение графов при исследовании интерфейсов пользовательских программ. / Материалы IV региональной научной конференции “Математическое моделирование и информационные технологии”. – Георгиевск: СевКавГТУ, 2004.

2. Зуев А.С. Оптимизация интерфейсов пользовательских программ. / Сборник трудов Второй всероссийской научно-практической конференции “информационные модели экономики”. – М.: МГАПИ, 2004.

3. Зуев А.С. Принципы работы с узлами привязки визуальных компонентов объектно-ориентированных языков программирования.

наст. сборник.

А.С. Зуев Россия, Москва, Московская государственная академия приборостроения и информатики ПРИНЦИП РАБОТЫ С УЗЛАМИ ПРИВЯЗКИ ВИЗУАЛЬНЫХ КОМПОНЕНТОВ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ В работе [1] рассматривались возможности проектирования интерфейсов пользовательских программ (ПП) с помощью узлов привязки, предусмотренных как дополнительные свойства для компонентов языков визуального объектно-ориентированного программирования. В данной работе рассматриваются свойства, которыми должны обладать узлы привязки и режимы работы “Проектирование”, “Связка узлов” и “Изменение формы компонента”, возможные при работе с ними, на примере языка Delphi6. В режиме “Проектирование” компонент обладает стандартными свойствами, предусмотренными языком программирования и отображаемыми в Инспекторе Объектов. Режим “Связка узлов” предназначен для установления связей между узлами привязки различных компонентов, работа в этом режиме может осуществляться на формах, включенных в программу, при этом свойства компонентов, предусмотренные в режиме “Проектирование”, становятся недоступными. Рассмотрим свойства, требующиеся для узлов привязки и используемые в режиме работы “Связка узлов”:

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

Рисунок 1.

2. Каждый узел привязки одного компонента может быть связан наложением или линией с узлом привязки другого компонента, рисунок 2.

Рисунок 2.

3. Все узлы компонента должны располагаться на одном родительском компоненте [1].

4. Каждый компонент обладает системой координат, связанной с его левым верхним углом, рисунок 3.

Рисунок 3.

5. Компонент, один из узлов которого связан с узлом данного компонента будем считать связанным по отношению к данному, компоненты могут быть взаимосвязанными.

6. Каждый узел может быть связан только с одним узлом, узлы не могут быть взаимосвязаны.

7. С каждым узлом может быть связано неограниченное количество узлов.

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

9. В режиме “Связка узлов” пользователю недоступно изменение формы и размеров компонента, но доступно перемещение компонента на форме.

10. Каждый узел обладает свойствами Xcoord и Ycoord, значения которых имеют тип integer и равны соответственно его координатам в пикселях по горизонтали и вертикали на форме, на которой он располагается.

Xcoord = x + a, Ycoord = y + b, где x и y – координаты левого верхнего угла родительского компонента в системе координат, связанной с родительским по отношению к нему компонентом, a и b – координаты данного узла в системе координат родительского компонента. Свойства Xcoord и Ycoord являются глобальными и могут использоваться для перемещения компонентов между формами программы.


11. Каждый узел обладает свойствами X и Y, значения которых имеют тип integer и равны соответственно его координатам в пикселях по горизонтали и вертикали в системе координат родительского компонента (X=a, Y=b).

Cвойства X и Y являются локальными и действуют только в пределах компонента, родительского по отношению к данному.

12. Координаты узлов привязки определяются при переходе в режим “Связка узлов” и в момент окончания перемещения компонента, значения свойств Height – высота и Weight – ширина компонента при этом не используются.

13. При перемещении компонента изменяются не только координаты узлов привязки, но и координаты связанных с ними узлов других компонентов.

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

Рисунок 4.1. Рисунок 4.2.

Деформация компонента возможна также при его перемещении и в момент установления связи между его узлом и узлом другого компонента.

14. Узлы компонента не могут быть связаны между собой.

15. Узлы могут быть связаны линией, либо наложением.

При связи наложением используется процедура PutOn:

Procedure PutOn(FromTop, ToTop:TTop);

{FromTop – узел, который связывается наложением, ToTop – узел с которым осуществляется связь наложением, оба узла были выбраны пользователем ранее} begin FromTop.Xcoord := ToTop.Xcoord;

(1) FromTop.Ycoord := ToTop.Ycoord;

(2) end;

При связи линией используется процедура LineTo:

Procedure LineTo(FromTop, ToTop:TTop);

{FromTop – узел, который связывается линией, ToTop – узел с которым осуществляется связь линией, оба узла были выбраны пользователем ранее.} begin FromTop.Xcoord := ToTop.Xcoord + a;

(3) FromTop.Ycoord := ToTop.Ycoord + b;

(4) end;

Здесь a и b – координаты в пикселях связываемого узла в системе координат родительского компонента, относительно узла, с которым он связывается. В режиме “Связка узлов” свойства узлов выбранного компонента отображаются в специальном Инспекторе Узлов, рисунок 5.

Рисунок 5.

Значения свойств узлов привязки можно обрабатывать в исходном тексте программы. Рассмотрим пример, рисунок 6.

Рисунок 6.

Button1.1Top.Xcoord:=Button4.3Top.Xcoord + 98;

Координаты по горизонтали первого узла компонента Button приравниваются к координатам третьего узла компонента Button4 плюс пикселей.

Button1.1Top.Ycoord:=Button4.3Top.Ycoord + 25;

Координаты по вертикали первого узла компонента Button приравниваются к координатам третьего узла компонента Button4 плюс пикселей.

LineTo(Button1.3Top, Button2.3Top) {Третий узел компонента Button1 и третий узел компонента Button2 соединяются линией.} PutOn(Button3.3Top, Button1.7top) {Третий узел компонента Button связывается наложением с седьмым узлом компонента Button1.} После последовательного выполнения представленных действий компоненты Button1, Button2, Button3, Button4, произвольно расположенные на форме, будут размещены в порядке, представленном на рисунке 6.

С помощью обработки рассмотренных свойств можно настраивать перемещение элементов интерфейса в процессе работы программы по различным траекториям, описываемым уравнениями зависимости между значений их свойств Xcoord и Ycoord при перемещении на другой родительский компонент и X и Y при перемещении по родительскому компоненту. Для этого используется процедура MoveComponent.

Procedure MoveComponent(FromTop, ToTop:TTop;

A, B, C, D, E: Integer);

Var X, Y : integer;

{A, B, C, D, E – значения коэффициентов функции, передаваемые в процедуру} begin X := FromTop.Xcoord;

Y := FromTop.Ycoord;

while X ToTop.Xcoord do while Y ToTop.Ycoord do {условие зависит от положения компонентов относительно друг друга} begin X := X +1;

Y := A*Power(X,4) + B*Power(X,3) + C*Power(X,2) + D* X + E;

Sleep(10);

end;

end;

Выполнение рассмотренной процедуры может вызываться в тексте программы следующим образом:

MoveComponent(Button4.3Top, Button1.1Top, -1, 7, 0, 3, -5);

Для установления связи между узлами пользователю требуется выполнить следующие действия:

1. В дополнительном окне, рисунок 7, нажать кнопку “Выбрать узлы”.

2. Последовательными нажатиями левой клавиши мыши выбирать связываемый узел и узел, к которому требуется осуществить привязку.

3. В дополнительном окне, рисунок 7, выбирать тип связи.

Рисунок 7.

При выборе пункта “Связать наложением” координаты связываемого узла определяются по формулам (1) и (2). При выборе пункта “Связать линией” координаты связываемого узла определяются по формулам (3) и (4).

Режим “Связка узлов” может быть предусмотрен и в процессе работы с программой для предоставления пользователю возможностей настройки положения элементов интерфейса.

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

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

2. Изменение размеров компонентов.

3. Изгиб линии между узлами компонента.

Для изгиба линии между двумя узлами пользователю требуется выполнить следующие действия:

1. В дополнительном окне, рисунок 8, нажать кнопку “Выбрать узлы”.

2. Последовательными нажатиями левой клавишей мыши выбрать два узла, линию между которыми требуется изогнуть, нажать кнопку “Узлы выбраны”.

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

Рисунок 8.

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

Рисунок 9.

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

В режиме “Изменение формы компонента” свойства узлов выбранного компонента и функции, описывающие линий между ними отображаются в специальном Инспекторе формы компонента, рисунок 10.

Рисунок 10.

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

Литература 1. Зуев А.С. О дополнительных свойств для компонентов объектно ориентированных языков программирования. наст. сборник.

Г.Н. Чижухин, О.В. Кулагин, Ю.Г. Бочкарева Россия, Пенза, Пензенский государственный университет, Пензенский филиал ФГУП НТЦ «Атлас»

РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ АЛГОРИТМА ПРОГРАММЫ ДЛЯ АНАЛИЗА ЕЕ СВОЙСТВ ПРИ ВЕРИФИКАЦИИ При анализе свойств программ, необходимых для доказательства их правильности (верификации), исходным документом является листинг программы, написанной на языке высокого уровня (ЯВУ). Анализ листинга можно проводить вручную, что потребует значительных затрат ресурсов и времени.

Поэтому необходимо стремится к автоматизации анализа и начинать надо с автоматизированного преобразования функций из файла на языке Си в ту граф-схему алгоритма (ГСА), которая явилась основой создания этой программы. Получив ГСА, необходимо осуществить равносильные преобразования алгоритма [1] – сначала получить на основе алгебры событий регулярное выражение алгоритма (РВА) [2] и затем преобразовать его в алгебраическое тензорное уравнение алгоритма (ТУА) [3]. Ниже рассмотрим особенности подобного анализа программ для двух последних (теоретических) этапов – преобразование ГСА в РВА и преобразование РВА в ТУА.

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

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

Это достигается за счет преобразования (которое автоматизируется с помощью специальной программы перевода) полученной ранее ГСА в инверсную граф схему алгоритма (ИГСА) (рис.1в). Затем (автоматически с помощью еще одной специальной программы) осуществляется синтез регулярного выражения алгоритма (РВА) за счет использования алгебры событий [4] и возведения в степень исходной автоматной матрицы, полученной из ИГСА и являющейся автоматом без выхода [5].

а) а А1 б) А1 А2 А3 А 1 а а А2 А1 а А2 А3 А в) 1 2 3 4 5 А3 а А Рис.1. Равносильные схемы алгоритма: а) ГСА;

б) общепринятый граф, совпадающий с ГСА;

в) инверсный граф (ИГСА).

В качестве примера приведем получение РВА для ИГСА, показанной на рис.1в. Ее исходная квадратная автоматная матрица представлена в табл. 1.

Таблица 1.

1 2 3 4 5 1 A1 0 0 0 2 0 [a=0] [a=1] 0 3 0 0 A2 0 4 0 0 0 A3 5 0 0 0 0 A 6 0 0 0 0 После возведения ее в степень (m-1)=5 получится матрица в табл. 2.

Таблица 2.

1 2 3 4 5 1 A1 A1[a=0] A1([a=0]A2[a=1]) A1([a=0]A2 A1([a=0]A [a=1])A3 [a=1])A3A 2 0 [a=0] ([a=0]A2 [a=1]) ([a=0]A2 ([a=0]A [a=1])A3 [a=1])A3A 3 0 0 A2 A2A3 A2A3A 4 0 0 0 A3 A3A 5 0 0 0 0 A 6 0 0 0 0 В ячейке таблицы на пересечении 1-й строки с 6-м столбцом этой результирующей матрицы получается РВА A1([a=0]A2[a=1])A3A4. (1) Особенность рассматриваемого равносильного преобразования алгоритма программы на этапе переводов ГСАИГСАРВА в том, что все эти переводы выполняются автоматически на основании известных правил преобразования (ГСА ИГСА) или возведения в степень квадратной матрицы (ИГСАРВА) и, значит, не будет наблюдаться какого-либо искажения алгоритма.

Тензорное уравнение алгоритма. Получив РВА на языке булевой алгебры, преобразуем его в истинно алгебраическую формулу в виде ТУА.

Рассмотрим это на примере выражения (1) для РВА.

Для этого сначала определим ТУА, описывающего оператор условного перехода. Так как операторы последовательных программ представляют собой на самом низком уровне операции, как минимум, над парами, то алгоритмический оператор условного перехода: «if x y then z = x else z = y» на языке ТАС описывается тензорным уравнением y х у ху x y = 1 := x = 0 := z чx уy ее (2) z где x и y – сравниваемые переменные, – булеан, являющийся результатом сравнения и представляющий собой множество {0,1}, одно из двух значений которого 0 (ложно) или 1 (истинно) он может принимать. Каждая из двух ветвей условного перехода (для РВА это условия [а=0] и [а=1]) начинается с тензоров соотношений =1 или = 0. Они интерпретируют равенство булеана одному из значений: 0 или 1. Так как эти значения константы, то они записываются на основном уровне тензора. Завершается алгоритмический оператор условного перехода тензорами объектов, интерпретирующими графики диагональных отображений [3] ' ' ', у, у у х'х означающими копирование переменных, у, х и указывающих сколько ' х раз она использована в этом операторе.

Наше РВА (1) аналогично тензорному уравнению (2) и принимает вид ехеу ху = 0 А2 = 1 А3 А А (3) В выражении (3) операторы А1, А2, А3, А4 представлены в общем виде, подразумевая, что они тоже должны представлять собой какие-то тензоры, а условный оператор есть тензор предикатов, ветви которого ху определяются тензорами соотношений =1 и = 0 и контролируются тензором объектов ' ' ', Из сравнения выражений (1) и (3) видно, что логическое уравнение (1) превращается в алгебраическое (3). Особенность такого равносильного перевода алгоритма программы на этапе РВАТУА заключается в том, что ТУА начинает выполнять роль контролера происходящих процессов в алгоритме.

Литература.

1. Чижухин Г.Н.Лекции по основам математической логики и теории алгоритмов. Учеб. пособие. – Пенза: Изд-во Пенз. гос.ун-та,1999. – 56с.

2. Чижухин Г.Н, Кулагин О.В. Синтез алгоритмов программ на основе алгебры событий и автоматных матриц. Актуальные проблемы науки и образования: Труды Международного юбилейного симпозиума: В 2-х т. Т.2/ Под ред. д.т.н.,проф.М.А. Щербакова – Пенза: Информационно-издательский центр ПГУ, 2003. – 382-383с.

3. Чижухин Г.Н. Тензорная алгебраическая система. / Труды V Междуна- родной научно-технической конференции "Новые информационные технологии и системы", Пенза, ПГУ, 2002, – с.

195-202.

4. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

5. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтезтез). – М.: Наука, 1970.

Г.Н. Чижухин, О.В. Кулагин, Ю.Г. Бочкарева Россия, Пенза, Пензенский государственный университет РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ АЛГОРИТМОВ Введение. Существующие подходы к распараллеливанию вычислений разными средствами решают задачу выделения независимых ветвей в программе и организации их параллельного исполнения на разных исполнительных устройствах. В зависимости от объема этих ветвей различают четыре формы параллелизма: заданий, задач, команд и операций [1]. Из них наиболее распространен параллелизм команд, реализуемый в суперскалярных процессорах и процессорах с длинным командным словом (VLIW и EPIC) [2].

Эти процессоры предназначены для выполнения существующих «последовательных» программ, для которых арифметические и логические операции выполняются не более чем над двумя операндами, однако параллельное выполнение в них производится с использованием нескольких двухвходовых арифметико-логических устройств (АЛУ) при отсутствии связей между параллельно выполняемыми операциями. Тот же принцип выполнения операций используется и в других параллельных вычислительных системах, например, в конвейерных [3] и векторных [1].

Возможность распараллеливания вычислений с использованием многовходовых АЛУ еще полностью не изучена. Такие АЛУ: 1) имеют более двух входов;

2) способны выполнять за один такт арифметические и логические операции над несколькими операндами (например, вычислить следующее постфиксное арифметическое выражение ab + c + q =);

3) формируют единственный результат операции. Известен, например, многовходовый параллельный сумматор [4], выполняющий одновременное суммирование от трех до семи чисел. Такой способ распараллеливания выражений можно назвать многовходовым параллелизмом.

Из-за аппаратной сложности многовходовых вычислительных устройств довольно трудно сделать универсальное n-входовое АЛУ, способное вычислять произвольное арифметико-логическое выражение над n входными переменными (в зависимости от подаваемых на него кодов операций). Более простыми являются многовходовые вычислительные устройства с жесткой логикой, в частности: 1) устройства, выполняющие одну операцию над n входными переменными;

2) устройства, вычисляющие арифметико-логическое выражение над n входными переменными. Такие устройства целесообразно синтезировать в процессе аппаратной компиляции программ [5, 6] для выполнения вычислений, определяемых на линейных участках компилируемого алгоритма.

В данной работе рассматривается подход к распараллеливанию программ на основе регулярных выражений алгоритмов (РВА) [7], позволяющий, в числе прочего, реализовывать и многовходовый параллелизм.

Выделение независимых ветвей в программе с использованием РВА.

При распараллеливании любой программы в ней необходимо выделить независимые ветви для отдельного вычисления каждой из них. Известно много процедур выделения независимых ветвей в программе [1, 8, 9].

Распараллеливание программ осложняют условные переходы, так как они не позволяют заранее, до вычисления условия, определять адрес следующей команды, подлежащей исполнению. Для решения этой, так называемой «проблемы условных переходов», предложен метод ее обхода [2], заключающийся в применении условной конверсии (if-conversion). Условная конверсия заключается в одновременном исполнении обеих ветвей условного перехода с последующим отбором истинного результата. Например, в РВА, описывающим конструкцию [a=0]A[a=1]В, необходимо согласно условной конверсии сначала одновременно выполнить команды по обеим ветвям программы, а затем выполнить дизъюнкции обоих полученных результатов.

Для ациклических участков программ существует простая техника распараллеливания, заключающаяся в одновременном выполнении независимых операций. Существует три вида зависимости между операциями – информационная, логическая, конкурентная. Между операторами А и В существует информационная связь в том случае, если оператор В использует данные, формируемые оператором А. Логическая связь между ними означает, что выполнение оператора В определяется некоторым условием, формируемым оператором А. Конкурентная зависимость проявляется тогда, когда перемещение операторов в ярусы может вызвать конкуренцию над памятью, т.е. затирание каких-то переменных до их использования [9].

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

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

На основе инверсного графа алгоритма [7] (вершины которого нумеруются по порядку от 1 до m, а ребра соответствуют линейным и условным операторам алгоритма), описываемого квадратной автоматной матрицей, при возведении ее в степень (m–1) получается РВА – выражение, описывающее алгоритм при помощи операций алгебры событий. Линейные участки обозначаются в РВА большими буквами, а условия переходов указываются в квадратных скобках (например, [a=1] или [a=0]). Под линейными участками подразумеваются как отдельные линейные операторы, так и базовые блоки [10] – последовательности линейных операторов программы, каждая из них имеет один вход и один выход.

В работе [11] введено понятие терма (или одночлена) регулярного выражения. Им является «такое регулярное выражение, в котором дизъюнкция не является последним из выполняемых действий». Например, регулярные выражения АВ, АВ(СЕ), {AB} являются термами. Так как структура РВА отвечает всем требованиям алгебры событий, то понятие терма также применимо и к РВА.

Рассмотрим пример в виде следующего РВА:



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 

Похожие работы:





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.