контроллер памяти, который выполняет команды считывания и записи не в порядке простой очереди

Формула изобретения

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

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

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

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

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

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

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

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

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

Описание изобретения к патенту

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

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

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

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

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

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

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

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

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

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

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

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

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

В дальнейшем изобретение будет охарактеризовано с использованием следующих чертежей.

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

Фиг. 2 - упрощенная блок-схема подсистемы памяти, показанной на фиг. 1.

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

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

Фиг. 5 - иллюстрация синхронизации последовательных операций записи в различные строки динамического запоминающего устройства с произвольной выборкой.

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

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

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

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

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

Фиг. 11 - таблица, иллюстрирующая выборы следующего адреса доступа записи для комбинаций посланных записей, которые могут содержать совпадения страницы (то есть строки); пропуски страницы; или совпадения страницы и пропуски страницы.

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

Фиг. 13 - иллюстрация высокоуровневого функционального представления буфера посланной записи, показанного на фиг. 8 и фиг. 12.

Фиг. 14 - иллюстрация функциональной логики управления указателями, показанной на фиг. 12, которая формирует основной указатель вводимых данных.

Фиг. 15 - иллюстрация функциональной логики управления указателями, показанной на фиг. 12, которая формирует выходной указатель.

Фиг. 16 - иллюстрация функциональной логики управления указателями, показанной на фиг. 12, которая формирует входной указатель.

Ниже будет приведен предпочтительный вариант реализации изобретения.

На фиг. 1 показаны части вычислительной системы 100, выбранной в качестве примера, относящейся к настоящему изобретению. Вычислительная система 100 содержит модуль 110 центрального процессора, который содержит, например, микропроцессор 113 и сверхоперативную память 115. Как хорошо известно, модуль 110 центрального процессора содержит также другую обычную схемотехнику, например, контроллер шины, интерфейс шины и аналогичные устройства, которые не показаны на этом чертеже. Модуль 110 центрального процессора имеет связь с подсистемой 120 памяти посредством шины 125 системы. Подсистема 120 памяти дополнительно содержит контроллер 130 памяти и множество динамических запоминающих устройств 135 с произвольной выборкой. Типовая вычислительная система 100 содержит другие компоненты, например, интерфейс ввода-вывода, дисководы и контроллеры дисководов, видеодисплеи, клавиатуры и аналогичные устройства, которые также не показаны на фиг. 1, для того, чтобы придать выразительность настоящему изобретению. Должно быть также очевидно, что другие такие компоненты могут иметь доступ к подсистеме 120 памяти при использовании транзакций прямого доступа к памяти через шину системы.

Шина 125 системы, показанная на фиг. 1, иллюстрируется как сложная (составная) шина. Квалифицированному в этой области техники специалисту будет очевидно, что шина 125 системы содержит множество линий адресации, множество линий передачи данных и множество линий передачи сигналов управления. Линии передачи сигналов управления могут содержать, например, линию ввод-вывод/память, которая делает выбор между командами перехода между модулем 110 центрального процессора и устройствами ввода-вывода (не показаны) или командами перехода между модулем 110 центрального процессора и подсистемой 120 памяти; и линию считывания/записи, которая делает выбор между командами перехода из подсистемы 120 памяти в модуль 110 центрального процессора (считывание) или из модуля 110 центрального процессора в подсистему 120 памяти (запись). Она может содержать также линии выбора байта, причем эти линии определяют какие байты данных в многобайтовом слове должны передаваться; и сигналы (инициирования одного или более циклов), которые возбуждаются микропроцессором 113 в модуле 110 центрального процессора для запуска цикла доступа. Например, в микропроцессоре Intel, например, 80486, Pentium или аналогичных микропроцессорах, микропроцессор для инициирования цикла доступа возбуждает сигнал строба адреса.

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

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

На фиг. 3 и фиг. 4 иллюстрируются, приведенные в качестве примера, диаграммы синхронизации для доступа считывания (фиг. 3) и доступа записи (фиг. 4) к этим динамическим запоминающим устройствам с произвольной выборкой. Как показано, контроллер 130 памяти содержит декодер 138 области памяти, синхрогенератор 140, мультиплексор 142 адресации строки/столбца и двунаправленный буфер 144 данных. Контроллер 130 памяти принимает множество разрядов адреса из шины 125 системы на множество линий 154 адресации, которые для ясности этой иллюстрации являются разрядами AD2-AD31 адреса. Линии выбора байта используются контроллером памяти вместо разрядов AD0 и AD1 адреса для выбора конкретных байтов четырехбайтового слова памяти, к которому нужен доступ. В некоторых системах слово памяти может иметь большее число байтов, а разряды AD2 адреса или выше могут быть заменены дополнительными линиями выбора байта для выбора между большим числом байтов. В варианте воплощение, описываемом в этой заявке, разряды AD20-AD31 используются для выбора конкретной подсистемы в ответ на доступ к шине 135 системы, например, подсистемы 120. Кроме того, в описываемом варианте осуществления разряды AD2-AD21 используются для выбора конкретной ячейки памяти в подсистеме 120 памяти. Должно быть также очевидно, что распределение разрядов AD0-AD31 для управления подсистемы 120 памяти изменится в соответствии с емкостью памяти и выбранной областью адресации подсистемы 120 памяти.

Линии 154 адресации связаны с мультиплексором 142 адресации строки/столбца. Квалифицированному в этой области техники специалисту будет очевидно, что для нормализации адресов перед сообщением адресов в мультиплексор 142 адресации строки/столбца, подсистема 120 памяти может содержать схему нормализации адресации (не показана). В приведенных в качестве примера системах на основе дисковых операционных систем, в которых используются процессоры семейства Intel, область адресации содержит ряд "дыр", вызванных распределением частей областей адресации, например, для запоминающего устройства с произвольной выборкой для хранения видеоинформации. Эти адреса косвенно адресованы операционной системой как ячейки памяти. Поскольку физические ячейки памяти, соответствующие этим "дырам", не будут использоваться иначе, схема нормализации адресации передает логические адреса выше начала "дыр" для переадресации доступов к физическим адресам, соответствующим ячейкам с "дырами". Такие схемы нормализации адресации хорошо известны на современном уровне техники и по этой причине не показаны на фиг. 2, 7 и 8 и не описываются в этой заявке.

