КОНТРОЛЛЕР ПАМЯТИ И СПОСОБ РАБОТЫ ТАКОГО КОНТРОЛЛЕРА ПАМЯТИ Российский патент 2016 года по МПК G06F13/16 G11C29/18 

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

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

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

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

Одной из разновидностей запоминающего устройства, обладающего вышеупомянутым свойством, является запоминающее устройство, содержащее множество банков, где каждый банк содержит множество строк, а каждую строку необходимо активировать перед доступом к этой строке. Примером такого запоминающего устройства является динамическое оперативное запоминающее устройство 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).

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

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

на фиг.2 изображена блок-схема динамического запоминающего устройства (динамического ОЗУ) из фиг.1 согласно одному варианту осуществления изобретения;

на фиг.3 изображена блок-схема контроллера памяти динамического ОЗУ из фиг.1 согласно одному варианту осуществления изобретения;

на фиг.4A схематично проиллюстрирован элемент перечня, упорядоченного на основе приоритета, согласно одному варианту осуществления изобретения;

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

на фиг.5A схематично проиллюстрирован элемент перечня, упорядоченного по времени доступа, согласно одному варианту осуществления изобретения;

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

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

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

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

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

на фиг.10A схематично проиллюстрировано функционирование схемы ограничителя согласно одному варианту осуществления изобретения;

на фиг.10B и фиг.10C схематично проиллюстрировано функционирование схемы ограничителя согласно альтернативному варианту осуществления изобретения;

на фиг.11A и фиг.11B проиллюстрированы этапы, выполняемые при извлечении элемента, соответственно, из перечня, упорядоченного на основе приоритета, и из перечня, упорядоченного по времени доступа, согласно одному варианту осуществления изобретения;

на фиг.12 схематично проиллюстрировано то, как извлекают элемент из перечня, упорядоченного на основе приоритета, согласно способу из фиг.11A;

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

на фиг.14 схематично проиллюстрировано то, как этапы 730 и 735 эскалации считывания из фиг.13 влияют на элементы перечня, упорядоченного на основе приоритета, согласно одному варианту осуществления изобретения;

на фиг.15 схематично проиллюстрировано то, как этапы 740 и 745 из фиг.13 могут вызывать генерацию перечня-ответвления из перечня, упорядоченного по времени доступа, согласно одному варианту осуществления изобретения; и

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

ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

На фиг.1 изображена блок-схема системы обработки данных, включающей в себя множество ведущих устройств 10, 20, соединенных посредством схемы 30 межсоединений с несколькими ведомыми устройствами 55, 60. Одним из ведомых устройств является динамическое запоминающее устройство DRAM 55 то есть, соединенное со схемой 30 межсоединений через контроллер 50 памяти динамического ОЗУ.

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

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

В схеме 40 управления схемой 30 межсоединений может быть предусмотрено наличие схемы добавления/удаления идентификатора для обеспечения возможности однозначной идентификации транзакций из различных ведущих устройств в схеме 30 межсоединений. Например, такая схема добавления и удаления идентификатора могут быть устроена так, что для каждого идентификатора транзакции, выданного соответствующим ведущим устройством, она расширяет этот идентификатор транзакции номером ведущего устройства, что позволяет направлять ответы обратно в это ведущее устройство. Аналогичным образом, когда передачи направляют обратно в ведущее устройство, схема добавления/удаления идентификатора удаляет номер ведущего устройства перед возвратом ответной передачи в соответствующее ведущее устройство 10, 20. В дополнение к обеспечению возможности направления ответов обратно в надлежащее ведущее устройство, расширение идентификатора транзакции номером ведущего устройства для создания идентификатора транзакции нового типа в схеме 30 межсоединений также имеет следствие, заключающееся в том, что в этом случае любое ведомое устройство 50, 55, 60, способное переупорядочивать транзакции, имеющие различные идентификаторы транзакции, также способно переупорядочивать транзакции из различных ведущих устройств даже, если они изначально имели один и тот же идентификатор транзакции.

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

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

