Статическое моделирование временных характеристик работы СБИС с использованием вычислительных систем с общей памятью тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Князев, Николай Александрович

• Князев, Николай Александрович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Князев, Николай Александрович

Содержание

Статическое моделирование временных характеристик работы СБИС с

использованием вычислительных систем с общей памятью

Введение

Описание предметной области

Описание задачи статического временного моделирования работы СБИС

Обзор существующих методов поиска критических путей в задаче статического моделирования временных характеристик схем

Статический временной анализ ациклических схем

Статический временной анализ схем с циклами, триггер-граф

Фазовый сдвиг

Простейший алгоритм на триггер-графе

Корректировка задержек

Алгоритм распространения от триггеров

Сравнение алгоритмов на графах с циклами

Инкрементальные Алгоритмы

Упрощенный инкрементальный алгоритм

Точный инкрементальный алгоритм

Случай увеличения задержек

Случай уменьшения задержек

Общий случай

Сравнение инкрементальных алгоритмов

Подходы к параллелизации СВА

Параллелизация с использованием ранжирования

Выводы к обзору существующих методов поиска критических путей в задаче СВА

Глава 1. Параллельный алгоритм построения критических путей в задаче моделирования временных характеристик СБИС

Математическая модель и основные понятия СВА

Параллельный алгоритм временного анализа на графе без циклов

Первый этап. Инициализация счетчиков

Второй этап. Расчет элементов

Расчет одного элемента

Корректность алгоритма

Оценка сложности предлагаемого алгоритма

Инкрементальный параллельный алгоритм временного анализа после единичного изменения

Алгоритм поиска критических путей и циклов для схем с последовательной логикой

Общий вид алгоритма

Обнаружение циклов

Пример работы алгоритма

Корректность алгоритма

Оценка сложности алгоритма

Глава 2. Программная реализация алгоритмов для систем с общей памятью

Описание существующих средств программирования для систем с общей памятью

Описание параллельной реализации предложенных алгоритмов

Глава 3. Эксперименты и теоретические пределы масштабируемости поиска критических путей в задаче статического временного анализа

Корректность полученных результатов

Эффективность работы планировщика заданий

Эффективность реализации алгоритма на различном числе потоков

Граф работ

Максимальное ускорение для различных типов схем

Эффективность реализации алгоритма

Выводы

Заключение

Список литературы

Приложение 1

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

Приложение 2

Введение диссертации (часть автореферата) на тему «Статическое моделирование временных характеристик работы СБИС с использованием вычислительных систем с общей памятью»

Введение

Актуальность работы

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

Цели и задачи диссертационной работы

1. Разработка параллельного метода построения критических путей в задаче статического моделирования временных характеристик схемы для систем с общей памятью.

2. Анализ масштабируемости распространенных методов построения критических путей в задаче статического моделирования временных характеристик схемы для реальных промышленных схем.

3. Реализация разработанного метода в рамках системы автоматического проектирования и проведение экспериментов на реальных промышленных схемах.

Научная новизна

Научная новизна диссертационной работы состоит в новом подходе к параллелизации схем содержащих комбинационную логику. В диссертационной работе предложен параллельный метод для статического моделирования временных характеристик схем с последовательной логикой, позволяющий достичь ускорения до 14 раз на 16 потоках. В работе впервые проведена теоретическая оценка масштабируемости методов статического моделирования временных характеристик схем и получены верхние оценки масштабируемости метода для реальных схем на неограниченном числе потоков.

Практическая значимость

Результаты диссертационной работы были внедрены в экспериментальную систему автоматического проектирования, разрабатываемую в ЗАО «Интел А/О». Реализация метода была использована для оценки масштабируемости параллельных методов СВА на используемых в промышленности схемах.

Апробация работы

Результаты работы докладывались и обсуждались на следующих конференциях:

1. Международная конференция «Научный сервис в сети Интернет: экзафлопсное будущее», г. Новороссийск, 2011.

2. Международная конференция-школа «Современные проблемы прикладной математики и информатики», г. Дубна, 2012

3. Международная конференция «Микроэлектронные системы», г. Москва, 2012.

На международной конференции «Микроэлектронные системы», проводящийся раз в два года, работа была отмечена как лучшая по тематике «Методы систем автоматического проектирования».

Личный вклад автора

Автором был разработан и реализован предложенный в работе параллельный алгоритм, проведены эксперименты и анализ масштабируемости метода.

Достоверность представленных результатов

Достоверность представленных результатов подтверждается сравнением с применяемыми в промышленности алгоритмами и инструментами статического временного анализа. Следует отметить, что задачи создания полноценного промышленного инструмента статического временного анализа не ставилось, однако полученная точность сравнима с результатами используемых на практике при создании схем инструментов. Сравнение выполнялось на реальных, используемых в промышленности СБИС.

Объем и структура диссертации

Диссертация состоит из трех глав, Введения и Заключения.

7

Диссертация содержит 95 страниц, 35 рисунков. В Списке литературы присутствует 36 наименований.

В первой главе приведено подробное описание используемой модели, описывается предлагаемый подход к параллелизации методов, который сравнивается с существующими методами.

Во второй главе приводится описание реализации предложенных методов для систем с общей памятью. В главе приводится классификация вычислительных систем и обзор методов параллелизации алгоритмов. Рассматриваются характерные проблемы и распространенные методы, используемые в параллельном программировании для систем с общей памятью. В качестве технологии реализации используется библиотека Intel® Threading Building Blocks, которая предлагает подход, ориентированный на параллельное выполнение независимых задач.