Синхрогенератор 140 является чувствительным к управляющим сигналам из шины 125 системы для формирования соответствующих сигналов доступа к динамическим запоминающим устройствам 135 с произвольной выборкой. Декодер 138 области адресации декодирует адрес (содержащий разряды AD2-AD31 адреса), сообщаемые в контроллер 130 памяти, и определяет, находится ли сообщенный адрес в области адресации, выделенной для подсистемы 120 памяти. Декодер 138 области адресации обеспечивает активный выходной сигнал к синхрогенератору 140, если сообщенный адрес находится в пределах такой области адресации. Если активируется сигнал строба адреса на линии 150, в то время как активен выходной сигнал декодера 138 области адресации, то синхрогенератор 140 инициирует допуск к динамическим запоминающим устройствам 135 с произвольной выборкой. Если сигнал считывания/записи на линии 152 считывания/записи выбран для доступа считывания, этот доступ будет инициирован как доступ считывания. Аналогичным образом, если сигнал считывания/доступа выбран для доступа записи, то этот синхрогенератор инициирует доступ записи к динамическим запоминающим устройствам 135 с произвольной выборкой.

Контроллер 130 дополнительно принимает множество сигналов (D0-D31) данных с помощью соответствующего множества линий 156 передачи данных. Приведенная в качестве примера система, описываемая в этой заявке, является тридцатидвухразрядной системой. Должно быть очевидным, что приведенное ниже описание будет относиться к системам, имеющим большое число разрядов на слово данных.

Синхрогенератор 140 формирует сигнал строба адреса строки (RAS^*) на линии 160, сигнал строба адреса столбца (CAS^*) на линии 162, сигнал разрешения записи (WE^*) на линии 164, сигнал разрешения вывода (OE^*) на линии 166 и сигнал (S) выбора мультиплексора на линии 168. (Применяемая в этой заявке звездочка (^*) после названия сигнала указывает на активный низкий сигнал). Множественные сигналы строба адреса строки (RAS^*) и строба адреса столбца (CAS^*) могут быть обеспечены для множества блоков динамических запоминающих устройств с произвольной выборкой так, чтобы только некоторые из динамических запоминающих устройств с произвольной выборкой управлялись каждым сигналом строба адреса строки (RAS^*) и строба адреса столбца (CAS^*).

Функционирование, представленной в качестве примера, подсистемы 120 памяти будет кратко описано со ссылкой на диаграммы синхронизации, показанные на фиг. 3 и фиг. 4. Специалисту, знакомому с динамическими запоминающими устройствами с произвольной выборкой, будет очевидно, что цепи динамических запоминающих устройств с произвольной выборкой имеют, как правило, только половину линий адресации, необходимых для полной адресации ячеек памяти в каждой цепи. Например, для адресации динамического запоминающего устройства емкостью 1 мегабайт, имеющего 1048576 ячеек памяти, требуется 20 разрядов адресации; однако, вследствие ограничений штырьковых выводов и вследствие рабочих характеристик динамических запоминающих устройств с произвольной выборкой, предусматривают только 10 штырьковых выводов адресации. 20 разрядов адресации, необходимых для полной адресации динамического запоминающего устройства с произвольной выборкой, мультиплексируются в динамическое запоминающее устройство с произвольной выборкой по 10 разрядов адресации за один раз. В частности, сигнал (S) выбора мультиплексора сначала прикладывается к мультиплексору 142 адресации строки/столбца на первом логическом уровне для сообщения первых десяти разрядов адреса из шины 125 системы в качестве адреса строки, как иллюстрируется частью СТРОКА сигнала адреса (ADDR), показанного на фиг. 3. Исторически, самые значительные разряды разрядов адресации сообщаются как адрес строки, однако могут быть также использованы другие комбинации разрядов адресации с частью из наиболее значительных разрядов и частью из наименее значительных разрядов, (см., например, патент США N 5247643). После выбора разрядов адресации для адреса строки, синхрогенератор возбуждает сигнал строба адреса строки (RAS^*), как иллюстрируется на фиг. 3. После соответствующей задержки, определяемой частными характеристиками динамических запоминающих устройств 135 с произвольной выборкой, синхрогенератор 140 переключает уровень на селекторной линии 168, чтобы заставить мультиплексор 142 адресации строки/столбца сообщить остающиеся разряды адресации как разряды адреса столбца, как показано частью СТОЛБЕЦ сигнала адреса (ADDR) на фиг. 3. Синхрогенератор 140 активирует сигнал строба адреса столбца (CAS^*), чтобы заставить адрес столбца стробироваться в динамических запоминающих устройствах 135 с произвольной выборкой. Поскольку это является доступом считывания, сигнал разрешения записи (WE^*) на линии 164 становится неактивным, а сигнал разрешения вывода (OE^*) на линии 166 становится активным так, чтобы достоверные данные выводились из динамических запоминающих устройств с произвольной выборкой после короткой задержки, определяемой временем доступа адреса столбца. Буфер 144 также управляется сигналом разрешения вывода (OE^*) для передачи выходных данных из динамических запоминающих устройств 135 с произвольной выборкой в линии 156 передачи данных шины 125 системы. (В некоторых системах динамические запоминающие устройства 135 с произвольной выборкой могут быть непосредственно соединены с шиной 125 системы без использования буфера 144.)

На фиг. 4 иллюстрируется аналогичная последовательность синхронизации для доступа записи; однако до сообщения разрядов адреса столбца и возбуждения сигнала строба адреса столбца (CAS^*), активируется сигнал разрешения записи (WE^*) на линии 164, а сигнал разрешения вывода (OE^*) на линии 166 становится неактивным. Таким образом, данные передаются из шины 125 системы через буфер 144 в динамические запоминающие устройства 135 с произвольной выборкой и хранятся в них.

