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

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

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

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

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

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

АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата физико-математических наук

2 я СЕН 2013

Москва 2013

005533595

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

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

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

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

декан факультета Вычислительной Математики и

Кибернетики

Гергель Виктор Павлович

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

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

Защита диссертации состоится 17 октября 2013г. в 14.00 часов на заседании диссертационного совета Д 002.024.03 в Федеральном государственном бюджетном учреждении науки Российской академии наук Институте прикладной математики им. М.В. Келдыша по адресу: 125047, г.Москва, Миусская пл., д.4А.

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

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

Учёный секретарь

диссертационного совета Д 002.024.03, доктор физико-математических наук

Н.В. Змитренко

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

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

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

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

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

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

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

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

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

диссертационной работе предложен параллельный метод для статического моделирования временных характеристик схем с последовательной логикой,

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задержка события t(e) - время наступления события относительно некоторого начала отсчета.

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

Фронт переключения события (Тип события) f(e) - направление переключения уровня сигнала (с 1 на 0 или с 0 на 1)

Время фронта переключения s(e) - Время, за которое изменяется уровень сигнала.

Родительское событие р(е) - событие на соседнем узле, порождающие данное событие

Событие генератора тактовых импульсов ref(e) - синхронизирующее событие, относительно которого считается задержка.

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

(Временной) путь - последовательность событий, где очередное событие порождается предыдущим в смежном узле, т.е. такая последовательность событий e¡... еп ,где V i, i Ф 1: p(e¡) = е^

Задержкой пути, e¡ еп заканчивающегося событием еп, называется задержка этого события t(e„).

Критический путь - это такой путь e¡... е„ , что V события е на временном графе выполняется следствие:

v(e) - v(en) И f(e) = f(en) => t(e) < t(en)

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

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

управлением

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

Триггер со статическим управлением (latch, или с управлением по уровню) - триггер, в котором условием передачи сигнала служит состояние входа синхронизации (0 или 1), определяющее «прозрачность» триггера. Триггер прозрачен (открыт) между открывающим и закрывающим событиями синхронизирующей цепи, в остальное время триггер непрозрачен (закрыт). Обозначим время распространения события со входа данных на выход как Д а время распространения события синхронизации на выход - как Dc, опишем событие на выходе евых через входящее событие евх и события синхронизации

еоткр И езакр

е вх D Выход

Вход / в вых

/ е откр е за нр \ Вход синхронизации

Рисунок 1 Триггер, тактируемый уровнем

Рассмотрим различные варианты соотношения задержек событий

1. Триггер прозрачен : с1(ех,ч,)>с1(е„х) >й(еоткр)

О й(евъи) = й(е„х) + О + с1(геДенх)) - с1(геДсоткр)) (фазовый сдвиг) и) Изменение события синхронизации, относительно которого рассчитывается задержка триггера называется фазовым сдвигом: ге[(с,,ых) = Уе^е0ткр), Ш) р(евых) = евх

2. Триггер закрыт: с1(евх) <й(еоткр) О с1(еных) = с1(е,ткр) + Ос

п) геДевьа) = геДеоткр);

ш) р(е„ых) = соткр (распространяется е„ткр)

3. Восстановление сигнала: с1(с„х) >с1(езакр). В случае если событие произошло позже закрывающего события синхронизирующей цепи, то в рамках модели допускается «восстановление» события, и считается что событие на входе произошло в одновременно с закрывающим событием. Однако данная ситуация, как правило, является нарушением и о ней необходимо сообщить проектировщику схемы о (¡(е„Ь1Х) = й(еткр) + Бс и) ге/(евш) = ге/(епткр);

