Борис Цирлин
Если спросить в интернете о предмете, вынесенном в название, например у Яндекса, то, подключив Алису AI, тот даст в качестве ответа какой-нибудь лозунг типа:
pipeline — это фундаментальный паттерн организации цифровых процессов, позволяющий превратить хаотичный поток данных или задач в предсказуемый, управляемый и высокоэффективный конвейер,-
украсив это примерами конвейерной обработки команд в CPU или GPU и общим описанием соответствующих программистских приемов. На самом деле общеизвестные цифровые устройства, например, регистры, существуют и в конвейерной (далее pipeline) реализации. Их рассмотрению посвящена эта статья.
Впервые схема pipeline регистра была приведена в статье Д. Е. Маллера, но рассмотрение начнем с устройства моделирующего pipeline процесс, что-то типа распределителя импульсов, ячейка которого приведена на рис.1, а.
В статье "О совершенной реализации" (с которой лучше ознакомится, чтобы облегчить понимание излагаемого здесь) уже говорилось о так называемом С-элементе Малера (Г-триггер в отечественной литературе - последнего термина будем придерживаться и впредь). Этот логический элемент переключается в 1 (0) тогда и только тогда, когда все его входы равны 1 (0), что наводит на аналогию с гистерезисом, откуда и произошло русское название. С учетом сказанного ячейка может быть описана логическим уравнением:
Zi = ZiZi-1 v Zi~Zi+1 v Zi-1*Zi+1
Чтобы избежать излишнего формализма обозначим состояние Zi = 1 через P (рабочее состояние), а Zi = 0 - через Г (состояние гашения).
Рассмотрим некоторые свойства моделирующего pipeline. Пусть исходно все n ячеек рис.1, составляющих цепочку, находятся в состоянии Г, а источник, подключенный к первой ячейке, пытается закачать в нее (перевести ее в) состояние Р. Для осуществления этого первая ячейка должна быть в состоянии Г, как и следующая за ней вторая ячейка. Как впрочем и для дальнейшего продвижения рабочего состояния по цепочке, перед ячейкой в состоянии Р должны находится, как минимум, две в состоянии Г. С другой стороны, чтобы послать цепочку следующее состояние Р источник должен погасить первую ячейку и дальше состояние Г будет распространяться по цепочке до тех пор, пока не достигнет ячейки в состоянии Р, перед которой будет погашенная ячейка. Итак, чередуя посылку состояний Р и Г, передатчик сможет заполнить все цепочку, но при этом из сказанного следует, что ячейки в состояниях Р и Г будут чередоваться т.е. в состояниях Р будет только половина из общего числа n. Аналогично и приемник может получить из цепочки не более n/2 состояний Р при неработающем источнике, т.е. описанная цепочка обладает буферными свойствами, позволяя некоторым образом согласовать неравномерность работы источника и приемника. Но главное - этот принцип позволяет в n/2 раз ускорить темп выдачи информации по сравнению с чисто последовательным способом обработки.
Дальнейший путь использования моделирующего pipeline казалось бы очевиден: поскольку он принадлежит классу полумодулярных схем, а целью является построение устройств, принадлежащих тому же классу, то взяв такие же исполнительные элементы (например, элементы памяти) и объединив их с моделирующим pipeline по известной теореме Миллера, получим искомое. Но полученные таким образом решения зачастую, мягко говоря, не элегантны.
Целью дальнейшего рассмотрения является рассмотрение методов получения более оптимальных технических решений.
Сдвиговые pipeline регистры.
Первое устройство этого типа было предложено в уже упомянутой статье Маллера и представляет собой две цепочки из ячеек рис.1 - одна для хранения и передачи единиц, а вторая - нулей и имеющих общие инвертирующие элементы ИЛИ-НЕ в обратной связи. Схема ячейки этого регистра приведена на рис.2.
В нем состоянию Р соответствует наличие единицы на выходе одного из Г-триггеров ячейки, а состоянию Г (или как его еще называют - спейсеру) - ноль на обоих этих выходах. Наличие единицы на выходах обоих Г-триггеров ячейки является запрещенным (оно нарушает полумодулярность схемы) и это накладывает определенные требовании к работе источника, подключенного к первой ячейке такого регистра. Как бы то ни было эта схема оригинальна в том смысле, что используя как основу моделирующий pipeline ее создатель не пытался пришить к нему традиционные узлы (здесь элементы памяти), а просто удвоил оборудования и получил требуемый результат. Попытаемся ее улучшить используя совершенную реализацию.
Совершенная реализация ячейки моделирующего pipeline приведена на рис.3.
Заметим, что по сравнению c исходной схемой рис.1 здесь имеет место некоторая экономия оборудования и уж точно увеличение быстродействия. Поэтому первое, что хочется попробовать это пойти тем же путем и просто удвоить цепочку для получения регистра, но уже используя совершенную реализацию ее ячейки.
Для того, чтобы определить функции установки S и сброса R триггеров этой совершенной реализации выпишем логическое уравнение, например, элемента
Z1i схемы рис.2:
Z1i = Z1iZ1i-1 v Z1i~(Z1i+1 v Z0i+1) v Z1i-1*~(Z1i+1 v Z0i+1) =
= Z1iZ1i-1 v Z1i~Z1i+1 v Z1i*~Z1i+1*~Z0i+1 v Z1i-1*~Z1i+1*~Z0i+1
Из которого видно, что функция установки совершенной реализации элемента Z1i:
S1i = Z1i-1*~Z1i+1*~Z0i+1
Аналогично, для элемента Z0i имеем:
S0i = Z0i-1*~Z1i+1*~Z0i+1
С функциями сброса дело обстоит еще проще - нет необходимости учитывать состояние следующей ячейки соседней цепочки ибо если, например, Z0i+1 = 1, то Z1i нет необходимости сбрасывать, т.к и так Z1i =0. Таким образом имеем:
R1i = ~Z1i-1*Z1i+1
R0i = ~Z0i-1*Z0i+1
Полученная в результате совершенная реализация регистра Маллера приведена на рис.4. и, как ожидалось, оказалась экономичней прототипа.
Более интересна схема сдвигового регистра pipeline тоже основанная на совершенной реализации рис.3, использующая трехстабильные триггеры - рис.5.
Эта схема защищена Авт. св. СССР № 661606 и описана в книге "Автоматное управление асинхронными процессами в ЭВМ и дискретных системах", поэтому не будем углубляться в ум��заключения, приведшим к ее созданию. Заметим только, что ячейка прототипа (рис.2) имеет 3 состояния: 2 - Р (соответствующих 0 и 1) и Г - при котором информация в ячейке отсутствует - имеет место так называемый спейсер. Вот эти-то смыслы и закреплены за устойчивыми состояниями триггера. Известно, что последние в таких триггерах имеют общую характеристику, например две единицы и ноль или два нуля и единица. В рассматриваемой схеме выбрана первая. А на долю транзитных состояний достались состояния второго типа, т. е. признаком того или иного устойчивого состояния в этом триггере является наличие двух единиц на его выходах. Это своего рода обобщение совершенной реализации, где таким признаком является появление одной единицы. Из-за этого информация о том или ином состоянии из одной ячейки в другую передается не по одному проводу, а по паре. Таким образом приходится платить за сокращение числа элементов в такой ячейке. В функциях установки и сброса триггера этой ячейки явно прослеживаются аналогии с предыдущими схемами:
S1i = Zi-1*~Z0i-1*~Z1i+1*~Z0i+1
S0i = Zi-1*~Z1i-1*~Z1i+1*~Z0i+1
Ri = ~Z1i-1*~Z0i-1*Zi+1
Уплотнение pipeline
Все рассмотренные pipeline имеют один общий недостаток - неплотное заполнение информацией: при общем количестве n ячеек регистра в него можно записать не более n/2 бит. Рассмотрим пути решения этой проблемы, пусть даже за счет некоторого усложнения схемы.
Из-за чего имеет место неплотное заполнение информацией pipeline регистра? В них чтобы различить соседние биты их разделяют спейсером, т.е. между двумя ячейками в состоянии Р (хранящими информацию) расположена, как минимум, одна ячейка в состоянии Г (в которой информация стерта). Но соседние биты в pipeline регистре могут отличаться друг от друга и своими значениями. Их можно, очевидно, располагать в соседних ячейках без зазора. На этом принципе основана схема ячейки, так называемого, полуплотного pipeline - рис.6.
Она, как нетрудно заметить, очень схожа с ячейкой рис.4. Правда, правый триггер в последней заменен его отражением по вертикали, но это сделано только для большей лаконичности изображения. Разница заключается в функциях S установки триггеров этих ячеек, которые попарно и рассмотрим. Итак в неплотном pipeline рис.4 имеем:
S1i = Z1i-1*~Z1i+1*~Z0i+1
S0i = Z0i-1*~Z1i+1*~Z0i+1
где первые члены этих термов знаменуют собственно передачу информации из ячеек i-1 в i, а два последних свидетельствуют о состоянии Г ячейки i+1,
при котором такая передача допускается. А в полуплотном рис.6:
S1i = Z1i-1*~Z1i+1*~Z0i
S0i = Z0i-1*~Z0i+1*~Z1i
следующая (i+1)-я ячейка представлена только одним членом, который говорит о том, что в ней не записан бит с тем же значением, что пишется в данную ячейку i - там может быть спейсер или бит с другим значением. Зато при наличии последнего в самой ячейке i запись в нее блокируется третьими членами термов.
Предложенное решение позволяет очевидно повысить информационную емкость в случае чередующихся значений битов вплоть до значения n при среднем значении 3n/4 если информационная последовательность является бернуллиевской.
Эта схема защищена Авт. св. СССР № 1136216 и описана в упомянутой книге, представляя собой тот счастливый случай, когда заявленный эффект достигается без дополнительных затрат.
Дальнейшее развитие этой идеи приводит к регистрам с заполнением информацией
вообще без зазоров - плотным pipeline. Исходя из принципа, положенного в основу предыдущей схемы напрашивается решение, основанное на дополнительной маркировке каждого бита, с тем, чтобы соседние различались независимо от их значения. Для этого достаточно иметь всего два значения маркера, а для хранения такого маркированного бита хватает двух RS-триггеров, т.е. структура ячейки аналогична уже рассмотренным рис.4 и рис.6. Состояние Г при этом исключается, т.е. такой регистр всегда хранит информацию, хотя бы один бит. В последнем случае все ячейки регистра находятся в одном и том же состоянии. Описание алгоритма работы такого регистра начнем с анализа функций
установки S и сброса R триггеров его ячейки - рис.7.
Szi = Zi-1*~Zi+1*~Mi*~Mi+1 v Zi-1*~Zi+1MiMi+1
Rzi = ~Zi-1Zi+1~Mi*~Mi+1 v ~Zi-1*~Zi+1MiMi+1
Smi = Mi-1*~Mi+1ZiZi+1 v Mi-1*~Mi+1*~Zi*~Zi+1
Rmi = ~Mi-1Mi+1ZiZi+1 v ~Mi-1Mi+1*~Zi*~Zi+1
Нетрудно заметить, что первые два члена всех термов этих функций типичны для pipeline (по крайней мере для тех примеров, которые уже были рассмотрены) и означают лишь то, что в данную ячейку i из предыдущей i-1 будет записан бит (или метка), только отличающиеся своим значением от записанных в следующей ячейке i+1.
Два последних члена каждого терма разрешают эту запись если метка или бит из данной ячейки i уже переписаны в следующую ячейку i+1, а поскольку могли быть переписаны и 0, и 1, то для проверки этого факта необходимы две пары членов, что и приводит к удвоению числа термов в этих функциях. Причем для записи бита учитывается состояние меток и наоборот.
Таким образом источник, записывая очередной бит в этот pipeline должен снабдить его меткой, отличной от предыдущей, что обеспечит продвижение этой пары вплоть до ячейки, еще не передавшей свой бит в следующую. А как только эта передача осуществиться, станет возможным продвижение свежей информации как минимум еще на одну ячейку. Эта схема также описана в упомянутой книге и защищена Авт. св. СССР № 1372361. В последнем предлагаются и адаптеры для этого регистра, согласующими его входы и выходы с источником и приемником с традиционным интерфейсом.
Заключение
Конечно, приведенные примеры не покрывают возможные варианты реализации pipeline регистров. Так, например, не были рассмотрены решения на основе трехстабильных триггеров типа рис.5,- включив в такую ячейку дополнительный RS-триггер для хранения метки и можно получить плотный pipeline даже более экономичный, чем приведенный на рис.7. Такие ячейки тоже описаны в упомянутой книге и защищены Авт.св.СССР № 905860, № 1015441 и № 1076951.
Однако, чтобы не перегрузить статью громоздким техническим материалом, были отобраны те схемы, в которых легко прослеживалась первоначальная идея pipeline, условно говоря, сохранившие гены своего родоначальника рис.1.
Кроме того эти схемы являются практической иллюстрацией метода совершенной реализации, описанного в статье с очевидным названием.