Другим свойством транзакций является то, что они могут включать в себя указатель приоритета, либо в виде явного поля транзакции, либо полученный на основании некоторого логического вывода, который может быть определен из транзакции (например, понятно, что транзакции, выданные первым ведущим устройством 10, имеют более высокий приоритет, чем транзакции, выданные вторым ведущим устройством 20). В одном описанном здесь конкретном варианте осуществления изобретения каждая транзакция включает в себя явный указатель приоритета в виде указателя качества обслуживания (QoS). Согласно описанным здесь способам, контроллер 50 памяти динамического ОЗУ предпринимает попытку переупорядочения транзакций для сокращения времен доступа к динамическому ОЗУ 55, но, при этом, также учитывает указатели уровня качества обслуживания (QoS) транзакций для гарантии того, что обслуживание транзакций производится надлежащим образом с учетом их указателя качества обслуживания (QoS).

На фиг.2 схематично проиллюстрировано динамическое ОЗУ 55 из фиг.1 согласно одному варианту осуществления изобретения. Динамическое ОЗУ 55 состоит из множества банков 130, 135, 140, причем каждый банк состоит из множества строк. Предусмотрено наличие схем 100, 110, 120 доступа, соответствующих каждому банку, которые реагируют на команды доступа, выданными контроллером 50 памяти динамического ОЗУ. Каждая схема 100, 110, 120 доступа включает в себя буфер 105, 115, 125 строк для хранения по меньшей мере одной строки данных из соответствующего банка. Для доступа к значению данных в строке эта строка сначала должна быть перемещена в соответствующий буфер строк посредством команды RAS, выданной из контроллера памяти, причем на такую команду RAS здесь также ссылаются как на команду активации. Затем, после того, как строка была сохранена в буфере строк, доступ к адресам отдельных памяти в этой строке может быть осуществлен посредством команды CAS, выданной из контроллера памяти. В конце концов, когда операции доступа к строке были завершены, или когда нужно осуществить доступ к новой строке, из контроллера памяти выдают команду предварительной зарядки, вызывающую сохранение текущего содержимого строки в буфере строк быть обратно в соответствующий банк в динамическом ОЗУ 55.

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

На фиг.3 схематично проиллюстрирован контроллер 50 памяти динамического ОЗУ из фиг.1 согласно одному варианту осуществления изобретения. Входные транзакции, принятые из схемы 30 межсоединений, подают во входной интерфейс 200, который может включать в себя какую-либо локальную схему 210 управления переупорядочением. Эта схема 210 управления переупорядочением может, например, изменять идентификаторы транзакций для входных транзакций для того, чтобы фактически разъединять множество транзакций, имеющих один и тот же идентификатор транзакции для обеспечения возможности обработки этих транзакций не по порядку динамическим запоминающим устройством DRAM. Однако, необходимо переупорядочение этих транзакций до вывода какого-либо ответа обратно в схему 30 межсоединений, поскольку в этом варианте осуществления изобретения предполагают, что схема 30 межсоединений требует, чтобы ответы из динамического ОЗУ для транзакций, имеющих один и тот же идентификатор транзакции, возвращались по порядку. Соответственно, может быть предусмотрено наличие буфера 215 данных в схеме 210 управления переупорядочения для обеспечения возможности локального переупорядочения до вывода данных ответа в схему 30 межсоединений.

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

Как показано на фиг.3, интерфейс 200 может необязательно включать в себя схему 205 форматирования пакетов. В частности, одно из ведущих устройств 10, 20 может выдать пакетную транзакцию, имеющую длину пакета, превышающую длину пакета, разрешенную для доступа к запоминающему устройству DRAM. Соответственно, такая пакетная транзакция, принятая интерфейсом 200, может быть преобразована схемой 205 форматирования пакета во множество связанных пакетных транзакций, причем контроллер памяти обрабатывает каждую связанную пакетную транзакцию как отдельную транзакцию. Схема 210 управления переупорядочением может обеспечивать внутренний идентификатор транзакции для каждой связанной пакетной транзакции.

