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

од

московским

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В .ЛОМОНОСОВ А

Факультет вычислительной математики и кибернетики

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

МАШЕЧКИН Игорь Валерьевич

"Многофункциональная , адаптируемая система кросс-про) раммироваиия"

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

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

Москва 1998

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

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

член корреспондент РАН, доктор физико-математических наук, профессор Г.Г.Рябов

доктор физико-математических наук профессор А.Н.Томилин

доктор физико-математических наук профессор С.Ю.Соловьев

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

Московский институт радиоэлектроники и автоматики

Защита диссертации состоится 20 марга 1998 года в 11 часов на заседании Диссертационного Совета Д 053.05.38 при Московском государственном университете имени М.В .Ломоносова по адресу: 119899, Москва, Воробьевы горы, МГУ, факультет ВМиК аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан "17" февраля 1998 г.

Ученый секретарь Диссертационного Совета

профессор Н.П.Трифонов

Актуальность темы. Тема настоящей работы непосредственно

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

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

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

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

Второе. Неотъемлемой характеристикой современных вычислительных систем является широкое использование параллелизма при обработке информации. От локального параллелизма, заложенного внутри процессорных элементов (на

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

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

Характерной особенностью современных вычислительных систем, объединяющих в себе последние две тенденции, является формирование класса специализированных вычислительных систем, обладающих специфическими архитектурными особенностями, позволяющими исиользовать данные ЭВМ для эффективного решения конкретных типов задач. Это ведет к расширению понятия специализированной ЭВМ от систем, применяемых в управлении техническими объектами, до специализированных систем, ориентированных на решение сложных задач математического моделирования, информационного поиска и доступа к данным, которые также как и управляющие вычислительные системы, имеют значительные особенности в архитектуре и программировании. Примерами подобных ВС могут служить транспьютерные системы, процессорные матрицы, вычислительные системы обработки графической информации, NON STOP системы и т.п. С точки зрения инструментальных средств программирования специализированных вычислительных систем, актуальным является решение проблемы оптимизации программ, учитывающей архитектурные особенности целевых ЭВМ.

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

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

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

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

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

Методы исследований. Настоящие исследования основываются на

анализе современных архитектур вычислительных систем, теоретических основах компиляции, теории выявления зависимостей и оптимизации программ, теории генерации кода. Благодарности. Автор выражает глубочайитую благодарность всем тем студентам, аспирантам и сотрудникам кафедры АСВК факультета ВМиК МГУ, кто более 10 лет принимал непосредственное участие в данных исследованиях. В первую очередь хочется отметить неоценимый вклад Т.И.Даниярходжаева, В.Ю.Маслова, Г.В.Нишанова, С.Ш.Артыгалина, Е.Ю.Марьяскина. Апробация работы. Основные результаты работы докладывались на следующих семинарах, конференциях и совещаниях:

• на IV конференции молодых ученых закавказских республик(Тбилиси, 1986г.);

• на Всесоюзной конференции "Методы трансляции и конструирования программ" (Новосибирск, 1988г.);

• на VII международном семинаре "Проблемы информатики и ее применения в управлении, обучении и научных исследованиях" (НРБ, София, 1999г.)

• на конференции ДИАЛОГ 87" (Тбилиси 1988г.);

• на расширенном заседании семинара института прикладной математики им.И.Н.Векуа (Тбилиси 1989г.);

• на научно-исследовательском семинаре института проблем кибернетики АН СССР (Москва, 1989г.);

• на ИХ международном семинаре "Проблемы информатики л ее применения в управлении, обучении и научных исследованиях" (Москва, 1989г.)

• на заседании рабочей группы по локальным вычислительным сетям (Смоленск, 1989г.);

• на 15-всесоюзной школе-семинаре по вычислительным сетям. (Москва. 1990г.);

• на IX международном семинаре "Проблемы информатики и ее применения в управлении, обучении и научных исследованиях" (НРБ, София, 1990г.)

• на научно-исследовательском семинаре вычислительного центра Сычуаньского университета (КНР, Чэнду, 1990г.);

• на научно-исследовательском семинаре Сычуаньского политехнического института (КНР, Чэнду, 1990г.);

• на научно-исследовательском семинаре вычислительного центра Пекинского университета (КНР, Пекин, 1991г.);

• на всесоюзной конференции смешанные вычисления и преобразования программ. (Новосибирск, ВЦ СОАН СССР, 1991г.);

• Совещание по программированию и математическим методам решения физических задач (Дубна, 1993г.);

• на семинаре компании Votek (США, Огайо, Коламбус, 1993г);

• на семинаре компании AT&T (США, Огайо, Коламбус, 1996г);

• на Ломоносовских чтениях (МГУ, факультет ВМиК 1997г.);

• на Московском городском семинаре по программированию под руководством М.Р.Шура-Бура (1997г.);

• на научно-исследовательском семинаре кафедры АСВК факультета ВМиК.

Настоящая работа поддерживалась в соответствие с Программами Правительства России: "Информатизация России", "Университеты России", "Российский фонд фундаментальных исследований". Публикации. По материалам диссертации опубликовано 28 печатных работ.

Объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Постановка задачи. Исследование и разработка методов построения инструментальных средств программирования современных вычислительных систем, адаптируемых к конкретным архитектурам ЭВМ и предметным областям.

Содержание работы.

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

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

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

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

Далее в главе рассматривается система кросс-транслнторов, позволяющая использовать в качестве инструментальных средств программирования группу традиционных языков высокого уровня, таких как: СИ, СИ++, ПАСКАЛЬ, ФОРТРАН, МОДУЛА-2, ОБЕРОП. Отличительной чертой организации трансляторов для этих языков является выделение машинонезависимого этапа обработки исходных программ и перевода их в нотацию единого машинонезависимого промежуточного языка - Унифицированного Промежуточного Представления (УТТП). Данное промежуточное представление разрабатывалось на основе анализа и обобщения семантических свойств наиболее распространенных процедурных и объектно-ориентированных языков программирования. УПП является модульным промежуточным языком, обладающим синтаксисом, который не требует сложного анализа при распознавании конструкций. Семантика конструкций УПП, по своей сути, соответствует семантике конструкций группы входных языков системы кросс-трансляторов, что определяет возможность эффективной генерации и оптимизации кода. Средствами УПП возможно, машинонезависимым образом, представлять конструкции управления и обработки данных исходных протрамм. УПП имеет средства отображения параллельной обработки информации, что позволяет с одной стороны, интерпретировать соответствующие

конструкции входных языков, с другой, генерировать код для векторных ЭВМ.

В главе рассматривается схема функционирования системы кросс-трансляторов, которая состоит в следующем.

На первом этапе исходная программа переводится кросс-транслятором в форму Villi. При этом полностью осуществляется лексический и синтаксический анализ, а также частично проводится семантический анализ. В результате обработки программы, написанной на одном из входных языков системы кросс программирования образуется соответствующий ей модуль, в котором через конструкции УПП отображены объекты исходной программы и действия над ними, сформирована специализированная база данных, необходимая для отладки программ в терминах входных языков. В модуле УПП специфицированы обращения к стандартным библиотекам языков, что дает возможность стыковки с системами программирования и их библиотеками, размещенными на объектных ЭВМ или с кросс библиотеками, размещенными на инструментальной ЭВМ. Данный этап является открытым для расширения количества входных языков - за счет использования единого промежуточного представления. Включение нового языка в систему будет заключаться в разработке транслятора данного языка в УПП.

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

На третьем этапе работы осуществляется машинно-ориентированная обработка программы - генерация модуля в кодах объектной ЭВМ, машинно-ориентированная оптимизация. Для генерации кода в системе разработан и используется алгоритм оптимальной генерации кода вычисляемых выражений. Оптимизация при генерации кода осуществляется в пределах одного

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

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

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

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

2. На уровне Машиионезависимого интерпретатора происходит выполнение команд, не требующих связи (информационной или по управлению) с объектной ЭВМ, к таким командам можно отнести просмотр текста оператора или функции. Команды, выполнение которых зависит от объектной ЭВМ, преобразуются Машинонезависимым интерпретатором в форму, соответствующую протоколу связи с Машиноориентированным интерпретатором. Например, команда "установить контрольную точку на операторе" преобразуется к виду: "установить контрольную точку по адресу, содержащемуся в записи информационной таблицы с данным дескриптором", т.е. при данном преобразовании команды будет найдено соответствие между номером указанного оператора программы и дескриптором записи информационной таблицы, в которой содержится адрес начала оператора в памяти объектной ЭВМ.

3. Третий уровень - Машинно-ориентированный интерпретатор преобразует полученный запрос в адресную форму и передает его Исполняющей системе.

4. На уровне Исполняющей системы происходит итоговое выполнение примитивов, обеспечивающих выполнение базовых действий по отладке: установка и снятие контрольной точки по адресу; чтение и запись содержимого памяти программы по адресу; пошаговое выполнение машинной команды и т.д. Реализация Исполняющей системы зависит от операционного окружения, работающего на объектной ЭВМ. В частности Исполняющая система может быть встроена в имитационный комплекс объектной ЭВМ.

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

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

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

УПП - программа представляет собой совокупность нескольких модулей. Каждый модуль состоит из функций и операторов, объявляющих глобальные объекты. Обобщенная структура УПП представлена на Рис. 1.

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

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

Разделение объектов на классы основывается на различии во времени существования значений объекта, в видимости объекта из различных точек программы, в дисциплине размещения значений в памяти. В УПП представлены следующие классы: EXPORT, IMPORT, COMMON, FORMAI,, STATIC, AUTOMATIC, REGISTER, CON LOC, STR_OFFS, TYPE DEF, среди которых есть классы, традиционно используемые в языках высокого уровня, а также классы, характерные для УПП. К последним, к примеру, можно отнести CONLOC - объект этого класса есть константа, которая имеет значение и не имеет адреса или TYPE_DEF - класс, называемый контейнер типа, используется для объявления объекта, являющегося объявлением нового типа.

Унифицированное Промежуточное Представление

Л

Объекты

Объект -именованная в УПП сущность (константа, область памяти, описание типа). В пределах модуля все объекты имеют единую нумерацию, которая строится по стековому признаку

Модуль

1

Выражения

Операторы

Типы

Классы

различие в представлении данных, операциях над ними

дисциплина размещения объектов в памяти, видимость, существование объектов в других модулях УПП -программы

Выполняемые операторы

I

Невыполняемые операторы

1

Средства векторной

вычислить выражение перейти по метке

объявить метку

условное

ветвление

вариантное

ветвление

параметрическ

ийцикл

закончить

выполнение

функции

закончить

выполнение

программы

• описание функции • векторное расширение

« начало/конец операндов

оператора языка (использование

высокого уровня элемента вектора,

• комментарий линейная форма от

• экспортируемый, переменных циклов)

общий, • скалярные/векторные

импортируемый, циклы

локальный, » вызов функции без

статический, побочных эффектов

автоматический • вычисление

объект, формальный выражения без

параметр, локальная побочных эффектов

константа • вычисление

• описатель типа выражения под маской

• описатели

структур/объединений

• уничтожение описаний

операнды (константа, размер типа, строка, сохраненный результат, значение, адрес, смещение объекта, локальная -база) унарные операции (приведение к типу, битовое /логическое отрицание, изменение знака, сохранение результата) бинарные операции (арифметические, битовые, сравнения, логические операции, условного вычисления, последовательности) вызов функции

Рис. 1 Унифицированное промежуточное представление

Тип объекта определяет множество операций, применимых к объекту, размер, требования на выравнивание по границам элементарных единиц памяти. Типы У1Ш состоят из так называемых простых типов, большинству из которых соответствуют простые типы данных традиционных языков высокого уровня, а также сложных типов. Сложные типы УПП состоят из группы указательных типов в которую входят: указатель на объект простого типа (POINTER; следует отметить, что указатель, в общем случае не является адресом); обобщенный адрес - указатель на значение произвольного типа (ADDRESS); адрес машинной инструкции (I_ADDRESS) - данный тип позволяет оптимизировать обработку адресной арифметики в случае специализированных вычислительных систем, имеющих раздельные адресные пространства команд и данных; макроподстановка типа (TYPE_USE NUMBERJ6)

Рассмотрим пример в котором представлено соответствие фрагмента программы на языке Си конструкциям УПП.

Пример 1. /* fir St. с */ ftoat а;

void main (intargc, char *argv[]) {

static int b; char c;

register int r;

}

Результат трансляции из Си в УПП.

00 "first.c" :7

01 FILENAME "first.c"

02 EXPORT ObjNum=0 "a" AREA SIZEOF REAL SIMPLE NULL

03 FUNC BEGIN

04 EXPORT ObjNum—1 "main " ENTRY

05 FORMAL ObjNum=2 "argc" AREA SIZEOF 1NT_SIMPLE NULL

06 FORMAL ObjNum ~3 "argv " AREA SIZEOF ADDRESS NULL 07STATIC 0bjNum=4 "b" AREA SIZEOFINTJSIMPLENULL

08 AUTOMATIC ObjNum=5 "c" AREA SIZEOFINTJBYTENULL

09 REGISTER ObjNum=6 "r" AREA SIZEOF INT_SIMPLE NULL

10 REMOVE :5 ObjNum =2

11 NULL

Пояснение. В строке (00) указано имя модуля (в случае Си именем модуля считается имя файла, содержащего исходный текст программы) и максимальное число одновременно видимых объектов плюс 1. Строка (01) - имя исходного файла. В строке (02) объявляется экспортируемая переменная а, занимающая область памяти размером, равным размеру типа REAL SIMPLE; она не инициализируется. В языке С все описываемые нестатические глобальные объекты являются по умолчанию экспортируемыми. В строке (03) объявляется начало описания тела функции. В следующей строке объявляется ее имя "main", как точка входа. Строки (05) и (06) описывают формальные параметры функции. Обратим внимание на то, что второй параметр имеет тип ADDRESS. Строки (07) - (09) описывают локальные переменные функции. Оператор REMOVE в строке (10) удаляет из таблицы объектов 5 локальных переменных. Хотя переменная Ь, описана как static, ссылка на неё в таблице объектов будет удалена! Это не ошибка, т.к. таблица объектов - обозначает только, область видимости. Размещением же переменной будет заниматься генератор кода. Строка (11) - конец описания тела функции.

Рассмотрим короткий пример, иллюстрирующий использование TYPE_DEF и TYPEUSE.

Пример 2.

/* фрагмент программы на языке Си */

typedefint *pint; typedef float **ppfloat; pint PINT; ppfloat PPFLOAT;

Результат трансляции в УПП. Будем считать, что к моменту обработки описания типа внутренний номер объекта (ObjNum) был равен 100.

TYPE DEF ObjNum=Wl "pint" DTYPE POINTER INT_SIMPLE TYPE_DEF ObjNum=W2 "ppfloat" DTYPE ADDRESS EXPORT ObjNum=103 "PINT" AREA SIZEOF TYPEJJSE .101 NULL

EXPORT ObjNum-104 "PPFLOAT" AREA SIZEOF TYPE_VSE :102 NULL

УПП программа может содержать операторы. Операторы УПП подразделяются на выполняемые (которые явно предусматривают определенную последовательность действий по управлению и/или обработке данных) и невыполняемые, к которым можно отнести операторы объявления и уничтожения объектов, начала и конца функций, комментарий и т.п. Средствами невьптолняемых операторов У ГШ (STRBEGIN, STR OFFS, STR CONT и др.) возможно конструирование составных объектов, таких как структуры, объединения, массивы. Состав выполняемых операторов характерен для большинства языков высокого уровня. Это оператор вычисления выражения; безусловная передача управления на метку в программе; операторы передачи управления по условию; операторы цикла; возврата из функции и т.п.

Основой большинства операторов УПП является конструкция ВЫРАЖЕНИЕ, выделенное в УПП в отдельный оператор. Выражение представляется в УПП в виде польской постфиксной форме и связывает между собой операнды и соответствующие операции. Операндами могут быть значения объектов, адреса объектов и константы. Операнды связывают ся операциями, которые могут быть арифметическими, логическими, сравнения, присваивания, преобразования типов, извлечения значения объекта по адресу, вызова функций и т.н. Предполагается, что проблема соответствия типа операнда операции решается на этапе трансляции программы из нотации языка высокого уровня в УПП. Выражение УПП является основной конструкцией, обеспечивающей возможность трансляции программ, написанных на входных языках системы, в промежуточное представление с сохранением избыточной информации, необходимой для генерации эффективного объектного кода.

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

В третьей главе работы представлены конкретные результаты исследований в области автоматизации обработки

программ на уровне УПП. В частности, оптимизации и генерации кода.

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

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

• ПО_РА11 - все итерации цикла выполняются параллельно без синхронизации, либо в произвольном порядке;

• 00_81М - все итерации цикла выполняются одновременно, с синхронизацией по присваиваниям (тип синхронизации аналогичен синхронизации векторных присваиваниях ФОРТРАНа-8Х);

• ОО8Е0 - итерации цикла, выполняются строго последовательно.

Данные циклы являются основой ВУПП-фрагмента, который является гнездом циклов БО РЛИ, Б0_81М или БОБЕС^. В гнездо входят специализированные операторы ВУПП. Основная суть ВУПП фрагмента есть "корректное" использование памяти программы, заключающееся в следующем:

1. выделены специальные конструкции работы с переменными цикла ЬМГОЯМ (получение линейной формы от значений переменных циклов, охватывающих данную конструкцию) и ЬООРУАЯ (получение значения переменной цикла заданного уровня, охватывающего данную конструкцию);

2. запрет на доступ к содержимому памяти по указателю - все обращения к памяти осуществляются посредством операции АКЛЕЬТ (доступ к элементу массива) и ОШ_УАШЕ,

3. введение оператора присваивания (то есть на выражение УПП накладывается ограничение - в выражении обязательно присутствует одна и только одна операция присваивания);

4. внутри ВУПП - фрагмента допустимо использование только чистых функций СА1Л_Р1ЖЕ (чистая функция -функция при обращении к которой отсутствует побочный эффект).

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

Следует отметить, что ВУПП - фрагменты могут содержать различные комбинации вложений циклов различных типов. I ссио вложенное гнездо циклов типа БО_81М может быть выполнено как на векторной, так и на различных процессорах многопроцессорной системы. Цикл типа 130 8ЕС>, в который вложены циклы типа ВО 81М, соответствует последовательному выполнению серии векторных/параллельных вычислений. Вложение циклов типа ВОБЕС} в циклы типа БОРАИ соответствует выполнению гнезда последовательных циклов на нескольких процессорах.