Как иллюстрируется на фиг. 3 и фиг. 4, доступ к динамическим запоминающим устройства 135 предусмотрен посредством двухэтапной операции, в которой адрес строки сообщается динамическим запоминающим устройствам 135 с произвольной выборкой и стробируется в динамических запоминающих устройствах с произвольной выборкой посредством возбуждения сигнала строба адреса строки (RAS^*). Это заставляет динамические запоминающие устройства начать доступ к множеству ячеек памяти для хранения данных, которые имеют общий адрес строки. Данные из всей строки передаются в выходной мультиплексор в каждом динамическом запоминающем устройстве с произвольной выборкой после задержки, называемой временем доступа строки. Множество разрядов данных, допущенных в одну строку, расположено в столбцах в строке. После этого, если адрес столбца сообщен динамическим запоминающим устройствам 135 с произвольной выборкой и возбужден сигнал строба адреса столбца (CAS^*), адрес столбца выбирает один из столбцов данных для вывода из каждого динамического запоминающего устройства 135 с произвольной выборкой. В альтернативном варианте, при доступе записи, данные, сообщенные на вход каждого из динамических запоминающих устройств 135 с произвольной выборкой, хранятся в выбранной строке в столбце, определенном выбранным адресом столбца.

Если в динамическое запоминающее устройство с произвольной выборкой сообщается новый адрес, то сигнал строба адреса строки (RAS^*) должен быть деактивирован в течение достаточного времени, чтобы позволить внутренним адресам строки перезарядиться и был сообщен новый адрес строки. Задержка, соответствующая времени доступа строки, снова имеет место прежде, чем адрес столбца может быть сообщен и выбран конкретный столбец данных для считывания или записи. Таким образом, как иллюстрируется на фиг. 5, имеет место значительное штрафное время каждый раз, когда инициируется доступ новой строки.

Большинство современных динамических запоминающих устройств с произвольной выборкой частично уменьшают штрафное время доступа строки благодаря работе в так называемом страничном режиме, в котором могут иметь место последовательные доступы к многочисленным столбцам в одной строке динамического запоминающего устройства с произвольной выборкой без дополнительных доступов строки. В частности, как иллюстрируется на фиг. 6, ряд доступов к одной строке инициируется посредством сообщения адреса строки динамическим запоминающим устройствам с произвольной выборкой и возбуждения сигнала строба адреса столбца (CAS^*). После первого доступа сигнал строба адреса строки (RAS^*) не дезактивируется. Вместо этого, дезактивируется только сигнал строба адреса столбца (CAS^*), сообщается новый адрес столбца и становятся доступными данные из нового столбца или данные для нового столбца сохраняются только после короткого времени доступа столбца. Таким образом, если последовательность доступов имеет место в одной строке, то получают существенную экономию времени.

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

Штрафное время может стать более значительным в микропроцессорных вычислительных системах, которые разрешают запоминать посланные записи. Как было описано выше, в системе, имеющей посланные записи, например, в системе 180, иллюстрируемой на фиг. 7, микропроцессор 113 сообщает данные, данные записи и соответствующие управляющие сигналы к шине 125 системы для инициирования доступа записи в подсистему 120 памяти. Вместо того, чтобы ждать завершения доступа записи, как показано активацией и последующей деактивацией сигнала занятости из подсистемы 120 памяти, микропроцессор 113 продолжает осуществление транзакций шины. Для размещения посланных записей контроллер 182 памяти в подсистеме 180 памяти содержит буфер 184 посланной записи. Буфер 184 посланной записи хранит адрес и данные, подлежащие записи в динамических запоминающих устройствах 135 с произвольной выборкой. В известных системах посланной записи буфер 184 посланной записи может хранить более одной посланной записи и работает как буфер простой очереди. Контроллер 182 памяти передает данные ранее всего посланной записи в динамические запоминающие устройства 135 с произвольной выборкой сообщением адреса на выход буфера 184 посланной записи к динамическим запоминающим устройствам с произвольной выборкой как часть, соответствующую адресу строки, и часть, соответствующую адресу столбца, как описано выше, при том отличии, что адрес и данные обеспечиваются буфером 184 посланной записи, а не прямо из шины 125 системы. Синхронизация хранения информации запроса доступа записи в буфере 184 простой очереди и сообщение адреса и выходных данных из буфера 184 простой очереди в динамические запоминающие устройства 135 с произвольной выборкой обеспечивается синхрогенератором и контроллером 186 простой очереди по шине 187 передачи сигналов управления. Синхрогенератор и контроллер 186 простой очереди управляет мультиплексором 188 адресации строки/столбца аналогично тому, как это было описано выше.

Как правило, когда микропроцессор 113 инициирует доступ считывания в подсистему 120 памяти, микропроцессору 113 необходимо иметь данные ответа прежде, чем он начнет следующую операцию. Таким образом, приводимые в качестве примера, системы памяти посланной записи обеспечивают режим считывания вокруг, в котором контроллер 182 памяти делает запрос доступа считывания на шине 125 системы приоритета перед ожидающими посланными записями. То есть, если запрос считывания ожидается, когда текущий доступ завершается, то доступ считывания осуществляется независимо от того, является ли посланная запись ожидающей, если запрос доступа считывания направлен в ту же ячейку адресации, что и посланная запись.

Поскольку важно, чтобы доступ считывания осуществил выборку большинства текущих данных, известные системы посланной записи делают одну из двух операций, если запрос считывания направлен в тот же адрес, что и посланная запись. Буфер посланной записи очищается для записи данных записи в динамические запоминающие устройства 135 с произвольной выборкой или, в альтернативном варианте, запрос считывания удовлетворяется посредством вывода запрошенных данных из буфера 184 посланной записи аналогичным образом в подсистему сверхоперативной памяти. Режим считывания вокруг поддерживается мультиплексором 190 адресации считывания/записи, который принимает информацию адресации из выхода буфера 184 простой очереди посланной записи во время допусков записи и который принимает информацию адресации непосредственно из шины 125 системы во время доступов считывания. Буфер 192 выходных данных буферизует выходные данные из динамических запоминающих устройств 135 с произвольной выборкой на шине 125 системы.