Контроллер 50 памяти динамического ОЗУ включает в себя буфер 230 ожидающих транзакций для временного хранения в качестве ожидающих транзакций тех транзакций, принятых интерфейсом 200, которые еще не были выданы контроллером 50 памяти в динамическое ОЗУ 55. В дополнение к хранению соответствующих подробностей каждой транзакции буфер 230 ожидающих транзакций обеспечивает хранение набора перекрывающихся упорядоченных перечней 235, причем эти перечни включают в себя перечень, упорядоченный на основе приоритета, для каждого банка, для которого существует по меньшей мере одна ожидающая транзакция, (такие перечни, упорядоченные на основе приоритета, именуют здесь перечнями QoS) и перечень, упорядоченный по времени доступа, для каждой строки каждого банка, для которой имеется по меньшей мере одна ожидающая транзакция (такие перечни именуют здесь перечнями попаданий в строку). При приеме каждой транзакции интерфейсом 200 ее подают в схему 220 распределения по перечням, которая устроена так, что распределяет эту ожидающую транзакцию, в качестве элемента по меньшей мере одного из упорядоченных перечней 235. В частности, в одном варианте осуществления изобретения схема 220 распределения по перечням распределяет каждую ожидающую транзакцию, в качестве элемента обоих перечней: соответствующего перечня QoS и соответствующего перечня попаданий в строку. Более подробное описание перечней и функционирования схемы 220 распределения по перечням приведено ниже со ссылкой на остальные чертежи.

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

Когда необходимо выдать новую транзакцию в динамическое запоминающее устройство DRAM 55, например, вследствие того, что контроллером 50 памяти определено, что динамическое запоминающее устройство DRAM 55 способно обработать новую транзакцию, схема 240 арбитража устроена так, что выполняет операцию арбитража, во время которой обращаются к множеству упорядоченных перечней 235 для выбора из ожидающих транзакций победившей транзакции, подлежащей выводу в динамическое ОЗУ 55. Более подробное описание функционирования схемы арбитража приведено ниже, но в общих чертах операция арбитража, выполняемая схемой арбитража, обычно смещается к продолжению выбора элементов из одного из перечней попаданий в строку, когда последняя победившая транзакция была выбрана из этого перечня попаданий в строку. Однако, некоторые условия вызывают отклонение схемы арбитража от этого естественного обычного смещения для гарантии того, что будут учтены уровни качества обслуживания (QoS), соответствующие отдельным транзакциям.

Подробности каждой победившей транзакции, выбранной схемой 240 арбитража, выводят в интерфейс 250 запоминающего устройства, который включает в себя локальный буфер 255 для хранения транзакций и планировщик 260 динамического ОЗУ для создания последовательности команд для динамического ОЗУ для реализации каждой транзакции. Буфер 255 обычно необходим потому, что он может являться необходимым для выдачи множества команд из планировщика динамического ОЗУ для осуществления доступа, требуемого каждой транзакцией, и, кроме того, интерфейсный тракт между планировщиком 260 динамического ОЗУ и динамическим ОЗУ 55 может быть таким, что за каждый период тактовых импульсов может быть выдана только одна команда. Следовательно, может иметься множество транзакций, находящихся в процессе исполнения интерфейсом 250 запоминающего устройства, например, транзакции, направленные в различные банки динамического ОЗУ, и различные команды, необходимые для выполнения этих транзакций, планируются планировщиком 260 динамического ОЗУ с учетом доступности необходимых схем 100, 110, 120 доступа.

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

Несмотря на то, что в одном варианте осуществления изобретения все компоненты, показанные на фиг.3 могут быть созданы вне схемы 30 межсоединений (как схематично показано на фиг.1), понятно, что в некоторых вариантах осуществления изобретения один или более компонентов контроллера 50 памяти динамического ОЗУ могут быть созданы внутри схемы 30 межсоединений как часть блока интерфейса схемы 30 межсоединений. Например, в одном варианте осуществления изобретения все компоненты, кроме интерфейса 250 запоминающего устройства, могут быть созданы в схеме 30 межсоединений, при этом только интерфейс 250 запоминающего устройства создан вне интерфейса между схемой 30 межсоединений и динамическим ОЗУ 55. Однако, вне зависимости от точного физического расположения компонентов, проиллюстрированных на фиг.3, в системе обработки данных, эти компоненты в совокупности именуют здесь “контроллером памяти” динамического ОЗУ 55.

Как упомянуто выше, одним типом перечня, хранящегося в буфере 230 ожидающих транзакций является перечень QoS, причем каждый перечень QoS состоит из нескольких элементов перечня QoS. Каждый элемент перечня QoS имеет вид, схематично проиллюстрированный объектом 300 из фиг.4A. Термины, используемые на фиг.4A, означают следующее:

Ptr: указатель на следующий элемент в перечне, упорядоченном по QoS, для заранее заданного банка

Банк: целевой банк для транзакции, хранящейся в этом элементе

QoS: показатель QoS для транзакции, хранящейся в этом элементе

pQoS: показатель QoS для транзакции, хранящейся в элементе, на который указывает Ptr (“следующий элемент”)

