ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ПЕРЕКЛЮЧАЕМОЙ СТРУКТУРОЙ Российский патент 1997 года по МПК G11C11/00 

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

Известно устройство, содержащее блоки (модули) памяти, одноименные линии входов адреса, входов управления, входов данных и выходов данных которых соединены между собой и являются соответственно линиями входа адреса первой группы, линиями входа управления, линиями входа данных и линиями выхода данных устройства, а выходы идентификации (готовности) которых являются выходами идентификации (готовности) устройства, и дешифратор, линии входа которого являются соответственно линиями входа адреса второй группы, а выходы которого соединены с входами выбора модуля соответствующих блоков (модулей) памяти. Адрес любого элемента многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек памяти данного устройства, может быть представлен в двоичной разрядной сетке совокупностью векторов, определяющих адреса элементов этого массива в соответствующих измерениях. При этом адрес любого элемента многомерного массива в данном устройстве может быть представлен только в одном формате адреса, что позволяет для любых двух соседних элементов в произвольном измерении многомерного массива обращаться к одному элементу по адресу, полученному путем модифицирования адреса другого элемента на константу, значение которой различно для различных измерений массива [1]
Однако данное устройство не позволяет для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек памяти данного устройства, обращаться к одному элементу по адресу, полученному путем модифицирования адреса другого элемента на единицу.

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

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

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

Целью изобретения является расширение функциональных возможностей устройства.

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

Адрес любого элемента Q-мерного массива может быть представлен в двоичной разрядной сетке совокупностью Q векторов, для которых справедливо утверждение, что значение q-го вектора, где q целое число, удовлетворяющее условию
1≅q≅ Q,
определяется значением q-го индекса. Количество двоичных разрядов адреса i, необходимое для адресации элемента Q-мерного массива, может быть определено по формуле

где i_q количество двоичных разрядов адреса, необходимое для адресации элемента в q-ом измерении массива. Значение i_q является целым числом, удовлетворяющим условию
0 ≅ (i_q log₂D_q)<1,
где D_q максимальное значение, принимаемое q-ым индексом. Очевидно, что в множество ячеек памяти запоминающего устройства (ЗУ) может быть взаимно однозначно отображено множество элементов многомерного массива, размерность которого Q определяется целым числом, удовлетворяющим условию
1 ≅ Q ≅ M,
где M количество линий входа адреса ЗУ, если количество двоичных разрядов адреса i, необходимое для адресации элемента Q-мерного массива, удовлетворяет условию
1 ≅ i ≅ M.

