СПОСОБ ТЕСТИРОВАНИЯ КОМПОНЕНТОВ МИКРОПРОЦЕССОРОВ, ТЕСТОВЫЙ ОРАКУЛ ДЛЯ ТЕСТИРОВАНИЯ КОМПОНЕНТОВ МИКРОПРОЦЕССОРОВ, СПОСОБ РАБОТЫ ТЕСТОВОГО ОРАКУЛА, СПОСОБ ПОСТРОЕНИЯ ТЕСТОВОГО ОРАКУЛА
METHOD OF TESTING MICROPROCESSOR COMPONENTS, TEST ORACLE FOR TESTING MICROPROCESSOR COMPONENTS, TEST ORACLE OPERATION METHOD, METHOD OF CONSTRUCTING TEST ORACLE

Область техники
Предлагаемая группа изобретений относится к системам тестирования микропроцессоров и может использоваться при проектировании, производстве и эксплуатации микропроцессорной техники, в частности для микропроцессоров конвейерной архитектуры.
Уровень техники
В современной экономике производство микропроцессоров имеет большое значение в силу их широкого использования во многих отраслях. Микропроцессор является сложным электронным устройством, производство которого можно начать только после тщательного проектирования. Проектирование микропроцессоров чаще всего выполняется на специализированных языках моделирования аппаратного обеспечения (например, Verilog, VHDL, SystemC), позволяющих абстрагироваться от деталей расположения и соединения отдельных элементов электронной схемы. Проект микропроцессора на таком языке является исполнимой программой с набором параметров, представляющих входы процессора, и называется моделью. По окончании проектирования модель транслируется в точное описание расположения и соединения друг с другом отдельных элементов электронной схемы процессора. Модель обычно имеет иерархическую структуру - в процессоре выделяются модули, более простые, чем процессор в целом, и определяются правила взаимодействия между ними. Каждый из модулей решает четко определенные задачи так, чтобы набор взаимодействующих модулей в целом делал ровно то, что требуется от микропроцессора. Отдельные модули могут быть декомпозированы далее на еще более мелкие модули.
Поскольку большинство современных микропроцессоров являются очень сложными устройствами, при их проектировании часто делаются ошибки. Ошибка проектирования впоследствии может проявиться как некорректное, несоответствующее требованиям поведение процессора в определенной ситуации. Ошибки в микропроцессорах способны приносить очень большой ущерб, однако их исправление в уже изготовленном процессоре возможно только в исключительных случаях и требует колоссальных затрат. Поэтому большую часть ошибок крайне желательно выявить и исправить еще в процессе проектирования, при разработке модели.
Для этого используют различные техники верификации моделей микропроцессоров, нацеленные на обнаружения ошибок, то есть отклонений поведения от требуемого. Наиболее широко используемый метод верификации - имитационное тестирование. Оно состоит в программной имитации работы процессора, описываемого моделью, с помощью симулятора языка моделирования, на котором она написана, в рамках ряда специально разработанных сценариев, представляющих основные варианты использования функций этого процессора, возможные при его эксплуатации. Симулятор языка моделирования - это программное средство, позволяющее выполнять программы на этом языке. Для имитационного тестирования, помимо симулятора и самой модели, необходим также набор тестов, являющихся обычно программами на том же языке и описывающих различные сценарии использования процессора.
Наибольшую сложность при имитационном тестировании составляет подготовка тестов. Каждый тест определяет сценарий подачи в определенном порядке различных сигналов на разные входы процессора и получения ответных сигналов на выходах и выполняет проверку правильности этих ответов. Набор ответов считается правильным, если он соответствует требованиям к процессору, сформулированным в техническом задании на него.
Поскольку современные процессоры очень сложны, отдельные их модули также часто бывают достаточно сложны. Для большей эффективности обнаружения ошибок и упрощения их анализа тестирование процессора включает тестирование его модулей по отдельности. При этом имитационное тестирование организуется практически так же, только вместо модели процессора используется модель его отдельного модуля, а вместо тестов всего процессора - тесты, описывающие различные сценарии взаимодействия этого модуля с другими частями процессора. При создании тестов для отдельного модуля для определения правильности выдаваемых им результатов используется не техническое задание на процессор, а проектные документы, описывающие функции именно этого модуля. Далее в тех местах, где речь идет об имитационном тестировании процессора или модуля процессора, используется термин тестируемый компонент.
Создание хороших наборов тестов является сложной технической задачей, поскольку тесты должны также обеспечивать достаточно представительное множество сценариев работы тестируемого компонента (полноту тестирования), чтобы выводы о качестве и надежности его работы по результатам тестирования соответствовали действительности.
В настоящее время существует три основных подхода к созданию тестов для имитационного тестирования микропроцессоров и их модулей.
Разработка тестов вручную. Это наиболее широко применяемый метод, описанный в работах: J.Bergeron. Writing Testbenches: Functional Verification of HDL Models. Second edition. Springer, 2003; A. Meyer. Principles of Functional Verification. Newnes, 2003; W.K.Lam. Hardware Design Verification: Simulation and Formal Method-Based Approaches. Prentice Hall, 2005. Он состоит в том, что каждый отдельный тест создается членом группы проектирования - тестировщиком. Тестировщик сам должен определить, как проверить правильность получаемых результатов в тестах, а также обеспечить достаточную полноту тестового набора в целом. Достоинством этого подхода является его простота, а его основной недостаток - это сильная зависимость полноты набора тестов от опыта и аккуратности тестировщика. Кроме того, при этом подходе общее количество используемых тестов ограничено производительностью труда тестировщиков и временем, отпущенным в проекте на тестирование. Это делает зависимость их полноты от грамотного проектирования тестового набора в целом еще более сильной.
Автоматическая генерация тестов как всех различных комбинаций возможных входных сигналов для тестируемого компонента описана в работах: W.К.Lam. Hardware Design Verification: Simulation and Formal Method-Based Approaches. Prentice Hall, 2005; H.Al-Assad and J. P. Hayes. Design Verification via Simulation and Automatic Test Pattern Generation. International Conference on Computer Aided Design, 1995, pp.174-180; S. Bhattacharya, S. Dey, and B. Sengupta. An RTL Methodology to Enable Low Overhead Combinational Testing. Technical Report 96-CO16, C&C Research Labs, NEC USA, April 1996. При этом разрабатывается программа-генератор тестов, генерирующая различные сценарии подачи сигналов. Для проверки соответствия результатов требованиям к тестируемому компоненту вручную разрабатывается программа, выполняющая эту проверку. Достоинством этого подхода является возможность получить набор тестов, покрывающий очень большой набор возможных ситуаций. Его недостаток - это невозможность строить в генерируемых тестах сложные сценарии использования тестируемого компонента, поскольку сложность проверки правильности получаемых результатов в этом случае значительно возрастает и разработка программы для этого становится слишком сложной.
Автоматическая генерация тестов на основе модели требований к тестируемому компоненту описана в работах: A.Aharon, D.Goodman, M.Levinger, Y.Lichtenstein, Y.Malka, C.Metzger, M.Molcho, and G.Shurek. Test program generation for functional verification of PowerPC processors in IBM. In 32-nd Design Automation Conference, DAC 95, pages 279-285, 1995; J.Dushina, M.Benjamin, and D.Geist. Semi-formal test generation with Genevieve. In Design Automation Conference, DAC 2001, pages 617-622, 2001; В.П.Иванников, А.С.Камкин, В.В.Кулямин, А.К.Петренко. Применение технологии UniTesK для функционального тестирования моделей аппаратного обеспечения. Препринт 8 ИСП РАН, Москва 2005. Модель требований представляет собой формальное описание требуемого поведения тестируемого компонента. Различные сценарии тестов определяются так, чтобы задействовать все элементы этой модели (операции, инварианты и другие проверяемые ограничения). При разработке тестов в этом случае создаются модель требований и набор сценариев тестирования, а также используется специальный программный инструмент - транслятор моделей требований и сценариев. Достоинством этого подхода является возможность автоматизации генерации сложных тестов, проверяющих различные функции тестируемого компонента более глубоко. Его недостаток - сложность и повышенные требования к навыкам разработчиков модели требований и сценариев тестирования. Однако при его использовании один разработчик модели требований может подготовить столько тестов, сколько при ручной разработке сделают за то же время десяток тестировщиков.
Подход к генерации тестов на основе модели требований может использовать следующую общую структуру тестов, описанную в работах: В.П.Иванников, А.С.Камкин, В.В.Кулямин, А.К.Петренко. Применение технологии UniTesK для функционального тестирования моделей аппаратного обеспечения. Препринт 8 ИСП РАН, Москва 2005; I.Bourdonov, A.Kossatchev, V.Kuliamin, and A.Petrenko. UniTesK Test Suite Architecture. In Proc. of FME 2002. LNCS 2391, pp.77-88, Springer-Verlag, 2002; В.В.Кулямин, А.К.Петренко, А.С.Косачев, И.Б.Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003. При этом подходе тест состоит из генератора тестовой последовательности и тестового оракула, где:
Генератор тестовой последовательности строит последовательность обращений к различным входам тестируемого компонента (или его исполнимой модели). Каждое обращение определяет набор сигналов, одновременно подаваемых на входы модели.
Тестовый оракул или просто оракул собирает все полученные от тестируемого компонента (или его модели) результаты и оценивает их корректность, то есть соответствие требованиям к этому компоненту.
В ходе выполнения теста в рамках имитационного тестирования с помощью симулятора выполняется имитация работы тестируемого компонента по его модели на языке моделирования. При этом имитируется периодическое изменение сигнала генератора тактовой частоты, определяющего базовый цикл работы компонента. В начале каждого цикла генератор тестовой последовательности строит очередное обращение к модели и передает все входящие в него сигналы как самой модели, так и оракулу. После этого оракул собирает все выходные сигналы модели и производит оценку их корректности как ответов на все поступившие до этого момента входные сигналы. Если оракул обнаруживает ошибку - несоответствие полученных результатов требованиям, - тест завершается с выдачей сообщения о найденной ошибке.
Если ошибок не обнаруживается, по окончании тестовой последовательности генератор создает нулевые сигналы на всех входах столько раз, сколько модели требуется для выдачи ответов на все ранее поданные входные сигналы. Оракул проверяет и их корректность тоже. Если он обнаруживает ошибку, тест завершается с выдачей сообщения о найденной ошибке. Если до того момента, когда больше не остается не выданных результатов, тестируемая модель работает корректно, тест завершается с сообщением об успешном окончании.
Генератор тестовой последовательности создается на основе сценария, описывающего набор различных способов обращения к модели.
Оракул генерируется с помощью транслятора моделей требований из спецификации (описания модели) требований к тестируемому компоненту.
До последнего времени оставалась нерешенной проблема автоматической генерации тестов, использующих параллельные обращения к тестируемому компоненту или проверяющих корректность выполнения последовательностей инструкций в конвейерных микропроцессорах. В процессорах конвейерной архитектуры выполнение каждой инструкции разлагается на выполнение нескольких микроопераций (стадий выполнения этой инструкции) и происходит «перемешивание» микроопераций: микрооперации различных инструкций могут выполняться разными модулями одновременно или даже в порядке, обратном порядку соответствующих инструкций. При этом проверка правильности работы каждой инструкции значительно усложняется и не может напрямую использовать те же свойства ее результатов, которые выполняются при отдельном выполнении этой инструкции.
Для процессоров конвейерной архитектуры и их модулей тесты, использующие возможности параллельного выполнения инструкций или выполнения цепочки инструкций с возможным «перемешиванием» их микроопераций на сегодняшний день, разрабатываются только вручную, поскольку общих техник построения автоматизированного оракула для таких тестов не существует.
Решаемая техническая задача
Техническая задача состояла в создании группы изобретений, позволяющих осуществлять построение автоматизированного тестового оракула для проверки правильности моделей компонентов микропроцессоров конвейерной архитектуры, а также проверки правильности работы самих компонентов микропроцессоров и создании на его основе способа тестирования моделей микропроцессоров конвейерной архитектуры и их модулей. Причем этот способ должен обеспечивать применение тестов, использующих возможности параллельного выполнения инструкций или выполнения цепочки инструкций с возможным «перемешиванием» их микроопераций.
Сущность изобретения
Сущность предлагаемого способа тестирования компонентов микропроцессоров, входящего в группу изобретений, решающих техническую задачу, в том, что тестирование организуют в виде последовательности тактов работы тестируемого компонента, при этом в начале каждого такта с помощью генератора тестовой последовательности создают очередное обращение к тестируемому компоненту и передают все входящие в это обращение сигналы тестируемому компоненту и оракулу, в конце каждого такта оракулу передают все выходные сигналы тестируемого компонента, и производят оценку их корректности в качестве ответов на все поступившие до этого момента входные сигналы, если оракул обнаруживает ошибку в виде несоответствия полученных результатов требованиям к тестируемому компоненту, то тест завершают и выдают сообщение о найденной ошибке, если оракул ошибок не обнаруживает, то продолжают тестирование, по окончании тестовой последовательности с помощью генератора тестовой последовательности создают нулевые входные сигналы столько раз, сколько тестируемому компоненту требуется для выдачи ответов на все ранее поданные входные сигналы, при этом с помощью оракула проверяют их корректность, если оракул обнаружит ошибку, то тест завершают и выдают сообщение о найденной ошибке, если оракул за все время тестирования не обнаружит ошибку, то после получения ответов на все ранее поданные входные сигналы делают вывод о корректной работе тестируемого компонента, тест завершают и сообщают об успешном завершении тестирования, при этом генератор тестовой последовательности строят из сценария, описывающего набор различных способов обращения к тестируемому компоненту, а оракул с помощью транслятора модели требований генерируют из спецификации требований к тестируемому компоненту и вспомогательных библиотечных функций сдвига конвейера и проверки стадий.
Причем компонентом микропроцессора может быть как сам микропроцессор, так и модуль микропроцессора, а также модель микропроцессора или модель модуля микропроцессора.
Причем компонентом микропроцессора может быть модель микропроцессора или модель модуля микропроцессора, работающие в рамках симулятора языка моделирования, на котором они написаны.
Причем компонентом микропроцессора может быть микропроцессор конвейерной архитектуры или модуль микропроцессора конвейерной архитектуры.
Сущность предлагаемого тестового оракула, входящего в группу изобретений, решающих техническую задачу, в том, что он состоит из модели требований к тестируемому компоненту, включающей описание интерфейса тестируемого компонента, описание внутренних данных тестируемого компонента и описание ограничений на поведение тестируемого компонента, извлеченных из требований к нему, состоящее из перечня ограничений целостности данных, перечня предусловий операций, перечня условий блокировки отдельных стадий, перечня постусловий отдельных стадий, и модели конвейера тестируемого компонента, включающей модель данных конвейера, функцию сдвига конвейера и функцию проверки корректности стадий.
Причем компонентом микропроцессора может быть как сам микропроцессор, так и модуль микропроцессора.
Причем компонентом микропроцессора может быть модель микропроцессора или модель модуля микропроцессора, работающие в рамках симулятора языка моделирования, на котором они написаны.
Причем описание интерфейса тестируемого компонента может состоять из списка функций на одном из языков программирования или языков моделирования, причем для каждой функции определены ее имя, число, имена и типы параметров, тип результата и список стадий, причем стадии также представлены в виде функций без параметров на том же языке программирования или моделирования.
Причем описание внутренних данных тестируемого компонента может представлять собой список глобальных переменных или полей классов на одном из языков программирования или языков моделирования, причем для каждой переменной или поля определены ее имя и тип.
Причем каждое ограничение целостности данных тестируемого компонента может представлять собой функцию на одном из языков программирования или языков моделирования, для которой определено имя, число, имена и типы параметров, в качестве типа возвращаемого значения используется булевский тип.
Причем каждое предусловие операции тестируемого компонента может представлять собой функцию на одном из языков программирования или языков моделирования, для которой число, имена и типы параметров совпадают с числом, именами и типами параметров функции, представляющей соответствующую операцию, а в качестве типа возвращаемого значения используется булевский тип.
Причем каждое условие блокировки стадии операции тестируемого компонента может представлять собой функцию на одном из языков программирования или языков моделирования, без параметров, имеющую в качестве типа возвращаемого значения булевский тип.
Причем каждое постусловие стадии операции тестируемого компонента может представлять собой функцию на одном из языков программирования или языков моделирования, без параметров, имеющую в качестве типа возвращаемого значения булевский тип.
Причем компонентом микропроцессора может являться микропроцессор конвейерной архитектуры или модуль микропроцессора конвейерной архитектуры.
Сущность предлагаемого способа работы тестового оракула, входящего в группу изобретений, решающих техническую задачу, состоящего из модели требований к тестируемому компоненту, включающей описание интерфейса тестируемого компонента, описание внутренних данных тестируемого компонента и описание ограничений на поведение тестируемого компонента, и из модели конвейера тестируемого компонента, включающей модель данных конвейера, функцию сдвига конвейера и функцию проверки корректности стадий, в том, что в начале тестирования инициализируют внутренние данные тестируемого компонента, а модель данных конвейера полагают равной пустому множеству, затем в начале каждого такта работы тестируемого компонента функции сдвига конвейера передают созданный генератором тестовой последовательности набор операций, которые нужно вызвать на данном такте, с помощью функции сдвига конвейера удаляют из модели данных конвейера уже выполненные стадии операций, добавляют следующие стадии для тех из выполняемых операций, для которых такие имеются, а также добавляют первые стадии операций, полученных от генератора тестовой последовательности, если получаемая при этом модель данных конвейера не пуста, передают управление функции проверки корректности стадий, в противном случае завершают работу оракула с сообщением об успешном завершении теста, в конце каждого такта работы тестируемого компонента передают функции проверки корректности стадий результаты работы тестируемого компонента на данном такте, с помощью функции проверки корректности стадий проверяют условия целостности данных, условия блокировки стадий, находящихся в модели данных конвейера, и для тех из них, для которых условия блокировки не выполнены, проверяют постусловия, если одно из условий целостности данных или постусловий не выполняется, завершают работу оракула с сообщением о найденной ошибке в работе тестируемого компонента, в противном случае все стадии, для которых выполняются их постусловия, помечают как выполненные на данном такте, и передают управление функции сдвига конвейера.
Причем компонентом микропроцессора может являться микропроцессор или модуль микропроцессора.
Причем компонентом микропроцессора может являться модель микропроцессора или модель модуля микропроцессора, работающая в рамках симулятора языка моделирования, на котором она написана.
Причем компонентом микропроцессора может являться микропроцессор конвейерной архитектуры или модуль микропроцессора конвейерной архитектуры.
Сущность предлагаемого способа построения тестового оракула, входящего в группу изобретений, решающих техническую задачу, состоящего из модели требований к тестируемому компоненту, включающей описание интерфейса тестируемого компонента, описание внутренних данных тестируемого компонента и описание ограничений на поведение тестируемого компонента, и из модели конвейера тестируемого компонента, включающей модель данных конвейера, функцию сдвига конвейера и функцию проверки корректности стадий, в том, что модель требований получают из требований, обусловленных функциональным назначением компонента микропроцессора, в ходе преобразования в формальные интерфейсные контракты в форме описаний требований к поведению тестируемого компонента на расширении одного из языков программирования или моделирования аппаратного обеспечения, при этом операции тестируемого компонента и стадии этих операций оформляют как функции этого языка, помеченные ключевым словом расширения, позволяющим отличить их от всех остальных функций, а ограничения целостности внутренних данных, предусловия операций, условия блокировки и постусловия стадий оформляют как блоки инструкций, возвращающих булевский результат, помеченные ключевыми словами расширения, выделяющими, соответственно, ограничения целостности, предусловия операций, условия блокировки и постусловия стадий; затем эти формальные спецификации с помощью транслятора моделей преобразуют в модель требований на самом языке программирования или моделирования, при этом все ключевые слова расширения удаляют, каждое отдельное ограничение целостности внутренних данных, предусловие операции, условие блокировки или постусловие стадии преобразуют в функцию, имеющую в качестве тела тот блок инструкций, с помощью которого это ограничение целостности внутренних данных, предусловие операции, условие блокировки или постусловие стадии описано в спецификациях, кроме того, с помощью транслятора моделей на основе списка описанных в спецификациях операций и их стадий и типов данных вспомогательной библиотеки генерируют модель данных конвейера, как тип данных, способный хранить множество выполняемых на данном такте стадий операций, и добавляют к полученным элементам функции сдвига конвейера и проверки корректности стадий из вспомогательной библиотеки.
Причем компонентом микропроцессора может являться микропроцессор или модуль микропроцессора.
Причем компонентом микропроцессора может являться модель микропроцессора или модель модуля микропроцессора, работающая в рамках симулятора языка моделирования, на котором она написана.
Причем компонентом микропроцессора может являться микропроцессор конвейерной архитектуры или модуль микропроцессора конвейерной архитектуры.
Технический результат от использования изобретений состоит в том, что способ тестирования компонентов микропроцессоров, тестовый оракул для тестирования компонентов микропроцессоров, способ работы тестового оракула и способ построения тестового оракула позволяют построение автоматизированного тестового оракула для проверки правильности моделей компонентов микропроцессоров конвейерной архитектуры, и позволили создать на его основе сам тестовый оракул и способ тестирования микропроцессоров конвейерной архитектуры, их модулей и их моделей. Причем созданные способы и устройства работают с применением тестеров, использующих возможности параллельного выполнения инструкций или выполнения цепочки инструкций с возможным «перемешиванием» их микроопераций.
Ниже описывается способ построения тестового оракула для проверки правильности моделей компонентов конвейерной архитектуры. Построенный таким способом оракул работоспособен при произвольном сценарии подачи инструкций на входы модели.
Предлагаемый способ построения оракулов позволяет автоматизировать процесс создания и выполнения имитационных тестов моделей микропроцессоров конвейерной архитектуры и их модулей на основе моделей требований в гораздо более общей ситуации, чем это возможно на сегодняшний день.
Предлагаемые изобретения и их работа поясняются графическими материалами, представленными на Фиг.1-5.
На Фиг.1 представлена общая схема тестирования компонентов микропроцессоров конвейерной архитектуры, где 1 - генератор тестовой последовательности, 2 - тестируемый компонент, 3 - тестовый оракул, 4 - модель требований к тестовому оракулу, 5 - модель конвейера тестируемого компонента, 6 - тестовый отчет.
На Фиг.2 представлена схема предлагаемого устройства тестового оракула 3, где 4 - модель требований к тестируемому компоненту, 5 - модель конвейера тестируемого компонента, 7 - описание структуры интерфейса, 8 - модель внутренних данных, 9 - ограничения, 10 - ограничения целостности данных, 11 - предусловия операций, 12 - условия блокировки стадий, 13 - постусловия стадий, 14 - модель данных конвейера, 15 - функция сдвига конвейера, 16 - функция проверки стадий.
На Фиг.3 представлены первые два такта работы оракула 3 по описанному способу.
На Фиг.4 представлена схема предлагаемого способа построения тестового оракула, где 17 - формальная спецификация требований к тестируемому компоненту на расширении языка программирования или моделирования аппаратного обеспечения, 18 - вспомогательная библиотека, 19 - транслятор моделей требований.
На Фиг.5 представлена временная диаграмма сигналов сумматора.
Предлагаемые изобретения и их работа описаны в нижеприведенных материалах.
- Способ тестирования компонентов микропроцессоров
Тестирование компонентов микропроцессоров, в том числе конвейерной архитектуры, устроено практически так же, как и традиционное тестирование на основе моделей, за одним исключением - используется тестовый оракул, построенный особым, описываемым ниже способом.
- Тестовый оракул для тестирования компонентов микропроцессоров
Устройство тестового оракула определяет набор элементов, из которых состоит оракул, и связи между ними.
- Способ работы тестового оракула
Этот способ определяет алгоритм работы элементов оракула, задаваемых его описываемым устройством. Данный алгоритм обеспечивает выполнение основной функции оракула - сопоставление получаемых в ходе теста результатов работы тестируемого компонента с требованиями к нему и вынесение вердикта об их соответствии или несоответствии.
- Способ построения тестового оракула
Этот способ позволяет строить оракулы, имеющие описываемое устройство, из минимально необходимой исходной информации. Часть элементов оракула при этом генерируется из формальных спецификаций, описывающих требования к тестируемому компоненту, другая часть строится на основе библиотечных элементов.
Предлагаемое решение может быть использовано для тестирования микропроцессоров и модулей микропроцессоров конвейерной архитектуры - арифметических и логических устройств, буферов трансляции адресов, модулей управления работой с кэшами и памятью, блоков вычислений с плавающей точкой и т.д.
Общая схема тестирования компонентов микропроцессоров конвейерной архитектуры (представлена на Фиг.1)
Предлагаемая схема тестирования построена на основе общеупотребительной схемы (описанной, например, в работах: В.П.Иванников, А.С.Камкин, В.В.Кулямин, А.К.Петренко. Применение технологии UniTesK для функционального тестирования моделей аппаратного обеспечения. Препринт 8 ИСП РАН, Москва 2005; I.Bourdonov, A.Kossatchev, V.Kuliamin, and A.Petrenko. UniTesK Test Suite Architecture. In Proc. of FME 2002. LNCS 2391, pp.77-88, Springer-Verlag, 2002; В.В.Кулямин, А.К.Петренко, А.С.Косачев, И.Б.Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003; С.Campbell, W.Grieskamp, L.Nachmanson, W.Schulte, N.Tillmann, M.Veanes. Model-Based Testing of Object-Oriented Reactive Systems with Spec Explorer. Microsoft Research Technical Report MSR-TR 2005-59) введением в нее тестового оракула, имеющего особое устройство.
При тестировании компонентов конвейерной архитектуры используются следующие модули.
- Тестируемый компонент
Тестируемый компонент 2 представляет собой модель микропроцессора или модуля микропроцессора конвейерной архитектуры. При тестировании он работает в рамках симулятора.
В ходе теста проверяется, что тестируемый компонент работает в соответствии с зафиксированными требованиями к его поведению. Для этого на все входы тестируемого компонента в начале каждого такта подаются некоторые сигналы, а в конце каждого такта его выходные сигналы считываются с выходов.
- Генератор тестовой последовательности
Генератор тестовой последовательности 1 создает последовательность входных сигналов, на которой проверяется поведение тестируемого компонента 2. Он же отвечает за симуляцию работы генератора тактовой частоты, генерируя и подавая на соответствующий вход тестируемого компонента 2 периодически изменяющийся сигнал.
В начале каждого такта генератор тестовой последовательности 1 передает очередной набор входных сигналов на входы тестируемого компонента 2 и на входы тестового оракула 3.
Генератор тестовой последовательности 3 разрабатывается таким образом, чтобы он реализовывал возможные сценарии работы тестируемого компонента. Различные способы построения генераторов тестовой последовательности описаны в работах: В.П.Иванников, А.С.Камкин, В.В.Кулямин, А.К.Петренко. Применение технологии UniTesK для функционального тестирования моделей аппаратного обеспечения. Препринт 8 ИСП РАН, Москва 2005; I.Bourdonov, A.Kossatchev, V.Kuliamin, and A.Petrenko. UniTesK Test Suite Architecture. In Proc. of FME 2002. LNCS 2391, pp.77-88, Springer-Verlag, 2002; В.В.Кулямин, А.К.Петренко, А.С.Косачев, И.Б.Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003; С.Campbell, W.Grieskamp, L.Nachmanson, W.Schulte, N.Tillmann, M.Veanes. Model-Based Testing of Object-Oriented Reactive Systems with Spec Explorer. Microsoft Research Technical Report MSR-TR 2005-59.
- Тестовый оракул
Тестовый оракул 3 оценивает соответствие поведения тестируемого компонента 2 в ходе теста требованиям к нему и выносит вердикт о их соответствии или несоответствии. Входные сигналы, получаемые тестируемым компонентом 2 в начале такта, выходные сигналы, выдаваемые им в конце такта, а также свой вердикт об их корректности оракул записывает в тестовый отчет 6. Тестовый оракул 3 в начале каждого такта принимает входные сигналы, создаваемые генератором тестовой последовательности 1, в конце каждого такта он принимает выходные сигналы тестируемого компонента 2, анализирует их корректность, после чего записывает входные сигналы, выходные сигналы и вердикт об их корректности в тестовый отчет 6.
Если оракул 3 обнаруживает некорректные результаты работы тестируемого компонента 2, он, помимо записи в отчет, сигнализирует об этом и генератору тестовой последовательности 1, чтобы остановить тестирование. Тестовый оракул 2 для тестирования компонентов конвейерной архитектуры строится особым, описываемым ниже способом и состоит из модели требований к тестируемому компоненту 4 и модели конвейера тестируемого компонента 5.
- Тестовый отчет
Тестовый отчет 6 представляет собой запись событий, происходивших во время тестирования (передаваемых тестируемому компоненту 2 входных сигналов, получаемых от него выходных сигналов), и результатов проверки их корректности оракулом 3. Он используется для анализа результатов тестирования и обнаруженных в ходе теста ошибок. Запись в тестовый отчет 6 выполняется тестовым оракулом 3.
Устройство тестового оракула (представлено на Фиг.2)
Предлагается строить тестовый оракул 3 для компонентов конвейерной архитектуры из двух основных элементов - модели требований к тестируемому компоненту 4 и модели конвейера тестируемого компонента 5.
- Модель требований к тестируемому компоненту
Этот элемент содержит набор ограничений, проверка которых позволяет оракулу 3 установить выполнение или нарушение требований к поведению тестируемого компонента на тех результатах его работы, которые получаются в ходе теста. Модель требований 4 состоит из следующих частей.
- Описание структуры интерфейса 7 тестируемого компонента 2
Такое описание представляет собой определение входов и выходов тестируемого компонента 2. Возможные входные сигналы разделяются на операции и их аргументы.
Для каждой операции определяется список стадий, на которые разбивается ее выполнение тестируемым компонентом. Для каждой стадии определяются выходы тестируемого компонента, которые могут быть получены в результате ее выполнения.
- Описание модели внутренних данных 8 тестируемого компонента 2
Это описание определяет элементы внутренних данных компонента, необходимые для оценки выполнения требований к его поведению. Такие данные представляют собой состояние компонента, влияющее на выполнение им операций, и, в свою очередь, изменяемое ими. Для каждого элемента внутренних данных определяется тип этих данных и имя этого элемента.
- Описание ограничений 9 на поведение тестируемого компонента 2.
Ограничения представляют собой основное содержание требований.
Ограничения бывают четырех видов.
- Ограничения целостности данных 10
Эти ограничения определяют условия, при которых внутренние данные тестируемого компонента 2 могут рассматриваться как корректные. Их нарушение означает, что в ходе работы требования к поведению тестируемого компонента 2 были нарушены, но это нарушение можно проследить только на некоторой последовательности операций, результаты каждой из которых в отдельности выглядят правильными.
- Предусловия операций 11
Эти ограничения определяют аргументы операций, с которыми она может быть вызвана. Нарушение предусловия 11 означает попытку неправильного использования тестируемого компонента 2 и является ошибкой теста.
- Условия блокировки отдельных стадий 12
Эти ограничения определяют ситуации (значения внутренних данных и состояние конвейера), в которых соответствующая стадия не может быть выполнена. Однако выполнение условия блокировки означает не ошибку, а необходимость отложить выполнение данной стадии на последующие такты. Стадия остается невыполненной до тех пор, пока условие блокировки не нарушится на некотором такте, на этом же такте эта стадия будет выполнена.
- Постусловия отдельных стадий 13
Эти ограничения определяют правила проверки результатов отдельных стадий и правила изменения внутренних данных конвейера. Нарушение постусловия означает несоответствие между поведением тестируемого компонента и требованиями к нему, то есть ошибку в поведении компонента.
- Модель конвейера тестируемого компонента 5
Этот элемент позволяет проследить взаимосвязи и взаимовлияния между различными операциями, выполняемыми тестируемым компонентом 2, и проверить корректность выполнения каждой из них в любой комбинации, которую она может составить с другими операциями при параллельном и последовательном их вызове. Модель конвейера 5 состоит из следующих частей.
- Модель данных конвейера 14
Это описание состояния конвейера. Каждое состояние представляет собой множество стадий операций, выполняемых на данном такте. Операции, не вызывавшиеся до текущего такта, или те, выполнение которых уже завершилось, никак не участвуют в состоянии конвейера. Состояние конвейера изменяется в ходе тестирования с помощью функции сдвига конвейера 15.
- Функция сдвига конвейера 15
Эта функция отвечает за изменение состояния конвейера 15 при переходе от одного такта к следующему. В начале каждого такта она помещает в состояние конвейера первые стадии всех вызванных на этом такте операций, увеличивает на единицу номера выполняемых стадий всех незаконченных операций, у которых не выполнены условия блокировок, а законченные операции удаляет из состояния конвейера.
- Функция проверки корректности стадий 16
Эта функция отвечает за проверку корректности выполнения всех стадий. На каждом такте она проверяет условия блокировок всех текущих стадий выполнения операций и для каждой стадии, условие блокировки которой не выполнено, проверяет ее постусловие. Перед проверкой постусловий проверяются также все ограничения целостности внутренних данных тестируемого компонента.
Способ работы тестового оракула
Предлагаемый способ работы тестового оракула выглядит следующим образом. (На Фиг.3 показаны первые два такта работы оракула по описанному способу.)
Перед началом тестирования инициализируются внутренние данные, модель данных конвейера инициализируется пустым множеством.
В процессе тестирования на каждом такте производятся следующие действия.
- Функция сдвига конвейера 15 получает от генератора тестовой последовательности 1 набор операций, которые нужно вызвать на данном такте. Этот набор может быть пустым (пустая операция).
- Для каждой выполненной стадии в состоянии конвейера функция сдвига конвейера 15 удаляет ее из состояния конвейера и помещает туда следующую стадию той же операции, если таковая есть.
- Для каждой вызванной на данном такте операции функция сдвига конвейера 15 добавляет в состояние конвейера первую стадию этой операции.
- Если полученное состояние конвейера не пусто (есть хотя бы одна выполняемая стадия), функция сдвига конвейера 15 передает управление функции проверки корректности стадий 16. Иначе, работа оракула 3 заканчивается и генератору тестовой последовательности 1 передается сообщение о нормальном завершении работы теста.
- Функция проверки корректности стадий 16 получает от тестируемого компонента 2 результаты его работы на данном такте.
- Для каждой из стадий в текущем состоянии конвейера проверяется ее условие блокировки 12.
Если оно выполнено, стадия помечается как отложенная.
Иначе, стадия помечается как выполненная.
- Проверяются ограничения целостности внутренних данных 10 и результатов работы тестируемого компонента 2.
Если хотя бы одно из этих ограничений нарушено, выносится вердикт о некорректном, несоответствующем требованиям поведении тестируемого компонента 4, запись об этом заносится в тестовый отчет 6 и сообщение об ошибке передается генератору тестовой последовательности 1 для остановки работы теста. Иначе работа продолжается.
- Для каждой выполненной стадии в состоянии конвейера проверяется ее постусловие 13, в проверке которого используются полученные от тестируемого компонента результаты.
Если хотя бы одно из проверяемых постусловий нарушено, выносится вердикт о некорректном, несоответствующем требованиям поведении тестируемого компонента 2, запись об этом заносится в тестовый отчет 6 и сообщение об ошибке передается генератору тестовой последовательности 1 для остановки работы теста.
Иначе работа продолжается.
- Функция проверки корректности стадий 16 передает управление функции сдвига конвейера 15.
В конце тестирования, после того, как тестовая последовательность заканчивается, генератор тестовой последовательности 1 подает на выполнение последовательность пустых операций, пока оракул 3 не выдаст ему сообщение о нормальном завершении работы теста или об ошибке.
Способ построения тестового оракула
Процедура генерации тестового оракула описана ниже и выполняется специальным инструментом - транслятором моделей требований 19. Общая схема его работы представлена на Фиг.4. Общие правила работы такого транслятора описаны в работе В.В.Кулямин, А.К.Петренко, А.С.Косачев, И.Б.Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003.
При построении тестового оракула 3, имеющего описанное выше устройство (Фиг.2), для уменьшения количества выполняемой вручную работы предлагается создавать вручную только модель требований к тестируемому компоненту 4. Модель конвейера тестируемого компонента 5 может быть сгенерирована автоматически из модели требований 4 и вспомогательных библиотечных компонентов, задающих общий вид модели данных конвейера 14, а также работу функций сдвига конвейера 15 и проверки корректности стадий 16.
Модель требований к тестируемому компоненту 4 создается аналитиком требований по методике FOREST (описанной в работе: В.В.Кулямин, Н.В.Пакулин, О.Л.Петренко, А.А.Сортов, А.В.Хорошилов. Формализация требований на практике. Препринт 13 ИСП РАН, Москва, 2006), в виде формальных спецификаций на расширении одного из языков программирования 17 (например, С, Java, Pascal) или моделирования аппаратного обеспечения (например, Verilog, VHDL, SystemC), содержащих те же элементы, что и модель требований в описанном выше устройстве оракула. Добавляемые в такое расширение конструкции служат для выделения этих элементов.
- Описание интерфейса 7 тестируемого компонента
Представляет собой определение входов и выходов тестируемого компонента. Возможные входные сигналы разделяются на операции и их аргументы. Для каждой операции определяется ее имя, имена и типы ее параметров, список стадий, на которые разбивается ее выполнение тестируемым компонентом. Для каждой стадии определяются ее имя, имена и типы выходов тестируемого компонента, которые могут быть получены в результате ее выполнения.
- Описание внутренних данных 8 тестируемого компонента
Определяет элементы внутренних данных компонента, представляющих состояние компонента и необходимые для оценки выполнения требований к его поведению. Для каждого элемента внутренних данных определяется тип этих данных и имя этого элемента.
- Описание ограничений 9 на поведение тестируемого компонента 2
- Ограничения целостности данных 10
Определяют условия, при которых внутренние данные тестируемого компонента могут рассматриваться как корректные.
- Предусловия операций 11
Определяют аргументы операций, с которыми она может быть вызвана.
- Условия блокировки отдельных стадий 12
Определяют условия, при которых соответствующая стадия не может быть выполнена на данном такте и должна быть отложена.
- Постусловия отдельных стадий 13
Определяют правила проверки результатов отдельных стадий и правила изменения внутренних данных конвейера.
При генерации оракула 3 формальные спецификации преобразуются в модель требований к тестируемому компоненту 4, являющуюся частью оракула. При этом они подвергаются минимальным преобразованиям - текст на расширении языка программирования или моделирования аппаратного обеспечения преобразуется в программу на самом этом языке при помощи удаления вспомогательных конструкций.
Кроме этого, при генерации оракула автоматически создается модель конвейера тестируемого компонента. Для ее создания на основе описания интерфейса тестируемого компонента и библиотечных типов генерируются типы данных для модели данных конвейера. Функции сдвига конвейера и проверки корректности стадий берутся из вспомогательной библиотеки 18.
Пример работы оракула - сумматор чисел с плавающей точкой
Описание работы сумматора чисел с плавающей точкой
Общее описание
Сумматор предназначен для сложения нормализованных и нулевых чисел с плавающей точкой, имеющих однократную точность и представленных в соответствии со стандартом IEEE 754 [IEEE 754-1985. IEEE Standard for Binary Floating-Point Arithmetic. NY: IEEE, 1985]. Результатом работы сумматора является нормализованное или нулевое число, полученное округлением суммы операндов в сторону нуля.
Согласно стандарту IEEE 754, числа с плавающей точкой, имеющие однократную точность, представляются в следующей форме.
знак
порядок
мантисса
1 бит [31]
8 бит [30:23]
23 бита [22:0]
Нуль представляется как число, порядок и мантисса которого равны нулю, а знаковый бит принимает произвольное значение: 0 или 1.
В нормализованных числах значение порядка изменяется в диапазоне [1,254], а мантисса и знаковый бит могут принимать произвольные значения.
ε-127
Пусть n=(sign, exponent, fraction) - представление нормализованного числа, имеющего однократную точность, тогда значение этого числа получается следующим образом: ν(n)=σ·2·µ, где:
- ε - число, двоичное представление которого равно exponent;
i
где fraction - значение i-го бита поля fraction, то есть µ - число, двоичное представление которого равно 1.fraction.
Интерфейс сумматора
Входы сумматора
- clk - тактовый импульс;
- add - сигнал подачи операции;
- ор1 [0:31] - первый операнд;
- ор2 [0:31] - второй операнд.
Выходы
- res [0:31] - результат операции;
- inexact_align - потеря точности при выравнивании порядков;
- inexact_norm - потеря точности при нормализации результата.
Выполнение операции
Временная диаграмма сигналов сумматора представлена на Фиг.5.
Фронты сигнала тактового импульса clk (под фронтом сигнала понимается изменение уровня сигнала с низкого на высокий) разбивают непрерывное время на дискретный набор интервалов, называемых тактами. Запуск операции и выполнение ее отдельных стадий синхронизируется с фронтами сигнала clk.
Подача операции на выполнение осуществляется путем установки высокого уровня сигнала на входе add, а также присваиванием значений операндов входам орl и ор2 сразу после возникновения фронта сигнала clk. Устанавливаемые значения должны продержаться на входах один такт до возникновения очередного фронта сигнала clk, после чего значения можно изменить.
Выполнение операции сложения состоит из трех стадий. Выполнение каждой стадии занимает ровно один такт. Результат каждой стадии формируется перед возникновением очередного фронта clk, сигнализирующего о начале следующего такта и, следовательно, следующей стадии выполнения операции. Результат каждого стадии держится на выходах по крайней мере один такт.
1. Выравнивание порядков
На первой стадии осуществляется выравнивание порядков: новый порядок операнда с меньшим значением порядка становится равен порядку второго операнда. При этом, чтобы компенсировать увеличение порядка операнда, его мантисса уменьшается в соответствующее число раз. Для этого мантисса сдвигается вправо на число позиций, равное разности порядков, после этого, поскольку в мантиссе хранится только дробная часть, на место первого нулевого бита записывается единица.
2. Сложение мантисс
На второй стадии осуществляется сложение мантисс с учетом знаков операндов. На этой стадии определяется знак результата и предварительное значение мантиссы результата. Отметим, что при сложении мантисс операндов возможно переполнение. В этом случае результат должен быть нормализован.
3. Нормализация результата
Нормализация результата осуществляется на третьей стадии. Если при сложении мантисс было переполнение, то мантиссу результата нужно сдвинуть на один разряд вправо и увеличить на единицу значение порядка. Однако это можно сделать, только если значение порядка отлично от максимального значения 254. В последнем случае, результирующей мантиссе присваивается максимальное значение 8388607 (все 23 бита равны единице), а увеличение значения порядка не производится.
Данный пример является искусственным, он создан только с целью демонстрации всех основных элементов описываемой схемы тестирования, а также предлагаемых устройства тестового оракула, способов его построения и работы.
Требования к результатам работы сумматора
Общие требования
Операция сложения определена только для нормализованных или нулевых значений операндов ор1 и ор2.
Если значения обоих операндов ор1 и ор2 равны нулю, то значение результата выполнения операции res также равно нулю, при этом на соответствующих тактах сигналам inexact_align и inexact_norm присваиваются нулевые значения.
Если значение только одного операнда ор1 или ор2 равно нулю, то значение результата выполнения res операции равно значению ненулевого операнда, при этом на соответствующих тактах сигналам inexact_align и inexact_norm присваиваются нулевые значения.
Случай, когда значения обоих операндов ор1 и ор2 отличны от нуля, описан для каждой стадии в отдельности.
Выравнивание порядков
Если порядки операндов различны, то мантисса операнда с меньшим значением порядка сдвигается вправо на разницу порядков (shift), если при этом среди сдвигаемых бит мантиссы присутствует хотя бы одна единица, то сигналу inexact_align присваивается единица, иначе - нуль.
После сдвига мантиссы на позицию (23 - shift) ставится единица.
Сложение мантисс
Мантиссы операндов, полученные после выравнивания порядков, складываются с учетом знака, в результате чего получаются знак результата, предварительное значение мантиссы и бит переполнения. Наблюдаемый результат отсутствует.
Нормализация результата
Если при сложении мантисс было переполнение, тогда:
- Если значение порядка не равно максимальному значению 254, то:
- если младший бит предварительной мантиссы равен единице, то сигналу inexact_norm присваивается единица, иначе - нуль;
- осуществляется сдвиг мантиссы на один разряд вправо и порядок результата увеличивается на единицу.
- Иначе сигналу inexact_norm присваивается единица и результирующей мантиссе присваивается максимальное значение 8388607 (все 23 бита равны единице).
Если переполнения не происходит, никакие дополнительных действий не выполняются.
Построение тестового оракула для сумматора чисел с плавающей точкой
Спецификация требований к сумматору чисел с плавающей точкой
Описание интерфейса тестируемого компонента
Достаточно подробное описание интерфейса приведено выше. Тестируется ровно одна операция - сложение, состоящее из трех стадий.
Описание внутренних данных тестируемого компонента
В нашем примере модуль не имеет внутренних данных, которые описывали бы влияние различных вызовов операции друг на друга, поэтому внутренние данные сумматора представлены только выходами (result, inexact_align и inexact_norm).
// Спецификационное представление сумматора
specification typedef struct AdderUnitT
{
// Спецификационное представление выходов
SingleT result;
bool inexact_align;
bool inexact_norm;
} AdderUnitT;
Поле result, отвечающее за представление выхода res, имеет тип SingleT, который определяется следующим образом.
typedef uint32_t SingleT;
Для работы со значениями этого типа определены следующие функции.
// Функция проверки, является ли число нормализованным
bool isNormalized_SingleT (SingleT sf);
// Функция проверки, является ли число нулевым
bool isZero_SingleT (SingleT sf);
Описание ограничений на поведение тестируемого компонента
Ограничения целостности данных
В нашем примере таких ограничений нет.
Предусловия операций
Для нашего примера предусловие операции выглядит следующим образом:
specification void ADD_spec (SingleT op1, SingleT op2)
{
pre
{
return (isZero_SingleT (op1)||
isNormalized_SingleT (op1))
&& (isZero_SingleT (op2)||
isNormalized_SingleT (op2));
}
…
}
Условия блокировки отдельных стадий
В рассматриваемом примере отдельные стадии могут выполняться в любых комбинациях, поэтому условия их блокировки отсутствуют.
Постусловия отдельных стадий
Постусловия определяются для каждой стадии в отдельности и описывают ограничения на результат стадии. Стадии выполнения операций специфицируются отдельно друг от друга.
reaction ADDOperationT* ADD_align_spec (void)
{
post {…}
}
reaction ADDOperationT* ADD_add_spec (void)
{
post {…}
}
reaction ADDOperationT* ADD_norm_spec (void)
{
post {…}
}
Рассмотрим спецификацию следующего требования.
Если порядки операндов различны, то мантисса операнда с меньшим значением порядка сдвигается вправо на разницу порядков, если при этом среди сдвигаемых бит мантиссы присутствует хотя бы одна единица, то сигналу inexact_align присваивается единица, иначе - нуль.
// Спецификация стадий выравнивания порядков
reaction ADDOperationT* ADD_align_spec (void)
{
AdderUnitT*adder_unit=getAdderUnit ();
ADDOperationT *add=ADD_align_spec;
post
{
…
// Спецификация требования
if (add->op1_exponent>add->op2_exponent)
{
int shift=add->op1_exponent - add->op2_exponent);
return adder_unit->inexact_align==
(add->op2_fraction & mask(shift)) !=0;
}
if (add->op1_exponent<add->op2_exponent)
{
int shift=add->op2_exponent-add->op1_exponent);
return adder_unit->inexact_align==
(add->op1_fraction & mask(shift)) !=0;
}
…
}
}
Модель конвейера тестируемого компонента
Модель конвейера тестируемого компонента строится на основе модели требований к нему и библиотечных компонентов. Для облегчения понимания ее структуры и работы ее элементов в данном примере они описаны в адаптированном виде, привязанном к структуре тестируемого компонента.
Модель данных конвейера
Модель данных конвейера задается списком текущих стадий операций. В структурный тип AdderUnitT для представления модели данных конвейера добавляется поле pipe.
// Модель данных конвейера
List*pipe;
…
В данном примере модель данных конвейера является списком элементов следующего типа.
specification typedef struct ExecutionT
{
Object *operation;
ADDStageT stage;
} ExecutionT;
Поле operation содержит дескриптор операции (его структура описывается ниже), поле stage - стадию выполнения операции.
typedef enum ADDStageT
{
STAGE_ALIGN=0,
STAGE_ADD=1,
STAGE_NORM=2
} ADDStageT;
Дескриптор операции содержит информацию о ходе выполнения операции: значения ее аргументов, результат операции, а также промежуточные значения, которые используются для спецификации требований. Например, в приведенных выше требованиях для стадии нормализации результата используется такой промежуточный результат, как переполнение, возникающее при сложении мантисс, поэтому в дескриптор операции сложения нужно включить соответствующее поле.
// Дескриптор операции сложения
specification typedef struct ADDOperationT
{
// Первый операнд операции
uint32_t op1_sign;
uint32_t op1_exponent;
uint32_t op1_mantissa;
// Второй операнд операции
uint32_t op2_sign;
uint32_t op2_exponent;
uint32_t op2_fraction;
// Результат операции
uint32_t res_sign;
uint32_t res_exponent;
uint32_t res_fraction;
bool inexact_align;
bool inexact_norm;
// Бит переполнения при сложении мантисс
bool overflow;
} ADDOperationT;
Функция сдвига конвейера
Функция сдвига конвейера предназначена для изменения состояния конвейера. В нашем примере она имеет следующий вид.
void shiftPipeline_AdderUnitT(AdderUnitT*adder_unit)
{
int i, size;
for (i=0; i<size_List (adder_unit->pipe); i++)
{
ExecutionT *execution=get_List(adder_unit->pipe, i);
if (execution->stage++==2)
{remove_List(adder_unit->pipe, i); }
}
}
Функция проверки корректности стадий
Функция проверки корректности стадий предназначена для определения стадий выполнения операций, выполняющихся в текущем такте. В нашем примере она имеет следующий вид.
void composeStages_AdderUnitT(AdderUnitT*adder_unit)
{
int i;
for (i=0; i<size_List (adder_unit->pipe);)
{
ExecutionT *execution=get_List(adder_unit->pipe, i);
switch (execution->stage)
{
case STAGE_ALIGN:
{
registerReaction
(
adder_unit->chid,
NULL,
ADD_align_spec,
execution->operation
);
break;
}
case STAGE_ADD:
{
registerReaction
(
adder_unit->chid,
NULL,
ADD_add_spec,
execution->operation
);
break;
}
case STAGE_NORM:
{
registerReaction
(
adder_unit->chid,
NULL,
ADD_norm_spec,
execution->operation
);
break;
}
}
}
}
Пример работы оракула
Рассмотрим работу оракула при подаче подряд 3-х операций сложения со следующими значениями операндов.
Операция
Операнд 1
Операнд 2
Операция 1
(0, 0, 0)
(0, 0, 0)
Операция 2
(0, 128, 0)
(0, 127, 1)
Операция 3
(0, 254, 4194304)
(0, 254, 4194304)
Спустя 1 такт после подачи первой операции
Выполнилась 1-я стадия 1-й операции, подалась на выполнение 2-я операция.
Операция 1
Стадия 1
Стадия 2
Стадия 3
Операция 2
Стадия 1
Стадия 2
Стадия 3
Операция 3
Стадия 1
Стадия 2
Стадия 3
Проверяются требования на 1-ю стадию для 1-й операции.
- Для 1-й операции оба операнда ор1 и ор2 равны нулю, поэтому проверяется, что значение сигнала inexact_align равно нулю.
Спустя 2 такта после подачи первой операции
Выполнилась 2-я стадия 1-й операции и 1-я стадия 2-й операции, подалась на выполнение 3-я операция.
Операция 1
Стадия 1
Стадия 2
Стадия 3
Операция 2
Стадия 1
Стадия 2
Стадия 3
Операция 3
Стадия 1
Стадия 2
Стадия 3
Проверяются требования на 2-ю стадию 1-й операции и на 1-ю стадию для 2-й операции (порядок осуществления проверок не важен).
- На 2-й стадии наблюдаемый результат отсутствует, поэтому соответствующая проверка для 1-й операции отсутствует.
- При выравнивании порядков операндов 2-й операции порядок ор2 увеличивается на единицу, поэтому мантисса должна быть сдвинута вправо на один разряд. Поскольку младший бит мантиссы ор2 равен 1, осуществляется проверка того, что inexact_align равен единице.
Теперь мантисса ор2 равна 4194304 (единица в 22-м разряде).
Спустя 3 такта после подачи первой операции
Выполнилась 3-я стадия 1-й операции, 2-я стадия 2-й операции и 1-я стадия 3-й операции.
Операция 1
Стадия 1
Стадия 2
Стадия 3
Операция 2
Стадия 1
Стадия 2
Стадия 3
Операция 3
Стадия 1
Стадия 2
Стадия 3
Проверяются требования на 3-ю стадию для 1-й операции, на 2-ю стадию для 2-й операции и на 1-ю стадию для 3-й операции (порядок осуществления проверок не важен):
- Для 1-й операции оба операнда ор1 и ор2 равны нулю, поэтому проверяется, что значение сигнала inexact_norm равно нулю и что значение res равно нулю.
- На 2-й стадии наблюдаемый результат отсутствует, поэтому соответствующая проверка для 2-й операции отсутствует.
23
Значение суммы мантисс равно (0+4194304) mod 2=4194304, переполнения нет.
- Порядки операндов 3-й операции совпадают, поэтому осуществляется проверка того, что inexact_align равен нулю.
Спустя 4 такта после подачи первой операции
Выполнилась 3-я стадия 2-й операции и 2-я стадия 3-й операции.
Операция 1
Стадия 1
Стадия 2
Стадия 3
Операция 2
Стадия 1
Стадия 2
Стадия 3
Операция 3
Стадия 1
Стадия 2
Стадия 3
Проверяются требования на 3-ю стадию для 2-й операции и на 2-ю стадию для 3-й операции (порядок осуществления проверок не важен).
- Поскольку для 2-й операции на 2-й стадии переполнения не было, нормализации результата на 3-й стадии не требуется, поэтому выполняется проверка того, что значение сигнала inexact_norm равно 0.
- На 2-й стадии наблюдаемый результат отсутствует, поэтому соответствующая проверка для 3-й операции отсутствует.
23
Значение суммы мантисс равно (4194304+4194304) mod 2=0, возникло переполнение.
Спустя 5 тактов после подачи первой операции
Выполнилась 3-я стадия 3-й операции.
Операция 1
Стадия 1
Стадия 2
Стадия 3
Операция 2
Стадия 1
Стадия 2
Стадия 3
Операция 3
Стадия 1
Стадия 2
Стадия 3
Проверяются требования на 3-ю стадию для 3-й операции:
- Поскольку на 2-й стадии 3-й операции возникло переполнение, необходима нормализация результата. Поскольку значение порядка равно 254, проверяется, что значение сигнала inexact_norm равно 1 и значение res равно (0, 254, 8388607).
Второй пример - буфер трансляции адресов
Описание работы буфера трансляции адресов
Общее описание
Буфер трансляции адресов (TLB, Translation Lookaside Buffer), входящий в состав большинства современных микропроцессоров, предназначен для кэширования таблицы страниц - таблицы операционной системы, хранящей соответствие между номерами виртуальных и физических страниц памяти. Использование такого буфера позволяет значительно увеличить скорость трансляции адресов. Буфер представляет собой ассоциативную память с фиксированным числом ячеек.
В общих словах трансляция виртуального адреса осуществляется следующим образом. Если буфер содержит ячейку с нужным номером виртуальной страницы, на определенном выходе модуля формируется соответствующий физический адрес - номер виртуальной страницы меняется на номер физической, а смещение остается прежним; в противном случае, на одном из выходов модуля устанавливается сигнал, говорящий о промахе в буфер.
Рассмотрим следующее упрощенное устройство буфера трансляции адресов. Память TLB состоит из 64 ячеек, которые составляют объединенный TLB (JTLB, Joint TLB). Кроме того, для повышения производительности модуль содержит два дополнительных буфера: TLB данных (DTLB, Data TLB) и TLB инструкций (ITLB, Instruction TLB). DTLB используется при трансляции адресов данных, ITLB - при трансляции адресов инструкций. Оба буфера содержат по 4 ячейки, их содержимое является подмножеством JTLB, а обновление происходит путем замещения дольше всего не использовавшейся ячейки (LRU, Last Recently Used). Разрядность адреса равна 32 битам, размер смещения равен 12 битам. Трансляцию адресов данных и инструкций можно осуществлять параллельно.
Трансляция адресов выполняется в две стадии.
- Трансляция адреса данных
- доступ к DTLB;
- доступ к JTLB.
- Трансляция адреса инструкции
- доступ к ITLB;
- доступ к JTLB.
Каждая стадия выполняется ровно один такт.
Интерфейс буфера трансляции адресов
Входы буфера трансляции адресов
- clk - тактовый импульс;
- d_req - сигнал подачи на выполнение операции трансляции адреса данных;
- d_va[0:31] - виртуальный адрес данных;
- i_req - сигнал подачи на выполнение операции трансляции адреса инструкций;
- i_va[0:31] - виртуальный адрес инструкции.
Выходы буфера трансляции адресов
- d_pa [0:31] - физический адрес данных;
- d_jtib_req - сигнал запроса к JTLB от операции трансляции адреса данных;
- i_pa [0:31] - физический адрес инструкции;
- i_jtlb_req - сигнал запроса к JTLB от операции трансляции адреса инструкции;
- j tlb_hit - сигнал попадания в JTLB.
Требования к результатам работы буфера трансляции адресов
Подача операций на выполнение
- Между двумя последовательными подачами на выполнение одноименных операций трансляции должна быть задержка, по крайней мере, в один такт.
- Разноименные операции трансляции можно подавать на выполнение с произвольными задержками между ними. В частности, их можно подавать одновременно.
Трансляция адреса данных
Стадия 1
- Если при трансляции адреса данных запись с соответствующим номером виртуальной страницы не содержится в DTLB, то сигналу d_jtlb_req присваивается значение 1, иначе - 0.
Стадия 2
- Осуществляется обновление содержимого DTLB по алгоритму LRU.
- Если запись с номером виртуальной страницы транслируемого адреса не содержится в JTLB, то сигналу jtlb_hit присваивается значение 0, иначе - 1.
- В случае попадания в JTLB (в частности, при попадании в DTLB) на выходе d_pa формируется физический адрес, соответвующий виртуальному адресу, установленному на входе d_va в момент подачи операции на выполнение (номер виртуальной страницы меняется на номер физической, смещение остается прежним).
Трансляция адреса инструкции
Стадия 1
- Если при трансляции адреса инструкции запись с соответствующим номером виртуальной страницы не содержится в ITLB, то сигналу i_jtlb_req присваивается значение 1, иначе - 0.
Стадия 2
- Осуществляется обновление содержимого ITLB по алгоритму LRU.
- Если запись с номером виртуальной страницы транслируемого адреса не содержится в JTLB, то сигналу jtib_hit присваивается значение 0, иначе - 1.
- В случае попадания в JTLB (в частности, при попадании в ITLB) на выходе i_pa формируется физический адрес, соответствующий виртуальному адресу, установленному на входе i_va в момент подачи операции на выполнение (номер виртуальной страницы меняется на номер физической, смещение остается прежним).
Ограничения на доступ к JTLB
- При одновременном обращении к JTLB при параллельном выполнении операции трансляции адреса данных и операции трансляции адреса инструкции приоритет отдается операции трансляции адреса данных, выполнение операции трансляции адреса инструкции приостанавливается на один такт.
Пример работы оракула
Для иллюстрации работы оракула рассмотрим следующий фрагмент заполнения буфера JTLB (значения представлены в шестнадцатеричном формате):
Номер виртуальной страницы
Номер физической страницы
1
11
2
12
Будем считать, что JTLB не содержит записи, номер виртуальной страницы которой равен 3. Также будем считать, что перед началом тестирования в буферах DTLB и ITLB нет ни одной записи.
Рассмотрим следующую тестовую последовательность (для наглядности в записи адресов номер страницы отделен от смещения точкой).
1. d_va=1.001||i_va=2.002 - операции 1 и 2 соответственно;
2. пауза в 1 такт;
3. d_va=1.002 - операция 3;
4. i_va=3.003 - операция 4;
Запись d_va=page.offset означает подачу на выполнение операции трансляции адреса данных с номером страницы page и смещением offset, запись i_va=page.offset - то же для операции трансляции адреса инструкции. Параллельные операции разделены символом ||.
Спустя 1 такт после начала тестирования
Выполнились 1-я стадия 1-й операции и 1-я стадия 2-й операции.
Операция 1
Стадия 1
Стадия 2
Операция 2
Стадия 1
Стадия 2
Операция 3
Стадия 1
Стадия 2
Операция 4
Стадия 1
Стадия 2
Проверяются требования на 1-ю стадию 1-й операции и 1-ю стадию 2-й операции (порядок осуществления проверок не важен):
- Номер виртуальной страницы для аргумента 1-й операции равен 1. Поскольку записи с таким номером в DTLB не содержится (буфер пуст), осуществляется проверка того, что значение сигнала d_jtlb_req равно 1.
- Номер виртуальной страницы для аргумента 2-й операции равен 2. Поскольку записи с таким номером в ITLB не содержится (буфер пуст), осуществляется проверка того, что значение сигнала i_jtlb_req равно 1.
Приоритет доступа к JTLB имеет 1-я операция, поскольку это операция трансляции адреса данных, выполнение 2-й операции блокируется на один такт.
Спустя 2 такта после начала тестирования
Выполнилась 2-я стадия 1-й операции, начала выполняться 2-я стадия 2-й операции, подана на выполнение 3-я операция.
Операция 1
Стадия 1
Стадия 2
Операция 2
Стадия 1
Стадия 2
Операция 3
Стадия 1
Стадия 2
Операция 4
Стадия 1
Стадия 2
Проверяются требования на 2-ю стадию 1-й операции (порядок осуществления проверок не важен):
- Запись с номером виртуальной страницы 1 содержится в JTLB (это запись (1, 11)), поэтому осуществляется проверка того, что значение сигнала jtlb_hit равно 1.
- Проверяется, что значение выхода d_pa равно 11.001.
В результате выполнения 2-й стадии 1-й операции в DTLB из JTLB была скопирована запись (1, 11).
Спустя 3 такта после начала тестирования
Выполнилась 2-я стадия 2-й операции и 1-я стадия 3-й операции, подалась на выполнение 4-я операция.
Операция 1
Стадия 1
Стадия 2
Операция 2
Стадия 1
Стадия 2
Операция 3
Стадия 1
Стадия 2
Операция 4
Стадия 1
Стадия 2
Проверяются требования на 2-ю стадию 2-й операции и 1-ю стадию 3-й операции (порядок осуществления проверок не важен):
- Запись с номером виртуальной страницы 2 содержится в JTLB (это запись (2, 12)), поэтому осуществляется проверка того, что значение сигнала jtlb_hit равно 1.
- Проверяется, что значение выхода i_pa равно 12.002.
- Номер виртуальной страницы для аргумента 3-й операции равен 1. Запись с таким номером содержится в DTLB (это запись (1, 11)), осуществляется проверка того, что значение сигнала d_jtlb_req равно 0.
В результате выполнения 2-й стадии 2-й операции в ITLB из JTLB была скопирована запись (2, 12).
Спустя 4 такта после начала тестирования
Выполнилась 2-я стадия 3-й операции и 1-я стадия 4-й операции.
Операция 1
Стадия 1
Стадия 2
Операция 2
Стадия 1
Стадия 2
Операция 3
Стадия 1
Стадия 2
Операция 4
Стадия 1
Стадия 2
Проверяются требования на 2-ю стадию 3-й операции и 1-ю стадию 4-й операции (порядок осуществления проверок не важен):
- Запись с номером виртуальной страницы 2 содержится в JTLB (это запись (2, 12)), поэтому осуществляется проверка того, что значение сигнала jtlb_hit равно 1.
- Проверяется, что значение выхода d_pa равно 11.001.
- Номер виртуальной страницы для аргумента 4-й операции равен 3. Поскольку записи с таким номером в ITLB не содержится (буфер содержит одну запись (2, 12)), осуществляется проверка того, что значение сигнала i_jtlb_req равно 1.
Спустя 5 тактов после начала тестирования
Выполнилась 2-я стадия 4-й операции.
Операция 1
Стадия 1
Стадия 2
Операция 2
Стадия 1
Стадия 2
Операция 3
Стадия 1
Стадия 2
Операция 4
Стадия 1
Стадия 2
Проверяются требования на 2-ю стадию 4-й операции:
- Запись с номером виртуальной страницы 3 не содержится в JTLB, поэтому осуществляется проверка того, что значение сигнала jtlb_hit равно 0.
Полученные результаты
Выше описаны четыре основных элемента изобретения.
- Способ тестирования компонентов микропроцессоров конвейерной архитектуры, использующий тестовый оракул, имеющий описанное устройство. В рамках этого способа генератор тестовой последовательности используется для генерации различных последовательностей входных сигналов, используемых для тестирования проверяемого компонента, а тестовый оракул - для проверки правильности выходных сигналов, генерируемых тестируемым компонентом в ходе тестирования.
- Устройство тестового оракула для компонентов микропроцессоров конвейерной архитектуры
Оракул, устроенный по предложенной схеме, состоит из следующих элементов.
- Модель требований к тестируемому компоненту
- Описание интерфейса тестируемого компонента, состоящее из списка операций, которые тестируемый компонент может выполнять, и разбиения каждой операции на конечный набор стадий;
- Описание внутренних данных тестируемого компонента, необходимое для оценки правильности его выходных сигналов;
- Описание ограничений на поведение тестируемого компонента;
- Ограничения целостности внутренних данных
- Предусловия операций, которые должны выполняться при их вызове, чтобы тестируемый компонент мог работать корректно;
- Условия блокировки отдельных стадий, которые определяют, когда выполнение данной стадии должно быть отложено;
- Постусловия отдельных стадий, определяющие корректность результатов работы соответствующей стадии;
- Модель конвейера тестируемого компонента
- Модель данных конвейера, состоящая из набора стадий вызванных ранее операций, выполняемых компонентов на данном такте;
- Функция сдвига конвейера, изменяющая состояние конвейера тестируемого компонента при переходе к следующему такту;
- Функция проверки корректности стадий, вызывающая проверку условий блокировок выполняемых стадий и постусловий тех стадий, которые не были заблокированы на данном такте;
- Способ работы тестового оракула для компонентов микропроцессоров конвейерной архитектуры, позволяющий автоматически оценивать правильность результатов работы таких компонентов при произвольной последовательности входных сигналов, в которой некоторые сигналы могут поступать на входы тестируемого компонента параллельно с другими, поступающими на другие его входы.
- Способ построения тестового оракула для компонентов микропроцессоров конвейерной архитектуры, позволяющий автоматически сгенерировать модель конвейера тестируемого компонента на основе описания модели требований к нему на расширении одного из языков программирования или моделирования аппаратного обеспечения.