By far most Term Rewriting Systems (TRS) in EDA are used for verification, which means bottom-up use. The by the year 2002 the only known example of top-down use of TRS in EDA was the KARL-based automatic generation of an integer multiplier floorplan from the Math formula, as published in the early 80ies. This has been investigated in 2001 by the TRS expert Prof. Mauricio Ayala-Rincón from Universidad de Brasilia. The following equations are the set of rules to be used by the TRS system for this 4 bits wide integer multiplier example.
Here "shl" is the KARL language's shift left operator and its prefix i or j or (i+j) or (i-j) is the number of bit positions to be shifted and "shr" stands for "shift right". The following equation is the design task: a 4 bit integer multiplier:
For more details on the term rewriting sequence and its results see:
The following figure shows the ABL graphic editor's presentation illustrating the result: a 4 bit integer multiplier, where "lsb" selects the least significant bit.
The following image shows the layout of the multiplier circuit having been manufactured for testing purposes via the MPC service of the E.I.S. Project.
This term rewriting example has been published in the early 80ies, but has been ignored by the TRS experts. In 2001 Prof. Ayala-Rincon investigated this and came to the conclusion, that working for verification, all EDA applications of TRS had used only bottom-up methods, and, that this multiplier design example is still new, since it is the only known top-down TRS application in the EDA scene. The following publications are the result from this cooperation.
Reiner Hartenstein "Fundamentals of Structured Hardware Design - A Design Language Approach at Register Level"; North Holland Publ. Co./American Elsevier (Elsevier Scientific), Amsterdam / New York, 1977 <see the book>
R. Hartenstein: KARL Subset used as a Design Algebra; ACM SIGDA Newsletter, vol. 10, no. 2, August 1980; <pdf>
R. Neto, M. Ayala-Rincón, R. Jacobi, C. Llanos, R. Hartenstein: Applying ELAN Strategies in Simulating Processors over Simple Architectures; 2nd int'l Workshop on Reduction Strategies in Rewriting and Programming (WRS 2002); Copenhagen, Denmark, July 21, 2002 pdf
R. M. Neto, M. Ayala-Rincón, R. P. Jacobi, C. Llanos, R. Hartenstein: Applying ELAN Strategies in Simulation Processors over Simple Architectures; (reprint) Electronic Notes in Theoretical Computer Science (ENTCS) 70/6; Elsevier Science Pubnlishers pdf
M. Ayala-Rincón, R. P. Jacobi and C. Llanos, R. Hartenstein: Designing Arithmetic Digital Circuits via Rewriting-Logic, - pdf - wann ??? wo ???
M. Ayala-Rincón, R. Maya Neto, R. Jacobi, C. Llanos, R. Hartenstein: Architectural Specification and Simulation Through Rewriting-Logic; Colombian J. of Computation 2003 pdf
(s) (together with M. Ayala-Rincón, R. P. Jacobi, and C. Llanos): Modeling Reconfigurable Systolic Arrays for Computing Algebraic Operations via Rewriting-Logic, pdf wann ? wo ??
M. Ayala-Rincón, R. Nogueira, C. Llanos, R. Jacobi, R. Hartenstein: Efficient Computation of Algebraic Operations over Dynamically Reconfigurable Systems Specified by Rewriting-Logic Environments, - pdf. - pdf2 - In IEEE CS press Proc. 23rd SCCC, pp 60-69, 2003..
M. Ayala-Rincón, R. B. Nogueira, R.
C. Llanos, R.
a Reconfigurable System for Computing the FFT in Place via Rewriting-Logic,
pdf2 -. In IEEE CS Press Proc. 16
C. Llanos (speaker), M. Ayala-Rincón, R. B. Nogueira, R. P. Jacobi, R. Hartenstein: Modeling Dynamically Reconfigurable Systems via Rewriting-Logic, 2nd Dagstuhl Seminar on Dynamically Reconfigurable Systems: Dagstuhl, Germany, July 20-25, 2003 - pdf -
R. Hartenstein, R. P. Jacobi, M. Ayala-Rincón, C. Llanos: Using Rewriting-Logic Notation for Functional Verification in Data-Stream Based Reconfigurable Computing, pdf pdf2 . In Forum on Specification and Design Languages - FDL 03, Frankfurt, Germany, Sep 23-26, 2003
M. Ayala-Rincón, R. Hartenstein, R. Maya Neto, R. P. Jacobi and C. Llanos: Architectural Specification, Exploration and Simulation Through Rewriting-Logic, pdf, 1. Colombian Journal of Computation, Vol 3(2):20-34, 2003.
M. Ayala-Rincón, L. Carvalho, C. Llanos, R.
Systems for Sequence Alignment and for General Dynamic Programming,
M. Ayala-Rincón, R.
L. G. A. Carvalho, C. Llanos, R.
and Prototyping Dynamically Reconfigurable Systems for Efficient Computation of
Dynamic Programming Methods,
- pdf2 - . ACM Proc. 17
C. LLanos, R. P. Jacobi, M. Ayala-Rincón, R. Hartenstein: A Dynamically Reconfigurable System for Space-Efficient Computation of the FFT, - pdf - pdf2 - Soc. Mex. Comp. Proc. International Conference on Reconfigurable Computing and FPGAs 2004 - ReConFig'04, pp 360-369, Colima, Mexico, Sep 20-21, 2004
R. Jacobi, M. Ayala-Rincón, L. Carvalho, C. Llanos, R. Hartenstein: Reconfigurable Systems for Sequence Alignment and for General Dynamic Programming; Genetics and Molecular Research, 4(3):543-552, 2005. pdf
C. Morra, J. Becker, M. Ayala-Rincón, R. Hartenstein: FELIX: Using Rewriting-Logic Functionally Equivalent Implementations; 15th Int'l Conf. on Field-Programmable Logic and Applications FPL 2005, Aug 24-26, 2005, Tampere, Finland, pdf
M. Ayala-Rincón, C. Llanos, R. Jacobi, R. Hartenstein. Prototyping Time- and Space-Efficient Computations of Algebraic Operations over Dynamically Reconﬁgurable Systems Modeled by Rewriting-Logic. ACM Trans. Design Autom, of Electronic Systems, 11(2), 2006. pdf
C. Morra, M. Sackmann, J. Becker, R. Hartenstein: Using Rewriting Logic To Generate Different Implementations of Polynomial Approximations in Coarse-Grained Architectures (2006) pdf
C. Morra , M. Sackmann , S. Shukla , J. Becker , R. Hartenstein: From Equation To Vhdl: Using Rewriting Logic For Automated Function Generation (2006) - pdf - wo ???
Carlos Morra: A Flexible Framework for Hardware/Software Design Space Exploration using Rewriting Logic; Ph.d. dissertation; Defense: 20.05.2010 (Karlsruhe Institute of Technology); Dissertation advisors. Mauricio Ayala-Rincón; Jürgen Becker, Reiner Hartenstein - pdf -