77378

СИСТЕМА СОБЫТИЙНО-УПРАВЛЯЕМОЙ ТРАНСЛЯЦИИ LiME

Научная статья

Информатика, кибернетика и программирование

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

Русский

2015-02-02

34.5 KB

0 чел.

СИСТЕМА СОБЫТИЙНО-УПРАВЛЯЕМОЙ ТРАНСЛЯЦИИ LiME

М.О. Бахтерев

Институт математики и механики имени Красовского УрО РАН, Екатеринбург

Разработка процессора с новой системой команд в настоящее время подразумевает и разработку трансляторов с некоторых языков высокого уровня на ассемблер с этой новой системой команд. Если система команд существенно не отходит в основных принципах своей организации от принципов давно используемых в CISC, RISC и VLIW системах, то задача разработки трансляторов существенно упрощается, так как в этом случае можно положится на существующие развитые программные пакеты, такие как LLVM и GCC. Однако, если система команд отличается от традиционных, использование этих пакетов может оказаться весьма затруднительным.

Предлагаемые распространёнными системами трансляции абстракции для описания наборов инструкций целевых процессоров всегда подразумевают, что после записи значения V в регистр, который указывается в команде именем N, все последующие чтения данных по имени N до следующей записи выдают значение V.

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

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

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

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

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

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

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

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

На практике мы опробовали нашу систему в разработке транслятора с языка Си99 на ассемблер мультиклеточных процессоров. Этот опыт показал, что описывать процесс построения графа в виде набора активируемых по событиям форм, в некотором смысле проще, чем создание программы с аналогичной функциональностью на одном из традиционных языков программирования. Здесь можно провести такое сравнение: в одном из самых компактных трансляторов Си99 -- Tiny C Compiler -- основной цикл трансляции реализован в 6200 строках кода на Си99 (без учёта вспомогательных процедур). Нам удалось реализовать аналогичный цикл всего в 2500 строках кода для системы LiME.

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

Работа выполнена при поддержке Программы фундаментальных исследований УрО РАН “Информационные, управляющие и интеллектуальные технологии и системы”, проект 12-П-1-1034.


 

А также другие работы, которые могут Вас заинтересовать

51474. Средства создания Web-сайтов. Введение в разработку Web-приложений 1.06 MB
  Введение в разработку Webприложений. Webстраницы Webсайты Webсервисы и Webприложений. Средства создания Webсайтов. Примеры создания простых Webсайтов средствами языка HTML.
51475. Создание Web-приложений средствами ASP.NET 1.1 MB
  Создание Webприложений средствами SP. Начало работы с Visul Studio и создание нового Webприложения NET Почти все крупномасштабные Webсайты на базе технологии SP.NET разрабатываются с использованием Visul Studio предлагаемой компанией Microsoft полнофункциональной среды разработки Webприложений гибкого и универсального инструмента проектирования и создания законченных приложений для платформы Windows.
51477. Определение отклика на гармоническое воздействие 397 KB
  Определить комплексную передаточную функцию КПФ и ее составляющие: модуль Hω и аргумент θω привести полученную КПФ к общему виду КПФ для цепи первого порядка. Схема исследуемого четырехполюсника Исходные данные цепи: Ом мГн Функции воздействия: и Решение Определение комплексной передаточной функции КПФ четырехполюсника Комплексная передаточная функция записывается: По формуле чужого сопротивления находим : Отсюда = Подставим полученное выражения для в формулу нахождения КПФ: Таким образом мы привели полученную КПФ к...
51478. Определение отклика на гармоническое воздействие при подключении и отключении источника 305 KB
  В лабораторной работе определен отклик цепи при подключении и отключении источника, построены необходимые графические изображения и таблицы
51479. Определение отклика на периодическое негармоническое воздействие 346.5 KB
  Построить спектр амплитуд и спектр фаз отклика. Определить действующее и среднее значение отклика мощность выделяемую на сопротивлении нагрузки. Определение отклика цепи Определим отклик.
51480. Кинематика материальной точки 287 KB
  Рассмотрим участок АВ: Согласно II закону Ньютона При проектировании на оси координат получаем величина непостоянная а переменная то ускорение непостоянно. Получаем где выражение это определение скорости. Подставляя полученные значения в исходное выражение получаем. Интегрируем обе части выражения получаем.
51481. Динамика вращательного движения вокруг горизонтальной оси 263 KB
  Система состоящая из диска массой m и радиуса R с прикрепленными к нему тонкими стержнями общей массой m может свободно вращаться вокруг горизонтальной оси. Через обод на диске переброшена тонкая невесомая нерастяжимая нить к концам которой привязаны грузы массой каждый. На ободе диска прикреплен шарик массой пренебрежимо малого размера. На какой наибольший угол повернётся система если на один из висящих на нити грузов положить перегрузок массой .
51482. Отклонить тело из положения равновесия и написать уравнение колебаний 210.5 KB
  Найдем центры масс каждого тела отдельно а затем и всей системы: ; Центр массы стержня 1 лежит на его середине: Центр массы стержня 2 лежит на его середине: Центр массы большого диска 3 лежит в его центре а центр находится на оси OX: Центр массы большой пластины 4 лежит на пересечении ее диагоналей: Центр массы малого диска 5 лежит в его центре: Центр массы малой пластины 6 лежит на пересечении ее диагоналей: Найдем центр масс всей системы: Координаты центра масс: С0.14 Угол на который отклонится центр масс системы от нормали: где ...