Патент на изобретение №2164037
|
||||||||||||||||||||||||||
(54) СПОСОБ ФОРМИРОВАНИЯ АДРЕСА
(57) Реферат: Изобретение относится к вычислительной технике и может быть использовано для формирования адресов программ и данных. Техническим результатом является расширение возможностей способа за счет произвольной адресации многомерного массива. Способ заключается в том, что перед сложением адреса области адресного пространства и смещения указывающего положение операнда в этой области вычисляют смещение путем аппаратного циклического сдвига в противоположном направлении на заданное число разрядов значения логического смещения. 1 ил. Изобретение относится к вычислительной технике и может быть использовано в устройствах универсальных и специализированных цифровых вычислительных машин для формирования адресов программ и данных. Известен способ формирования сегментированного адреса, заключающийся в том, что в каждой команде выделяют два отдельных поля адреса, используемых под номер сегмента и под номер байта внутри сегмента, определяют адрес сегмента и адрес байта и складывают полученные значения адресов. Этот способ для любых двух соседних элементов в произвольном измерении одномерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу. Однако данный способ для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, не позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу [1]. Известен способ формирования машинного адреса, заключающийся в том, что аппаратно циклически сдвигают на заданное число разрядов значение логического адреса, равное значению машинного адреса, циклически сдвинутому на это же заданное число разрядов, но в противоположном направлении сдвига. Этот способ для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек фиксированной области некоторого адресного пространства, позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу. Однако данный способ для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, не позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу [2]. Известен способ формирования исполнительного адреса, заключающийся в том, что аппаратно складывают адрес области адресного пространства, в которой размещен операнд, и смещение, указывающее положение этого операнда относительно начала данной области адресного пространства. Этот способ для любых двух соседних элементов одномерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу. Однако данный способ для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, не позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу [3]. Наиболее близким техническим решением к описываемому изобретению является способ формирования исполнительного адреса, заключающийся в том, что аппаратно складывают адрес области адресного пространства, в которой размещен операнд, и смещение, указывающее положение этого операнда относительно начала данной области адресного пространства. Этот способ для любых двух соседних элементов одномерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу. Данный способ для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, не позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу [3]. Целью изобретения является расширение возможностей способа. Поставленная цель достигается тем, что в способе формирования исполнительного адреса, заключающемся в том, что аппаратно складывают адрес области адресного пространства, в которой размещен операнд, и смещение, указывающее положение этого операнда относительно начала данной области адресного пространства, перед сложением адреса области адресного пространства и смещения вычисляют смещение путем аппаратного циклического сдвига на заданное число разрядов значения логического смещения, равного значению смещения, циклически сдвинутому на это же заданное число разрядов, но в противоположном направлении сдвига. Для раскрытия сущности предлагаемого изобретения особый интерес представляют два вида организации виртуальной памяти: страничная и сегментная и соответственно два способа управления виртуальной памятью: управление страничной памятью по запросам и управление сегментной памятью. При страничной организации памяти адресное пространство каждого задания делится на равные части, называемые страницами, и подобным образом физическая память делится на части одинакового размера, называемые блоками. При наличии соответствующих аппаратных средств преобразования любая страница может быть помещена в любой блок. Что же касается аппаратных средств, осуществляющих отображение адресного пространства на физическую память, то для каждой страницы должен быть предусмотрен специальный регистр; эти регистры в совокупности образуют таблицу переадресации страниц или таблицу страниц и могут либо представлять собой специальные аппаратные регистры, либо занимать часть основной памяти. Особенностью рассматриваемой страничной организации виртуальной памяти является управление страничной памятью по запросам, обусловленное отказом от требования, чтобы все адресное пространство задания одновременно находилось в основной памяти; вместо этого в память загружается только часть адресного пространства, а при попытке обращения к странице, отсутствующей в основной памяти, аппаратно генерируется страничное прерывание. Обработка этого прерывания должна заключаться в загрузке требуемой страницы в память и корректировке соответствующим образом элементов таблицы страниц. Прерванная команда после этого может быть повторена. Сегментная организация находит широкое применение в модульном программировании, при котором с целью упрощения понимания, написания и контроля программы и отдельных ее частей для реализации каждой функции используется отдельный программный модуль. Сегмент может быть определен как логическая группа информации, такая как программа, массив или область данных. Таким образом, адресное пространство каждого задания представляется в виде совокупности сегментов. Сегментация и является методом управления этими сегментами, который может быть реализован с помощью аппарата преобразования адресов, подобного механизму преобразования адресов, используемому в системах со страничной организацией памяти. Одним из способов формирования сегментированного адреса является представление адресного пространства как двумерного, адресуемого двумя компонентами: номером сегмента и номером байта. Преобразование двумерного сегментированного адреса в адрес линейной физической памяти осуществляется автоматически во время выполнения программы. Вычисление физического адреса при данном подходе сводится к сложению адреса области памяти, занимаемой сегментом, и смещения, определяющего положение операнда внутри сегмента. Данный способ формирования адреса физической памяти применим и для сегментно-страничного распределения памяти, сохраняющего достоинства сегментации и повышающего эффективность использования памяти, заключающегося в объединении двух схем распределения памяти – страничного распределения и распределения сегментами. Сегмент можно представить не как нечто единое и непрерывное, а как совокупность страниц или подсегментов. В этом случае способ формирования адреса физической памяти может быть легко сведен к сложению адреса области памяти, занимаемой подсегментом, и смещения, определяющего положение операнда внутри подсегмента. Данный способ формирования адреса позволяет решать проблемы, возникающие при адресации элементов одномерного массива, отображенных на множество ячеек некоторого адресного пространства, но для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области этого адресного пространства, не позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу. Как известно, адрес любого элемента Q-мерного массива может быть представлен в двоичной разрядной сетке совокупностью Q векторов, для которых справедливо утверждение, что значение q-го вектора определяется значением q-го индекса. Формат адреса элемента Q-мерного массива может быть задан Q! способами, отличающимися порядком расположения векторов, и, по крайней мере, Q способами, при которых младшие разряды адреса, представленного в q-м формате, соответствуют q-му вектору. Каждому q-му формату адреса может быть поставлен в соответствие базовый формат адреса, в качестве которого может быть выбран любой из Q! форматов адреса. При этом каждый формат адреса предполагает определенную организацию данных в ячейках некоторого адресного пространства, а каждое установленное соответствие между q-м и базовым форматами адреса предполагает отображение одной организации данных в ячейках этого адресного пространства в другую и задает q-ю структуру хранения. Для реализации q-й структуры данных, включающей выбор q-й структуры хранения, достаточно преобразовать q-й формат адреса в базовый формат адреса. Функция, описывающая преобразование некоторого q-го формата адреса в базовый формат адреса, может быть представлена в табличном виде и реализована аппаратно. Очевидно также, что, если q-й формат адреса может быть получен в результате циклического сдвига вправо адреса, представленного в базовом формате, то q-я структура данных может быть реализована функцией циклического сдвига влево адреса, представленного в q-м формате, на число разрядов адреса, определяемое номером разряда адреса, представленного в базовом формате, соответствующим младшему разряду q-го вектора. Так как младшему разряду q-го вектора может соответствовать любой номер разряда адреса, представленного в базовом формате, то для реализации q-й структуры данных, как известно, достаточно аппаратно реализовать функцию циклического сдвига адреса, аргументом которой является число разрядов, на которое сдвигается адрес. Поскольку фиксированное упорядоченное множество объектов и отношения между ними образуют структуру, а в качестве объектов структуры могут рассматриваться ячейки некоторого адресного пространства, то для изменения структуры этого адресного пространства достаточно изменить способ упорядочения адресных разрядов в двоичной разрядной сетке, в которой может быть представлено множество адресов всех ячеек рассматриваемого адресного пространства, а для изменения структуры адресного пространства некоторого устройства достаточно изменить способ упорядочения адресных выходов этого устройства. Аппаратная реализация функции циклического сдвига адреса на произвольное заданное число разрядов является ключевым звеном способа формирования машинного адреса, заключающегося в том, что аппаратно циклически сдвигают на заданное число разрядов значение логического адреса, равное значению машинного адреса, циклически сдвинутому на это же заданное число разрядов, но в противоположном направлении сдвига. Поскольку сегмент может быть определен как логическая единица информации, представляющая собой многомерный массив данных, а способ формирования машинного адреса для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек фиксированной области некоторого адресного пространства, позволяет адресовать один элемент адресом другого элемента, модифицированным на единицу, то для того, чтобы для любых двух соседних элементов в произвольном измерении многомерного массива, множество элементов которого взаимно однозначно отображается в множество ячеек произвольной области некоторого адресного пространства, адресовать один элемент адресом другого элемента, модифицированным на единицу, достаточно в способе формирования исполнительного адреса, заключающемся в том, что аппаратно складывают адрес области адресного пространства, в которой размешен операнд, и смещение, указывающее положение операнда относительно начала данной области адресного пространства, перед сложением адреса области адресного пространства и смещения вычислить смещение путем аппаратного циклического сдвига на заданное число разрядов значения логического смещения, равного значению смещения, циклически сдвинутому на это же заданное число разрядов, но в противоположном направлении сдвига. При этом логическое смещение и смещение могут соотноситься между собой так же, как и логический адрес и машинный адрес в известном способе формирования машинного адреса, представленные соответственно в q-м и базовом форматах. Аналогично, формат смещения может быть определен как базовый формат, а формат логического смещения – как q-й рабочий формат или просто как рабочий формат. Следовательно, логическое смещение и смещение могут различаться между собой форматами смещения, т. е. способами упорядочения векторов, заданных значениями индексов элемента многомерного массива данных. Таким образом, элемент многомерного массива данных, множество элементов которого взаимно однозначно отображается в множество ячеек области некоторого адресного пространства, может быть идентифицирован различными логическими адресами, каждый из которых может быть вычислен в результате сложения адреса данной области адресного пространства, и соответствующего логического смещения. Предлагаемый способ формирования адреса позволяет использовать дополнительные возможности при адресации соседних элементов многомерного массива, заключающиеся в таком взаимно однозначном отображении множества элементов этого массива в множество ячеек произвольной области некоторого адресного пространства, при котором адрес произвольного элемента многомерного массива может быть вычислен в результате инкрементирования или декрементирования адреса соседнего элемента в произвольном измерении этого массива, что позволяет повысить эффективность вычисления адресов элементов многомерных массивов, а также производительность вычислительных систем, реализующих предлагаемый способ формирования адреса и функции инкрементирования, декрементирования или функции обработки цепочек данных. На чертеже приведена схема формирования адреса, отображающая пример реализации предлагаемого изобретения, в котором для вычисления значения смещения используется шифратор, реализующий функцию аппаратного циклического сдвига значения логического смещения на произвольное заданное число разрядов. Предлагаемый способ формирования адреса реализован следующим образом. Возможности, предоставляемые данным изобретением, в наиболее полной мере могут быть использованы при адресации элементов цепочки данных, состоящей из последовательности элементов в произвольном измерении многомерного массива, т. е. элементов цепочки данных, взаимно однозначно отображенных в множество элементов в произвольном измерении многомерного массива. При этом изначально известно измерение многомерного массива, в котором в множество элементов этого массива отображаются элементы цепочки данных, и значения индексов элемента многомерного массива, в который отображается первый элемент цепочки данных. Кроме того, для наиболее полного использования возможностей, предоставляемых предлагаемым изобретением, понадобится выполнить ряд подготовительных шагов. Сначала необходимо множество элементов этого массива взаимно однозначно отобразить в множество ячеек оперативной памяти вычислительного устройства, в котором реализовано рассматриваемое изобретение. Ввиду того, что ситуация, при которой размер свободной области оперативной памяти не позволяет разместить в ней определенный массив данных, может быть разрешена с использованием методов управления памятью и, в конечном счете, не влияет на предлагаемый способ формирования адреса, то при рассмотрении этого способа можно ограничиться случаем, когда в оперативной памяти может быть выделена свободная область достаточного размера для размещения в ней данного многомерного массива. Установленное взаимно однозначное соответствие между множеством элементов многомерного массива и множеством ячеек оперативной памяти означает, что известны адрес выделенной области памяти и базовый формат смещения. Затем определяют все рабочие форматы логического смещения, которые только можно получить, циклически сдвигая вправо векторы базового формата смещения, и выбирают рабочий формат логического смещения, младшие разряды которого занимает вектор, задающий индекс выбранного измерения многомерного массива (т. е. измерения, в котором в элементы массива отображаются элементы цепочки данных). В следующем шаге определяют число разрядов, на которое следует циклически сдвинуть вправо базовый формат смещения, чтобы получить выбранный в предыдущем шаге рабочий формат логического смещения. Полученное значение задает число разрядов, на которое необходимо циклически сдвинуть влево значение логического смещения, чтобы вычислить значение смещения в базовом формате. Перечисленные действия могут быть учтены на этапе написания исходной программы и реализованы в процессе подготовки данной программы к выполнению, включая процесс загрузки в оперативную память. Для того, чтобы сформировать адрес для адресации первого элемента цепочки данных в выбранном измерении многомерного массива аппаратно циклически сдвигают влево на предварительно определенное заданное число разрядов значение логического смещения и полученное в результате циклического сдвига значение смещения складывают со значением адреса выделенной области памяти. Для того, чтобы сформировать адрес для адресации следующего элемента цепочки данных в выбранном измерении многомерного массива аппаратно циклически сдвигают влево на то же предварительно определенное заданное число разрядов инкрементированное (если адрес первого элемента цепочки данных совпадает с адресом цепочки данных) или декрементированное (если адрес последнего элемента цепочки данных совпадает с адресом цепочки данных) значение логического смещения, использованное при формировании адреса для адресации предыдущего элемента цепочки данных, и полученное в результате циклического сдвига значение смещения складывают со значением адреса выделенной области памяти. Таким образом, при адресации элементов цепочки данных, состоящей из последовательности элементов в произвольном измерении многомерного массива, взаимно однозначно отображенного в множество некоторой произвольной области памяти, рассматриваемое изобретение позволяет вычислять значение логического смещения для каждого следующего элемента цепочки данных путем инкрементирования или декрементирования значения логического смещения, использованного для адресации предыдущего элемента этой цепочки данных, что позволяет для любых двух соседних элементов в произвольном измерении данного многомерного массива адресовать один элемент адресом другого элемента, модифицированным на единицу. Источники информации 1. Мэдник С., Донован Дж. Операционные системы. – М.: Мир, 1978, с. 217 – 218. 2. Патент N 2092912 на изобретение “Запоминающее устройство с переключаемой структурой”, RU. 3. Скэнлон Л. Персональные ЭВМ IBM PC и XT. Программирование на языке ассемблера. – М.: Радио и связь, 1989, с. 18 – 19, рис. 1.1 (прототип). Формула изобретения
РИСУНКИ
MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 21.01.2005
Извещение опубликовано: 27.12.2005 БИ: 36/2005
|
||||||||||||||||||||||||||
