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

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

Лялин

Александр Сергеевич ^^гтДЙ^

МАТЕМАТИЧЕСКИЕ МОДЕЛИ В ПРОЕКТИРОВАНИИ АППАРАТНО-ПРОГРАММНЫХ РЕАЛИЗАЦИЙ АЛГОРИТМОВ, ЗАДАННЫХ ТЕКСТАМИ

ПРОГРАММ

Специальность-05.13.18 0034523Э6

Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 3 цг^с< "ООО

Москва-2008

003452396

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета).

Научный руководитель:

доктор физико-математических наук, профессор Столяров Лев Николаевич

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Семёнов Виталий Адольфович кандидат технических наук, Бутузов Александр Валерьевич Институт точной механики и вычислительной техники им. С.А.Лебедева РАН

Защита состоится 2008 г. в ¡2°° часов на заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан /7- ОЦСГЛг)^,^ 2008 г.

Ученый секретарь диссертационного совета / ' Федько О.С.

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

Актуальность работы. В настоящее время все известные системы автоматизированного проектирования (САПР) построены на принципе заранее придуманной проектировщиком аппаратно-программной реализациии некоторого алгоритма на специальном формальном языке (например, на языках Си, Уеп1о§ или УНОЬ).

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

Такая автоматизированная технология проектирования, названная в работе «от программы к аппаратно-программной реализации», даёт возможность, по сравнению с существующими САПР, вовлечь в поле проектирования огромный запас уже созданных программ на алгоритмических языках.

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

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

аппаратно и программно на специализированных или универсальных процессорах.

Для решения этих задач использованы следующие формальные модели: 1) логическая структура алгоритма (ЛСА), которую задаёт исходная программа, 2) информациионная структура алгоритма (ИСА), которая вычисляет функции в исходной программе, 3) визуальные формы ИСА, удобных для анализа: ярусно-параллельные формы (ЯПФ), многопроцессорные и конвейерные разложения ИСА, 4) модель синхронизации процессов в аппаратной и программной частях, буферной памяти, 5) модель информационной структуры управления процессами (ИСЯ).

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

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

Апробация работы. Результаты диссертации докладывались на следующих научных конференциях и семинарах: ХЬУП и ХЬУШ научные конференции Московского физико-технического института (2004, 2005); 10-я Байкальская Всероссийская конференция с международным участием «Информационные и математические технологии в науке, технике и образовании» (2005); 12-я Всероссийская межвузовская конференция студентов и аспирантов «Микроэлектроника и Информатика - 2005»; X Международная научно-техническая конференция и молодёжная школа-семинар «Актуальные проблемы твердотельной электроники и микроэлектроники», ПЭМ-2006 (2006); 4-я международная научно-техническая конференция «Фундаментальные проблемы радиоэлектронного приборостроения» (2006); 9-я международная конференция «Методы проектирования и использования систем САПР в микроэлектронике СА08М-2007»; научные семинары кафедры информатики Московского физико-технического института (2003-2007 гг.).

Результаты работы были использованы в проекте РФФИ № 05-07-90406 «Экспертная система для информационной поддержки проектирования энергосберегающих вычислительных архитектур».

Публикации. По теме диссертации опубликовано 11 работ, в том числе одна - из списка изданий, рекомендованных ВАК РФ [11].

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

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

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

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

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

1.1 Информационная структура алгоритма (ИСА) представляет собой сложную функцию, заданную графом подстановок из элементарных функций. Пример ИСА показан на рис.1. Ребра графа фактически представляют собой «провода», соединяющие аппаратные операционные элементы.

1.2 Аппартно-программная реализация. На рис. 3 схематично представлена очень простая задача проектирования алгоритма, заданного своей программой (рис.2) вычисления функции ИСА (рис.1). На рис.3 показано, что

а).

б).

хь Х2, Хз- входные переменные. ^ fз ^ 2Ь22, г3- промежуточные данные.

элементарные функции. Формула вычисления ИСА: у = Г3( х2)), Г2(хь х3))

Рис.1. Информационная структура алгоритма (ИСА): а) граф ИСА, б) формулы ИСА.

аппаратно-программная реализация (АПР) требует специальную буферную память и синхронизацию между аппаратной и программной системами.

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

Программа на спец. процессоре

Алгоритм, заданный программой

Действия вычисляют элементарные функции Di—*fi, D2-*f2, D2->f2, D4—>f.

ПР

синхронизатор 1

fi ни fl

43J

a*

AP

"Xi

-x2 -x3

"Zi

-z2

■Z3

-y

Шины

буферной

памяти

Аппаратура

Рис.2. Алгоритм задан своей Рис.3. Разбиение ИСА на

программой. процессорную реализацию (ПР) и

аппаратную реализацию (АР) и их совместной работы.

1.4 Существующие системы поддержки проектирования. Известны зарубежные системы поддержки проектирования, которые используют программу алгоритма, описанную на языке Си, для реализации аппаратного обеспечения. Например, зарубежный коммерческий программный продукт ImpulseC и академический проект Spark Стэнфордского университета. Недостатком систем является существенные ограничения на используемые языковые конструкции. Также известны системы проектирования от компаний

Cadenee, Mentor Graphics и Synopsys. В настоящее время ведутся исследования в ИТМ и ВТ им. С.А.Лебедева, в ЗАО «МЦСТ», в ЗАО НТЦ «Модуль» и ГУП НПЦ «Элвис», которые посвящены, в основном, развитию архитектуры процессоров общего и специализированного назначения. Все они используют Си-подобный язык (SystemC, Verilog). Программа на таких языках уже содержит описание схемной реализации, буферной памяти и синхронизации, выбираемых проектировщиком. Таким образом, существующие техники проектирования значительно отличаются от рассматриваемой в диссертации содержательной задачи.

1.5 Основные результаты теории схем программ. Идея схематизации алгоритмов и программ принадлежит A.A. Ляпунову (1953). Первое систематическое рассмотрение свойств схем программ было сделано Ю.И. Яновым (1956 год). Пример схемы Янова показан на рис. 4а и фактически представляет собой блок-схему алгоритма (программы). Ю.И. Яновым был исследован вопрос эквивалентных преобразований блок-схемы программы и построена полная система преобразований, содержащая 14 аксиом и 3 правила вывода. А.П. Ершов рассмотрел теорию Янова в терминах граф-схем, что позволило уменьшить количество аксиом до 6 и упростить правила вывода, а). б).

Рис. 4. а). Схема Янову (блок-схема алгоритма).

б). Граф БМ, соответствующий схеме Янова. В теории стандартных схем объектом исследования была не только блок-

схема программы, а также и информационные взаимосвязи между операторами

через общие переменные. А.П.Ершов ввёл понятие графа информационных

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

1.6 Основные результаты главы 1. Теория схем программ в виде JICA может быть использована для разработки автоматических процедур проектирования АПР. Алгоритм, заданный в исходной программе, который вычисляет некоторую систему функций, может быть представлен в виде своей Информационной структуры (ИСА). Специальная процедура профилирования выделяет в программе элементарные функции и их взаимосвязи (подстановки), «спрятанные» в линейных участках программы. Преобразование программы в форму ИСА является функционально эквивалентным преобразованием. JICA и ИСА являются формальными моделями, которые могут быть использованы в разработке автоматических процедур проектирования.

Во второй главе рассматриваются формальные модели Информационной структуры алгоритма (ИСА) и Логической структуры алгоритма (ЛСА).

2.1 ЛСА является конечным автоматом SM = {S, R, Р, D, i2}, где S = {Sb S2, S3, ... Sk} - конечное множество состояний, R = {(R+i, R1), (R+2> R^)--- (R+n, Rn)} - конечное множество условий переходов в виде предикатов, определённых на конечном множестве элементарных предикатов Р = {рь рг •■, pm}, D = {Di, D2, D3... Dk} - конечное множество действий, Q = {S„ R, —* SJ; Dj} , i = j = l...n — конечное множество правил перехода. В западной литературе более употребляем эквивалентный термин - «машина состояний» (SM) или State Machine. Условия переходов SM генерируются внутри машины, а не во внешней среде. На рис.4б представлена SM, которой соответствует ЛСА в виде схемы Янова (рис.4а).

2.2 Совершенное регулярное выражение ЛСА. Каждой ЛСА (SM) соответствует регулярное выражение. Пример такого выражения для SM рис. 46 в виде совершенной регулярной формы (СРВ) приведён на рис. 5. СРВ

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

Do-RVD, • (R.VD3'RVD2'RVD|)**RVD4'D5 +

D0 • R+i • D, • R+2 • D, • R"3 • D2 • (R> D,» R+2 • D3 • R> D2)* • R+4 • D4 • D5 +

D0 • R+i • D, • R+2 • D3 • (R"3 • D2 • R~4 • D, • R+2 • D3)* • R+3 • D5

Рис. 5. Совершенное регулярное выражение (СРВ) для JICA рис. 46.

2.3 ИСА. Информационная структура алгоритма является композицией функций и данных. Она представляет собой ориентированный граф 1=<Х, V>, где X - множество вершин, интерпретированных именами переменных х и именами функций (операциями) /, которые вычисляют эту переменную (x,J) с X : V- направленные дуги {<(xi.fi), fe,каждая дуга интерпретируется, как элементарная подстановка. Пример элементарной ИСА представлен на рис.1. ИСА является составной функцией g и задаёт схему подстановок между элементарными функциями (//, /2 ,f¡ ■) для вычисления g: у = g (x¡, х2, х2), g = f,(fs(f,(x,, X2)),f2(Xl. X})).

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

а). Рекурсивная формула вычисления функции Фибоначчи.

F(0) = 1, F(l) = 1, F(n+1) = F(n)+F(n-1).

б). ИСА. в). Повторяющийся фрагмент ИСА.

Рис.6. ИСА функции Фибоначчи.

Примитивно-рекурсивная функция задаётся бесконечной схемой подстановок:

/(*/, ...,х„, 0)=g(xh ...,х„);

/(XI,..., х„, у+1) = И(х,.....х„, у,/(х,,.... х„, у));

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

2.5 Информационные связи между действиями в исходной программе описываются матрицей <0„ Ц|>, ¡, ] = 0...к и выделяются из исходной программы применением известной профилирующей процедуры.

2.6 Ярусно-параллельная форма ИСА. Понятие Ярусно-параллельной формы (ЯПФ) представления ИСА было введено Д.А.Поспеловым. На каждом ярусе расположены элементарные функции, которые вычисляются независимо друг от друга. На каждой паре соседних ярусов <Я„ Я,, ¡> находятся «поставщики» информации и только для функций яруса Я,+{. В ЯПФ вводится дополнительная функция «хранения информации» на ярусе (обозначена как «=»). На рис. 7а показана ИСА некоторой функции, на рис. 76 показана ИСА в форме ЯПФ с интерпретацией ИСА именами переменных 1, 2, ... . На рис. 7в показана ЯПФ с памятью, причём количество памяти минимизировано по теореме Ершова для ИСА рис.7а. На рис.7г показана ЯПФ с максимальным количеством памяти, равном количеству переменных ИСА рис.7а.

2.7 Выделение фрагментов ЯПФ для аппаратного или программного исполнения. Синхронизация процессов. Вычисление функции ИСА можно

а). Функция ИСА.

