Page 24 - 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. 24
of the hierarchy is a block denoted by TOP in further. Program Num. of Num. of Num. of
i operations links blocks
agh j
1 PID controller 29 36 0
k 2 MP3 SFB 93 133 6
b ef 3 MP3 ssum 19 25 1
4 MP3 uconv 32 45 0
cd 5 MP3 usum 11 16 1
Table 1: Summary of the compiler tests
Figure 3: MR-EOG Haskell code automatically, 2) it reports in case of any com-
piler errors, 3) the structure of the compiler is modular (it
An example can be seen in Figure 3. Here the block TOP has a frontend and a backend part), thus the parts could
contains the operations a, i, j and k, and two inner blocks. be used separately in other projects. 4) external pipeline
One of that contains the operations g and h, and the other optimization stage can be included, since it has a dataflow
contains b, e and f, and its inner block contains the opera- graph as intermediate representation. 5) the operation set
tions c and d. is able to be extended, because they are from an external
database separated from the compiler program itself.
For the new multi-rate representation, there is an important
purpose: ensure that the general algorithms performed in The method, including its extended variant for multi-rate
dataflow graphs (such as pipeline optimization algorithms) tasks, was tested with practical applications, such as a PID
can also be used in MR-EOG. The solution is running the controller and an MP3 synthesis filter bank algorithm.
algorithms recursively, starting with the innermost block.
Since the innermost block does not contain inner blocks, the 6. REFERENCES
methods developed for a single-rate dataflow graph can be
performed without restriction. If the algorithm finish with [1] Peter Arato, Visegrady Tamas, and Istvan Jankovits.
a given block, the block has to be substituted by a virtual High Level Synthesis of Pipelined Datapaths. John
operation. The execution time of this operation will be the Wiley & Sons, Inc., New York, NY, USA, 2001.
same as the execution time of the whole block was.
[2] C. P. R. Baaij. Cλash: From haskell to hardware.
When a block contains only operations (including virtual Master’s thesis, Univ. of Twente, December 2009.
operations), the same algorithm can be run on it. In the
end, even the block TOP is performed, and the algorithm is [3] Per Bjesse, Koen Claessen, Mary Sheeran, and
finished for the whole MR-EOG hierarchy. Satnam Singh. Lava: hardware design in haskell.
SIGPLAN Not., 34:174–184, September 1998.
4. SOME CHARACTERISTIC TASKS FOR
TESTING [4] Simon Frankau. Hardware synthesis from a
stream-processing functional language, 2004.
We implemented the compiler program based on the method
introduced above in Haskell language. For testing the func- [5] Shaori Guo and Wayne Luk. Compiling ruby into
tionality, two characteristic tasks (written also in Haskell) fpgas. In Proceedings of the 5th International
were chosen. The first one is a PID controller, which is a Workshop on Field-Programmable Logic and
single-rate algorithm, therefore the method written in Sec- Applications, FPL ’95, pages 188–197, London, UK,
tion 2 can even compile this code to generate the desired 1995. Springer-Verlag.
VHDL. The second one is the synthesis filter bank (SFB)
part of the MP3 decoder algorithm. Since it contains sev- [6] ISO/IEC. Ieee 1076-2008: Ieee standard vhdl language
eral loops, it can only be represented by multi-rate types of reference manual. Technical report, Institute of
dataflow graphs efficiently. The multi-rate extension of the Electrical and Electronics Engineers, Computer
method detailed in Section 3 was used to compile this task. Society, 26. January 2009.
A brief summary of the functional tests are shown in Table [7] M. Kooijman. Haskell as a higher order structural
1. Row 1 shows the characteristic numbers of the PID con- hardware description language, December 2009.
troller, while Row 2 shows the same for the MP3 SFB. The
subtasks of the MP3 SFB can be seen in Row 3, 4 and 5 [8] E.A. Lee and D.G. Messerschmitt. Synchronous data
separately. flow. Proceedings of the IEEE, 75(9):1235 – 1245, sept.
1987.
5. CONCLUSIONS
[9] Simon Marlow. Haskell 2010 language report, 2010.
A compiler program is developed on base of the novel method [10] Neil Mitchell. Rethinking supercompilation. SIGPLAN
introduced in this paper. The method meets the require-
ments that was set before: 1) it generate the VHDL from Not., 45:309–320, September 2010.
[11] K.K. Parhi. Algorithm transformation techniques for
concurrent processors. Proceedings of the IEEE,
77(12):1879 –1895, dec 1989.
[12] Mary Sheeran. ufp, an algebraic vlsi design language -
phd thesis, 1983.
[13] Andrew Tolmach. An external representation for the
ghc core language, 2009.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 24
Koper, Slovenia, 10-11 October
i operations links blocks
agh j
1 PID controller 29 36 0
k 2 MP3 SFB 93 133 6
b ef 3 MP3 ssum 19 25 1
4 MP3 uconv 32 45 0
cd 5 MP3 usum 11 16 1
Table 1: Summary of the compiler tests
Figure 3: MR-EOG Haskell code automatically, 2) it reports in case of any com-
piler errors, 3) the structure of the compiler is modular (it
An example can be seen in Figure 3. Here the block TOP has a frontend and a backend part), thus the parts could
contains the operations a, i, j and k, and two inner blocks. be used separately in other projects. 4) external pipeline
One of that contains the operations g and h, and the other optimization stage can be included, since it has a dataflow
contains b, e and f, and its inner block contains the opera- graph as intermediate representation. 5) the operation set
tions c and d. is able to be extended, because they are from an external
database separated from the compiler program itself.
For the new multi-rate representation, there is an important
purpose: ensure that the general algorithms performed in The method, including its extended variant for multi-rate
dataflow graphs (such as pipeline optimization algorithms) tasks, was tested with practical applications, such as a PID
can also be used in MR-EOG. The solution is running the controller and an MP3 synthesis filter bank algorithm.
algorithms recursively, starting with the innermost block.
Since the innermost block does not contain inner blocks, the 6. REFERENCES
methods developed for a single-rate dataflow graph can be
performed without restriction. If the algorithm finish with [1] Peter Arato, Visegrady Tamas, and Istvan Jankovits.
a given block, the block has to be substituted by a virtual High Level Synthesis of Pipelined Datapaths. John
operation. The execution time of this operation will be the Wiley & Sons, Inc., New York, NY, USA, 2001.
same as the execution time of the whole block was.
[2] C. P. R. Baaij. Cλash: From haskell to hardware.
When a block contains only operations (including virtual Master’s thesis, Univ. of Twente, December 2009.
operations), the same algorithm can be run on it. In the
end, even the block TOP is performed, and the algorithm is [3] Per Bjesse, Koen Claessen, Mary Sheeran, and
finished for the whole MR-EOG hierarchy. Satnam Singh. Lava: hardware design in haskell.
SIGPLAN Not., 34:174–184, September 1998.
4. SOME CHARACTERISTIC TASKS FOR
TESTING [4] Simon Frankau. Hardware synthesis from a
stream-processing functional language, 2004.
We implemented the compiler program based on the method
introduced above in Haskell language. For testing the func- [5] Shaori Guo and Wayne Luk. Compiling ruby into
tionality, two characteristic tasks (written also in Haskell) fpgas. In Proceedings of the 5th International
were chosen. The first one is a PID controller, which is a Workshop on Field-Programmable Logic and
single-rate algorithm, therefore the method written in Sec- Applications, FPL ’95, pages 188–197, London, UK,
tion 2 can even compile this code to generate the desired 1995. Springer-Verlag.
VHDL. The second one is the synthesis filter bank (SFB)
part of the MP3 decoder algorithm. Since it contains sev- [6] ISO/IEC. Ieee 1076-2008: Ieee standard vhdl language
eral loops, it can only be represented by multi-rate types of reference manual. Technical report, Institute of
dataflow graphs efficiently. The multi-rate extension of the Electrical and Electronics Engineers, Computer
method detailed in Section 3 was used to compile this task. Society, 26. January 2009.
A brief summary of the functional tests are shown in Table [7] M. Kooijman. Haskell as a higher order structural
1. Row 1 shows the characteristic numbers of the PID con- hardware description language, December 2009.
troller, while Row 2 shows the same for the MP3 SFB. The
subtasks of the MP3 SFB can be seen in Row 3, 4 and 5 [8] E.A. Lee and D.G. Messerschmitt. Synchronous data
separately. flow. Proceedings of the IEEE, 75(9):1235 – 1245, sept.
1987.
5. CONCLUSIONS
[9] Simon Marlow. Haskell 2010 language report, 2010.
A compiler program is developed on base of the novel method [10] Neil Mitchell. Rethinking supercompilation. SIGPLAN
introduced in this paper. The method meets the require-
ments that was set before: 1) it generate the VHDL from Not., 45:309–320, September 2010.
[11] K.K. Parhi. Algorithm transformation techniques for
concurrent processors. Proceedings of the IEEE,
77(12):1879 –1895, dec 1989.
[12] Mary Sheeran. ufp, an algebraic vlsi design language -
phd thesis, 1983.
[13] Andrew Tolmach. An external representation for the
ghc core language, 2009.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 24
Koper, Slovenia, 10-11 October
