Dekompozycja funkcjonalna z wbudowanym kodowaniem wejść dla układów FPGA opartych o komórki LUT

• Autorzy: Deniziak S. , Wiśniewski M.

Warianty tytułu

EN

An Integrated Input Encoding and Symbolic Functional Decomposition for LUT-Based FPGAs

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiona jest metoda symbolicznej dekompozycji funkcji z wielowartościowymi wejściami. Poprzez zastosowanie funkcjonalnej dekompozycji symbolicznej, proces kodowania binarnego wartości wejść jest zintegrowany z dekompozycją. Algorytmy optymalizacji stosowane w metodzie mają na celu minimalizację kosztu implementacji funkcji w układach FPGA. Wyniki wykonanych eksperymentów wykazują dużą efektywność opracowanej metody, dla większości benchmarków uzyskano znacznie lepsze wyniki niż w dotychczas stosowanych metodach.

EN

In this paper a method for decomposition of functions with multi-valued inputs is presented. Decomposition is performed simultaneously with encoding of symbolic values. In this way an impact of input encoding on decomposition efficiency is taken into consideration during optimization. The goal of our method is to find encoding that maximally simplifies functional decomposition. Input encoding is built in balanced decomposing strategy based on parallel end serial functional decompositions. Experimental results showed that the presented method significantly reduces the cost of FPGA implementations for most evaluated benchmarks.

Słowa kluczowe

PL

dekompozycja funkcji symbolicznych; FPGA; synteza logiczna

EN

FPGA; functional decomposition; logic synthesis

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 489--492
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Deniziak S.

autor

Wiśniewski M.

• Katedra Informatyki Technicznej, Politechnika Krakowska,

Bibliografia

• [1] J. A. Brzozowski, T. Łuba, “Decomposition of Boolean Functions Specified by Cubes”, Journal of Mult.-Valued Logic & Soft Computing, vol.9, 2003, pp. 377-417.
• [2] M. Nowicka, T. Łuba, M. Rawski, “FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation”, Proc. of the 6th Int. Conf. on Advanced Computer Systems, 1999, pp. 501-509.
• [3] R. K. Brayton, S. P. Khatri, “Multi-valued Logic Synthesis”, Proc. of the Int. Conference on VLSI Design, 1999, pp. 196-205.
• [4] P. Ashar, S. Devadas, A. R. Newton, “Sequential Logic Synthesis”, Kluwer Academic Pub., Norwell, 1992.
• [5] M. Martinez, M. J. Avedillo, J. M. Quintana, J. L. Huertas, “COPAS: A New Algorithm for the Partial Input Encoding Problem”, VLSI Design, Vol. 14 (2), 2002, pp. 171-181.
• [6] S. Malik, L. Lavagno, R. K. Brayton, A. Sangiovanni-Vincentelli, “Symbolic minimization of multilevel logic and the input encoding problem”, IEEE Transactions on CAD, vol.11, no. 7, 1992, pp. 825–843.
• [7] J. A. Brzozowski, J. J. Lou, “Blanket algebra for multiple-valued function decomposition”, Proc. of the International Workshop on Formal Languages and Computer Systems 1997, in. Algebraic Engineering, C.L.Nehaniv and M.Ito,eds.World Scientific, 1999, pp. 262-276.
• [8] R. Murgai, R. K. Brayton, A. Sangiovanni-Vincentelli, “Optimum Functional Decomposition Using Encoding”, Proc. of the DAC, 1994, pp. 408-414.
• [9] V. Muthukumar, “An Improved Input-Output Encoding Approach for Functional Decomposition”, Proc. of the Euromicro DSD, 2001.
• [10] S. Deniziak, „Kodowanie stanów dla układów FPD o architekturze opartej o komórki LUT", VII Krajowa Konferencja Reprogramowalne Układy Cyfrowe, 2004, str. 19-26.
• [11] M. Rawski, H. Selvaraj, T. Łuba, P. Szotkowski, “Application of symbolic functional decomposition concept in FSM implementation targeting FPGA devices”, Proc. of the 6th Intl Conf. on Computational Intelligence and Multimedia Applications, 2005, pp.153-158.