Задачей проектирования аппаратно-программных систем является переход от описания реализуемых алгоритмов к аппаратно-программной реализации (АПР), которая эти алгоритмы вычисляет (рис. 1).
Рис. 1. Формулировка основной задачи.
Переход от описания алгоритмов к АПР определяется выбранной методологией, то есть совокупностью моделей и методов, используемых в технологическом маршруте перехода от описания содержательной задачи до корректно функционирующего аппаратного и программного обеспечения (рис.2).
Рис. 2. От содержательной задачи к аппаратно-программному комплексу.
Содержательная задача описывает функции алгоритмов, вычислимые проектируемой АПР, и набор рекомендаций по выходным характеристикам будущей системы (энергопотребление, площадь схемной реализации, производительность). Содержательную задачу ещё называют техническим заданием.
Методология структурно состоит из моделей описания содержательной задачи и некоторого количества этапов, на каждом из которых осуществляется преобразование над моделями. Когда техническое задание накладывает на разрабатываемые системы жёсткие нормативы по энергопотреблению, производительности, размеру и т. д. правильный выбор методологии становится особенно важным, так как этот выбор определяет время проектирования. Время проектирования зависит от временных издержек методологических переходов. Поэтому в настоящее время особое внимание уделяется изучению формальных моделей и методов автоматизации, которые позволяют сократить эти временные издержки.
Объект исследования.
Объектом исследования являются математические модели, которые могут использоваться для описания этапов проектирования аппаратно-программных реализаций (АПР) и которые могут быть поддержены системами автоматизации проектирования. При этом под аппаратной реализацией (АР) понимается набор схем в виде соединённых между собой функциональных элементов, таких как мультиплексоры, триггеры, элементы «И», «ИЛИ» и т. д.- под программной реализацией (ПР) понимается вычисление части функции алгоритма программой специального или универсального процессора (рис.3).
Рис. 3, поясняющий выбор объекта исследования.
Общие проблемы современных методов проектирования.
Основой традиционной методологии является функциональная спецификация (ФС). В ФС на основании заданного технического задания и своего опыта эксперты описывают модели.
Техническое задание:
• словесное описание алгоритма.
• технические условия.
I Математическая П модель в виде программы.
Функциональная спецификация ппаратная еализация.
Программная)еализация.
Неформальный, неавтоматический переход.
Рис. 4. Переход от описания алгоритма к математической модели.
Первая проблема заключается в том, что в традиционной методологии спецификация является полу-формальным документом, который составляется экспертами на основании их опыта и интуиции. Спецификация определяет функциональность аппаратного и программного обеспечения устройства с учётом технического задания. В действительности, соответствие техническому заданию можно проверить только на поздних этапах разработки АПР. Поэтому правильно составленная экспертами спецификация не гарантирует, что система будет работать корректно. Данная проблема традиционно решается использованием нескольких моделей устройства (математическая модель устройства в виде программы, модель аппаратного и программного обеспечения), имитационное моделирование которых служит для доказательства непротиворечивости АПР техническому заданию.
Из-за того, что описание в функциональной спецификация является неформальным, в каждую модель (рис.4) могут быть внесены ошибки, обусловленные человеческим фактором (ошибки экспертов при реализации моделей). Исправление таких ошибок и тестирование исправлений существенно увеличивает время разработки.
Вторая проблема. Алгоритмы, описанные в содержательной задаче, могут иметь различные способы их разделения на аппаратную (АР) и программную реализацию (ПР). В традиционных технологических маршрутах проектирования принято фиксировать в ФС (рис.4) функциональность аппаратного и программного обеспечения, что объясняется тем, что в настоящее время все известные системы автоматизированного проектирования (САПР) построены на принципе заранее придуманной проектировщиком аппаратной и программной реализации (АПР), описанных на специальных формальных языках (например, на языках Си, Уеп^ или УНБЬ). Отсутствие механизмов САПР для поддержки исследования различных АПР алгоритма не позволяет вести поиск лучшей из них.
Решаемые проблемы в диссертации.
Решению перечисленных проблем посвящена данная работа.
• В качестве формального описания алгоритма принимается схема моделирующей алгоритм программы.
• Решается проблема преобразования схемы программы в виде логической структуры алгоритма (ЛСА) в примитивно-рекурсивную информационную структуру алгоритма (ИСА) для тех алгоритмов, которые это допускают.
• Рассматривается модель алгоритма в виде ИСА. Задача разделения алгоритма, заданного программой, сводится к поиску разбиения ИСА, отвечающему набору правил. Совокупность правил формулируется в виде лемм.
Научная новизна работы.
В работе рассматривается возможность построения САПР, основанной на совершенно ином принципе проектирования по сравнению с существующими методами (рис.4). Алгоритмы, заданные обычной программой и определяющие функциональность разрабатываемой аппаратно-программной системы, автоматически преобразуются в специальные визуальные формы, удобные для проектировщика, на которой он выделяет области для аппаратного и программного (на специальных процессорах) исполнения. САПР автоматически проверяет правильность (реализуемость) такого разбиения и строит схему синхронизации процессов, протекающих в аппаратной и программной частях, буферную память и систему управления.
Такая автоматизированная технология проектирования, названная в работе «от программы к аппаратно-программной реализации», даёт возможность, по сравнению с существующими САПР, вовлечь в поле проектирования огромный запас уже созданных программ, и автоматизировать поиск лучшей АПР.
Научная новизна работы заключается в том, что в диссертации построены и исследованы формальные модели и методы анализа программ алгоритмов, которые могут использоваться для решения задачи проектирования их аппаратно-программной реализации.
Для решения поставленных задач использованы следующие формальные модели:
1) логическая структура алгоритма (ЛСА), которую задаёт исходная программа,.
2) информационная структура алгоритма (ИСА), которая описывает функцию программы,.
3) визуальные формы ИСА, удобных для анализа: ярусно-параллельные формы (ЯПФ), многопроцессорные и конвейерные разложения ИСА,.
4) модель синхронизации процессов в аппаратной и программной частях и передачи информации через буферную память,.
5) модель информационной структуры управления процессами (ИСЯ).
Доказаны утверждения (леммы) о свойствах этих моделей, которые позволяют строить автоматические процедуры анализа, преобразований и конструирования АПР алгоритма, описанного исходной программой. Объединение лемм представляет собой конструктивно доказанную теорему, устанавливающую функциональную эквивалентность исходной программы и построенной аппаратно-программной реализации (АПР).
Представленные результаты получены самостоятельно (являются оригинальными), представляют научную новизну работы и выносятся на защиту.
История исследований.
Исследования над методами и моделями для автоматизации разработки программно-аппаратных комплексов начались в 2003 году и в основном проводились в рамках работы над грантом РФФИ № 05−07−90 406 «Экспертная система для информационной поддержки проектирования энергосберегающих вычислительных архитектур».
Логика построения работы и её краткое содержание.
В первой главе уточняется основная задача диссертации. Рассматриваются традиционные методы проектирования аппаратно-программных реализаций и указываются их недостатки. Кратко описываются перспективные методы проектирования, которые включают в себя языки формальных спецификаций, и использование программы алгоритма в качестве формальной модели алгоритма. Неформально излагается этапы предлагаемой в диссертации технологии проектирования. Рассматриваются основные результаты теории схем программ и делается вывод о возможности использования моделей теории для разработки технологии. Так как современные программы далеки от процедурного описания" программ, исследованных в теории схем программ, рассматриваются современные системы компилляции.
Во второй главе рассматриваются формальные модели информационной структуры алгоритма и логической структуры алгоритма. Логическая структура алгоритма представляется в виде совершенного регулярного выражения (СРВ). Даётся формальное определение информационной структуры алгоритма (ИСА). На примере функции Фибоначчи рассматривается примитивно-рекурсивная информационная структура. Указывается, что примитивная рекурсия реализуема аппаратно в виде обратных связей в аппаратной схеме. Рассматриваются последовательности действий (или операторов), которые может порождать конечный автомат ЛСА, и для последовательностей восстанавливаются информационные связи между действиями. Через восстановление информационных связей: 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) задача установления правильности разбиения информационной структуры. Для решения этих двух задач были исследованы свойства математических моделей логической структуры алгоритма и информационной структуры алгоритма. Результаты исследования были сформулированы в пяти леммах. Совокупность сформулированных и доказанных лемм является конструктивно доказанной теоремой о построении аппаратно-программного представления алгоритма, заданного исходной программой, и разбиениях, заданных проектировщиком.
Таким образом, была предложена технология, которая отличается от традиционных методов проектирования. Технология была подцержена набором формальных моделей и методов, исследованных в диссертации.