В третьей главе приводятся результаты экспериментов и анализ масштабируемости предложенного метода. Реализация алгоритма была протестирована на ряде промышленных схем. В ходе анализа было проверено соответствие результатов, с полученными с помощью применяемых в промышленности инструментов СВА, определено ускорение, достигаемое на разном количестве потоков.

Результаты диссертационной работы изложены в следующих публикациях:

1. Князев Н.А., Малинаускас К.К. «Параллельный алгоритм поиска критических путей и циклов в задаче статического временного анализа для схем с последовательностной логикой» // Сборник трудов конференции Микро и Нано Электронные Системы, г. Москва, 2012, С. 43-48.

2. Князев Н.А., Малинаускас К.К. «Алгоритмы поиска критических

путей в задаче статического временного анализа СБИС» // Журнал

8

«Информационные Технологии» №11, г.Москва, 2012, С. 2-9

3. Князев H.A., «Статический временной анализ синхронных цифровых схем на многоядерных ЭВМ» // Научный сервис в сети Интернет: экзафлопсное будущее: Труды Международной суперкомпьютерной конференции, г. Новороссийск, 2011, С. 617-625.

4. Князев H.A. «Параллельный статический временной анализ цифровых схем с последовательностной логикой» // Труды Конференции «Современные проблемы прикладной математики и информатики», [Электронный ресурс] г. Дубна, 2012, 6 С.

Также по тематике высокопроизводительных вычислений у автора имеются публикации:

5. H.A. Князев, А.Н. Сальников «Система справедливого планирования и унифицированного запуска задач пользователя на суперкомпьютерах //Параллельные вычислительные технологии» (ПаВТ'2010): Труды международной научной конференции (Уфа, 29 марта - 2 апреля 2010 г.) [Электронный ресурс] - Челябинск: Издательский центр ЮУрГУ, 2010. - ISBN 978-5-696-03987-9

6. Knyazev N., Salnikov A. «The Dynamic Priority Controlling Add-On to the System of Batch Processing Tasks of MAUI» // Scientific computing. Proc. of the Intern. Eugene Lawler Ph.D. School. Micheal О hEigeartaigh, Nina Popova (Eds.). Waterford, Ireland: WIT press, 2010. P. 198-209.

7. Князев H. А., Сальников А.Н. «Управление динамическими приоритетами в планировании задач на многопроцессорных комплексах» // Программные системы и инструменты. Тематический сборник No. 10. M.: Изд-во ф-т ВМиК МГУ, 2009. С.64-74

8. Князев Н. А. «Надстройка над системой пакетной

обработки задач пользователя MAUI с целью управления

динамическими приоритетами» // Материалы докладов XVI

9

Международной конференции студентов, аспирантов и молодых ученых «Ломоносов 2009» / Отв. ред. И.А. Алешковский, П.Н. Костылев, А.И. Андреев. ISBN 978-5-317-02774-2

9. Князев Н. А. «Система справедливого планирования задач пользователя на основе генетического алгоритма и унифицированного запуска задач через веб-интерфейс на разных вычислительных комплексах» Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2010» / [Электронный ресурс] - М.: МАКС Пресс, 2010.

10. Князев Н. А., Сальников А.Н. «Планирование запуска программ на суперкомпьютерах» Монография/ LAP LAMBERT Academic Publishing. 2011 50 С. ISBN-13:978-3-8433 -0712-3 ISBN-10:3843307121 EAN-.9783843307123

Описание предметной области

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

Описание задачи статического временного моделирования работы СБИС

Основная задача статического временного моделирования (или статического временного анализа) схемы - определить для каждого узла схемы максимальное и минимальное время распространения сигнала от входа до данного узла. Различают статический и динамический временной анализ схем [1]. При динамическом анализе производится полное моделирование переходных процессов при различных возможных вариантах переключений входных сигналов. Динамический

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

Обзор существующих методов поиска критических путей в задаче статического моделирования временных характеристик схем

В данном разделе предлагается обзор алгоритмов поиска критических путей на временном графе, используемых в СВА. Эти алгоритмы несколько отличаются от классических алгоритмов поиска путей наибольшей (наименьшей) длины (Дейкстры, Беллмана-Форда и других), известных в теории графов, поскольку задача СВА имеет свою специфику [7-9]

Современные СБИС содержат миллионы логических элементов, а время их анализа может занимать более суток [2]. В такой ситуации важную роль в СВА начинают играть инкрементальные и параллельные алгоритмы. Инкрементальные алгоритмы анализируют схему после ее

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

Одной из проблем СВА является выявление «ложных путей», т.е. путей, которые не реализуемы ни в одном из сценариев нормальной работы схемы. Эта проблема подробно рассмотрена в работах [11-13], однако предлагаемые алгоритмы редко используются в коммерческих САПР из-за большой сложности задачи [3]. Другая проблема - это проблема выбора к критических путей [11,14,15]. Большинство алгоритмов предполагает выявление только критических (худших по своим временным характеристикам) путей в графе. Однако инженерам часто требуется знать некоторое количество околокритических путей в данном узле. В работе [4] представлен полиномиальный алгоритм выделения множества путей в схеме с задержками, превышающими некоторое заранее заданное пороговое значение, этот метод не предполагает выявление критических путей, а находит все пути удовлетворяющие условию. Основа всех методов СВА -распространения событий (изменения уровня сигнала в узле схемы). События распространяются по временному графу, где вершинами являются узлы схемы, а ребра соответствуют причинно-следственным связям между возможными событиями в узлах. Последовательность порождающих друг друга событий называется временным путем. Задачей временного анализа, таким образом, является определение задержек событий, которые рассчитываются относительно событий синхронизирующей цепи.

