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

OPTIMIZATION OF MICROPIPELINE ARCHITECTURE DESIGNED IN LOGICAL BASIS OF FPGA / STRUCTURED ASIC

Kononov A.S. 1 Mindeeva A.A. 1 Petrosyan V.S. 1 Manukyan A.A. 1
1 National Research University of Electronic Technology
In this paper were studied the methods of optimization for micropipeline digital circuits, which are constructed in logical basis of FPGA / structured ASIC. The methods are based on use of Series-Parallel Binary Decision Diagrams (SP-BDD). With use of software digital circuits at first were presented in the form of SP-BDD and then was made a SP-BDD reordering. The main idea of the proposed method is to optimize combinational fragments of micropipeline after combining them into the larger combinational circuit, instead of optimizing them separately. Optimization of the combined scheme should be more effective because of bigger space for search. Optimization was carried out in three versions for each scheme: the combinational fragments individually, after combining them in pairs, after combining all combinational parts of micropipeline. The results of the test are presented in the form of table. In all cases, a positive result is gained in form of improved performance and reduced size of the scheme. The most effective method was the method of combining whole combinational parts. In that case there was achieved up to 44,5 percent of reduction in size and up to 3,5 times increase in performance.
optimization of micropipelines; scheme optimization; combinational scheme optimization; binary decision diagrams; digital scheme optimization
1. Glebov A.L., Gurariy M.M., Zharov M.M. et.al., Aktualnye problem modelirovaniya v sistemakh avtomatizatsii skhemotekhnicheskogo proektirovaniya [Actual problems of modeling in circuit design automation systems]. Moscow, Nauka, 2003. 430 p.
2. Glebov A.L. Informatsionnye tekhnologii, 1997, no. 10, pp. 18–22.
3. Kononov N. Lambert Academic Publishing, Germany, 2011.
4. Stroganov A. Komponenty i tekhnologii, 2008, no. 5, pp. 148–153.
5. Glebov A.L., Blaauw D., Jones L.G. Intern. Symp. On Low Power Design. Dana Point, CA, 1995, pp. 161–166.
6. Glebov A.L., Gavrilov S.V., Blaauw D. et.al. ICCAD-97, 1997, pp. 461–467.
7. Mohideen S.K., Perinbam J.R. International Journal of Applied Engineering and Research, India, 2007, Vol. 2, no. 1, pp. 139–146.
8. Sutherland I.E. Communications of ACM, 1989, Vol. 32. pp. 720–738.

Понятие микроконвейера первоначально введено в 1989 году И. Сазерлендом в качестве архитектуры для асинхронных схем [8]. Асинхронный микроконвейер схематически изображен на рис. 1.

Микроконвейер состоит из линейной последовательности регистров (на рис. 1 – R1, R2, R3, R4) и комбинационных схем (на рис. 1 – CL3, CL4), вычисляющих некоторые системы Булевых функций. Поскольку схема асинхронная, она не имеет единого тактового сигнала, и работа каждой пары соседних регистров синхронизируется с помощью контрольной логики (CTL), реализующей механизм «handshaking» (рукопожатие).

pic_11.tif

Рис. 1. Асинхронный микроконвейер

Существует также синхронный аналог микроконвейера, изображенный на рис. 2.

Архитектура микроконвейера выбрана не случайно. Дело в том, что в форме микроконвейера может быть представлена практически любая цифровая схема, как синхронная, так и асинхронная [7].

pic_12.tif

Рис. 2. Синхронный аналог микроконвейера

Оптимизация микроконвейерной архитектуры

В данной работе предложен метод оптимизации цифровых схем, имеющих архитектуру микроконвейера, основанный на использовании диаграмм двоичных решений специального вида. Были рассмотрены схемы микроконвейерной архитектуры, спроектированной в базисе ПЛИС/СБМК [4]. Указанный базис содержит однотипные универсальные логические модули (УЛМ), каждый из которых может вычислять произвольную Булеву SP (последовательно-параллельную) функцию, имеющую не более четырех аргументов [3]. Указанная Булева функция реализована в виде поисковой таблицы (LUT). Кроме того, УЛМ содержат элементы памяти, которые могут быть использованы для формирования регистров микроконвейера.

Предлагаемый метод структурной оптимизации микроконвейера основан на использовании программы структурной оптимизации комбинационных цифровых КМОП схем OPTI, использующей внутреннее представление цифровой схемы в виде SP-BDD [5, 2].

При обработке SP-BDD представления схемы используются следующие алгоритмы:

• Экстракция SP-BDD из транзисторной схемы.

• Переупорядочение вершин (транзисторов КМОП вентиля).

• Слияние двух SP-BDD (двух КМОП вентилей).

• Декомпозиция SP-BDD (КМОП вентиля).