Обычные системы посланной записи сохраняют штрафное время, если последовательные посланные записи направляются в разные строки динамических запоминающих устройств 135 с произвольной выборкой. В частности, если контроллер 182 памяти обеспечивает допуск буфера посланной записи простой очереди, он должен изменить адрес строки всякий раз, когда две последовательные посланные записи направляются в разные строки в динамических запоминающих устройствах 135 с произвольной выборкой. Кроме того, если доступ считывания идентифицирует другую строку, чем строка текущего доступа, то назначается штрафное время доступа строки. Обычный контроллер памяти частично уменьшает штрафное время благодаря обнаружению, когда последовательные адреса направляются на одну страницу (то есть строку). Как иллюстрируется на фиг. 7, в этом случае имеется фиксатор строки и компаратор 194, который принимает часть, соответствующую адресу строки, выхода мультиплексора 190 адресации считывания/записи. Фиксатор строки и компаратор 194 фиксирует часть, соответствующую адресу строки, предшествующего доступа при наличии активного сигнала строба адреса строки (RAS^*). Зафиксированная часть, соответствующая адресу строки, сравнивается с частью, соответствующей адресу строки, текущего доступа для определения, одинаковы ли эти два адреса строки. Если эти два адреса строки одинаковы, то фиксатор строки и компаратор 194 обеспечивает активный сигнал к синхрогенератору и контроллеру простой очереди, чтобы заставить его сохранить текущую страницу (то есть строку) открытой и изменить только адрес столбца посредством возбуждения сигнала строба адреса столбца (CAS^*) для нового текущего доступа.

На фиг. 8 иллюстрируется подсистема 200 памяти, соответствующая настоящему изобретению. В частности, подсистема 200 памяти содержит контроллер 202 памяти, который включает в себя усовершенствованный буфер 204 посланной записи. Контроллер 202 памяти дополнительно содержит синхрогенератор и контроллер 206 буфера, который будет описан ниже более подробно. Синхрогенератор и контроллер 206 буфера соединен с буфером 204 посланной записи шиной 208 посредством двунаправленной управляющей шины 208.

Мультиплексор 210 адресации считывания/записи, мультиплексор 212 адресации строки/столбца и буфер 214 выходных данных работают аналогично соответствующим элементам, описанным выше. Контроллер 202 памяти, показанный на фиг. 8, дополнительно содержит фиксатор 220 адреса строки, который принимает и фиксирует часть, соответствующую адресу строки, выхода мультиплексора 210 адресации считывания/записи. Фиксатор 220 адреса строки фиксируется при наличии активного сигнала строба адреса строки (RAS^*) так, чтобы часть, соответствующая адресу строки, текущего доступа сохранялась каждый раз, когда адрес строки сообщается динамическим запоминающим устройствам с произвольной выборкой. Зафиксированный выход фиксатора 220 адреса строки обеспечивается как вход в синхрогенератор и контроллер 206 буфера.

Аналогично обычным контроллерам памяти посланной записи, например контроллеру, иллюстрируемому на фиг. 7, синхрогенератор в контроллере 202 памяти посланной записи, показанном на фиг. 8, сохраняет дорожку адреса строки текущего доступа посредством фиксатора 220 адреса строки. В отличие от обычных контроллеров памяти, синхрогенератор и контроллер 206 буфера содержит цепь 230 компараторов и логической схемы управления указателями, которая сравнивает части, соответствующие адресу строки, текущей открытой страницы (то есть строки), хранимой в буфере 204 посланной записи, и определяет имеет ли какой либо из активных запросов посланной записи часть адреса, соответствующую зафиксированному адресу строки текущего доступа в динамические запоминающие устройства 135 с произвольной выборкой. Цепь 230 компараторов и логической схемы управления указателями дополнительно указывает ячейку в буфере 204 (посланной записи), в которой хранится адрес и данные запросов поступающей записи, посредством входного указателя и указывает ячейку, из которой выводится адрес и данные посланной записи, выбранные как следующий доступ в динамические запоминающие устройства 135 с произвольной выборкой посредством выходного указателя.

Синхрогенератор и контроллер 206 буфера дополнительно принимает текущий адрес посредством шины 125 системы и, если уровень сигнала на селекторной линии 152 считывания/записи указывает, что запрос доступа на шине 125 системы является запросом доступа считывания, то цепь 230 компараторов и логической схемы управления указателями в синхрогенераторе и контроллере 206 буфера сравнивает часть, соответствующую адресу строки, запрашиваемого адреса считывания, с зафиксированным адресом строки для определения, одинаковы ли они. Цепь 230 компараторов и логической схемы управления указателями сравнивает также часть, соответствующую адресу строки, запрашиваемого адреса считывания с частями адреса строки посланных записей для определения, согласуются ли эти части, соответствующие адресу строки. Результаты сравнений адреса считывания, адресов посланной записи и зафиксированного адреса строки определяют, какой доступ в динамические запоминающие устройства 135 с произвольной выборкой будет выбран в качестве следующего доступа.

Выборы следующего доступа к динамическому запоминающему устройству с произвольной выборкой иллюстрируется в таблице 300, показанной на фиг. 9, для первого предпочтительного варианта осуществления настоящего изобретения. Каждая линия таблицы 300 имеет три столбца, в которых первый (левый) столбец, называемый "Считывание", является результатом сравнения части, соответствующей адресу строки, запрашиваемого доступа считывания с зафиксированным адресом строки (то есть с частью, соответствующей адресу строки, текущего доступа); второй (средний) столбец, называемый "Запись", является результатом сравнения частей, соответствующих адресу строки, с зафиксированным адресом строки и с частью, соответствующей адресу строки, запрашиваемого доступа считывания; и третий (левый) столбец, называемый "Доступ", идентифицирует запрос, который будет сообщен динамическим запоминающим устройствам 135 (с произвольной выборкой) в качестве следующего доступа.

