Разработка программно-вычислительного комплекса, предназначенного для разработки эффективных форматов микрокоманд для различных способов микропрограммирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
итывание файла с исходным списком микроопераций;
-public static int FindNumberOfOperation() - создание массива, хранящего список всех микроопераций;
-private static bool NotDuplicate(string p) - проверка исходных данных на корректность, а именно поиск повторяющихся микрокоманд в микрооперации;
-public static int[,] gorizont() - кодирование микроопераций горизонтальным способом;
-private static bool FindOperation(string p, int stroka) - поиск микрооперации заданного номера в микрокоманде;
-internal static int[,] vertikal() - кодирование набора микрокоманд горизонтальным способом;
-private static int StrokaMaxRank(int[,] arr) - поиск максимального ранга строки в массиве с учетом уже выбранных строк;
-private static int StrokaMaxRankFromKod(int[,] arr) - ищет строку с максимальным рангом в сгенерированном массиве кодов с учетом уже выбранных строк, используется для генерации кодов вертикального кодирования;
-internal static string[] getBoolForGorizont() - выдает список булевых функций для горизонтального кодирования;
-internal static string[] getBoolForVertical() - выдает список булевых функций для вертикального кодирования;
-private static void getTableMicroOperation(int[,] verKod) - поиск иформации о том, в какой микрокоманде хранится заданная микрооперация;
-internal static string[] optimisationBoolForVert() - выдает список оптимизированных булевых функций для вертикального кодирования;
-private static void conglutination(int num) - поглощение строк ядерной строкой при минимизации таблицы покрытий;
-private static bool skleivanie(int i, int g, int num) - проверка на склеиваемость списка булевых функций;
-internal static int[] FindMinCover(int[,] workArray) - поиск минимального покрытия графа;
-internal static string gorVertKod() - кодирование горизонтально-вертикальным способом;
-private static int YestStroka(List list_2) - поиск пустых строк в исходном файле;
-private static List subGrafs) - формирование универсальной группы микроопераций;
-internal static string vertGorKod() - кодирование вертикально-горизонтальным способом;
-private static int[,] FindSovmestOper() - поиск совместимых микроопераций в группе.
6.2.4 Класс PermutationsWithRepetition
Класс предназначен для генерации всех возможных комбинаций заданной длины для заданного множества элементов. Эти комбинации далее используются для формирования кодов. Содержит поля:
-private int variationLength - поле типа int, которое определяет длину комбинаций;
-private int[] source - массив исходных элементов, в котором производятся перестановки.
Класс содержит единственный метод int[,] getVariations( ), который возвращает двумерный числовой массив, содержащий коды заданной длины.
6.2.5 Класс Statistic
Класс предназначен для сбора статистических данных в таблицу, оценку сложности, а так же последующий вывод их на экран в виде графиков.
Методы, реализованные в классе:static int [, ]getStatistData() - создание массива, хранящего статистич данные (длина кода, сложность ФСМО).Данные считываются из файла Exel, лежащего в директории проекта;
public static writeStatistData(int [, ]) - запись статистических данных в двумерный массив;
public static grafiki(int[,]) - отображение данных в виде графиков.
6.3 Описание основных алгоритмов
В разработанном программно-вычислительном комплексе использованы следующие алгоритмы: четыре алгоритма микропрограммирования (описанные в пункте 2.3), алгоритм Брона - Кербоша для поиска максимальных подграфов, алгоритм поиска минимального покрытия, алгоритм минимизации логических функций методом Квайна. Схемы алгоритмов функционирования комплекса представлены на чертеже СевНТУ 7.091501.4.П.
6.3.1 Алгоритм Брона - Кербоша
Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа [16].
Алгоритм оперирует тремя множествами вершин графа:
-множество compsub - множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно;
-множество candidates - множество вершин, которые могут увеличить compsub;
-множество not - множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.
Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.
ПРОЦЕДУРА extend (candidates, not):
ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1.Выбираем вершину v из candidates и добавляем ее в compsub;
2.Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v;
.ЕСЛИ new_candidates и new_not пусты;
4.ТО compsub - клика;
5.ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not);
6.Удаляем v из compsub и candidates и помещаем в not [16].
6.3.2 Алгоритм поиска минимального покрытия
Для нахождения минимального покрытия используются такие алгоритмы:
-алгоритм полного перебора. Основан на методе упорядочения перебора подмножеств множества А;
-алгоритм граничного перебора по вогнутому множеству. Основан на одноименном методе сокращения перебора;
-алгоритм разложения по столбцу таблицы покрытия. Основан на методе сокращения перебора, который состоит в рассмотрении только тех строк таблицы покрытия, в которых имеется 1 в выбранном для разложения столбце;
-алгоритм сокращения таблицы покрытия. Основан на мет