Коммутативность многоканальных информационных систем с конвейерами

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

Пример решения проблемы

Вмногоканальных информационных системах с конвейерами и их подобиями, например, в ЭВМ, Internet, в устройствах отображения информации (дисплеях), синтез (коммутации) сложных объектов («изображений») из простых элементов, распределенных вдоль конвейера,реализуется,по аналогии с наборными машинами (НМ), над модулями сумм кольца целых чисел Z_n – номерами объектов в списках.

Известно, что кольцом называют класс объектов R с двумя абстрактными бинарными операциями – сложением и умножением по отношению, к которым он замкнут. Кольцо для Zn в части суммы (a + b) является абеле- вой группой, в части произведения c(a + b) – мультипликативным моноидом [1].

Группа коммутативна, или абелева, если для любых ее элементов a и b выполняется условие ab = ba в мультипликативной форме. В аддитивной форме ему соответствует условие ( a + b ) = ( b + a ). Интерпретация условия коммутативности в случае кольца целых чисел, например при n = 6, связана с накопленной суммой по модулю 6. Для a и b – целых чисел, где a = 5, b = 4, сумма ( a + b )mod6 = 3. Изменив порядок размещения слагаемых в этой сумме, получим тот же результат, так как ( b + a )mod6 = (4 + 5)mod6 = 3.

Если a = t_c = t₁ – условное время затраченное на переход к месту набора знака в списке знаков «строки», b = t_ш = t₂ – время затраченное на переход в списке изображений знаков в «шрифтоносителе», тогда t_о = t₁ + t₂ = ( a + b ) – суммарное затраченное время переходов. В коммутативной среде время t_o не зависит от порядка размещения слагаемых в суммах.

Суммирование чисел выполняется на этапе программирования «набора». Вторая групповая операция в структуре кольца реализуется при возвращении системы в исходное (невозмущенное) состояние во время исполнения программы набора.

Коммутативность сумм позволяет, без потери точности величины суммарного (приведенного) времени t_о (см. таблицы 1 и 2), соотносить края таблицы сумм кольца Z_n разным физическим величинам и строить «наборные» машины, в которых первой учитывается координата знакоместа, или же первым учитывается положение знака в шрифтоносителе.

Таблица 1. Случай прямого порядка обозначения краев таблицы

j ↓ \ i →	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
.	.	.	.	.	. 0	.

Здесь: i – номер знака в строке (номер знакоместа); j – номер знака в шрифтоносителе; i + j = (5 + 4)mod6 = (9)mod6 = 3 – суммарная величина задержки.

Таблица 2. Случай обратного обозначения краев таблицы

j ↓ \ i →	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
.	.	.	.	.	.	.

В таблицах 1-2 изменение обозначений не касается направления суммирования чисел. Оно остается произвольным, но только прямым или только обратным.

В комплексе, i + j = j + i = (5 + 4)mod6 = = (4 + 5)mod6 = (9)mod6 = 3. Баланс задержек определяется свойствами таблиц.

Во всех рассмотренных случаях величина сумм не превышает число 5. Это говорит о замкнутости множества объектов, образующих кольцо Z_n для n = 6 или для любого конечного целого n . Однако роль коммутативности для НМ с конвейерами этим не ограничивается.

Строки таблицы модулей сумм для кольца Z_n образуют циклическую группу подстановок вращения:

012345⎞ ⎛ 012345 ⎞ ⎛ 012345 ⎞ 012345 ^⎟⎠ ^{, ⎜}⎝123450 ^⎟⎠ ^{, ⎜}⎝ 234501 ^⎟⎠ ^, ⎛ 012345 ⎞ ⎛ 012345 ⎞ ⎛012345⎞ ^{. ⎜}⎝ 345012 ^⎟⎠ ^{, ⎜}⎝ 450123 ^⎟⎠ ^{, ⎜}⎝501234 ^⎟⎠

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

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