р(евьа) = е„х (распространяется енх с задержкой с1(е,шр) + Ос) Пусть события евъа1 ,евШ2 произошли на одном узле и входят в один путь, и при этом событие евых1 произошло раньше. Такой путь называется критическим циклом, если (¡(е„ьи2) - ¿(ге/(евЬ1х2)) > ¿(евш1) - с1(ге/(евЬ1Х,))

Критический цикл является ошибкой проектирования, т.к. задержка на нем накапливается, что приводит к сбою

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

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

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

3Yen S., Du D., Ghanta S. Efficient Algorithms for Extracting the K Most Critical Paths in Timing Analysis // In Proc. Design Automation Conference (DAC). 1989 r.

4Schultze P., Korf R. E. Large-Scale Parallel Breadth-First Search// Menlo Park, CA; Cambridge, MA; London. 1994 r.

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

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

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

Вход: граф схемы с установленными счетчиками

Выход: рассчитанные задержки событий на вершинах графа,

с учетом прореживания

1. Поместить в очередь начальные элементы.

2. Выбрать элемент из очереди.

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

4. Осуществить прореживание сигналов.

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

6. Для элементов, входы которых соединены с выходами данного, уменьшить счетчик на 1.

7. Если счетчик какого-либо из элементов стал равен О, то добавить его в очередь.

8. Если очередь пуста, закончить алгоритм, иначе перейти на пункт 2.

Рисунок 2 Алгоритм СВА для схемы без циклов

Физический расчет элементов выполняется при помощи библиотеки RICE5 и остается за пределами данной работы.

В данном алгоритме рассчитывать и добавлять элементы в очередь можно в параллельном режиме. Все затратные по времени операции алгоритма

5Pillage L.T., Ratzlaff C. L. RICE rapid interconnect circuit evaluation // 28th ACM/ IEEE

Design Automation Conference. 1994 r.

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

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

Лемма 1

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

Лемма 2

Если на путь v/...v„ является критическим, то для любого к, к<п путь V/...vkтакже является критическим.

Лемма 3

Построенные на этапе распространения событий пути на выходах элемента после осуществления прореживания являются критическими путями.

Стоит отметить, что Лемма 3 остается верной, только в случае, когда не учитывается длина фронта переключения сигнала. Событие с «пологим» фронтом переключения и малой задержкой на выходе схемы может «накопить» задержку больше, чем событие с большей задержкой, но с «крутым» фронтом переключения6, тем не менее учитывать величину фронта переключения при прореживании сигнала невозможно без расчета путей всех входящих сигналов, что делает а анализ слишком затратным, а прореживание бессмысленным.

Утвериедение 1

В процессе выполнения алгоритма для комбинационных схем в корректной схеме (схеме, не содержащей циклов) этап распространения событий выполнится для каждого элемента схемы

6Blaamv S., Zolotov D., Sundareswaran V. Slope Propagation in Static Timing Analysis // Proceedings of the 2000 IEEE/ACM international conference on CAD. 2000 r.

10

Утверждение 2

Корректность алгоритма для комбинационных схем

Пусть v¡...vn - критический путь в комбинационной схеме, от входа V/ к некоторой вершине у„, тогда в рамках работы предложенного алгоритма будет создан критическая путь е/... е„, такой, что у(е1)= V/... у(еп)= у„.

В данной главе показывается оценка сложности предлагаемого алгоритма

Сложность алгоритма складывается из сложностей его составных частей. Пусть количество достижимых элементов в схеме N. Как было сказано ранее, инициализация счетчиков занимает намного меньше времени, чем расчет схемы. Во время второго этапа алгоритма каждый элемент вычисляется только один раз, таким образом, сложность равна О(Ы).

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

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

Алгоритм для комбинационных схем

^^ Триггеры, с измененными событиями ^^

Распространение событий на триггерах

^^ Список элементов с новыми ^^_событиям на входе_

Рисунок 3 Алгоритм поиска критических путей в задаче статического моделирования временных характеристик схем с триггерами

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

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

1-я итерация. Анализ комбинационной логики.

|тП

1-я итерация. Активизация триггеров Т1, ТЗ, Т4.

Т1

Т2

ТЗ

ОЙ-СИ

Т4

2-я итерация. Активизация триггеров Т2 и 2-я итерация. Анализ Т5 На одном из выходов Т5 обнаружен комбинационной логики. цикл

3-я итерация. Активизация триггеров ТЗ и Т4. Новых событий на комбинационной логике не появляется.

3-я итерация. Анализ комбинационной логики.

Комбинационная логика Триггер

I-1 «Активные» элементы I____) Запрещенный триггер

— I-> (распространение худших событий)

Рисунок 4. Пример работы алгоритма для схем, содержащих триггеры

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

схемы. Для доказательства корректности доказываются утверждения, из них ключевые:

Утверждение 3

Доказательство корректности алгоритма для последовательных схем

Пусть v/...v„ -критический путь на схеме, не содержащей критических циклов временном графе последовательной схемы, от входа V; к некоторой вершине v„. Тогда в рамках работы алгоритма для последовательных схем будет создан критический путь е/...е„, такой, что v(e1)= Vi...\'(en)= v„.

Также доказывается сходимость алгоритма:

Утверждение 4

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