V: элемент является действующим (то есть, содержит транзакцию, которая еще не была обработана)

L: устанавливают для указания того, что элемент содержит последнюю (хвостовую) транзакцию для заданного перечня для банка

F: устанавливают для указания того, что элемент содержит первую (головную) транзакцию для заданного перечня для банка

Кроме того, число, идентифицированное полем 305 в каждом элементе 300, идентифицирует место, где хранятся подробности транзакции в буфере 230.

Соответственно, пример заполненного перечня QoS для банка 1 может иметь вид, схематично проиллюстрированный перечнем 310 из фиг.4B. Из фиг.4B видно, что перечень 310 QoS можно считать сформированным из нескольких подперечней 311, 312, 313, 314. В каждом подперечне каждый элемент имеет один и тот же указатель QoS, и относительное упорядочение элементов в каждом подперечне зависит от временного порядка приема этих транзакций интерфейсом 200 из контроллера 50 памяти. Как показано на Фиг.4B, первый флаг одного и только одного элемента в подперечне 311 установлен так, что указывает, что эта транзакция является головной транзакцией для перечня 310 QoS, и, аналогичным образом, последнее поле последней транзакции в подперечне 314 установлено так, что указывает, что эта транзакция является хвостовой транзакцией для конкретного перечня QoS.

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

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

Банк: целевой банк для транзакции, хранящейся в этом элементе

Строка: целевая строка для транзакции, хранящейся в этом элементе

T: устанавливают для указания того, что элемент содержит хвостовую транзакцию для заданного перечня попаданий в строку

H: устанавливают для указания того, что элемент содержит головную транзакцию для заданного перечня попаданий в строку

IB: устанавливают для указания того, что элемент содержит попадание в строку внутри пакета, а не обычное попадание в строку

Когда новую ожидающую транзакцию распределяют в буфер 230 ожидающих транзакций, то, если уже имеется хранящаяся транзакция с соответствующими банком/строкой, которая помечена как хвостовой перечень попаданий в строку, то элемент для новой транзакции, проталкивают в этот перечень для формирования нового хвостового элемента. В противном случае элемент распределяют так, что формируют новый перечень попаданий в строку. Следовательно, пример заполненного перечня попаданий в строку для строки 4 банка 1 может иметь вид, схематично проиллюстрированный на фиг.5B как перечень 330.

На фиг.6 изображена блок-схема последовательности операций, на которой проиллюстрировано функционирование схемы 220 распределения по перечням из фиг.3 согласно одному варианту осуществления изобретения, причем в этом варианте осуществления изобретения предполагают, что поле IB попадания в строку внутри пакета не используется. На этапе 350 схема 220 распределения по перечням принимает новую транзакцию для распределения этой транзакции, направляемой в строку B банка A, и показатель QoS для нее равен Z. На этапе 355 определяют, имеется ли уже перечень QoS для банка A, то есть, имеются ли какие-либо другие ожидающие транзакции, направленные в банк A. Если они отсутствуют, то в последовательности операций переходят к этапу 375, на котором создают элемент в новом перечне QoS для банка A, и устанавливают оба флага для этого элемента: “первый” и “последний”. Если перечень QoS для банка A отсутствует, то также имеет место то, что перечень попаданий в строку для строки B банка A отсутствует, и, соответственно, если этап 375 выполнен, то в способе также выполняют этап 390, на котором создают элемент в перечне попаданий в строку для строки B банка A и устанавливают оба флага: “головной” и “хвостовой”, для этого элемента.

Принимая, что на этапе 355 определено, что перечень QoS для банка A существует, то переходят к этапу 360, на котором определяют, является ли показатель Z QoS для текущей транзакции большим, чем показатель QoS для элемента с самым высоким приоритетом в перечне QoS для банка A, то есть, для элемента, для которого установлено его поле “первый”. Если это так, то это указывает, что новую транзакцию следует добавить в головную позицию перечня QoS, и, соответственно, в последовательности операций переходят к этапу 370, на котором создают элемент в головной части существующего перечня QoS, причем этот элемент наследует флаг “первый” от предыдущего головного элемента из этого перечня QoS. Однако, если показатель Z QoS не превышает показатель QoS для элемента с самым высоким приоритетом в перечне QoS для банка A, то в последовательности операций переходят к этапу 365, на котором создают элемент и помещают его в надлежаще место в перечне QoS для банка A. Описание одного из способов выполнения этапа 365 из фиг.6 приведено ниже со ссылкой на фиг.7.

