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

АКАДЕМИЯ НАУК СССР НАУЧНЫЙ СОВЕТ ПО КОМПЛЕКСНОЙ ПРОБЛЕМЕ

УДК 681.3.068:681.325

ЗЕВИН Григорий Яковлевич

СИСТЕМА СИСТОЛИЧЕСКОГО ПРОГРАММИРОВАНИЯ, ОРИЕНТИРОВАННАЯ НА ТРАНСПЬЮТЕРНЫЕ

СИСТЕМЫ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 1990

Работа выполнена в Институте проблем кибернетики Академии наук СССР

Научный руководитель: доктор технических наук, профессор Ю.Г.ДАДАЕВ

Официальные оппоненты: доктор физико-математических наук В.Б.БЕТЕЛИН кандидат физико-математических наук С.С.ГАЙСАРЯН

Ведущая организация: Институт математики АН I

на заседании специализированного совета Д.002.82.01 Научного Совета АН СССР по комплексной проблеме "Кибернетика" по адресу: 117333, г. Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Совета.

Защита состоится

.«

1990 г. в

Автореферат разослан

1990 г.

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

Д.002.82.01,

кандидат физико-математических наук Г.ГТ.Амирджанов

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

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

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

многих случах программа, имитирующая СБ (систолическая программа) имеет хорошие показатели производительности. Такой подход находит все большее применение и позволяет облегчить составление и написание базового математического обеспечения для многих супер-'ЭБМ.

Цель работы состоит в разработке и реализации системы систолического программирования (SPS - Systolic Programming Syetem), которая может быть использована как для разработки оптимальнш программ для параллельных систем, построенных на базе транспьютеров, так и для имитационного моделирования СВ. Входным языкок системы является разработанный автором специализированный язы> систолического программьтрования ПРЬ (Systolic Programming Language), который предназначен также для спецификации и имитационного моделирования СВ.

Научная новизна: Разработанный язык spl позволяет описыват! сложные систолические вычислители и полностью отвечает природе алгоритмов работы СВ, а построенная на его базе система систолического программирования - генерировать систолические программ! на языке Окнам, являющиеся эффективными для решаемого класса задач.

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

Практическая ценность. Реализованная система и язык систолического программирования SPL могут быть использованы разработчиками базового математического обеспечения мультитранспьютерные систем. Ранее реализованные и разрабатываемые систолическио алгоритмы могут быть записаны на языке SPL и включены в состев разработанной информационно-справочной системы. Затем их можно легк< странслировать в ОккаМ-программы, и, тем самым создать библиотек; эффективных "систолических" программ для транспьютерных систем Разработанная на основе языка SPL система имитационного моделиро вания может быть использована для верификации СВ еще до стадм

:го реализации.

Апробация работы. Основные результаты работы докладывались ia семинаре отдела базового программного обеспечения Института фоблем кибернетики АН СССР, Международной конференции »arcella'80 (г. Берлин, ГДР, 1988 г.), IX и X семшарах по однородным вычислительным средам и систолическим структурам (г. Тьвов, 1989 г.), vil Всесоюзной школе-семинаре "Распараллеливание эбработка информации" (г. Львов, 1989 г.), 1-й Всесоюзной конференции "Однородные выислительные среда и систолические структуры" (г. Львов, 1990 г.), х Всесоюзном семинаре "Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях" (г. Уфа, 1990).

Публикации. Представляемые на защиту результат» опубликованы а работах Г1-5].

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

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

Во введении обосновывается актуальность темы, определяется цель работы и формулируются ее основные положения. Приводится краткое содержание диссертационной работы.

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

В $1.1 приведен обзор программных и аппаратных средств систолического программирования и имитационного моделирования СВ -SDEF, SïSIM, SAS, LISAS, SCE, Miss. Приводятся основные характеристики, достоинства и недостатки этих систем.

В. §1.2 рассматриваются универсальные систолические ЭВМ (Warp, Matrix-1, мультитранспьютерные системы) и языки их программирования - W2, АХ, Оккам. Даны основные характеристики этих языков.

