Буферное запоминающее устройство Советский патент 1992 года по МПК G11C19/00 

Изобретение относится к вычислительной технике и может быть использовано при построении средств ввода одиночного потока данных в мультипроцессорные вычислительные системы (МВС) класса одиночный поток команд - множественный поток Данных.

Известно буфернсе запоминающее устройство (БЗУ), содержащее накопители по числу каналов ввода МВС и блоки управления, которое обеспечивает согласование интенсивности входного потока данных с пропускной способностью многоканального ядра обработки.

Недостатком известного БЗУ являются большие затраты на реализацию блоков управления и ограниченная пропускная способность из-за невозможности расслоения памяти при записи.

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

Известное БЗУ позволяет осуществлять реконфигурацию при изменении числа каналов ввода МВС, преобразовать одиночный поток данных в множественный поток, что необходимо при вводе информации от устройств сканирования изображений в МВС, и обеспечивать высокую пропускную способность за счет перекрытия временных диаграмм накопителей.

Однако при обработке цифровых изображений поле результирующего изображеЧ 00

00

ел

00

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

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

На фиг. 1 показана структурная схема БЗУ; на фиг. 2 - схема коммутатора; на фиг. 3 - схема блока формирования накопителя; на фиг. А - схема блока формирования начального адреса; на фиг. 5 - схема блока селекции накопителей, на фиг, б - схема блока управления.

Устройство содержит накопители 1i,.. ,1s, коммутатор 2, блок 3 управления, мультиплексор 4 адреса, счетчик 5 адреса записи, счетчик 6 адреса чтения, блок 7 селекции накопителей, блок 8 формирования начального адреса, первый 9 и второй 10 блоки формирования номера накопителя, регистр 11, реверсивный счетчик 12, делитель 13. первый 14 и второй 15 сумматоры- вычмтатели, информационные входы 16,

информационные выходы 17i17s, входы

18 загрузки устройства, вход 19 синхронизации загрузки устройства, первый управляющий вход 20 (вход заявки записи), второй управляющий вход 21 (вход заявки чтения), третий управляющий вход 22 (вход режима). Информационные входы накопителей 1i. ..,1s объединены и соединены с информационными входами 16. Адресные входы накопителей 1i. .1s подключены к выходам мультиплексора А адреса, входы операции - к первому выходу 23 блока 3 управления, соединенному также с адресным входом мультиплексора 4 и вторым входом блока 7 селекции накопителей, входы выбора - к первым выходам 24i . 24s блока 7 селекции накопителей Информационные выходы

25i25s накопителей 1i.,.1s соединены с

информационными входами коммутатора 2, первый 26, второй 27 и третий 28 стробиру- ющие входы которого подключены соответственно к девятому, десятому и одиннадцатому выходам блока 3 управления, а адресные входы 29 коммутатора 2 соединены с четвертыми входами блока 7 селекции накопителей и выходами второго

0 сумматора-вычитателя 15. Информационные входы мультиплексора 4 адреса под- кл ючены к выходам счетчика 5 адреса записи и вторым выходам 30 первого блока 9 формирования номера накопителя и к вы5 ходам первого сумматора вычитателя 14. Информационные входы счетчика 5 адреса записи соединены с первыми выходами 31 блока 8 формирования начального адреса, вторые выходы 32 которого подключены к

0 информационным входам счетчика 6 адреса чтения. Вход записи счетчика 5 соединен с третьим выходом 33 блока 9 и вторым входом блока 8 формирования начального адреса. Первые входы блока 7 селекции

5 накопителей подключены к первым выходам 34 блока 9, третий вход 35 - к второму выходу блока 3 пятый вход 36 - к четвертому выходу 3, входы загрузки и вход синхронизации загрузки блока 7 - соответственно

0 к входам 18 и 19 устройства. Вторые выходы 37 блока 7 соединены с третьими входами второго блока 10 формирования номера накопителя. Счетные входы счетчиков 5 и 6 подключены к третьему 38 и пятому 39 вы5 ходам блока 3. Первый 40 и второй 41 входы второго блока 10 соединены с шестым и седьмым выходами блока 3 соответственно, а первый вход 42 первого блока 9 -с восьмым выходом блока 3. Входы загруз0 ки обоих блоков 9 и 10 и информационные входы регистра 11 перекрытия соединены с входами 18 устройства, а входы синхронизации загрузки блоков 9 и 10 и вход записи регистра 11 с входом 19 устройства. Чет$ вертый выход 43 второго блока 10 подключен к входу записи счетчика 6 адреса чтения, Первый выход второго блока 10 формирования номера накопителя соединен с первым входом второго сумматора вычитателя

