go to Xputer pages

homepage | impressum |  survey |  MM | TRS   Lit   02   

KARL-based TRS

TU Kaiserslautern

 Karlsruhe Institute of Technology (KIT) homepageInstitut für Technik der Informationsverarbeitung (ITIV) des Karlsruher Institut für Technologie (KIT)


For a survey on KARL-related pages click here                  

Term Rewriting (TR) using KARL

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:

http://xputers.informatik.uni-kl.de/karl/karl_history_fbi.html#3.1 algebraic structured design 

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: Structured Hardware Design - a KARL-based integer multiplier floorplan design calculus; Dec 1978, Computer Structures Chair, TU Kaiserslautern, Germany <pdf>  <ppt>  <ppt2>


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. P. Jacobi, C. Llanos, R. Hartenstein: Modeling a Reconfigurable System for Computing the FFT in Place via Rewriting-Logic  pdf  -  pdf2  -. In IEEE CS Press Proc. 16th Symposium on Integrated Circuits and System Design - SBCCI 03, pp 205-210, São Paulo, Brasil, (Sep 8-11, 2003).   

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.     


R. Jacobi, M. Ayala-Rincón, L. Carvalho, C. Llanos, R. Hartenstein: Reconfigurable Systems for Sequence Alignment and for General Dynamic Programming,  pdf 3rd Brazilian Workshop on Bioinformatics - WOB 2004, pp 25-32 Brasília D. F., Brasil, Oct. 20-22, 2004       

M. Ayala-Rincón, R. Hartenstein, R. Jacobi and C. Llanos: Designing Arithmetic Digital Circuits via Rewriting-Logic,  - pdf  - In preparation, 2004.           

M. Ayala-Rincón, R. P. Jacobi, L. G. A. Carvalho, C. Llanos, R. Hartenstein: Modeling and Prototyping Dynamically Reconfigurable Systems for Efficient Computation of Dynamic Programming Methods, -  pdf  -  pdf2  - . ACM Proc. 17th Symposium on Integrated Circuits and System Design - SBCCI 04, pp 248-253 Porto Galhinas, Brasil, (Sep 7-11, 2004).          

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 Reconfigurable 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  - 

For a survey on KARL-related pages click here

About Term Rewriting:  J. W. Klop: Term Rewriting Systems; University of Bremen, Germany  RTA conference homepage  Loria Rewriting homepage N.N.: Rewriting; Wikipedia  N.N.: Termersetzungssystem;  Wikipedia