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.


 

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

46402. Розрахунок деталі ”Вал-шестерня” 2.3 MB
  Деталь ”Вал-шестерня” входить до фартуха токарно-револьверного верстату моделі 1Г340ПЦ, і призначений для переміщення фартуха у повздовжньому напрямку.
46403. Составление программ циклической структуры 64 KB
  Изучить основные операторы для организации циклов. Разработать алгоритм решения задачи. Составить программу решения задачи. Вычислить на ЭВМ значение интеграла на отрезке. Число разбиений отрезка интегрирования равен 100, метод интегрирования – метод трапеций.
46404. Психологічні умови попередження та врегулювання конфліктів у військовому колективі 158.5 KB
  Життєвий цикл конфлікту. Найважливіші з них: предмет конфлікту його об’єкт суб’єкти конфліктна ситуація інцидент структура. Виникнення спірної ситуації Сприйняття ситуації як конфліктної хоч би однією із сторін ні так Наявність конфліктної ситуації Виникнення інциденту ні так Розгортання конфлікту Відсутність конфлікту Рис. Конфліктна ситуація – це основна умова виникнення конфлікту на підставі порушення балансу інтересів учасників взаємодії.
46405. Психологічні особливості консультування 146 KB
  Впливати на ситуацію він може тільки через клієнта використовуючи можливості доступні клієнтові в його становищі. Ефективність психологічної допомоги виявляється в готовності клієнта витрачати час гроші душевні сили на розвязання його проблеми. Психологконсультант у консультативному процесі виступає в ролі...
46406. Педагогічні особливості культури офіцера 184 KB
  Обговорення другого питання: Педагогічні техніки військового педагога 30 хв. 30 Педагогічні техніки військового педагога 30 Психологічні особливості педагогічної майстерності 20 3. Обговорення другого питання: Педагогічні техніки військового педагога 30 хв. Педагогічну культуру вони розглядають як оволодіння військовим педагогом педагогічним досвідом людства ступінь його досконалості в педагогічній діяльності досягнутий рівень розвитку його особистості як педагога.
46408. Характеристика військового колективу 138.5 KB
  Хоча психічний склад колективу є соціально обумовленим, але він у багато чому визначається характером і умовами колективної діяльності, віковим і національним складом членів колективу. Тому при аналізі психічного складу колективів можливий і професійний, і віковий, і національний підходи...
46409. Доказательство и доказывание в гражданском процессе 118.5 KB
  Представители по гражданскому делу, или защитники по уголовному делу, делу об административном правонарушении, или медиаторы - об обстоятельствах, которые стали им известны в связи с исполнением обязанностей представителя, защитника или медиатора...
46410. Розмір речення та ідіостиль 36.21 KB
  Підготувала студентка 2го курсу ФІФ Група 2338 н Бреніч Наталія Розмір речення та ідіостиль Ця доповідь присвячена висвітленню теми Розмір речення та ідіостиль Поліни Ігорівни Климової. Обьектом статті є речення в свою чергу предметом є розмір речення та поняття іліостиль. Адмоні даючи детальну характеристику особливостям побудови речення в творах цього письменника наголошував на тому що у фразі Томаса Манна наявний процес пошуку істини це проявляється. Цією статтею робимо спробу дослідити недостатньо вивчений аспект ідіостиля...