W artykule zostanie przedstawiona metoda umożliwiająca syntezę skończonego automatu stanów typu Moore’a z wbudowanym blokiem pamięci (ang. Embedded Memory Blocks, EMB) w strukturach programowalnych typu FPGA (ang. Field Programmable Gate Array, FPGA). Zaproponowana metoda bazuje na kodowaniu pewnej wybranej części zbioru warunków logicznych przez dodatkowe zmienne. W artykule zostanie zaprezentowany przykład projektowania układu.
EN
The model of the Moore finite state machine (FSM) is very often used for representing a control unit [1]. Nowadays, two classes of programmable logic devices: complex programmable logic devices (CPLD) and field-programmable gate arrays (FPGA) are used for implementing logic circuits of FSMs [2, 3]. This paper deals with FPGA-based Moore FSMs. It is very important to use EMBs in the logic design. It leads to decreasing in both the number of interconnections and chip area occupied by an FSM logic circuit. In turn, it results in decrease in the propagation time as well as the consumed power of a circuit [9]. A lot of methods for implementing an FSM logic circuit with RAMs are known [10 – 19]. For rather complex FSMs, the method of replacement of logical conditions [20] is used. In this case, optimization efforts target hardware reduction for the multiplexer executing the replacement. In this paper we propose a method based on existence of pseudoequivalent states of the Moore FSM for solving this problem [21]. The method is based on replacement of some part of the set of logical conditions by additional variables. It results in diminishing the number of LUTs in the multiplexer used for replacement of logical conditions. To represent a control algorithm, the language of graph-schemes of algorithms [20] is used. An example of application of the proposed design method is given.
W artykule przedstawiona została koncepcja implementacji sprzętowej algorytmu MD5 z wykorzystaniem mikroprogramowanego układu sterującego. Cechą charakterystyczną rozwiązania jest wykorzystanie osadzonych bloków pamięci do realizacji układu sterującego. Przedstawione rozwiązanie jest przeznaczone przede wszystkim do realizacji w układach FPGA. W artykule przedstawione zostały wyniki syntezy kilku wybranych struktur układów mikroprogramowanych. Otrzymane wyniki zostały porównane do typowej realizacji w postaci automatu Moore'a.
EN
The paper presents an example of application of Compositional Microprogram Control Unit (CMCU) to hardware implementation of MD5 algorithm. The MD5 algorithm is a widely used hash function with a 128-bit hash value. MD5 is used in many security applications, for example to hash passwords in FreeBSD operating system [14]. MD5 is also commonly used to check the integrity of files. MD5 was designed by Ron Rivest in 1991 [10]. Other similar algorithms are SHA [7] and RIPEMD [6]. The hardware implementation of MD5 in FPGAs is usually based on embedded memory blocks (EMB) because the algorithm uses a lot of constants during calculations [8]. In the paper the authors present an alternative solution in which constants are generated by CMCU (Fig. 3) circuit. The CMCU is also based on EMB. It can generate constants for MD5 and also signals for other tasks. The research results show that CMCU requires less hardware amount when compared to traditional Moore FSM (Tab. 1). The results were obtained using Xilinx ISE 12.1 and Xilinx Spartan-3 (xc3s50-5pq208) [13]. The models of control units were generated by the authors' software.
W artykule przedstawiona została metoda syntezy umożliwiająca zmniejszenie liczby tablic LUT potrzebnych do realizacji układu mikroprogramowanego z współdzieleniem kodów. Metoda jest przeznaczona dla układów FPGA z osadzonymi blokami pamięci. Część kombinacyjna układu mikroprogramowanego jest realizowana z użyciem tablic LUT, natomiast pamięć sterująca z użyciem osadzonych bloków pamięci. Redukcję liczby tablic LUT osiągnięto dzięki wykorzystaniu klas łańcuchów pseudorównoważnych. W artykule przedstawiono przykład zastosowania proponowanej metody oraz rezultaty eksperymentów.
EN
The paper presents new research results of synthesis of Composi-tional Microprogram Control Unit (CMCU) with Codes Sharing. The method allows reduction of look-up table elements in the combina-tional part of the control unit. The method assumes application of field-programmable gate arrays for implementation of the combinational part, whereas embedded-memory blocks are used for implementation of its control memory. Programmable logic devices are nowadays widely used for implementation of Control Units (CU) [16, 18]. The problem of the CU optimisation is still actual in computer science and it solution permits to decrease the cost of the system [17]. The proposed method is oriented on reduction of hardware amount of CMCU addressing circuit by placing codes of classes of pseudoequivalent states in the control memory. These classes are formed by division of the set of Operational Linear Chains (OLC) into partitions which correspond to pseudoequivalent states of Moore FSM [4]. The research results show that application of the method to tested control algorithms gives on average 50% decrease in hardware amount when compared to CMCU based structure (Tab. 2). The results were obtained using Xilinx ISE. The models of control units were generated by the authors' software using the control algorithms from [15].
Osadzone bloki pamięci w układach mikroprogramowanych mogą być konfigurowane w ograniczonym zakresie. Oznacza to, że w wielu przypadkach część pamięci sterującej pozostaje niewykorzystana. Zaproponowana przez autorów metoda syntezy pozwala wykorzystać niezagospodarowane obszary pamięci do redukcji części kombinacyjnej mikroprogramowanej jednostki sterującej. Rozwiązanie opiera się na umieszczeniu w pamięci sterującej kodów klas łańcuchów pseudorównoważnych, dzięki czemu możliwe jest uproszczenie tabeli przejść układu. Przeprowadzone eksperymenty dowodzą, że zaproponowana przez autorów metoda pozwala zredukować zasoby sprzętowe potrzebne do implementacji układu mikroprogramowanego z współdzieleniem kodów w przypadku liniowych sieci działań.
EN
The paper presents a synthesis method of compositional microprogram control unit with the code sharing. The method is addressed to FPGA devices with embedded memory blocks. In the proposed method the combinational part of microprogram control unit is implemented with LUT tables and the control memory is implemented with embedded memory blocks. The size of combinational part of the control unit is reduced in comparison to the base structure by introduction of the classes of pseudoquivalent operational linear chains. The article contains an example of the application and the results of synthesis in Xilinx ISE.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Two methods are proposed targeted at reduction in the number of look-up table elements in logic circuits of compositional microprogram control units (CMCUs) with code sharing. The methods assume the application of field-programmable gate arrays for the implementation of the combinational part of the CMCU, whereas embedded-memory blocks are used for implementation of its control memory. Both methods are based on the existence of classes of pseudoequivalent operational linear chains in a microprogram to be implemented. Conditions for the application of the proposed methods and examples of design are shown. Results of conducted experiments are given.
Method of decreasing of the number of PAL macrocells in logic circuit in Moore FSM is proposed. This method is based on the use of free outputs of embedded memory blocks to represent the code of the class of pseudoequivalent states. The proposed approach allows minimizing the hardware without decreasing of the digital system performance. An example of application of the proposed method is given.
PL
Wzrost zużycia zasobów sprzętowych jest jednym z aktualnych problemów w logicznych układach jednostki sterującej. Specyficzną cechą układu PAL jest duża ilość wejść makrokomórek i ilość termów na makrokomórkę. Cechą automatów Moore'a jest istnienie pseudorównoważnych stanów i regularny charakter mikrooperacji, które daje się implementować z użyciem EMB (ang. Embedded Memory Blocks). W artykule proponowana jest metoda pozwalająca zmniejszyć wykorzystanie zużycia sprzętowego bez zmniejszania wydajności systemów cyfrowych, przy użyciu wyżej wspomnianych cech. Podany również jest przykład aplikacji zaproponowanego rozwiązania.
Method of decrease in the number of PAL macrocells in logic circuit of Moore FSM is proposed. This method is based on the implementation of free outputs of embedded memory blocks to represent the code of the class of the pseudoequivalent states. The proposed approach allows minimizing hardware without decreasing of the digital system performance. An example of application of the proposed method is given.
PL
Wzrost zużycia zasobów sprzętowych jest jednym z aktualnych problemów w logicznych układach jednostki sterującej. Specyficzną cechą układu PAL jest duża ilość wejść makrokomórek i ilość termów na makrokomórkę. Cechą automatów Moore'a jest istnienie pseudorównoważnych stanów i regularny charakter mikrooperacji, które daje się implementować z użyciem EMB (ang. Embedded Memory Blocks). W tym artykule proponowana jest metoda pozwalająca zmniejszyć wykorzystanie zużycia sprzętowego bez zmniejszania wydajności systemów cyfrowych, przy użyciu wyżej wspomnianych cech.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Sensible application of programmable structures to the realization of digital systems cannot take place without computer aided design systems. It is particularly important when the design is intended for novel programmable structures containing LUT-based cells and embedded memory blocks, since traditional methods for technology mapping are oriented towards gate structures and based on minimization and factorization of Boolean functions. This article focuses on finite state machine synthesis including logic optimization techniques, the technology mapping techniques, and the techniques that provide the resulting circuits with concurrent error detection capability. It is shown that a considerably more effective method of synthesis intended for CPLD and FPGA structures is based on the decomposition scheme.
W pracy przedstawiona została metoda zmniejszania ilości makro-komórek w układach typu PAL przy pomocy skończonych automatów stanów z wyjściami typu Moore'a. Metoda ta jest oparta na wykorzystaniu nieużywanych wyjść osadzonych obszarów pamięci w celu reprezentacji kodu klasy pseudo-równoważnych stanów. Zaproponowane podejście pozwala zmniejszyć ilość wymaganego zużycia sprzętowego bez zmniejszenia wydajności systemów cyfrowych. Podany również jest przykład aplikacji zaproponowanego rozwiązania.
EN
Method of decrease of number of PAL macrocells in the circuit of Moore FSM is proposed. Method is based on usage of free outputs of embedded memory blocks to represent the code of the class of the pseudoequivalent states. Proposed approach permits to decrease the hardware amount without decrease of digital system performance. An example of application of proposed method is given.
Method of decrease of number of PAL macrocells in the circuit of Moore FSM is proposed. Method is based on usage of free outputs of embedded memory blocks to represent the code of the class of the pseudoequivalent states. Proposed approach permits to decrease the hardware amount without decrease of digital system performance. An example of application of proposed method is given.
PL
W pracy przedstawiona została metoda zmniejszania ilości makro-komórek w układach typu PAL przy pomocy automatów Moore'a FSM. Metoda ta jest oparta na wykorzystaniu nieużywanych wyjść osadzonych obszarów pamięci w celu reprezentacji kodu klasy pseudo-równoważnych stanów. Zaproponowane podejście pozwala zmniejszyć ilość wymaganego zużycia sprzętowego bez zmniejszenia wydajności systemów cyfrowych. Podany również jest przykład aplikacji zaproponowanego rozwiązania.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.