Введение к работе
Актуальность. Современные задачи обработки сигналов и изображений, линейной алгебры, вычислительной геометріш предопределяют переход к использоваїшга новейших вычислителышх технологий. В настоящее время доступны дешевые высокоскоростные кристаллы сверхбольших интегральных схем (СБИС), содержащие около IOOOOQ транзисторов на кристалле, причем каждые два-три года плотность размещения вентилей на кристалле увеличивается вдвое. Кроме того, наличие различных систем автоматизированного проектирования (САПР) СБИС позволяет создавать специализированные системы, удов-летворящие требованиям конкретной вычислительной задачи. В большинстве случаев для задач обработки сигналов и изображения единственным решением является применение специализированных матричных процессоров, так как универсальные параллельные ЭВМ довольно дорога и, кроме, того, но обеспечивают должный уровень производительности из-за больших системных расходов. Так как связь для СБИС является ограничивающим фактором, большое значение приобретают массивы с короткими локальными связями. Этим требовагаїям удовлетворяют структуры систолических вычислителей (СВ).
Систолические вычислители могут быть составлены из небольшого числа типов модулей, соединенных регулярным способом, причем существует небольшое число типов графов межсоединений (около 10). СВ производят ритмичные вычисления и передачу данных по массиву процессоров, каждый из которых прокачивает данные, выполняя в каждый момент короткие вычисления с тем, чтобы в сети сохранялся регулярный поток данных. Разработка, проектирование и анализ СВ достаточно сложны, для чего нужны специальные методики для точной спецификации и формальной верификации сетей СВ. В связи с этим возникла необходимость в языках и средствах описания и моделирования СВ. Такие языки позволяют унифицировать описание СВ и производить пошаговый контроль их работы. Кроме того, языки спецификации и имитационного моделирования СВ оказываются весьма полезными -и в систолическол програхлировании - недавно возникшей методике параллельного программировать, которая заключается в'моделировании СВ (который, как правило, является оптимальным для решаемого класса задач) на какой-либо параллельной супер-ЭВМ. Во
многих случах программа, имитирующая СВ {систолическая программа) имеет хорошие показатели производительности. Такой подход находит все большее применение и позволяет облегчить составление и написание базового математического обеспечения для многих супер-'ЭБМ.
Цель работы состоит в разработке и реализации системы систолического программирования (SPS - Systolic Programming System), которая может быть использована как для разработки оптимальній програми для параллельных систем, построенных на базе транспьютеров, так и для имитационного моделирования СВ. Входным языкок системы является разработанный автором специализированный язы* систолического программирования ПРЬ (Systolic Programming Language), который предназначен также для спецификации и имитационногс моделирования СВ.
Научная новизна: Разработанный язык spl позволяет описнваті сложные систолические вычислители и полностью отвечает природе алгоритмов работы СВ, а построенная на его базе система систолического программирования - генерировать систолические программ! на языке Оккам, являющиеся эффективными для решаемого класса задач.
Разработанная информационно-справочная система систоличеекго алгоритмов (СА) представляет собой "компьютеризованную" верста библиотеки СА и позволяет получить сведения об основных алгоритмах из многих областей применения СВ и существенно облегчает работу по исследованию и каталогизации СА.
Практическая ценность. Реализованная система и язык систолического программирования SPL могут быть использованы разработчиками базового математического обеспечения мульглтранспыотерньи систем. Ранее реализованные и разрабатываемые систолические алгоритмы могут быть записаны на языке SPL и включены в состев разработанной информационно-справочной системы. Затем их можно легк< странслировать в ОккеМ-программы, и, тем самым создать библиотек; эффективных "систолических" программ для транспьютерных систем Разработанная на основе языка SPL система имитационного моделиро вания может быть использована для верификации СВ еще до стади
:го реализации.
Апробация работы. Основные результаты работы докладывались іа семинаре отдела базового программного обеспечения Института проблем кибернетики АН СССР, Международной конференции »агсе11а'8в (г. Берлин, ГДР, 1988 г.), IX и X семшарах по одно-эодным вычислительным средам и систолическим структурам (г. Тьвов, 1989 г.), VII Всесоюзной школе-семинаре "Распараллелизание эбработга информации" (г. Львов, 1989 г.), 1-й Всесоюзной конфе-эенции "Однородные выислительные среды и систолические структуры" (г. Львов, 1990 г.), х Всесоюзном семинаре "Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях" (г. Уфа, 1990).
Публикации. Представляемые на защиту результати опубликованы а работах Г1-5].
Структура диссертации. Диссертация состоит из введения, трех глав, заключения, приложений и списка литературы, содержащего 57 наименований.