Далее, в главе представлен анализ возможности применения ВУПП для промежуточной нотации программ, написанных на языке Фортран-8Х. Проведен обзор основных векторных операций и операторов Фортран-8Х и возможности эффективной нотации векторного параллелизма Фортран-8Х средствами ВУПП. В главе рассматриваются подходы, предлагаемые при генерации кода для векторно-конвейерных ЭВМ, исходя из программы в нотации ВУПП. Анализируется возможность использования ВУПП при векторизации последовательных программ, написанных на языке Си.

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

распараллеливание циклов весьма близки по своей сути. Их отличие состоит в том, что в векторизованном цикле ( типа DO SIM) все реализации одной операции присваивания в разных итерациях выполняются одновременно, а в распараллеленном цикле ( типа DO_PAR) все присваивания, как и остальные операции, могут выполняться в произвольном порядке, то есть не производится никакой синхронизации. Кроме того, внутри гнезда векторизованных циклов не могут находиться циклы других типов. Этого ограничения нет для распараллеленных циклов - внутри их могут находиться как последовательные, так и векторизованные циклы. Поэтому векторизацию и распараллеливание циклов следует понимать как одно и то же, естественно, в пределах вышеназванных отличий.

Во втором пункте данной главы представлены основные результаты исследований и экспериментальной разработки векторизатора программ на уровне УПП, который выполняет следующие действия:

• Обнаружение гнезд параметрических циклов (не обязательно тесно вложенных).

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

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

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

В контексте решения общей проблемы генерации кода, проблема генерации эффективного кода выражения занимает одно из главенствующих мест. Так как в общем случае последняя сводится к оптимальному выбору комбинации машинных команд различных типов, составляющих машинный код выражения при отсутствии однозначного и четко определенного критерия, который избавит от возможных больших переборов. В рамках многофункциональной системы кросс программирования был выбран алгоритм, основанный на модификации и развитии алгоритма динамического программирования предложенного A.V.Aho и S.C.Johnson. Рассмотрим, кратко, суть используемого в системе алгоритма.

Входными данными для алгоритма являются: описание системы команд целевой машины, в котором для каждой команды задается цена - некоторое положительное число и вычисляемое выражение, т.е. формула над некоторым набором операций и операндов. Алгоритм строит программу из заданного набора команд, вычисляющую указанное выражение так, чтобы сумма цен использованных команд была минимальной. При этом время построения программы линеино зависит от числа операции во входном выражении. На целевую машину в исходном алгоритме А.V.Alio и S.C.Johnson накладывается ограничение, заключающееся в том, что все регистры должны быть взаимозаменяемы, т.е. во всех машинных командах регистром-операндом может служить любой из регистров, доступных для генерации. Вследствие этого оригинальный алгоритм не применим к большинству современных архитектур, т.к. условие взаимозаменяемости регистров нарушается как архитектурными свойствами процессора, так и условиями, накладываемыми системой программирования (например плавающие и целочисленные регистры и/или регистры, служащие для возврата значения функции).

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

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