Рассмотрим распространенные методы поиска критических путей в задаче статического временного анализа, включая инкрементальные и параллельные подходы.

Статический временной анализ ациклических схем

Обычно в правильно спроектированной комбинационной схеме

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

В работе [5] приводится обобщенный алгоритм СВА для ацикличного графа, который можно представить так:

Вход: список начальных элементов.

Выход: худшие задержки (ЬАТ) во всех узлах схемы.

1. Проинициализировать ЬАТ в каждом узле схемы значением

2. Для каждого элемента д схемы из списка (в порядке от входов к выходам) выполнить:

2.1 Распространить события со входов элементов на выходы, вычислить ЬАТ на выходах, выполняя прореживание.

2.2 Распространить события с выходов элементов на входы следующих элементов, вычислить ЬАТ на входах, выполняя прореживание.

Алгоритм 1. Общий алгоритм для ациклического графа

После определения худших задержек во всех узлах схемы можно восстановить критические пути, вычислить их запасы и определить пути с нарушениями.

Параллельные алгоритмы для комбинационных схем представлены в работах [6], [7] и рассмотрены ниже.

Статический временной анализ схем с циклами, триггер-граф

В последовательных схемах могут содержаться элементы памяти

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

В некоторых работах предлагается рассматривать вместо полного временного графа так называемый триггер-граф, где вершинами являются триггеры, а вес ребер между триггерами йе1ау(¥иУ^ равен суммарной задержке во временном графе между ними. Сложность построения триггер-графа для временного графа С, имеющего N триггеров равна 0(ЩС\), где - число вершин в графе С. Пример построения триггер-графа на основе графа схемы изображен на рисунке 1.

І-

Входы синхронизирующей цепи

Вход

Триггер

Граф схемы

Триггер

Вход

Тригге

Триггер ^

Триггер-граф на основе графа схемы Рисунок 1 Пример триггер-графа

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

Рисунок 2 Комбинационная логика и триггеры

Стоит отметить, что в правильно спроектированных схемах сигнал в цикле, содержащем статический триггер, успевает пройти через цикл за время меньшее одного такта. В этом случае на этапе прореживания пришедший на вход данных сигнал не будет распространяться, так как со входа синхронизирующей цепи придет сигнал синхронизации с большей задержкой. В случае, когда сигнал на вход данных приходит после сигнала синхронизирующей цепи имеется критический цикл и необходимо или закончить анализ или для его продолжения разорвать цикл.

Фазовый сдвиг

Задержки всех распространяемых в СВА событий отсчитываются относительно синхронизирующих событий «идеального» генератора тактовых импульсов. В представленных ниже алгоритмах задержка события, распространяемого со входа данных на выход прозрачного триггера V,, корректируется, изменяя точку отсчета на точку отчета закрывающего события (С1к_С1оБе,) в цепи синхронизации данного триггера. Таким образом, задержка события е после прохождения триггера будет составлять Це)=Агг, + Д - Лр, где Ар - оператор фазового сдвига между триггером У1 и триггером - источником события Агг1 (подробное описание приведено в работе [8]).Фазовый сдвиг позволяет различать критические и не критические циклы на триггер графе. Если после фазового сдвига задержка нового события зациклившегося пути становится меньше, чем уже задержка уже существующего события этого пути в этой точке, то путь является некритическим. Данные факт будет определен на этапе прореживания.

Простейший алгоритм на триггер-графе

В работе [8] предлагается простейший алгоритм расчета триггер-

графа, основанный на Алгоритме Форда-Беллмана [9] (Алгоритм 2).

Прерывание по числу итераций на шаге 2 используется для предотвращения зацикливания алгоритма в случае наличия критических циклов. Нарушения, соответствующие отрицательным путям и циклам, не различаются и выводятся вместе. Стоит отметить, что в данном алгоритме не используется распространение событий от входов к выходам, и таким образом при анализе задержки не учитывается длина фронта переключения сигнала, что снижает точность алгоритма.

Вход: временной граф схемы. Выход: список нарушений.

1 Для всех выходов триггеров Vi установить ArrPreVi = Arr± = Depi = .

2 Для каждого триггера вычислить худшую задержку на выходе:

Depi = max {ArrPrev± + D± - Ajif С1к_Ореп± + Dc±) .

3 Для каждого триггера вычислить худшую задержку на входе:

