Описание (Задание 1 - Структурный анализ схем)

Практическое задание №1.Структурный анализ схем.Общее описание заданияЗадание представляет первую часть составного задания по анализ и классификациилогических схем. Основная цель указанного задания реализация алгоритмов извлеченияструктурных параметров для заданной логической схемы. При выполнении заданияможно выделить следующие основные этапы:1.реализация структур данных для хранения структуры логической схемы;2.реализация транслятора, позволяющего преобразовывать схемы, записанныев формате Verilog, в реализованные на предыдущем этапе структуры данных;3.выбор множества анализируемых структурных параметров и реализацияалгоритмов их расчета.Задание выполнять в папке Spring 2015 – Homework 1 в Вашей папке именной папкев Dropbox. Так как задание выполняется в паре, то папка должна быть разделяемой междувсеми исполнителями задания.

Задание должно быть выполнено с использованиемсистемы контроля версия Git (фактически, в этой папке Вы должны в самом началесоздать Git репозиторий). Работа каждого студента будет оцениваться в первую очередьпо тем commit-ам, которые он сделал. Так как это Ваш первый опыт парной работы сиспользованием системы контроля версий, рекомендуется, чтобы у Вас была локальнаякопия сделанной работы. Это позволит минимизировать риск потери работы принесогласованной работе с системой контроля версий.Распределение студентов по группам будет размещено на сайте кафедры.Для тестирования результатов выполнения практического задания на сайте кафедрыбудет выложен набор тестовых схем.

Кроме того, программа будет тестироваться наскрытом наборе схем.Результаты выполнения практического задания сопровождаются отчетом опроделанной работе, подробной инструкцией по сборке и запуске программы и makefileом.Любые вопросы по заданию присылать по электронной почте на следующий адрес:mikle.shupletsov@gmail.com.Тема письма имеет следующий формат: [318] [Фамилия Имя] [Вопрос].Реализация структур данных для хранения структуры логическойсхемы.Требуется реализовать согласованную структуру классов, которая позволит хранитьграф рассматриваемой схемы и выполнять необходимые операции для вычислениявыбранного набора структурных параметров.

Для того, чтобы ускорить разработку,предполагается, что для реализации основной функциональности классов будетиспользоваться библиотека Boost Graph Library(http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/index.html). Для того, чтобы объемрепозитория на Dropbox был разумным, библиотеку загружать в репозиторийзапрещается. Библиотека должна быть загружена на локальную машину исоответствующим образом прописана в путь.Реализация транслятора с языка Verilog.Требуется реализовать транслятор схем из языка Verilog в разработанные напредыдущем этапе структуры данных. При этом считается, что схемы заданы так, чтоиспользует довольно небольшое подмножество конструкций языка Verilog. На схемунакладываются следующие ограничения:1.

схема комбинационная (не содержит регистров);2. схема состоит из одного модуля с именем top;3. схема представлена на уровне функциональных элементов (gate-level) и при этомиспользуются только стандартные примитивы языка Verilog (buf, not, and, nand, or,nor, xor, xnor), которые могут иметь произвольное конечное число входов (кромеbuf и not);4. все элементы соединяются только при помощи wire (соединения могут быть какскалярные, так и векторные).Пример входного файла на языке Verilog:module top(a, sel, out);input [2:0] a;inputsel;output [1:0] out;wire [2:0] a;wiresel;wire [1:0] out;wire [3:0] z;wire w1, w2, w3, w4, w5, w6, w7;not (z[0], a[0]);xnor (z[1], a[0], a[1]);or (w1, a[0], a[1]);xnor (z[2], a[2], w1);and (w2, a[2], a[1]);and (w3, a[2], a[0]);nor (z[3], w2, w3);nor (w4, sel, z[3]);nor (w5, sel, z[2]);and (w6, sel, z[1]);and (w7, sel, z[0]);or (out[1], w4, w6);or (out[0], w5, w7);endmoduleФункциональность реализованного транслятора должна быть достаточной для того, чтобыобрабатывать логические схемы, удовлетворяющие указанным ограничениям.

Другиеконструкции языка Verilog реализовывать не требуется.Структурные параметры схемы.Предполагается, что в рамках задания каждая группа реализует алгоритмы расчетавыбранного ими набора структурных параметров логической схемы. Структурнымипараметрами считаются любые параметры, связанные со структурой графа схемы.Например, параметры вершин и ребер схемы, структура путей и подсхем в схеме и т.д.При этом этот набор должен включать в себя как ряд обязательных параметров (у каждойгруппы набор обязательных параметров определяется индивидуально), так и рядпараметров по выбору группы. При этом поощряется реализация алгоритмов расчетадополнительных параметров, которая будет оцениваться отдельно.Распределение обязательных параметров по группам:1.