• ПП-сужение (разложение Шеннона для SP-BDD).

• Минимизация SP-BDD (КМОП вентиля) [6, 1].

Основная идея предлагаемого метода оптимизации следующая. С одной стороны, каждую комбинационную схему в микроконвейере (CL3, CL4, рис. 2) можно оптимизировать по отдельности. С другой стороны, можно на время оптимизации удалить регистр R3 и объединить схемы CL3, CL4 в одну комбинационную схему большего размера. После оптимизации этой схемы она может быть вновь «разрезана» (если это необходимо) на две составные части CL3’, CL4’, и между ними может быть вставлен соответствующий регистр R3’. В случае оптимизации объединенной схемы пространство поиска является более разнообразным, чем при оптимизации ее частей по отдельности, поэтому результат оптимизации может быть более сильным.

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

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

В качестве исходного использовался набор комбинационных схем, содержащий некоторые из схем ISCAS-85, а также ряд фрагментов промышленных схем. Каждая из исходных схем после отображения в базис ПЛИС/СБМК была преобразована в микроконвейерную схему посредством упорядочения универсальных логических модулей (УЛМ), декомпозиции на четыре равные по размеру части и добавления пяти регистров необходимой разрядности.

После этого обработка (оптимизация) каждого микроконвейера выполнялась в трех вариантах:

– каждый из четырех комбинационных фрагментов обрабатывался отдельно;

– перед обработкой комбинационные фрагменты объединялись попарно с временным удалением промежуточного регистра;

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

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

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

В первой колонке указаны исследуемые схемы. Во второй и третьей колонке соответственно исходный размер (под размером в данном случае понимаем количество поисковых таблиц в комбинационной части схемы, «Р» в таблице) и исходное быстродействие, то есть минимальный период («МП» в таблице) тактового сигнала, на котором может работать схема. В данном случае под минимальным периодом понимается максимальная длина критического пути комбинационного фрагмента микроконвейера, вычисленная в предположении единичной задержки каждого УЛМ. Три варианта оптимизации в таблице обозначены соответственно Опт. 1, Опт. 2, Опт. 3. Результаты эксперимента в для трёх вариантов оптимизации представлены соответственно в колонках 4, 6, 7, 9, 10, 12. Проценты уменьшения размера («%» в таблице) в результате оптимизации схем представлены в колонках 5, 8, 11.

Результаты эксперимента

1

2

3

4

5

6

7

8

9

10

11

12

схема

исх.

Р

исх. МП

опт.1

Р

%

опт. 1 МП

опт. 2

Р

%

опт. 2 МП

опт. 3

Р

%

опт. 3 МП

c432

150

8

142

–5,3

8

137

–8,7

7

138

–8,0

5

c1355

482

18

301

–37,6

13

298

–38,2

9

299

–38,0

6

c1908

499

24

364

–27,1

21

353

–29,3

11

277

–44,5

8

cla

200

15

200

0

15

153

–23,5

6

157

–21,5

5

cla1

139

11

139

0

11

139

0

11

139

0

11

cnt_0

68

11

58

–14,7

11

54

–20,6

9

54

–20,6

6

cnt_1

73

11

53

–27,4

8

52

–28,8

8

53

–27,4

6

cnt_ones

51

8

48

–5,9

6

48

–5,9

6

48

–5,9

6

cnt_zeros

50

7

48

–4,0

6

47

–6,0

6

49

–2,0

5

newckt

115

7

103

–10,4

5

109

–5,2

4

111

–3,5

2

Из приведенной таблицы видно, что для всех тестируемых схем оптимизация приводит к уменьшению размера, в ряде случаев значительному (максимальное значение для одной схемы ‒ 44,5 %). Быстродействие схем во всех случаях значительно (для одной схемы в 3,5 раз) улучшается, в том числе с укрупнением оптимизируемых фрагментов. Для сравнения, для тех же схем по первым двум вариантам оптимизации были получены следующие результаты: уменьшение размера на 27,1 % в первом варианте, на 29,3 % во втором, увеличение быстродействия в 1,4 раза в первом варианте, в 1,75 раза.

Заключение

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

Таким образом, предлагаемый метод оптимизации микроконвейерных схем обладает высокой эффективностью (отчасти связанной с используемым алгоритмом структурной оптимизации цифровых КМОП схем). Полученные результаты доказывают практическую ценность данного метода оптимизации микроконвейерной архитектуры, спроектированной в базисе ПЛИС/СБМК.

Рецензенты:

Глебов А.Л., д.т.н., профессор, старший научный сотрудник, Национальный исследовательский университет «МИЭТ», Зеленоград, г. Москва;

Адамов Ю.Ф., д.т.н., профессор, ведущий научный сотрудник, Институт проблем проектирования в микроэлектронике Российской академии наук, Зеленоград, г. Москва.

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