Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

RESEARCH AND DEVELOPMENT OF MEMRISTOR BASED VLSI IP-CORES CAD

Kulakov A.A. 1 Kovalev A.V. 1 Zatylkin A.V. 2
1 Southern Federal University
2 Federal state budgetary educational institution of Higher Education Penza State University
This paper describes the electronic design automation problems of very-large-scale integrated circuits IP cores (IP blocks) with memristors. IP cores with memristors features and capabilities are explored and the modified design flow is proposed. The principal difference between IP blocks with memristors is a large number of connections between the logical elements of the scheme, as well as in the presence of the memristors control units affecting the size of scheme elements. That elements are placed in such a way that usage of standard cells design methodology is not possible. We have explored the use of modified genetic algorithm with coding permutations to solve placement problem of varied-dimension element blocks, algorithm’s time complexity is O(n2). Developed design automation software combines object-oriented programming interface and analysis toolkit allowing to visualize the data and to estimate the quality of the algorithms.
electronic design automation
ip-cores
memristors
1. Bakalo M.A., V.M. Kureichik, V.V. Kureichik. Modificirovannyjj algoritm razmeshhenija metodom parnykh perestanovok // Izvestia TRTU. Tematicheskijj vypusk «Intellektual’nye SAPR». 2007, pp. 77–84.
2. Gladkov L.A., Kureichik V.V., Kureichik V.M. Geneticheskie algoritmy.: Uchebnoe posobie / Pod red. V.M. Kureichika. Moscow, Fizmatlit, 2004. 400 p.
3. Gladkov L.A., Victor M. Kureichik, V.V. Kureichik, P.V. Sorokoletov Bioinspired methods in the field of optimization. Moscow, Physmatlit, 2009.
4. Ivanova E.N. Sistemy proektirovanija. Tendencii mirovogo rynka SAPR SBIS // Ehlektronika: Nauka, Tekhnologija, Biznes, no. 2, 2006.
5. Kureichik V.V., Sorokoletov P.V. Konceptual’naja model’ predstavlenija reshenijj v gene-ticheskikh algoritmakh // Izvestija JuFU. Tekhnicheskie nauki. 2008. no. 9 (86). pp. 7–12.
6. Kureichik V.M., Lebedev B.K., Lebedev O.B. Reshenie zadachi razmeshhenija na osnove ehvo-ljucionnogo modelirovanija // Moscow, Izvestija RAN. Teorija i sistemy upravlenija. 2007. no. 4. pp. 78–90.
7. Norenkov I.P. Fundamentals of computer-aided design. Moscow, Moscow State Technical University n.a. N.E. Bauman, 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. no. 5. рр. 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, Vol. 10, no. 2, April 2005.
11. Strukov D.B. Gregory S. Snider, Duncan R. Stewart, R. Stanley Williams. The missing memristor found // Nature. 2008. Vol. 453. рр. 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.