262080484

2. Rozwiązanie problemu dużej złożoności obliczeniowej algorytmu redukcji w programie PROTON

Ze względu na dużą złożoność obliczeniową zastosowałem nietypową strukturę danych. Wszystkie dane pośrednie w programie są przechowywane w 32 bitowym słowie. Umożliwia to szybkie operacje porównania całych wierszy i kolumn w jednym cyklu maszynowym procesora, co znacznie przyspieszyło program.

2.1. Wyznaczenie minimalnych pokryć M w programie PROTON

Wyznaczenie minimalnych pokryć M jest bardzo pracochłonne ponieważ trzeba sprawdzić wszystkie kombinacje kolumn, dlatego też zastosowałem optymalizację, która umożliwia pominięcie bardzo wielu porównań. W poniższym przykładzie zaczynamy wyznaczanie minimalnego pokrycia od kolumny a, która na trzeciej pozycji (wierszu) ma wartość zero. Do następnego etapu brane są tylko te kolumny, które mają jedynkę na trzeciej pozycji. Kolumny te są następnie łączone z kolumną a przy użyciu funkcji OR, a następnie sprawdzane jest czy kolumna składa się wyłącznie z jedynek, jeśli nie w następnym kroku dokładana jest kolumna, która ma jedynkę w brakującym miejscu. Jeśli wynik sklejania kolumn składa się z samych jedynek to minimalnym pokryciem są kolumny które zostały sklejone. Tak wyznaczone pokrycia kolumn trzeba jeszcze porównać z innymi wyszukanymi dla tej samej tablicy, ponieważ pojawia się dużo powtórzeń albo wyników z większym pokryciem.

Tabela 12 Przeszukiwane macierzy M w celu wyznaczenia minimalnych pokryć Źródło: opracowanie własne

a	b	c	d	e	f	9	h	i	j
i	i	0	0	0	1	0	i	0	0
i	0	0	0	0	1	0	0	i	0
0	0	1	0	i	0	0	0	0	1
0	0	1	0	0	1	0	0	1	0
0	0	1	0	0	1	0	1	0	0

18