WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 5 | 6 || 8 |

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

Краткая техническая характеристика системы. Система позволяет: - задавать входные сигналы алгоритма или двоичными, или абстрактными (для абстрактных обязательно использование обозначение zi), что расширяет диапазон применения системы; - задать (описать) алгоритм на любом из стандартных языков таких, как ГСА, РВАС, СКУ и СВФ; - выполнить преобразование описания алгоритма заданного на одном из языков на любой другой из этих языков; - произвести, если это необходимо, преобразование ( детерминизацию ) параллельного алгоритма в последовательный ( это в ряде случаев полезно и для анализа самого параллельного алгоритма ); - произвести упрощение (минимизацию) алгоритма; - проверить правильность (верифицировать) алгоритм моделированием его работы с заданием входа алгоритма по отдельным шагам или на любое число шагов, с возможностью возврата на шаг или на несколько шагов и с возможностью вставки последовательности сигналов в уже промоделированную входную последовательность ( при этом автоматически осуществляется моделирование с учетом вставки сигналов ).

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

Необходимые ресурсы для работы системы "СОМПА": операционные системы - Windows 95( минимальный размер ОЗУ - 8Мб) или Windows NT(минимальный размер ОЗУ - 16Мб) До запуска системы "СОМПА" необходимо, установить специально разработанный для нее шрифт NDA.ttf, используя "панель управления" WINDOWS и значок "шрифты" в ней. Тогда ввод отрицания двоичного входного сигнала или отрицания события производится при нажатой клавише Shift в латинском алфавите, например < Shift > + (при этом прописные буквы исключены), а операции дизъюнкции,- одновременным нажатием + < прерывистая вертикальная черта > также в латинском алфавите.

Приведем описание меню, подменю и вкладок в окнах системы "СОМПА".

При запуске приложения "СОМПА", окно, появляющееся на экране содержит следующие пункты основного меню: "Файл", "Окно", "Помощь". "Файл" позволяет: - вновь задать (подпункт "создать") алгоритм на одном из языков: СКУ и СВФ, РВАС, ГСА по выбору пользователя;, - вновь задать ("создать таблицу") алгоритм на языке ТПиВ; - открыть существующий файл с алгоритмом; - выйти из приложения. Пункты "Окно" и "Помощь" стандартны для приложения под ОС Windows.

Если алгоритм работы задается на языке РВАС то происходит контекстная смена основного меню, которое будет теперь содержать пункты: "Файл", "Правка", "Формат", "Преобразования" "Окно", "Помощь". В "Файл" добавляются пункты подменю, которые позволяют закрыть, сохранить, сохранить с изменением имени создаваемые или открытые файлы. При этом расширение файла формируется автоматически в контекстной зависимости от языка, используемого в активном окне (для РВАС - <имя файла>.rvs). Пункты "Правка", "Формат" основного меню это стандартные подпункты текстовых редакторов, в том числе с возможностью включения / выключения переноса и изменения размера шрифта. Пункт "Преобразования" позволяет выполнить переход от описания алгоритма на языке РВАС к языкам ТПиВ или СКУ и СВФ.

При работе с языком СКУ и СВФ представляются аналогичные возможности (для СКУ и СВФ расширение -.sku).

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

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

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

При выборе пункта "Преобразования" и подпункта "детерминизация" открывается окно содержащее три вкладки. Вкладка "общее" дает общую информацию по алгоритму.

Вкладка "алфавит" позволяет просмотреть алфавиты состояний и входных сигналов.

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

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

5 Л И Т Е Р А Т У Р А 1. Вашкевич Н. П. Синтез микропрограммных управляющих автоматов: Учеб. пособие. - Пенза: Пенз. политехн. ун-т, 1990. - 115 с.

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

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

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 535 с.

5. Foster Ian "Designing and Building Parallel Programs": Конспект лекций. Электронный адрес - www.mcs.anl.gov.

ПРИЛОЖЕНИЕ ------------------------------------------------------------------------------------------------------------- // ЗАГОЛОВОЧНЫЙ ФАЙЛ // nda.h // #ifndef NDA_H #define NDA_H #define NUM_OF_EVENTS 10 //число уравнений СКУ.

#define BOOL short int #define TRUE 0xFFFF #define FALSE #define Sk1 0 //определение констант препроцессора для более удобной #define S1 1 //адресации массива событий СКУ.