xi,

,z2> .Vi

х2

Z3

б). ЯПФ ИСА. «=» - функция запоминания переменной.

в). Вариант конвейерного разложения с min памятью (по А.П.Ершову).

^ Я2 Я3

г). Вариант конвейерного разложения с шах памятью.

Я, Я2 Я3 Я

Рис. 7. Ярусно-параллельные формы ИСА.

а). Разбиение ИСА.

разбиение П2

JXi 5 7

1у?) У&——+Ф -

-«у ' т \* 9

2 4 6 \ 8

П1 разбиение

►о

■о

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

: ! 6,

1: 2;

П2

r2; М "'ir2

\

>ф-

¡П1

зТ 5-.......

Рис.8. Двухпроцессорное разбиение ИСА.

проводить не только на одном процессоре (вычислительном устройстве). На рис. 8а показано произвольное разбиение ИСА, действия 1, 2, 6 вычисляются на процессоре Пь остальные действия на процессоре П2. Для синхронизации вычислений необходимы буферные регистры и синхронизаторы передачи информации между процессами в разных процессорах. Пример разбиения ИСА представлен на рис. 8а, двухпроцессорное взаимодействие на рис.86, модели синхронизаторов конвейеров, описываемые сетями Петри, на рис. 8в, 8г. Функционирование сети Петри описывается пусковыми и флаговыми функциями, которые могут использоваться для реализации синхронизаторов.

2.8 Основные результаты главы 2. В главе были рассмотрены основные формальные модели и соответствующие автоматические процедуры, которые будут составлять технологию проектирования «От программы к аппаратно-программной реализации»: 1) Совершенное регулярное выражение (СРВ) для ЛСА исходной программы, которая определяет последовательность «склеивания» ИСА из отдельных блоков, 2) эквивалентные преобразования ЯПФ ИСА в конвейерные и многопроцессорные разложения.

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

Для удобства действия в ЛСА (рис. 46) будем обозначать натуральными числами (рис.9а). Действие 0 задаёт начальные значения переменных, действие

а). Рассматриваемая ЛСА.

б). Интерпретация действий аргументами и результатами

х

01

У

\л/_ тГ

о.

>х "У

в). Цепочки Совершенной регулярной формы. Ц,: 1 «(Я^'З 'Я-з^'^» I)*» К'г» 4 • 5

Ц,: О»^,« 1 • Я+2 • 3 • Я"з • 2 • (Я'4 • 1« 3 • • 2)*» 11> 4 • 5 Цз: 0 • Л+1 • 1 • К+2• 3 • (Я'з• 2 • К"4» 1 • К+2» 3)* • Я+3 • 5 Рис. 9. ЛСА и цепочки СРВ. 5 - «читает» результаты вычисления из переменных. Выражения, объединённые операцией разделённого «или», называются цепочками СРВ.

3.1 Анализ возможных связей ЛСА. Каждая цепочка СРВ для действий представима своей примитивно-рекурсивной ИСА, в которой между действиями ЛСА устанавливаются информационные связи.

Лемма 1. О необходимых условиях информационных связей между действиями ЛСА. Между действиями ЛСА О,}, /, у=0..к возможна информационная связь, если О, следует за Б, хотя бы в одной из цепочек СРВ.

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

1). Раскрывается каждая операция «звезда Клини» для цепочек СРВ по правилу (Я)* —► 11*11+0, где Я - регулярное выражение. Например, цепочка Ц] (рис.9)

раскрывается следующим образом: 0*1*(3*2»1)**4*5 —►0*1*3*2«1*3 • 2 •1*4*5 + 0,1,4«5.

2). Получаемое регулярное выражение снова представляется в виде совершенной формы, для цепочек которой строится конвейерное разложение. Пример для выражения 0*1«3*2*1*3*2 •1*4*5, получаемого из цепочки Ць показан на рис. 10а. Действие по лемме I может быть информационно связано с 04, но между ними не устанавливается фактическая информационная связь в конвейере (рис. 10а). В диссертации формулируется и доказывается лемма:

Лемма 2. О достаточных условиях информационных связях между действиями. Выражения, полученные из цепочек СРВ в процедуре (2), задают фактические информационные связи между действиями в ИСА.

0 1 3 2 1 3 2 1 4 5

Рис. 10. Конвейерное разложение для выражения ОЧ'З^Ч'З^'М^.

а). Таблица возможных б). Таблица фактических

информационных связей. информационных связей.

О0 о, о2 Бз В4 о5 О0 О, ъ2 Оз В4 05

О0 - + + + + + Во - + + + + +

о, - + + + + + в, - - + - + +

Г>2 - + + + + + - - + - + +

03 - + + + + + Оз - - - - + +

о4 + о4 +

о5 о5

Табл. 1. Информационные связи.

Таблица фактических информационных связей представлена в табл. 16 и получена при интерпретации ИСА каждого действия.

3.4 Интерпретация ИСА. Действия ИСА могут быть интерпретированы через некоторый набор элементарных функций (рис. 11). а). Пример возможной интерпретации действий элементарными функциями. 1 2 ,3, , 4 .

! х-*.

! *5>* -»■г

г-*

•Ф-.

\л/-

б). Интерпретации действий ИСА выражения 0*1*2*1*4*5. ОМ'2'1 '4*5 , 1

_

х У

»ф.

4-"

Ц

\Л/1

Рис. 11. Интерпретация ИСА. Действия содержат ИСА, которые интерпретированы элементарными функциями.

