LUT Cascade-Based Architectures for High Productivity Embedded Systems


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


Fast, flexible, cheap in hardware or low-power implementations of multiple-output Boolean functions are often required in embedded systems. The paper describes digital system architectures which embody some of these attributes. They are based on already known, and recently reinvented, representation of combinational logic by Look-Up Table (LUT) cascades. Theoretical background of cascade decomposition is revised and a relation to decision diagrams is pinpointed. The design of LUT cascades is discussed and a heuristic method of cascade synthesis is given. Three possible applications of LUT cascades are presented: combinational logic pipelines, efficient micro-programs with multi-way branching and fast logic simulation in software. It is shown that LUT cascades are quite flexible in making trade-offs between performance and cost by adjusting cascade length, complexity of its cells and multiplicity of cascades. The method of LUT cascades may be quite useful not only for high performance pipelined stream processing or embedded microprocessor or microcontroller firmware, but also in digital system simulation.
Copyright © 2018 Praise Worthy Prize - All rights reserved.

Keywords


LUT Cascades; Binary Decision Diagrams BDD; MTBDD; Iterative Disjunctive Decomposition; Multi-Way Branching

Full Text:

PDF


References


K.K. Maitra: Cascaded switching networks of two-input flexible cells, IRE Trans. Electron. Comput., pp, 136-143, 1962.

M. Yoeli : The Synthesis of Multivalued Cellular Cascades. IEEE Trans. On Computers, Vol. C-9, Nov. 1970, pp.1089-1090.

V. Dvořák: Decomposition Theory with Applications in Programmable Digital Systems. A thesis required for Doctor of Sciences (DrSc) degree. Faculty of Electrical Engineering, Technical University of Brno, May 1989. (224 pages, in Czech).

B.M. Moret: Decision Trees and Diagrams. Computing Surveys, Vol.14, No.4, Dec. 1982, pp. 593-623.

V. Dvořák: Automated Cascade Partitioning of Combi-national Logic. Proc. of the 1st conf. CompEuro 87, VLSI and Computers. Eds. W.E.Proebster and H.Reiner, Hamburg, 1987, pp. 315 - 318.

V. Dvořák: An optimization technique for ordered (binary) decision diagrams, Proceedings of the 6th Annual European Computer Conference CompEuro' 92, Hague, NL, 1992, pp. 1-4.

K. Nakamura, T. Sasao, M. Matsuura, K. Tanaka, K. Yoshizumi, H. Qin, and Y. Iguchi, "Programmable logic device with an 8-stage cascade of 64K-bit asynchronous SRAMs," Cool Chips VIII, IEEE Symposium on Low-Power and High-Speed Chips, April 20-22, 2005, Yokohama, Japan.

V. Dvořák: A cascade implementation of digital systems, In: Microprocessing and Micropro-gramming, North-Holland, Vol. 29, No. 1, 1990, pp. 151-163.

V. Dvořák: Microsequencer architecture supporting arbitrary branching up to 2^m targets, Computer Architecture News, IEEE Publ., US, March 1990, 1990, pp. 9-16

T.Sasao´s group publications:
www.lsi-cad.com/sasao/Papers/pub2001.html to 2007.html

A. Mishchenko, T. Sasao: Logic Synthesis of LUT Cascades with Limited Rais – A Direct Implementation of Multi-Output Functions. Technical report of IEICE, The Institute of Electronics, Information and Communication Engineers Vol.102, No.476(20021121) pp. 103-108. VLD2002-99, ISSN:09135685.

T. Sasao, Y. Iguchi, M. Matsuura, "LUT cascades and emulators for realizations of logic functions," RM2005, Tokyo, Japan, Sept. 5 - Sept. 6, 2005, pp.63-70.

V. Dvořák: Bounds on Size of Decision Diagrams, JUCS - The Journal of Universal Computer Science, Vol.3, 1997, pp. 2-23.

V. Dvořák: Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software. Proc. of the 14th IEEE Int. Conf. And Workshops on the Engineering of Computer-Based Systems. IEEE CS Press, Los Alamitos, CA, 2007, pp.178-185.

T. Sasao, S. Nagayama, and J. T. Butler, "Programmable numerical function generators: Architectures and synthesis system," FPL 2005, Tampere, Aug.24-26, 2005, pp.118-123.

H. Qin, T. Sasao, and Y. Iguchi, "An FPGA design of AES encryption circuit with 128-bit keys," GLS VLSI 2005, Chicago, IL, April 17-19, 2005, pp. 147-151.

T. Sasao and J. T. Butler, "Implementation of multiple-valued CAM functions by LUT cascades," ISMVL-2006, Singapore, May 17-20, 2006.

H.A. Curtis: A New Approach to the Design of Switching Circuits (Van Nostrand Comp. Inc., Princeton, N.J., 1962).

R. Drechsler, M. Herbstritt, B. Becker: Grouping heuristics for word-level decision diagrams. Proceedings of the 1999 IEEE International Symposium on Circuits and System ISCAS '99, pp. 411--415.

T. Sasao, J. T. Butler, and M. D. Riedel, "Application of LUT cascades to numerical function generators," The 12th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI2004), Oct. 18-19, 2004, Kanazawa, Japan, pp.422-429.

H. Nakahara, T. Sasao and M. Matsuura, "A fast logic simulator using an LUT cascade emulator," ASPDAC 2006, Yokohama Jan. 2006, pp.466-465.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize