8.4.3. ЧИСЛО КОМАНД ДЛЯ РЕАЛИЗАЦИИ ФУНКЦИИ

Для реализации заданной функции, вообще говоря, можно использовать много различных программ. Число команд и количество ячеек ЦМД, требуемых для реализации любой заданной функции на основе заданного типа (типов) команд, зависят от конкретной реализации и могут изменяться в широких диапазонах, что видно на следующем примере.

а 2k ДОЛЖНО быть делителем п, максимальная длина пути минимальна при k = \/nlQ, если это число целое. Следовательно, если п ~ 62, то максимальная длина пути для схемы размещения, показанной на рис. 8.12, равна (Vs \/п - i). Ниже приведены некоторые типичные значения п и максимальной длины пути для значений k, обеспечивающих минимум максимальной длины пути.

k п Длина пути

2 24 9

3 54 15

4 96 21 Б 150 27

Для получения нижней граничной оценки максимальной длины пути для схемы памяти, содержащей п ячеек и допускающей взаимодействие между любой парой ячеек, рассмотрим наиболее плотную упаковку этих ячеек (без транзитных точек) в двумерном пространстве, а именно в круге. Если радиус круга равен г, п-г^ = п или г = Vп/п. Максимальное расстояние между двумя точками равно 2г = V4п/п. Ясно, что эта граница не достижима, потому что при определении граничной оценки все точки круга рассматриваются как ячейки данных.

Итак, в лучшем случае мы получим путь максимальной длины, равной Сл/п, где С>л/4/п. В памяти, структура которой показана на рис. 8.12, максимальная длина пути < 6 п, что приблизительно в два раза больше нижней граничной оценки. Рассмотренные выше схемы памяти допускают взаимодействие между всеми парами ячеек данных и, следовательно, пригодны для реализации произвольной программы. Для реализации специальных функций часто оказывается, что взаимодействие необходимо только внутри подмножества пар ячеек данных, вследствие чего достаточен меньший объем памяти. Максимальную длину пути можно сократить и в общем случае. В этом случае полученные выше оценки памяти и максимальной длины пути оказываются верхними граничными оценками.

Рис. 8.14. Схема для программы Р', пример 8.1

рис. 8.12, содержащей восемь ячеек. Поскольку эта программа не требует взаимодействия между всеми ячейками данных, то, как можно показать, для обеспечения требуемых взаимодействий необходимым и достаточным количеством оказывается 7 ячеек. Однако ниже приведена программа Р', также содержащая шесть команд и требующая шесть ячеек данных, которую можно реализовать, используя только шесть ячеек в соответствии с рис. 8.14.

Р'-{Хи F,)(Xo, Fo)(Z Хо){Хо, Fo){Yo, F,) (Fo, F,).

Этот пример показывает, что каноническая реализация может быть не эффективной в смысле числа команд, времени вычислений, а также потребности в объеме памяти. Неэффективность канонической реализации становится еще более явной, если сравнить каноническую реализацию f = xi@x2® ... ®Хп