Arr± = max{"Depj+delay (V3,vi) | из всех входящих ребер (Vi,vj))-

4 Если хотя бы для одного триггера ArrPreVi Ф Arri и количество итераций меньше числа триггеров, то установить ArrPrev± = Arr± и перейти на п.2.

5 Вычислить запасы и вывести нарушения.

Алгоритм 2. Простой алгоритм на триггер графе

Корректировка задержек

Рассмотрим случай, когда на триггере со статическим управлением задержка события (Агг) на входе больше задержки закрывающего события (СІк_СІОБе), то есть, нарушена корректная работа схемы. В этом случае иногда считают, что событие на входе наступило одновременно с закрывающим событием. Это делается для

того, чтобы не прерывать распространение «опоздавшего» события, а продолжить распространение в предположении, что нарушение исправлено. Таким образом, задержка события на выходе элемента (Dep) корректируется: Dep = min (max(Arr, ClkjOpen), Clk_Close).

В работе [8] корректировка задержек представляется добавлением между триггером и следующими за ним элементами еще одного элемента, так называемой min-вершины, этот элемент передает событие с задержкой не большей, чем Clk_Close (рисунок 3). В остальном используется простой алгоритм на триггер графе, описанный выше.

Триггер

К

Триггер в графе

Триггер в графе, после добавления min-вершины

Рисунок 3 Пример min-вершины

Алгоритм распространения от триггеров

В работе [8] предлагается алгоритм с обнаружением циклов на триггер-графе с помощью построения путей, начиная от триггеров. На г-том шаге алгоритма для каждого триггера выбирается худший путь длины г-1 (длина пути равна количеству триггеров, входящих в этот путь), заканчивающийся на данном триггере. Если данный путь имеет задержку Агг большую, чем открывающий сигнал С1к_Ореп (т.е. триггер прозрачен), то строится путь длины / путем дальнейшего распространения события через триггер на его выход и до следующих триггеров. Алгоритм выглядит следующим образом:

Вход: граф схемы

Выход: список критических путей и циклов, список нарушений

1 Всем триггерам ставим в соответствие путь нулевой длины, начинающийся и заканчивающийся в этом триггере, устанавливаем текущую длину путей 1 = 1

2 Выполнять следующие действия, пока есть путь длины 1-1

2.1 На входе каждого триггера Ь найти худшее событие, порождаемое путем длины 1-1, заканчивающимся в триггере, соединенным с входом данного.

2.2 Если данное событие имеет задержку большую, чем С1к_0реп, выполнить:

2.2.1 Если этот путь не содержит триггер Ь ранее, то расширить путь (распространить события) до длины 1, включив триггер Ь в путь. В противном случае сообщить об обнаруженном цикле.

3 Вычислить запасы и вывести пути с нарушениями и циклы.

Алгоритм 3. Алгоритм распространения от триггеров

Сравнение алгоритмов на графах с циклами

В работе [8] приводятся результаты реализации алгоритмов на основе триггер-графа, сравнивается работа алгоритмов на одинаковых схемах с несколькими тысячами триггеров. Самым быстрым является алгоритм распространения от триггеров, он работает около 5-6 секунд для графов схем с несколькими тысячами вершин. Простейший алгоритм с корректировкой задержек работает около 9-14 секунд для графов схем с несколькими тысячами вершин. При этом без использования корректировки задержек, выполнение простого алгоритм на триггер-графе занимает несколько часов. Отметим, что алгоритм

распространения от триггеров потенциально может быть реализован в параллельном варианте, так как поиск худших путей заданной длины можно выполнять параллельно. Однако, в работе [8] вопрос параллелизации не рассматривается.

Инкрементальные Алгоритмы

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

Назовем множество элементов в направленном графе, достижимых из данного элемента, выходным конусом элемента. Объединение выходных конусов изменившихся элементов назовем конусом изменений. В работе [11] доказывается, что после изменения нескольких элементов, задержки изменятся только в конусе изменений, и поэтому расчет задержек можно сократить только до элементов, входящих в конус изменений.

Упрощенный инкрементальный алгоритм

В случае, когда граф изменился незначительно, на практике часто допускают, что структура критических путей не изменилась. В этом случае выполнять повторно СВА всей схемы нет необходимости. Для отражения этого изменения достаточно вычислить заново задержки во всех критических путях, проходящие через измененный элемент. Инкрементальный перерасчет конуса занимает существенно меньше времени, чем СВА всей схемы. Простой инкрементальный алгоритм, по сути, представляет собой простой обход графа критических путей. Обход графа поиском в ширину хорошо распараллеливается [7]. В

работе [6] предлагается реализация простого инкрементального алгоритма, с помощью которой удалось достичь 13-кратного ускорения на 16 потоках. Сложность данного алгоритма линейна по отношению к числу событий в конусе. При использовании прореживания эта сложность равна 0(И), где N - число элементов в конусе изменений.

Вход: множество ребер увеличивших свой вес Е+ Выход: позднее время прибытия сигнала для каждой вершины графа схемы

0. Произвольно пронумеровать вершины графа схемы внутри конуса (сопоставляем каждому узлу ЛТі число Ыб(У±)), назовем ребра положительными, если они ведут из вершины с меньшим номером в вершину с большим номером, иначе отрицательными.

1. Установить счетчик Л2=0, добавить в очередь 0° все вершины на изменившихся ребрах графа схемы.

2. Пока очередь О™ не пуста выполнить:

2.1 Извлечь вершину VI из начала очереди, для всех ребер (Уі,У^) , исходящих из этой вершины, выполнить:

2.1.1. Если Ыв (Уі) (У^) (ребро

положительное) и

ЬАТ(УІ) +йе1ау (УіУі) >ЬАТ (У±) , обновить значение ЬАТ(Уі) и граф худших путей, добавить узел У^ в конец очереди 0™.

2.1.2 Если Ыб (У±) >Ыб (У^) (ребро

отрицательное) и У^ отсутствует в очереди то добавить узел в начало

очереди .

3. Если очередь пуста, то увеличить счетчик та на 1, если очередь 0т+І пуста, то закончить алгоритм, иначе перейти на шаг 2.

Алгоритм 4. Инкрементальный алгоритм для случая увеличения задержек.

Точный инкрементальный алгоритм

В статье [11] отдельно рассматривают случай увеличения и

уменьшения задержек. Для общего случая предлагается смешанный

алгоритм, использующий алгоритмы для увеличения и уменьшения

задержки.

Случай увеличения задержек

В случае, если задержки событий на всех измененных элементах

увеличились, доказывается, что остальные задержки также могут только увеличиться и только внутри конуса изменений.

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

Случай уменьшения задержек

Если в результате изменений вес ребер уменьшился, аналогично

с предыдущим алгоритмом доказывается, что задержка в конусе изменений могла только уменьшиться.

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

Назовем ребра где принадлежит графу критических

путей, а VI не принадлежит граничными ребрами.

Вход: множество ребер уменьшивших свой вес Е" Выход: обновленные задержки на вершинах графа схемы, список ребер Out

1 Отсортировать ребра конуса дерева худших путей в соответствии с топологическим порядком.

2 Для каждого ребра (VitVj) в топологическом порядке, если узел Vj не отмечен как посещенный:

1.1 Создать очередь Q и положить в нее Vj.

1.2 Пока очередь Q не пустая:

1.2.1 Извлечь узел Vi из очереди и отметить его как посещенный, пусть в дереве худших путей в этот узел входит ребро (VkiVi) .

1.2.2 Пересчитать задержку сигнала в узле Vi как LAT (Vx) = LAT (Vk)+delay (VltVk)

1.2.3 Для каждого входящего граничного ребра (ym/Vi) : если LATiVx) <