• алгоритм в общем не зависит от целевой машины, что позволяет использовать его для автоматизации построения генераторов кода.

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

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

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

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

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

Кроме того, вся совокупность данных отладчика подразделяется на два логических уровня: данные, содержащие характеристики на всю отлаживаемую программу (например, списки имен внешних объектов) данные, характеризующие каждый объектный модуль программы.

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

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

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

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

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

• На основе обобщения семантических возможностей современных языков программирования (таких как Си, Си++, Паскаль, Модула, Фортран, Оберон и др.) разработан новый промежуточный язык -Унифицированное Промежуточное Представление, используемый в системе для нотации семантики исходных программ после проведения лексического, синтаксического, а также, частично, семантического анализа исходных программ. Разработанный промежуточный язык позволяет сохранять семантические свойства исходных программ, необходимые для проведения оптимизационных преобразований (в частности, векторизации) и генерации

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

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

• Разработана экспериментальная система кросс-отладки адаптируемая к конкретным условиям применения.

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

Список литературы, опубликованной по теме диссертационной работы:

1. Т.И.Даниярходжаев, И.В.Машечкин. Реализация языка Си в рамках кросс-системы.//М.Деп. в ВИНИТИ 14.11.86, №7811-В86.

2. Т.И.Даниярходжаев, В.Ю.Маслов, ИВ.Машечкин. Средства описания данных в унифицированном промежуточном представлении системы кросс-трансляторов.//М.Деп. в ВИНИТИ 14.11.86, №7810-В8б.