После выполнения либо этапа 365, либо этапа 370, на этапе 380 определяют, имеется ли перечень попаданий в строку для банка A и строки B. Если нет, то совершают переход к этапу 390, но если перечень попаданий в строку уже имеется для строки B банка A, то переходят к этапу 385, на котором создают новый элемент в хвосте этого перечня попаданий в строку, причем этот элемент наследует флаг “хвостовой” от предыдущего хвостового элемента.

На фиг.7 изображена блок-схема последовательности операций, на которой проиллюстрирована последовательность этапов, которые могут использоваться для реализации этапа 365 из фиг.6, согласно одному варианту осуществления изобретения. На этапе 400 параметр N устанавливают равным нулю, после чего на этапе 405 определяют, является ли уровень QoS для элемента N большим или равным показателю Z QoS, и, кроме того, является ли показатель pQoS, идентифицированный в элементе N, меньшим, чем показатель Z QoS. Если это не так, то переходят к этапу 410, на котором определяют, был ли проанализирован последний элемент перечня QoS, и если он не был проанализирован, на этапе 415 производят приращение параметра N, и в способе возвращаются к этапу 405. Когда для конкретного элемента определено, что выполнено условие, установленное на этапе 405, то в последовательности операций переходят к этапу 420, на котором создают элемент непосредственно после элемента N в перечне QoS. Для того, чтобы всегда обеспечивалось выполнение условия из этапа 405 для одного элемента из перечня, показатель pQoS последнего элемента в перечне может быть установлено равным некоторому заранее заданному значению, которое, как полагают, всегда является меньшим, чем показатель Z QoS. Например, со ссылкой на фиг.4B, такой заранее заданный уровень указан символом “X” в хвостовом элементе перечня QoS.

В дополнение к созданию элемента на этапе 420, при необходимости на этапе 425 устанавливают флаг “последний” (обычно, это может быть сделано путем наследования флага “последний” от элемента N), и, кроме того, на этапе 430 обновляют значение указателя и показателя pQoS для элемента N.

Этот способ схематично проиллюстрирован на фиг.8, где элемент, показанный на фиг.4A, вставляют в перечень 310 QoS из фиг.4B а качестве нового элемента 455 для создания модифицированного перечня 450 QoS. В частности, в этом случае показатель Z QoS для новой транзакции, подлежащей распределению, равен “4”, и, следовательно, элемент 457 идентифицируют как элемент N, удовлетворяющий условию из этапа 405 на фиг.7, поскольку изначально показатель QoS для него был равен 4, а показатель pQoS был равен 1 (что очевидно из соответствующего элемента в перечне 310 QoS из фиг.4B). Соответственно, распределяют новый элемент 455, унаследовавший исходное значение указателя от элемента 457, тогда как элемент 457 видоизменяют так, чтобы он указывал на новый элемент 455. Кроме того, показатель pQoS, хранящийся в элементе 457, обновляют с “1” до “4” для правильной идентификации показателя QoS для следующего элемента 455. Поскольку новый элемент 455 не является последним элементом в перечне QoS, то для него флаг “последний” не устанавливают.

Несмотря на то, что в варианте осуществления изобретения, описанном выше со ссылкой на фиг.7 и фиг.8, рассмотрен один подходящий механизм для выполнения этапа 365 из фиг.6, где каждый элемент хранит оба показателя: показатель QoS и показатель pQoS, понятно, что для упрощения и ускорения процедуры распределения при желании могут использоваться и другие способы. Например, при желании может использоваться способ обхода таблицы.

На фиг.9 изображена блок-схема последовательности операций, на которой проиллюстрирована операция арбитража, выполняемая схемой 240 арбитража из фиг.3, согласно одному варианту осуществления изобретения. Когда необходимо выбрать новую транзакцию для передачи в интерфейс 250 запоминающего устройства, то операция арбитража начинается на этапе 500, после которого на этапе 505 определяют, был ли установлен сигнал ограничителя. Этот сигнал будет более подробно рассмотрен ниже со ссылкой на чертежи фиг.10A-фиг.10C. Однако, если этот сигнал ограничителя не установлен, то в последовательности операций переходят к этапу 510, на котором определяют, был ли элемент, для которого был ранее осуществлен арбитраж (то есть, элемент, соответствующий предыдущему запросу на выявление победителя при выполнении операции арбитража в прошлый раз), помечен как хвостовой элемент из его перечня попаданий в строку. Если нет, это указывает, что соответствующий перечень попаданий в строку еще не является пустым, и, соответственно, в процедуре выполняют переход к этапу 520, на котором элементом, выбранным при операции арбитража, является тот элемент в перечне попаданий в строку, на который указывает указатель попадания из элемента, для которого был ранее осуществлен арбитраж.

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

