Метод кодирования наборов фрагмента переменных
Предложен метод оптимизации аппаратурных затрат в цифровых устройствах управления с гетерогенной структурой кодированием фрагмента переменных. Получены аналитические оценки эффективности предложенного метода. Запропоновано метод оптимізації апаратурних витрат у цифрових пристроях керування з гетерог...
Gespeichert in:
| Veröffentlicht in: | Комп’ютерні засоби, мережі та системи |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46485 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод кодирования наборов фрагмента переменных / А.А. Баркалов, Я.Е. Визор, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 33-38. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46485 |
|---|---|
| record_format |
dspace |
| spelling |
Баркалов, А.А. Визор, Я.Е. Матвиенко, А.В. 2013-06-30T11:25:30Z 2013-06-30T11:25:30Z 2012 Метод кодирования наборов фрагмента переменных / А.А. Баркалов, Я.Е. Визор, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 33-38. — Бібліогр.: 5 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/46485 004.274 Предложен метод оптимизации аппаратурных затрат в цифровых устройствах управления с гетерогенной структурой кодированием фрагмента переменных. Получены аналитические оценки эффективности предложенного метода. Запропоновано метод оптимізації апаратурних витрат у цифрових пристроях керування з гетерогенною структурою кодуванням фрагмента змінних. Отримано аналітичні оцінки ефективності запропонованого методу. The method of optimization of hardware expenses in digital devices with coding of variables and heterogeneous structure is described. Analytical dependences of effectiveness and results of research of offered method are received. ru Інститут кібернетики ім. В.М. Глушкова НАН України Комп’ютерні засоби, мережі та системи Метод кодирования наборов фрагмента переменных The method of encoding of fragment sets of variables Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод кодирования наборов фрагмента переменных |
| spellingShingle |
Метод кодирования наборов фрагмента переменных Баркалов, А.А. Визор, Я.Е. Матвиенко, А.В. |
| title_short |
Метод кодирования наборов фрагмента переменных |
| title_full |
Метод кодирования наборов фрагмента переменных |
| title_fullStr |
Метод кодирования наборов фрагмента переменных |
| title_full_unstemmed |
Метод кодирования наборов фрагмента переменных |
| title_sort |
метод кодирования наборов фрагмента переменных |
| author |
Баркалов, А.А. Визор, Я.Е. Матвиенко, А.В. |
| author_facet |
Баркалов, А.А. Визор, Я.Е. Матвиенко, А.В. |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Комп’ютерні засоби, мережі та системи |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
The method of encoding of fragment sets of variables |
| description |
Предложен метод оптимизации аппаратурных затрат в цифровых устройствах управления с гетерогенной структурой кодированием фрагмента переменных. Получены аналитические оценки эффективности предложенного метода.
Запропоновано метод оптимізації апаратурних витрат у цифрових пристроях керування з гетерогенною структурою кодуванням фрагмента змінних. Отримано аналітичні оцінки ефективності запропонованого методу.
The method of optimization of hardware expenses in digital devices with coding of variables and heterogeneous structure is described. Analytical dependences of effectiveness and results of research of offered method are received.
|
| issn |
1817-9908 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46485 |
| citation_txt |
Метод кодирования наборов фрагмента переменных / А.А. Баркалов, Я.Е. Визор, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 33-38. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT barkalovaa metodkodirovaniânaborovfragmentaperemennyh AT vizorâe metodkodirovaniânaborovfragmentaperemennyh AT matvienkoav metodkodirovaniânaborovfragmentaperemennyh AT barkalovaa themethodofencodingoffragmentsetsofvariables AT vizorâe themethodofencodingoffragmentsetsofvariables AT matvienkoav themethodofencodingoffragmentsetsofvariables |
| first_indexed |
2025-11-24T19:09:33Z |
| last_indexed |
2025-11-24T19:09:33Z |
| _version_ |
1850490221570818048 |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2012, № 11 33
A.A. Barkalov, Y.E. Vizor,
A.V. Matvienko
THE METHOD OF ENCODING
OF FRAGMENT SETS
OF VARIABLES
The method of optimization of hard-
ware expences in digital devices with
coding of variables and heterogene-
ous structure is described. Analytical
dependences of effectiveness and re-
sults of research of offered method
are received.
Key words: control unit, optimiza-
tion, coding.
Запропоновано метод оптимізації
апаратурних витрат у цифрових
пристроях керування з гетероген-
ною структурою кодуванням
фрагмента змінних. Отримано
аналітичні оцінки ефективності
запропонованого методу.
Ключові слова: пристрій керуван-
ня, оптимізація, кодування.
Предложен метод оптимизации
аппаратурных затрат в цифро-
вых устройствах управления с
гетерогенной структурой коди-
рованием фрагмента переменных.
Получены аналитические оценки
эффективности предложенного
метода.
Ключевые слова: устройство уп-
равления, оптимизация, кодирова-
ние.
А.А. Баркалов, Я.Е. Визор,
А.В. Матвиенко, 2012
УДК 004.274
А.А. БАРКАЛОВ, Я.Е. ВИЗОР, А.В. МАТВИЕНКО
МЕТОД КОДИРОВАНИЯ НАБОРОВ
ФРАГМЕНТА ПЕРЕМЕННЫХ
В настоящее время при проектировании
цифровых устройств управления широко
применяется гетерогенный элементный ба-
зис, позволяющий снизить стоимость, как
отдельных узлов, так и устройства в целом. В
качестве такого базиса часто используется
комбинация «программируемая логическая
матрица + постоянное запоминающее уст-
ройство» («ПЛМ+ПЗУ»), допускающая при-
менение метода кодирования наборов пере-
менных.
Для оптимизации аппаратурных затрат в
схеме устройства управления в настоящей
работе предлагается метод кодирования на-
боров фрагмента переменных, который бази-
руется на кодировании наборов переменных
и приводит к структурной модификации уст-
ройства.
В работе дано аналитическое обоснование
эффективности предлагаемого метода, а так-
же рассмотрены результаты эксперименталь-
ных исследований, определяющих область
его эффективного применения.
Важными структурными элементами циф-
ровых вычислительных систем являются
устройства управления, которые могут быть
реализованы в виде цифровых автоматов [1].
Минимизация аппаратурных затрат в логиче-
ских схемах цифровых автоматов является
актуальной задачей при разработке и произ-
водстве средств вычислительной техники.
Известен ряд методов оптимизации аппа-
ратурных затрат в схемах автоматов, осно-
ванных на кодировании наборов переменных
(кодирование наборов микроопераций, коди-
рование классов псевдоэквивалентных со-
стояний и т. д.) [2, 3]. Обычно эти методы
А.А. БАРКАЛОВ, Я.Е. ВИЗОР, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 34
используют гетерогенную реализацию логической схемы устройства, которая в
общем случае приводит к уменьшению стоимости схемы. При этом коды набо-
ров формируются комбинационной схемой на базе ПЛМ, а для преобразования
кодов используется ПЗУ [2, 4, 5] (рис. 1). На рис. 1 код набора D формируется
блоком ПЛМ на основании множества аргументов X и используется схемой ПЗУ
для формирования множества переменных Y.
ПЛМ ПЗУ
D YX
РИС. 1. Схема формирования переменных с использованием кодирования наборов
Если считать, что число аргументов для формирования кода набора равно L,
а множество переменных в наборе равно N, то число бит ПЛМ можно опреде-
лить как суммарную площадь матриц «И» и «ИЛИ» [3, 4]:
RQQV L 2
ÏËÌ 2 ,
где Q – общее число термов ПЛМ, R – разрядность кода набора переменных.
Аналогично можно определить полную емкость ПЗУ дешифратора, считая,
что число формируемых переменных равно N:
NV R 2ÏÇÓ .
Пусть k1 – стоимостный коэффициент, позволяющий перевести информаци-
онную емкость ПЛМ в ее стоимость, k2 – аналогичный коэффициент для ПЗУ.
Тогда стоимость логической схемы фрагмента, показанного на рис. 1, может
быть определена как
NkRQQkS RL 22 2
2
1 . (1)
Пусть в схеме на рис. 1 содержимое ПЗУ дешифратора наборов соответст-
вует табл. 1. Очевидно, что здесь среди N = 8 микроопераций мы имеем W = 9
наборов микроопераций, для задания которых ПЛМ должна сформировать код
разрядности R = ] log2W [ = 4. При этом полная емкость ПЗУ будет равна 8*24 =
= 128 бит.
Для уменьшения аппаратурных затрат в схеме формирования переменных
предлагается метод кодирования наборов фрагмента переменных, заключаю-
щийся в следующем.
МЕТОД КОДИРОВАНИЯ НАБОРОВ ФРАГМЕНТА ПЕРЕМЕННЫХ
Комп’ютерні засоби, мережі та системи. 2012, № 11 35
Поскольку от изменения порядка следования строк и столбцов смысл табл. 1
принципиально не изменится, расположим строки и столбцы так, как показано в
табл. 2.
ТАБЛИЦА 1. Содержимое ПЗУ дешифратора наборов
A\Y y1 y2 y3 y4 y5 y6 y7 y8
a1 1 0 1 0 1 1 0 0
a2 0 0 0 0 0 1 0 1
a3 1 1 1 1 1 1 0 0
a4 0 0 0 0 0 0 0 1
a5 0 1 0 0 0 0 1 0
a6 0 1 0 0 0 0 1 1
a7 0 0 0 0 0 1 0 0
a8 0 1 0 0 0 1 1 1
a9 1 0 1 0 1 0 0 1
ТАБЛИЦА 2. Преобразованная таблица дешифратора набороов
A\Y y1 y2 y3 y4 y5 y7 y6 y8
a2 0 0 0 0 0 0 1 1
a4 0 0 0 0 0 0 0 1
a7 0 0 0 0 0 0 1 0
a1 1 0 1 0 1 0 1 0
a9 1 0 1 0 1 0 0 1
a5 0 1 0 0 0 1 0 0
a6 0 1 0 0 0 1 0 1
a8 0 1 0 0 0 1 1 1
a3 1 1 1 1 1 0 1 0
Если рассматривать первые N1 = 6 столбцов табл. 2, в них можно выделить
W1 = 4 набора переменных:
Y1 = {}, Y2 = {y1, y3, y5}, Y3 = {y2, y7}, Y4={y1, y2, y3, y4, y5}.
Для их кодирования достаточно R1 = ] log2W1 [ переменных (в случае табл. 2
величина R1 = 2).
Назовем подмножество переменных, составляющих первые 6 столбцов
табл. 2, фрагментом переменных (ФП), размер которого равен N1 переменных.
Организуем ПЛМ так, чтобы она формировала R1 = 2 разряда кода набора в вы-
бранном фрагменте, а также разряды y6 и y8, которые не вошли во фрагмент пе-
ременных. При этом ПЛМ, как и ранее, будет формировать 4 разряда, т. е. ее
А.А. БАРКАЛОВ, Я.Е. ВИЗОР, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 36
информационная емкость существенно не изменится. На рис. 2 показана струк-
тура устройства, использующего предлагаемый метод.
ПЛМ
ПЗУ
1
3
2
1
8
7
6
L
2
5
4
1
2
x
y
y
y
y
y
y
x
x
y
y
D
D
РИС. 2. Схема формирования переменных с использованием кодирования наборов фрагме нта
Разряды, кодирующие наборы переменных внутри фрагмента, поступают на
ПЗУ дешифратора наборов. Поскольку для кодирования наборов внутри фраг-
мента достаточно 2-х разрядов, ПЗУ должно иметь R1 = 2 входа и N1 = 6 выхо-
дов, а его емкость равна 121
1
ÏÇÓ
R
NV и составит 6*22 = 24 бит. Это в 5.33 раза
меньше, чем в случае схемы без использования кодирования наборов фрагмента.
Чтобы оценить, насколько выигрыш в уменьшении емкости ПЗУ повлиял на
уменьшение стоимости системы «ПЛМ+ПЗУ», рассмотрим отношение KS стои-
мостей, рассчитанных по формуле (1) для схем на рис. 1 и рис. 2:
1
2
1 2
2
1 1 1 1 1 2 1
(2 ) 2
(2 ( )) 2
L R
S RL
k Q Q R k N
K
k Q Q R N N k N
,
(2)
где Q1 – число внутренних термов в ПЛМ схемы рис. 2.
Несмотря на то, что ПЛМ в схемах на рис. 1 и 2 формируют одинаковое ко-
личество функций, эти функции различны, т. е. для их формирования требуется
в общем случае различное количество внутренних термов. Следовательно, при-
менение метода кодирования наборов фрагмента может привести как к увеличе-
нию числа внутренних термов ПЛМ, так и к их уменьшению, что соответст-
вующим образом отразится на стоимости ПЛМ. Этот факт может быть учтен
лишь для конкретной системы функций.
Для определения эффективности предлагаемого метода исследуем зависи-
мость коэффициента KS от аргументов функции (2). При этом будем считать, что
величины R, N, R1, N1 будут взяты согласно табл. 1 и 2. В качестве аргументов
выделим величины L, Q, Q1 и отношение стоимостных коэффициентов k1/k2.
Примем для рассматриваемого примера следующие параметры: Q = Q1 = 10,
МЕТОД КОДИРОВАНИЯ НАБОРОВ ФРАГМЕНТА ПЕРЕМЕННЫХ
Комп’ютерні засоби, мережі та системи. 2012, № 11 37
L = 3, k1/k2 = 5. Отметим, что при данных параметрах KS = 1.030, т. е. выигрыш
составляет 3 %.
Зависимость коэффициента KS от числа входов ПЛМ при изменении их ко-
личества от 1 до 10 приведена в табл. 3. Очевидно, что с увеличением числа
входов ПЛМ выигрыш от уменьшения емкости ПЗУ стремится к нулю.
ТАБЛИЦА 3. Зависимость коэффициента KS от числа входов ПЛМ
L 1 2 3 4 5 6 7 8 9 10
KS 1,24 1,10 1,03 1,007 1,002 1,001 1,000 1,000 1,000 1,000
Определим зависимость KS от соотношения коэффициентов k1/k2. Данное
соотношение может иметь широкий разброс значений в зависимости от типа и
информационной емкости используемых микросхем, однако обычно стоимость
ПЗУ не превышает стоимость ПЛМ (k1/k2 ≥ 1). Результаты расчетов представле-
ны табл. 4. Очевидно, что при увеличении величины k1/k2 от 1 до 10 в нашем
примере выигрыш снижается с 14,7 % до 1,5 %.
ТАБЛИЦА 4. Зависимость коэффициента KS от соотношения k1/k2
k1/k2 1 2 3 4 5 6 7 8 9 10
KS 1,147 1,075 1,050 1,038 1,030 1,025 1,022 1,019 1,017 1,015
Определим зависимость KS от количества внутренних термов исходной и ре-
зультирующей ПЛМ. Результаты представлены табл. 5, а ее графическая интер-
претация показана на рис. 3. Отметим, что наиболее вероятные значения KS
группируются в таблице вдоль главной диагонали (при Q ≈ Q1).
ТАБЛИЦА 5. Зависимость коэффициента KS от числа внутренних термов ПЛМ
Q \ Q1 5 10 15 20 25
5 1,06 0,53 0,35 0,26 0,21
10 2,04 1,03 0,69 0,52 0,41
15 3,03 1,53 1,02 0,77 0,61
20 4,01 2,02 1,35 1,02 0,81
25 5,00 2,52 1,68 1,26 1,01
А.А. БАРКАЛОВ, Я.Е. ВИЗОР, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 38
РИС. 3. Зависимость KS от числа внутренних термов
Таким образом, использование предлагаемого авторами метода кодирования
наборов фрагмента переменных позволяет уменьшить емкость ПЗУ дешифрато-
ра наборов без изменения числа выходов ПЛМ. Изменение числа внутренних
термов ПЛМ оказывает значительное влияние на стоимостный коэффициент, и
этот факт необходимо учитывать при применении предложенного метода.
1. Baranov S. Logic Synthesis for Control Automata. – Dordrecht: Kluwer Academic Publishers,
1994. – 312 p.
2. Баркалов А.А, Палагин А.В. Синтез микропрограммных устройств управления. – Киев:
ИК НАН Украины, 1997. – 136 с.
3. Баркалов А.А. Синтез устройств управления на программируемых логических устройст-
вах. – Донецк: ДНТУ, 2002. – 262 с.
4. Соловьев В.В. Проектирование цифровых схем на основе программируемых логических
интегральных схем. – М.: Горячая линия-ТЕЛЕКОМ, 2001. – 636 с.
5. Грушницкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем с использованием
микросхем программируемой логики. – СПб: БХВ. – Петербург, 2002. – 608 с.
Получено 20.08.2012
5
10
15
20
25 5
10
15
20
25
0
0,5
1
1,5
2
3
3,5
4
4,5
5
Ks
Q
Q1
|