LAT (Vm) +delay (Vm/Vk) , то обновить худшую задержку и граф худших путей.

1.2.4 Для всех ребер (VltVk) на графе худших путей добавить в очередь узел Vk, если он еще не посещен.

3 Для всех ребер (VitVj) , не входящих в граф худших путей, но входящих в конус изменений, если LAT(Vj) < LAT (Vj)+delay(Vi/Vj) , то добавить (VitVj) в список Out (этот список используется в алгоритме для общего случая, описанном ниже).

Алгоритм 5. Инкрементальный алгоритм для случая уменьшения задержек.

\

Общий случай

Для общего случая, когда среди измененных ребер графа есть ребра и увеличившие и уменьшившие свой вес, предлагается общий алгоритм:

Вход: набор изменившихся ребер

Выход: обновленные задержки на вершинах графа

схемы

1 В список Е~ добавить все ребра, уменьшившие свой вес. В список Е+ добавить все ребра увеличившие свой вес.

2 Выполнить алгоритм для случая уменьшения задержки: на вход алгоритму передать Е~, считая оставшиеся веса неизменными и сформировать список Out. Очистить список Е~ .

3 Выполнить алгоритм для случая увеличения задержек, подавая на вход объединение списков Е+ и Out. Очистить список Е+ .

4 Для каждого найденного на шаге 3 цикла, разорвать его: для одного из ребер, входящих в цикл, установить задержку и добавить это ребро в Е~.

5 Если Е~ пуст закончить алгоритм иначе перейти на шаг 2.

Алгоритм 6. Инкрементальный Алгоритм для общего случая.

Авторами доказывается, что сложность каждой итерации алгоритма не превосходит 0(И), где N количество элементов в конусе изменений. Таким образом, сложность всего алгоритма равна 0(Ы*Ыс), где Ис число циклов в схеме

Сравнение инкрементальных алгоритмов

Упрощенный инкрементальный алгоритма рассматривает случай,

когда структура критических путей в схеме не изменилась, что не всегда

справедливо. Таким образом, простой алгоритм не всегда вычисляет

правильно худшие задержки, однако хорошо распараллеливается и

масштабируется, и может быть использован для предварительных

оценок. Точный инкрементальный алгоритм выдает правильный

24

результат СВА. К сожалению, в нем используется линейный порядок вершин, что делает параллелизацию невозможной. Однако есть работы по замене линейного порядка частичным [7], что может позволить извлечь ограниченную пользу от использования многопоточности.

Подходы к параллелизации СВА

На сегодняшний день предпринималось много попыток

реализовать поиск критический путей в СВА на многопроцессорных вычислительных комплексах. Однако все подходы, так или иначе, используют ранжирование вершин по уровням.

Параллелизация с использованием ранжирования

Многие современные методы обхода временного графа в СВА

предусматривают анализ вершин в заранее определенном порядке (основанном на топологическом). Наличие топологического порядка гарантирует, что перед анализом элемента события на входах элемента будут рассчитаны, однако ограничивает применимость методов ациклическими графами. В [12] предлагается для параллелизации использовать ранжирование вершин графа по максимальной удаленности от входных элементов. Это позволяет независимо и параллельно рассчитывать элементы на одном уровне с синхронизацией при переходе на следующий уровень.

Недостатком подхода является то, что, если на моделирование элемента 2 будет тратиться больше времени, чем на моделирование элемента 3 (рисунок 5 или 4?), то пока моделируется элемент 2, остальные вычислительные мощности будут простаивать.

В работах [7] и [12] представлена реализация данного подхода. В [12] исследуется работа алгоритма СВА, использующего ранжирование вершин на многопроцессорных системах. Авторы отмечают, что они сталкиваются с проблемой малого количества элементов на одном

