Методика автоматизированного анализа производительности подсистем коммутации проектируемых СнК на основе графовых моделей целевых приложений тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Жезлов Кирилл Александрович
- Специальность ВАК РФ00.00.00
- Количество страниц 168
Оглавление диссертации кандидат наук Жезлов Кирилл Александрович
Введение
Глава 1. Анализ проблем функциональной верификации СнК
1.1 Функциональная верификация в маршруте проектирования СнК
1.1.1 Основные виды СФ-блоков
1.1.2 Основные методики верификаций СФ-блоков
1.1.3 Пространство параметров верификации
1.1.4 Платформенный подход
1.1.5 Абстракция как необходимый элемент платформенного подхода
1.2 Подходы к функциональной верификации
1.2.1 Основные способы проверки модели устройства
1.2.2 Основные виды тестов
1.2.3 Проблемы функциональной верификации
1.3 Организация подсистем коммутации в составе СнК
1.4 Подходы к оценке производительности коммутационных сред
1.4.1 Модели трафика
1.4.2 Модели коммутационных сред и метрики производительности
1.4.3 Проблемы оценки производительности
1.5 Выводы
Глава 2. Методика оценки эффективности коммутаторов
2.1 Трансляция требований и ограничений
2.1.1 Требования и ограничения со стороны системы
2.1.2 Требования и ограничения со стороны задачи
2.2 Графо-ориентированный подход к формированию тестовых воздействий
2.2.1 Графовая модель трафика в коммутационных средах
2.2.2 Расчёт характеристик задач по графовой модели трафика
2.2.3 Точность графовой модели трафика
2.3 Комплекс метрик производительности
2.3.1 Расчёт метрик для одной транзакции
2.3.2 Способы усреднения значений метрик
2.4 Критерии оценки производительности
2.5 Выводы
Глава 3. Разработка алгоритмов и архитектуры программного комплекса
3. 1 Базовая верификационная инфраструктура
3.1.1 Шаблонные тестовые окружения
3.1.2 Модульное средство сборки
3.2 Инструмент для автоматизированного формирования тестовых воздействий
3.2.1 Алгоритм генерации графов транзакций
3.2.2 Алгоритм воспроизведения графов транзакций
3.3 Инструмент для автоматизированного вычисления метрик производительности
3.4 Инструмент для автоматизированного запуска и анализа результатов тестов производительности
3.5 Архитектура верификационной инфраструктуры
3.6 Выводы
Глава 4. Практические результаты
4.1 Воспроизведение тестовых сценариев
4.2 Применение методики в проектах
ОКР «Обработка-11»
ОКР «Интерфейс-7»
4.2.1 Результаты применения методики
4.3 Результаты внедрения методики
4.4 Рекомендации по тестированию подсистем коммутации
4.4.1 Базовые тесты производительности
4.4.2 Сценарии использования
4.5 Выводы
Заключение
Список литературы
Приложение 1. Акты внедрения
Приложение 2. Свидетельство о регистрации программы для ЭВМ «Универсальный генератор потоков для подсистем коммутации»
Приложение 3. Пример работы генератора графов
Приложение 4. Описание проектов АО НПЦ «ЭЛВИС», в которых была применена предложенная методика
ОКР «Обработка-11»
ОКР «Интерфейс-7»
ОКР «Процессор-И1»
ОКР «Базис-Б3» («RoboDeus»)
ОКР «Сложность-И3» («Скиф»)
«^Сот-05»
ОКР «Базис-Б5»
Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Разработка методики и алгоритмов верификации гетерогенных многоядерных систем на основе графовой модели иерархии когерентной кэш-памяти2021 год, кандидат наук Гаращенко Антон Витальевич
Встречное тестирование высокопроизводительных микропроцессоров2013 год, кандидат наук Чибисов, Петр Александрович
Разработка моделей и алгоритмов функциональной верификации при проектировании программируемых логических интегральных схем2010 год, кандидат технических наук Дьячков, Юрий Владимирович
Методы и модели оценивания производительности структурообразующих звеньев корпоративных сетей2003 год, доктор технических наук Сергеев, Владимир Григорьевич
Обнаружение аномалий и нейтрализация угроз в распределенных автоматизированных системах управления на основе мониторинга сетевых информационных потоков2024 год, кандидат наук Абрамова Таисия Вячеславовна
Введение диссертации (часть автореферата) на тему «Методика автоматизированного анализа производительности подсистем коммутации проектируемых СнК на основе графовых моделей целевых приложений»
Введение
Актуальность работы. Микроэлектронная промышленность как часть отрасли информационных технологий (IT — от англ. Information technology) сегодня является одним из основных драйверов развития экономики и в России, и во всем мире. Каждая микросхема проходит путь от проектирования до производства и поставки конечному пользователю. И проектирование, и производство являются очень дорогостоящими и ресурсозатратными процессами, как с точки зрения времени, так и с точки зрения интеллектуального труда. Модернизация отечественной экономики через развитие микроэлектронной промышленности невозможна без наличия собственных дизайн-центров, способных проектировать интегральные схемы высокой сложности, по современным технологическим нормам и отвечающие постоянно растущим требованиям к производительности и энергопотреблению. Сокращение трудозатрат на проектирование позволит ускорить разработку и выпуск микросхем для жизненно важных отраслей: космической, оборонной, телекоммуникационной.
Каждый из этапов проектирования микросхемы, начиная от планирования архитектуры и заканчивая проектированием топологии кристалла, связан с верификацией полученных результатов. «Функциональная верификация является критическим этапом маршрута разработки системы на кристалле. Постоянный рост сложности разрабатываемых систем на кристалле (СнК) привел к ситуации, когда на их верификацию затрачивается значительно больше времени, чем собственно на разработку. Для современных систем верификация в обязательном порядке дополняется процессами оценки реализуемости целевых задач на проектируемой системе и подтверждения её эффективности для всех целевых режимов работы. Это делает задачу верификации одной из наиболее сложных и ответственных в маршруте проектирования» [1].
Современные гетерогенные системы на кристалле состоят из большого количества разнородных СФ-блоков. В их число входят процессорные ядра, сопроцессоры, аппаратные ускорители, периферийные блоки, различные виды памяти, коммутаторы или подсистемы коммутации. В современных высокопроизводительных СнК подсистема коммутации является критическим элементом, зачастую определяющим производительность всей системы.
Существенный вклад в разработку теории и практики автоматизации процессов проектирования и верификации СнК внесли российские учёные: Г.Г. Казённов, В.Г. Немудров, А.С. Камкин, А.Н. Мешков, и другие. В развитии подходов к анализу производительности подсистем коммутации в составе СнК участвовали зарубежные учёные: Mehta A.B., Orgas U.Y., Srinivasan K., Dally W.J. Разработку высокопроизводительных СнК и коммутаторов различных архитектур в их составе проводят отечественные предприятия: АО «МЦСТ», ПАО «ИНЭУМ им. И.С.Брука», НТЦ «Модуль», «Байкал Электроникс», ФНЦ НИИСИ РАН, АО «НИИМА «Прогресс», АО НПЦ «ЭЛВИС», АО «ПКК Миландр».
Наибольшую трудоёмкость в верификации высокоуровневых моделей систем и отдельных СФ-блоков составляет процесс создания тестовой инфраструктуры и тестов. Анализ маршрута проектирования СнК показывает, что существенная доля усилий проектировщиков тратится на создание или повторную отладку верификационного кода или скриптов, частично повторяющих функциональность кода, уже созданного на других этапах разработки СнК или в рамках работы над другими СнК. Вместо этой работы намного эффективней использовать время для решения задач улучшения качества верификации, а не для регулярной адаптации под новые условия того, что уже было создано.
Традиционный подход к верификации СнК (и подсистемы коммутации в ее составе), заключается в запуске на RTL-модели СнК целевых прикладных программ (приложений) и проверке как правильности, так и скорости их выполнения. Однако такой подход сопряжен с очень значительными временными затратами по следующим причинам:
• для выполнения сложных программ могут требоваться десятки миллионов тактов, и потактовое моделирование (симуляция) исполнения таких программ на RTL-модели, содержащей миллионы логических элементов, может растягиваться на длительное время, измеряемое иногда сутками и даже неделями;
• во время проектирования СнК целевое программное обеспечение (ПО) также, как правило, находится в состоянии разработки и/или адаптации к архитектуре проектируемой СнК, и процесс создания ПО нередко отстает от разработки RTL-модели;
• процесс поиска и устранения ошибок при таком подходе подразумевает одновременную отладку и ПО, и RTL-модели в рамках итеративного цикла: «моделирование — поиск и устранение ошибок в ПО или RTL-модели — моделирование», что многократно увеличивает время отладки.
Для повышения качества проверки подсистем коммутации в составе СнК, необходимо начинать их проверку как можно раньше. Также как можно раньше следует начинать и анализ их производительности, в частности, проверку на соответствие требованиям со стороны целевых приложений. Однако, здесь возникает проблема высокой сложности автономной проверки подсистем коммутации с имитацией работы целевых задач.
В данной работе предлагается и исследуется новый подход, при котором для анализа производительности RTL-модели подсистемы коммутации не требуется
« « ТЛ
моделирование вычислительной части целевых приложений. В предлагаемом подходе моделируется лишь коммуникационная часть приложения, при этом вычислительная часть приложения описывается в виде параметров задержек соответствующих коммуникационных задач.
Такой подход, очевидно, имеет свои ограничения. Он, в частности, неприменим для сложных программ, в которых характер коммуникационных задач зависит от содержания вычислительной части приложения. При этом он хорошо соответствует широкому кругу приложений, связанных с потоковой обработкой данных. В подобном стиле работают такие широко применяемые в составе СнК устройства, как процессоры обработки сигналов, графические процессоры, различные ускорители, контроллеры DMA и т.д.
Кроме того, для повышения качества и снижения трудозатрат на верификацию подсистем коммутации в составе СнК необходим инструментарий, позволяющий не только количественно оценивать производительности, но и выявлять существующие или потенциальные проблемы. В применяемых маршрутах верификации СнК наблюдается недостаток инструментов для выявления узких мест в производительности RTL реализации подсистемы коммутации с учётом сценариев применения.
В связи с этим, при разработке новых СнК, в частности высокопроизводительных процессоров, актуальной является задача разработки методики автоматизированного анализа производительности RTL-моделей подсистем коммутации в составе СнК,
позволяющих учитывать структуру СнК и сценарии её применения.
Таким образом, данная работа посвящена исследованию и разработке моделей, алгоритмов и методов для анализа проектных решений.
Объектом исследования в данной работе является подсистема коммутации в составе СнК — программируемая система, реализующая передачу данных между своими портами или выводами. Предмет исследования — методы и средства анализа производительности RTL-моделей подсистем коммутации.
Исходя из анализа существующих проблем, связанных с автоматизированным анализом производительности коммутационных сред в составе СнК, были сформулированы следующие цели и задачи диссертационной работы.
Целью диссертационной работы является исследование и разработка методики анализа производительности RTL-моделей подсистем коммутации в составе СнК, позволяющих учитывать структуру СнК и сценарии её применения без моделирования вычислительной части приложений.
Для достижения этой цели необходимо решить следующие задачи:
1. Исследовать возможности создания методики автоматизированного анализа производительности подсистемы коммутации проектируемых СнК, не требующей выполнения вычислительной части приложений
2. На основе проведённых исследований разработать способ формирования графовых моделей трафика целевых приложений через подсистемы коммутации проектируемых СнК без моделирования вычислительной части приложений.
3. Разработать методику автоматизированного анализа производительности RTL-моделей подсистем коммутации, включающую в себя формирование и воспроизведение входных воздействий на основе графовых моделей трафика целевых приложений, расчёт метрик производительности и оценку результатов тестов, и позволяющую выявлять проблемы производительности при различных сценариях использования устройства.
4. Разработать программный комплекс, реализующий методику автоматизированного анализа производительности RTL-моделей подсистем коммутации, включающий в себя модули, реализующие автоматизированное формирование тестовых воздействий на основе высокоуровневого описания графа потоков данных, автоматизированное вычисление и анализ метрик производительности и формирование отчета.
Методы исследования. Для решения поставленных задач использовались теория графов, теория алгоритмов, теория программирования, теория и методы проектирования интегральных схем.
Научная новизна. При выполнении диссертационной работы были получены следующие новые научные результаты.
При выполнении диссертационной работы были получены следующие новые научные результаты.
1. Разработан метод формирования моделей трафика целевых приложений в подсистемах коммутации в виде направленных ациклических графов, позволяющий, в отличие от известных подходов, моделировать коммуникационные задачи без моделирования вычислительной части приложений и не привязанный к трассе исполнения программы.
2. Предложен аналитический способ вычисления ожидаемых характеристик функционирования подсистемы коммутации СнК при заданном графе транзакций.
3. Разработан алгоритм воспроизведения графа транзакций для предложенной графовой модели трафика, позволяющий выдерживать заданную скорость передачи данных и компенсировать временные снижения скорости передачи данных в рамках отдельных потоков данных.
4. Предложен набор метрик и критериев для автоматизированного анализа производительности подсистем коммутации СнК.
5. На основе предложенных моделей, алгоритмов, метрик и критериев разработана методика автоматизированного анализа производительности RTL-моделей подсистем коммутации, позволяющая локализовать причины проблемы производительности при различных сценариях использования устройства.
Практическая значимость работы состоит в следующих достижениях.
1. На основе предложенной методики разработан программный комплекс автоматизированного анализа производительности подсистем коммутации.
2. Применение предложенной методики позволяет проводить оценку производительности RTL-модели подсистемы коммутации на основе сценариев использования без моделирования вычислительной части приложений, обеспечивает возможность локализации причин проблем производительности и снижение числа ошибок, обнаруживаемых на следующих этапах проектирования.
3. Применение предложенной методики обеспечивает возможность повторного использование кода тестов и тестовых сценариев и позволяет снизить трудозатраты на написание тестов производительности, в зависимости от сложности проекта, в 3-10 раз.
4. Предложенный способ вычисления ожидаемых характеристик функционирования подсистемы коммутации СнК при заданном графе транзакций позволяет вычислять указанные характеристики с погрешностью не превышающей 1% для большинства реальных прикладных задач.
Достоверность результатов работы обусловлена применением общепринятых методов математического моделирования, использованием современных систем автоматизированного проектирования, и подтверждается рядом выпущенных систем на кристалле, с подсистемами коммутации различной архитектуры, разработанных на основе теоретических и технических концепций, изложенных в данной работе.
Внедрение результатов работы.
Полученные научные результаты были применены при проектировании, верификации и анализе производительности подсистем коммутации в ряде проектов АО НПЦ «ЭЛВИС». На текущий момент с использованием предложенной методики выпущены микросхемы 1892ВМ15Ф, 1892ВМ206, 1892ВМ218, 1892ВМ248, 1892ВА018, 1892ВМ288 и 1892ВА028.
Основные научно-технические результаты работы, основанные на исследованиях автора, использованы при выполнении семи ОКР и НИР, проводившихся на предприятии АО НПЦ «ЭЛВИС» в течение ряда лет (см. глава 4 «Практические результаты»)
Личный вклад автора. Все выносимые на защиту научные положения, полученные в рамках диссертационной работы теоретические и экспериментальные исследования, разработка и внедрение выполнены автором лично.
На защиту выносятся:
1. Метод формирования моделей трафика в подсистемах коммутации СнК в виде направленных ациклических графов, вершинами которых являются потоки данных, а дугами — зависимости между ними, позволяющий моделировать коммуникационные задачи без моделирования вычислительной части приложений и не привязанный к трассе исполнения программы.
2. Аналитический способ вычисления ожидаемых характеристик функционирования подсистемы коммутации СнК при заданном графе транзакций, позволяющий вычислять ожидаемые характеристики функционирования подсистемы коммутации.
3. Алгоритм воспроизведения графа транзакций, позволяющий выдерживать заданную скорость передачи данных и компенсировать временные снижения скорости передачи данных в рамках отдельных потоков данных.
4. Набор метрик и критериев для автоматизированного анализа производительности подсистем коммутации СнК.
5. Методика автоматизированного анализа производительности подсистем коммутации, позволяющая локализовать проблемы производительности при различных сценариях использования СнК.
6. Архитектура программного комплекса автоматизированного анализа производительности RTL-моделей подсистем коммутации СнК.
Апробация работы. Основные результаты работы докладывались и обсуждались
на следующих конференциях:
• Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем 2015», г. Москва. 2015;
• Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем 2016», г. Москва. 2016;
• CDNLive EMEA 2018, Германия, г. Мюнхен. 2018;
• IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, г.Москва. 2019;
• 26-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика - 2019», г. Москва. 2019;
• Всероссийская научно-техническая конференция «Проблемы разработки
перспективных микро- и наноэлектронных систем 2020», г. Москва. 2020; • 19-я Отраслевая научно-техническая конференция радиоэлектронной промышленности «Микроэлектроника - 2020», г. Ялта. 2020.
По теме диссертации опубликовано 12 научных работ. Из них в ведущих рецензируемых журналах, входящих в перечень, утверждённый ВАК — 4, входящих в перечень Scopus — 1, тезисов докладов всероссийских и международных конференций — 7, 1 авторское свидетельство о регистрации программы для ЭВМ. Без соавторов опубликована 1 работа.
Структура и объём диссертации. Диссертационная работа состоит из введения, четырёх глав, заключения, списка использованной литературы и приложений. Объём основного текста диссертации — 120 страниц. В работе содержится 41 рисунок и 15 таблиц. Список литературы содержит 81 наименование.
Во введении обосновывается актуальность темы исследования, формулируются цели и задачи работы, перечисляются элементы научной новизны и практической значимости, даётся краткое содержание глав работы.
В первой главе проведён обзор современных подходов к верификации систем на кристалле, в частности подсистем коммутации. Рассмотрены способы формирования входных воздействий для тестируемых моделей и проанализированы их особенности с точки зрения применения к описанию моделей трафика в коммутационных средах. Также проведён обзор современных подходов к анализу производительности коммутаторов. Был выявлен ряд проблем и недостатков в существующем комплексе средств верификации коммутаторов, и на основании этого сформулированы требования к методике автоматизированного анализа производительности коммутационных сред в составе СнК.
Во второй главе рассмотрены основные составляющие предложенной методики автоматизированного анализа производительности коммутационных сред. На основе анализа требований к методике предложена и теоретически обоснована графовая модель трафика, подход к описанию трафика тестовых сценариев в виде направленного ациклического графа транзакций и способ предварительной оценки результатов исполнения сценария. Также изложен комплекс метрик производительности и критериев их анализа, направленный на выявление причин проблем с производительностью.
В третьей главе рассмотрены вопросы практической реализации программного комплекса, решающего задачу автоматизации методики анализа производительности коммутаторов. Изложены алгоритмы, используемые для генерации входных воздействий на основе высокоуровневого описания тестового сценария, исполнения сценария, вычисление метрик и критериев производительности, формирования отчёта. Описана реализация основных модулей, входящих в состав программного комплекса, и их взаимодействия между собой и с другими инструментами.
Четвертая глава посвящена практическим аспектам использования предложенной методики. Приведены подтверждения корректности работы программного комплекса. Приведена информация о структуре СнК и подсистем коммутации в их составе, при проектировании и верификации которых была использована предложенная методика. Изложены оценки трудозатрат на создание верификационной инфраструктуры и тестов с использованием предложенной методики и без. Также приведены рекомендации по использованию методики для описания базовых сценариев тестов производительности.
В заключении сформулированы основные результаты работы.
Приложения содержат акты о внедрении проведенных в диссертации исследований (Приложение 1), свидетельство о регистрации программы для ЭВМ «Универсальный генератор потоков для подсистем коммутации» (Приложение 2), пример работы генератора графов (Приложение 3) и описание проектов АО НПЦ «ЭЛВИС», в которых была применена предложенная методика (Приложение 4)
Глава 1. Анализ проблем функциональной верификации СнК
1.1 Функциональная верификация в маршруте проектирования СнК
«Верификацией называется проверка соответствия результатов, полученных на отдельных этапах проектирования (разработки) программных и аппаратных систем, требованиям и ограничениям, установленным для них на предыдущих этапах (на начальном этапе проверяется соответствие исходным требованиям — техническому заданию)» [2].
«Функциональная верификация является критическим этапом маршрута разработки системы на кристалле (далее СнК). Для современных систем она в обязательном порядке дополняется процессами оценки реализуемости целевых задач на проектируемой системе и подтверждения её эффективности для всех целевых режимов работы (в ряде источников данный процесс называют валидацией [3]). Это делает этап верификации одним из наиболее сложных и ответственных в маршруте проектирования» [1].
Могут быть выделены следующие несколько типов верификации.
1. Функциональная верификация (functional verification) — её задача состоит в проверке соответствия результатов моделирования целевой функции, реализуемой проектируемой системой.
2. Формальная верификация (formal verification) — проверка эквивалентности представлений проектируемой системы на разных этапах маршрута проектирования или проверка истинности утверждений.
3. Статический анализ кода (static code analysis) — проверка исходного кода исследуемой программы или описания модели устройства на одном из языков описания аппаратуры на соблюдение правил использования языка и его конструкций. Производится без реального выполнения исследуемой программы.
4. Физическая верификация — проверка модели топологии проектируемой системы на соблюдение технологических норм и правил проектирования (DRC — Design Rule Check), и соответствия модели топологии логической и электрической схемам (LVS — Layout Versus Schematic) [4].
5. Прототипирование — использование ПЛИС для функциональной проверки
проектируемой системы.
В соответствие с работой Г.Г. Казённова [4] могут быть выделены различные уровни представления проектируемой системы:
1. Системный.
2. Микросхемный.
3. Регистровый.
4. Логический.
5. Схемотехнический.
6. Топологический.
7. Компонентный.
На каждом из перечисленных этапов могут быть выявлены ошибки, обусловленные степенью детализации используемого представления и свойствами проектируемой системы, описываемыми на данном этапе.
Маршрут верификации напрямую зависит от состава сложно-функциональных блоков (далее СФ-блоки), входящих в СнК. Далее рассмотрим основные виды СФ-блоков и подходы к их верификации. Материалы разделов 1.1.1 и 1.1.2 изложены в работе [1] автора.
1.1.1 Основные виды СФ-блоков
«Процессорные ядра. Штатный способ их верификации — запуск последовательности команд (управляющей программы, чаще всего генерируемой [5]) непосредственно на модели устройства. Внешнее управление устройством осуществляется через команды отладочного интерфейса (посредством JTAG). Разработка программного драйвера, исполняемого на другом CPU, не требуется. Процессоры — инициаторы запросов, поэтому в окружении требуется модель ведомого устройства, отрабатывающего запросы от процессора. Минимальная функциональность такой модели, должна включать в себя память, в которую загружается программа и данные. При верификации процессорных ядер используются эталонные модели различной точности, позволяющие исполнять ту же программу, что и на верифицируемой модели. Для упрощения процесса отладки программ, создаваемых на высокоуровневых языках, в окружении требуются средства тестовой печати (реализация функции printf или её аналогов), и средства обеспечения быстрых операций с памятью для ускорения времени моделирования. Важным моментом для ускорения отладки ПО
является возможность использования штатных средств отладки и профилирования ПО (типа gdb) при работе с тестовым окружением процессорного ядра.
Сопроцессоры, автономные сопроцессоры, в том числе DMA (англ. Direct Memory Access — прямой доступ к памяти). Требования к тестовым окружениям устройств данного класса схожи с процессорными окружениями, однако их особенностью является необходимость регистрового управления и разработки программного драйвера устройства.
Аппаратные ускорители алгоритмов. Основное отличие от сопроцессоров, заключается в том, что как эталонная программа, так и тестовый сценарий представляют собой реализации одного и того же комплексного алгоритма, выполненные, как правило, на высокоуровневых языках программирования. В зависимости от модели управления устройством сложность программного драйвера может варьироваться.
Периферийные СФ-блоки. Основная особенность окружений — наличие компонента, имитирующего периферийное устройство (VIP). Программный драйвер для таких блоков может быть достаточно сложным, кроме того имеется необходимость синхронизации настроек и действий тестового сценария и активности внешнего VIP. Чаще всего периферийные блоки, наравне с процессорами, являются инициаторами запросов на системную шину.
Коммутаторы, подсистема памяти. На верхнем уровне абстракции данные устройства являются просто трактом передачи данных. Драйвер, если он и требуется, является достаточно простым, а все основные тестовые воздействия задаются трафиком транзакций, для которого требуются специальные генераторы в составе тестового окружения.
Специализированные блоки, не имеющие регистрового управления через стандартные интерфейсы. Примерами таких блоков служат подблоки вычислительного ядра, такие как АЛУ или программный декодер. Основная особенность — отсутствие программного драйвера устройства в явном виде и использование нестандартных интерфейсов для управления и обмена данными. Использование какого-либо общего шаблона для таких блоков затруднено.
Подсистема, система. В роли системы может выступать не только модель СнК, но и какая-либо ее часть, в которой в общем случае возможно наличие всех перечисленных выше устройств. Поэтому требования к окружению системы объединяют в себе
требования к окружению процессора и периферийной логики. Акценты верификации на данном уровне делаются на проверку интеграции блоков и эффективности их взаимодействия. Окружение системы, как правило, содержит в себе и окружения подблоков, которые могут работать в пассивном режиме монитора, фоновой проверки или в частично активном режиме (например, включенный имитатор периферийного устройства).» [1]
1.1.2 Основные методики верификаций СФ-блоков
«При описании основных особенностей верификации разных классов устройств, кроме требований к составу окружения приводились такие параметры как сложность программного драйвера и источник тестовых воздействий. Далее эти моменты будут рассмотрены уже с точки зрения основных способов создания тестовых сценариев.
Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Модели и методы тестирования программных систем на основе алгебраического подхода2013 год, кандидат наук Вигура, Антон Николаевич
Разработка и исследование модели алгоритма динамической маршрутизации для сетей GMPLS2008 год, кандидат технических наук Нижарадзе, Тимур Зурабович
Метод многокритериальной интеграции модели системы управления трафиком телекоммуникационной сети2013 год, кандидат наук Рудь, Дмитрий Евгеньевич
Автоматизированное проектирование корпоративных сетей на основе нечетких гиперграфов2006 год, кандидат технических наук Макеев, Антон Сергеевич
Модели и алгоритмы структурного тестирования взаимодействия классов в объектно-ориентированном программном обеспечении2013 год, кандидат наук Киселев, Алексей Викторович
Список литературы диссертационного исследования кандидат наук Жезлов Кирилл Александрович, 2023 год
Источник (у5)
Приемник (у<) <1 <1 <1 <1 <1 <1 <1 <1 <1 <1 <1
Операция (о) г г г г w w г w w w г
Объем данных, МБ (^) 2 5 3 10 7 8 1 12 4 5 10
Скорость, МБ/с (я) 20 40 20 40 20 40 20 20 40 40 20
Пауза, с (р) 0 0 0 0 0 0 0 0 0 0 0
v11
Рисунок 12. Пример графа потоков данных
Данный граф может быть представлен в виде матрицы инцидентности (таблица 2). Таблица 2. Матрица инцидентности выбранного графа коммуникационных задач
el e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14
vi 1 1 1 0 0 0 0 0 0 0 0 0 0 0
v2 -1 0 0 1 0 0 0 0 0 0 0 0 0 0
v3 0 -1 0 0 1 0 0 0 0 0 0 0 0 0
v4 0 0 -1 0 0 1 1 0 0 0 0 0 0 0
v5 0 0 0 -1 0 0 0 0 0 1 0 0 0 0
v6 0 0 0 0 -1 0 0 1 0 0 0 0 0 0
v7 0 0 0 0 0 -1 0 0 1 0 0 0 0 0
v8 0 0 0 0 0 0 -1 0 0 0 1 0 0 0
v9 0 0 0 0 0 0 0 -1 -1 0 0 1 1 0
v10 0 0 0 0 0 0 0 0 0 -1 0 -1 0 1
vil 0 0 0 0 0 0 0 0 0 0 -1 0 -1 -1
Граф коммуникационных задач (потоков данных) является моделью достаточно высокого уровня и, соответственно, довольно абстрактным описанием тестового
сценария. Для уточнения этой модели, как уже было описано, граф коммуникационных задач может быть транслирован в граф транзакций. Важным условием корректности трансляции является кратность объёма данных, передаваемых потоком данных, длине используемых транзакций. Это необходимо для получения целого количества транзакций и, следовательно, вершин графа.
Каждая вершина графа коммуникационных задач vi е V может быть представлена графом транзакций, а каждая дуга ei е E будет отображать связи между графами транзакций. Таким образом, может быть задано отображение
f1: V ^ T,
где T — множество графов транзакций, где каждый граф транзакций Tt = (Vi, E,). Здесь Vi — множество вершин графа, каждая из которых представляет собой одну транзакцию одной коммуникационной задачи, Et — множество дуг графа, указывающих на порядок исполнения транзакций. Каждая вершина графа транзакций определяется как
v _ t, = (vs , Vd, ),
где vs — инициатор передачи данных, master-устройство , vd — slave-устройство, c, — множество характеристик транзакции. Описание транзакции и коммуникационной задачи во многом совпадают: они имеют одинаковые источник и приемник данных, а так же характеристики за рядом исключений. Ниже представлены величины, составляющие множество характеристик транзакции.
1. Адрес.
2. Длина транзакции (Байт).
3. Ширина транзакции (Байт).
4. id транзакции.
5. Расчётное время исполнения транзакции (пс).
6. Величина паузы после транзакции, если она является последней в потоке(пс).
Дуги определяются как
e _ t = (v _ t,, v _ tj).
Формирование транзакций одной коммуникационной задачи происходит следующим образом. Для i-го графа транзакций Tt = f1(vi), vt eV, количество вершин |Vi| определяется как
, . = ) ' length(vi)'
где w(vi) — объём передаваемых данных в задаче vi■, Iещ— длина транзакций для задачи vi.
Количество оШ^а^^-транзакций, заданное для ■-й задачи указывает на количество простых путей в соответствующем ему графе транзакций.
Графы транзакций каждой задачи должны быть соединены дугами в том же порядке, как соединены вершины графа коммуникационных задач. Может быть задано следующее отображение:
Л :Е ^ ТЕ
Каждой дуге е} = Vj) ставится в соответствие множество дуг таких что, они выходят из всех вершин не имеющих исходящих дуг, и входят во все вершины 7}, не имеющие входящих дуг.
Таким образом, полный граф транзакций может быть определён как
G = (U V, U E ^ ТЕ), iе N, где n = VI,
i=1 i=1
то есть как совокупность графов транзакций каждой коммуникационной задачи и зависимостей между коммуникационными задачами.
В качестве примера рассмотрим граф, описывающий две взаимосвязанных задачи. Для этих задач укажем лишь те характеристики, которые существенны для трансляции в граф транзакций. Количество outstanding-транзакций обозначим как outs.
w(v0) = 16 Байт length(v0) = 4Байта, v1 = outs(v0) = 2
w(v1) = 16 Байт length(vl) = 2Байта . outs(v1) = 4
Пусть вершины v0 и v1 соединены дугой е0. Тогда такой граф задач может быть транслирован в граф транзакций, представленный на рисунке 13.
v0 = <
Рисунок 13. Получение графа транзакций на основе графа потоков данных
Поток v0 был транслирован в граф с двумя путями, а поток v1 в граф с четырьмя путями. В соответствие дуге е0 были поставлены дуги, соединяющие все вершины без исходящих дуг первого графа со всеми вершинами без входящих дуг второго графа.
2.2.2 Расчёт характеристик задач по графовой модели трафика
Для каждой задачи передачи данных vi может быть рассчитано её время исполнения. Обозначим его как t(vi). Оно вычисляется как отношение объема данных w(vi) к скорости передачи
=
Соответственно, для каждой задачи в графе, описанном в п.2.2.1, время исполнения будет следующим (таблица 3):
Таблица 3. Время исполнения коммуникационных задач выбранного графа
Vl v2 v3 v4 v5 v6 v7 v8 v9 v10 v11
Время исполнения, мс (Фд) 100 125 150 250 350 200 50 600 100 125 500
Теперь, зная время исполнения отдельных задач, зависимости и паузы между ними, могут быть вычислены время исполнения всех задач (от начала первой до конца последней), а также время исполнения задач, в которых участвуют один и тот же источник или приёмник.
Поскольку в предлагаемой методике граф коммуникационных задач является направленным ациклическим графом, то задача вычисления времени исполнения всех входящих в него задач может быть сведена к задаче о самом длинном пути (задача поиска простого пути максимальной длины в заданном графе), которая может быть решена за линейное время. В качестве веса дуг в данном случае можно использовать
сумму времени исполнения родительской задачи и величины паузы. То есть для каждой дуги соединяющей вершины и и V, его вес будет равен
Поскольку в общем случае рассматриваемый граф может иметь более одной начальной и конечной вершин, то необходимо добавить в граф одну начальную и одну конечную вершину А и В. Они должны быть добавлены таким образом, чтобы начальная вершина была соединена исходящими дугами со всеми вершинами, не имеющими входящих дуг, а конечная вершина была соединена входящими дугами со всеми вершинами, не имеющими исходящих дуг. Вес рёбер, исходящих из начальной вершины должен быть нулевым.
После этой модификации граф, рассматриваемый в качестве примера, будет выглядеть следующим образом (рисунок 14).
Самый длинный путь в этом графе будет представлен цепью
Соответственно общее время исполнения всех потоков данных, описываемых данным графом, можно вычислить как
|(и^)| = ^и) + р(и).
с = {А, VI, v4, v8, VII, В}.
и составит 1450мс.
Рисунок 14. Модифицированный граф потоков данных
Для задачи оценки производительности коммутационных сред также важно рассчитать теоретическое значение времени выполнения коммуникационных задач, относящихся к определённому источнику или приёмнику. Эта задача может быть решена аналогично предыдущей, но самый длинный путь необходимо искать в подграфе От исходного графа О, в котором начальная и конечная вершины будут соответствовать необходимому источнику или приёмнику. Аналогично, в этот подграф должны быть добавлены начальная и конечная вершины А и В. Также может быть дополнительно введён параметр операции, реализуемой задачей. Для рассматриваемого графа можно рассчитать время исполнения всех потоков от источников з1 и з2 по чтению и записи. Кроме того, на основе данных подграфов могут быть вычислены суммарный объём переданных данных в рамках одной операции между одним источником и приёмником.
На основании суммарного времени исполнения задач может быть рассчитано теоретическое значение скорости передачи данных. Результат вычислений представлен в таблице 4.
Таблица 4. Теоретические значения скорости передачи данных для каждого источника и операций чтения и записи
Коммуникационные задачи Путь Время исполнения, мс Суммарный объём данных, МБ Скорость передачи данных, МБ/с
s1, чтение {А, VI, v4, v8, VII, В} 1450 12 8,3
s1, запись {А, v8, В} 600 19 31,7
s2, чтение {А, v4, В} 250 15 60
s2, запись {А, v6, v9, v10, В} 425 17 40
Расчёт данных параметров необходим для одного из следующих шагов в описываемой методике анализа производительности коммутационных сред. Вычисленная скорость передачи данных и время исполнения каждой коммуникационной задачи должны быть использованы в качестве эталонных значений для сравнения с результатами, полученными после вычисления метрик производительности, которые будут описаны в следующем разделе.
2.2.3 Точность графовой модели трафика
Предложенная графовая модель трафика является приближённой. Точность модели определяется разницей между временем исполнения коммуникационной задачи, рассчитанным аналитически, и временем, вычисленным по результатам моделирования. Точность для /-ой коммуникационной задачи может быть выражена формулой:
где £(^) — время исполнения /-ой коммуникационной задачи, вычисленное по результатам моделирования, |Д£(гг)| — разница между временем исполнения коммуникационной задачи, рассчитанным аналитически, и временем, вычисленным по
результатам моделирования i-ой коммуникационной задачи.
В предложенной модели трафика предполагается, что первые транзакции в каждом простом пути, порождённом одной коммуникационной задачей, начнутся одновременно. Однако в моделях проектируемых устройств такие транзакции будут отправлены друг за другом с разницей как минимум в один такт. Это приводит к появлению задержки от момента начала исполнения задачи до момента, когда все входящие в неё подзадачи (по количеству outstanding-транзакций) начинают работать одновременно. При увеличении количества outstanding-транзакций эта не учитываемая в модели задержка будет увеличиваться. Таким образом, априорная оценка точности для i-ой коммуникационной задачи может быть выражена формулой:
OUts(Vj)
где N(Vi) — общее количество транзакций i-ой коммуникационной задачи, outs(vi) — количество outstanding-транзакций i-ой коммуникационной задачи.
2.3 Комплекс метрик производительности
В данном разделе будет описан комплекс метрик производительности и методы их вычисления, необходимые для анализа производительности коммутационных сред.
Предлагаемые метрики вычисляются на основе ряда величин, связанных с параметрами транзакций, поэтому введём несколько условных обозначений:
• Tn — текущая транзакция;
• size(Tn) — объем текущей транзакции;
• start(Tn) — время начала текущей транзакции;
• end(Tn) — время завершения; текущей транзакции;
• end(Tn-1) — время завершения предыдущей транзакции;
• t - длина временного промежутка, на котором производится измерение.
На рисунке 15 приведено условное графическое представление транзакции с обозначенными на нём параметрами.
t
Тп-1 Тп
cnd(Tn.!) start(Tn)
end(Tn)
time
Рисунок 15. Условное графическое представление транзакций
В таблице 5 представлены метрики, вычисление которых в рамках предлагаемой методики позволит оценить производительность подсистем коммутации. Таблица 5. Метрики производительности
Метрика Единицы измерения Формула
Время исполнения всего сценария с А = end(TN) — start (Т0), где T0 — первая транзакция, TN — последняя
Время исполнения транзакции с Ln = end(Tn) — start (Тп)
Средняя скорость передачи данных Байт/с v = X size(Tn) Vavg ^
Локальная пропускная способность Байт/с = size(Tn) n end(Tn) — end(Tn_1)
Скорость исполнения транзакции Байт/с = size(Tn) n end(Tn) — start (Tn)
Незавершённые транзакции шт On = XTm + l для Tmтаких, что startn < startm < endn
Все метрики кроме средней скорости передачи данных вычисляются отдельно для каждой транзакции, эти данных впоследствии могут быть усреднены различными способами, о которых будет сказано ниже. Важно отметить, что в качестве единицы времени может быть использована как секунда и кратные ей величины, так и период тактового сигнала как самостоятельная величина. Величины, связанные с объемом данных, такие как объем транзакции, измеряются в байтах и кратных им единицах.
2.3.1 Расчёт метрик для одной транзакции
Метрика «время исполнения транзакции» показывает время между началом передачи транзакции и полным ее приёмом (или получением ответа) и вычисляется как разность между временем конца и начала текущей транзакции и имеет размерность времени. На рисунке 16 представлен пример вычисления.
Рисунок 16. Вычисление времени исполнения транзакции
В данном случае время исполнения каждой транзакции равно 8 нс.
¿0 = 8 - 0 = 8 нс
^1,2,3 = ¿0 = 8 нс
Следовательно, усреднённый результат для четырёх транзакций также будет равен
8 нс.
4*8 ш ^ауд = 4 = 8 НС
Средняя скорость передачи данных показывает фактическую загрузку канала передачи данных и вычисляется как отношение суммарного объема переданных данных к длине временного промежутка, за который эти данные были переданы и, соответственно, имеет размерность скорости. На рисунке 17 приведён пример вычисления данной метрики. Для четырёх транзакций, размер каждой из которых равен 64 байта, и протяженности промежутка измерения в 2560 нс средняя скорость передачи данных будет равна 100 МБ/с.
2560 ns
64В 64В 64В 64В -►
time
Рисунок 17. Вычисление скорости передачи данных
64 * 4 = 2560 Б/НС Vavg = 100 МБ/с
Локальная пропускная способность позволяет учесть паузы между транзакциями и временной интервал её измерения для одной транзакции начинается с конца предыдущей транзакции и заканчивается концом текущей. На рисунке 18 представлен пример её вычисления.
Рисунок 18. Вычисление локальной пропускной способности
Для нулевой транзакции предыдущая транзакция отсутствует, поэтому за время её конца принимается время начала измерения, в данном случае 0 нс. Соответственно, локальная пропускная способность для нулевой транзакции будет равна 2 Б/нс:
16 В
С0 = ———-= 2 Б/нс
0 (8-0) пя '
Все следующие транзакции идут через равные промежутки времени и локальная пропускная способность для них равна 1,6 нс:
^1 =
16 В
= 1,6 Б/нс
(18 - 8) пя ^2,3 = = 1,6 Б/нс.
Следовательно, средняя локальная пропускная способность для четырёх транзакций будет равна 1,7 Б/нс:
X Сп 6,8
г =
до
= — = 1,7 Б/нс 4
Скорость исполнения транзакции показывает, как быстро была исполнена транзакция, то есть отношение объёма транзакции к времени её исполнения. На рисунке 19 представлен пример вычисления данной метрики.
Рисунок 19. Вычисление скорости исполнения транзакции
В данном примере каждая из четырёх транзакций объёмом в 16 байт была исполнена за 8 нс, соответственно скорость исполнения каждой из них равна 2 Б/нс:
16 Б
^0,1,2,3 = 77777 = 2 Б/нс
Р =
8 нс 4*2 Б/нс
4
= 2 Б/нс
Отличие от локальной пропускной способности состоит в том, что данная метрика не учитывает возможное наличие пауз между транзакциями. Рассмотрим пример вычисления трёх метрик скорости (средняя скорость передачи данных, локальная пропускная способность и скорость исполнения транзакции) для одного и того же случая. Пример последовательности транзакций изображён на рисунке 20.
Рисунок 20. Пример последовательности транзакций
В данном случае имеется 9 транзакций объёмом 16 байт каждая, временной промежуток измерения t = 44 нс. В этом случае мы получим следующие значения локальной пропускной способности и скорости исполнения транзакции:
16 Б
с0 =
(4 - 0) нс
= 4 Б/нс
16 Б
Сг_8 =-— = 3,2 Б/нс 5 нс
16 Б
Ео"9 = т^с = 4 Б/нс
Усреднив эти значения для количества транзакций и вычислив среднюю скорость передачи данных, получим:
4 + 3,2 * 8
С =
^avg
9
= 3,29 Б/нс
^avg = 4 Б/нс
16*9
Vavg 44
= 3,27 Б/нс
Из формул в таблице 5 легко видеть, что при уменьшении длины паузы и увеличения количества транзакций значение локальной пропускной способности и средней скорости передачи данных будут стремиться к значению скорости исполнения транзакций.
Последней метрикой из предлагаемого комплекса метрик для оценки производительности подсистем коммутации является количество незавершённых или одновременно исполняемых транзакций ('outstanding). Данная метрика показывает, какое количество транзакций началось с момента начала текущей транзакции и до момента её окончания, включая саму эту транзакцию. Иными словами, данная метрика характеризует способность проверяемого интерфейса отправлять или принимать одновременно несколько транзакций. На рисунке 21 представлен пример вычисления
количества одновременно исполняемых транзакции.
Рисунок 21. Вычисление количества одновременно исполняемых транзакций
В данном примере имеются четыре транзакции, начинающиеся последовательно друг за другом и имеющие следующие характеристики:
start(T0)=0, endo=5 start(T 1)=1, end1=6 start(T2)=2, end2=7 start(T3)=3, end3=8
Для T0 условие 0 < < епй0 выполняется для транзакций T1, T2 и T3,
соответственно О0 = 4.
2.3.2 Способы усреднения значений метрик
Как было сказано в предыдущем разделе, каждая метрика вычисляется для одной транзакции, однако для удобства практического использования предлагаемой методики результаты вычисления этих метрик могут быть усреднены различными способами для получения интегральных значений.
Для усреднения значений удобно разбить весь временной диапазон, на котором производится вычисление, на несколько более маленьких диапазонов с определённым шагом. На каждом из этих диапазонов могут быть рассчитаны минимальное, максимальное и среднее значение локальной пропускной способности, времени и скорости исполнения транзакции. Также подобное усреднение может быть произведено и на всём промежутке измерения. Таким образом,
с =
^ард до
Е =И
^ард до
где N - количество транзакций, попавших в данный диапазон.
Для количества одновременно исполняемых транзакций удобно использовать статистический подход к усреднению. В качестве случайной величины может быть принято значение данной метрики на некотором промежутке времени. В данной работе используется следующий подход. Весь диапазон измерения разбивается на поддиапазоны с неравномерным шагом — одной из границ поддиапазона является начало или конец какой-либо транзакции. Пример такого разбиения приведён на Рисунок 22. На каждом таком поддиапазоне вычисляется количество попавших в него транзакций. Для каждого значения метрики необходимо просуммировать длины диапазонов, на которых оно встречается. По результатам этих вычислений может быть построена гистограмма, и вычислена мода - ей будет значение, которому соответствует максимальный временной промежуток. Иными словами, в качестве интегральной характеристики должно быть взято значение, которое проявлялось большее количество времени, чем любое другое.
О 2
Количество А транзакций 8 7 б 5 4 3 2 1
0 4 64
Рисунок 22. Вычисление интегрального значения количества одновременно
исполняющихся транзакций
Просуммировав длины временных промежутков для каждого значения количества одновременно исполняемых транзакций, будет получен следующий результат: на протяжении 34 нс одновременно исполнялось 8 транзакций. Это время составляет 53% всего времени измерения (64 нс) и является максимальным. Поэтому соответствующее
ему значение может быть взято в качестве интегральной характеристики для всего диапазона измерения.
2.4 Критерии оценки производительности
Для оценки эффективности работы коммутационных сред в рамках данной методики необходимо ввести ряд критериев, применение которых к результатам вычисления метрик производительности поможет выявить возможное несоответствие системы заявленным требованиям, а также его причину.
Перед определением критериев необходимо ввести ряд условных обозначений:
• Лрассч — время исполнения полного графа задач, рассчитанное аналитически (с);
• ^ге/ — эталонное значение пропускной способности (Байт/с);
• Кс — коэффициент допустимого отклонения локальной пропускной способности, 0 < Кс < 1;
• Ке — коэффициент допустимого отклонения скорости исполнения транзакций, 0 < Ке < 1.
В рамках решаемой задачи все перечисленные величины считаются заранее определёнными на стадии проектирования архитектуры СнК и планирования и разработки самой коммутационной среды.
В таблице 6 приведены критерии оценки результатов вычисления метрик производительности.
Таблица 6. Критерии оценки результатов вычисления метрик производительности
1 Л > Л -^рассч Полный граф задачи выполняется медленнее, чем ожидалось
2 ^ард < ^^ге/ Устройство не обеспечивает необходимой скорости передачи данных.
3 Г < К * Г Локальная пропускная способность значительно ниже максимальной. Потенциально устройство может работать быстрее.
4 Еауд < ^е * ^тах Транзакции исполняются медленнее, чем потенциально могли бы. Потенциально устройство может работать быстрее.
5 ^тах < ^^ге/ Максимальная локальная пропускная способность ниже ожидаемой пропускной способности. Нужная скорость передачи данных не достигается.
6 г ~ Р °ауд ~ итах Транзакции передаются плотным потоком. Канал передачи полностью загружен. В противном случае устройство не создаёт необходимой нагрузки.
7 Еауд(т < Master-устройство медленнее обрабатывает транзакции.
78 Еард 0^) < Еауд(МБ) Slave-устройство медленнее обрабатывает транзакции.
2.5 Выводы
В данной главе были представлены теоретические основы методики оценки производительности коммутационных сред с учётом структуры СнК и прикладных задач. Были рассмотрен подход к трансляции ограничений с уровня системы и других блоков на уровень подсистемы коммутации, теоретические аспекты подхода к формализации тестовых сценариев в виде направленного графа потоков данных, предложен комплекс метрик производительности и критерии их оценки.
Предложенный метод трансляции ограничений позволяет учитывать структуру СнК на уровне характеристик интерфейсов взаимодействия всей системы с подсистемой коммутации, а также состава и характеристик блоков, подключенных к подсистеме коммутации.
Описанная в данной главе графовая модель трафика позволяет исключить необходимость учёта вычислительных задач в процессе верификации. Параметры описания трафика, используемые в предложенной модели, обладают достаточной подробностью для описания трафика приложений. Кроме того, предложенный подход к построению формального описания трафика позволяет абстрагироваться от архитектуры, состава и реализации подсистемы коммутации, что значительно облегчает задачу верификации.
Предложенные метрики и критерии оценки производительности не зависят от модели трафика и подсистемы коммутации. Они позволяют не только оценить производительность, но и выявить потенциальные «узкие места» подсистемы коммутации. В случае несоответствия требованиям к производительности предложенный комплекс метрик и критериев позволит выявить область подсистемы коммутации, которая стала причиной падения производительности.
Таким образом, в данной главе были решены перечисленные ниже проблемы.
1. Для описания автономных тестов, учитывающих структуру СнК и характеристики отдельных блоков и подсистем, на высоком уровне абстракции разработана методика трансляции ограничений с уровня системы на уровень подсистемы коммутации и отдельных блоков.
2. Предложенная графовая модель трафика в коммутационных средах позволяет отказаться от симуляции вычислительных задач. Учёт их влияния в математической модели трафика может быть задан с помощью параметра «пауза» р^
3. Проблема описания трафика в подсистемах коммутации, связанная с недостаточной точностью для проверки свойств подсистемы коммутации и выявления влияние различных характеристик трафика на производительность, решена благодаря учёту ограничений со стороны системы и других блоков, а также введением в модель трафика дополнительных параметров описания потоков данных.
4. Предложенная математическая модель трафика позволяет абстрагироваться от архитектуры подсистемы коммутации и унифицировать способ формирования входных воздействий, что решает проблему сложности верификации подсистем коммутации, имеющих различную архитектуру и состав блоков.
5. Проблема сложности унификации верификационных компонент и стандартизации маршрута верификации, связанная с зависимостью определения и способа вычисления метрик производительности от выбранной математической модели подсистемы коммутации, решена благодаря введению формул расчёта метрик, не зависящих от выбранного представления подсистемы коммутации.
6. Проблема локализации причины несоответствия модели проектируемой подсистемы коммутации требованиям к производительности решена благодаря введению критериев оценки метрик производительности.
Глава 3. Разработка алгоритмов и архитектуры программного комплекса
В данной главе рассмотрены вопросы разработки алгоритмов и архитектуры программного комплекса для предложенной методики автоматизации анализа производительности коммутаторов. Изложены алгоритмы, используемые для генерации входных воздействий на основе высокоуровневого описания тестового сценария, исполнения сценария, вычисление метрик и критериев производительности, формирования отчёта. Описана архитектура программного комплекса и верификационной инфраструктуры, реализация основных модулей, входящих в его состав, и взаимодействия этих модулей между собой и с другими инструментами.
Для реализации методики автоматизированного анализа производительности в рамках данной работы был разработан программный комплекс, включающий в себя программные средства для реализации отдельных этапов этой методики. Для реализации данного комплекса необходима базовая верификационная инфраструктура, позволяющая унифицировать тестовые компоненты и дающая возможность их повторного использования. На рисунке 23 представлена структура предлагаемого программного комплекса. Пунктирным контуром на схеме обозначены данные, которые являются входными и выходными для различных модулей.
Рисунок 23. Структура программного комплекса, реализующего методику автоматизированного анализа производительности коммутационных сред, в виде
диаграммы модулей
Помимо базовой верификационной инфраструктуры, включающей в себя
шаблонные тестовые окружения и модульное средство сборки Project Compiler, в предлагаемый программный комплекс входят инструменты для автоматизированного запуска параметризованных тестовых сценариев, расчета метрик и анализа критериев производительности, формирования отчета, а также генератор тестовых воздействий на основе графов. Каждый элемент этого комплекса будет подробно рассмотрен в следующих разделах.
3.1 Базовая верификационная инфраструктура
Необходимость автоматизированной оценки производительности коммутационных сред подразумевает, что предлагаемая методика может быть применена к любой подсистеме коммутации при соблюдении интерфейсов взаимодействия между различными инструментами. Это создаёт необходимость в унификации этих инструментов и, следовательно, в возможности свободного переноса кода от проекта к проекту.
Описываемая в данной работе реализация методики анализа производительности коммутационных сред опирается базовую верификационную инфраструктуру, включающую в себя генерируемые шаблонные тестовые окружения и модульное средство сборки.
Основные положения и результаты, описанные в разделах 3.1.1 и 3.1.2, изложены в следующих работах автора: [75], [76], [1], [77], [78].
3.1.1 Шаблонные тестовые окружения
Исходя из обозначенных в предыдущей главе особенностей разных классов СФ-блоков и подходов к их верификации, можно сформулировать основные свойства шаблонного окружения, пригодного для создания окружений для большинства классов СФ-блоков.
• «Обеспечение возможности запуска любых обозначенных в предыдущей главе типов тестовых сценариев, в том числе в многопоточном гетерогенном режиме (различные сочетания типов параллельно исполняемых сценариев) с обеспечением единого механизма синхронизации и обмена данными.
• Единая для автономных и системных окружений инфраструктура тестовой печати, управления внешними агентами (VIP) и синхронизации между процессами, доступная всем типам тестовых сценариев.
• Единое адресное пространство доступное со стороны тестовых сценариев, верифицируемого устройства и агентов быстрого доступа к памяти.
• Интегрированые агент JTAG интерфейса и средства подключения отладчика (типа gdb).
• Параметризация верификационных компонент.
• Обеспечение возможности запуска высокоуровневой (С++/^М) модели устройства.
• Поддержка пассивного режима работы.
• Все агенты интерфейсов содержат мосты для преобразования транзакций к унифицированному типу, таким образом, что большинство высокоуровневых компонент окружения (типа анализаторов, модулей печати и т.п.) не привязываются к конкретным интерфейсам и пригодны к использованию в большинстве окружений различных блоков.
• Окружение имеет базовую часть, содержащую стандартные компоненты, типа генераторов тактового сигнала и сброса, мониторов прерываний, контроллеров двунаправленных портов, мониторы, анализаторы, базовые тестовые последовательности, и прочие компоненты не привязанные к реализации верифицируемого устройства. Генерируемые окружения создаются как классы, наследующие описанную базовую часть» [1].
На рисунке 24 представлена схема унифицированного тестового окружения. Оно включает в себя три основных компонента - базовую часть, одинаковую для всех устройств, базовую часть для класса устройств, и часть, реализующую свойства и объекты, специфичные для конкретных устройств.
База для всех |~| База для класса устройств [~] Конкретное устройство
у^Г
Agent
Default slave
DPI С++ interface
UVM GP Master Agents
base seq lib
UVM EVENT Agents
UVM CLK/RST Agents
Virtual Sequencer
1 REG ■ MODEL ♦backdoor
UVM GPIO Agents
ENV ADDR MAP
UVM GP Slave Agents
UVM TEST Sequence
Default statistic and debug
user statistic and debug
ScoreBoard (dummy)
Рисунок 24. Унифицированное тестовое окружение
«Отличительным свойством базовой части является интегрированный интерфейс взаимодействия с тестовыми программами исполняемыми процессором рабочей станции. К базовой части окружения привязана программная компонента интерфейса взаимодействия ПО с окружениями, обеспечивающая работу драйверов устройств и тестовых сценариев» [1].
3.1.2 Модульное средство сборки
Для решения задачи свободного переноса тестовых компонент по всем направлениям пространства этапов верификации, определённого в разделе 1.1.3, необходима инфраструктура, позволяющая отвязать реализацию различных действий (в том числе типовых), производимых с тестовыми компонентами, от реализации этих компонент и структурной организации проекта. Такими действиями могут быть, к примеру, компиляция тестов, элаборация rtl-описания проекта, запуск симуляции, сбор покрытия, обработка данных от мониторов агентов, построение различных отчетов, расчет метрик производительности.
Предлагаемая в данной работе методика автоматизированной оценки производительности коммутационных сред опирается на разработанное модульное средство сборки Project Compiler. Оно представляет собой распределённую
инфраструктуру, состоящую из xml-файлов, флйлов с программными блоками на языке python и набор управляющих модулей (также на языке python), реализующих основной функционал инструмента. Таким образом, Project Compiler является оболочкой для выполнения команд, автоматизирующей маршрут верификации СнК.
Структура конфигурационных xml-файлов данного инструмента представлена на рисунке 25.
«Класс Compiler является основным классом, выполняющим загрузку xml и запуск команд. Объект имеет древовидную иерархию, соответствующую иерархии конфигурационных xml. Структура конфигурационных xml-файлов представляет собой три группы: файлы для конкретного проекта, файлы для группы проектов и общие (глобальные). Все файлы для конкретного проекта, равно как и файлы для группы проектов, подключаются в одном файле. Параметры и переменные, определённые в глобальных xml, подключаются в xml верхнего уровня группы проектов, который, в свою очередь, подключается в xml верхнего уровня конкретного проекта. Таким образом, части одной команды могут быть описаны в разных файлах. Такая структура позволяет выделить настройку или определение только тех переменных, параметров и команд, которые необходимо настроить для конкретного проекта, что позволяет увеличить повторное использование кода сборки и запуска библиотек, тестов и драйверов» [1].
Рисунок 25. Структура конфигурационных xml-файлов инструмента
Project Compiler
«Данный инструмент поддерживает возможность компиляции нескольких библиотек и компиляцию тестов одновременно для разных библиотек и разных целей, например для ядер различной архитектуры. Эти действия выполняются так же при помощи конфигурационных xml-файлов.
Модульный подход подразумевает выделение блоков кода, общих для нескольких проектов. Это упрощает процесс разработки, но увеличивает зависимость группы разработчиков от различных коррекций в общей для них части кода. Для работы над проектами с большой иерархической вложенностью, а также для увеличения повторного использования большого объема общего для многих проектов кода, правки в котором влияют сразу на группу проектов, возникла необходимость в разработке системы релизов. Таким образом, было принято решение о необходимости создания системы управления релизами, учитывающей потребности разработчика, верификатора и тополога. Релиз (от англ. release) - это срез состояния RTL и верификационных компонент, представляющий собой стабильную версию проекта. Каждый релиз содержит информацию о степени его готовности и особенностях данной версии. Релизы проекта являются опорными точками в его разработке. Это даёт возможность использовать заведомо работающую версию блока при работе над проектом. Система релизов также позволяет выполнять моделирование проекта с заданными пользователем версиями блоков, например для анализа причин сбоев. Для определения статуса релиза, а также для его подтверждения, применяются так называемые квалификационные тесты - при попытке выпуска очередного релиза, автоматически выполняется некоторый набор тестов, и в случае его успешного прохождения создаётся новый релиз. Релиз хранится в виде иерархического xml-описания блока и его зависимостей. В xml-описании указывается путь к репозиторию и ревизия данного блока. Основными компонентами описания зависимых блоков являются путь к конкретному блоку в репозитории и его ревизия, которая включена в данный релиз. Данная система релизов отвечает требованиям, которые предъявляются к ней со стороны разработчика RTL и верификатора, среди которых:
• создавать проекты с иерархической структурой из релизов;
• обеспечить возможность выбора конкретной версии для каждого используемого релиза блока;
• разрешать конфликты при интеграции релизов блоков (СФ-блоки ссылаются на различные релизы своих зависимых блоков);
• подтвердить статус релиза, выпущенного разработчиком, проверив его набором квалификационных тестов.
Использование релизов позволяет минимизировать вероятность случайной правкой сделать неработоспособной модель СнК и систематизировать библиотеку СФ-блоков, в том числе автоматически ведя учёт их использования в разных проектах.
Таким образом, предлагаемый инструмент является в первую очередь средством автоматизации маршрута верификации. Его основным преимуществом является модульность, что позволяет существенно снизить временные затраты на разработку и, как следствие, удешевить конечный продукт. Важно помнить о том, что снижение временных затрат зависит от конкретной группы разработчиков, инфраструктуры, используемой на предприятии, и конкретного проекта. Экономия времени достигается за счет достигнутой для конкретного проекта модульности и пропорциональна количеству уровней иерархии проекта и повторно используемых модулей. Кроме того, данный инструмент делает процесс разработки и отладки более контролируемым - это достигается за счет подробной системы логирования и контроля входных аргументов. Поддержка системы релизов позволяет разработчику избавиться от зависимости от правок в используемых им блоках и работать со стабильными, прошедшими проверку версиями» [1].
3.2 Инструмент для автоматизированного формирования тестовых воздействий
Одним из основных элементов предлагаемого в данной работе программного комплекса для автоматизированной оценки производительности коммутационных сред является набор программных средств, реализующий автоматизированное формирование тестовых воздействий. Данный инструмент формирует тестовые сценарии, представленные в виде графа транзакций на основе высокоуровневого описания потоков передачи данных. Предлагаемый программный комплекс состоит из двух основных блоков: генератора графа транзакций и их проигрывателя.
Предлагаемый программный позволяет генерировать тесты следующих типов:
• тесты для проверки карты памяти;
• синтетические тесты для оценки производительности;
• тесты на основе сценариев использования устройства.
Кроме того, в него заложена возможность генерации случайных и параметризованных тестов. На рисунке 26 представлена структурная схема данного комплекса.
Основные положения и результаты, приведённые в разделах 3.2, 3.2.1, 3.2.2 изложены в следующих работах автора: [79], [80].
Рисунок 26. Структурная схема программного комплекса автоматизированного формирования тестовых воздействий
3.2.1 Алгоритм генерации графов транзакций
В данном блоке происходит преобразование описания потоков передачи данных в описание графа транзакций. Входные и выходные данные являются текстовыми, описанными с использованием специально разработанного синтаксиса. Сам генератор представляет собой программу, написанную на языке python.
Входные данные
Входными данными для генератора являются таблица ограничений, описание потоков данных и служебный настроечный файл. Пример таблицы ограничений приведён на рисунке 27.
Таблица ограничений представляет собой csv-файл (данные с разделителем) и включает в себя матрицу коммутации, карту памяти, допустимые значения и
характеристики master и slave агентов. Все эти данные представлены в виде двумерной таблицы. Ниже приведён пример подобной таблицы.
CLK S 0
RlL maste MAINM
Slave agen ts axi m if
Length 1 2 4 8
Width 1 2 4 8
4kBound 1
Align 0
Com rw
OUTSTANDING TRANS ID CLK M RTL slave Master agents Length Width 4kBound Align Com Num 0
16 0-4 0 L2C axi elv s if 1 2 4 8 4 8 1 1 rw 0 00000000 100000000
Рисунок 27. Пример таблицы ограничений
В строках таблицы располагаются характеристики RTL-slave портов, в столбцах RTL-master портов, на их пересечении располагается карта памяти, совмещённая с матрицей коммутации. В таблице 7 приведены обязательные поля таблицы и их значение.
Таблица 7. Поля таблицы ограничений
Поле таблицы Описание
Num Номер master/slave-агента.
com Возможность порта осуществлять операции чтения и записи. Например, запись «сот=т» говорит о том, что данный порт может осуществлять и запись, и чтение.
align Флаг, принимающий значения «0» и «1». Индикатор необходимости выравнивания адреса по размеру транзакции.
4kBound Флаг, принимающий значения «0» и «1». Индикатор запрета на пересечение одной транзакцией 4К-адресного диапазона.
width Допустимые значения (диапазоны значений) ширин транзакций, которые может отправлять данный порт.
length Допустимые значения (диапазоны значений) длин транзакций, которые может отправлять данный порт.
master_agents / slave_agents Имя интерфейса, подключенного к агенту.
RTL_slave / RTL_master Имя RTL-порта.
mem_ranges Диапазоны адресов карты памяти, по которым взаимодействуют
Поле таблицы Описание
порты, указывается на пересечении строки и столбца master- и slave-порта соответственно. В случае отсутствия соединения между двумя портами, вместо диапазона адресов указывается символ «s». Для данной ячейки (и только для неё) числа указываются в шестнадцатеричном формате.
CLK_M / CLK_S Номера источников тактовых сигналов, соответствующих агентам.
TRANS_ID Допустимые значения (диапазоны значений) id транзакций, отправляемых интерфейсом.
OUTSTANDING Максимальное количество транзакций, которое может быть отправлено master-интерфейсом с одним значением id.
Описание потоков данных (коммуникационных задач) является формой представления тестового сценария, на основе которого генерируется граф транзакций. Оно представляет собой текстовый файл с расширением .Ш (по умолчанию имеет имя «streamSets.txt») и в общем случае содержащий в себе описание серий независимых и зависимых друг от друга операций чтения и записи с использованием специального синтаксиса. В таблице 8 представлены значения полей, необходимых для описания одной коммуникационной задачи в соответствие с положениями, приведённым в разделе 2.2.1.
Таблица 8. Поля описания потоков данных
Имя Допустимые значения Описание
Обязательные поля
outstanding_trans actions целое число / default Количество outstanding транзакциий, на которое будет разбиваться поток. При default значение будет браться из таблицы, указанной в файле settings.py
name любая строка Уникальное имя потока
master целое число Номер master-порта, отправляющего транзакции
slave целое число Номер slave-порта, принимающего транзакции
operation r / w Операция (чтение, запись)
addr default / Адрес или диапазон адресов,
Имя Допустимые значения Описание
aaaa-bbbb,cccc-dddd (в шестнадцатиричной системе без символов x или 'h.) куда будут отправляться транзакции.
vol целое число / целое число[единицы измерения] Общий объем данных, которые необходимо передать
speed целое число / целое число[единицы измерения] / max Скорость, с которой будет передаваться этот объем данных. При значении max будет задана максимальная скорость
length целое число / целое число[единицы измерения] / ключевые слова Длина транзакции в байтах
width целое число / целое число[единицы измерения] / ключевые слова Ширина транзакции в байтах
static_pause целое число Время ожидания между потоками
next строка Имя потока, который будет запущен по окончании текущего. Если поле пустое, то не будет запущен ни один поток
Необязательные поля
id_mode cycle / rand / single Способ генерации id транзакций. cycle - циклические id rand - рандомные id single - фиксированный id Значение по-умолчанию: rand
id_value a / a-b,c-d / a-b,c-d,e / default (все числа целые) Диапазоны значений, из которых будут выбираться id. При значении default диапазоны будут браться из table_of_constraints.csv. Если там не заполнен столбец TRANS ID, то id сгенерируется случайным образом из диапазона 0-216. Значение по умолчанию: default
Кроме приведённых выше полей, в описании потоков данных могут использованы специальные ключевые слова, необходимые для описания потоков в параметризованных сценариях, а также для использования значений по умолчанию.
Первым типом ключевых слов являются параметры. Они определяются в начале файла перед описанием потоков. Параметры могут быть двух типов и определяются ключевыми словами «@iter» и «@param». Для первых параметров запускается полный перебор всех комбинаций, значения вторых будут просто подставлены в описание потока в те места, где они используются. Пример:
@iter: master=[0,1] @iter: slave=[0,1] @param: length=8 Будут сгенерированы следующие комбинации значений:
master[0], slave[0], length master[0], slave[1], length master[1], slave[0], length master[1], slave[1], length В качестве значений полей потока или значений параметров могут быть использованы следующие ключевые слова: «max_length_m», «max_length_s», «max_width_m», «max_width_s», «max_width», «max_length», «default», обозначающие соответственно максимальную длину транзакций для master/slave-агента, максимальную ширину транзакций для master/slave-агента, максимальную общую длину/ширину транзакций для пары master-slave и значение по-умолчанию (если таковое определено).
Последним необходимым элементом входных данных является служебный настроечный файл. Он представляет собой файл с расширением .py (по-умолчанию имеет имя «settings.py»), написанный на языке python. Он содержит описание служебных переменных, необходимых для корректной работы генератора (такие как пути к различным элементам верификационной инфраструктуры), а также параметры работы для конкретного теста, если необходимо. В частности, для генерации случайного теста в этом файле должны быть описаны параметры генерируемых случайных потоков, такие как количество транзакций записи/чтения с определенных master-агентов, количество адресов, попадающих на края адресного диапазона и вероятность попадания транзакции в край адресного диапазона.
Выходные данные
Выходными данными генератора являются два текстовых файла с расширением .Ш и по-умолчанию имеющих названия «tranz.txt» и «preWrite.txt». В этих файлах содержится описание транзакций с очерёдностью их выполнения (плоское представление графа транзакций) и данные, необходимые для предзаписи в память. В таблице 9 приведён список параметров, с помощью которых описываются транзакции. Таблица 9. Описание транзакций в файле «tranz.txt»
Название Описание
Имя транзакции Уникальный идентификатор транзакции, включающий в себя порядковый номер. Необходим для определения зависимостей между транзакциями и, соответственно, очерёдности их выполнения. Может быть два типа имён: начинающиеся с «adam» и начинающиеся с «louis». Первый тип имён присваивается транзакциям, не имеющим родительских транзакций, то есть не зависящим ни от одной другой.
id Id транзакции.
strm name Имя потока, к которому относится транзакция. Оно соответствует имени, указанному в описании потока.
mN=>sN / mN<=sN Интерфейсы передачи и приёма транзакции, её тип. Интерфейс обозначается его номером из таблицы ограничений, прибавленным к символу «m» (для master-агентов) или «s» (для slave-агентов). Комбинация символов «=>» соответствует записи, «<=» - чтению.
address Адрес, начиная с которого будет произведено чтение/запись. Указывается в шестнадцатеричной форме без специальных символов.
length Длина транзакции в байтах.
streaming_width Ширина транзакции в байтах.
static_pause Длина статической паузы в пикосекундах, которую необходимо выдержать между завершением текущей транзакции и началом всех зависящих от неё транзакций.
dynamic_pause Длина динамической паузы в пикосекундах. Если время исполнения текущей транзакции оказалось меньше этой величины, то до отправки следующей транзакции необходимо выдержать время, равное разнице между величиной динамической паузой и временем исполнения транзакции.
relation Транзакция, которая будет запущена после окончания текущей. Это единственное поле, которое может быть указано несколько раз для одной транзакции. Имеет вид «relation <имя транзакции>», например «relation louisl».
Файл предзаписи содержит в себе строки, последовательно указывающие начальный адрес и количество данных в байтах, которые необходимо записать в память, начиная с этого адреса. Пример:
1ab2b5dc780 32
В данном случае в память будет записано случайное слово длиной в 32 байта начиная с адреса 1ab2b5dc780.
Алгоритм работы
Генератор имеет три режима работы: стандартный (для генерации графа транзакций по описанию потоков), параметрический (для генерации набора описаний потоков по параметризованному описанию) и случайный (для генерации случайных графов транзакций по заданным ограничениям).
В общем случае алгоритм работы генератора состоит из трёх основных шагов: предварительной обработки данных, формирования графа транзакций и данных для предзаписи и формирование выходных файлов. С учетом различных режимов работы её можно представить в виде структурной схемы, изображенной на рисунке 28.
В первую очередь рассмотрим обычный режим работы. Для этого режима данные из файла streamSets. txt после считывания преобразуются во внутренний формат данных, после чего происходит подстановка значений ключевых слов (если они присутствуют), преобразование единиц измерения (временные величины переводятся в пикосекунды, объем данных в байты, скорость передачи данных в Байт/пс). «Далее полученные данные проверяются на соответствие таблице ограничений; в случае, если хотя бы одна из характеристик потока не соответствует требованиям, данный поток отбрасывается. Далее формируется граф потоков на основе полей «next» в описании каждого потока. После этого для каждого потока происходит формирование графа транзакций на основе его описания. Когда сформированы графы транзакций для каждого потока они объединяются в один путем указания соответствующих зависимостей для первых и последних транзакций графа. На основании полученного графа транзакций формируется набор данных для предзаписи. Для этого выбираются все уникальные адреса, по которым будут отправляться транзакции и их длины» [79]. Последним шагом является вывод полученных данных в файлы tranz.txt иpreWrite.txt.
Начало
Чтение
Э^е amSets.txt
Бы бор режима работы
1 1
Параметрический Обьшный Случайный
1 | 1
Чтение параметров Формирование графа потоков Генерация графа потоков
Создание допустимых комбинаций 'значений параметров Формирование графа транзакций на основе графа потоков
Подстановка значений параметров в описание потоков Генерация данных для пред записи
Вывод сгенерированных потоков в файлы Вывод в файл графа транзакций и данных для пред записи
Конец
Рисунок 28. Структурная схема алгоритма работы генератора
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.