37316

LiME - THE EVENT DRIVEN TRANSLATION SYSTEM

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

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

Nowadays the development of CPU with new instruction set architecture (ISA) implies that translators to this ISA assembler from the certain set of high level programming languages should be developed too. If the basic principles of the ISA are close enough to the long time used traditional CISC

Английский

2015-01-19

24.5 KB

1 чел.

LiME -- THE EVENT DRIVEN TRANSLATION SYSTEM

M.O. Bakhterev

The Krasovski Institute for Mathematics and Mechanics of UrB RAS, Yekaterinburg

Nowadays the development of CPU with new instruction set architecture (ISA) implies that translators to this ISA assembler from the certain set of high level programming languages should be developed too. If the basic principles of the ISA are close enough to the long time used traditional CISC, RISC and VLIW systems, then the translators development could be simplified by using existing mature software packages such as LLVM and GCC. But if the ISA diverges from traditional ones, the usage of these packages may become inconveniently hard.

The wide known translation systems suggest abstractions for target CPU ISA description which imply that after write of the value V to the register, referred in command with the name N, all the next reads from N till the next write to N will issue the same value V.

This mirror one of the basic ideas for CISC, RISC and VLIW CPUs -- an idea about strict sequential modification of the computer's memory (register set and system RAM) state, through which the information is communicated between computation steps described by instructions. Keeping such an order of computation significantly limit the efficiency of traditional architecture solutions, in the framework of which the high information processing speeds may be achieved either by significant amounts of additional hardware and increase in power consumption (CPUs with out of order execution), or by limiting the class of efficiently executed programs (GPGPUs which could be viewed as vector RISC-machines).

However, as the experience of the multicelluar processor developmen shows, it is possible to maintain high speed in program execution without large amount of additional hardware and without limiting the class of effectively executed programs. To achieve that it is needed to abandon the semantic of sequential instruction execution with mutable state of system RAM and registers threading. But such an abandonment makes utilization of traditional translation systems impossible and frequently leads to refusal from research works on new architectural ideas because of high costs of translation systems development. But the multicellular processor architecture, beside increase in code execution efficiency, possesses the set of another important practical features such as program execution continuation under some of the functional units hardware failures and runtime functional units configuration optimization for certain tasks with the ability to shutdown some of the units for power saving. These features are quite attractive to initiate new translation system development.

The first of the most difficult tasks that should be solved due this development is the task of the source code translation into the intermediate form convenient for further processing. Such convenient form for multicellular processors is program representation as control flow dag in witch the nodes are linear blocks described with data flow dags.  

The difficulty of building such program representation by abstract syntax tree emerges from that for every tree node there are many variants of linking dags build for child subtrees into larger structure. And that is complicated by dependency of linking variants in the node on some tree level on results of linking in the nodes on upper and lower tree levels.

To construct links correctly it is necessary to analyze all that variants and when programming in traditional languages to describe that analysis by lengthy multilevel pattern matching structures. And this is most labor-intensive part of work on translator into intermediate representation, demanding from highly skilled programmers tiring attention to details.

However, some time ago we've formalized one approach to distributed computational processes description in the form of dynamically constructed data flow graphs. The approach was intended to solve the problem of managing complex crossreferences in data processed by parallel code. One of the our approach features allowing to lower the complexity of parallel code development is an ability to progressively build computation structure in some namespace by the named events of new results generation emerging during that computation. This feature, as it was expected, had to simplify both tasks of the distributed computation decomposition into independent parts and the following composition of their results in order to get overall result. In its turn the simplification of these tasks had to lower labor-intensity of parallel code development. We have tested our approach in the coding of some parallel algorithms, and it has payed our expectations off.

The problems emerging when constructing the dag in some node of abstract syntax tree from child subtrees dags are similar to those emerging in the composition and decomposition of distributed computation processes. It may be that such similarity has deep strict mathematical reason, since the structures of the abstractions of communicating sequential processes and of recursive mu-types are quite similar.

Having been following that similarity we have developed the LiME translation system based on the program graph dynamic construction with the same principles as those in the basis of the RiDE system for distributed processes programming. The graph is built by the process of the forms application which are similar to the RiDE rules. These applications are activated by the events of inputs availability. During the form application new arcs leading from existing graph through the inputs to the new graph part described by the form being activated are built. After form activation new outputs pointing to the nodes of grown graph and new forms potentially ready for further activation appear. This process closely mirrors the process of data flow graph dynamic construction in the RiDE system. And we suggest for such method of program graph construction the name event-driven translation.   

We used our system in practice in the development of translator from C99 language to the assembler of multicellular processors. This experience has shown that description of the program graph construction process as the set of forms activated by events is in some sense simplier than encoding similar functionality in one of traditional programming languages. We can refer here to the following comparison. The main translation cycle of one of the most compact C99 translators -- Tiny C Compiler -- is encoded in 6200 lines of C99 code (not counting auxiliary functions). We have managed to implement comparable cycle in just 2500 lines of code for LiME system.