Строки таблицы сумм (вторые строки подстановок) в безразмерной форме несут необходимую информацию о моментах переноса изображений набираемых знаков из шрифтоносителя в набор.

Упомянутое множество подстановок образует абелевую группу подстановок – степеней для подстановок «сдвигателей». Речь идет о подстановках правого и левого вращения:

012345⎞ ⎛012345⎞

123450 ^⎟⎠ ^{и ⎜}⎝501234 ^⎟⎠ ^.

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

Признаком коммутативности подстановок является наличие циклов («петель»). Произведения степеней подстановок с циклами тоже коммутативны. Например, коммутативны следующие произведения:

а б

аб

1. ⎛012345⎞⎛012345⎞ ⎛012345⎞ – ⎜⎝501234 ⎟⎠⎜⎝345012 ⎟⎠ = ⎜⎝234501 ⎟⎠ прямое произведение;

а         б         аб

2.⎛012345⎞⎛012345⎞ ⎛012345⎞ – ⎜⎝345012 ⎟⎠⎜⎝501234 ⎟⎠ = ⎜⎝234501 ⎟⎠ обратное произведение.

Подстановки – степени подстановок – «сдви-гателей» реализуют циклическую группу подстановок вращения над таблицей сумм кольца целых чисел Z_n . В силу коммутативности произведений подстановок вращения, полученная группа – абелева [2].

На втором этапе работы (при отображении информации), НМ компенсирует или возвращает через умножение подстановок возмущения системы, введенные в неё при программировании.

Подстановки рассматриваемого вида не создают особых проблем на абстрактном уровне. Однако их сложно реализовать технически. Если элементам подстанов ⎜^{⎛ 012345} ⎟^⎞ поставить в со-

\ J J А Л “ i ответствие физические объекты, их нельзя переставить – нет свободного места.

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

Отображениечерезшрифтоносительравносиль-ноумножению двух подстановок. Перваяотобража-ет знаки на шрифтоноситель, вторая компенсирует деформации и размещает знаки в новом начертании в исходном порядке в «пустом» месте –

012345⎞ ⎛012345⎞ ⎛012345⎞305214 ⎟⎠ ⎜⎝143052 ⎟⎠=⎜⎝012345 ⎟⎠.

Компенсация деформаций необходима, т.к. порядок размещения знаков на новом месте, после операций со шрифтоносителем, не обязательно является первоначальным.

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

Таблица 3. Пример фильтрации для букв А

0	1	2	3	4	5	6	7	...	n
x	x	A	x	Б	x	A	Б	...	x
0	0	1	0	0	0	1	0	...	x
0	1	0	0	0	1	0	0	...	0

В первой строке таблицы 3 помещены номера знакомест, во второй – фильтруемый текст, в третьей – текст после фильтрации. Отфильтрованный текст составлен из нолей и единиц. В третьей строке ноли – представители любых знаков, кроме буквы A, единицами представлены буквы A. Буквой x во второй строке обозначены знаки фильтруемого текста, не являющиеся буквами A или Б, n – число знаков в строке текста. Приемником информации служит, например, циклический сдвигающий регистр.

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

Сдвигврегистревыполняетсяна«пустое»мес-

⎛ 01234567... n ⎞ то с помощью подстановки ⎜ ⎟

⎝n0123456...(n -1)⎠ - циклического вращения на одну позицию влево.

Если сдвигающих регистров много,сколько разных знаков в шрифтоносителе, отфильтрованные представители хранятся непосредственно в них.Это позволяет устранить неопределенность в наборе.

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

Таблица 4. Пример фильтрации для букв Б

0	1	2	3	4	5	6	7	...	n
x	x	A	x	Б	x	A	Б	...	x
0	0	0	0	1	0	0	1	...	0
0	0	1	0	0	1	0	0	...	0