В §1.3 обсуждается методология систолического программирования, которое состоит в моделировании СА на параллельных ЭВМ, что позволяет создавать переносимое и эффективное программное обеспечение. Еще одной задачей систолического программирования является разработка средств спецификации и имитационного моделирования СВ и языков программирования СВ.

В §1.4 дано описание предложенного языка систолического программирования SPL, который предназначен также для спецификации и имитационного моделирования СВ. Он основан на естественном разбиении СА на три стадии - загрузку начальных условий, поддержание граничных условий и функционирование. В СА можно явно выделить две переменные - целочисленную t (время) и в (пространство), поскольку СВ осуществляют вычисления во времени и пространстве. Каждый элемент дашшх СА имеет по крайней мере два индекса в и t, т.е. для переменной X[t,s] индекс t указывает момент вычисления переменной х, а в - вершину графа СВ, в которой вычисляется X.

Основное назначение языка spl - дать возможность разработчику средства создания программных моделей СВ, их трассировки и отображения. Он разрабатывался в качестве базового языка системы систолического программирования, ориентированной на транспьютерные системы. Кроме того, spl призван служить стандартным средством для записи СА, которое было бы доступно как разработчику СА, так и инженеру, разрабатывающему конкретную систолическую СБИС. Поэтому при разработке языка spl были учтены следующие требования:

- средства SPL должны обеспечивать легкое и ясное описание СВ;

- SPL должен позволять описывать СВ высокой сложности;

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

- spl должен иметь удобные средства трассировки.

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

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

В SPL имеются следующие простые типы данных: целый (integer), вещественный (Real), булев (Boolean), символьный (Character).

Программа на языке SPL может включать 8 последовательных секций (разделов) и имеет следующую синтаксическую структуру:

Сшзлбхинеская-програлла : := SPROO иля-систомческой-програлжи ; Секция-опредёления-кошжвт Сет^я-огшссошя-переленных Сею^-отюания-клеток Сещая-аг\исанш-с&юе0.-&х0у-1иетхсшх . Сещия-загрузюг-нансиъкых-значений Сещия-псЮОерхания-гржинных-условиО. Сещия-футищионщювания Cetajua-mpaccvpoemi ENDSP . .

В SPL, как и в большинстве языков высокого уровня, можно определять константы и описывать переменные. Константы должны быть определены в секции под названием constants. После определена константа Судет иметь тип выражения. Ниже приведены примеры опрк -деления констант в SPb.

CONSTANTS

FillerJ = О; Filler_2 = "Заполнитель";

String_Pattern_1 = "ABODE";

Ы = 2; Contenta_Oi_HegiBter_A = 2.8554342;

Все переленные в программе должны быть описаны. В SPL зарезервирована специальная переменная CLOCK, которая служит для ссылки на глобальный такт задающего генератора СВ. Она может быть использована при обращении к элементам массивов и в специальных конст-1 рукциях, о которых будет сказано ниже.

Приведем следующий пример описания переменных на SPL:

VARIABLES

V,I,J,K : Integer; S.Time ,Time2 : Real;

Switch : Boolean; ltatrix_Pattern[M.N] : Real;

String[5] : Character

в spl kjiotiai cb представляются как элемента зарезервированного массива cells, который может быть одномершм или двухмерным. Оси, вдоль которых Оудут производится индексация массива cells, могут выоираться произвольно.

Клетка СБ описывается следующим образом. Задаются границы шаексов массива cells, в которых клетки имеют один и тот же тип и функции. Для однотипных клеток задаются их регистры, порты ввода-вывода и выполняемые функция. Описашю производится по слежующей схьме:

cells [... ] where нихняя гранит # псрэхешюя # верхняя гранит ports

Описание портов registers

Описание регистров auxproc имя вспологатэлыюй процедуры "

Вспомогательная процедура —. . .

END АР FUNCTION

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

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

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

ности операторов. Они могут оперировать только глобальными переменными и константами.