Примитивно-рекурсивная ИСА каждой из цепочек СРВ преобразуется соответственно интерпретации действий. Например, ИСА для выражения 0 • 1 • 2 • 1 • 4 • 5 представлена на рис. 11.

3.5 Задача разбиения ИСА на фрагменты формально определяется следующим образом. Каждой вершине графа ИСА однозначно ставится в соответствие элемент из множества фрагментов и = {аь а2, а3 ...}. Фрагменты объединяются в группы в = {(рь (р2, фз •••}• Фрагменты могут быть функционально эквивалентны друг другу, то есть являться эквивалентными подстановками элементарных функций ИСА. Группа - ничто иное, как множество фрагментов ИСА, функции которых будут вычисляться на одном и том же АР или ПР (см. определения АР и ПР на рис.3).

3.3 Необходимое условие правильного разбиения. В работе доказывается: Лемма 3. О необходимом условии правильного разбиения ИСА. Для

любых двух фрагментов а; и а2, принадлежащих одной группе <р и вершин ИСА (х/, х2, у¡, У:}, таких, что X/, х? с а1; уи у2 е а2, в случае, если существует дуга ИСА <Х[, у1>, необходимо, чтобы отсутствовала дуга <у2, х2>.

На рис. 12а представлена ИСА некоторого вычислительного алгоритма, на рис.126 разбиение ИСА на фрагменты а0, и а°2, на рис.12в ИСА разбивается на другие фрагменты а\ и а'2. Разбиение рис. 12а нарушает необходимое условие, функции фрагментов а0, и а°2 не могут быть вычислены одним и тем же процессором или аппаратным блоком. Разбиение рис.12в не нарушает это условие.

а).

б).

в).

а , а 2

— ®

> > в

о-— ф

о- е- / ©

/О

;<о —о

Рис.12, а). Пример ИСА. б). Пример неправильного разбиения ИСА. в). Пример правильного разбиения ИСА.

3.4 Конструирование управляющей схемы. Упраляющая схема задаётся 2-мя таблицами 1). (р, ... рп) х (Яь Яг...!^) - матрица вхождения элементарных предикатов в распознаватели и 2). (р! ... рп) х (Э,, 02...0к) - матрица вычислений элементарных предикатов в соответствующих действиях. Для ЛСА рис. 9а с множеством элементарных предикатов {р,, р2}, множеством распознавателей {Яь Я2, Я3,114} и множеством действий {О0, Оь Б2, Бз, Б5} соответствующие таблицы показаны в табл.2 и 3. Для создания информационной системы управления вводятся преобразования, правильность которых определяется леммой 4.

Лемма 4. О перестановке распознавателей. Если в цепочке СРВ присутствует подвыражение Л, • Д • • Д и предикаты (р,1, р,2, р,3..), входящие в распознаватель В.р не вычисляются в действии Д то ИСА цепочки Е„ * Д • Д будет функционально эквивалентна ИСА цепочки /?, • Д • • Д, при этом /?„= Я/бсЯр где операция & - есть операция конъюкции над предикатами распознавателей Я, и Яг

Аналог конвейерного разложения для управляющей структуры для цепочки СРВ показан на рис. 13. Действия Т)2 и Б] могут быть объединены на одном ярусе, так как Э2 не вычисляет элементарные предикаты, входящие в распознаватель, задающий условие вычисления Оь

Я. я2 Яз 1*4

Р1 - + - +

Р 2 + + + -

0 1 2 3 4

Р1 + + - - -

Р 2 + - - + -

Табл. 2. Матрица вхождения элементарных предикатов в распознаватели.

Табл. 3. Матрица вычислений элементарных предикатов в соответствующих действиях.

а). Цепочка: 0 • • (1 • • 3 • Л'з • 2 • Я^)* • 1 • Л'г • 4 • 5.

б). ИСК - информационная структура управления в виде конвейерного разложения:

0 13 2 14 5

Р2-

\И / АН .......

п /

^ Я2 Яз 1*4 И2 в). Эквивалентная цепочка, преобразованная в соответствии с леммой 4:

Рис.13. Конвейерное разложение схемы управления.

3.5 Дополнительные условия правильного разбиения. Пусть ИСА разбита на фрагменты и = {а0,, а°2, а'з .. }. Для удобства верхний индекс фрагмента означает его принадлежность соответствующей группе в = {фь <р2, фз .. }, см. пример (рис. 14). Пусть разбиение отвечает необходимому условию правильного разбиения. Тогда между фрагментами, принадлежащей группе, устанавливается частичный порядок, соответствующий дугам вершин ИСА, которые входят в фрагменты. Например, если существует дуга <хи у,> и X/ е а1 ь У1 е а'6, отношение порядка будет а'|<а'6. Частичный порядок устанавливает возможные последовательности «вычислений» фрагментов на АР или ПР группы (рис.15). Звезда Клини означает на рис.15 возможную рекурсию в ИСА. При восстановлении ИСА из СРВ каждой вершине х графа примитивно-рекурсивной ИСА можно поставить в соответствие распознаватель, который ему предшествует (если такой имеется). Поэтому каждому фрагменту соответствует некоторое множество распознавателей, соотнесённых вершинам фрагмента. Поэтому частичный порядок на множестве фрагментов определяет также частичный порядок выполнения распознавателей.

К4

Я"2 ЕС2 ф,:

Я;

ф2:

т а*5 гЛ и 8 а2]0

J *

Фз:

гД о3п

Рис. 14. Разбиение ИСА на фрагменты Рис. 15. Возможный порядок