Как иллюстрируется первой строкой 301 таблицы 300, если запрашиваемый доступ считывания не согласуется с текущим доступом и буфер посланной записи пуст, то доступ считывания будет сообщен динамическим запоминающим устройствам 135 (с произвольной выборкой) в качестве следующего доступа, требующего сигнала строба адреса строки (RAS^*), деактивируемого синхрогенератором и контроллером 206 буфера, и после заданной задержки для разрешения перезарядить адреса строки, посылающим часть, соответствующую адресу строки, запроса доступа считывания к динамическим запоминающим устройствам с произвольной выборкой, возбуждающим сигнал строба адреса строки (RAS^*) и продолжающим доступ, как описано выше. Для этого доступа не обеспечивается особой выгоды в скорости.

Как иллюстрируется во второй строке 302, третьей строке 303 и четвертой строке 304, если запрашиваемый доступ считывания не согласуется с текущим доступом, а буфер 204 посланной записи не пуст, то доступ, выбранный как следующий доступ, зависит от содержимого строки посланных записей в буфере 204 посланной записи. В частности, как иллюстрируется в четвертой строке 304, если одна или более посланных записей имеют части, соответствующие адресу строки, соответствующие текущему зафиксированному адресу строки, то ранее всего посланная запись, имеющая соответствующую часть, соответствующую адресу строки, может быть выбрана в качестве следующего доступа с преимуществом не изменять адрес строки, а только стробирования в новом адресе столбца для осуществления доступа. В особенно предпочтительных вариантах осуществления настоящего изобретения, синхрогенератор и контроллер 206 буфера, обеспечивает два режима работы, которые поддаются выбору посредством разряда программируемого режима в регистре конфигурации (не показан). В первом режиме, описываемом в этой заявке, посланные записи, имеющие одинаковую часть, соответствующую адресу строки, в качестве текущего зафиксированного адреса строки, имеют приоритет перед считываниями, которые имеют другую (отличающуюся) часть, соответствующую адресу строки. Во втором режиме, доступам - считывания всегда дается приоритет перед посланными записями. В зависимости от смешения адресов, различные случаи применения установят разряд режима для выбора либо первого, либо второго режима, в соответствии с которым режим обеспечивает оптимальное общее время выполнения операции для конкретного случая применения. Эмпирические исследования времени выполнения могут быть выполнены для различных случаев применения с целью определения, какой режим предпочтителен для конкретного применения.

Если посланная запись имеет часть, соответствующую адресу строки, не согласующуюся с текущим зафиксированным адресом строки, то часть, соответствующая адресу строки, запрашиваемого доступа считывания сравнивается с частью, соответствующей адресу строки, всех посланных записей. Если часть, соответствующая адресу строки, запрашиваемого доступа считывания отличается от частей, соответствующих адресу строки, всех посланных записей, как показано входом "Новая (ОТЛ.)" во второй строке 302 таблицы 300, то доступ считывания выбирается как следующий доступ. С другой стороны, если часть, соответствующая адресу строки, запрашиваемого доступа считывания согласуется с частью, соответствующей адресу строки, одной или более посланных записей, то самая ранняя посланная запись сообщается как следующий доступ. Такое решение делается для того, чтобы гарантировать, что доступ считывания к ячейке недавно записанных данных, который может быть еще послан в буфер 204 посланной записи, принимает правильные данные. Как описано выше, синхрогенератор и контроллер 206 буфера может содержать логическую схему (не показана), которая подает данные, посланные в буфер 204 посланной записи как выходные данные, если запрос считывания направлен в ячейку, имеющую посланную запись, хранящуюся в настоящее время в буфере 204 посланной записи.

Как иллюстрируется в пятой строке 305 и в шестой строке 306 таблицы 300, если часть, соответствующая адресу строки, запроса доступа считывания согласуется с зафиксированной частью, соответствующей адресу строки, то доступ считывания будет осуществлен как следующий доступ, если буфер 204 посланной записи пуст (строка 305) или буфер 204 посланной записи содержит только посланные записи в ячейки, имеющие части, соответствующие адресу строки, отличающиеся от текущей зафиксированной части, соответствующей адресу строки. Таким образом, получают преимущество в скорости, благодаря тому, что между доступами не приходится изменять адрес строки.

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

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

Из предшествующего описания следует, что вариант осуществления, представленный с помощью таблицы 300, имеет остаточное время ожидания считывания, если часть, соответствующая адресу строки, запрашиваемого доступа считывания и часть, соответствующая адресу строки, одной или более посланных записей согласуются. Однако, хотя доступ считывания может быть к той же строке динамического запоминающего устройства с произвольной выборкой, имеется значительная вероятность того, что доступ считывания может быть к другому столбцу в строке. В таком случае, отсутствует необходимость хранить данные посланной записи в одном столбце до считывания данных из другого столбца. Таким образом, если сравнение между адресом доступа считывания и адресами посланной записи расширено до части, соответствующей адресу столбца, то ряд конфликтов можно избежать так, чтобы доступ считывания мог быть завершен до посланных записей. Например, путем сравнения одного разряда части, соответствующей адресу столбца, запрашиваемого доступа считывания и посланных записей, вероятность конфликта в одной строке может быть уменьшена на 50%. Каждый дополнительный сравниваемый разряд дополнительно уменьшает вероятность конфликта; однако для каждого дополнительного разряда для каждой из посланных записей должен быть обеспечен компаратор. Между дополнительной логической схемой, требуемой для сравнений и вероятного уменьшения времени ожидания считывания, обеспечиваемого каждым дополнительным разрядом, может быть сделан компромисс.

В таблице 310, показанной на фиг. 10 иллюстрируются альтернативные выборы для следующего доступа в динамическое запоминающее устройство с произвольной выборкой, когда сравнение запроса считывания с посланными записями расширяется в часть, соответствующую адресу столбца, как только что было описано выше. Таблица 310 аналогична таблице 300, причем строка 311 таблицы 310 соответствует строке 301 таблицы 300 и так далее; однако работа этого альтернативного варианта осуществления в соответствии со строкой 312, строкой 313 и строкой 317 отличается, кроме того прибавлена новая строка 318.