Доступ к pscipcaM ¡слетки осуществляется чорез так называемый селектор клотки. Например, ïamîCb CELL[2].X означает доступ к регистру X клэтки СЕЪЬ[2]. Обращешш к портам клетки проиллюстрировано в вышеприведенном примере.

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

definition

CELLS tl] WHERE 1 tt I # 5; — размер CB

ports

Zin: Real (In); — порты CB

Zout: Real (Out);

A: Real (In);

registers — регистр для хранения

X: Real — результата

— описание функции CB

— производится вычисление промежуточного результата

— и передача в порт Zout значения из порта zin

function

X := X + A*Zin;

Zout := Zin;

На рис» I приведена структура вышеописанного CB и показаны порты и регистр одной метки.

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

Для описания связей s.ezdy imemixuai во время функционирования СВ слузит секция LINKAGE. По умолчанию предполагается обмен па каждом такте работы. Если rte необходимо изменить частоту обмена Ь между портами каких-либо клеток, то это надо указать явно. а Описание связей производится следующим образом. Для однотипных клеток (их границы указываются после толевого слова bounds) с помощью оператора связи описываются порты получения данных (в левой части оператора) и порты передачи данных (в правой части оператора). Если это необходимо, можно указать период обмена Mer-

it- 4

\ ч \ \ \

cells [1] cells [2] cellsí3] cells (4) celi£(5]

Рис. I

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

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

linkage

bounds 1# i # 8;

— Здесь порту.zin 1-ой клетки присваивается значение порта

— Zout (1-1)—ой клетки на предыдущем такте (так как по

— умолчания период обмена равен такту, то это на указано) СКШI].Zin <- СЕШ1-1 ].Zout{

— Начиная с значения clock=2 будет производится ввод

— содержимого порта Dout клетки cell[1-1] в порт Din

— клетки СЕШ1] через каждый такт (т.е. с шагом 2). CELLfl].Din <- CELL[1-1].Dout (PERI0D=2);

Для CB умножения матрицы на вектор [2], секция likkaqb имеет? следующий вид: linkaoe

BOUNDS .1 # I # M ; CEU.tIJ.Zin <- СЕШ 1-11.Zout ; Загрузка начальных значений является первой стадией систолического алгоритма. На этой стадии при t=o выполняется (последовательно или параллельно) один или несколько циклов по

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

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

Начальные значения для СВ четно-нечетной сортировки запишутся

так:

INITCOND

PAR I:=1 ТО N CELL[I].A:=B[I]; CELL(I].X:=0 HHDPAR;

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

INITCOND

PAR I:=1 Т.0 U

CELL[I].X:=B[I] ENDPAR;

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

условий производится при t=0,___,т по множеству граничных клеток

СВ. Здесь Т - время (число тактов) работы СВ.

Для описания граничных условий в spl введен оператор take. По умолчанию приращеште переменной clock подразумевается +1. Явно приращение можно указать после ключевого слова skip. Ниже приведет! два примера написания секции граничных условий на spl - для СВ для умножения матрицы на вектор и для СВ умнокеютя ленточных матриц.

— СВ для умножения матрицы на вектор bouhcond

TAKE CLOCK FROM О TO M-1

CELL[1]-Zin (CLOCK):=Y[CLOCK+1];

— СВ для умножения ленточных матриц

bouncond

TAKE CLOCK FROM О ТО 3*n+2»(p+q) г := max(p,q); РАЙ I:=-p ТО р CELL(I,-q-1j.Xin (CLOCK):= А[(CLOCK+2»I+q-r)/3,(CLOCK-i+q-r) /3 J! EMDPAR;

PAR J:=-q TO q CELLt-p-1 ,J].YJLn (CLOCK):= B[(CLOCK+p-J-r) /3,(CLOCK+2*J+p-r)/3]• EMDPAR; ENDTAKE;

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

Специальный оператор цикла по времени timinq (с управляюще! переменной clock) введен из-за того, что здесь применить оператор for нельзя, так как запрещено использовать в качестве управляпдеИ переменной цикла зарезервированную переменную clock, которая, кап указывалось выше,, используется для ссылки на такт задающего генератора СВ.

Для СВ умножения ленточных матриц секция функционировать выглядит так:

iteration

TIMING FROM О ТО 3*n+2*(p+q) PAR I:=-p TO p PAR J:=-q TO q

CELLFUNCTIONtl.J] ENDPAR ENDPAR

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

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

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

