Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 2011

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: selection of compatibility classes

Sortuj według:

Ogranicz wyniki do:

Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów

Wiśniewska M., Adamski M., Wiśniewski M.

Pomiary Automatyka Kontrola

2011

R. 57, nr 6

675-678

Redukcja pojemności pamięci jest istotnym etapem w procesie projektowania systemów dyskretnych. Często pojemność prototypowanej pamięci przekracza rozmiar docelowego bloku pamięci (np. w układach programowalnych FPGA). Najczęściej stosowanym rozwiązaniem jest redukcja rozmiaru mikroinstrukcji w projektowanym systemie. Algorytm bazuje na wyznaczeniu, a następnie selekcji klas kompatybilności poszczególnych mikrooperacji. W artykule zaprezentowane zostaną 2 autorskie algorytmy selekcji klas kompatybilności. Metody opierają się o wykorzystanie teorii hipergrafów (zastosowanie pokrycia wierzchołkowego). Proponowane rozwiązania zostaną gruntownie przeanalizowane oraz porównane z metodą tradycyjną, bazują na przekształceniach macierzowych.

The problem of memory size reduction is a very important part of design process of discrete systems. The prototyped memory size very often exceeds the size of memory blocks offered by programmable devices (in example FPGAs). One of the most popular solutions to this problem is memory size reduction. The reduction process is based on selection of the compatibility classes of microoperations. Three methods of selection of compatibility classes are presented in the paper. The first one is a well-known method of selection, to which the fast reduction algorithm is applied. The algorithm bases on the matrix operations, which can also be represented as reduction of the hypergraph incidence matrix. In each step some vertices and edges are reduced. The reduced matrix holds the final result. The two other solutions introduced in the paper are based on the idea of computation of the minimal transversal (vertices covering) of hypergraphs. Proper microop-erations are represented by the hypergraph vertices, while compatibility classes are described by the hyperedges. Therefore, any method of hypergraph transversal calculation can be applied to achieve the selection. In the paper the authors propose and analyse the effectiveness of backtracking and greedy algorithms. The proposed solutions are compared with the traditional method, which is based on transformation of the hypergraph incidence matrix. The obtained results of experiments are analysed and discussed in detail.