После этапа 515 или этапа 520 в последовательности операций переходят к этапу 525, на котором выбранный элемент извлекают из перечня QoS и из перечня попаданий в строку, а эта процедура описана ниже со ссылкой на чертежи фиг.11A и фиг.11B.

На фиг.10A схематично проиллюстрирован пример схемы 550 ограничителя, которая может использоваться в одном варианте осуществления изобретения. В одном конкретном варианте осуществления изобретения схема ограничителя предусмотрена отдельно для каждого банка, и можно считать, что она является частью схемы 240 арбитража. Каждая схема ограничителя включает в себя счетчик 555, приращение показания которого выполняют при каждом выборе победившей транзакции для соответствующего банка из перечня попаданий в строку. Кроме того, показание счетчика сбрасывают при каждом выборе победившей транзакции из перечня QoS для этого банка. Если значение отсчета, которое сохраняет счетчик 555, достигает заранее заданного порогового значения, то устанавливают сигнал ограничителя. Со ссылкой на этап 505 из Фиг.9, понятно, что когда сигнал ограничителя установлен, то это вызывает переход в последовательности операций непосредственно к этапу 515, вследствие чего следующую победившую транзакцию выбирают из перечня QoS, а не из перечня попаданий в строку, даже если последняя победившая транзакция была из того элемента перечня попаданий в строку, который не расположен в хвостовой позиции. За счет такого подхода все же может быть обеспечен учет уровня QoS других транзакций, даже при наличии большого количества ожидающих транзакций в конкретной строке в конкретном банке, что, следовательно, гарантирует, что при наличии большого количества ожидающих транзакций в конкретной строке не будет происходить задержка транзакции с высоким приоритетом до недопустимого уровня.

На фиг.10B проиллюстрирован альтернативный пример схемы ограничителя, где вместо простого счетчика используется схема для выполнения некоторой функции 565 анализа выгоды. В дополнение к сигналам, принятым счетчиком 555 из фиг.10A, функция 565 анализа выгоды принимает указатель QoS, соответствующего головному элементу перечня QoS для соответствующего банка. Вследствие свойств динамического запоминающего устройства DRAM, может быть сформирован график, такой как, например, график, показанный на фиг.10C, определяющий выгоду попадания в строку при последовательных операциях доступа к адресам памяти в конкретной строке. Изначально выгода попадания в строку является очень большой, поскольку необходимо активировать строку до того, как к ней можно будет осуществлять доступ, и также обычно существует заранее заданная задержка, необходимая перед тем, как снова сможет быть произведена предварительная зарядка этой строки. Следовательно, в течение этого промежутка времени график имеет горизонтальную форму, показанную на фиг.10C. Однако, после этого начального промежутка времени выгода медленно уменьшается, что показано криволинейным графиком 570, вследствие того, что непроизводительные издержки уменьшаются вследствие множества операций доступа к конкретной строке. Соответственно, график из фиг.10C может быть преобразован в шкалу с уменьшающимися приоритетами, которая соответствует продолжающимся операциям доступа к конкретной строке, то есть, при увеличении количества последовательных операций доступа фактический показатель QoS, соответствующий этим операциям доступа, уменьшается. Соответственно, в некоторый момент этот псевдопоказатель QoS падает до уровня меньшего, чем показатель QoS, соответствующий головному элементу из перечня QoS, и в этот момент сигнал ограничителя может быть установлен таким, что вызывает выбор следующей победившей транзакции из головного элемента перечня QoS банка вместо ее выбора из перечня попаданий в строку.

