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.


 

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

29519. Конфликт: предотвращение и управление 84 KB
  Моргунов В этой теме вы узнаете: Все о конфликтах о типологии конфликтов а также их предотвращении; О причинах и фазах конфликта; О конфликте и эмоциях; О задачах и основных понятиях конфликтологии; О типичных ошибках конфликтологии и технологии разрешения конфликта; Необходимо сразу оговорить что безконфликтных организаций не существует. Поэтому понимать истоки конфликта и уметь управлять его течением и разрешением неотъемлемое умение руководителя. Если противоречие получает развитие говорят о возникновении конфликта....
29520. Организация как система 44.5 KB
  Общая теория систем это не столько научная теория в традиционном смысле слова сколько комплекс методологических подходов к обширному классу объектов объединенных названием сложные системы Шрейдер Ю. Определения и свойства системы Часть смысловых связей понятия система можно обнаружить в его противопоставлении с несколькими понятиями: система беспорядочное образование; система аморфность; система случайная совокупность; система случайность; система множество из элементов не связанных в целое.Блюменфельду системой...
29521. Управление нововведениями в организации 78.5 KB
  Управление нововведениями в организации Е.Моргунов В этой теме вы узнаете: О том как управлять инновациями в организации; О видах изменений происходящих в жизни организации; О технологиях работы с организационным сопротивлением; Рекомендациях по внедрению изменений. Понятие изменение подразумевает что между двумя последовательными моментами времени имеются заметные различия в ситуации человеке рабочей группе организации или взаимоотношениях. Изменения в организации могут касаться любого аспекта или фактора.
29522. Организационная культура. Компоненты и уровни организационной культуры 83 KB
  Моргунов В этой теме вы узнаете: Об организационной культуре; О компонентах и уровнях организационной культуры; О характеристиках поведения руководителей; Все организации независимо от формы собственности и целей деятельности создаются и живут в определенной среде носящей название культура. Общеупотребимого определения культуры нет хотя интуитивно ясно что это такое. В дополнение к нормам принятым в обществе каждая группа людей в том числе и организация вырабатывает собственные культурные образцы которые получили название...
29523. Коммуникативное поведение в организации 49 KB
  Моргунов В этой теме вы узнаете: Об общении и функциях общения в организации; О возможностях понимания человека человеком; Об эффектах межличностного восприятия; О половых различиях в общении. Источники информации в общении сигналы непосредственно от другого человека сигналы от собственных сенсорноперцептивных систем информация о внешних по отношению к общению условиях информация об итогах деятельности информация от внутреннего опыта информация о вероятном будущем. Теория транзакций Эрик Берн 1902 1970 развивал...
29524. ПОВЕДЕНИЕ И ЭФФЕКТИВНОСТЬ ОРГАНИЗАЦИИ 68.5 KB
  Школа научного управления 1885 1920. Школа научного управления наиболее тесно связана с именами Фредерик Уинслоу Тейлор Фрэнк Банкер Гилбрет с женой Лилиан Генри Лоуренс Гантт.Тейлором 1856 1915 который возглавил движение научного управления. Он интересовался эффективностью деятельности не отдельного человека а организации что и положило начало развитию школы научного управления.
29525. Активация, утомление и другие состояния работника 101.5 KB
  Так например для состояния утомления характерны совершенно определенные сдвиги в деятельности сердечнососудистой системы. По мере развития утомления в первую очередь наблюдается снижение силы сердечных сокращений. Поэтому диагностически значимыми для состояния утомления являются не сами по себе симптомы увеличенной частоты сердечных сокращений повышенного артериального давления и изменения минутного объема крови в их непосредственном количественном выражении а направление и величина сдвигов этих показателей и соотношений между ними....
29526. Группа: как управлять коллективом 60.5 KB
  Фрезер в 1978м году предложил список 6ти основных характеристик группы: взаимодействие членов восприятие группы как чегото реального наличие групповых целей формирование норм взаимодействия в группе синергетический эффект от взаимодействия в группе эмоциональные отношения между членами группы относительная закрепленность ролей. Психологической группой можно назвать некоторое число людей которые: взаимодействуют друг с другом знают друг друга воспринимают себя членами одной группы. Свойства группы: размер...
29527. ГРУППА И ГРУППОВОЕ ПОВЕДЕНИЕ В ОРГАНИЗАЦИИ 68 KB
  Основные характеристики группы. Реальные группы это объединения людей в которых имеет место единство деятельности условий обстоятельств признаков. Группы бывают большими и малыми контактными в которых имеется возможность непосредственных контактов каждого с каждым.