3. Т.И.Даниярходжаев, В.Ю.Маслов, И.В.Машечкин. Конструкции обработки данных в унифицированном промежуточном представлении системы кросс-трансляторов.//М.Деп. в ВИНИТИ 14.11.86, №7812-В86.

4. Т.И.Даниярходжаев, И.В.Машечкин. О разработке универсального кросс-транслятора для языка Си.//Сб. "Численные методы в математической физике." М.изд.МГУ, 1986г.

5. Т.И.Даниярходжаев, И.В.Машечкин. Машинонезависимый промежуточный код системы кросс-трансляторов.//Тезисы

докладов IV конференции молодых ученых закавказских республик. Тбилиси, 1986г.

6. Т.И.Даниярходжаев, И.В.Машсчкин. Средства кросс отладки Си-программ.//М.Деп. в ВИНИТИ 13.04.86, №2793-В88.

7. И.В.Машечкин. Миогоязыковая система кросс программирования.//Сб. тезисов докладов Всесоюзной конференции "Методы трансляции и конструирования программ" СО АН СССР, Новосибирск, 1988, часть 2, с.42-43.

8. Т.И.Даниярходжаев, В.Ю.Маслов, И.В.Машечкин. Промежуточный язык многоязыковой кросс-системы программирования.//Сб. "Архитектура и численные методы", препринт ОВМ АН СССР, Москва, 1988.