Пример 8.1. Рассмотрим вычисление функции f = x@y при использовании команд пересылки и расщепления ЦМД. Пусть, как это указывалось выше, для представления каждой переменной X используются ячейки Хо и Х\. При использовании канонического представления в виде рассмотренной ранее суммы произведений возникает необходимость вычисления четырех минтермов (двух для самой функции и двух для ее дополнения.) При этом общее число команд, за исключением команд очистки выходных ячеек Fo и Fi, равно 32. (Это число можно уменьшить до 24, используя очевидные упрощения, но по-прежнему используя представление в виде суммы произведений.) Число необходимых ячеек равно 8 (по две на два входа и на выход и две для промежуто'чного хранения). При использовании схемы размещения, показанной на рис. 8.12, память должна содержать И ячеек.

Другая программа Р, содержащая только 6 команд, также вычисляет эту функцию, если ячейки Fo и Fi первоначально пусты.

Р =(Хь Y{){Xo, Fo)№, Fo){Xo, Fo){Yu Fo)(F Fi).

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

Рис. 8.15. Модули, соответствующие пересылке ЦМД (о) и расщеплению

ЦМД (б).

Задача минимизации числа команд программы вычисления комбинационной функции соответствует задаче реализации функции с использованием наименьшего числа модулей данного типа. Команду пересылки ЦМД можно, например, представить в виде модуля, показанного на рис. 8.15, й. Для обозначения выходных ячеек на рис. 8.15 используются скобки. Модуль, представляющий расщепление ЦМД, показан на рис. 8.15,6. Создание и разрушение ЦМД можно представить соответствующими входными константами (1 или 0). Если функцию можно реализовать на основе модулей этих типов, то реализацию можно затем интерпретировать как программу вычисления данной функции. Все ячейки ЦМД, использующиеся в программе, будут при этом соответствовать входам схемы. При этом, хотя эффективная реализация функций на основе модулей, соответствующих допустимым взаимодействиям ЦМД, позволяет получить эффективные программы, алгоритмы построения таких эффективных реализаций в настоящее время не известны. Следующий пример поясняет, как получается программа, соответствующая реализации заданной функции на основе модулей, показанных на рис. 8.15.

Пример 8.2 [10]. Рассмотрим функцию f = ас-\- bed + bed, которую требуется вычислить, используя только пересылки ЦМД. Пусть каждая переменная представляется двумя ячейками. Мы хотим реализовать f и f, используя только изображенный на рис. 8.15, а модуль при отсутствии разветвлений на выходе.

с реализацией в виде (... ((i ф хг) ф а;з) ф ... фд: ), где каждая операция Исключающее ИЛИ выполняется прогэаммой вышеописанного типа.

Рассмотренный пример выявляет несколько нерешенных задач, связанных с разработкой эффективных программ вычисления комбинационных функций. Во-первых, составление программы вычисления данной функции с наименьшим числом команд; во-вторых, распределение ячеек таким образом, чтобы минимизировать общее число ячеек, необходимых для реализации функции, и, в-третьих, поскольку необходимое число ячеек памяти зависит не только от числа команд, но и от специфики программы, получение программы с минимальными требованиями к объему памяти.

Входы схемы состоят из переменных и их дополнений: f=cri-j--\-bc-{-acd-\-abc=c(b-{-d)-\-ac{b-{-d). Получаем схему, изображенную иа рис. 8.16, которая реализует и f, и f. Интерпретируя каждый модуль как соответствующую команду, получаем следующую программу:

Р = (Во, Do) {Do, С,) (В Di){Ao, Co)(D Л) (Do, D,)(Cb Б,)Х

Х{Во, Ао){Со, Ах) {Во, Со){Сх, Q.

По окончании программы f и f будут соответственно в Со и Di. При интерпретации схемы в виде программы модули схемы рассматриваются последовательно, т.е. данный модуль не интерпретируется в виде соответствующей команды до тех пор, пока не были рассмотрены модули, определяющие его входные сигналы.

Не менее важным является определение правильного соответствия между ячейками ЦМД и выходными окончаниями модуля. После исполнения команды {X, У) само значение ху появляется в ячейке х, а значение х-\-у появляется в ячейке Y.

В предыдущем примере не возникало необходимости использовать ячейки для расщепления или временного хранения ЦМД. При этом входная информация не сохранялась. Исходя из предположения, что все входные переменные представляются двумя ячейками, можно показать [13], что все функции четырех переменных можно реализовать без использования расщепления или временного хранения ЦМД. Было показано также существование функций 11 переменных, которые нельзя реализовать на основе только пересылки ЦМД, однако наибольшее число переменных, все функции которых могут быть реализованы только посредством пересылки пузырьков, в настоящее время не определено.

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

8.4.4. УСКОРЕНИЕ ВЫЧИСЛЕНИЙ

Мы видели, как с помощью программ с различным числом команд и требованиями к объему памяти можно вычислять различные комбинационные функции. Если, как предполагалось ранее, команды программы выполняются последовательно по

ъ . bd

cc(b+d) ас*Ь±й

abed

ac+bcd -0

Рис. 8.16. Модульная реализация функции

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

Пример 8.3. Рассмотрим показанную на рис. 8.16 реализацию функции f = ас + bed + bed. Разбиение модулей по уровням производится следующим образом. Уровень 1: (1,3,4); уровень 2: (2,5,9); уровень 3: (6,7,8); уровень 4: (10); уровень 5: (11). Программа Р может быть выполнена за пять шагов:

1. (Во,/)о)(Вь 1)(Л, Со).

2. {Do, Ci){Du Ло)(Со, Л,).

3. (Do, Д)(С В,)(Во, Ло).

4. {Во, Со),

5. (Сь Со).

ОДНОЙ, ТО время вычисления функций зависит от числа команд в программе. При этом процесс вычислений можно ускорить путем параллельного выполнения нескольких команд.

Естественным способом достижения распараллеливания при выполнении программы является одновременное выполнение независимых команд. Такие команды могут быть определены на основе рассмотрения соответствующей схемы, как обсуждалось в предшествующем разделе. Далее модули схемы разбиваются на уровни следующим образом. Модули, входами которых являются только входные переменные (или их дополнения), относятся к уровню 1. Уровень любого модуля а определяется как

Другая ситуация, при которой возможно параллельное выполнение команд, может быть пояснена на примере последовательности команд (А, В) {А, С). Выполнение этой последовательности команд дает

аЬс в ячейке А, а + Ь в ячейке В, аЬ + с в ячейке С,

Изменив порядок выполнения команд на {А, С) {А, В), получаем

аЬс в ячейке А. ас-\-Ь в ячейке В, а-\- с в ячейке С.

Если команды {А, В) и {А, С) выполняются одновременно, то ячейка А будет содержать аЬс, в то время как содержимое ячеек В С будет не определено, поскольку оно зависит от того, какая из двух команд была выполнена первой. Однако если нам нужно получить только терм аЬс, то эти две команды могут выполняться параллельно. Вообще при формировании комбинаций термов из п переменных (и-1) команда может выполняться одновременно. Аналогично одновременное выполнение команд (Б,5),... оставляет значение суммы й-\-Ъ-\-... в ячейке S, а содержимое ячеек Л, В,... остается неопределенным. На основе такого подхода программа из примера 8.3 может быть выполнена за 4 шага, поскольку шаги 4 и 5 могут выполняться одновременно.

Вычисление можно также ускорить на основе подхода, используемого при образовании сигналов в асинхронных схемах. Комбинационную функцию f можно выразить в виде суммы минтермов. Функция может быть вычислена путем подсчета этих минтермов по одному. Как только будет получена 1, вычисление по существу закончится, поскольку уже ясно, что значение функции равно 1. Таким образом, вычисления можно закончить, как только управляющие цепи обнаружат в выходной ячейке наличие ЦМД.

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

<

г

т

Рис. 8.17. Структура полусумматора.

На рис. 8.17 изображена структура полусумматора, обсуж-давщаяся в гл. 6. Эта структура позволяет образовывать все минтермы от п переменных и может быть использована для реализации любой комбинационной функции п переменных на основе выбора соответствующих минтермов и их суммирования в (п+ 1)-ряду. Число элементов матрицы равно (n-f-1)2 , а протяженность самого длинного пути в матрице равна 2 -f- п. Следовательно, время, необходимое для вычисления функции п переменных, пропорционально 2 + п.

Как отмечалось в разд. 8.2, функции х@у и ху можно реализовать на основе эффекта отталкивания ЦМД. Однако значение функции ху при этом помещается в две ячейки. Соединив одну из них с ячейкой, предназначенной для уничтожения ЦМД (в соответствии с рис. 8.5), мы обеспечим реализацию двух функций, необходимых для матрицы, осуществляющей функцию полусумматора. Таким образом, отдельные элементы можно реализовать на основе использования вращающегося магнитного поля.

8,5. РЕАЛИЗАЦИЯ ИТЕРАТИВНЫХ МАТРИЦ

В гл. 6 рассматривалось использование итерационных массивов для реализации комбинационных и последовательностных схем. Работа некоторых таких матриц может быть смоделирована на основе взаимодействия магнитных доменов. В такой моделирующей итеративную матрицу структуре ЦМД однотипные команды выполняются одновременно во всех элементах матрицы. Обеспечить требуемые итерации можно на основе использования вращающегося в одной плоскости магнитного поля и специальных пермаллоевых накладок.

2 cmo ffiio6

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

В момент времени = 1 на вход элемента, находящегося в позиции (1, 1), подаем входной сигнал Хп и константу 1. В момент времени t = 2 элементы, находящиеся в позициях (1,2) и (2,1), получают сигналы от первого элемента. В этот момент подаем константу 1 на второй столбец и входной сигнал Xni на второй ряд. В общем случае в момент времени t = i на i-й ряд и/или столбец подается входной сигнал. Следовательно, на последний столбец сигнал подается в момент времени t - 2 , а выходная функция образуется в момент = 2 -f-п-j-1.

Хотя для вычисления значения функции п переменных требуется (2 -j- п) временных единиц, последовательные входные сигналы можно подавать и с большей скоростью. Фактически входные сигналы можно изменять каждую единицу времени при условии, что будут сохранены относительные временные соотношения между объединенными входными сигналами. В этом случае для обеспечения появления ЦМД на каждом единичном временном интервале к верхнему ряду следует подсоединить генераторы ЦМД. Как и в гл. 6, последний ряд осуществляет суммирование минтермов реализуемой функции. ЦМД предыдущего ряда разрешается перейти в последний ряд (на основе специальной формы пермаллоевой накладки) только в том случае, если соответствующий минтерм является единичной точкой функции. В противном случае ЦМД должны быть направлены в разрушающее их устройство (разрушитель).

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

8.6. ЛОГИКА, ОБЕСПЕЧИВАЮЩАЯ СОХРАНЕНИЕ ОБЩЕГО ЧИСЛА ЦМД

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

1 или О наличие или отсутствие ЦМД и сохраняя общее число ЦМД, невозможно. Одним из методов сохранения ЦМД является параллельная реализация k функций k переменных. При этом функции должны выбираться таким образом, чтобы число выходных ЦМД было равно числу входных. Следовательно, число функций, имеющих на выходе 1 при любой комбинации на входе, должно быть равно числу входных переменных, равных 1 для этой входной комбинации. Назовем такие множества функций множествами k-k-фунщий. Для k = 2 единственным множеством 2-2-функций (за исключением тривиального случая, когда множество функций совпадает с множеством входных переменных) является {ху, х-\-у}, где х я у определяют множество входных переменных. Вспомним, что это множество функций реализуется на основе обсуждавшихся в разд. 8.3 команд пересылок ЦМД.

Множества 3-3-функций были изучены Минником и др. [14]. Пусть {/i {х, у, z), /г {х. У, z), f3 {х, у, z)} является множеством 3-3-функций. Из определения множества 3-3-функций следует, что

h(0, О, 0) = /2{0, о, 0) = /з(0, О, 0) = 0. fi(l, 1, 1) = /2(1, 1, 1)=-Гз{1, 1, 1) = 1.

Для каждой из шести оставшихся комбинаций существуют три возможных определения /], /2 и fs, учитывающие сохранение единиц. Таким образом, число множеств 3-3-функций равно 3 = 729. Эти множества можно сгруппировать в 31 класс эквивалентности, учитывая возможные перестановки входов [14].

Системы на магнитных доменах, реализующие множества 3-3-функций, назовем 3-3-схемами. Такие схемы могут быть реализованы на основе использования вращающегося в одной плоскости магнитного поля и пермаллоевых накладок. Вместо линейных и Т-образных элементов Минник и др. [14] использовали накладки в форме шеврона, предложенные Бобеком и Сковилом [7] (рис. 8.18). В дополнение к сдвигу ЦМД по дорожкам из шевронных накладок под действием вращающегося магнитного поля можно получить требуемый наклон градиента магнитного поля по отношению к направлению сдвига ЦМД. При реализации 3-3-схем используется тот факт, что ЦМД стремятся двигаться по градиенту в поисках положения, обеспечивающего энергетический минимум.

На рис. 8.18 изображена типичная 3-3-схема, реализующая {хуXZyz, xyz, x + y + z). Вследствие наличия градиента магнитного поля ЦМД, находящиеся на дорожке X или дорожке У, будут двигаться в сторону дорожки Z, которая будет содержать ЦМД, если на одну из этих трех дорожек попадет хотя

Рис. 8.18. Реализация 3-3-схемы.

ЦМД Присутствуют на всех трех дорожках. Следовательно, /г == хуг. На основе использования аналогичных схем можно реализовать все 3-3-функции.

Использование логики, сохраняющей ЦМД, для реализации комбинационных функций

Рассмотрим прежде всего случай, когда на входе не используются константы О и 1 и каждая переменная представляется единственной ячейкой. В этом случае можно сделать заключение о том, что реализовать все комбинационные функции на основе только 3-3-схем нельзя, поскольку все функции, принадлежащие множествам 3-3-функций, сохраняют общее число нулей и общее число единиц. (В соответствии с теоремой 2.9 ни одно из таких множеств функций не является полным.) Тот же результат справедлив при любом А и для множеств А-А-функций.

Если допустимо использование генераторов ЦМД, то на основе использования 3-3-схем возможна реализация любой комбинационной функции. Можно показать [14], что 26 из 31 класса эквивалентности множеств 3-3-функций являются слабо полными множествами простейших логических элементов. Для примера рассмотрим множество функций {x-\-yz, y{x-\-z), z], таблица истинности которых приведена на рис. 8.19. Установим X = О (т. е. отсутствие ЦМД на входе) и у = I (соединение с генератором ЦМД), тогда получим /i = /г = 2 и fz = z. Если

бы ОДИН ЦМД. Следовательно, h = х-\- у-}- z. Если ЦМД присутствуют на любых двух из всех трех дорожек, то в результате взаимного отталкивания ЦМД домен вытесняется на дорожку X, т. е. будет реализована функция fi = ху уг xz. На средней дорожке домен останется в том и только том случае, если