«вычисления» фрагментов Лемма 5 о достаточном условии правильного разбиения ИСА па фрагменты определяется четырьмя правшами. 1 правило. Для выбранных фрагментов выполняется необходимое условие правильного разбиения. 2 правило. Множество распознавателей, соответствующее одному фрагменту

должно совпадать с множеством распознавателей, которые можно объединить по лемме о перестановке распознавателей операцией конъюкции для вершин фрагмента 3 правило. По крайней мере одна последовательность распознавателей, допустимая частичным порядком выполнения, должна входить в регулярное выражение для распознавателей, соответствующее ЛСА. 4 правило. Если условия 1, 2 и 3 выполняются для всех цепочек СРВ и заданных фрагментов, то выбранное разбиение является правильным

1-е правило проверяет «связанность» вычислений по данным. 2-е правило означает, что условия для вычисления фрагмента должны быть «вычислены заранее». 3-е правило означает, что управление вычислениями элементарных функций фрагментов в АР или в ПР должно быть синхронизировано с управлением, задаваемым ЛСА. Для примера ЛСА рис.9а для вершин Б] и Оз можно задать вид возможного фрагмента (рис.16). Фрагмент не нарушает необходимое условие правильного разбиения, но нарушает достаточное (условие 2), так как для управляющей структуры рис.136 элементарный предикат рь входящий в распознаватель Я2, вычисляется в действии и не может быть вычислен «заранее». Для вершин и составлен фрагмент, который удовлетворяет необходимому условию (рис.17).

элементарных функций, выбраной из элементарных функций, выбранных из

Рис. 16. Фрагмент состоит из информационной структуры

Рис. 17. Фрагмент состоит из информационной структуры

О, и Эз.

Б, и Б2.

3.6 Основные результаты главы. Технология «От алгоритма к аппаратно-программной реализации» представляет собой последовательность процедур, основанных на восьми формальных моделях: 1) логическая структура алгоритма (ЛСА), 2) информационная структура алгоритма (ИСА), 3) ЛСА в виде совершенных регулярных выражений (СРВ), 4) ярусно-параллельная форма (ЯПФ) ИСА, 5) многопроцессорные и конвейерные разложения ИСА, 6) модель синхронизации в виде сети Петри, 7) модель системы управления в виде информационной структуры вычисления предикатов, 8) модель правильного разбиения ИСА. Возможность применения процедур проектирования АПР обусловлена доказательством лемм: леммы 1 о необходимых условиях информационных связей между действиями ЛСА, леммы 2 о достаточных условиях информациионных связях между действиями ЛСА, леммы 3 о необходимых условиях правильного разбиения ИСА, леммы 4 о перестановке распознавателей в ЛСА, леммы 5 о достаточных условиях правильного разбиения ИСА. Фактически глава 3 содержит конструктивное доказательство теоремы о построении аппаратно-программного представления алгоритма, заданного исходной программой, и разбиениях, заданных проектировщиком. Теорема обеспечивает функциональную эквивалентность двух реализаций - реализации исходной программы и аппаратно-программной реализации.

В четвёртой главе представлены примеры разбиения на фрагменты и использования формальных моделей для проектирования АПР.

4.1 1-й пример разбиения ИСА продемонстрирован на алгоритме Быстрого преобразования Фурье (БПФ) из 8 точек. ИСА алгоритма представлена на рис.18. Вершины графа ИСА перегруппированы (см. рис.19) в соответствии с заданным разбиением ИСА на фрагменты. ИСА разбивается на функционально эквивалентные фрагменты, выделенные пунктиром. ИСА таких фрагментов называется шаблоном. Выбираемое разбиение является правильным, алгоритм БПФ может вычислить процессор с операцией шаблона.

Производится конвейерное однопроцессорное разложение ИСА по выбранному шаблону и реализуется схема процессора.

В табл.4 сравнивается энергопотребление, площади схемной реализации и частоты для технологии 0,18 микрон, соответсвующие процессорной схеме и схеме, в которой ИСА БПФ-8 реализуется аппаратно в виде конвейера. Рассматриваемые реализации имеют равную производительность.

Рис. 18. ИСА БПФ 8 точек. Рис. 19. Разбиение ИСА.

Частота, МГц Площадь схемы, 103*мкм2 Мощность, мВт

Конвейерная схема 125 140 30

Процессорная схема 1000 90 60

Табл.4. Оценки для конвейерной и процессорной реализаций.

4.2 2-й пример перехода от программы к программно-аппаратной реализации. Рассматривается алгоритм сжатия изображений JPEG2000. В программе алгоритма был выделен блок, который решено было реализовать в виде аппаратуры. С помощью специального программного обеспечения Spark из программы был выделен граф JICA блока. С помощью библиотеки Graphviz на языке Perl была написана программа преобразования ЛСА в ИСА. В

процессе разработки программы были использованы разработанные в диссертации формальные модели и соответствующие им автоматические процедуры. Модель ИСА была автоматически спроектирована в виде АР, описанной на SystemC. Остальная часть алгоритма исполнялась как обычная программа на С. Полученная АПР была протестирована на большом количестве изображений, чтобы убедиться в правильности преобразований программы на языке Perl. Все изображения были успешно закодированы в стандарте JPEG2000.

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

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

Для решения задачи проектирования аппаратно-программной реализации алгоритма, заданного исходной программой, в диссертации решены две основные задачи: 1) восстановления из программы информационной структуры алгоритма, 2) проверки правильности разбиения информационной структуры на фрагменты, которые могут выполняться аппаратно и программно на специализированных или универсальных процессорах. Для решения этих задач сформулированы и доказаны пять лемм, которые конструктивно доказывают теорему о построении аппаратно-программного представления алгоритма, заданного исходной программой, и разбиениях, заданных проектировщиком. Теоретические результаты и практика их применения для некоторых алгоритмов показывают, что на этом теоретическом фундаменте могут быть построены САПР, ориентированные на широкий класс алгоритмов, заданных исходной программой.