9. И.В.Машечкин. Многофункциональная кросс-система программирования./'/Сб."Материалы конференции ДИАЛОГ 87", препринт института вычислительной математики АН ГССР, Тбилиси 1988г.

Ю.Т.И.Даниярходжаев, В.Ю.Маслов, И.В.Машечкин.. Единый промежуточный код для группы языков высокого

уровня./'/Сб.'"Материалы конференции ДИАЛОГ 87", препринт института вычислительной математики АН ГССР, Тбилиси 1988г.

11 .Т.И.Даниярходжаев, И.В.Машечкин, Е.О.Орлова. Использование модифицированного алгоритма Ахо-Джонсона для генерации кода в многоязыковой системе кросс программирования.//Сб. тезисов докладов Всесоюзной конференции "Методы трансляции и конструирования программ" СО АН СССР, Новосибирск, 1988, часть 2.

12.И.В.Машечкин. Инструментальные средства программирования высокопроизводительных ЭВМ. //Доклады расширенного заседания семинара института прикладной математики им.И.Н.Вскуа, изд. Тбилисского университета, Тбилиси 1989г.

13.М.Я.Инденбаум, И.В.Машечкин. Интегрированная инструментальная система для разработки и отладки переносимого программного обеспечения станций локальной сети с высоким уровнем сервиса.//15-всесоюзная школа-семинар по вычислительным сетям. Тезисы докладов. Ч.З. М. Изд. ВИНИТИ, 1990г., с.181-186.