уровне даже на «широких» графах. В случае, если на одном уровне оказывается малое число вершин, то загрузка процессоров осуществляется неравномерно, ускорение уменьшается. Однако авторам удалось достичь 100-кратного ускорения на 1024 процессорах для схемы, содержащей 3 млн элементов (эффективность параллелизации около 10% ). Стоит отметить, что с алгоритм применим только схемам не содержащих триггеры тактируемые уровнем.

В [13] предлагается параллельный алгоритм СВА без использования прореживания событий. Однако предложенный алгоритм использует эвристику и не является точным.

Вход

Уровень 1

л

*|Элем.

Уровень2

Элем. 2

Элем. 3

Уровень 3

Элем. 4

Уровень4

Элем.^ 5

Элем. 6

Выход

Выход

Рисунок 4. Параллелизация по уровням

Стоит отметить, что данные подходы эффективно применимы только для «широких» временных графов (где длина пути от входов до выходов значительно меньше числа вершин), иначе авторы [12] отмечают малую загрузку процессоров.

Выводы к обзору существующих методов поиска критических путей в задаче СВА

Статический Временной Анализ - давно исследуемая область применения математических методов в САПР, в рамках которой разработаны эффективные алгоритмы для комбинационных и

последовательных схем, в том числе содержащих циклы. На содержащих миллионы элементов СБИС традиционные алгоритмы СВА работают непозволительно долго. В некоторых случаях можно применять инкрементальные методы, однако, и они не всегда работают достаточно быстро или дают неточный результат. Однако когда разрабатывались алгоритмы временного анализа, многопоточного исполнения обычно не предполагалось. Применение методов параллелизации для описанных алгоритмов может существенно сократить время анализа цифровых схем.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Князев, Николай Александрович

Основные результаты работы

1. Разработан параллельный метод и алгоритмы для вычислительных систем с общей памятью, реализующий поиск критических путей в задаче статического моделирования временных характеристик комбинационных и последовательных СБИС. Доказана корректность этих алгоритмов.

2. На основе разработанных алгоритмов создана параллельная программа. Программа интегрирована в экспериментальную систему анализа схем.

3. Проведены вычислительные эксперименты, показавшие, что полученные результаты заметно отличаются от промышленных инструментов СВА не более чем в 5% случаев. Получены оценки эффективности параллельных вычислений (эффективность составила 6090%) и пределов масштабируемости метода для более чем 80 промышленных СБИС.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Князев, Николай Александрович, 2013 год

Список литературы

1. Hassoun S., Sasao Т. Logic synthesis and verification // Springer 2002 r. C. 373-401.

2. Scheffer L., Lavagno L. EDA for 1С implementation, circuit design, and process technology // CRC Press. 2006 г. C. 608

3. Соловьев P.А., Глебов A.JI. и Гаврилов С.В. Статический временной анализ с обнаружением ложных проводящих путей на основе логических импликаций // Проблемы разработки перспективных микроэлектронных систем - 2006. Сборник научных трудов / под общ. ред. А.Л.Стемпковского. М.:ИППМ РАН, 2006. С. 22-28.

4. Ahn К., Sahni S. NP-hard module rotation problems // IEEE Transactions on Computers, 42 (12). 1993 г. C. 1506.

5. Гаврилов C.B., Стемпковский А.Л. , Глебов А.Л. Методы логического и логико-временного анализа цифровых СБИС // Москва, Наука. 2007 г. 226С .

6. Князев Н.А. Статический временной анализ синхронных цифровых схем на многоядерных ЭВМ // Научный сервис в сети Интернет: экзафлопсное будущее: Труды Международной суперкомпьютерной конференции (сентябрь 2011 г., г. Новороссийск). 2011 г. С. 617-625.

7. Schultze P., Korf R. Е. Large-Scale Parallel Breadth-First Search// Menlo Park, CA; Cambridge, MA; London. 1994 г С. 1380-1385.

8. Burks Т. M., Sakallah К. A., Mudge Т. N. Critical Paths in Circuits with Level-Sensitive Latches // IEEE Transactions on Very Large Scale Integration (VLSI) systems. 1995 г., Т. 3. С. 273-291

9. Bellman R. On a routing problem // Quarterly of Applied Mathematics. 1958 г., С. 87-90.

10. Flynn, Michael J. Some Computer Organizations and Their Effectiveness //IEEE Trans. Comput. T-21 (9): 1972 г. C. 948-960.

11. Jin-fuw L., Tang D. T. An Algorithm for Incremental Timing Analysis // Proceeding DAC '95 Proceedings of the 32nd annual ACM/IEEE Design Automation Conference. 1995 г. C. 696-701

12. Holder A., Christopher D. C., Kalafala K. Prototype for a Large-Scale Static Timing Analyzer running on an IBM Blue Gene // in Proc. IPDPS Workshops. 2010 г. C. 1-8

13. Li-Ren C., Liu D., Hsi-Chuan D. An Efficient Parallel Critical Path Algorithm // Proceeding DAC '91 Proceedings of the 28th ACM/IEEE Design Automation Conference. 1991 г. C. 535-540

14. Yen S., Du D., Ghanta S. Efficient Algorithms for Extracting the К Most Critical Paths in Timing Analysis // In Proc. Design Automation Conference (DAC). 1989 г. C.649-654