Основные результаты диссертации опубликованы в работах:

1. А.С.Лялин. Информационная технология «От алгоритма к аппаратуре» на примере аппаратной реализации БПФ. // Моделирование процессов управления. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2004. - С.203-210.

2. А.С.Лялин. Принцип асинхронного проектирования и информационная структура алгоритма. // Труды 12-й Всероссийской межвузовской конференции студентов и аспирантов «Микроэлектроника и Информатика» - 2005" / Моск. ин-т элек.-тех. -М., 2005.- С.223.

3. А.С.Лялин. Возможности асинхронного взаимодействия процессов для уменьшения энерговыделения при проектировании цифровой аппаратуры // Труды X Байкальской Всероссийской конференции «Информационные и математические технологии в науке технике и образовании» / ИСЭМ СО РАН. -Иркутск, 2005. - Часть 1 - С.249-251.

4. А.С.Лялин. Информационный анализ программных алгоритмов для реализации энергосберегающих вычислений // Моделирование процессов управления. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2006. - С.243-249.

5. А.СЛяпин. Возможности алгоритмического анализа для проектирования аппаратуры. // Труды десятой международной научной конференции «Актуальные проблемы твердотельной электроники и микроэлектроники» / ТРТУ-Таганрог, 2006, С. 149-152.

6. А.С.Лялин. Алгоритмический анализ для проектирования цифровой аппаратуры: автоматический подход // Труды 49-й научной конференции МФТИ, секция информатики / Моск. физ.-тех. ин-т. -М., 2006. - С.63-64.

7. А.С.Лялин. Автоматический алгоритмический анализ для проектирования цифровой аппаратуры // Труды IV международной научно-технической конференции «Фундаментальные проблемы радиоэлектронного приборостроения» / Моск. ин-т рад., элект. и авт., Москва, 2006. - Часть 2 -С. 176-179.

8. А.С Лялин. Методика проектирования вычислительных систем с аппаратно-программной архитектурой // Моделирование процессов обработки информации. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2007. - С.242-245

9. Alexander Lyalin. Formal methods of algorithm analysis for decreasing RTL-verification complexity // 9th International Conference «The experience of designing and application of CAD systems in microelectronics», CADSM 2007, Proceedings / Polyana, Ukraine, 2007 - P. 101-103.

10. А.С Лялин. Скрытые возможности интеллектуализации тестирования электронных цифровых систем // Информационные технологии моделирования и управления - 2007, №1(35) - С. 105-112.

11. А.С. Лялин Скрытые возможности интеллектуализации проектирования электронных цифровых систем. // Системы управления и информационные технологии -2007, №4.1(30). - С. 166-169.

Заказ № 189/10/08 Подписано в печать 15 10 2008 Тираж 100 экз Уел пл 1,5

(>■ ООО "Цифровичок", тел (495) 797-75-76, (495) 778-22-20 )} www.cfr.ru; e-mail, info@cfr.ru

ГЛАВА 1. МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ.

1.1. Возможные реализации алгоритма.

1.2. Традиционные методы проектирования.

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

1.4. Автоматизация проектирования.

1.5. Неформальное изложение технологии проектирования.

1.6. Основные результаты теории схем программ.

1.7. Современные системы компилляции.

Задачей проектирования аппаратно-программных систем является переход от описания реализуемых алгоритмов к аппаратно-программной реализации (АПР), которая эти алгоритмы вычисляет (рис. 1).

Рис. 1. Формулировка основной задачи.

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

Рис.2. От содержательной задачи к аппаратно-программному комплексу.

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

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

Объект исследования.

Объектом исследования являются математические модели, которые могут использоваться для описания этапов проектирования аппаратно-программных реализаций (АПР) и которые могут быть поддержены системами автоматизации проектирования. При этом под аппаратной реализацией (АР) понимается набор схем в виде соединённых между собой функциональных элементов, таких как мультиплексоры, триггеры, элементы «И», «ИЛИ» и т.д.; под программной реализацией (ПР) понимается вычисление части функции алгоритма программой специального или универсального процессора (рис.3).

Рис. 3, поясняющий выбор объекта исследования.

Общие проблемы современных методов проектирования.

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

Техническое задание:

• словесное описание алгоритма

• технические условия

I Математическая П \ модель в виде программы

Функциональная спецификация ппаратная еализация

Программная )еализация

Неформальный, неавтоматический переход

Рис.4. Переход от описания алгоритма к математической модели.

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

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

Вторая проблема. Алгоритмы, описанные в содержательной задаче, могут иметь различные способы их разделения на аппаратную (АР) и программную реализацию (ПР). В традиционных технологических маршрутах проектирования принято фиксировать в ФС (рис.4) функциональность аппаратного и программного обеспечения, что объясняется тем, что в настоящее время все известные системы автоматизированного проектирования (САПР) построены на принципе заранее придуманной проектировщиком аппаратной и программной реализации (АПР), описанных на специальных формальных языках (например, на языках Си, Уеп^ или УНБЬ). Отсутствие механизмов САПР для поддержки исследования различных АПР алгоритма не позволяет вести поиск лучшей из них.

Решаемые проблемы в диссертации.

Решению перечисленных проблем посвящена данная работа.

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

• Решается проблема преобразования схемы программы в виде логической структуры алгоритма (ЛСА) в примитивно-рекурсивную информационную структуру алгоритма (ИСА) для тех алгоритмов, которые это допускают.

