Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПОДСИСТЕМЫ САПР СФ-БЛОКОВ СБИС НА ОСНОВЕ МЕМРИСТОРОВ

Кулаков А.А. 1 Ковалев А.В. 1 Затылкин А.В. 2
1 ФГАОУ ВПО «Южный федеральный университет»
2 ФГБОУ ВПО «Пензенский государственный университет»
В работе рассмотрены основные проблемы реализации подсистемы САПР сложно-функциональных блоков сверхбольших интегральных схем с мемристорами, предложен модифицированный маршрут проектирования, рассмотрены особенности формирования блоков с мемристорами. Принципиальное отличие СФ-блоков c мемристорами состоит в большом количестве связей между логическими элементами схемы, а также в наличии блоков управления мемристорами, влияющими на габариты размещаемых элементов таким образом, что использовать методику проектирования размещения на основе стандартных ячеек не представляется возможным. Для решения задачи размещения разногабаритных блоков с мемристорами предложен генетический алгоритм с кодированием перестановок, имеющий допустимую временную сложность. Разработана подсистема САПР, сочетающая в себе объектно-ориентированный программный интерфейс и аналитическую подсистему, позволяющую визуализировать данные и проводить оценку качества работы алгоритмов.
автоматизация проектирования интегральных схем
сложно-функциональные блоки
мемристоры
1. Бакало М.А., Курейчик В.В. Модифицированный алгоритм размещения методом парных перестановок // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». – 2007. – С. 77–84.
2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учебное пособие / под ред. В.М. Курейчика. – М.: Физматлит, 2004. – 400 с.
3. Биоинспирированные методы в оптимизации / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик, П.В. Сороколетов. – М.: ФИЗМАТЛИТ, 2009. – 384 с.
4. Иванова Е.Н. Системы проектирования. Тенденции мирового рынка САПР СБИС // Электроника: Наука, Технология, Бизнес. – 2006. – № 2.
5. Курейчик В.В., Сороколетов П.В. Концептуальная модель представления решений в генетических алгоритмах // Известия ЮФУ. Технические науки. – 2008. –№ 9 (86). – С. 7–12.
6. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи размещения на основе эволюционного моделирования // Известия РАН. Теория и системы управления. – 2007. – № 4. – С. 78–90.
7. Норенков И.П. Основы автоматизированного проектирования / И.П. Норенков. – М.: Изд-во МГТУ имени Н.Э. Баумана, 2006. – 448 с.
8. Adya S.N., Yildiz M., Markov I.L., Villarrubia P.G., Parakh P.N., Madden P.H. Benchmarking for large-scale placement and beyond. In Proceedings of the International Symposium on Physical Design. ACM, Monterey, 95–103. – 2003.
9. Chua L.O. Memristor – the missing circuit element // IEEE Transactions on circuit theory. – 1971. – Vol. 18. – № 5. – P. 507–519.
10. Jason Cong, Joseph R. Shinnerl, Min Xie, Tim Kong, Xin Yuan. Large-Scale Circuit Placement. ACM Transactions on Design Automation of Electronic Systems. April 2005. – Vol. 10. – № 2,.
11. Strukov D.B. Gregory S. Snider, Duncan R. Stewart, R. Stanley Williams. The missing memristor found // Nature. – 2008. – Vol. 453. – P. 80–83.

Современные сверхбольшие интегральные схемы (СБИС), реализуемые по идеологии «система на кристалле», представляют собой совокупность интегрированных на кристалле взаимосвязанных сложно-функциональных блоков (СФ-блоков, IP-cores), каждый из которых выполняет определённую функцию.

Для проектирования СФ-блоков СБИС в настоящее время используются системы автоматизированного проектирования (САПР), поставляемые компаниями Cadence Design Systems, Synopsis, Mentor Graphics и др. [4], которые изначально не обладают возможностью синтеза блоков с мемристорами.

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

1. Маршрут проектирования

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

Исходные данные для подсистемы представляются в формате EDIF. Выбор формата EDIF обусловлен широтой его применения в существующих EDA (Electronics Design Automation) для описания топологии СБИС [7]. Он удобен для передачи данных, включающих списки соединений, параметры cхемы, спецификации тестовых наборов, результаты моделирования и т.п.

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

На втором этапе производится размещение элементов СФ-блока на коммутационном поле.

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

рис_105.tif

Рис. 1. Маршрут проектирования подсистемы САПР СФ-блоков СБИС с мемристорами

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

На пятом этапе производится общая оценка габаритов и расстановка внешних контактных площадок. По результатам данного этапа принимается решение о синтезе файлов GDSII или CIF для передачи на производственный цикл или повторной итерации проектирования.

Подсистема синтезирует решение задач этапа конструкторского проектирования СФ-блоков в виде топологии в формате GDSII или CIF на выбор пользователя.

Рассмотрим основные особенности разработки подсистемы САПР СФ-блоков СБИС с мемристорами.

Мемристор – пассивный элемент, электрическое сопротивление которого зависит от приложенного ранее напряжения. Основополагающая работа в области теории пассивных элементов с эффектом памяти, в которой было введено понятие «мемристор», была опубликована в 1971 году [9]. Однако данная концепция оставалась чисто теоретической до демонстрации в 2008 году экспериментальной модели мемристора сотрудниками Hewlett-Packard [11].

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

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

2. Процедура размещения разногабаритных элементов
СФ-блоков СБИС

Задача размещения является одним из наиболее важных шагов в процессе проектирования СБИС, поскольку она определяет межсоединения, которые к настоящему времени стали «узким местом», определяющим производительность субмикронных интегральных схем [10].