15. Elmore W. C. The transient respone of damped linear networks with particular regard to wideband amplifiers // Oak Ridge, Tenn. : Atomic Energy Commission. 1948 г., Т. 19. С. 55-63

16. Ирбенек В. С. Временная верификация и оптимизация размещения компонентов предельных по быстродействию ЭВМ // Институт микропроцессорных вычислительных систем Российской академии наук, Москва. 2001 г. 193 с.

17. Blaauw S., Zolotov D., Sundareswaran V. Slope Propagation in Static Timing Analysis // Proceedings of the 2000 IEEE/ACM international conference on CAD. 2000 г. C. 338-343

18. Duncan, Ralph A survey of parallel computer architectures // IEEE Computer 23 (2): 1990г C. 4-5

19. Pillage L.T., Ratzlaff C. L. RICE rapid interconnect circuit evaluation // 28th АСМ/ IEEE Design Automation Conference. 1994 г. C. 763-776

20. Amdahl, Gene. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities // AFIPS Conference Proceedings (30). 1967 г. C. 483-485

21. Норенков И. П. Учебный курс МГТУ им. Баумана «Основы САПР. Моделирование», http://bigor.bmstu.ru. [Электронный Ресурс]

22. Матросова А.Ю., Кудин Д.В., Николаева Е.А. Обнаружение ложных путей в комбинационной схеме // Вестник Томского Государственного Университета, Вычислительная техника и информатика. №2. 2011 г. С. 99-107

23. Shenoy N. V., Brayton R. K., Sangiovanni-Vincentelli A. Resynthesis of multi-phase pipelines // in Proc. Des. Automa. Conf. 1993 г. C. 490-497

24. Pillage L.T., Rohrer R. Asymptotic Waveform Evaluation for Timing Analysis // IEEE Transactions of CAD. 1990 г., Т. 9. С 352-356

25. Lockyear В., Ebeling С. Optimal retiming of multi-phase level-clocked circuits // In Proc. Adv. Res. VLSI Parallel Syst. 1992 r.

26. Kukimoto Y., Berkelaar M., Sakallah K. Static Timing Analysis // The Kluwer International Series in Engineering and Computer Science. 2003 г., Т. 654. С. 373-401

27. Kirkpatrick Т. I., Clark N. R. PERT as an aid to logic design // IBM Journal of Research and Development Journal. 1966 г., Т. 10. С.135-141

28. Jayabharathi, Rathish. Effects on delay modeling on critical path analysis. 1993 r.

29. J. Lee, D. T. Tang, С. K. Wong. Timing Analysis Algorithm for Circuits with Level-Sensitive Latches // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v. 15, May. 1996 г. C. 535 - 543

30. Ishii A., Leiserson С. E., Papaefthymiou M. C. Optimizing two phase level-clocked circuitry," in Adv. Res. VLSI Parallel Syst. 1992 г. C. 148-199

31. Hitchcock R. В., Smith G. L., Cheng D. D. Timing analysis of computer hardware// IBM J. Res. Develop. 1982 г., Т. 26. С. 100-105

32. Hadley S.W., Mark B.L., Vanelli A. An efficient eigenvector approach for finding netlist partitions // Trans, on CAD, 11. 1992 г. C.885-892

33. Ganley J. L., Cohoon J. P. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles // Proc. IEEE Int. Symp. on Circuits and Systems. 1994 г С. 113-116

34. Dijkstra E. A note on two problems in connection on graphs // Numerische Mathematic, 1. 1959 г. C. 269-271

35. Chadha J., Bhasker R. Static Timing Analysis for Nanometer Designs, A Practical Approach. 2009 r. 569 C.

36. Intel(R) Threading Building Blocks Reference Manual. http://www.intel.com. [В Интернете] 2010 г. 363 P.

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

В качестве основного инструмента использовалась библиотека Intel® Threading Building Blocks (TBB) для языка С++ [13], предоставляющая высокоуровневые шаблоны и примитивы параллельного программирования для многопроцессорных систем с общей памятью. Основной концепцией ТВВ является абстрагирование от исполняемых потоков и архитектуры конкретной вычислительной системы. Для достижения высокой эффективности параллелизма и масштабируемости программы от разработчика требуется разбить вычислительную проблему на множество мелких задач. Обычно это легко достигается при реализации параллелизма по данным. Встроенный в ТВВ динамический планировщик задач назначает их на исполняемые потоки, используя технику «воровства задач» для балансировки загрузки (простаивающие потоки забирают задачи у перегруженных). Кроме того, библиотека ТВВ оптимизирована под использование кэш-памяти.

В реализации наших алгоритмов используется шаблон ТВВ parallel_do, который позволяет добавлять задачи в общий пул, в том числе в процессе выполнения задач. В качестве неделимой задачи выступает временной анализ отдельного логического элемента и распространение событий через межсоединения на смежные с ними элементы. Для параллельного анализа триггеров используется шаблон parallel_for, который позволяет параллельно выполнять заранее определенное количество задач, не имеющих зависимостей по данным. В процессе выполнения шаблон parallel_for рекурсивно делит представленный к выполнению интервал задач, до достижения

«минимальной» работы и назначает данные работы на различные ядра.

87

Также библиотека Intel® Threading Building Blocks (TBB) предоставляет набор инструментов для реализации потокобезопасного доступа к данным.

