- Tytuł:
-
Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów
Application of the hypergraph theory to selection of compatibility classes - Autorzy:
-
Wiśniewska, M.
Adamski, M.
Wiśniewski, M. - Powiązania:
- https://bibliotekanauki.pl/articles/152400.pdf
- Data publikacji:
- 2011
- Wydawca:
- Stowarzyszenie Inżynierów i Techników Mechaników Polskich
- Tematy:
-
hipergraf
selekcja klas kompatybilności
transwersale (pokrycie wierzchołkowe) hipergrafu
mikrooperacja
redukcja pojemności pamięci
hypergraph
selection of compatibility classes
transversals (hitting set), microoperation
memory size reduction - Opis:
-
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. - Źródło:
-
Pomiary Automatyka Kontrola; 2011, R. 57, nr 6, 6; 675-678
0032-4140 - Pojawia się w:
- Pomiary Automatyka Kontrola
- Dostawca treści:
- Biblioteka Nauki
Artykuł