В первой строке таблицы 4 помещены номера знакомест в виде положительных целых чисел, начинающиеся с ноля. Вторая строка занята исходным текстом, в котором явно показаны только буквы A и Б. Третья строка занята представителями букв Б – единицами, и нолями – представителями других знаков. Третья строка получена ⎛ 01234567 ...n ⎞ после реализации подстановки ⎜ _{01234567 ...}n ⎟ _– тождественного отображения информации, относящейся к букве Б, в пустой сдвигающий регистр.

Четвертая строка повторяет третью после сдвига ее содержимого на две позиции влево в общем, циклическом сдвигающем регистре. Сдвиг на две позиции соответствует второму месту знака Б в шрифтоносителе. Он выполняется с уче-

0    1234567 .....n том подстановки ⎜⎝(n - 1)n0123456 ...(n - 2) ⎟⎠-циклического вращения на две позиции влево в абсолютных координатах. Сдвинутая информация является управляющим словом для канала, закрепленного за этим видом знаков в НМ.

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

Содержимое общего сдвигающего регистра сбра-сывается.Не сброшенным остается только накопленный (суммарный)сдвиг общего для всех знаков набираемой строки регистра управляющих слов. Он составлен из номеров знаков в шрифтоносителе. Выше это были числа 1 и 2.Общий сдвиг от двух подстановок a + b = (1 + 2) mod n = 3,где a = 1, b = 2.

Если в шрифтоносителе расположение матриц букв А и В изменить, не изменяя установленную нумерацию позиций матриц, закрепленные за ними подстановки изменятся. Букве А будет от-

⎛ 0     1234567...n ⎞ вечать подстановка ⎜                            ⎟,

⎝(n-1)n0123456...(n-2)⎠

⎛ 01234567... n ⎞ букве Б – подстановка                    .

⎝n0123456...(n - 1)⎠

Величина сдвига для буквы А станет равной 2 ( а = 2), для буквы Б она равна 1 ( b = 1). Подстановка для А реализуется первой, затем подстановка для буквы Б. Относительный сдвиг равен 1.

Суммарный сдвиг от действия двух подстановок в этом случае образуется суммой ( b + a )mod n = (2 + 1)mod n = 3. Следовательно, от перестановки знаков в шрифтоносителе суммарный сдвиг не зависит. Суммарный относительный сдвиг ( a + b )mod n = 2. Это эффект конвейера.

СпособностьконвейеризованныхНМииханало-гов работать правильно с любым вариантом шрифтоносителя делает их универсальными устройствами. Поэтому конвейеры, как системы, применимы в разных областях. Другие знаки алфавита в исходном тексте обрабатываются при программировании НМ по аналогии с обработкой знаков А и Б.

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

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

Затем производится сортировка сумм вместе с отметками в порядке возрастания их величин.Одно-временно,как правило,нарушается исходный порядок размещения знаков в тексте.Исходный текст де-формируется.Управляющие слова из представителей знаков генерируются над подстановками вращения в соответствии с деформированным третьим списком.

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

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

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

Таблица 5. Пример заполнения таблицы задержек для слова багги

Текст →		Б	А	Г	Г	И
	j ↓ \ i →	0	1	2	3	4
А	0	0	1**	2	3	4*
Б	1	1**	2	3	4	0
В	2	2	3	4	0	1
Г	3	3	4	0*	1**	2
Д	4	4	0	1	2	3
↑ Алфавит

Cлучаи одинаковых задержек t_о = 1 в строках таблицы отмечены двумя звездочками. Знаки А, Б и Г при реализации набора набираются в один такт работы системы. Оставшиеся знаки набираются в моменты t_о = 0 и t_о = 4.

Суммы получаются одинаковыми вне зависимости от разрывов в диагоналях. Если одна диагональ с эквивалентными суммами заканчивается, делается переход на другую. Такое явление наблюдается, в частности, в таблице 5. Его уместно назвать автокоммутативностью.

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

Заключение

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