Во втором столбце строки 312 и строки 313, входы "Новая (ОТЛ.)" и "Новая (ТАКАЯ ЖЕ)" теперь относятся к расширенному сравнению, в котором часть, соответствующая адресу строки, запрашиваемого доступа считывания и часть, соответствующая адресу строки, каждой посланной записи сравниваются так же, как и прежде; однако также сравниваются выбранный разряд или разряды частей, соответствующих адресу столбца, запрашиваемого доступа считывания и посланных записей. Таким образом, посланная запись в адрес новой строки будет выбрана по запрошенному доступу считывания в адрес новой строки только в том случае, если адрес строки и выбранный разряд или разряды частей, соответствующих адресу столбца, одинаковы. Иначе, запрошенный доступ считывания будет выбран как следующий доступ.

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

В таблицах 300 и 310 иллюстрируются выборы между доступами считывания и доступами записи. В таблице 320, показанной на фиг. 11, иллюстрируется дополнительная подробность выборов между доступами посланной записи в соответствии с тем, направлена ли какая-либо из посланных записей в ту же строку в качестве текущего доступа. Таблица 320 имеет четыре строки 321, 322, 323 и 324. Первый столбец каждой из строк 321-324 указывает, содержит ли буфер посланной записи по меньшей мере один доступ посланной записи, направленный в ту же строку, что и часть, соответствующая адресу строки, текущего доступа (например, совпадение страницы). Второй столбец в каждой из строк 321-324 указывает, содержит ли буфер 204 посланной записи по меньшей мере один доступ посланной записи, направленный в строку, отличающуюся от части, соответствующей адресу строки текущего доступа (например, пропуск страницы). Третий столбец указывает, который доступ записи выбран из буфера 204 посланной записи в качестве следующего доступа записи.

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

Выполнение вариантов осуществления, показанных на фиг. 8-11, требуют необычного буфера 204 посланной записи, поскольку посланные записи не обязательно выходят из буфера в том же порядке в котором они записаны в буфер. Таким образом, не может быть использован буфер простой очереди. Необходимо следить за ячейками активных посланных записей, если посланные записи могут быть извлечены не в порядке простой очереди и сравнение частей, соответствующих адресу строки, и выбранных разрядов частей, соответствующих адресу столбца, выполняется посредством цепи 230 компараторов и логической схемы управления указателями в синхрогенераторе и контроллере 206 буфера. Более подробно цепь 230 компараторов и логической схемы управления указателями поясняется на фиг. 12-16.

На фиг. 12 иллюстрируется общая блок-схема цепи 230 компараторов и логической схемы управления указателями, а также показана дополнительная деталь буфера 204 посланной записи. Буфер 204 посланной записи содержит буферную матрицу 400, которая имеет множество буферных ячеек, которое в предпочтительном варианте осуществления содержит четыре ячейки 401-404. Каждая из буферных ячеек 401-404 обеспечивает хранение множества разрядов данных (например, 32 разряда), множество разрядов адресации (например, адреса AD2-AD21) и разряд готовности. Буфер 204 посланной записи предпочтительно является буфером с двумя портами, который обеспечивает возможности независимой адресации для записей данных и считываний данных. Кроме того, данные внутри буфера 204 посланной записи обеспечиваются как выходные данные непосредственно для цепи 230 компараторов и логической схемы управления указателями, как описывается ниже. Например, буфер 204 посланной записи, иллюстрируемый на фиг. 12, содержит схему 410 выбора считывания, чувствительную к выходному указателю из цепи 230 компараторов и логической схемы управления указателями для выбора данных в одной из буферных ячеек 401-404 в качестве выходных данных из буфера 204 посланной записи. Схема 410 выбора считывания предпочтительно является, например, декодером. В альтернативном варианте, выходной указатель может быть использован для адресации выходного мильтиплексора (не показано).

Буфер 204 посланной записи содержит также схему 412 выбора записи, которая формирует сигнал записи для выбора одной из буферных ячеек 401-404 в ответ на сигнал входного указателя и записи буфера из цепи 230 компараторов и логической схемы управления указателями. Если возбуждается сигнал записи буфера, то схема 412 выбора записи декодирует точку входа и записывает данные и адрес и сигнал готовности на входе к буферной матрице 400 к декодируемым буферным ячейкам 401-404.

Как иллюстрируется на фиг. 12, адресная часть каждой из буферных ячеек 401-404 дополнительно делится на часть, соответствующую адресу строки (например, ROW0, ROW1, ROW2, ROW3, соответственно), и на часть, соответствующую адресу столбца (например, COL0, COL1, COL2, COL3, соответственно). Соответствующие разряды готовности аналогичным образом идентифицируются аналогичным образом (например, RDY0, RDY1, RDY2, RDY3, соответственно).

Цепь 230 компараторов и логической схемы управления указателями содержит логическую схему 420 управления указателями и множество компараторов 430-438. Компараторы 430-433 являются компараторами считывания, которые сравнивают часть, соответствующую адресу строки, и выбранные разряды части, соответствующей адресу столбца, запроса считывания на шине 125 системы с адресными частями и выбранными разрядами части, соответствующей адресу столбца, каждой из посланных записей в буферной матрице 400. Например, компаратор 430 сравнивает часть, соответствующую адресу строки и выбранную часть, соответствующую адресу столбца, запроса считывания с ROW0 и выбранными разрядами COL0 из буферной ячейки 401. Выходом компаратора 430 является сигнал согласования (МАТСН0), который указывает на то, что запрос считывания направлен в адрес той же строки и возможно в адрес того же столбца, что и у посланной записи, хранимой в буферной ячейке 401. (Если компаратор 430 расширен так, чтобы охватывать все разряды столбца, то компаратор 430 может определять точное согласование. ) Аналогичным образом, компараторы 431, 432 и 433 обеспечивают соответствующие выходы MATCH1, МАТСН2 и МАТСН3, указывающие на согласования между посланными записями в ячейках 402, 403 и 404, соответственно.

Компаратор 434 принимает часть, соответствующую адресу строки, запроса текущей строки и зафиксированный адрес строки из фиксатора 220 адреса строки (фиг. 8). Компаратор 434 формирует выходной активный сигнал READ HIT, если две части, соответствующие адресу строки, идентичны, для указания на то, что запрос доступа считывания направлен в открытую в настоящее время страницу памяти (то есть в доступную в настоящее время строку динамических запоминающих устройств 135 с произвольной выборкой).