#define S2 #define Sk2 #define S3 #define S4 #define Sk3 #define S5 #define S6 #define Sf #define S0 #endif // // nda.cpp - основной файл.

#include "nda.h" #include

char name[81]; //буфер для ввода имени файла.

BOOL Sprev[NUM_OF_EVENTS]; //массив для событий СКУ от (t-1).

BOOL Snext[NUM_OF_EVENTS]; //массив для событий СКУ от (t).

BOOL Z[256]; //массив для входных сигналов с Z0 по Z255.

int ch=0; //переменная для хранения очередного байта файла.

int flag=0; //признак обнаружения цепочки-образа.

int i=0; //счетчик цикла.

//ввод имени файла для поиска.

printf("Пример программы поиска цепочек-образов в файле \n");

printf("Введите имя файла (полный путь): ");

gets(name);

fl=fopen(name,"r");

if(fl==NULL){ perror("Вы ошиблись! ");

getch();

return;} //инициализация начальных значений S(t) и S(t-1) СКУ.

for(i=0;i

for(i=0;i

//установка начальных событий (в данном примере одного).

Sprev[S0]=TRUE;

//чтение байта из файла while((ch=fgetc(fl))!=EOF){ for(i=0; i<256; i++) (i==ch)(Z[ch]=TRUE):(Z[i]=FALSE);

//вычисление СКУ Sprev[S0]=TRUE;

Snext[SK1]=Sprev[S1]&Z[1];

Snext[S1]=(Sprev[S2]&Z[2])|(Sprev[S1]&Z[2]);

Snext[S2]=Sprev[S0]&Z[1];

Snext[Sk2]= Sprev[S3]&Z[1];

Snext[S3]=Sprev[S4]&Z[2];

Snext[S4]=Sprev[S0]&Z[3];

Snext[Sk3]=Sprev[S5]&Z[1];

Snext[S5]=(Sprev[S0]&Z[3])|(Sprev[S6]&Z[3]);

Snext[S6]=Sprev[S5]&Z[2];

//проверка обнаружения цепочки-образа if(Snext[SK1]|Snext[SK2]| Snext[SK3]){ printf("Найдена одна из цепочек \n");

flag=1; //флаг обнаружения установлен } else //перепись S(t) в S(t-1) for(i=0;i

} if(flag==0) printf("Ни одна из цепочек не найдена \n");

i=getch();

} ---------------------------------------------------------------------------------------------- ПРИЛОЖЕНИЕ -------------------------------------------------------------------------------------------------- //Scandir.cpp - основной модуль проекта для С++Builder 3.//--------------------------------------------------------------------------- #include

USEFORM("main.cpp", Form1);

USEFORM("result.cpp", OKBottomDlg);

//--------------------------------------------------------------------------- WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int) { try { Application-Initialize();

Application-Title = "Выбор диска и каталога";

Application-CreateForm(classid(TForm1), &Form1);

Application-Run();

} catch (Exception &exception) { Application-ShowException(&exception);

} return 0;

} //--------------------------------------------------------------------------- main.h - заголовочный файл //--------------------------------------------------------------------------- #ifndef mainH #define mainH //--------------------------------------------------------------------------- #include

TLabel *Label1;

TButton *Button1;

TButton *Button2;

TDriveComboBox *DriveComboBox1;

TDirectoryListBox *DirectoryListBox1;

TFileListBox *FileListBox1;

void fastcall Button2Click(TObject *Sender);

void fastcall Button1Click(TObject *Sender);

void fastcall DriveComboBox1Change(TObject *Sender);

void fastcall DirectoryListBox1Change(TObject *Sender);

void fastcall FileListBox1Change(TObject *Sender);

private: // User declarations bool file;

public: // User declarations fastcall TForm1(TComponent* Owner);

};

//--------------------------------------------------------------------------- extern PACKAGE TForm1 *Form1;

//--------------------------------------------------------------------------- #endif main.cpp - главная форма приложения "Выбор диска и каталога" //--------------------------------------------------------------------------- #include

//--------------------------------------------------------------------------- fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { file=false;

} //--------------------------------------------------------------------------- void fastcall TForm1::Button2Click(TObject *Sender) { Release();

Application-Terminate();

Pages:     | 1 |   ...   | 5 | 6 || 8 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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