• Рассматривается модель алгоритма в виде ИСА. Задача разделения алгоритма, заданного программой, сводится к поиску разбиения ИСА, отвечающему набору правил. Совокупность правил формулируется в виде лемм.

Научная новизна работы.

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

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

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

Для решения поставленных задач использованы следующие формальные модели:

1) логическая структура алгоритма (ЛСА), которую задаёт исходная программа,

2) информационная структура алгоритма (ИСА), которая описывает функцию программы,

3) визуальные формы ИСА, удобных для анализа: ярусно-параллельные формы (ЯПФ), многопроцессорные и конвейерные разложения ИСА,

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

5) модель информационной структуры управления процессами (ИСЯ).

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

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

История исследований.

Исследования над методами и моделями для автоматизации разработки программно-аппаратных комплексов начались в 2003 году и в основном проводились в рамках работы над грантом РФФИ № 05-07-90406 «Экспертная система для информационной поддержки проектирования энергосберегающих вычислительных архитектур».

Логика построения работы и её краткое содержание.

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

Во второй главе рассматриваются формальные модели информационной структуры алгоритма и логической структуры алгоритма. Логическая структура алгоритма представляется в виде совершенного регулярного выражения (СРВ). Даётся формальное определение информационной структуры алгоритма (ИСА). На примере функции Фибоначчи рассматривается примитивно-рекурсивная информационная структура. Указывается, что примитивная рекурсия реализуема аппаратно в виде обратных связей в аппаратной схеме. Рассматриваются последовательности действий (или операторов), которые может порождать конечный автомат ЛСА, и для последовательностей восстанавливаются информационные связи между действиями. Через восстановление информационных связей: 1) устанавливается функциональная эквивалентность двух последовательностей, 2) «восстанавливается» ИСА последовательности из действий. Конструктивно рассматривается, как из ЛСА можно восстановить примитивно-рекурсивную PICA. Даются формальные определения визуальным формам представления ИСА: Ярусно-паралелльной форме (ЯПФ) и конвейерному разложению. Конструктивно описывается процедура автоматической генерации аппаратной (или программной) реализации из формально определённого конвейерного разложения. Рассматривается выделение фрагментов ЯПФ для аппаратного и программного исполнения.

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

Теоретический материал разбивается на следующие разделы:

1. Анализ возможных связей ИСА. Лемма о необходимом условии информационных связей.

2. Анализ фактических связей ИСА. Лемма о достаточном условии информационных связей.

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

4. Лемма о необходимом условии правильного разбиения.

5. Управляющая структура алгоритма (HCR).

6. Лемма о перестановках распознавателей в Л CA.

7. Лемма о достаточном условиях правильного разбиения.

Дополнительно рассматривается преобразование «раскрутка» циклов, которая может упростить анализ программы реализуемого алгоритма.

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

В четвёртой главе представлены примеры использования разработанных методов и моделей для разработки АПР некоторых алгоритмов. Рассмотрено влияние различных вариантов разделения алгоритма на физические характеристики получаемых АПР. Даны относительные оценки влияния различных архитектур АПР на энергопотребление и площадь схемной реализации. С теоретической точки зрения исследованы причины превосходства технологии Transmeta Crusoe по сравнению с традиционной архитектурой х86.

4.5. Основные выводы главы 4.

В главе были рассмотрены примеры использования разработанных в диссертации формальных методов и моделей для реализации алгоритмов быстрого преобразования Фурье и дискретного вейвлет-преобразования. При этом использовалось свойство программы алгоритмов — возможность «раскрутки» циклов. В результате алгоритмы были представлены в виде «проволочной» информационной структуры алгоритма, которые допускают конвейерную реализацию, в которой «проволочная» информационная структура опредляет электрические цепи между функциональными элементами. Были рассмотрены возможные разбиения алгоритмов и выбраны варианты правильных разбиений, в которых информационная структура разбивалась на функционально эквивалентные некоторому вычислительному шаблону фрагменты. Была проведена процедура конвейерного разложения, по которой автоматически сгенерированы аппаратные реализации специализированных процессоров с функцией шаблона. Результаты сравнения физических характеристик конвейерной реализации и реализации со специальным процессором позволяют убедиться, что у алгоритма может быть несколько вариантов аппаратно-программной реализации, каждая из которых будет иметь собственные физические характеристики. Таким образом, на характеристики реализации можно влиять через преобразования, описанные в диссертации.

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

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

Заключение.

Основным практическим результатом диссертации является предложенная технология проектирования аппаратно-программных реализация алгоритмов [20, 21]. Этапы технологии представлены на рис.65а. Алгоритм, заданный текстом программы, методами лексического и синтаксического анализа переводится в промежуточное представление. Промежуточное представление с помощью методов, описанных в диссертации, переводится в конечный набор конечных цепочек выполнения действий (операторов) программы. Из конечных цепочек методом интерпретации действий элементарными функциями и конструктивно описанным в диссертации методом восстановления информационных связей строятся «проволочные» информационные структуры цепочек (так называемые Wire Nets). «Проволочные» информационные структуры представляются в виде удобных визуальных форм, на которых экспертом выделяются фрагменты для аппаратного или программного исполнения. Такое разбиение информационной структуры переводится автоматически в аппаратную, программную реализации, систему управления и синхронизации (рис.65а).

