Персоналии

• Просмотров: 719 | Комментариев : 0

• Просмотров: 156 | Комментариев : 0

Методы анализа выполнимости булевых формул являются одним из эффективных подходов к решению задачи булевого сопоставления и проверки эквивалентности цифровых схем. В комбинации с классическими трассировочными алгоритмами и оптимизационными техниками данные методы показывают результаты, превосходящие классические алгоритмы трассировки по скорости работы и качеству получаемого результата. В работе выполнен анализ современной практики применения методов на основе задачи выполнимости булевых формул в системах автоматизации проектирования сверхбольших интегральных схем. Рассмотрены примеры подходов на основе задачи выполнимости булевых формул к задачам трассировки и формальной проверки эквивалентности описаний цифровых схем в рамках технологического отображения в составе маршрута проектирования ПЛИС. Разработан и представлен алгоритм детальной трассировки блоков коммутации ПЛИС с применением задачи выполнимости. Результаты его работы продемонстрированы на примере программируемого логического блока интегральной микросхемы российского производства 5400ТР094. Блок имеет островную архитектуру, т.е. малые программируемые логические блоки и блоки коммутации образуют регулярно повторяющуюся схемотехническую структуру. Свойства выбранной классической архитектуры позволяют расширить область применения предложенного алгоритма на весь класс ПЛИС островного типа. Тестирование алгоритма проведено на наборах проектных схем ISCAS-85, ISCAS-89 и LGSynth-89. Выполнено сравнение разработанного алгоритма на основе методов анализа выполнимости булевых формул с известным алгоритмом трассировки Pathfinder по критериям затраченного времени и достигнутой степени разводимости блоков коммутации. Установлено, что методы анализа выполнимости булевых формул для задачи трассировки способны к доказательству неразводимости рассматриваемой трассировочной задачи в отличие от алгоритма Pathfinder, результаты работы которого могут лишь косвенно свидетельствовать об этом. Показано, что применение более производительного решателя для задачи выполнимости существенно ускоряет работу предложенного алгоритма детальной трассировки.

• Просмотров: 736 | Комментариев : 0

Параллельные архитектуры вычислительных систем, в том числе с массивным параллелизмом, в настоящее время интересуют исследователей в области теоретической информатики. Основной задачей при этом становится аппаратное или алгоритмическое ускорение межпроцессорного обмена. Одним из подходов к построению алгоритмов может быть использование нетрадиционного формализма - нейронных сетей или клеточных автоматов (КА), реализующих модель ближнего взаимодействия элементарных вычислителей. В работе рассмотрены три операции с матричными данными: унарная (поэлементная), отражение, транспонирование. Операции реализованы параллельными алгоритмами в формализме КА в предположении, что данные введены в КА до начала расчета. Показано, что все представленные алгоритмы имеют линейную по размеру матрицы сложность. Движение и преобразование данных осуществлено с помощью введения в состояние ячейки битовых и/или тритовых, т.е. с тремя состояниями, флагов-компонент. Условия останова расчета - наступление stop-состояния флага выделенной ячейки КА или всех ячеек поля КА, т.е. их «заморозка». Освоение техники клеточно-автоматной алгоритмики на примере элементарных операций над матрицами может служить базой для решения более сложных задач (например, вычисление детерминанта матрицы), возникающих в рамках численного моделирования процессов, операций и устройств микроэлектроники.

• Просмотров: 1970 | Комментариев : 0

Одно из главных преимуществ проектирования пользовательских схем на ПЛИС - высокая скорость разработки, поэтому создание эффективных средств автоматизированного проектирования для современных микросхем этого класса имеет важное значение. Наиболее времязатратными этапами маршрута проектирования на ПЛИС являются размещение и трассировка. От качества результатов этих этапов зависят итоговые характеристики пользовательских цифровых схем, реализованных на ПЛИС. В работе рассмотрен подход к ускорению этапа трассировки в рамках маршрута топологического проектирования на ПЛИС за счет улучшения алгоритма трассировки. Исследован базовый алгоритм трассировки, представляющий собой модифицированный Pathfinder для смешанного графа трассировочных ресурсов. Этот алгоритм построен на основе согласования маршрутов цепей проектной схемы и работает по принципу итерационного устранения перегрузок трассировочных ресурсов базового кристалла ПЛИС. Для проведения экспериментальных запусков использованы наборы тестовых цифровых схем ISCAS’85, ISCAS’89, LGSynth’89 и несколько пользовательских промышленных проектов. Работа улучшенного алгоритма трассировки проанализирована на примере четырех архитектур ПЛИС. Вследствие усовершенствования алгоритма среднее уменьшение времени трассировки составило от 1,3 до 2,6 раза в зависимости от архитектуры ПЛИС без значительного отрицательного влияния на временные характеристики проектируемых схем.

• Просмотров: 536 | Комментариев : 0

Архитектурно-ориентированная модель расширенного смешанного коммутационного графа позволяет описать особенности трассировочных ресурсов современных программируемых логических интегральных схем (ПЛИС). Такая модель может применяться для решения задачи трассировки проектных межсоединений в составе маршрута топологического проектирования на основе ПЛИС. В работе рассмотрена архитектурно-ориентированная модель расширенного смешанного коммутационного графа. Предложены две модификации базового метода автоматической трассировки - классического алгоритма Pathfinder, адаптированного к смешанному графу коммутационных ресурсов. Первая модификация построена на применении идеи направленного поиска на графовой модели с использованием данных о пространственно-геометрических характеристиках базового кристалла, вторая - сочетает стратегию направленного поиска с учетом предварительной оценки перегруженности коммутационных ресурсов ПЛИС по результатам процедуры размещения. Показано, что предложенные модификации позволяют ускорить сходимость базового метода к трассировочному решению в среднем на 50,6 и 38,6 % соответственно. При сохранении полной трассируемости тестовых наборов IWLS’2005, ISCAS’89 и LGSynth’89 применение только направленного поиска привело к улучшению временных характеристик имплементаций проектных схем на 5,2 % в среднем, а использование его совместно с оценкой перегруженности перед началом трассировки позволило улучшить их на 9,3 % в среднем относительно результатов базового метода Pathfinder.

• Просмотров: 280 | Комментариев : 0

Приведены отсутствующие в литературе последних десятилетий клеточно-автоматные формулировки алгоритмов сортировки массивов символов и строк. Впервые предложен клеточный автомат, умножающий два целых числа, записанных в системе счисления с произвольным основанием. Алгоритм основан на схеме параллельного умножения Атрубина для систолического массива процессоров и требует четыре компонента (регистра) вместо пяти.

• Просмотров: 1828 | Комментариев : 0