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.


 

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

17053. Робота з вікнами. Вивчення прийомів роботи з обєктами 949 KB
  Практична робота №3 Тема: Робота з вікнами. Вивчення прийомів роботи з обєктами. Мета: ознайомитися із структурою стандартного вікна ОС Windows прийомами роботи з одним і декількома вікнами. Навчитися прийомам роботи з обєктами. Устаткування: ПК. Операційна система Win...
17054. Управління теками, файлами і ярликами 470.5 KB
  Практична робота №4 Тема: Управління теками файлами і ярликами Мета: придбати уміння і навик роботи з теками і файлами а також створення ярликів до них. Призначення: оволодіння прийомами створення і перейменування тек копіювання переміщення видалення і відновленн...
17055. Використовування програми «Провідник» 479.5 KB
  Практична робота №5 Тема: Використовування програми Провідник Мета: придбати уміння і навик роботи з програмою Провідник. Призначення: оволодіння засобами програми Провідник забезпечить закріплення навиків придбаних при виконанні попередньої роботи і сп
17056. Социальная защита населения. Социальные трансферты 186 KB
  В подобном контексте рассматриваемое понятие неизбежно связано с политикой обеспечения прав и гарантий в области уровня и качества жизни: на минимально достаточные средства для жизни; на социальное обеспечение в старости, в случае болезни, потери кормильца; на защиту от безработицы, охрану здоровья...
17057. Програмування арифметичних дій множення і розподіл 43.5 KB
  Практична робота №21 Тема: Програмування арифметичних дій множення і розподіл. Мета: Навчитися створювати програми на асемблері виконуючі операції множення і розподіл.. Устаткування: ПК. Програма Turbo Assembler 5.0. Правила ТБ. Хід роботи Описати коже...
17058. Програмування арифметичних виразів 40 KB
  Практична робота №22 Тема: Програмування арифметичних виразів. Мета: Навчитися створювати програми на асемблері виконуючі основні арифметичні дії. Устаткування: ПК. Програма Turbo Assembler 5.0. Правила ТБ. Методичні рекомендації. Індивідуальне завдання ...
17059. Основні прийоми роботи в середовищі Windows 247 KB
  Практична робота №1 Тема: Основні прийоми роботи в середовищі Windows. Мета: вивчити структуру робочого столу і властивості основних об'єктів. Призначення: ознайомитися з основними об'єктами робочого столу теками Мій комп'ютер Мережеве оточення Корзина і па
17060. Метод анкетного опроса как инструмент диагностики проблем в образовательной системе Республики Беларусь 324 KB
  Переход от одного типа общества к другому не бывает скоротечным и мгновенным. Это длительный и трудоемкий процесс, требующий исследований с целью выявления слабых сторон системы для дальнейшего анализа и совершенствования.
17061. Проектирование кулачкового механизма с прямолинейно движущимся роликовым толкателем 1.17 MB
  Кулачковый механизм предназначен для перемещения толкателя по определенному закону, который задается при проектировании. Первый этап проектирования состоит в определении положения центра вращения кулачка по отношению к траектории точки В толкателя