На фиг.11A изображена блок-схема последовательности операций, на которой проиллюстрированы этапы, выполняемые на этапе 525 из фиг.9 для извлечения элемента из перечня QoS. Когда на этапе 600 определено, что такой элемент необходимо извлечь, то в последовательности операций переходят к этапу 605, на котором определяют, находится ли элемент, подлежащий извлечению, в головной части перечня QoS. Ясно, что это имеет место, если этап 525 из фиг.9 был достигнут в результате выполнения этапа 515 из фиг.9, но что это не обязательно имеет место, если этап 525 был достигнут через этап 520 из фиг.9. В частности, когда элемент выбирают из перечня попаданий в строку, то соответствующий ему элемент в перечне QoS для банка может находиться в любом месте в этом перечне QoS для банка.

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

Процедура, выполняемая на этапе 615, схематично проиллюстрирована на фиг.12, где извлекают элемент 477 в перечне 470 QoS, в результате чего обновляют указатель элемента 475, который ранее указывал на элемент 477, так, чтобы он указывал на элемент 478, и обновляют его показатель pQoS так, чтобы он отражал показатель QoS элемента 478. Поскольку для извлеченного элемента 477 его флаг “последний” не установлен, то элемент 475 также не установлен как последний элемент.

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

На фиг.13 изображена блок-схема последовательности операций, на которой проиллюстрированы этапы, выполняемые схемой 220 распределения по перечням из фиг.3, согласно альтернативному варианту осуществления изобретения. Сравнивая фиг.13 с описанным выше чертежом фиг.6, понятно, что этапы 700-725 и 750-760 из фиг.13 соответствуют, соответственно, этапам 350-375 и 380-390 из фиг.6, и, следовательно, подробное описание этих этапов не приведено. Однако, в блок-схеме последовательности операций из фиг.13 выполняют четыре дополнительных этапа, а именно, этапы 730-745.

В частности, на фиг.13 перечни QoS включают в себя опцию эскалации считывания, которая может быть активирована или деактивирована, причем эту опцию эскалации считывания также именуют здесь схемой “близнецов”. Если опция эскалации считывания не активирована, то в последовательности операций переходят к этапу 740. Однако, если функция эскалации считывания активирована, то в последовательности операций переходят к этапу 735, на котором повышают показатель QoS указанного элемента так, чтобы он был равным показателю Z QoS. Это схематично проиллюстрировано на чертеже фиг.14, на котором показано то же самое распределение, которое было рассмотрено выше со ссылкой на фиг.8, но которое дополнительно демонстрирует эффект функции эскалации считывания. В частности, при введении нового элемента 455 показатель QoS для следующего элемента 460 увеличивают так, чтобы он был равным показателю QoS для нового элемента, то есть, указывающим показатель QoS, равный 4. В результате показатель pQoS, идентифицированный во введенном элементе 455, теперь принимает значение, равное 4. В противном случае эта процедура является в точности такой же, как и процедура, рассмотренная выше со ссылкой на фиг.8. Целесообразность такого подхода состоит в том, что приоритет элемента 460 повышают при введении нового элемента перед ним в перечне QoS, и в результате это может предотвратить неопределенное блокирование транзакций с более низким приоритетом, что позволят реализовать прогнозируемые вычисления задержки. Несмотря на то, что в варианте осуществления изобретения, рассмотренном со ссылкой на фиг.13, показатель QoS элемента, на который он указывает, обновляют так, чтобы он был равен показателю Z QoS, понятно, что это не является требованием, и в альтернативном варианте осуществления схемы эскалации считывания может являться достаточным просто увеличение показателя QoS на некоторую заранее заданную величину.

Этапы 740 и 745 относятся к связанным пакетным транзакциям, которые упомянуты выше. В частности, в одном варианте осуществления изобретения перечни попаданий в строку могут быть скомпонованы так, что обеспечивают поддержку одного или более перечней-ответвлений, причем каждый перечень-ответвление имеет несколько элементов из перечней-ответвлений, идентифицирующих связанные пакетные транзакции. Следовательно, на этапе 740 определяют, являлась ли новая транзакция, подлежащая распределению, связанной пакетной транзакцией, для которой более ранней соответствующей связанной пакетной транзакций уже был выделен элемент в перечне попаданий в строку для строки B банка A. Если она является такой, то в последовательности операций переходят к этапу 745, на котором создают элемент перечня-ответвления в перечне-ответвлении из перечня попаданий в строку для строки B банка A, и этот элемент помечают как находящийся “внутри пакета” путем установки флага IB. Это схематично проиллюстрировано на фиг.15 для перечня попаданий в строку 480. В частности, первой связанной пакетной транзакции назначен элемент 485 в перечне 480 попаданий в строку. Однако, каждой последующей связанной пакетной транзакции назначен элемент 487, 489 перечня-ответвления в перечне-ответвлении. Такие элементы перечня-ответвления могут быть затем обработаны по-иному во время арбитража, что будет рассмотрено, например, со ссылкой на фиг.16.