0 15, второй вход которого подключен к счетчику 12 перекрытия. Входы первого сумматора-вычитателя 14 соединены с выходами счетчика 6 адреса чтения и счетчика 12 перекрытия соответственно Вход 44 операции сумматора-вычитателя 14 соединен с двенадцатым выходом блока 3 управления, а вход 45 трансляции кода счетчика 6 - с тринадцатым выходом блока 3 управления. Аналогичные входы 46 и 47 второго сумматора-вычитателя 15 подключены к семнад5

цатому и восемнадцатому выходам блока 3 управления. Информационные входы счетчика 12 перекрытия связаны с выходами регистра 11 перекрытия, вход записи - с четырнадцатым выходом 48 блока 3, вход +1 - с пятнадцатым выходом 49 и вход -1 - с шестнадцатым выходом 50 блока 3 управления. Информационные входы делителя 13 перекрытия также соединены с выходами регистра 11, счетный вход этого делителя 13 подключен к девятнадцатому выходу 51 блока 3, а выход делителя 13 - к четвертому входу 52 блока 3 управления. Коммутатор 2 состоит из мультиплексоров 53 по числу накопителей 1 с объединенными адресными входами, которые подключены к адресным входам 29 коммутатора 2, а информационные входы мультиплексоров 53i...53 соединены с информационными входами коммутатора 2. Принцип соединения входов мультиплексоров 53i...53s состоит -в циклическом сдвиге влево на один номер последовательности номеров входов, упорядоченной в порядке возрастания слева направо, при увеличении номеров мультиплексоров 53 от 1 до S. Мультиплексоры 53i и 53s имеют индивидуальные стро- бирующие входы, соединенные с первым 26 и вторым 27 стробирующими входами ком- мутатора, а у мультиплексоров 53i...53s-i стробирующие входы объединены и подключены к третьему стробирующему входу 28 кбммутатора 2, Блоки 9 и 10 формирования номера накопителя включают в себя счетчик 54 текущего номера накопителя, счетчик 55 начального номера накопителя, счетчик 56 процессоров, делитель 57 объема зоны процессора, делитель 58 каналов, первый 59 и второй 60 элементы ИЛИ, пер- вый 61 и второй 62 элементы задержки, регистры: начального номера накопителя 63, объема зоны процессора 64, количества каналов 65 и количества процессоров 66. На счетный вход счетчика 54 подается сигнал 42 модификации текущего номера накопителя с первого входа блока 9 (40 для блока 10), а на вход записи - с выхода второго элемента 60 ИЛ И. На счетный вход делителя 57 поступает сигнал с второго входа 41 бло- ка 10 (42 для блока 9). Коэффициент деления делителя 57 задается кодом с регистра 64 объема зоны процессора. Выход делителя 57 подключен к счетному входу счетчика 56 процессоров, сыходы которого явля- ются вторыми информационными выходами 30 блока 9 (младшие разряды адреса записи). Коэффициент деления счетчика 56 задается кодом в регистре 66. Сигнал пере-- носа счетчика 56 поступает на счетный вход счетчика 55, счетный вход делителя 58 и

через первый элемент 61 задержки на первый вход второго элемента 60 ИЛИ. второй вход которого соединен с четвертым выходом 43 блоков 9 и 10 и через второй элемент 62 задержки с входом 19 синхронизации загрузки блоков 9 и 10, подключенным к входами записи регистров 63, 64, 65 и 66. Информационные входы счетчика 54 соединены с выходами счетчика 55. а выходы счетчика 54 являются первыми выходами 34 блока 9. Выход делителя 58 каналов соединен с первым входом первого элемента 59 ИЛИ, второй вход которого подключен к второму входу второго элемента 60 ИЛИ, четвертому выходу 43 блока 10 и выходу второго элемента 62 задержки. Выход первого элемента 59 ИЛИ соединен с входами записи счетчика 55, делителей 57 и 58 и третьим выходом 33 блока 9. Информационные входы регистров 63, 64 и 66 обоих блоков 9 и 10 подключены к входам 18 загрузки блоков 9 и 10, а входы регистра 65 - к информационным входам 37 блока 10 (18 для блока 9). Имеется и пятый выход блока 10 - выход делителя 58. Блок 8 формирования начального адреса содержит накапливающий сумматор 67, элементы 68 И-ИЛИ по числу разрядов сумматора 67. регистры: 69 объема зоны канала, содержащего поля объема зоны процессора и количества процессоров, и 70 начального адреса. Входы сумматора 67 соединены с выходами элементов 68 И-ИЛИ, одни входы которых подключены к выходам соответствующих разрядов регистра 69 и к входу 19 синхронизации блока 8, а вторые - к выходам соответствующих разрядов регистра 70 и к входу 33 записи блока 8. Входы записи регистров 69 и 70 соединены с входом 19 блока 8, их информационные входы - с входами 18 загрузки блока 8. Выходы 31 сумматора 67 являются первыми выходами блока, а выходы 32 регистра 70 - вторыми выходами 7.

