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.


 

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

68668. Оценка экономической эффективности инвестиций в создание автомобильного производства «Автофрамос» в г. Москве 1.51 MB
  В конечном итоге именно производство создает базу для получения валового внутреннего продукта страны поэтому обеспечение производства основными и оборотными средствами которое осуществляется через инвестирование является необходимым условием экономического роста.
68670. Повышение эффективности деятельности туристической фирмы (на примере туристического агенства ООО «Альпана») 2.32 MB
  Цель исследования - на основе исследования современных тенденций развития туристского рынка в Украине разработать конкретные предложения по повышению эффективности деятельности ООО «Альпана» с целью ее экономического роста. Для достижения поставленной цели предполагается решение следующих основных задач...
68671. Развитие творческого потенциала младших школьников на уроке математики 142 KB
  Приобрести вычислительные навыки значит для каждого случая знать какие операции и в каком порядке следует выполнять чтобы найти результат арифметического действия и выполнять эти операции достаточно быстро. Приобрести вычислительные навыки значит для каждого случая знать какие операции и в каком...
68672. Анализ работы контакторной панели троллейбуса ЗиУ-682Г. Устройство и компоновка контакторной панели троллейбуса ЗиУ-682Г 572.5 KB
  Контакторы и реле, обеспечивающие коммутацию силовых цепей, управление подвижным составом и защиту электрооборудования, для удобства монтажа, облегчения ремонта и сокращения проводки группируют по изоляционным панелям и ящикам. Изоляционные панели унифицированы и поставляются заводом-изготовителем комплектом.
68675. Технического обслуживания локомотива ТО-2 134.57 KB
  При ТО-2 не реже одного раза в двое суток проверяют состояние основного оборудования и ходовых частей электровоза и устраняют выявленные при осмотре неисправности. Кроме того, выполняют работы, записанные локомотивными бригадами в журнале технического состояния электровоза...
68676. Анализ предметной области и разработка технического задания для разработки распределенной информационной системы «Магазин компьютерной техники» 452 KB
  Анализ предметной области это первый шаг этапа системного анализа с которого начинается разработка программной системы. Концептуальная модель применяется для структурирования предметной области с учетом информационных интересов пользователей системы.