Разработка эффективных форматов микрокоманд для различных способов микропрограммирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
тания очередной вершины из множества кандидатов на расширение подграфа;
-SubtractSet(List set2) - метод, в котором реализовано вычитание одного множества из другого;
-List G(int vert) - метод, определяющий список вершин, не смежных с указанной в параметре.
Класс содержит поле public static int[,] gmatrix, содержащее в себе текущий обрабатываемый граф.
6.2.3 Класс Program
Класс предназначен непосредственно для кодирования набора микрокоманд одним из четырех способов микропрограммирования - горизонтальным, вертикальным, горизонтально-вертикальным или вертикально-горизонтальным. Содержит следующие поля:
-public static List MasMK - двумерный динамический массив, предназначенный для хранения исходной микропрограммы;
-public static List MasMO - двумерный динамический массив, предназначенный для хранения информации о том, в каких микрокомандах встречается каждая микрооперация;
-public static List listOfMicOp - список номеров микрооперций, встречающихся в микрпрограмме;
-public static int dlinKod - поле типа int, которое хранит длину формата команды при любом виде кодирования;
-public static bool errorMOcopy - булевый флаг, свидетельствующий о наличии ошибки В микрокоманде встречаются одинаковые микрооперации, изначально имеет значение false.
Методы, реализованные в классе Program:
-static void Main() - главный метод, который запускает программу;
-public static string ReadFile(String path) - считывание файла с исходным списком микроопераций;
-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), алгоритм Брона - Кербоша для поиска максимальных подграфов, алгоритм поиска минимального покрытия, алгоритм минимизации логических функций методом Квайна.
6.3.1 Алгоритм Брона - Кербоша
Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа [16].
Алгоритм оперирует тремя множествами вершин графа:
-множество compsub - множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. С