STATUS = ON ;

CLOCKS = 1..M*K ;

DELAY =3;

TRFILE = "MULT.TRC" ;

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

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

Ниже приведены примеры опораторов ввода-вывода.

read (A[],"BPUNDX.Í1LT");

read (В[ ], "BOUNDY.IÍLT" );

write (At],"resultB.out");

Описание грамматики языка SPL в форме модифицированных форм Бэкуса-Наура дано в Прнлсггепш I.

Вторая глава посвящена описанию первой версии системы систолического програглмированкя SPS (Systolic Programming System), которая предназначена для генерации систолических Оккам-программ. Базовым языком этой системы является описанный выше язык систолического программирования SPL.

В §2.1 обосновывается необходимость создания такой системы, которая обусловлена тем, что накоплено большое количество систолических алгоритмов, значительная часть которых может быть эффективно реализована па базе транспьютерных систем. Транспьютеры -высокопроизводительные RISC-микропроцессоры, предложенные фирмой INMOS, изготовлены по технологии СБИС и являются базовыми блокада для построения однородных мультимикропроцессорных систем, которые по своему функционированию напоминают систолические вычислители и

находят все большее применение в задачах обработки изображений и цифровой обработки сигналов. CA адекватным образом могут быть описаны на языке SPL, поэтому естественной является идея о трансляции CA в программу на языке Оккам, которая затем может быть скомпилирована при помощи системы TDS в исполняемый модуль. Система реализована на персональном компьютере, совместимом с IBM PC, на языке Турбо Пролог

В §2.2 приведена структура системы, показанная на рис. 2. Система SPS управляется при помощи системы меню, при помощи которой осуществляется вызов всех программных компонент. Основными блоками блоками системы являются: компилятор, текстовый peöamop, блок просмотра сгенерированной Оккал-програлжи и файловая система.

В §2.3 подробно описаны интерфейс пользователя и система меню. Взаимодействие пользователя с системой SPS осуществляется посредством двухуровневой системы спускающегося (pull-dovm) меню, которое расположено в верхнем прямоугольнике (рис. 3). В нижнем прямоугольнике располагается встроенный текстовый редактор. Меню первого уровня содержит четыре элемента. Выбор элемента меню осуществляется двумя способами: I) нажатием первой заглавной буквы элемента меню или 2) передвижением по элементам меню при помощи клавиш управления горизонтальным движением курсора С—или

Система иене

Текстовый

редактор

Оккаы-програмна

рис. 2

"«—"), причем текущий элемент меню будет обозначаться инверсными цветами; после выбора необходимо нажать клавишу "Enter". В данной

версии системы SPS второй уровень меню имеет только третий элемент ("Piles").

При помощи первого уровня меню пользователь имеет следующие возможности: I) Набрать во встроенном редакторе текст программы на языке SPL (элемент "Edit"); 2) Воспользоваться файловой системой ("Files"); 3) Скомпилировать программу ("Compile"); 4) Просмотреть сгенерированный текст Оккам-программц ("Viow occam code").

Compile Edit

Piles View occam code

,-Edit--,

5 *

i_i

Select with arrows or use first upper case letter

Flic. 3

При выборе элемента ram "Edit" осуществляется переход в текстовый редактор.

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

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

1) Загрузить файл с дискового накопителя в встроенный текстовый редактор ("Load file"). Для этого система запросит имя файла, причем можно задавать имя файла без расширения, расширение имени файла по умолчанию - "stl". Если пользователь нажмет клавишу "Enter" не указывая имени файла, то появляется еще одно окно, в котором буДут выведены все файлы с вышеуказанным расширением; используя клавиши управления движением курсора можно выбрать необходимый файл и затем нажать "Enter", при этом выбранный файл будет загружен в текстовый редактор.

