Informatics (E-Journal) / Информатика
Not a member yet
963 research outputs found
Sort by
ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ОДНОСТАДИЙНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ
Get PDFПриведен обзор результатов, полученных в лаборатории математической кибернетики ОИПИ НАН наук Беларуси по решению задач теории расписаний для одностадийных детерминированных систем обслуживания
МОДЕЛИРОВАНИЕ НЕИСПРАВНОСТЕЙ СБИС НА ПОВЕДЕНЧЕСКОМ УРОВНЕ НА ЯЗЫКЕ VHDL
Get PDFРассматривается задача моделирования неисправностей блоков комбинационного типа СБИС, представленных на поведенческом уровне на языке VHDL. Предлагается формальный подход к решению задачи, в основе которого лежит построение тестов для разных реализаций операторов языка VHDL на базе применения системы генерации тестов и моделирования неисправностей. Особенность получаемых функциональных моделей неисправностей состоит в их полном соответствии физическим неисправностям
Логическая минимизация булевых сетей с использованием разложения Шеннона
Get PDFA synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions.Синтез логических схем, реализующих комбинационные блоки сверхбольших интегральных схем, – одна из важнейших задач компьютерного проектирования, так как размерность задач проектирования увеличивается, возрастает также время выполнения этапов синтеза логических схем. Особенно трудоемкой является глобальная технологическая независимая оптимизация – первый этап синтеза логической схемы. Суть второго этапа заключается в технологическом отображении оптимизированных логических представлений функций на логические элементы технологической библиотеки. Основные характеристики логической схемы, такие как площадь, быстродействие, энергопотребление, зависят от эффективности первого этапа. Эволюция методов глобальной логической оптимизации показала эффективность разложения Шеннона при оптимизации многоуровневых представлений систем полностью определенных булевых функций. Разработано множество методов и программ, использующих графические представления разложений Шеннона – BDD-представления. Большинство разработанных методов оптимизации BDD-представлений используют задания исходных систем булевых функций в виде дизъюнктивных нормальных форм (ДНФ).Предлагается алгоритм минимизации числа вершин булевой сети, являющейся многоуровневым представлением системы полностью определенных булевых функций. Минимизация осуществляется на основе разложения Шеннона и поиска вершин сети, реализующих одинаковые и взаимно инверсные функции. Предложенный алгоритм логической оптимизации реализован в виде программы. Эксперименты показали, что данный алгоритм и полученную программу целесообразно использовать в случае, когда исходное многоуровневое представление функций невозможно представить (за приемлемое время работы компьютерной программы) в виде системы ДНФ либо когда система ДНФ, полученная из многоуровневого представления, содержит большое число (десятки и сотни тысяч) элементарных конъюнкций
ПРИНЦИПЫ ПОСТРОЕНИЯ СУПЕРКОМПЬЮТЕРОВ СЕМЕЙСТВА «СКИФ» И ИХ РЕАЛИЗАЦИЯ
No full textРассматриваются базовые архитектурные решения, основные принципы и решения в части базового ПО и аппаратных средств, а также подходы к созданию моделей суперкомпьютеров «СКИФ». Приведен обзор технических характеристик образцов суперкомпьютеров семейства «СКИФ»
ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ НА ЦВЕТНЫХ ИЗОБРАЖЕНИЯХ ТОПОЛОГИЧЕСКОГО СЛОЯ ИНТЕГРАЛЬНОЙ СХЕМЫ
Get PDFПредлагается новый алгоритм идентификации объектов топологического слоя интегральной схемы как по цветовым признакам, так и по признакам формы объектов. Слой представляется как набор изображений, где каждое из них имеет разные условия фотографирования. Предложенный алгоритм идентификации основывается на сегментации цветного изображения и двухэтапном улучшении изображения с использованием математической морфологии и семантической фильтрации
МУЛЬТИПРОЦЕССОРНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВИНОГРАДА ДЛЯ ДПФ НА ОСНОВЕ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ АРИФМЕТИКИ
Get PDFРассматривается разработка на основе минимально избыточной модулярной арифметики мультипроцессорной модели алгоритма Винограда для дискретного преобразования Фурье (ДПФ), которая полностью реализуется в режиме модульных вычислений. Это достигается за счет применения больших модулей и таблиц большой емкости. Предлагаемая вычислительная технология обладает высокой производительностью и позволяет также существенно упростить немодульные процедуры
РЕШЕНИЕ БОЛЬШИХ СИСТЕМ БУЛЕВЫХ УРАВНЕНИЙ
Get PDFМногие проблемы анализа, синтеза и диагностики неисправностей логических схем, а также проблемы дедуктивного вывода, распознавания образов и защиты информации сводятся к решению комбинаторных задач с неизбежным перебором вариантов. Значительная часть таких задач формулируется на языке логических уравнений. В статье рассматриваются два класса систем, содержащих сотни булевых уравнений и переменных: большие системы логических уравнений с ограниченным числом переменных в каждом из них (БСЛУ) и системы линейных логических уравнений (СЛЛУ). Для решения таких систем в лаборатории логического проектирования ОИПИ НАН Беларуси разработана серия комбинаторных методов. Результаты испытаний этих методов на потоке псевдослучайных систем свидетельствуют об их высокой практической эффективности
ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ РЕШЕНИЯ ЛОГИКО-КОМБИНАТОРНЫХ ЗАДАЧ
Get PDFПредлагается описание средств для программирования трудоемких алгоритмов логико-комбинаторного характера, основанных на представлении информации булевыми векторами и матрицами. Такие средства определяются классами в языке программирования С++. Приводятся результаты экспериментов по сравнению времен исполнения популярных логических операций, реализованных в разработанных классах
НАХОЖДЕНИЕ ОТНОШЕНИЯ ПАРАЛЛЕЛЬНОСТИ НА МНОЖЕСТВЕ ЦЕПОЧЕК АЛГОРИТМА УПРАВЛЕНИЯ
Get PDFРассматривается проблема нахождения отношения параллельности на множестве меток корректного алгоритма логического управления. Исследуется случай, когда структура переходов между цепочками алгоритма описывается небезопасной a-сетью, а корректность алгоритма обеспечивается с помощью специальных операций изменения последовательности выполнения цепочек, не отображаемых в a-сети, – операций гашения
МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ
Get PDFИсследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания n требований одним прибором при условии, что известны нижние и верхние границы возможных значений длительностей операций по обслуживанию требований. Доказывается необходимое и достаточное условие, при выполнении которого требование Ju доминирует требование Jv (иными словами, для каждого множества возможных длительностей операций существует оптимальная перестановка n требований, в которой Ju предшествует Jv). Приводится критерий существования единственной перестановки n требований, которая является оптимальной при любых возможных длительностях операций. Доказывается необходимое и достаточное условие, при котором любая перестановка n требований является единственной оптимальной перестановкой при некотором множестве возможных длительностей операций. Полученные условия проверяются за полиномиальное от n время