Блок 7 селекции накопителей включает в себя регистр 71 конфигурации, регистр 72 номера накопителя, элементы 73 ИЛИ по паре на каждый разряд регистра 72. первый дешифратор 74 с парафазными входами, второй дешифратор 75, узел 76 переноса, формирователи 77 длительности и мультиплексор 78. Информационные входы регистра 71 соединены с входами 18 загрузки блока 7, вход записи этого регистра 71 - с входом 19 синхронизации загрузки Выходы регистра 71 подключены к входам второго дешифратора 75, стробирующий вход которого соединен с входом выбора мультиплексора 78 и вторым входом 23 блока 7. Выходы дешифратора 75 подключены к узлу 76 переноса, выходы которого являются вторыми выходами 37 блока 7. Информационные входы мультиплексора 78 соединены с первыми 34 и четвертыми входами блока 7, а выходы мультиплексора 78 - с входами регистра 72, вход записи которого подключен к пятому входу 36 блока 7. Прямые и инверсные выходы каждого разряда регистра 72 соединены с первыми входами соответствующих каждому разряду паре элементов 73 ИЛИ, а вторые входы каждой пары элементов 73 ИЛИ объединены и подключены к соответствующим выходам узла 76 переноса. Парафазные входы дешифратора 74 соединены с выходами элементов 73 ИЛИ, а выходы дешифратора 74 - с входами формирователей 77 длительности, выходы которых являются первыми выходами 24i...24s блока 7.

Блок 3 управления содержит генератор 79, элемент 80 И, счетчик 81, триггер 82 пуска, триггер 83 режима, триггер 84 операции и программируемую логическую матрицу (ПЛМ) 85. S1-входы триггера 82 пуска соединены с первым 20 и вторым 21 входами блока 3, по которым поступают сигналы Заявка ЗАП (20) и Заявка ЧТГ (21). Вход триггера 83 режима подключен к третьему входу 22 блока 3. Режимы работы предлагаемого БЗУ идентичны режимам известного БЗУ (2). Единичный выход триггера 84 операции является первым выходом 23 блока 3. Выходы ПЛМ 85 являются остальными выходами блока 3. S-вход триггера 84 соединен с первым входом 20, а R-вход - с вторым входом 21 блока 3 Выход генератора 79 через элемент 80 И подключен к счетному входу счетчика 81. Второй вход элемента 80 И соединен с выходом триггера 82. Входы ПЛМ 85 подключены к выходам: счетчика 81, триггера 84 операции, обоим выходам триггера 83 режима, к четвертому 52 и к пятому 86 входам блока 3. Последний вход 86 блока 3 соединен с прямым выходом блока 10.

Устройство работает следующим образом, Сначала осуществляется загрузка, позволяющая настроиться на конкретные условия. Работа предлагаемого устройства при нулевом перекрытии во многом аналогична работе известного устройства 2, так как вновь введенные элементы никакого изменения в работу не вносят. Поэтому далее рассматривается работа устройства с ненулевым перекрытием предполагает, что участки, близкие к границам между фрагментами, находятся одновременно в двух соседних процессорных элементах. Поэтому при вводе перекрытия слева текущий номер накопителя уменьшается на единицу, а справа - наоборот, увеличивается на единицу Адрес элемента изображения в зоне перекрытия определяется для перекрытия слева как разность начального

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

0 адреса и увеличивающегося значения перекрытия. При формировании номера накопителя в случае чтения элементов зоны перекрытия используются log2S младших разрядов счетчика 12 перекрытия. Загрузка

5 блоков 7, 8, 9, 10 осуществляется аналогично известному устройству (2), т.е. данные по конфигурации МВС, количество процессоров в каждом канале, количество каналов определяются по тем же правилам.

0

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

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

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

0 формировании номера накопителя и адреса, обеспечивая обращение за элементами зоны перекрытия в зону соседнего фрагмента. В случае чтения элементов зоны перекрытия, расположенной слева от основного

