Современный научно-технический прогресс характеризуется внедрением во все области человеческой деятельности радиоэлектронной аппаратуры. Известно, что 40% мирового производства занято выпуском такой техники. Основным узлом радиоэлектронной аппаратуры являются большие интегральные схемы (БИС), постоянные запоминающие устройства (ПЗУ), программируемые логические матрицы (ПЛМ), базовые матричные кристаллы (БМК) и т. д. Процессы проектирования и изготовления интегральных схем являются наиболее автоматизированными.
За период нескольких десятилетий установился процесс проектирования микросхем, ставший традиционным. Считается, что процесс проектирования включает этапы схемотехнического, логического и топологического проектирования. На стадии топологического проектирования решается задача трассировки цепей соединения всех полупроводниковых элементов. Если учесть, что количество элементов достигает миллионов, то станет ясным, масштаб этой проблемы. Она решается путем создания множества алгоритмов трассировки, которые учитывают ту или иную специфику схемы, а также увеличения сроков проектирования до нескольких месяцев, соблюдая тщательность проектирования. Поэтому разработка алгоритмов, которые хотя бы на несколько процентов ускоряют или качественно улучшают решение задачи трассировки, является актуальной.
Таким образом, целью работы является разработка и исследование новых методов трассировки интегральных схем. Для реализации такой цели необходимо решить следующие научные задачи:
1. Провести анализ существующих алгоритмов трассировки, определить их эффективность в зависимости от специфики задачи.
2. Провести анализ существующих моделей данных различных алгоритмов трассировки.
3. Разработать принципы построения алгоритма трассировки, который будет иметь лучшие эксплутационные характеристики по сравнению с существующими классическими алгоритмами.
4. Разработать алгоритм трассировки, который после реализации будет иметь эксплутационные характеристики более лучшие чем классические алгоритмы.
5. Разработать модель представления данных в канале трассировки, учитывая специфику предлагаемого алгоритма разводки цепей.
6. Провести макетирование основных блоков алгоритма трассировки и сделать оценку эксплутационных характеристик.
Практическая ценность результатов работы позволит:
• ускорить и повысить качество разработки БИС;
• улучшить эксплуатацию программы проектирования БИС.
В результате проделанной работы на защиту выносятся:
1. Результаты анализа существующих алгоритмов трассировки, оценка их эффективности в зависимости от вида применения БИС в электронной вычислительной аппаратуре.
2. Разработанная модель представления объектов в канале, базирующаяся на моделях классических волнового и канального алгоритмов, и учитывающая особенности конструктива кристалла и разрабатываемого алгоритма.
3. Разработанный, так называемый Направленный Волновой Алгоритм (НВА) для канальной модели данных, который обеспечивает: нахождение пути, если его построение возможно, проведение оптимизации по длине пути и числу поворотов (межслойных переходов).
4. Включенный в НВА блок итеративной трассировки, который эвристическим методом изменяет порядок трассировки цепей.
5. Результаты макетирования основных блоков и оценка эксплутационных характеристик данного алгоритма.
Диссертация является законченной научно-исследовательской работой.
Краткое содержание работы сводится к следующему.
В первой главе «Анализ разновидностей и методов трассировки БИС» описываются стандартные, полузаказные и заказные микросхемы. К стандартным БИС относятся:
• микросхемы широкого применения (микропроцессоры, оперативные запоминающие устройства;
• микросхемы программируемые перед эксплуатацией (программируемые логические матрицы, постоянные запоминающие устройства).
Стандартные БИС характеризуются регулярностью структуры, простой конфигурацией соединений на уровне дискретных элементов, поэтому в этом случае задача трассировки не является актуальной.
Полузаказные БИС характеризуются тем, что имеют общие части в своей структуре, которые проектируются заранее (стандартные модули). Затем данные модули дорабатываются в соответствии с применением. К этим БИС относятся постоянные запоминающие устройства, программируемые логические матрицы и базовые матричные кристаллы (совокупность базовых элементов, из которых проектировщик может создать нужную схему). Задача трассировки полузаказных БИС требует раскрытия противоречия между числом базовых элементов и оставшейся площадью для трассировки, а также числом контактных площадок для внешних выводов.
Заказные БИС определяются полностью заказчиком и следовательно, каждая разновидность микросхемы такого типа требует полного цикла проектирования. Существует несколько методов проектирования.
1. Метод «стандартных ячеек». Существует набор стандартных ячеек, которые можно расположить на кристалле в виде рядов. У проектировщика имеется свобода в расположении ячеек и соединении их в схему с целью минимизации площади БИС и длины всех проводников.
2. Метод «блочного типа». Проектирование производится «сверху — вниз». Каждый уровень блоков определяется проектировщиком различных размеров. В отличие от предыдущего метода, где соблюдается регулярность в размещении ячеек, здесь ячейки могут находиться на произвольных местах.
Проведенный анализ основных алгоритмов трассировки соединений позволяет различить два подхода.
1. Группа графо-теоретических подходов.
2. Группа топографических методов.
Т.к. группа графо-теоретических подходов не пригодна для проектирования БИС большой интеграции, то все внимание уделено топографическим методам, которые состоят из следующих этапов:
• формирование списка соединений,.
• определение порядка сортировки соединений,.
• трассировка,.
• распределение соединений по слоям.
Анализируются следующие алгоритмы.
1. Волновой алгоритм. Коммутационное поле разбивается на блоки, в которых обозначаются ячейки. От источника до приемника поэтапно волнообразно распространяется числовой фронт. Направление распространения задается определенными критериями. По достижении цели строится путь.
2. Магистральный метод. Коммутационное поле представляется совокупностью горизонтальных и вертикальных магистралей. Поиск пути от заданного источника до приемника проводится посредством переходов с одной магистрали на другую. Направление определяется эвристически с целью уменьшения числа перебора.
3. Лучевой алгоритм. Основная идея этого метода состоит в циклическом повторении шагов:
• продвижение в оптимальном направлении;
• выявление препятствий и их обход.
4. Канальный метод. Основным элементов является канал, как замкнутое, прямоугольной формы пространство. Трассировка проводится в два этапа. На первом этапе определяются каналы по которым будут проходить цепи. На втором этапе разводятся все цепи, направленные через те или иные каналы.
5. Итерационные алгоритмы трассировки и алгоритмы, использующие деформацию трасс соединений Основой их являются рассмотренные ранее алгоритмы, но несколько модернизированные. Их особенность заключается в том, что каждая трасса строится путем итерационного применения определенного алгоритма. Каждый новый шаг прокладывает очередной участок учитывая влияние других разводимых цепей.
В этой главе проводится анализ преимуществ и недостатков всех рассмотренных методов. Констатируется, что в большинстве методов существуют эвристические правила, уменьшающие перебор вариантов. Делается вывод о том, что создание улучшенного алгоритма возможно путем комплексного применения всех методов.
Во второй главе «Подсистема проектирования БИС блочной структуры» рассматривается программный комплекс, в котором применяется разрабатываемый алгоритм разводки цепей. Вводятся понятия: функциональный блок (ФБ), канал и шлюз. Работа программы топологического проектирования начинается с размещения ФБ на рабочем поле кристалла, далее выполняется разбиение свободного для трассировки пространства на каналы, трассировка и распределение соединений по слоям (расслоение).
Для лучшего понимания на Рисунок 8 приведены все элементы, которым даны термины.
На этапе размещения ФБ располагаются на кристалле таким образом, чтобы уменьшить общую длину трассируемых позже цепей. Трассировка соединений осуществляется на первом этапе как глобальная, а затем локальная. Алгоритм глобальной трассировки определяет маршрут прохождения очередной цепи через каналы, затем закрепляются точки пересечения цепью границы канала на шлюзе. Локальная трассировка осуществляет во всех каналах перебор всех цепей и определение их конкретного размещения в канале. Основной алгоритм локальной трассировки использует параллельное разведение цепей. Но так как при этом используется эвристический алгоритм, данный метод не гарантирует полной прокладки цепей, даже если путь для проводников существует. Повысить процент разводимых цепей возможно за счет дополнительного использования других методов трассировки, а точнее их эвристик. Такая попытка сделана в данной работе. Основным требованием к разрабатываемому алгоритму, являющемуся конечной целью данной работы, является гарантированная трассировка всех цепей, если путь, при данной конфигурации уже проложенных соединений, существует. При этом все цепи должны строится с возможно меньшим числом поворотов и возможно меньшей длиной. Такой алгоритм будем называть регулярным.
Глава третья «Регулярный алгоритм локальной трассировки» описывает постановку задачи, вводимые требования, разработанную модель данных и алгоритм трассировки. Исходной информацией для разрабатываемого алгоритма является описание канала, блоков, шлюзов, описание разведенных цепей в канале, координаты контактов и описание ранее проложенных участков, принадлежащих разводимой цепи.
Задачей регулярного алгоритма трассировки является построение квазиоптимального дерева Штейнера в ортогональной метрике, с учетом ограничений, связанных с конкретной конструкторской реализацией СБИС.
Исходя из того, что проектируемые заказные БИС имеют нерегулярную структуру, в канале располагается определенное множество уже проложенных соединений, процесс трассировки цепей целесообразно представить как задачу поиска пути в лабиринте. Таким образом, делается вывод, что алгоритм трассировки является комбинаторным алгоритмом.
В данной главе обосновывается преимущество предложенной магистральной модели описания канала в отличие от классической дискретной или магистральной модели данных. Основные особенности используемой модели данных заключаются в следующем:
• Канал представляется как совокупность горизонтальных и вертикальных участков.
• Канал однозначно описывается как совокупность свободных участков магистралей (СУМ) и контактов. Поиска пути организуется посредством анализа СУМ.
• Соприкасающиеся СУМ одного направления, одинаковой длины и единичной толщины объединяются в единый блок, равный по ширине количеству объединяемых свободных отрезков. Таким образом алгоритм оперирует блоками, которые в общем случае могут иметь толщину больше или равную 1. В дальнейшем они будут именоваться СУМ.
Введенные усовершенствования позволили значительно уменьшить мощность множества элементов, описывающих данные в канале.
Для работы алгоритма создаются два списка: список «источники» и список «приемники», куда заносятся все контакты разводимой цепи и разведенные участки. Выбор источника из общего списка контактов выполняется по принципу: источник должен быть одиночным контактом. Обоснование этого правила, влияющего на скорость работы алгоритма приводится в данной главе.
Разработанный регулярный алгоритм трассировки состоит из двух этапов — прямой и обратный ход.
Зная направление движения от источника к приемникам происходит проход по СУМ, аналогично поиску пути в лабиринте. Направление поиска устанавливается динамически во время работы алгоритма, учитывая взаимное расположение текущей точки анализа и ближайшего приемника. Процесс поиска заключается в последовательном переборе еще не анализировавшихся СУМ. При этом свободные участки отмечаются числами, характеризующими этап хода вперед. В данной главе обосновывается утверждение, что если путь от источника до приемника существует, то алгоритм его найдет.
Реализуемый алгоритм хода вперед имеет следующие положительные характеристики.
• Реализован поиск на графе в глубину, а не в ширину.
• На данном этапе применяется ряд эвристических правил, способствующих более «интеллектуальному» и направленному поиску. В частности определяется область притяжения определенного приемника, который и устанавливается, как целевой.
• В случае захода в тупик реализован алгоритм «отката назад» посредством стека, где находится информация о ранее анализировавшихся участках. При этом восстанавливается информация о текущем состоянии и направлении обхода отрезка.
Как и в любом комбинаторном алгоритме, который использует определенные эвристические правила и не выполняет перебор всех возможных вариантов, в нашем случае нет гарантии нахождения самого оптимального решения. Обратный ход обеспечивает процесс оптимизации длины пути за счет спрямления излишних изгибов трассы, полученных в результате поиска пути в лабиринте СУМ. Данная операция заключается в обратном проходе по определенной цепочке СУМ от приемника к источнику. При этом участкам назначается определенный ранг по которому и идет оптимизация. Также введен ряд улучшений, необходимых для обработки специальных ситуаций в канале трассировки.
В диссертации дано подробное описание работы алгоритма трассировки.
В четвертой главе «Практическая реализация регулярного алгоритма трассировки БИС блочной структуры» дается описание разработанного комплекса программ на языке С++ в системе Borland С++ с использованием принципов объектно-ориентированного программирования.
В главе пятой «Пути повышения эффективности работы регулярного магистрального алгоритма» предлагаются дальнейшие шаги по повышению эффективности подсистемы трассировки. Все они требуют дальнейшего усложнения алгоритмов нахождения пути и алгоритмов оптимизации полученной трассы. Однако, принимая во внимание развитие вычислительной техники можно уверенно говорить о перспективности этих усовершенствований.
Глава шестая «Экспериментальные результаты тестирования магистрального регулярного алгоритма» включает в себя показатели эффективности применения разработанных эвристик. Проведенные эксперименты показали:
1. Используемая в алгоритме разработанная магистральная модель данных по сравнению с волновой дает значительную экономию по используемой памяти и временным затратам.
2. Разработанный магистральный метод по сравнению с традиционным волновым позволяет существенно сократить число поворотов у разведенных цепей и ускорить процесс поиска решения, применительно к данному конструктиву СБИС.
3. Построение модели канала производится один раз перед трассировкой, независимо от количества разводимых цепей. При работе происходит только настройка информации в модели данных. Это способствует уменьшению общего времени работы алгоритма.
4. При поиске пути за счет применения эвристических правил навигации в канале и обхода пересекающих участков на один-два порядка уменьшается время работы данного блока алгоритма.
5. Время работы разработанного алгоритма трассировки слабо зависит от размеров канала и расстояния между контактами.
6. Применение «рамок» при обратном ходе уменьшает время обратного хода на порядок.
Проверка системы трассировки на опытных образцах показала эффективность разработанного алгоритма трассировки и модели описания канала.
ВЫВОДЫ:
1. Используемая в алгоритме разработанная магистральная модель данных по сравнению с волновой дает значительную экономию по используемой памяти и временным затратам.
2. Разработанный магистральный метод по сравнению с традиционным волновым позволяет существенно сократить число поворотов у разведенных цепей и ускорить процесс поиска решения.
3. Построение модели канала производится один раз перед трассировкой, независимо от количества разводимых цепей. При работе происходит только настройка информации в модели данных. Это способствует уменьшению общего времени работы алгоритма.
4. При поиске пути за счет применения эвристических правил навигации в канале и обхода пересекающих участков на один-два порядка уменьшается время работы данного блока алгоритма.
5. Время работы разработанного алгоритма трассировки слабо зависит от размеров канала и расстояния между контактами.
6. Применение «рамок» при обратном ходе уменьшает время обратного хода на порядок.
Полученные экспериментальные результаты доказывают эффективность внесенных усовершенствований и выбранных методов и применимость разработанной системы трассировки для промышленного применения.
В тоже время, автор видит пути дальнейшего улучшения данной системы, которые описаны в главе 5. Данные усовершенствования требуют прежде всего использования более современной вычислительной техники.
Глава 7 Заключение.
Перед автором данной работы была поставлена задача разработки, программной реализации и исследования регулярного алгоритма трассировки заказных БИС блочной структуры и модели данных для его работы.
1. Проведен анализ существующих алгоритмов трассировки соединений для разных типов конструктивов СБИС, оценены их особенности и эффективность. Сделан вывод о необходимости комбинированного применения нескольких методов трассировки, использования поэтапного определения топологии.
2. Разработана модель представления топологии в канале. В основе данной модели лежат блоки, в общем случае не единичной толщины, свободные для трассировки.
3. Предложены методы работы с объектами в модели имитирующие построение множества свободных блоков для определенной разводимой цепи, добавления новых отрезков цепи, расщепления свободных блоков.
4. Показана эффективность применения свободных блоков, с точки зрения минимизации времени требуемого на трассировку и памяти отводимой для данных.
5. Проведена разработка Направленного Волнового Алгоритма (НВА) базирующегося на полученной модели данных, который производит направленный поиск приемников, с целью построения цепи. Данный алгоритм обеспечивает построение соединения, если путь существует, при данном расположении проводников, причем построенная цепь проходит оптимизацию по длине и числу поворотов. В НВА происходит поиск в глубину по гипотетическому дереву переходов. Реализован возврат назад в случае обнаружения тупика.
6. Предложены эвристические правила определения направления поиска приемников. Данные правила строятся на информации о взаимном расположении приемников и текущего анализируемого блока, загруженности определенных областей канала ранее разведенными цепями и т. п.
7. Предложенная система трассировки и модель данных были практически реализованы и доведены до промышленного использования в общей автоматизированной системе проектирования заказных СБИС блочного типа. При практической реализации применялся объектно-ориентированный подход разработки программного кода. Были внесены определенные предложения, касающиеся более оптимальной практической реализации алгоритма.
8. По результатам практического макетирования построенной системы трассировки были выполнены статистические исследования, направленные на обоснование эффективности предложенных эвристических правил трассировки и модели данных.
9. Предложены пути дальнейшего развития алгоритма трассировки направленные на увеличение скорости работы системы с большими микросхемами так и на построение более оптимальных соединений.
Глава 8 Экономическое обоснование работы.
Программная реализация регулярного алгоритма трассировки является частью САПР заказных БИС, разработанной в НПО «Импульс» и предназначается для трассировки соединений, неразведенных канальным методом. Таким образом, данные соединения обрабатываются не вручную оператором, а с помощью разработанного алгоритма. За счет этого достигается экономия времени проектирования БИС.
Конкретный экономический эффект от внедрения программы доразводки цепей на данном этапе определить затруднительно, т. к. разработка САПР заказных БИС закончилась недавно и в настоящий момент нет статистических данных, характеризующих трудоемкость проектирования заказной БИС с помощью этой системы. Поэтому ниже будет дана оценка экономии времени не для всего этапа проектирования БИС, а лишь для одного вызова локального трассировщика.
Общее количество цепей БИС, неразведенных канальным методом, зависит от различных параметров проектируемой БИС (количество цепей, размеры БИС и т. д.) и от качества выполнения этапов, предшествующих локальной трассировке, т. е. этапов размещения функциональных блоков и глобальной трассировки (результаты автоматического выполнения данных задач могут дорабатываться оператором вручную). Среднее число неразведенных канальным методом цепей для БИС, упоминаемых в экспериментальных результатах, составляет 13−18 штук. Среднее время разводки соединения составляет: вручную — около 4 минут, магистральным методом — около I минуты. Таким образом, экономия времени для одного этапа выполнения локальной трассировки составляет примерно 40−50 минут.
Как упоминалось ранее, топологическое проектирование заказной БИС является итеративным процессом, т. е. задача локальной трассировки цепей выполняется несколько раз за все время проектирования БИС. Поэтому для определения общей экономии времени от внедрения программы доразводки необходимо умножить £ГЛ на количество вызовов локального трассировщика:
К = ** * •.
Уменьшение времени проектирования БИС позволяет уменьшить себестоимость проектирования за счет снижения следующих расходов:
• заработная плата производственных рабочих на единицу продукции (заказная БИС);
• затраты на электроэнергию на единицу продукции;
• расходы на содержание и эксплуатацию оборудования (ЭВМ, графопостроитель, принтер) на единицу продукции.
Кроме того, более быстрое проектирование БИС с помощью разработанной САПР способствует завоеванию рынка заказов от производителей микросхем.
Глава 9 Техника безопасности.
Практическая реализация разработанного алгоритма является программным продуктом, поэтому при ее эксплуатации необходимо соблюдать общие правила техники безопасности при работе с ЭВМ:
I. Защита от поражения электрическим током. Необходимо эксплуатировать только исправный компьютер, снабженный заземлением.
II. Защита от вредных излучений. Необходимо обеспечить каждый монитор защитным экраном и соблюдать допустимую дистанцию оператора ЭВМ от монитора.
III. Общие требования к работе с компьютером:
A. использование монитора с возможно лучшими техническими показателями (тип монитора, размер пикселя, частота регенерации изображения и т. д.).
B. соблюдение режима работы оператора за компьютером.
C. создание максимально комфортного и эргономичного рабочего места оператора.