В Главе исследуется сложность предлагаемого метода. Сложность итерации оценивается как 0(N+M), где N - количество элементов комбинационной логики, а М — количество триггеров. Количество итераций алгоритма равно числу триггеров L в самом длинном критическом пути схемы. Следовательно, суммарная сложность алгоритма - 0((N+M)*L).

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

Параллельная реализация представляет собой несколько параллельных циклов созданных при помощи примитивов Intel© Threading Building Blocks. Алгоритмы реализованы с помощью шаблона parallel_do библиотеки Intel© Threading Building Blocks. Данный шаблон позволяет добавлять задачи в общий

пул, откуда они с помощью планировщика задач распределяются по потокам. В качестве задачи выступает распространение событий на одном элементе и через исходящие из данного элемента межсоединения дальше, на элементы входы которых соединены с выходом анализируемого элемента. Анализ элемента производится с помощью библиотеки численных методов моделирования задержки RICE (описание примитивов Intel© Threading Building Blocks описано в Приложении 1) В алгоритме для последовательных схем помимо параллелизации расчета комбинационной части также возможно параллельно выполнять расчет триггеров на этапе распространения событий на триггерах. На этом этапе нет зависимости по данным, и синхронизация не требуется. Таким образом можно использовать шаблон tbb::parallel_for для параллельного выполнения распространения событий. Шаблон tbb::paralIel_for позволяет параллельно выполнить наперед заданное количество задач (количество триггеров, на которых изменились события на входах нам известны). Как отмечалось в описании алгоритма, распространение событий через выходы схемы также можно выполнять параллельно. Поскольку количество выходов элемента заранее известно, то можно использовать шаблон tbb::parallel_for для параллельного распространения событий.

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

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

Была показана хорошая балансировка загрузки и приемлемый минимальный размер задачи. В результате экспериментов удалось установить, что 95% задач имеют время выполнения, превосходящее требуемое разработчиками системы Intel© Threading Building Blocks.

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

Ускорение Ускорение

число потоков

Рисунок 5 Ускорение алгоритма на различном числе потоков

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

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

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

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

г _ Трбщ

вычисляется как i>rnax — ^-

*критич

В главе показана зависимость максимального ускорения от размера схемы для различных типов схем: Произвольная (нерегулярная) логика, Схемы потоковый обработки данных, схемы памяти (регистры, ROM)

Максимальное ускорение 1000

100

■ Память

Потоковая обработка данных Произвольная логика

500

5000

50000

500000

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

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

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

достигнутое большее ускорение, чем на схеме, обладающей меньшим максимальным ускорением.

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

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

« 20

о ¡г

? 15

о с

чо

10

я

I

<и

а. §

2

10 100

Максимальное потенциальное ускорение

1000

Рисунок 7 Зависимость между максимальным и реальным ускорением

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

В Заключении сформулированы результаты, выносимые на защиту:

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

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

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

Публикации по теме диссертации

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

2. Князев H.A. Малинаускас К.К. "Алгоритмы поиска критических путей в задаче статического временного анализа СБИС // Журнал «Информационные Технологии» №11, 2012, г.Москва С. 2-9

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

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

Подписано в печать 12.09.2013. Формат 60x84/16. Усл. печ. л. 0,9. Тираж 75 экз. Заказ П-60. ИПМ им.М.В.Келдыша РАН. 125047, Москва, Миусская пл., 4

Институт Прикладной Математики имени М.В.Келдыша Российской Академии Наук

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

04201362392

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

общей памятью

Специальность 05.13.18 Математическое моделирование, численные методы и

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

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

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

доктор физико-математических наук М.В.Якобовский Научный консультант:

кандидат физико-математических наук К.К.Малинаускас

Москва 2013

Содержание

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

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

Введение...........................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий случай............................................................................23

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф работ..................................................................................................76

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

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

Выводы.......................................................................................................82

Заключение.....................................................................................................83

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

Приложение 1.................................................................................................87

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

Приложение 2.................................................................................................89

Введение

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

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

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

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] представлен полиномиальный алгоритм выделения множества путей в схеме с задержками, превышающими некоторое заранее заданное пороговое значение, этот метод не предполагает выявление критических путей, а находит все пути удовлетворяющие условию. Основа всех методов СВА -распространения событий (изменения уровня сигнала в узле схемы). События распространяются по временному графу, где вершинами являются узлы схемы, а ребра соответствуют причинно-следственным связям между возможными событиями в узлах. Последовательность порождающих друг друга событий называется временным путем. Задачей временного анализа, таким образом, явл