Numer: 07/2009 Str. 203-206
Autorzy: Marian Adamski , Monika Wiśniewska , Remigiusz Wiśniewski :
Tytuł: Redukcja rozmiaru mikroinstrukcji w procesie projektowania sterowników mikroprogramowanych
Streszczenie: Problem redukcji rozmiaru mikroinstrukcji jest ważnym etapem w procesie projektowania sterowników mikroprogramowanych. Jest to problem NP-trudny, dlatego też powstało wiele metod poszukujących rozwiązania. Zdecydowana większość zaproponowanych algorytmów bazuje na tradycyjnej teorii grafów. W artykule zaprezentowano nowatorską metodę redukcji rozmiaru mikroinstrukcji sterowników mikroprogramowanych, częściowo opierającą się na rozwiązaniach klasycznych. Metoda bazuje na wykorzystaniu teorii hipergrafów do wyznaczenia klas kompatybilności dla poszczególnych mikrooperacji. Mikrooperacje, które są parami kompatybilne mogą zostać zakodowane z wykorzystaniem mniejszej liczby bitów. Dzięki temu rozmiar pamięci układu mikroprogramowanego może zostać w znacznym stopniu zmniejszony. Zaproponowane rozwiązanie bazuje na wyznaczeniu hipergrafu dualnego, a następnie znalezieniu jego minimalnej transwersali (minimalnego pokrycia wierzchołkowego). Idea metody zostanie zilustrowana przykładem. Pokazane zostaną wszystkie kroki, jakie są niezbędne do zaprojektowania zmodyfikowanego układu pamięci. Zaproponowana metoda zostanie porównana z rozwiązaniami klasycznymi, bazującymi na teorii grafów.
Słowa kluczowe: hipergraf, klasa kompatybilności, sterownik (układ) mikroprogramowany, mikrooperacja, mikroinstrukcja, redukcja rozmiaru pamięci