На правах рукописи

Князев Николай Александрович

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

характеристик работы СБИС с использованием

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

Специальность 05.13.18

Математическое моделирование, численные методы и

комплексы программ

АВТОРЕФЕРАТ

Диссертации

на соискание ученой степени кандидата физико-математических наук

Москва 2013

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт прикладной математики им. М.В. Келдыша РАН.

доктор физико-математических наук

Научный руководитель:

ФГБУН Институт прикладной математики им. М.В.

Келдыша РАН, начальник сектора Якобовский Михаил Владимирович кандидат физико-математических наук

Научный консультант:

ЗАО «Интел А/О», старший научный сотрудник Малинаускас Костас Костович доктор технических наук, профессор

Официальные оппоненты:

Нижегородский государственный университет им Н. И.

Лобачевского, декан факультета Вычислительной Математики и Кибернетики Гергель Виктор Павлович Кандидат физико-математических наук Федеральное государственное бюджетное учреждение науки Институт Прикладной Математики им. М.В.

Келдыша РАН, заведующий сектором.

Болдарев Алексей Сергеевич Федеральное государственное бюджетное учреждение

Ведущая организация:

науки Научно-исследовательский институт системных исследований РАН

Защита диссертации состоится 17 октября 2013 г.в 14.00 часов на заседании диссертационного совета Д 002.024.03 в Федеральном государственном бюджетном учреждении науки Российской академии наук Институте прикладной математики им.

М.В. Келдыша по адресу: 125047, г.Москва, Миусская пл., д.4А.

С диссертацией можно ознакомиться в библиотеке ИПМ им. М.В. Келдыша РАН

Автореферат разослан сентября 2013 г.

Учёный секретарь диссертационного совета Д 002.024.03, Н.В.Змитренко доктор физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

1. Международная конференция «Научный сервис в сети Интернет:

экзафлопсное будущее», г. Новороссийск, 2011.

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

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

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

Личный вклад автора Автором был разработан и реализован предложенный в работе масштабируемости метода.

Объем и структура диссертации Диссертация состоит из 3х глав, введения, заключения и списка литературы. Диссертация содержит 80 страниц, 35 рисунков. В Списке литературы присутствует 36 наименований.

Также в исследуемой области параллельных технологий автором работы выпущена монография:

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

характеристик (или статического временного анализа, СВА) схемы – определить предельную тактовую частоту, на которой будет работать схема и построить критические пути прохождениях сигнала 1. В статическом временном анализе задержки вычисляются путем упрощенного использованием сценариев худшего случая распространения сигналов. В качестве результата СВА принято рассматривать набор критических путей во временном графе 2, определяющих быстродействие схемы. В реализациях методов СВА рассматривают несколько этапов – загрузка модели схемы в оперативную память (построение модели на основе описания схемы), расчет схемы и вывод результата. В данной работе рассматривается второй этап – расчет схемы. Время, затрачиваемое инструментами на каждый из этапов, сильно зависит от конкретной реализации и предъявляемых требований Гаврилов С., Стемпковский А., Глебов А. Методы логического и логиковременного анализа цифровых СБИС // Москва, Наука. 2007 г.

Hassoun S., Sasao T. Logic synthesis and verification // Springer pp. 373-401.

2002 г.

(способ хранения схемы, принцип вывода критических путей и т.д.).

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

Событие – изменение уровня сигнала (логического «0» или «1») в узле схемы (на входе или выходе логического элемента). Событие е характеризуется шестью характеристиками t(е), v(е), s(е), f(е), p(е), ref(e) Задержка события t(e) – время наступления события относительно некоторого начала отсчета.

Узел схемы v(e) – узел схемы, на котором наступает событие.

Фронт переключения события (Тип события) f(e) – направление переключения уровня сигнала (с 1 на 0 или с 0 на 1) Время фронта переключения s(e) – Время, за которое изменяется уровень сигнала.

порождающие данное событие синхронизирующее событие, относительно которого считается задержка.

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

(Временной) путь – последовательность событий, где очередное последовательность событий e1 … en,где Задержкой пути, e1 en заканчивающегося событием en, называется задержка этого события t(en).

