Статическое моделирование временных характеристик работы СБИС с использованием вычислительных систем с общей памятью

• Автор: Князев, Николай Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 95 с. : ил.

Содержание
Статическое моделирование временных характеристик работы СБИС с
использованием вычислительных систем с общей памятью
Введение
Описание предметной области
Описание задачи статического временного моделирования работы СБИС
Обзор существующих методов поиска критических путей в задаче статического моделирования временных характеристик схем
Статический временной анализ ациклических схем
Статический временной анализ схем с циклами, триггер-граф
Фазовый сдвиг
Простейший алгоритм на триггер-графе
Корректировка задержек
Алгоритм распространения от триггеров
Сравнение алгоритмов на графах с циклами
Инкрементальные Алгоритмы
Упрощенный инкрементальный алгоритм
Точный инкрементальный алгоритм
Случай увеличения задержек
Случай уменьшения задержек
Общий случай
Сравнение инкрементальных алгоритмов
Подходы к параллелизации СВА
Параллелизация с использованием ранжирования
Выводы к обзору существующих методов поиска критических путей в задаче СВА
Г лава 1. Параллельный алгоритм построения критических путей в задаче моделирования временных характеристик СБИС
Математическая модель и основные понятия СВА
Параллельный алгоритм временного анализа на графе без циклов
Первый этап. Инициализация счетчиков
Второй этап. Расчет элементов
Расчет одного элемента
Корректность алгоритма
Оценка сложности предлагаемого алгоритма
Инкрементальный параллельный алгоритм временного анализа после единичного изменения
Алгоритм поиска критических путей и циклов для схем с последовательной логикой
Общий вид алгоритма
Обнаружение циклов
Пример работы алгоритма
Корректность алгоритма
Оценка сложности алгоритма
Глава 2. Программная реализация алгоритмов для систем с общей памятью
Описание существующих средств программирования для систем с общей памятью
Описание параллельной реализации предложенных алгоритмов
Глава 3. Эксперименты и теоретические пределы масштабируемости поиска критических путей в задаче статического временного анализа
Корректность полученных результатов
Эффективность работы планировщика заданий
Эффективность реализации алгоритма на различном числе потоков .
Граф работ
Максимальное ускорение для различных типов схем
Эффективность реализации алгоритма
Выводы
Заключение
Список литературы
Приложение

Описание используемых примитивов библиотеки Intel® Threading Building Blocks
Приложение

путь, и при этом событие евх1 произошло раньше. При этом ref(eexI) = ref(eomKpI), ref(eex2) = ref(eomKp2) Такой путь называется критическим циклом, если d(eex2) - d(ref(eomKp2)) > d(eiaJ) - d(ref(eomKpI)), стоит отметить, что критический цикля является замкнутым критическим путем.
В общем случае, результат СВА - это набор всех путей и их запасов. Число путей может экспоненциально зависеть от размера схемы, поэтому, как правило, рассматривают анализ «худшего случая» (worst-case analysis) [1] [5] , где в качестве результата выступает набор худших (критических) путей. Данный подход подробно описан в [16].
В качестве входных данных для СВА выступает набор событий на входах схемы. При распространении событий используется прореживание: в каждом узле схемы выбираются события с наихудшей (наибольшей или наименьшей, в зависимости от типа анализа) задержкой, и дальше по схеме распространяются только эти события.
При вычислении задержек внутри элемента в общем случае необходимо учитывать следующие характеристики.
1. Задержки событий на всех входах элемента.
2. Длительность фронтов переключений (время между началом и окончанием изменения уровня). Длительность фронта переключения входного события влияет на задержку внутри элемента и межсоединения. Стоит отметить, что, событие с «пологим» фронтом переключения и малой задержкой на выходе схемы может «накопить» задержку больше, чем событие с большей задержкой, но с «крутым» фронтом переключения [17]. Тем не менее, учитывать величину фронта переключения при прореживании сигнала невозможно без расчета путей всех входящих сигналов, что делает прореживание бессмысленным, а анализ слишком сложным.
3. Тип событий. Некоторые пути в элементе могут быть доступны только для событий определенного типа.
4. Различные параметры и условия работы схемы (температура,