14.И.В.Машечкин. Многофункциональная система кросс программирования./ЛТрограммное обеспечение и модели системного анализа. М.: изд. МГУ, 1991г., с.34-44

15.В.Ю.Маслов, И.В.Машечкин. Векторное унифицированное промежуточное представление системы кросс

программирования./ЯТрограммное обеспечение и модели системного анализа. М.: изд. МГУ, 1991г., с.44-49

16.Т.И.Даниярходжаев, И.В.Машечкин, Е.О.Орлова. Алгоритм генерации кода в системе кросс программирования.//Про1раммное обеспечение и модели системного анализа. М.: изд. МГУ, 1991г., с.49-53

17.В.Ю.Маслов, И.В.Машечкин. Кодирование векторной обработки в промежуточном коде системы трансляторов.//М.Деп. в ВИНИТИ 01.03.91, N945-691.

18.И.В.Машечкин, Лян Чженья. Кросс-программирование: современные подходы к организации и новым областям применения.//Тверь. Программные продукты и системы, N3, 1991г., с.12-17.

19.В.Ю.Маслов, И.В.Машечкин. Принципы построения системы программирования для векторно-конвейерных ЭВМ.//С6. Трудов всесоюзной конференции "Смешанные вычисления и преобразования программ". Новосибирск, ВЦ СОАН СССР, 1991г., с.225-231.

20.И.В.Машечкин, Е.О.Орлова. Инструментальный комплекс разработки программного обеспечения. //Системное программирование и модели исследования операций. М.: изд.МГУ, 1993г., с.22-27

21.Е.В.Горбатенко, Т.И.Даниярходжаев, И.В.Машечкин. Оптимизирующий генератор кода для ЭВМ ПС-1001. //Системное программирование и модели исследования операций. М.: изд.МГУ, 1993г., с.28-35

22.И.В.Машечкин, М.В.Ручьев. Некоторые возможности языка Фортран-8Х. //Системное программирование и модели исследования операций. М.: изд.МГУ, 1993г., с.36-46

23.И.В.Машечкин, М.В.Ручьев. Организация кросс-транслятора языка Фортран-77. //Системное программирование и модели исследования операций. М.: изд.МГУ, 1993г., с.47-51

24.И.В.Машечкин, М.В.Ручьев, Р.В.Семенова. Редактор-компилятор языка Фортран-77.//Системное программирование и модели исследования операций. М.: изд.МГУ, 1993г., с.52-56

25.Т.И.Даниярходжаев, И.В.Машечкин, Г.В.Нишанов. Алгоритм генерации оптимального кода для вычисляемых выражений.//Сб. трудов совещания по программированию и математическим методам решения физических задач. Дубна, 1993г.

26.И.В.Машечкин, Г.В.Нишанов. Языки серии Оберон.//Сб. трудов совещания по программированию и математическим методам решения физических задач. Дубна, 1993 г.

27.Т.И.Даниярходжаев, И.В.Машечкин, Г.В.Нишанов. Об одном алгоритме генерации кода. //Вести. Моск. Ун-та. Сер. 15, Вычисл. Матем. и киберн., 1995г., №4, с.65-72.

28.И.В.Машечкин. Инструментальные средства программирования

современных вычислительных систем: концепции, некоторые решения.//Москва. Издательство РАН. Информационные технологии и вычислительные системы, № 1, 199бг, с.64-76.