MatrixComposer

Программа «MatrixComposer» предназначена для составления матриц B и C, а также для постановки задачи линейного программирования по информации о наборе инструкций.

Описание логической структуры

Основная часть кода программы matrixComposer выполняет:

• чтение данных из входного файла;
• создание и заполнение матриц B и C;
• разворачивание способов представления инструкции по разработанному алгоритму;
• вывод матриц B и C;
• вывод постановки задачи линейного программирования.

Важные для работы данные хранятся в программе в следующих переменных:

• список IS – набор инструкций, считанный из входного файла;
• список givenMethods – способы представления инструкций, считанные из входного файла;
• списки b, c – матрицы B и C соответственно;
• матрица instructionUsed содержит номера инструкций j, использованных в представлении инструкции i;
• матрица methods хранит способы представления инструкций j;
• список coef содержит номера элементов из матриц methods и instructionUsed для их комбинирования;
• вектор newPart хранит комбинацию из способов матрицы methods;
• вектор methodBasis хранит комбинацию из исходного способа представления инструкции i и номеров, использованных в разложении инструкций из матрицы instructionUsed;
• вектор newMethod хранит новый способ представления инструкции i.

Так же реализованы следующие вспомогательные функции:

• subSet(one, two) — Функция проверяет, является ли если one подмножеством two (one, two – способы представления инструкции). Пример: 1001 является подмножеством 1101, 0110 не является подмножеством 1000;
• clearMatrix() — Функция удаляет из матриц избыточные представления, получившиеся в результате последнего разворачивания;
• alreadyNotPresented(instrPresentation, newMethod) — Функция проверяет, включает ли в себя способ newMethod представления инструкции instrPresentation какой-либо из имеющихся способов для этой инструкции;
• gen(x, length) — Генерирует вектор для развертывания инструкций (x – количество комбинируемых инструкций, length - общее количество инструкций). Например: при x=11, length=10 функция вернет [6, 8, 9] так как 11 в двоичной системе с длиной слова 10 бит равно 0000001011, а активные биты находятся на местах 6, 8 и 9 (биты нумеруются слева направо с 0).

Используемые технические средства

Минимальные системные требования:

• оперативная память от 500 Мбайт;
• около 100 Кбайт на накопителе для хранения файла программы, а также файлов входных и выходных данных;
• операционная система Windows или *nix-совместимая;
• установленный интерпретатор языка Python версии 2.7 или выше и библиотека numpy версии 1.11 или выше;
• минимальные устройства ввода-вывода (монитор и клавиатура).

Установка и удаление

Программа не нуждается в установке. Для того, чтобы начать ее использование, необходимо скопировать файл matrixComposer.py в директорию. Для удаления достаточно удалить файл.

Вызов и загрузка

Вызов программы происходит из командной строки указанием ее имени и аргумента. Для запуска программы необходимо перейти в ее директорию и выполнить команду «./matrixComposer.py» (в *nix-совместимых операционных системах) или «python2 matrixComposer.py» (в Windows). В качестве атрибутов программе передается имя входного файла с описанием набора инструкций, например «./matrixComposer.py instructionSet.table».

Входные данные

Входной файл имеет расширение «.table» и содержит описание набора инструкций процессора. В первой строке через пробел перечисляются все инструкции из набора, затем в строках перечисляются способы представления инструкций. Инструкции в строке разделены пробелами, первая инструкция в строке (завершенная двоеточием) – та, которую представляет данный способ; перечисленные далее инструкции – те, которые используются в данном способе.

Разрешенное имя инструкции – последовательность символов, не содержащая пробелы и управляющие символы. Примеры разрешенных имен инструкций: «mov», «push», «mv1p».

Пример входного файла:

i1 i2 i3 i4
i2: i1 i3
i3: i1 i4

В этом примере набор инструкций состоит из четырех инструкций i1, i2, i3 и i4. Инструкция i2 может быть представлена при помощи i1 и i3, а инструкция i3 при помощи i1 и i4.

Выходные данные

Выходные данные – матрицы B и C и постановка задачи линейного программирования.

Матрицы B и C сохраняются в файлах с расширением .table, с дописанным к имени входного файла названия матрицы.

Постановка задачи линейного программирования сохраняется в файле с расширением LPX, имя которого совпадает с именем входного файла. Файл содержит следующую информацию:

• целевую функцию после ключевого слова «min»;
• именованные ограничения: v_i и w_i – первое и второе ограничения соответственно из системы (7);
• ключевое слово «int» с последующим перечислением x_i – указание на целочисленное решение по всем переменным.

Пример LPX-файла:

min: X1+X2+X3+X4;
v1: X1-Y1>=0;
v2: X1-Y5>=0;
v3: X1-Y6>=0;
v4: X1-Y7>=0;
v5: X2-Y2>=0;
v6: X3-Y3>=0;
v7: X3-Y5>=0;
v8: X4-Y4>=0;
v9: X4-Y6>=0;
v10: X4-Y7>=0;
w1: Y1>=1;
w2: Y2+Y5+Y7>=1;
w3: Y3+Y6>=1;
w4: Y4>=1;
int X1, X2, X3, X4;