Page 23 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 23
ge 3. Produce the operation dependency tree Elementary operation graph Make OperationSet
The operation dependency tree (ODT, here which is an in- ModuleList
termediate data structure between the Core and the EOG Preprocess OpVhdlMap
representation) consists of the operation nodes and the de- EOG VhdlModules
pendency edges between the operations. Two types of nodes
are defined in this tree: operation nodes and pointer nodes. Operations ModulList
An operation node has as many children as the number of
its operands. A pointer node is always leaf and it can be Produce Produce Produce
considered as a reference to an operation node. If an oper- Operations Signals Components
ation node has a pointer node child, it will mean the same
function as its child would be the operation node referenced Generate TopModule
by the given pointer node. VHDL Template
Producing the ODT is the largest part of the Haskell-EOG VHDL top module
compiler. The main concept is supercompilation [10], where
the idea is to travel the Core tree in the same order as the Figure 2: EOG-VHDL compiler
CPU would process the statements of this functional code.
During this graph traversal, the following conversions are operations will result in component declarations in VHDL
performed to produce the ODT (as the output tree) from (it is generated by the Produce Components task). Each
the Core description: EOG operation will result in component instantiation and
each dataflow link will result in signal declarations, which
• Var is transformed to pointer node in ODT interconnect the component instantiations. These parts are
generated by the Produce Operations and Produce Sig-
• Lit is transformed to constant operation node in nals tasks in Figure 2.
ODT
Finally, the Generate VHDL task creates the output VHDL
• App (if it is elementary) is transformed to elemen- (the top module), from the produced VHDL parts discussed
tary operation in ODT before.
• App (if it is complex): the body of the function must The EOG-VHDL compiler produces a single, structural VHDL
be inlined, and the nodes contained by the inlined tree file, which contains only certain types of language structures:
has to be processed as every other node component and signal declarations and component instan-
tiations. The behavior of the components are defined in
• Lam can be eliminated without restriction VHDL files separately component-by-component (these files
are stored in the OperationSet).
• Case nodes have already been eliminated in Stage 2
3. MULTI-RATE EXTENSION
Stage 4. Produce the EOG
The final step in the Haskell-EOG compiler is to transform The EOG, previously used as an interface between the com-
the ODT to elementary operation graph, which is a sim- piler frontend and backend, is a single-rate dataflow graph,
pler process, than the previous stages were. Every opera- which is a huge restriction. EOG can only represent dataflow,
tion node in ODT will also be operation in EOG, and every where each operation is performed once during one restart
dataflow link will also be link in EOG. The difference is that of the system (in other words: it is performed once for each
the pointer nodes must be resolved, and it has to be substi- input of the system). Although, certain loops can be im-
tuted by the operation node referenced by the pointer node. plemented in that case too, it is not an efficient way due to
In practice, if the end of a link is a pointer node, this end the increasing number of operation nodes. (for example, if
has to be replaced by the referenced operation node. After a loop iterates between 1 and 5, the operations of the loop
this transformation, the dataflow structure is obtained, not body have to be replicated 5 times) For overcome this re-
necessarily being a tree anymore. striction, a modified EOG is introduced, where groups of
operations can be performed in different number of times
2.2 EOG-VHDL compiler during one restart period.
The architecture of the EOG-VHDL compiler, which is the The extended version of EOG introduced in this section is
backend of the whole method and system introduced in this called multi-rate EOG (MR-EOG). In MR-EOG, groups of
paper, can be seen in Figure 2. First, the EOG goes through operations (blocks) can be defined, where each block con-
a preprocess task (Preprocess EOG in Figure 2), which tains one or more operations and optionally other block(s).
collects all of the information about the EOG nodes, then In this way the blocks are built up in a hierarchy, and the
saves it into the store Operations. Another task (Make
ModuleList in Figure 2) creates the store ModuleList,
which will contain all of the necessary information about
the modules used in the input EOG. These modules have
to exist in the external OperationSet, because the Make
ModuleList task loads the information from that for each
operation.
From the two stores created before, the produce tasks will
generate the parts of the VHDL output. All of the used
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 23
Koper, Slovenia, 10-11 October
The operation dependency tree (ODT, here which is an in- ModuleList
termediate data structure between the Core and the EOG Preprocess OpVhdlMap
representation) consists of the operation nodes and the de- EOG VhdlModules
pendency edges between the operations. Two types of nodes
are defined in this tree: operation nodes and pointer nodes. Operations ModulList
An operation node has as many children as the number of
its operands. A pointer node is always leaf and it can be Produce Produce Produce
considered as a reference to an operation node. If an oper- Operations Signals Components
ation node has a pointer node child, it will mean the same
function as its child would be the operation node referenced Generate TopModule
by the given pointer node. VHDL Template
Producing the ODT is the largest part of the Haskell-EOG VHDL top module
compiler. The main concept is supercompilation [10], where
the idea is to travel the Core tree in the same order as the Figure 2: EOG-VHDL compiler
CPU would process the statements of this functional code.
During this graph traversal, the following conversions are operations will result in component declarations in VHDL
performed to produce the ODT (as the output tree) from (it is generated by the Produce Components task). Each
the Core description: EOG operation will result in component instantiation and
each dataflow link will result in signal declarations, which
• Var is transformed to pointer node in ODT interconnect the component instantiations. These parts are
generated by the Produce Operations and Produce Sig-
• Lit is transformed to constant operation node in nals tasks in Figure 2.
ODT
Finally, the Generate VHDL task creates the output VHDL
• App (if it is elementary) is transformed to elemen- (the top module), from the produced VHDL parts discussed
tary operation in ODT before.
• App (if it is complex): the body of the function must The EOG-VHDL compiler produces a single, structural VHDL
be inlined, and the nodes contained by the inlined tree file, which contains only certain types of language structures:
has to be processed as every other node component and signal declarations and component instan-
tiations. The behavior of the components are defined in
• Lam can be eliminated without restriction VHDL files separately component-by-component (these files
are stored in the OperationSet).
• Case nodes have already been eliminated in Stage 2
3. MULTI-RATE EXTENSION
Stage 4. Produce the EOG
The final step in the Haskell-EOG compiler is to transform The EOG, previously used as an interface between the com-
the ODT to elementary operation graph, which is a sim- piler frontend and backend, is a single-rate dataflow graph,
pler process, than the previous stages were. Every opera- which is a huge restriction. EOG can only represent dataflow,
tion node in ODT will also be operation in EOG, and every where each operation is performed once during one restart
dataflow link will also be link in EOG. The difference is that of the system (in other words: it is performed once for each
the pointer nodes must be resolved, and it has to be substi- input of the system). Although, certain loops can be im-
tuted by the operation node referenced by the pointer node. plemented in that case too, it is not an efficient way due to
In practice, if the end of a link is a pointer node, this end the increasing number of operation nodes. (for example, if
has to be replaced by the referenced operation node. After a loop iterates between 1 and 5, the operations of the loop
this transformation, the dataflow structure is obtained, not body have to be replicated 5 times) For overcome this re-
necessarily being a tree anymore. striction, a modified EOG is introduced, where groups of
operations can be performed in different number of times
2.2 EOG-VHDL compiler during one restart period.
The architecture of the EOG-VHDL compiler, which is the The extended version of EOG introduced in this section is
backend of the whole method and system introduced in this called multi-rate EOG (MR-EOG). In MR-EOG, groups of
paper, can be seen in Figure 2. First, the EOG goes through operations (blocks) can be defined, where each block con-
a preprocess task (Preprocess EOG in Figure 2), which tains one or more operations and optionally other block(s).
collects all of the information about the EOG nodes, then In this way the blocks are built up in a hierarchy, and the
saves it into the store Operations. Another task (Make
ModuleList in Figure 2) creates the store ModuleList,
which will contain all of the necessary information about
the modules used in the input EOG. These modules have
to exist in the external OperationSet, because the Make
ModuleList task loads the information from that for each
operation.
From the two stores created before, the produce tasks will
generate the parts of the VHDL output. All of the used
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 23
Koper, Slovenia, 10-11 October