При этом число разрядов адреса d, определяемое выражением
d M i,
может быть произвольно распределено между Q векторами в адресе элемента Q-мерного массива. Формат адреса элемента Q-мерного массива может быть задан Q способами, отличающимися порядком расположения векторов, и, по крайней мере, Q способами, при которых младшие разряды адреса, представленного в q-ом формате, соответствуют q-му вектору. Каждому формату адреса может быть присвоен уникальный код код формата. Кроме того, q-му формату адреса может быть поставлен в соответствие базовый формат адреса, в качестве которого может быть выбран любой из Q форматов адреса. При этом каждый формат адреса предполагает определенную физическую организацию данных в памяти, а каждое установленное соответствие между q-ым и базовым форматами адреса предполагает отображение одной физической организации данных в памяти в другую и задает q-ю структуру хранения. Для реализации q-й структуры данных, включающей выбор q-й структуры хранения, достаточно преобразовать q-й формат адреса в базовый формат адреса. Функция, аргументом которой является значение кода формата, описывающая преобразование некоторого формата адреса в базовый формат адреса, может быть представлена в табличном виде и реализована аппаратно. Очевидно также, что, если q-й формат адреса может быть получен в результате циклического сдвига адреса, представленного в базовом формате, то q-я структура данных может быть реализована функцией циклического сдвига влево адреса, представленного в q-ом формате, на число разрядов адреса k, удовлетворяющее условию
0 ≅ k ≅ M,
и, определяемое номером разряда адреса, представленного в базовом формате, соответствующим младшему разряду q-го вектора. При этом q-му формату адреса может быть присвоен код формата, значение которого также определяется номером разряда адреса, представленного в базовом формате, соответствующим младшему разряду q-го вектора. Так как младшему разряду q-го вектора может соответствовать любой номер разряда адреса, представленного в базовом формате, то для того, чтобы реализовать q-ю структуру данных в некотором ЗУ, достаточно, чтобы в этом ЗУ была аппаратно реализована функция циклического сдвига влево адреса, поступающего на вход адреса ЗУ, аргументом которой является число разрядов k, на которое сдвигается адрес. Так как фиксированное упорядоченное множество объектов и отношений между ними образует структуру, а в качестве объектов структуры могут рассматриваться ячейки памяти ЗУ, то для изменения структуры ЗУ достаточно изменить способ упорядочения линий адреса на его входе адреса. Аппаратная реализация функции циклического сдвига влево адреса, поступающего на вход адреса ЗУ, аргументом которой является число разрядов k, на которое сдвигается адрес, расширяет функциональные возможности рассматриваемого устройства, позволяя при необходимости изменять его структуру. Для переключения структуры ЗУ (для обеспечения возможности выбора реализуемой структуры данных) необходимо, чтобы ЗУ имело вход формата, предназначенный для передачи в ЗУ значения кода формата. Количество линий входа формата L может быть задано целым числом, удовлетворяющим условию
0 ≅ (L log₂M) <1.

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

На фиг. 1 приведена структурная схема предлагаемого устройства; на фиг. 2 пример реализации шифратора на интегральных микросхемах К531КП2 для устройства, вход адреса которого содержит четыре линии адреса, где A0, A1, A2, A3 входы адреса шифратора, B0, B1, B2, B3 выходы шифратора, C0, C1 входы формата шифратора.

Устройство, представленное на фиг. 1, работает следующим образом.

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

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

При обращении к устройству на вход 12 адреса шифратора 8 поступает m-разрядный адрес, который используется в предлагаемом устройстве как адрес с заданным форматом, а с выхода 9 шифратора 8 на входы 10 модулей 1 памяти и на вход 11 дешифратора 5 поступают соответственно младшие и старшие разряды адреса, представленного в базовом формате. Старшие разряды адреса являются адресом M блоков памяти. На одном из выходов 6 дешифратора 5 вырабатывается сигнал выбора модуля памяти, который поступает на вход 7 выбора модуля соответствующего модуля 1 памяти, и разрешает дальнейшее распространение сигналов, поступающих на вход 2 управления этого модуля 1 памяти со входа управления устройства.

При выполнении процедуры записи на линии входа-выхода данных устройства подаются данные, которые поступают на входы-выходы 3 данных модулей 1 памяти и записываются в модуль 1 памяти, номер которого определяет дешифратор 5. При выполнении процедуры считывания модуль 1 памяти, номер которого определяет дешифратор 5, выставляет на линиях входа-выхода 3 данных считываемые данные, которые поступают на вход-выход данных устройства.

Выход 7 готовности отмечает период занятости соответствующего модуля 1 памяти.

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

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

Изобретение относятся к вычислительной технике и может быть использовано в вычислительных устройствах и системах, предназначенных для обработки многомерных массивов данных. Целью изобретения является расширение функциональных возможностей устройства. Устройство содержит модули 1 памяти, выход 4 готовности устройства, дешифратор 5, вход 7 выбора модуля памяти, шифратор 8, линии входа 12 адреса и линии входа 13 формата, которые представляют дополнительные возможности при формировании адреса произвольной ячейки памяти устройства. Новое в устройстве - шифратор 8, позволяющий при обращении к произвольной ячейке памяти использовать различные форматы адреса. 2 ил.

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