2) Сохранить содержимое текстового редактора ("Save filo"). В ответ на запрос необходимо ввести тля файла для записи на диск.

Если сохранение файла производится после выполнения п. I, то можно его имя оставить' прежним, нажав клавишу "Enter".

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

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

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

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

В том случао, когда программа на языке SPL не содержит шжа-ких ошибок, в окно "Message" будут выдаваться следующие сообщения: "Scanning" (сканирование), "Parsing" (синтаксический разбор), "Generating occam source code" (генерация Оккам-программы) и "Systolic program generated" (систолическая программа сгенерирована), информирующие об проходящем конкретном этапе компиляции и извещающие об окончании процесса компиляции.

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

Р10, после чего компиляция возобновится.

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

В §2.4 описывается реализация системы sps.

В §2.4.1 рассматриваются вопросы конструирования и реализации компилятора языка SPL. Компилятор, как и' вся система, реализован на языке Пролог и состоит из трех частей (блоков):

1) Лексического анализатора (сканера);

2) Синтаксического анализатора;

3) Блока семантического анализа и генерации кода.

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

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

Текст исходной программы

I

Лексический анализатор (сканер)'

I

| Первое промежуточное { представление

I

Синтаксический анализатор

___________ ____________________

Второе промежуточное представление

..............I

Блок семантического анализа и генерации кода

1

Оккан - программа

Рис. 4

Алгоритм работы сканера реализуется предикатом ^кИкурсор,строка, список_дексел), где курсор - начальное значение позиции в сканируемом тексте, строка - преобразованный в строку файл с исходным текстом, список_лексел - результат работы сканера, представляющий собой список термов вида Ь(лексеж1,курсор), причем аргумент ¡щрсор указывает на местоположение распознанной лексел* в исходном файле (эта информация используется в блоке обработки ошибок при выдаче сообщений).

Приведены фрагменты текста программы, реализующей сканер и

рассмотрены основные предикаты.

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

Синтаксический анализатор языка spl реализован по нисходящему методу и использует такие достоинства языка Пролог, как разностные списки и встроенный механизм отката, который позволяет легко реализовать метод рекурсивного спуска. Он был получен при помощи генератора синтаксических анализаторов, поставляемого вместе с системой Турбо Пролог1', что делает его эффективным. Система систолического программирования является экспериментальной, поэтому может оказаться необходимой некоторая модернизация языка spl, его наращивание, добавление некоторых новых конструкций. При использовании генератора синтаксических анализаторов такую модернизацию можно будет произвести довольно просто, так как для этого можно легко сгенерировать новый синтаксический анализатор, а "вручную" придется изменять только сканер и блок семантического анализа и генерации кода. Необходимо отметить, что этот генератор прост в использовании, и, при использовании соответствующих рекомендаций его сможет освоить прикладной программист. В параграфе дано описание входных спецификаций генератора и приведены примеры задания некоторых продукций грамматики языка spl. Полностью грамматика языка, подготовленная для обработки генератором -синтаксических анализаторов, приведена в Приложении 2.

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

Семантический анализ производится с целью проверки соблюдения определенных семантических соглашений входного языка. Примеры таких соглашений в языке spl:

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

- Недопустимо повторное описание идентификаторов;

- ИМейа переменных в описании клеток (celts [I] where 1 # I #

5) должны совпадать;

- При использовании селектора клетки необходимо соответствие размерности (например, если определен двумерный массив CELlß, а производится обращение к регистру сеььш.х).

- Если порт описан как выходной (In), то его использование в левой части оператора связи (в секции linkage) недопустимо.

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

Основным предикатом данного блока является предикат analyoe. Он производит следующие действия:

- Обработку и генерацию констант;

- Обработку и генерацию переменных;

- Анализ описания клеток;

-.Анализ секции связи;

- Генерацию функции клетки;

- Анализ и генерацию начальных условий;

- Анализ и генерацию граничных условий;

- Анализ функционирования

- Анализ секции трассировки;

- Генерацию операторов функционирования.

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