В частности на фиг.16 проиллюстрирована операция арбитража, которая может выполняться схемой 240 арбитража из фиг.3, согласно альтернативному варианту осуществления изобретения. В сравнении с описанным выше чертежом фиг.9, понятно, что этапы 825-845 соответствуют этапам 505-525 из фиг.9, и, соответственно, их подробное описание здесь не приведено. Однако, перед этапом 825 выполняют несколько дополнительных этапов. В частности, на этапе 805 определяют, указывает ли элемент перечня-ответвления с его установленным флагом “внутри пакета” на элемент, для которого был ранее осуществлен арбитраж. Следовательно, со ссылкой на фиг.15, если элементом, для которого был ранее осуществлен арбитраж, является элемент 485, то будет иметь место, поскольку элемент 487 указывает на него. Аналогичным образом, если элементом, для которого был ранее осуществлен арбитраж, являлся элемент 487, то также имеет место, что элемент 489 указывает на элемент 487.

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

Однако, если на этапе 805 определено, что такой элемент перечня-ответвления отсутствует, то в последовательности операций переходят к этапу 815, на котором определяют, имеется ли транзакция с ее установленным флагом TimedOut (превышение лимита времени). В частности, в этом варианте осуществления изобретения флаг TimedOut используют в качестве примера заранее заданного условия исключения, и когда флаг TimedOut установлен для идентификации наличия заранее заданного условия исключения, обычную процедуру арбитража не выполняют, а вместо этого в последовательности операций совершают переход к этапу 820. Флаг TimedOut может быть установлен по множеству причин. Однако, в одном варианте осуществления изобретения элементы в ином месте системы обработки данных могут определять, что обработку конкретной транзакции необходимо осуществлять настолько быстро, насколько это практически возможно, либо потому что, был достигнут верхний предел задержки для этой транзакции, либо потому, что различные другие транзакции не могут проходить до тех пор, пока не будет обработана эта транзакция, и т.д. Соответственно, эти элементы выдают управляющие сигналы, которые вызывают повышение приоритета этой транзакции, вызывая установление флага TimedOut в контроллере памяти для этой конкретной транзакции. Имеется несколько мест, где может храниться такой флаг TimedOut. Однако, в одном варианте осуществления изобретения этот флаг TimedOut хранится совместно с подробностями каждой ожидающей транзакции в буфере 230 ожидающих транзакций.

Если для какой-либо транзакции установлен флаг TimedOut, то в последовательности операций переходят к этапу 820, на котором выбирают транзакцию, для которой установлен ее флаг TimedOut. При наличии множества транзакций с установленным флагом TimedOut, то на этапе 820 победившая транзакция может быть выбрана с использованием любого подходящего способа выбора, например, путем случайного выбора из транзакций с установленным флагом TimedOut. Однако, обычно ожидается, что, как правило, не будет множества транзакций с установленным флагом TimedOut, поскольку это указывало бы, что контроллер 50 памяти не установил приоритеты показателей QoS, соответствующих транзакциям, надлежащим образом. В этом случае было бы целесообразно ослабить требование относительно установления сигнала ограничителя, чтобы переход от этапа 825 к этапу 835 происходил более часто, уменьшая, тем самым, вероятность того, что транзакция будет иметь ее установленный флаг TimedOut.

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

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

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

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

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

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

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

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

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

7. Контроллер памяти по п. 6, в котором каждый элемент дополнительно идентифицирует указатель приоритета соответствующей транзакции, подлежащей дальнейшему выполнению.

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

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

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

11. Контроллер памяти по п. 10, в котором обновляется указатель приоритета соответствующей ожидающей транзакции в упомянутом следующем элементе.

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

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

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

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

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

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

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

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

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

21. Контроллер памяти по п. 1 или 2, в котором упомянутым указателем приоритета является явный указатель приоритета, предусмотренный в поле каждой транзакции.

22. Контроллер памяти по п. 21, в котором упомянутым указателем приоритета является указатель уровня QoS.

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

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

25. Контроллер памяти по п. 1 или 2, в котором транзакциями, принятыми упомянутым интерфейсом, являются транзакции считывания.

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

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

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