5 фрагмента, содержимое регистра 11 переписывается в счетчик 12 по сигналу записи на четырнадцатом выходе 48 блока 3 управ- пения. При поступлении заявки чтения на второй вход 21 блока управления формиру0 ется каждый раз сигнал модификации (-1) счетчика 12 на шестнадцатом выходе 50 блока 3 и сигнал +1 для делителя 13 на девятнадцатом выходе 51 блока 3 управления. Заявка 21 чтения устанавливает триггер 84

5 операции в положение чтение, формируя соответствующий сигнал на выходе 23 блока 3 Это сигнал подключает выходы первого сумматора-вычитателя 14 через мультиплексор 4 адреса к адресным входам накопите0 лей 1т1$. ПЛМ 85 блока 3 формирует на

выходе 35 сигнал Выбор накопителей. Этот сигнал стробирует дешифратор 74 блока 7. Одновременно сигнал 23 Зап/Чт разрешает поступление на вход регистра 72 через

5 мультиплексор 78 кода с выходов второго сумматора-вычитателя 15 и разблокирует второй дешифратор 75 блока 7, разрешая участие в работе блока 7 и регистра 71 кон- фигураиии. Кодировка конфигурации МВС в данном случае не отличается от аналогич ной кодировки в известном устройстве 2

При чтении данных работает второй блок 10 формирования номера накопителя. В качестве коэффициента деления делителя 58 каналов используется код на выходах 37 узла 76 переноса блока 7. Заявка 21 чтения поступает от MB С на второй вход блока 3 управления, устанавливая в единицу триггер 82 и в нуль триггер 84. После этого импульсы с генератора 79 через элемент 80 И поступают на вход счетчика 81. С выходов ПЛМ 85 поступают сигналы в соответствии с микропрограммой чтения. Сигнал 23 Зап/Чт с выхода триггера 84 стробирует дешифратор 75 блока 10, ко- торый управляет формированием сигналов 24i24s в зависимости от кода конфигурации в регистре 71. При коде 001 (для случая восьми накопителей) производится чтение

из всех накопителей 1i1s, при коде ОЮ-

сначала нечетных накопителей 1, затем четных, при коде 100 - первый и пятый, затем второй и шестой и т.д.

Вначале читаются данные из соседнего (левого) накопителя 1. Для первого канала ввода МВС левое перекрытие нулевое, поэтому мультиплексор 53i коммутатора 2 не стробируется сигналом 26 с выхода блока 3 управления. Сумматор-вычитатель 15 сигналами 46 и 47 с выходов блока 3 переводится в режим вычитания, т.е. из номера блока памяти, формируемого блоком 10, вычитается содержимое младших разрядов счетчика 12, обеспечивая подключение к соответствующему каналу ввода МВС данные из пе- рекрываемой зоны соседнего (левого) фрагмента. Счетчик 12 переводится в режим вычитания. Сигнал -1 на входе 50 счетчи- ка 12 формируется после каждой заявки 21 чтения, которая модифицирует также номер накопителя 1, формируемый блоком 10 на своих первых выходах, и содержимое делителя 13. Модификация адреса чтения, формируемого счетчиком 6, осуществляется после S заявок чтения. Сумматор-вычита- тель 14 находится также как и 15 в режиме вычитания, вычитая из адреса чтения величину перекрытия из счетчика 12. Сигнал на выходе 52 делителя 13 свидетельствует об окончании зоны перекрытия, после чего сумматоры-вычитатели 14 и 15 переводятся в режим трансляции, передавая содержимое счетчика в адреса чтения и блока 10 формирования номера накопителя соответственно. При чтении данных фрагмента стробы 26, 27 и 28 подаются на все мультиплексоры 53i53s коммутатора 2. После

появления сигнала 86 Конец строки с выхода делителя 58 блока 10 сумматоры-вычитатели 14 и 15 переводятся в режим суммирования, а счетчик 12 также работает

как суммирующий. Стробы подаются на все мультиплексоры 53, кроме последнего 53s. Адрес накопителей 1 формируется как сумма адреса чтения и кода перекрытия, который меняется от нуля до заданного значения, а номер накопителя 1 - как сумма текущего номера накопителя, и младших разрядов счетчика 12. После появления сигнала 52 на выходе делителя 13 устройство переводится из режима перекрытия справа в режим перекрытия слева и т.д.

