Контроллер памяти и способ работы такого контроллера памяти

Контроллер памяти и способ работы такого контроллера памяти

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

УРОВЕНЬ ТЕХНИКИ, К КОТОРОМУ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

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

Необходимость активирования строк перед доступом к ним вызывает не только ухудшение производительности, как изложено выше, но и дополнительно вызывает излишнее потребление энергии вследствие потребления энергии при выполнении процедуры активации строки. Соответственно, считается желательным переупорядочение транзакций, выданных в такое запоминающее устройство, в качестве попытки сокращения времени доступа, и в особенности, обеспечения везде, где это возможно, множественных операций доступа к конкретной строке, когда была активирована эта строка. В статье С. Рикснера и др. (“Memory Access Scheduling” by S. Rixner et al., Computer Systems Laboratory, Stanford University, California, USA, appearing in Proceedings of the 27^th International Symposium on Computer Architecture 2000, 14 June 2000, pages 128-138), рассмотрены варианты архитектуры динамического ОЗУ и несколько способов установления очередности доступа к памяти, которые могут использоваться в попытке переупорядочения операций запоминающего устройства для использования неравномерных времен доступа к динамическому ОЗУ.

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

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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