Компаратор 435 принимает часть, соответствующую адресу строки, (ROW0) из буферной ячейки 401 и зафиксированную часть, соответствующую адресу строки, из фиксатора адреса строки 220. Компаратор 435 формирует активный выходной сигнал HIT0, если эти две части, соответствующие адресу строки, одинаковы. Аналогичным образом, компараторы 436-438 формируют соответствующие выходные сигналы HIT1, HIT2 и HIT3 в ответ на сравнение сигналов зафиксированного адреса строки и сигналов ROW1, ROW2 и ROW3, соответственно. В альтернативных вариантах осуществления настоящего изобретения, компараторы MATCH и HIT могут быть мультиплексированы по времени для уменьшения общего количества требуемого аппаратного обеспечения.

Сигналы МАТСН0, МАТСН1, МАТСН2, МАТСН3, READ HIT, HIT0, HIT1, HIT2 и HIT3 формируются как входные сигналы в логическую схему 420 управления указателями вместе с сигналами RDY0, RDY1, RDY2 и RDY3. Сигналы готовности комбинируются с сигналами согласования и сигналами совпадения так, чтобы логическая схема 420 управления указателями была чувствительна только к совпадениям и согласованиям с посланными записями, которые еще не записаны в динамических запоминающих устройствах 135 с произвольной выборкой. Таким образом, после того, как данные, связанные с посланной записью, занесены в буфер, для отмены соответствующих сигналов совпадения и согласования необходимо блокировать только соответствующий сигнал готовности.

Логическая схема управления указателями формирует на линии 450 селекторный выходной сигнал считывания для управления мультиплексором 210 адресации считывания/записи. Выходной селекторный сигнал считывания возбуждается, если имеет место совпадение считывания, а доступ считывания выбирается в соответствии с таблицей 310, показанной на фиг. 10, как описано выше. Подробные логические диаграммы или логические уравнения для формирования селекторного выходного сигнала считывания в соответствии с таблицей 310 не будут описаны в этой заявке, поскольку формирование таких логических диаграмм или логических уравнений хорошо известно квалифицированным в этой области техники специалистам.

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

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

Указатели в структуре очереди и соответствующие разряды готовности ввода для каждой позиции определяют состояние очереди. Указатель указывает конкретную позицию, если указатель удерживает соответствующий номер позиции, показываемый слева от каждой позиции на фиг. 13. Как показано на фиг. 13, позиции 1 и 2 ввода показаны как позиции, имеющие очередность вводов (то есть посланные записи, которые не были переданы в динамические запоминающие устройства 135 с произвольной выборкой), а позиции 0 и 3 показаны как пустые (то есть посланные записи, находившиеся ранее в этих позициях и уже переданные в динамические запоминающие устройства с произвольной выборкой). Таким образом, установлены разряды готовности ввода (то есть значение 1) для позиций 1 и 2 и 0 для позиций 0 и 3.

Входной указатель указывает на следующее доступное пустое поле в очереди. Указатель ввода действует, если соответствующий разряд готовности ввода не установлен (то есть 0). Иначе, если разряд готовности ввода установлен (то есть 1), то указатель ввода не действует, поскольку позиция уже занята.

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

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

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

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

Если буфер 204 обрабатывает вводы в том порядке, в котором они приняты, буфер функционирует как обычный буфер простой очереди, причем основной указатель ввода и выходной указатель всегда указывают одну ячейку. Другими словами, следующая посланная запись для передачи в динамические запоминающие устройства 135 с произвольной выборкой будет самым старым вводом, указываемым основным указателем ввода. Новый ввод может быть поставлен в очередь, если входной указатель указывает на ячейку, которая имеет разряд неактивной готовности ввода. Если входной указатель прогрессировал так, что указывает на ту же позицию, что и основной указатель ввода, то не может быть принято дополнительных вводов. Каждый раз, когда новый ввод хранится в буфере, устанавливается разряд готовности ввода позиции, где хранится ввод, и входной указатель перемещается к следующему более высокому числу позиции хранения. Указатели считают modulo-4 так, что, если указатель приращивается от величины 3 (то есть двоичного 11), то следующая величина будет 0 (то есть двоичное 00). Другими словами, указатель охватывает числа от 3 до 0.

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

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

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

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

Основной указатель ввода изменится только тогда, если выходной указатель указывает на ту же позицию, что и основной указатель ввода, а ввод в этой позиции удаляется посредством передачи данных динамическим запоминающим устройствам 135 с произвольной выборкой. Если ввод в следующей позиции очереди уже был удален, то логической схеме требуется выполнить переход над этой "дырой". В частности, как иллюстрируется на фиг. 14, матрица готовности ввода (RDY3, RDY2, RDY1, RDY0 из буферной матрицы 400) подается на входы четырехразрядного сдвигового регистра 500, который управляется двухразрядной величиной (В1, В0) текущего основного указателя 502 ввода. Входы в сдвиговый регистр сдвигаются вправо по кругу (то есть поворачиваются вправо) на величину, которая равна величине текущего основного указателя ввода. Например, если текущий основной указатель ввода имеет значение 2, то матрица готовности ввода сдвинется в правые два разряда, причем два наименьших значительных разрядов входов в сдвиговый регистр 500 становятся двумя самыми значительными разрядами выхода сдвигового регистра 500. Кодер 504 приоритета выбирает число разряда первого активного разряда готовности ввода, найденного в поворотном выходе. Это число разряда затем прибавляется к текущему основному указателю ввода в сумматоре modulo-4 для получения следующего основного указателя 508 ввода. Следующий основной указатель становится текущим основным указателем, если следующие данные списываются в динамические запоминающие устройства 135 с произвольной выборкой посредством сигнала записи, синхронизирующим текущий основной указатель ввода.

Сказанное выше может стать понятным при рассмотрении следующего примера, в котором текущий основной указатель ввода равен 1, а матрица готовности ввода равна 1011 (то есть RDY3=1, RDY2=0, RDY1=1, RDY0=1). Такие вводы существуют в позициях 3, 1 и 0, а дыра существует в позиции 2. Удаление ввода в позиции 1 изменяет матрицу готовности ввода до 1001. При повороте вправо на один разряд (величину текущего основного указателя ввода), выход сдвигового регистра 500 составляет 1100. Первым активным вводом справа является разряд 2. Прибавление 2 к 1 (modulo-4) дает "в результат величину 3 для нового основного указателя ввода, выполняя, таким образом, переход над дырой.