Процесс разбиения информационной структуры повторяется несколько раз пока не будет найдена реализация с физическими характеристиками, которые соответствуют техническому заданию. На рис. 656 изображён итеративный процесс поиска эффективной реализации. Эксперт задаёт разбиение, система автоматизированного проектирования автоматически проверяет правильность разбиения, и если оно не правильно, предлагает эксперту задать новое. Если разбиение правильное, автоматически генерируется аппаратно-программное описание, которое моделируется средствами традиционных САПР. В результате могут быть получены физические характеристики системы, которые сравниваются с техническими условиями. В случае, если аппаратно-программная реализация не соответствует техническим условиям — эксперту предлагается задать новое разбиение. а). Этапы технологии.

ИСА а). Поиск аппаратно-программной реализации.

Рис.65. Технология проектирования.

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

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

1. Ахо А. Теория синтаксического анализа, перевода и компиляции: Пер. С англ. М.: МИР, 1978 - 486 с.

2. Варшавский В.И. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. М.: Наука, 1986. - 400 с.

3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2003-384 с.

4. Ершов А.П. Теория программирования и вычислительные системы — М.: Знание, 1972-64 с.

5. Котов В.Е. Сети Петри. -М.: Наука, 1984. 160 с.

6. Котов В.Е., Саберфелъд В.К. Теория схем программ. М.: Наука, 1991. — 248 с.

7. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984-264 с.

8. Серебряков В.А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования М.: МЗ-Пресс, 2003 - 296 с.

9. Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ-М.: Мир, 1989.-264 с.

10. Ершов А.П. Об операторных схемах над общей и распределённой памятью // Кибернетика. 1968, № 4. - С.63-71.

11. Ершов А.П. Об операторных схемах Янова // Проблемы кибернетики: Сб. Статей, вып. 20 М.: Наука, 1967. -С. 181-200.

12. Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики: Сб. Статей. вып.27.-М.: Наука, 1973. С. 87-110.

13. Котов В.Е., Нарилъяни A.C. Асинхронные процессы и компьютерная память. // Кибернетика, 2(3) М, 1966 - С. 64-71

14. Лялин A.C. Информационная технология «От алгоритма к аппаратуре» на примере аппаратной реализации БПФ. // Моделирование процессов управления. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2004. -С.203-210.

15. Лялин A.C. Принцип асинхронного проектирования и информационная структура алгоритма. // Труды 12-й Всероссийской межвузовской конференции студентов и аспирантов «Микроэлектроника и Информатика» 2005" / Моск. ин-т элек.-тех. - М., 2005. - С.223.

16. Лялин A.C. Информационный анализ программных алгоритмов для реализации энергосберегающих вычислений // Моделирование процессов управления. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2006. -С.243-249.

17. Лялин A.C. Возможности алгоритмического анализа для проектирования аппаратуры. // Труды десятой международной научной конференции «Актуальные проблемы твердотельной электроники и микроэлектроники» / ТРТУ-Таганрог, 2006, С.149-152.

18. Лялин A.C. Методика проектирования вычислительных систем с аппаратно-программной архитектурой // Моделирование процессов обработки информации. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2007. С.242-245

19. Лялин A.C. Скрытые возможности интеллектуализации тестирования электронных цифровых систем // Информационные технологии моделирования и управления — 2007, №1(35) С.105-112.

20. Лялин A.C. Скрытые возможности интеллектуализации проектирования электронных цифровых систем. // Системы управления и информационные технологии -2007, №4.1(30). С. 166-169.

21. Слуцких А., Эйсымонт Л. Российский суперкомпьютер с глобально адресуемой памятью. // Открытые системы. 2007, № 9. - С. 42-51.

22. Черников В., Виксне П., Шелухин А., Шевченко П., Панфилов А., Косорукое Д., Черников А. Семейство процессоров обработки сигналов с векторно-матричной архитектурой NeuroMatrix®" //Компоненты и технологии. -2006, № 6, 2006 С. 1-6.

23. Шахнович И. Высокопроизводительные вычислительные архитектуры. Возрождение традиций. // Электроника НТБ. 2008, № 4 - С.81-83.

24. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики: Сб. Статей, вып. 1 -М.: Наука, 1958, С.75-127.

25. Gupta S., Gupta R., Dutt N., Nicolau A. SPARK: A Parallelizing Approach to the High-Level Synthesis of Digital Circuits. Springer, 2004 - 262 p.

26. Pellerin D., Thibault S. Practical FPGA Programming in C. Prentice Hall, 2005 - 464 p.

27. Potop D., Edwards S., Berry G. Compiling Esterel. Springer, 2007 - 335 p.

28. Halfhill T. Transmeta breaks x86 low power barrier I I Microprocessor Report -2000, 14(2) P.9-18

29. Benveniste A., Caspi P., Edwards S., Halbwachs N., Le Guernic P., de Simone R. The synchronous languages twelve years later. // Proceedings of the IEEE -2003, 91(1)-P.64-83.

30. Berry G., Kishinevsky M., Singh S. System level design and verification using synchronous language. // Proceedings of the IEEE/ACM international conference on Computer-aided design -2003 P. 433-449

31. Boussinot F., de Simone, R. The Esterel language. Proceedings of the IEEE — 1991, 79(9)-P.1293-1304.

32. Lorenz M., Leipers R., Marwedel P., Drager T., Fettweis G. Low energy DSP code generation using a Genetic Algorithm // Proceedings of the international conference on Computer Design 2001 - P. 431 - 437.

33. Flautner K., Mudge T. Vertigo: Automatic Performance-Setting for Linux // Proceeding of Symposium on Operating Systems Design and Implementation — ACM, 2002-P. 105-116.

34. Chakrapani L., Gyllenhaal J., Hwu W., Mahlke S., Palem K., Rabbah R. Trimaran: an Infrastructure for Research in Instruction-Level Parallelism I I In Lecture Notes in Computer Science Springer-Verlag, 2005, Volume 3602, -P.32-41.