Thus we show in this work that principles in foundation of the RiDE distributed programming system are quite universal, powerful and adequate for description even of such complex interlinks between computational procedures as arise on some stages of program compilation. Besides that we were able to refine and develop the RiDE formal model itself making it more suitable for description of data flows with extreme complex structures.

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


 

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

33046. Сущность финансового планирования и прогнозирования. Современные подходы и методы финансового планирования при разработке среднесрочных финансовых планов 33 KB
  Сущность финансового планирования и прогнозирования. Современные подходы и методы финансового планирования при разработке среднесрочных финансовых планов. Назначение и сущность финансового планирования заключается в определении общих направлений деятельности предприятия главных целей и основных способов их достижения предприятием. Конечным результатом финансового планирования является составление финансового плана.
33047. Финансовый контроль: понятие, цели, субъектный состав, формы, методы 38.5 KB
  Финансовый контроль: понятие цели субъектный состав формы методы. Финансовый контроль как и планирование является важнейшим показателем управления финансами. Государственный финансовый контроль вневедомственный ведомственный 2. Негосударственный финансовый контроль.
33048. Государственный финансовый контроль: Понятие, принципы, органы управления 40 KB
  Государственный финансовый контроль это установленная законодательством деятельность органов государственной власти и управления всех уровней по выявлению предупреждению и пресечению: ошибок и злоупотреблений в управлении государственными денежными и иными материальными ресурсами капиталами а также используемыми в хозяйственной деятельности и отчуждаемыми нематериальными объектами государственной собственности влекущих прямой или косвенный финансовый и или материальный ущерб государству; несоблюдения финансовохозяйственного в том...
33049. Государственные финансы: понятие, структура (федеральные финансы, финансы субъектов федерации) 28.5 KB
  Государственные финансы: понятие структура федеральные финансы финансы субъектов федерации. Государственные финансы являются составной частью общей финансовой систем и являются инструментом мобилизации средств всех секторов экономики для проведения государственной внутренней и внешней политики. Государственные финансы представляют собой единый комплекс финансовых операций органов государственного управления с помощью которого аккумулируются денежные средства и осуществляются денежные расходы. Государственные финансы это система денежных...
33050. Політична свідомість, правова та моральна свідомість 13.02 KB
  Це політична свідомість правова моральна релігійна естетична наукова свідомість тощо. Політична свідомість відображає суспільне буття найбільш безпосереднім і глибоким способом. Політична свідомість включає в себе ідеологічну і психологічну сторони. Важливу роль у регулюванні відносин між людьми відіграє правосвідомість.
33051. Характеристика свідомості 12.55 KB
  Активність свідомості проявляється в тому що людина відображає зовнішній світ цілеспрямовано вибірково. Дійсність відтворюється в свідомості людини не в дзеркальномертвому а в творчо перетвореному вигляді. Отже під активністю свідомості мається на увазі її вибірковість і цілеспрямованість яка виявляється у формуванні нових ідей в актах продуктивного уявлення в управлінні практичною діяльністю. Творчий характер свідомості в практичній діяльності людини виявляється в тому що поперше завдяки свідомості людина пізнає закони об'єктивної...
33052. Принципи діалектичного осмислення буття 14.4 KB
  Принцип об´єктивностіпоходить з атрибутивності відображення і вторинності свідомості як вищої форми відображення. Принцип об´єктивності доповнюється іншими принципами що забезпечують адекватність відображення. Цей принцип спрямовує мислення на перехід від явищ до їх сутності до пізнання закономірностей а також необхідних суттєвих зв´язків предмета що розглядається з оточуючими його предметами і процесами. Принцип історизмупотребує поперше якісної абосутнісної ретроспективизнання сутності; подругепередумовного розглядурозгляду...
33053. Закон єдності і боротьби протилежностей 15.08 KB
  Маючи обєктивний зміст закони діалектики виконують гносеологічну функцію: виступають ступенями проникнення в сутність розвитку його відтворення в обєктивній конкретній всезагальності від відображення розвитку як якісної зміни взагалі до розкриття суперечливої сутності цього процесу як єдності змін і збереження та як суперечності що розвязуються у формі поступального сходження від нижчого до вищого. Закон єдності і боротьби протилежностей один з основних законів діалектики який визнаєвнутрішнє джерело руху і розвитку в природі...
33054. Світоглядне і методологічне значення категорій 14.43 KB
  Він розглядав категорії як апріорні форми розсуду за допомогою яких розсудок упорядковує пізнавальний матеріал одержуваний за допомогою відчуттів. Кант оголосив категорії суб'єктивними формами розумової діяльності що притаманні свідомості до досвіду апріорі. Вчення про категорії найбільш розвинуте у філософії Гегеля в якого Наука логіки виступає як діалектична система філософських категорій. Заслуга Гегеля полягає саме у створенні діалектичної логіки де всі категорії взаємопов'язані переходять одна в одну і всі разом відтворюють...