Задача размещения разногабаритных элементов СФ-блока формулируется следующим образом. Для каждого размещаемого элемента ei заданы его габаритные размеры (длина ai , ширина bi), множество контактов Ci, через которые элемент сопрягается с другими элементами схемы, ориентация элемента oi: горизонтальная «0», вертикальная «1». Каждый контакт определяется координатами (x, y) и номером подключаемой к нему цепи tj [5].

Математической моделью описанной задачи является гиперграф G = (X, U, P) , где X = {xi|i = 1, 2, ..., n} – множество вершин, моделирующих элементы; U = {uj|j = 1, 2, ..., m} – множество гиперребер, моделирующих цепи; P – инцидентор, заданный на множестве X×U и равный 1, если uj инцидентно xi, или 0 в противном случае.

Расстояние между двумя элементами (xi, yi) и (xj, yj) в случае проведения проводников по каналам или магистралям, параллельным координатным осям коммутационного поля, определяется по формуле:

Eqn60.wmf

В качестве оценки длины цепи ti, моделируемой гиперребром uj, используется длина минимального связывающего дерева, построенного на множестве вершин xi ∈ X.

Необходимо найти некоторый вариант размещения элементов на коммутационном поле СФ-блока zj = {(x1, y1, o1), ..., (xi, yi, oi), ..., (xn, yn, on)} , где xi, yi – координаты базовой точки, а oi – ориентация элемента ei для данного размещения. При этом перекрытие размещенных элементов не допускается, а суммарная длина соединений и площадь, занятая конструкцией, должна быть минимальна.

Задача размещения является многокритериальной, поэтому для оценки качества полученного решения используется аддитивный критерий [5]:

Eqn61.wmf

где zj – некоторый вариант размещения; k1, k2, k3 – весовые коэффициенты, причем k1 + k2 + k3 = 1; L(zj) – суммарная длина межсоединений; O(L(zj)) – нормированная оценка общей длины соединений, приведенная к интервалу [0, 1]; Sобщ – фактическая площадь размеще-
ния, определенная как площадь минимального прямоугольника, описываю-
щего размещенные элементы; P(Sобщ(zj)) –
нормированная оценка общей площади размещения, приведенная к интервалу [0,1];
D(Tобщ) – нормированное значение задержки
сигналов.

Таким образом, задача размещения состоит в нахождении размещения z, минимизируюшего F.

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

Для решения многокритериальной задачи размещения при проектировании СФ-блоков СБИС в работе предлагается использовать генетический алгоритм (ГА).

Общее описание работы ГА для решения задач оптимизации дано в работах
[2, 6], мы же остановимся подробно на способе представления (кодирования) варианта размещения для данной задачи. Кодировать координаты элементов в хромосоме нецелесообразно, поскольку применение операторов случайных изменений будет приводить к образованию некорректных решений, в которых отдельные элементы будут накладываться друг на друга. Для задания размещения достаточно определить порядок следования элементов при их размещении, а их конкретные координаты будут определены при интерпретации данной последовательности. Для задачи размещения будем использовать способ «кодирования перестановок» [1]. Для представления некоторого размещения используются две хромосомы: числовая хромосома для задания последовательности размещаемых элементов и двоичная хромосома для задания ориентации размещаемых элементов. Процедура (де)кодирования в этом случае имеет линейную временную сложность O(n). В качестве генетических операторов используются простые генетические операторы кроссинговера и мутации, также имеющие сложность O(n).

Описанный способ представления размещения разногабаритных элементов позволяет размещать до 106 элементов с использованием иерархического разбиения. Временная сложность предложенного алгоритма размещения элементов СФ-блока составляет O(n2).

рис_106.tif

Рис. 2. Интерфейс разработанной подсистемы САПР СФ-блоков СБИС с мемристорами

3. Программная реализация

Подсистема САПР СФ-блоков СБИС с мемристорами разработана в среде Microsoft Visual Studio 2010 C# и работает под управлением OC семейства Windows или Linux (Mono). Реализованная подсистема (рис. 2) сочетает в себе объектно-ориентированный программный интерфейс и аналитическую подсистему, позволяющую визуализировать данные и проводить оценку качества работы алгоритмов. Такой подход обеспечивает удобство проектирования сложно-функциональных блоков СБИС, содержащих сотни тысяч элементов. Основной исполняемый файл представляет собой приложение, которое реализует требуемый маршрут проектирования, получая на вход данные о СБИС и сохраняя все результаты в файлы требуемого формата.

Заключение

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

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

Работа выполнена при финансовой поддержке Министерства образования и науки Российской Федерации (гос. соглашение № 14.A18.21.0107) в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы.

Рецензенты:

Агеев О.А., д.т.н., профессор, директор Научно-образовательного центра «Нанотехнологии» Южного федерального университета, г. Таганрог;

Рындин Е.А., д.т.н., профессор, ведущий научный сотрудник Южного научного центра Российской академии наук (ЮНЦ РАН), г. Ростов-на-Дону.

Работа поступила в редакцию 16.10.2012.


Библиографическая ссылка

Кулаков А.А., Ковалев А.В., Затылкин А.В. РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПОДСИСТЕМЫ САПР СФ-БЛОКОВ СБИС НА ОСНОВЕ МЕМРИСТОРОВ // Фундаментальные исследования. – 2012. – № 11-2. – С. 420-424;
URL: https://fundamental-research.ru/ru/article/view?id=30550 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674