Критический путь – это такой путь e1 … en, что временном графе выполняется следствие:

Запас – разность между фактической задержкой события (пути) и задержкой, предельно допустимой для корректной работы схемы.

Отрицательный путь – путь, имеющий отрицательный запас.

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

Триггер со статическим управлением (latch, или с управлением по уровню) – триггер, в котором условием передачи сигнала служит состояние входа синхронизации (0 или 1), определяющее «прозрачность» триггера.

Триггер прозрачен (открыт) между открывающим и закрывающим событиями синхронизирующей цепи, в остальное время триггер непрозрачен (закрыт). Обозначим время распространения события со входа данных на выход как D, а время распространения события синхронизации на выход – как Dс, опишем событие на выходе eвых через входящее событие eвх и события синхронизации eоткр и eзакр Рисунок 1 Триггер, тактируемый уровнем Рассмотрим различные варианты соотношения задержек событий 1. Триггер прозрачен : d(eзакр)>d(eвх) >d(eоткр) i) d(eвых) = d(eвх) + D + d(ref(eвх)) - d(ref(eоткр )) (фазовый сдвиг ) ii) Изменение события синхронизации, относительно которого рассчитывается задержка триггера называется фазовым сдвигом:

ref(eвых) = ref(eоткр ) ;

iii) p(eвых) = eвх 2. Триггер закрыт: d(eвх) d(eзакр). В случае если событие произошло позже закрывающего события синхронизирующей цепи, то в рамках модели допускается «восстановление» события, и считается что событие на входе произошло в одновременно с закрывающим событием. Однако данная ситуация, как правило, является нарушением и о ней необходимо сообщить проектировщику схемы i) d(eвых) = d(eзакр) + Dс ii) ref(eвых) = ref(eоткр ) ;

iii) p(eвых) = eвх (распространяется eвх с задержкой d(eзакр) + Dс) Пусть события eвых1,eвых2 произошли на одном узле и входят в один путь, и при этом событие eвых1 произошло раньше. Такой путь называется критическим циклом, если d(eвых2) - d(ref(eвых2)) > d(eвых1) - d(ref(eвых1)) Критический цикл является ошибкой проектирования, т.к. задержка на нем накапливается, что приводит к сбою В качестве входных данных для СВА выступает набор событий на входах схемы, при распространении событий используется прореживание: в каждом узле схемы выбираются события с наихудшей (наибольшей или наименьшей, в зависимости от типа анализа) задержкой, и дальше по схеме распространяются только эти события.

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

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

Для обеспечения «асинхронной» параллелизации каждому элементу ставится в соответствие счетчик, соответствующий числу входов, на которых еще не Yen S., Du D., Ghanta S. Efficient Algorithms for Extracting the К Most Critical Paths in Timing Analysis // In Proc. Design Automation Conference (DAC). 1989 г.

Schultze P., Korf R. E. Large-Scale Parallel Breadth-First Search// Menlo Park, CA;

Cambridge, MA; London. 1994 г.

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

На этапе расчета элементов производится непосредственно расчет схемы, т.е. распространение событий от входов схемы к ее выходам и расчет критических путей. Физический расчет элементов выполняется при помощи библиотеки RICE 5 и остается за пределами данной работы. Этап расчета элементов выглядит следующим образом:

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

7. Если счетчик какого-либо из элементов стал Рисунок 2 Алгоритм СВА для схемы без циклов В данном алгоритме рассчитывать и добавлять элементы в очередь Pillage L.T., Ratzlaff C. L. RICE rapid interconnect circuit evaluation // 28th ACM/ IEEE Design Automation Conference. 1994 г.

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

В случае, если у элемента несколько выходов, то обработку выходов можно выполнять параллельно (использовать параллельный цикл по выходам в пунктах 3 и 5 алгоритма СВА для схемы без циклов). Таким образом, существует возможность встроить в алгоритм «низкоуровневый»

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

Если в процессе выполнения алгоритма для комбинационных схем этап распространения событий не выполнен для какого-либо элемента (элемент не был проанализирован). То хотя-бы один из входов этого элемента соединен с элементом, для которого этот этап также не был выполнен.