Задача «Надёжность логических схем»

Преамбула: большинство задач в спортивном программировании оцениваются по однозначно правильному решению, по сути, сравнивая выдачу конкурсной программы с шаблоном правильного ответа. Однако существует пласт задач, где лучшее решение найти невозможно или крайне сложно в разумные временные рамки. Однако два решения легко можно сравнить между собой по некоторой метрике. Из-за этого усложняется проверяющая программа, однако, расширяется простор для разработки собственных эвристических алгоритмов решения. Представляю наш ваш суд одну такую задачу.

Комбинационные логические схемы входят в состав всех современных процессоров и других электронных средств обработки информации. Процессоры используются повсеместно и непрерывно усложняются. Количество транзисторов в современном процессоре уже превысило 2 млрд ? И, похоже, рост не планирует останавливаться. Одновременно с этим уменьшаются технологически процессы производства процессоров. Транзисторы становятся все меньше и уязвимее для внешних воздействий. И вот, даже не самые сильные внешние излучения и магнитные поля могут приводить к кратковременным изменениям логических значений в микроэлектронных схемах. Эта проблема особенно актуальна в космических и других критичных к надежности системах. В данной задаче поставим вопрос: как зная логическое назначение схемы сделать её более устойчивой к внешним воздействиям? Вашей задачей будет разработать алгоритм создания такой устойчивой схемы.

Пусть задана логическая схема, без обратных связей, состоящая из следующих 6 элементов:

Название Описание Операция Изображение INV инвертор OUT=!A AND логическое «И» OUT=A&B OR логическое «ИЛИ» OUT=A|B NAND инвертированный AND OUT=!(A&B) NOR инвертированный OR OUT=!(A|B) XOR исключающее «ИЛИ» OUT=A^B

На схему воздействует шум окружающей среды, с некоторой вероятностью изменяющий логическое значение вентилей на противоположное. Необходимо сконструировать схему, которая выполняет такую же логическую функцию, что и исходная, но при этом менее подвержена сбоям. По условиям задачи схема, которую вы сконструировали, должна не более чем в “K” раз превосходить исходную по площади.

Одним из параметров, которым характеризуют устойчивость логических схем к сбоям является COF — «Общая устойчивость схемы к ошибкам». COF рассчитывается как отношение числа корректных результатов работы схемы (все выходы схемы должны иметь правильное значение) к общему числу проведенных тестов. Соответственно для максимально надежных схем COF стремится к 1.

Каждый логический вентиль схемы характеризуется следующими параметрами: S – площадь вентиля, p – вероятность сбоя в процентах при текущих внешних условиях.

На первой строке указано число Z – количество тестов (Z < 400). Далее следует Z тестов.

На первой строке каждого теста указано число K (2.0 ≤ K ≤ 20.0) — максимальная избыточность схемы по площади.

На следующих 6 строках указаны по два числа площадь S (1 ≤ S ≤ 100) и вероятность сбоя q (0 ≤ q ≤ 20) в процентах, параметры каждого из логических элементов в следующем порядке: INV, AND, OR, NAND, NOR, XOR.

На следующей строке указано число “I” (0 < I < 250) – количество входов схемы, затем следует I строк не более 20 символов в каждом разделенных пробелами – имена входных узлов схемы.

На следующей строке указано число “O” (0 < O < 150) – количество выходов схемы, затем следует O строк не более 20 символов в каждом разделенных пробелами – имена выходных узлов схемы.

Далее указано число логических вентилей в схеме N (1 < N < 5000), после чего следуют N строк с описанием каждого вентиля.

Описание каждого вентиля начинается с его типа далее идут имена входных узлов, далее имя выходного узла

Для каждого теста необходимо вывести описание схемы в следующем формате. На первой строке число N (1 < N < 100000) – количество вентилей в результирующей схеме. Далее следует N – строк с описаниями вентилей. Описание каждого вентиля начинается с его типа далее идут имена входных узлов, далее имя выходного узла.

Количество полученных очков Score суммируется по всем тестам. Количество очков полученных за тест будет равно значению COF рассчитанному для вашей схемы. Расчет COF ведется по методу Монте-Карло ? в два этапа:

1) на первом этапе программа-судья определяет, что ваша схема работает идентично оригиналу. На вход обеим схемам подаются одинаковые тестовые последовательности (несколько тысяч раз) и сравниваются логические значения на выходах схемы. Если логические значения будут отличаться, то вы получите статус Wrong Answer.

2) на втором этапе программа-судья будет случайным образом по заданным вероятностям инвертировать значения на вентилях вашей схемы и сравнивать значения на вашей схеме и на схеме эталоне. Если хотя бы один из выходов будет отличаться, будет увеличиваться счетчик «неправильных ответов». Для расчета используется формула: COF = (TT — INC)/TT, где: TT — число тестов хотя бы с одной внедренной ошибкой INC — число тестов, где хотя бы на одном выходе схемы проявилась ошибка

Так же программа-судья проверяет, что избыточность схемы не превышает заданную.

1. Размер программы не более 50 Кбайт
2. Время на выполнение не более 50 секунд
3. Поддерживаются более 40 языков программирования (C/C++, Java, Pascal и.т.д.)

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

Пусть задана следующая логическая схема (см. рисунок). Требуемая избыточность не должна быть более 4.1 раз. Схема построена на библиотеке, у которой:

INV имеет площадь 50 и вероятность сбоя 3%

AND имеет площадь 60 и вероятность сбоя 3.1%

OR имеет площадь 60 и вероятность сбоя 3.2%

NAND имеет площадь 70 и вероятность сбоя 3.3%

NOR имеет площадь 70 и вероятность сбоя 3.4%

XOR имеет площадь 70 и вероятность сбоя 3.5%

Входной файл для этого задания будет иметь следующий вид:

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

Пусть наш алгоритм использует стандартный прием троирования и выбора логического значения, которое используется на большем количестве выходов (Triple Modular Redundancy (TMR)) ? . В этом случае выходной файл может быть записан следующим образом:

Рисунок для выходного файла

Начисление очков:

За это решение после моделирования будет начислено 0.682661 очков.

Для того что бы не писать программы с нуля можно использовать готовые наработки: 1) Простое решение задачи на C\C++ — программа зачитывает данные и выводит схему как есть, без изменений. 2) Судья на C\C++ — программа, которая используется на сервере для оценки решения задачи. Можно использовать локально для тестирования эффективности своих решений 3) Тестовый набор данных — набор из 102-ух тестовых схем, схожих с закрытым набором на сервере.