Группа №1:a. средняя степень вершин в графе схемы;b. спектр длин путей в графе схемы (для каждого значения длины пути в схеме(от минимального до максимального значения) вычисляется доля путей(рассматриваются только пути от входов до выхода схемы), длина которыхравна указанному значению);c. среднее число вершин во входном конусе вершины в графе схемы;2.

Группа №2:a. спектр степеней вершин (для каждого значения степени вершины (отминимального до максимального значения) вычисляется доля вершин,степень которых равна указанному значению);b. средняя длина пути в графе схемы (от входов до выхода схемы)c. среднее число входных переменных во входном конусе вершины в графесхемы;3. Группа №3:a. средняя полустепень захода вершин в графе схемы;b. средняя длина пути в графе схемы (по всем вершинам в графе схемы);c. спектр числа вершин во входном конусе вершины в графе схемы (длякаждого значения числа вершин во входном конусе вершины (отминимального до максимального значения) вычисляется доля вершин, длякоторых число вершин в их входном конусе равно указанному значению);4.

Группа №4:a. спектр полустепеней захода вершин (для каждого значения полустепенизахода вершины (от минимального до максимального значения)вычисляется доля вершин, степень которых равна указанному значению);b. максимальная длина пути в графе схемы (от входов до выхода схемы);c. средняя степень вершин во входном конусе вершины в графе схемы;5. Группа №5:a. минимальная степень вершин в графе схемы;b.

спектр длин путей в графе схемы (для каждого значения длины пути в схеме(от минимального до максимального значения) вычисляется доля путей(рассматриваются только пути от входов до выхода схемы), длина которыхравна указанному значению);c. средняя полустепень захода во входном конусе вершины в графе схемы;6. Группа №6:a. спектр полустепеней исхода вершин (для каждого значения полустепенизахода вершины (от минимального до максимального значения)вычисляется доля вершин, степень которых равна указанному значению);b.

минимальная и максимальная длина пути в графе схемы (от входов довыхода схемы);c. спектр числа входных переменных во входном конусе вершины в графесхемы (для каждого значения числа входных переменных во входномконусе вершины (от минимального до максимального значения)вычисляется доля вершин, для которых число входных переменных в ихвходном конусе равно указанному значению);Каждая группа может дополнительно реализовать расчет любого количества параметров,представленных в Приложении 1, а также предложить и реализовать расчет параметров,которые не представлены в указанном приложении.

Реализация расчета дополнительныхпараметров будет оцениваться отдельно.Приложение 1.средняя степень вершин в графе схемы;средняя полустепень захода вершин в графе схемы;средняя полустепень исхода вершин в графе схемы;минимальная степень вершин в графе схемы;максимальная степень вершин в графе схемы;спектр степеней вершин (для каждого значения степени вершины (отминимального до максимального значения) вычисляется доля вершин, степенькоторых равна указанному значению);7.

спектр полустепеней захода вершин (для каждого значения полустепени заходавершины (от минимального до максимального значения) вычисляется доля вершин,степень которых равна указанному значению);8. спектр полустепеней исхода вершин (для каждого значения полустепени заходавершины (от минимального до максимального значения) вычисляется доля вершин,степень которых равна указанному значению);9.

средняя длина пути в графе схемы (по всем вершинам в графе схемы);10. средняя длина пути в графе схемы (от входов до выхода схемы)11. минимальная длина пути в графе схемы (от входов до выхода схемы);12. максимальная длина пути в графе схемы (от входов до выхода схемы);13. спектр длин путей в графе схемы (для каждого значения длины пути в схеме отминимального до максимального значения вычисляется доля путей(рассматриваются все возможные пути в графе схемы), длина которых равнауказанному значению);14. спектр длин путей в графе схемы (для каждого значения длины пути в схеме (отминимального до максимального значения) вычисляется доля путей(рассматриваются только пути от входов до выхода схемы), длина которых равнауказанному значению);15.

среднее число вершин во входном конусе вершины в графе схемы;16. среднее число входных переменных во входном конусе вершины в графе схемы;17. средняя степень вершин во входном конусе вершины в графе схемы;18. средняя полустепень захода во входном конусе вершины в графе схемы;19. средяя полустепень исхода во входном конусе вершины в графе схемы;20. спектр числа вершин во входном конусе вершины в графе схемы (для каждогозначения числа вершин во входном конусе вершины (от минимального домаксимального значения) вычисляется доля вершин, для которых число вершин вих входном конусе равно указанному значению);21. спектр числа входных переменных во входном конусе вершины в графе схемы (длякаждого значения числа входных переменных во входном конусе вершины (отминимального до максимального значения) вычисляется доля вершин, для которыхчисло входных переменных в их входном конусе равно указанному значению);1.2.3.4.5.6..