Как иллюстрируется на фиг. 15, одна или более функций распределения приоритета могут быть использованы для отбора матрицы готовности ввода для следующей задачи. Выходной указатель образуется с помощью матрицы готовности ввода и логических элементов И, причем маска отбора приоритета, в настоящем изобретении, содержит разряды совпадения (HIT3, HIT2, HIT1, НIТ0 из компараторов 435-438, показанных на фиг. 12) в множестве логических элементов 521-524 И, как показано на фиг. 15. Маскированные выходы логических элементов 521-524 И обеспечены как соответствующие первые входы в соответствующие мультиплексоры 525-528 два к одному. Соответствующие вторые входы в мультиплексоры 525-528 два к одному соединены для приема разрядов готовности (RDY3, RDY2, RDY1, RDY0), соответственно. Маскированные выходы логических элементов 521-524 И также обеспечены как входы в логический элемент 529 ИЛИ, имеющий четыре входа, который обеспечивает активный выходной сигнал ENTRY_ RDY & PAGE_HIT всякий раз, когда один или более маскированных выходов логических элементов 521-524 И являются активными. Другими словами, логический элемент 529 ИЛИ обеспечит активный выход ENTRY_RDY & PAGE_HIT всякий раз, когда по меньшей мере один из активных входов посланной записи направляется к строке текущего доступа, как показано его разрядом готовности и его соответствующим разрядом совпадения, которые оба активны. Выход ENTRY_RDY & PAGE_HIT логического элемента 529 ИЛИ обеспечен как селекторный вход в каждый из мультиплексоров 525-528 два к одному. Если селекторный вход активен, то маскированные выходы логических элементов 521-524 И выбираются как выходы мультиплексоров. Таким образом, только мультиплексоры, соответствующие вводам, имеющим активный разряд ввода и активный разряд совпадения, будут иметь активный выход. По этой причине, формирование выходного указателя, описываемого ниже, будет основано только на вводах, имеющих совпадения страницы (то есть строки) и будет выбран самый старый ввод с совпадением страницы. С другой стороны, если ни один из активных вводов не имеет активного разряда совпадения, то выход логического элемента 529 ИЛИ будет неактивным, чтобы заставить мультиплексоры 525-528 два к одному выбирать немаскированные разряды готовности. Таким образом, выходной указатель будет формироваться на основе всех активных вводов и будет выбран старейший активный ввод.

Выходы мультиплексоров 525-528 два к одному предусмотрены как входы в сдвиговый регистр 530. Сдвиговый регистр 530 работает аналогично сдвиговому регистру 500, показанному на фиг. 14, в ответ на текущий основной указатель ввода. Выходы из сдвигового регистра 530 предусмотрены как входы в кодер 532 приоритета, который выбирает число разряда первого разряда готовности ввода справа поворотного выхода. Это число разряда прибавляется к основному указателю ввода в сумматоре 534 modulo-4 для формирования нового выходного указателя (иллюстрируемого как блок 536).

Вышесказанное может быть пояснено на следующем примере, в котором основным указателем ввода является 3, матрица готовности ввода - 1101, а маска отбора приоритета (то есть разрядов совпадения) - 0111, указывая на то, что только части, соответствующие адресу строки, в позициях 2, 1 и 0 согласуются с фиксированной частью, соответствующей адресу строки и, таким образом, имеют более высокий приоритет, чем ввод в позиции 3, который не согласуется с текущей частью, соответствующей адресу строки. Подача разрядов готовности ввода и разрядов совпадения в логический элемент И (то есть 1101 И 0111) приводит к формированию входа 0101 в сдвиговый регистр. Поворот входа сдвигового регистра на 3 приводит к получению выхода сдвигового регистра 1010. Число разряда первого активного разряда справа - 1. Прибавление этого разряда к основному указателю (modulo-4) ввода приводит к получению величины равной 0 (1+3) = (modulo-4)=0. Таким образом, для этого примера новым выходным указателем является 0 для указания на ячейку "самой старой" посланной записи, имеющей такую же часть, соответствующую адресу строки, что и текущий зафиксированный адрес строки, обеспечивая в соответствии с этим переход над более старой посланной записью, которая не имеет такой же части, соответствующей адресу строки, как текущий зафиксированный адрес строки.

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

Как иллюстрируется на фиг. 16, следующий входной указатель формируется правым поворотом матрицы готовности ввода на величину основного указателя ввода в сдвиговом регистре 550. Сдвинутые вправо выходы подаются как входы в кодер 552 приоритета, который, в этом конкретном случае, выбирает самый левый (то есть самый приоритетный) активный разряд и формирует значение выхода, представляющее позицию выбранного разряда. Выход кодера 552 приоритета прибавляется к значению 1 в сумматоре 554 modulo-4 и полученная сумма прибавляется к значению текущего основного указателя ввода в сумматоре 556 modulo-4. Выход сумматора 556 modulo-4 является новым входным указателем, как иллюстрируется блоком 558.

Вышесказанное может быть пояснено на следующем примере, в котором основной указатель ввода - 1, а матрица готовности ввода - 1010. Правый поворот матрицы готовности ввода на 1 формирует выход 0101 из сдвигового регистра 550. Кодер 552 приоритета формирует выход 2 для представления самого левого активного разряда в позиции 2. Прибавление величины 2 к величине 1 дает сумму 3, которая, если прибавляется к величине основного указателя ввода (то есть 1 в этом примере), дает сумму 4 (modulo-4), которая формирует окончательное значение 0. Таким образом, следующий входной ввод будет помещен в позицию 0, обеспечивая переход над дырой в позиции 2.

Логика управления очередью, описанная со ссылкой на фиг. 14-16, предпочтительно реализуется в виде интегральной схемы частного применения для образования структуры логической схемы 420 управления указателями, показанной на фиг. 12.

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

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