Преимущества предлагаемого устройства заключаются в более широких функци- ональных возможностях . за счет обеспечения программируемого перекрытия фрагментов, что позволяет обойтись без дополнительного объема памяти в БЗУ и обеспечить устранение разрывов при параллельной обработке на МВС. Формула изобретения Буферное запоминающее устройство, содержащее накопители, выходы которых соединены с информационными входами коммутатора, мультиплексор адреса, выходы которого подключены к адресным входам накопителей, блок селекции накопителей, выходы группы которого соединены с входами выбора соответствующих накопителей, счетчик адреса записи, выход которого соединен с информационными входами группы старших разрядов мульти- плексора адреса, блок формирования начального адреса, первый выход которого соединен с информационным входом счетчика адреса записи, первый и второй блоки формирования номера накопителя, причем выход первого блока формирования номера накопителя подключен к первому входу блока селекции накопителей, второй выход - к информационным входам группы младших разрядов мультиплексора адреса, третий выход - к первому входу блока формирования адреса и входу записи счетчика адреса записи, счетчик адреса чтения, информационный вход которого соединен со вторым выходом блока формирования начального адреса, вход записи счетчика адреса чтения подключен к первому выходу второго блока формирования номера накопителя, первый вход которого соединен с первым выходом блока селекции накопителей, блок управления, первый выход которого подключен к входам признака операций накопителей, к первому управляющему входу мультиплексора адреса и к второму .входу блока селекции накопителей, третий и четвертый входы которого соединены с вторым и четвертым выходами блока управления соответственно, третий выход которого соединен со счетным входом счетчика адресэ записи, пятый выход блока управления соединен со счетным входом счетчика адреса чтения, шестой и седьмой выходы блока управления подключены соответственно к второму и третьему входам второго блока формирования номера накопителя, восьмой выход блока управления соединен с первым входом первого блока формирования номера накопителя, пятый вход блока селекции накопителя соединен с первым управляющим входом коммутатора, выходы которого являются информационными выходами устройства, информационными входами которого являются информационные входы накопителей, входы загрузки и входы синхронизации загрузки блока формирования начального адреса, первого и второго блоков формирования номера накопителя и блока селекции накопителей являются соот- ветственно входами загрузки и синхронизации загрузки устройства, первый, второй и третий управляющие входы которого подключены соответственно к первому, второму и третьему входам блока управления, отличающееся тем, что, с целью расширения области применения устройства путем ввода данных с перекрытием, в него введены первый и второй сумматоры- вычитатели, реверсивный счетчик, делитель и регистр, причем второй, третий и четвертый управляющие входы коммутатора соединены соответственно с девятым, десятым и одиннадцатым выходами блока управления, двенадцатый и тринадцатый выходы которого соединены соответственно с первым и вторым управляющими входами первого сумматора вычитателя, выход которого соединен с информационным входом мультиплексора адреса, информационные входы первого сумматора-вычитателя соединены соответственно с выходами счетчика адреса чтения и реверсивного счетчика, информационный вход которого соединен с выходом регистра, информационный вход которого подключен к входу загрузки устройства, а вход записи - к входу синхронизации загрузки устройства, первый, второй и третий управляющие входы реверсивного счетчика соединены соответственно с четырнадцатым, пятнадцатым и шестнадцатым выходами блока управления, информационный вход второго сумматора- вычитателя соединен с пятым входом блока селекции накопителей и первым управляющим входом коммутатора, первый и второй информационные входы второго сумматора-вычитателя соединены соответственно с вторым выходом второго блока формирования номера накопителя и выходом реверсивного счетчика, первый и второй управляющие входы второго сумматора-вычитателя соединены соответственно с семнадцатым и восемнадцатым выходами блока управления, девятнадцатый выход которого соединен со счетным входом делителя, информационный вход которого соединен с выходом регистра, выход делителя подключен к четвертому входу блока управления, пятый вход которого соединен с третьим выходом второго блока формирования номера накопителя.

/

я

ху Фнп

Изобретение может быть использовано для ввода цифровых изобретений в мультипроцессорные вычислительные системы класса одиночный notoK команд - множественный поток данных, позволяющие организовать параллельную обработку нескольких фрагментов. Однако геометрические преобразования изображений, выполняемые над каждым фрагментом отдельно, приводят к разрывам на границах между соседними фрагментами. Для устранения этого эффекта в предлагаемом устройстве чтение осуществляется с перекрытием соседних фрагментов. С этой целью дополнительно введены два суммато- ра-вычитателя, реверсивный счетчик, делитель и регистр, назначение которых состоит в обеспечении возможности формирования адреса ячейки памяти и номера накопителя, соответствующих зоне перекрытия соседнего фрагмента. 6 ил. СО С

18SC8II

t+(o)M

l89C8il

iM

U

ii Uwv

л

Л

3

:«

«A

ч .

«

V H

«s

4

s

«I