Пример программы на языке SPL, описывающей СВ для умножения матриц, приводен в Приложении 3, а соответствующая программа, скомпилированная системой SPS, приведена в Приложении 4.

В §2.4.2. обсуждается программировать меню системы SPS, которое реализовано при помощи двух предикатов - pulldown и pdwaction. Описаны правила вызова этих предикатов.

В §§2.4.3, 2.4.4, 2.4.5 и 2.4.6 рассматривается реализация вызова компилятора языка spl, встроенного текстового редактора, файловой системы и блока просмотра Оккам-программы соответственно. Для всех перечисленных блоков системы sps приведены соответствующие правила для предиката pdwaction.

§2.4.7 посвящен обработке ошибок. Рассмотрены предикаты для обработки ошибок на стадиях лексического анализа (scan_error), синтаксического анализа (eyntax_error) и семантического анализа (ап_еггог И gen_error).

В третьей главе приведено описание автоматизированной инфор-мациошю-справочной системы систолических алгоритмов (АИСС-СА).

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

В качество стандартного средства записи СА предлагается язык , системы систолического программирования SPL.

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

Система реализована на язшсо Пролог на персональной ЭВМ типа IBM рс/лт. Она дает возможность получить информация о са из следующих областей применения:

Лилейная алгебра;

Обработка сигналов;

Решение дифференциальных уравнений;

Вычислешш с шогочлепами;

Линейное программирование;

Сортировка п поиск;

Обработка изображений.

Запрос к системе осуществляется посредством спускающегося основного меню, расположенного .в верхней части экрана. Под ним находится окно, в котором можно просмотреть текст программ, описывающей СА. Внизу экрана - строка подсказки, которая помогает пользователю в работе. "Снимок" экрана во время работы с системой приведен на рис. 5. Выбор элементов менц первого и второго уровня производится так же, как в системе sps. После выбора элемента меню первого уровня, пользователь имеет возможность выбрать инте

Выберите элемент меню при помощи стрелок и затем нажмите Enter

Рис. 5

ресующий его СА в меню второго уровня.

Выбранный СА можно затем просмотреть в окне просмотра.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан язык систолического программирования SPL, с помощью которого можно описывать сложные систолические вычислители.

2. Разработана и реализована система систолического программирования SPS, ориентированная на транспьютерные системы. При помощи этой системы можно получать эффективные программы на языке Оккам, которые затем можно запустить на выполнение на транспьютерной системе. В состав системы входит компилятор, систем; меню, файловая сиЬтема, встроенный текстовый редактор, блок просмотра Оккам-программ.

3. Разработана и реализована автоматизированная информационно-справочная система систолических алгоритмов, которая облегчает поиск нужного алгоритма. Стандартным средством записи СА принят язык систолического программирования SPL.

По теме диссертации опубликованы следующие работы:

1. Зевин Г.Я. Язык моделирования систолических вычислителей. В кн.:"Обеспечение надежности и живучести ОВС" (Под редакцией Я.А.Дуброва). Препринт ЛВ2-89, Львов, 1989, стр. 40-45.

2. Зевин Г.Я. Языковые средства имитационного моделирования систолических вычислителей. В кн.: "Распараллеливание обработки информации", Тезисы докладов и сообщений VII Всесоюзной школы-соминара "Распараллеливание обработки информации", Львов,

1989, часть I, стр. 152-153.

3. Зевин Г.Я. Языковые средства имитационного моделирования систолических вычислителей. В кн.: "Вопросы кибернетики. Прикладное программное обеспечение и моделирование супер-систем". М., 1990 (В печати).

4. Зевин Г.Я. Система имитационного моделирования систолических вычислителей. В кн.: "Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях". Тезисы докладов X Всесоюзного семинара, Киев, Институу кибернетики им. В.М.Глушкова АН УССР, 1990, стр. 189-190.

5. Зевин Г.Я. Информационно-справочная система систолических алгоритмов. В кн.: "1-я Всесоюзная конференция "Однородные вычислительные среды и систолические структуры" Тезисы докладов, т.1, Львов, 1990,• стр. 71-74.