В реализации были использованы потокобезопасные контейнеры, tbb::concurrent_hash_map и tbb::concurrent_vector, позволяют осуществлять параллельную вставку в соответствующие контейнеры. Эти контейнеры являются потокобезопасным аналогом стандартных контейнеров языка С++ библиотеки Standart Template Library (STL), std::map и std::vector.

Также используются примитивы для предотвращения одновременного доступа к данным - мьютексы (реализации различным типов семафоров): tbb::spin_mutex и tbb::mutex. Были использованы атомарные переменные и операции, т.е. небольшие операции, при выполнении которых система гарантирует, что другой поток не будет обращаться к данной переменной. Счетчики элементов были реализованы, как атомарные переменные с атомарной операцией увеличения. Был использован класс tbb::atomic.

Вместо медленных при использовании многопоточного программирования распределителей памяти malloc и free, были использованы потокобезопасные и быстрые распределители памяти tbb::concurrent malloc и tbb::concureent free.

Методики измерения ускорения алгоритма на многоядерных системах.

В данном разделе приводятся различные подходы к изменению ускорения. При различных запусках программы на одной схеме время работы программы может отличаться. Это зависит от многих факторов: загруженности компьютера, скорости доступа к тому месту оперативной памяти, где лежат данные, и т.д.

Таким образом, когда говорится об ускорении программы на определенном числе потоков необходимо отмечать, какие из запусков (наилучший, наихудший или средний) учитываются при вычислении ускорения. Рассмотрим, насколько отличаются времена работы алгоритмов для различных используемых в промышленности схем

Схема 1

Характеристики схемы Число Элементов: 19480

Число триггеров, со статическим управлением: 1528 Число триггеров в самом длинном пути схемы: 3

400,00

0,00 Т1те ¡п Бес.

16 потоков

1 поток

Характеристики схемы Число Элементов: 5465

Число триггеров, со статическим управлением: 691 Число триггеров в самом длинном пути схемы: 4

16 потоков

1 поток

Рисунок 2. Время работы разных запусков алгоритма для схемы 2 Схема 3

Характеристики схемы Число Элементов: 3244

Число триггеров, со статическим управлением: 350 Число триггеров в самом длинном пути схемы: 4

70,00 60,00 50,00 40,00 30,00 20,00 10,00

16 потоков

1 поток

Рисунок 3. Время работы разных запусков алгоритма для схемы 3

Характеристики схемы Число Элементов: 512

Число триггеров, со статическим управлением: 108 Число триггеров в самом длинном пути схемы: 3

10,00 8,00 6,00 4,00

2,00--

0,00--

время

К 1

16 потоков

1 поток

Рисунок 4. Время работы разных запусков алгоритма для схемы 4 Схема 5

Характеристики схемы Число Элементов: 1772

Число триггеров, со статическим управлением: 177 Число триггеров в самом длинном пути схемы: 4

50,00 45,00

40,00 35,00 30,00 25,00 20,00 15,00 10,00 5,00 -М 0,00 -1—1 время

16 потоков

1 поток

Схема 6

Характеристики схемы Число Элементов: 5228

Число триггеров, со статическим управлением: 390 Число триггеров в самом длинном пути схемы: 3

16 потоков

1 поток

Рисунок 6. Время работы разных запусков алгоритма для схемы б Схема 7

Характеристики схемы Число Элементов: 3573

Число триггеров, со статическим управлением: 319 Число триггеров в самом длинном пути схемы: 4

140,00

120,00

100,00

80,00

60,00

40,00

20,00

16 потоков

1 поток

Характеристики схемы Число Элементов: 24670

Число триггеров, со статическим управлением: 2034 Число триггеров в самом длинном пути схемы: 4

800,00

0,00 время

8 threads

1 thread

Рисунок 8. Время работы разных запусков алгоритма для схемы 8 Схема 9

Характеристики схемы Число Элементов: 6756

Число триггеров, со статическим управлением: 138 Число триггеров в самом длинном пути схемы: 3

250,00

200,00

150,00

100,00

50,00

16 потоков

1 поток

Схема 10

Характеристики схемы Число Элементов: 17435

Число триггеров, со статическим управлением: 1674 Число триггеров в самом длинном пути схемы: 4

0,00 время

16 потоков

1 поток

Рисунок 10. Время работы разных запусков алгоритма для схемы 10

Как видно из приведенных графиков абсолютные числа времени работы программы на больших схемах различаются не более чем на 5%. Все эксперименты проводились в «идеальных» условиях - при минимальной загрузке вычислителя. Однако, стоит отметить, что разница на 5% в абсолютном времени выполнении программы может существенно влиять на ускорение.

Рассмотрим различные значения ускорения алгоритма на 16 потоках, вычисленные различными способами.

Ускорение 10

ГП I І І I

I Наибольше время / Наименьшее время I Среднее время / Среднее время I Наибольше время / Наименьшее время I Наименьшее время / Наименьшее время Наибольше время / Наибольшее время

9 10

Номер схемы

Рисунок 11. Ускорение для различных схем, рассчитанное разными способами.

Как видно из приведенного графика, значения ускорений различаются не очень сильно. В процентном соотношении эти различия больше проявляются на небольших схемах, где время выполнения схемы невелико. Для того чтобы минимизировать издержки, связанные с нагрузкой вычислителя, для дальнейшего анализа было решено считать ускорение, как отношение наименьшего времени из всех запусков на нескольких потоках к наименьшему времени из всех запусков на одном потоке. Для каждой схемы и для каждого количества потоков