СОВМЕСТНО ИСПОЛЬЗУЕМЫЕ РЕСУРСЫ В УСТРОЙСТВЕ ОБРАБОТКИ ДАННЫХ ДЛЯ ВЫПОЛНЕНИЯ МНОЖЕСТВА ПОТОКОВ
SHARED RESOURCES IN DATA PROCESSING DEVICE FOR IMPLEMENTATION OF MULTITUDE OF STREAMS

Настоящее изобретение относится к области обработки данных. В частности, настоящее изобретение относится к устройству и способу обработки данных, в которых выполняется множество потоков.
Устройство обработки данных может выполнять множество потоков. Потоки могут развиваться в жесткой конфигурации. В частности, каждый поток может поддерживать свой собственный программный счетчик. Сама система может поддерживать свой собственный общий программный счетчик, таким образом, что команда, учитываемая общим программным счетчиком, выполняется для потоков, программные счетчики которых совпадают с общим программным счетчиком. Этот тип системы может именоваться, например, системой многопоточное выполнение единичной команды (SIMT). Поэтому, на каждом этапе, единичная команда выполняется для, по меньшей мере, поднабора из множества потоков. После выполнения команды для поднабора потоков, общий программный счетчик может изменяться для указания новой команды. В таких системах может быть предпочтительно устанавливать общий программный счетчик совпадающим с наименьшим из программных счетчиков, поддерживаемых каждым из потоков. Таким образом, самому заднему потоку может быть разрешено развиваться и, таким образом, догонять потоки, которые имеют более высокие программные счетчики. Это может приводить к схождению потоков, т.е. к совместному использованию одного и того же значения программного счетчика, таким образом, что единичная команда может выполняться в максимально возможном количестве потоков.
Модификация этой схемы предусматривает отслеживание глубины вызова функции каждого потока. В частности, всякий раз, когда поток совершает вызов функции, счетчик глубины вызова функции для этого потока увеличивается, и всякий раз, когда поток возвращается из вызова функции, счетчик глубины вызова функции для этого потока уменьшается. Когда общий программный счетчик подлежит изменению, он устанавливается совпадающим с программным счетчиком потока, сначала имеющим наибольший счетчик глубины вызова функции и затем (если существует несколько таких потоков) поток или потоки из этого набора, имеющим наименьшее значение программного счетчика. Другими словами, значение программного счетчика рассматривается только из всех потоков, имеющих наибольшую глубину вызова функции. Соответственно, это помогает предотвращать проблему производительности или ситуацию взаимоблокировки, которая может возникать, если рассматривать только значения программного счетчика. Когда поднабор потоков совершает вызов функции, это может приводить к сильному увеличению программных счетчиков, связанных с этими потоками, из-за чего, команды, которые должны выполняться после самой функции, не имеют наименьших значений программного счетчика. Благодаря выбору потоков для выполнения на основании глубины вызова функции, функция может обрабатываться в первую очередь, даже если она не имеет наименьшего программного счетчика.
Оба из двух вышеупомянутых механизмов склонны к взаимоблокировке, где код, подлежащий выполнению, содержит совместно используемый ресурс, к которому требуется монопольный доступ. Например, блокировка может удерживаться единичным потоком в любой один момент, что позволяет этому потоку и только этому потоку осуществлять доступ к совместно используемому ресурсу.
Поток, который осуществляет доступ к совместно используемому ресурсу, может иметь более высокий программный счетчик, чем остальные потоки, которые не могут осуществлять доступ к совместно используемому ресурсу. Следовательно, остальные потоки будут способны выполняться, тогда как поток, который имеет доступ к совместно используемому ресурсу, не будет. Взаимоблокировка будет происходить потому, что остальные потоки не будут способны осуществлять доступ к совместно используемому ресурсу, тогда как другой поток имеет доступ к нему. Однако потоку с доступом к совместно используемому ресурсу никогда не может быть разрешено выполняться. Соответственно, ни один из потоков не развивается, и система останавливается.
В соответствии с одним аспектом настоящего изобретения предусмотрено устройство обработки данных, выполненное с возможностью выполнения множества потоков, причем устройство обработки данных содержит: общий программный счетчик для идентификации одной команды в ряде команд, подлежащих выполнению для, по меньшей мере, поднабора из множества потоков, причем с каждым потоком в поднаборе связан программный счетчик потока для идентификации одной команды в ряде команд, блок выбора, выполненный с возможностью выбора выбранного потока из поднабора потоков и установления общего программного счетчика на программный счетчик потока, связанный с выбранным потоком; и процессор, выполненный с возможностью выполнения команды, идентифицированной общим программным счетчиком для одного или более из поднабора потоков, включающего в себя выбранный поток, причем поднабор потоков связан с по меньшей мере одним параметром блокировки для отслеживания, какой из поднабора потоков имеет монопольный доступ к совместно используемому ресурсу; причем процессор выполнен с возможностью изменения по меньшей мере одного параметра блокировки для указания, что поток получил монопольный доступ к совместно используемому ресурсу в ответ на первую команду, выполняемую для этого потока, и изменения по меньшей мере одного параметра блокировки для указания, что поток больше не имеет монопольного доступа к совместно используемому ресурсу в ответ на вторую команду, выполняемую для этого потока; и причем блок выбора выполнен с возможностью выбора выбранного потока на основании параметра блокировки, связанного с каждым потоком.
В соответствии с другим аспектом настоящего изобретения, предусмотрен способ обработки данных для выполнения ряда команд для поднабора из множества потоков, причем с каждым потоком в поднаборе связан программный счетчик потока для идентификации одной команды в ряде команд, причем способ обработки данных содержит этапы:
выбора выбранного потока из поднабора потоков и установления общего программного счетчика на программный счетчик потока, связанный с выбранным потоком, причем общий программный счетчик идентифицирует одну команду в ряде команд, подлежащих выполнению, для поднабора потоков; и
выполнения команды, идентифицированной общим программным счетчиком для одного или более из поднабора потоков, включающего в себя выбранный поток,
причем поднабор потоков связан с по меньшей мере одним параметром блокировки для отслеживания, какой из поднабора потоков имеет монопольный доступ к совместно используемому ресурсу;
причем по меньшей мере один параметр блокировки изменяется для указания, что поток получил монопольный доступ к совместно используемому ресурсу в ответ на первую команду, выполняемую для этого потока, и изменяется для указания, что поток больше не имеет монопольного доступа к совместно используемому ресурсу в ответ на вторую команду, выполняемую для этого потока; и
причем блок выбора выполнен с возможностью выбора выбранного потока на основании по меньшей мере одного параметра блокировки.
В соответствии с другим аспектом, предусмотрено устройство обработки данных, выполненное с возможностью выполнения множества потоков, причем устройство обработки данных содержит:
средство общего программного счетчика для идентификации одной команды в ряде команд, подлежащих выполнению для, по меньшей мере, поднабора из множества потоков, причем с каждым потоком в поднаборе связано средство программного счетчика потока для идентификации одной команды в ряде команд,
средство выбора для выбора выбранного потока из поднабора потоков и для установления средства общего программного счетчика на средство программного счетчика потока, связанное с выбранным потоком; и
средство процессора для выполнения команды, идентифицированной средством общего программного счетчика для одного или более из поднабора потоков, включающего в себя выбранный поток,
причем поднабор потоков связан с по меньшей мере одним параметром блокировки для отслеживания, какой из поднабора потоков имеет монопольный доступ к совместно используемому ресурсу;
причем средство процессора служит для изменения по меньшей мере одного параметра блокировки для указания, что поток получил монопольный доступ к совместно используемому ресурсу в ответ на первую команду, выполняемую для этого потока, и для изменения по меньшей мере одного параметра блокировки для указания, что поток больше не имеет монопольного доступа к совместно используемому ресурсу в ответ на вторую команду, выполняемую для этого потока; и
причем средство выбора служит для выбора выбранного потока на основании по меньшей мере одного параметра блокировки.
Дополнительные аспекты, признаки, преимущества и иллюстративные варианты осуществления настоящего изобретения будут описано, исключительно в порядке примера, со ссылкой на чертежи, в которых:
фиг. 1 - устройство обработки данных в соответствии с одним вариантом осуществления;
фиг. 2 - пример выполнения нескольких разных потоков, имеющих разные значения программного счетчика;
фиг. 3 - код в котором взаимоблокировка может происходить в системе SIMT;
фиг. 4 - второй пример кода, который поясняет, как можно предотвратить взаимоблокировку, показанную на фиг. 3;
фиг. 5 - блок-схема операций выбора между потоками системы SIMT;
фиг. 6 - блок-схема операций способа выполнения потоков;
фиг. 7 - другой пример данных состояния, поддерживаемых для поднабора потоков;
фиг. 8 - третий пример кода; и
фиг. 9 - блок-схема операций, демонстрирующая способ выбора программного счетчика потока с использованием данных состояния, показанных на фиг. 7.
В одном примере, с поднабором потоков связан по меньшей мере один параметр блокировки для отслеживания, какой поток из поднабора имеет монопольный доступ к совместно используемому ресурсу. Процессор может, в ответ на первую команду, выполняемую потоком, изменять по меньшей мере один параметр блокировки, чтобы, таким образом, указывать, что поток получил монопольный доступ к этому совместно используемому ресурсу. Аналогично, процессор может, в ответ на вторую команду, изменять по меньшей мере один параметр блокировки, чтобы, таким образом, указывать, что поток больше не имеет монопольного доступа к этому совместно используемому ресурсу. При выборе выбранного потока, программный счетчик потока которого используется в качестве значения для общего программного счетчика, и, таким образом, определения, какую команду выполнять следующей для поднабора потоков, устройство обработки данных может рассматривать по меньшей мере один параметр блокировки. Выбирая значение общего программного счетчика на основании параметра блокировки, можно управлять, какие потоки способны выполняться в любой конкретный момент, и, таким образом, снижать вероятность возникновения взаимоблокировки или предотвращать его.
Например, первая команда может выполняться, когда поток получает или получил монопольный доступ к совместно используемому ресурсу, и вторая команда может выполняться, когда поток отказывается или отказался от доступа к совместно используемому ресурсу.
Процессор может быть выполнен с возможностью предоставления монопольного доступа к потоку для совместно используемого ресурса в ответ на последовательность блокирования, содержащую по меньшей мере одну команда блокирования, выполняемую для этого потока. Последовательность блокирования может содержать несколько разных команд, предусматривающих различные сравнения, загрузки и сохранения. В этой последовательности может существовать команда блокирования, которая окончательно устанавливает 'владение' совместно используемым ресурсом. В некоторых примерах, команда блокирования может приводить к идентификации потока, имеющего монопольный доступ к совместно используемому ресурсу, подлежащему сохранению или записи. В других примерах, команда блокирования может лишь устанавливать указание, что ресурс заблокирован, в явном виде не идентифицируя поток владеет блокировкой. Последовательность блокирования, в ряде случаев, может не содержать первой команды. Другими словами, последовательность блокирования, которая предписывает потоку получать монопольный доступ к совместно используемому ресурсу, может быть отдельной от первой команды, которая указывает процессору, что поток получил монопольный доступ к совместно используемому ресурсу. Поэтому код может содержать последовательность блокирования, содержащую команду блокирования, предваряемую или сопровождаемую первой командой. Этот подход может быть полезен, чтобы гарантировать обратную совместимость с традиционными системами, которые не поддерживают первую команду. Даже если первая команда не поддерживается, последовательность блокирования все же может обрабатываться как нормальная традиционной системой. Некоторые примеры могут выполнять последовательность блокирования до первой команды, таким образом, что поток сначала пытается получить монопольный доступ к совместно используемому ресурсу, и затем, в случае успеха, параметр блокировки обновляется, соответственно, путем выполнения первой команды. Другие примеры могут выполнять первую команду до последовательности блокирования, благодаря чему, фактически, первая команда используется для запрашивания привилегии блокирования для потока до фактического осуществления блокировки с использованием последовательности блокирования. Во втором случае, развитие к последовательности блокирования может зависеть от успешного выполнения первой команды, которое может зависеть от того, имеет ли уже другой поток блокировку. В других вариантах осуществления, последовательность блокирования содержит первую команду. Другими словами, последовательность блокирования предоставляет одному из потоков монопольный доступ к совместно используемому ресурсу и также устанавливает параметр блокировки для этого потока для указания, что поток имеет монопольный доступ к совместно используемому ресурсу. Следовательно, существуют разные способы осуществления последовательности блокирования и первой команды.
Аналогично, процессор может быть выполнен с возможностью отказа от монопольного доступа к потоку для совместно используемого ресурса в ответ на последовательность разблокирования, содержащую по меньшей мере одну команду разблокирования, выполняемую для этого потока. Последовательность разблокирования может содержать несколько разных команд, включающих в себя сравнения, загрузки или сохранения, например, которые приводят к тому, что конкретный поток теряет монопольный доступ к совместно используемому ресурсу. От монопольного доступа к ресурсу можно отказываться путем удаления блокировки для ресурса или путем передачи монопольного доступа, например, другому потоку. В последовательности разблокирования может существовать команда разблокирования, которая используется для выяснения, какой поток имеет монопольный доступ к совместно используемому ресурсу, или для указания, что конкретный поток больше не имеет доступа к совместно используемому ресурсу. Другими словами, команда разблокирования может использоваться для установления или очистки переменной для указания, что конкретный поток больше не имеет монопольного доступа к совместно используемому ресурсу. В некоторых вариантах осуществления, последовательность разблокирования не содержит второй команды. Другими словами, последовательность разблокирования не изменяют параметр блокировки, связанный с потоком, для указания, что поток больше не имеет монопольного доступа к этому совместно используемому ресурсу. Соответственно, существует разделение между командой или командами в коде, которые осуществляют разблокирование, и командой в коде, которая устанавливает параметр блокировки для указания, что поток больше не имеет доступа к совместно используемому ресурсу. Это полезно по соображениям обратной совместимости, как рассмотрено выше. Вторая команда может выполняться после последовательности разблокирования. В других вариантах осуществления, последовательность разблокирования содержит вторую команду.
Блок выбора может быть выполнен с возможностью выбора, в качестве выбранного потока, первого потока, указанного по меньшей мере одним параметром блокировки как имеющего монопольный доступ к совместно используемому ресурсу, в порядке предпочтения второму потоку, указанному по меньшей мере одним параметром блокировки как не имеющего монопольного доступа к совместно используемому ресурсу. Другими словами, блок выбора может быть сконфигурирован таким образом, что поток, имеющий монопольный доступ к совместно используемому ресурсу, получает приоритет. Таким образом, этот поток способен завершать свое использование совместно используемого ресурса для разблокировки совместно используемого ресурса. Это помогает предотвращать взаимоблокировку, поскольку первому потоку, который имеет возможность разблокировки совместно используемого ресурса, разрешено выполняться и, таким образом, разблокировать совместно используемый ресурс.
Блок выбора может быть выполнен с возможностью выбора выбранного потока на основании параметра глубины вызова функции, связанного с каждым потоком в поднаборе потоков. Другими словами, блок выбора может рассматривать, как параметр глубины вызова функции, так и по меньшей мере один параметр блокировки, при определении программный счетчик потока какого потока следует использовать для установления общего программного счетчика.
Блок выбора может быть выполнен с возможностью выбора выбранного потока на основании программного счетчика потока, связанного с каждым потоком из поднабора потоков. Другими словами, блок выбора может рассматривать, как программный счетчик потока, так и по меньшей мере один параметр блокировки при принятии решения, какой программный счетчик потока устанавливать на общий программный счетчик.
Выбор выбранного потока может осуществляться по-разному. В некоторых примерах, поток можно выбирать напрямую, и затем программный счетчик потока этого потока можно использовать для общего программного счетчика. В других примерах, конкретный программный счетчик потока можно выбирать с использованием данного алгоритма выбора программного счетчика (неявно выбирая соответствующий поток в качестве выбранного потока). Следовательно, в общем случае, ссылки на выбор выбранного потока в этой заявке призваны охватывать выбор программного счетчика потока, связанного с потоком.
Параметр блокировки может принимать несколько разных форм. В одном примере, каждый поток в поднаборе может иметь соответствующий параметр блокировки. Когда поток, который получает монопольный доступ к совместно используемому ресурсу, выполняет первую команду, параметр блокировки для этого потока может изменяться для указания, что поток получил монопольный доступ к ресурсу. Аналогично, когда поток отказывается от монопольного доступа к потоку, соответствующий параметр блокировки может изменяться, в ответ на вторую команду, выполняемую для этого потока, для указания, что поток больше не имеет монопольного доступа к совместно используемому ресурсу. Например, параметр блокировки для каждого потока может указывать, сколько совместно используемых ресурсов в данный момент заблокировано этим потоком. В этом случае, процессор может разрешать множественным потокам одновременно иметь монопольный доступ к разным совместно используемым ресурсам. При выборе выбранного потока, блок выбора может рассматривать параметры блокировки потоков для выбора первого набора потоков (например, выбора потоков с параметром блокировки, указывающим наибольшее количество заблокированных ресурсов), и затем из первого набора потоков, выбирать второй набор потоков на основании глубины вызова функции, и затем выбирать один из второго набора потоков в качестве выбранного потока на основании программных счетчиков потока, связанных с потоками во втором наборе потоков. Этот подход обеспечивает повышенную производительность, поскольку позволяет множественным потокам одновременно удерживать блокировки разных ресурсов, благодаря чему, они могут продолжаться параллельно друг с другом.
Другими словами, блок выбора может быть выполнен с возможностью сначала рассматривать параметр блокировки потоков, затем глубину вызова функции и, наконец, программный счетчик. Рассмотрение параметров в этом порядке дает возможность предписывать в конкретный момент выполнение команды из наиболее подходящего потока. Заметим, что блоку выбора может не требоваться осуществлять выбор из первого набора или второго набора. Например, если один-единственный поток имеет нужный параметр блокировки, то для установления общего программного счетчика будет использоваться программный счетчик потока этого потока. Аналогично, если первый набор потоков содержит два потока и только один из этих двух потоков имеет нужную глубину вызова функции, то второй набор потоков можно конкретно не формировать и, вместо этого, программный счетчик потока для потока в первом наборе потоков, имеющих нужную глубину вызова функции, можно устанавливать на общий программный счетчик. Другими словами, хотя блок выбора может быть выполнен с возможностью осуществления трех вышеупомянутых выборов, не всегда может быть необходимо осуществлять три выбора в каждом отдельном случае.
В другом примере по меньшей мере один параметр блокировки может содержать совместно используемый параметр блокировки, совместно используемый в поднаборе потоков, и параметр владельца блокировки, указывающий, какой из поднабора потоков имеет монопольный доступ к совместно используемому ресурсу. В ряде случаев совместно используемый параметр блокировки может содержать счетчик блокировки, указывающий, к скольким ресурсам поток, владеющий блокировкой, указанный параметром владельца блокировки, имеет монопольный доступ. В других случаях, совместно используемый параметр блокировки может содержать флаг блокировки, указывающий, имеет ли в данный момент какой-либо из поднабора потоков монопольный доступ к совместно используемому ресурсу. Согласно этому примеру, процессор может гарантировать, что только одному потоку из каждого поднабора потоков разрешено одновременно иметь монопольный доступ к совместно используемому ресурсу. Следовательно, если один поток имеет монопольный доступ к первому совместно используемому ресурсу, второму потоку не разрешен монопольный доступ ко второму совместно используемому ресурсу (даже когда второй совместно используемый ресурс отличается от первого совместно используемого ресурса). Этот подход обеспечивает увеличенную защиту от взаимоблокировок, которые могут возникать при наличии рекурсивных блокировок, где разные потоки преодолевают блокирование ряда ресурсов и затем по очереди освобождают блокировки. Если известно, что код, подлежащий выполнению, не может включать в себя такие рекурсивные блокировки, то предыдущий подход, в котором каждый поток имеет соответствующий параметр блокировки, может быть предпочтителен для повышения производительности (и предыдущий подход по-прежнему значительно снижает вероятность возникновения взаимоблокировки по сравнению с уровнем техники). Однако, если рекурсивные блокировки нужны, то ограничение блокировок одним потоком за раз может обеспечивать увеличенную защиту от взаимоблокировки. В этом случае, обеспечивать параметр блокировки для каждого потока не требуется, поскольку каждый раз удерживать блокировку может только один поток. Альтернативно, параметр владельца блокировки, указывающий, какой поток в данный момент удерживает блокировку, и параметра блокировки, совместно используемого в поднаборе потоков (например, счетчика блокировки, указывающего количество потоков, удерживаемых потоком, владеющим блокировкой) достаточно для отслеживания, какой поток удерживает блокировку, благодаря чему, выбор программного счетчика может способствовать выбору потока, удерживающего блокировку по другим потокам во избежание взаимоблокировок и чтобы гарантировать развитие вперед. Счетчик блокировки позволяет гарантировать, что все блокировки, установленные потоком, снова снимаются, прежде чем другим потокам будет позволено удерживать блокировку.
Во втором примере, если по меньшей мере один параметр блокировки указывает, что поток имеет монопольный доступ к одному или более совместно используемым ресурсам, то блок выбора может выбирать поток, владеющий блокировкой, указанный параметром блокировки в качестве выбранного потока, благодаря чему, поток, владеющий блокировкой, может развиваться таким образом, что, в конце концов, он снимет блокировку, и другой поток, в свою очередь, сможет получить блокировку. С другой стороны, если ни один поток не удерживает блокировку, то выбор выбранного потока могут базироваться на глубине вызова функции и программных счетчиках потока для потоков, как в первом примере.
В обоих рассмотренных выше примерах по меньшей мере один параметр блокировки может увеличиваться в ответ на первую команду и уменьшаться в ответ на вторую команду (независимо от того, используется ли параметр блокировки совместно в поднаборе потоков или только для одного потока). В одном примере параметр блокировки может иметь только два состояния - первое состояние, указывающее, что поток имеет монопольный доступ к совместно используемому ресурсу, и второе состояние, указывающее, что поток не имеет монопольного доступа к совместно используемому ресурсу. Такой параметр легко представлять, поскольку он требует одного-единственного бита для каждого потока. Соответственно, для представления состояния каждого потока требуется очень мало места и, таким образом, энергия. В других вариантах осуществления, параметр блокировки может указывать количество совместно используемых ресурсов, к которому поток имеет монопольный доступ. Другими словами, параметр блокировки может действовать как счетчик, который увеличивается, когда поток получает монопольный доступ к совместно используемому ресурсу, и уменьшается, когда поток теряет монопольный доступ к совместно используемому ресурсу. Такая система обеспечивает лучший указатель приоритета для каждого потока. В частности, может быть желательно отдавать предпочтение потоку, который имеет монопольный доступ к нескольким совместно используемым ресурсам, по сравнению с потоком, который имеет монопольный доступ только к одному совместно используемому ресурсу. Однако для сохранения этой дополнительной информации требуется больше места и, следовательно, больше энергии должно выделяться для каждого потока, подлежащего выполнению в системе.
Один или более из поднабора потоков, которые выполняются процессором, могут содержать потоки, имеющие один или более параметров потока, которые совпадают с соответствующими параметрами потока для выбранного потока. В одном примере, один или более параметров потока могут содержать только программный счетчик потока. Следовательно, один или более выполняемых потоков могут быть потоками, программный счетчик потока которых идентифицирует ту же команду, которая идентифицируется общим программным счетчиком. Другими словами, устройство обработки данных может выполнять все потоки, программный счетчик которых идентичен общему программному счетчику. Альтернативно, параметры потока также могут включать в себя один или оба из параметра глубины вызова функции и параметра блокировки, помимо программного счетчика потока, благодаря чему, команды выполняются для потоков, имеющих комбинацию параметров потока, совпадающих с параметрами потока для выбранного потока. Таким образом, единичная команда может выполняться одновременно для множественных потоков.
Команды, которые выполняются процессором устройства обработки данных, могут быть микрооперациями. В некоторых системах, сложная команда (например, команда множественных загрузки/сохранения) может делиться на микрооперации, прежде чем эти команды достигнут процессора. Следовательно, ссылки на ʺкомандуʺ в настоящей заявке следует интерпретировать в смысле команд или микроопераций, соответствующих части команды.
Первую команду и вторую команду можно кодировать как команду NOOP (без операций) в по меньшей мере одном заранее заданном наборе команд. В подобных случаях, набор команд, используемый устройством обработки данных, является расширенной версией заранее заданного набора команд. Другими словами, набор команд, используемый устройством обработки данных, может задавать команды, не заданные в заранее заданном наборе команд. В результате кодирования первой команды и второй команды как команд NOOP в по меньшей мере одном заранее заданном наборе команд, первая команда и вторая команда могут игнорироваться в этих заранее заданных наборах команд. Код, написанный для выполнения на устройстве обработки данных, все же, правильно функционирует на втором устройстве обработки данных, реализующем заранее заданный набор команд, поскольку первая команда и вторая команда просто не будут действовать на втором устройстве обработки данных. Следовательно, код, написанный для устройства обработки данных можно считать обратно совместимым с традиционными системами. Это означает, что для разных систем не требуется писать разные версии кода, что делает разработку кода более эффективной.
Процессор может быть выполнен с возможностью осуществления дополнительной операции в ответ на по меньшей мере одну из первой и второй команд. Например, дополнительная операция может быть одной или более из: операции, которая является частью последовательности блокирования для получения монопольного доступа к совместно используемому ресурсу, операции, которая является частью последовательности разблокирования для отказа от монопольного доступа к совместно используемому ресурсу, операции для осуществления доступа к совместно используемому ресурсу, операции для определения, имел ли поток монопольный доступ к совместно используемому ресурсу, и операции сравнения и обмена. Это позволяет накладывать на функциональные возможности для обновления параметра блокировки для потока другую команду для уменьшения количества команд, которые необходимо выполнять.
Совместно используемый ресурс может содержать данные в памяти. Другими примерами совместно используемого ресурса могут быть аппаратное устройство, канал связи или критически важный участок кода.
Процессор может быть выполнен с возможностью выдачи операции барьера памяти в память до отказа от монопольного доступа к совместно используемому ресурсу. Система памяти могут обрабатывать транзакции в порядке, отличающемся от порядка, в котором транзакции принимаются от процессора. Операции барьера памяти могут выдаваться процессором для управления степенью, до которой память может переупорядочивать транзакции. Системе памяти запрещено переупорядочивать операции памяти через барьеры памяти. Таким образом, хотя память может свободно обрабатывать операции между последовательными операциями барьера памяти в любом порядке, при приеме операции барьера памяти память должна обрабатывать все операции памяти, принятые до операции барьера памяти до операций памяти, принятых после операции барьера памяти. Если ни одного барьера памяти не выдано, то существует опасность, что транзакция, выданная после отказа от монопольного доступа к ресурсу, будет обрабатываться системой памяти, несмотря на то, что монопольный доступ все еще удерживается, что может приводить к неправильным значениям данных. Благодаря выдаче операций барьера памяти до отказа от монопольного доступа к совместно используемому ресурсу, система может гарантировать возможность доступа к совместно используемому ресурсу одним-единственным потоком за раз и гарантировать согласованность данных в памяти.
На фиг. 1 показано устройство 100 обработки данных в соответствии с одним вариантом осуществления. Общий программный счетчик 120 устанавливается на один из программных счетчиков 184, связанных с конкретным потоком блоком 110 выбора. Затем значение общего программного счетчика 120 отправляется на блок 130 вызова, который вызывает команду, учитываемую общим программным счетчиком 120. Вызванная команда направляется на блок 140 декодирования, который декодирует команду, и декодированная команда отправляется на блок 150 выдачи. Блок 150 выдачи выдает один или более сигналов на процессор 160 для выполнения вызванной команды для одного или более из потоков. Процессор 160 имеет возможность выполнять команду для одного или более потоков одновременно или, по существу, одновременно. В некоторых вариантах осуществления, процессор 160 может иметь параллельные функциональные блоки для обработки каждого соответствующего потока, благодаря чему, одна и та же команда выполняется параллельно для множественных потоков. Другие системы могут иметь один-единственный функциональный блок, и поэтому одна и та же команда обрабатывается последовательно для каждого из поднабора потоков до перехода к следующей команде. Другие системы могут иметь несколько параллельных блоков, но меньше, чем суммарное количество потоков, благодаря чему, одна и та же команда обрабатывается для нескольких потоков сериями, меньшими, чем суммарное количество потоков.
Процессор 160 также может обращаться к памяти 170, которая может содержать кэш, а также основную память. Процессор также может сообщаются с регистровым файлом 180, в который значения данных могут загружаться или сохраняться. В этом варианте осуществления, регистровый файл 180 содержит несколько разных аппаратных блоков для каждого потока. Например, регистровый файл 180, показанный на фиг. 1, содержит, для каждого потока, набор регистров 182, программный счетчик 184, счетчик 186 глубины вызова функции и счетчик 188 блокировки. Очевидно, что возможны аппаратные конфигурации, отличные от показанных на фиг. 1. Например, единый банк 182 регистров может содержать регистры для более чем одного потока. Кроме того, показанный поднабор аппаратных компонентов может существовать вне регистрового файла 180.
Согласно описанному здесь варианту осуществления, рассматривается один-единственный набор потоков, в котором, параллельно выполняется, по меньшей мере, поднабор этих потоков. Однако очевидно, что устройство 100 обработки данных не ограничивается такой конфигурацией. Например, устройство 100 обработки данных может работать на множественных группах или поднаборах потоков, причем каждая группа потоков способна выполняться, по существу, одновременно. Соответственно, общий программный счетчик 120 может содержать набор общих программных счетчиков, причем каждый общий программный счетчик в наборе относится к отдельной группе потоков. В оставшейся части этого описания рассматривается одна-единственная группа (поднабор) потоков, но очевидно, что описанные методы могут применяться к каждой отдельной группе потоков при наличии множественных групп потоков.
На Фиг. 2 показана единичная группа потоков T#0 - T#31, выполняющих последовательность команд. Поскольку каждый из потоков имеет свои собственные регистры, и поскольку выполняемые команды относятся к регистрам, каждый из потоков могут вести себя по-разному при выполнении одних и тех же команд. Команда 0 предписывает суммирование друг с другом значений данных, удерживаемых в регистре 5 и регистре 3, и сохранение суммы в регистре 0. Команда в строке 1 предписывает переход выполнения потока к 'метке' в строке 3, если предыдущее сложение дает 0. В этом случае, результат сложения, осуществляемого потоком T#2 (0+0), и результат сложения, осуществляемого потоком T#4 (-1+1) равны 0, и, таким образом, управление обработкой для этих двух потоков переходит к 'метке'. Другие потоки не совершают переход, но, вместо этого, переходят к команде в строке 2.
Следовательно, программный счетчик для потоков T#2 и T#4 равен 3, и программный счетчик для остальных потоков равен 2. Для содействия схождения потоков, общий программный счетчик 120 для устройства 100 обработки данных будет устанавливаться на наименьший программный счетчик 184 потока из всех потоков (т.е. 2). Путем выбора значения общего программного счетчика 120, таким образом, потоки, которые не столь развиты, можно заставлять развиваться и, таким образом, догонять другие потоки, таким образом, приводя к схождению потоков. Это состояние, в котором желательно находиться, поскольку затем параллелизм системы повышается, т.е. больше потоков будет выполняться параллельно. Соответственно, общий программный счетчик 120 устанавливается на значение 2, которое является наименьшим значением программного счетчика связанный с любым потоком. Поскольку потоки T#2 и T#4 не имеют программного счетчика потока, равного 2, команда в строке 2 не выполняется для потоков T#2 и T#4. Остальные потоки осуществляют команду в строке 2, которая предписывает перемножать значения данных в регистре 0 и регистре 4 и сохранять произведение в регистре 6. Осуществляя умножение, программный счетчик потока для каждого из потоков, которые выполняют команду, развивается до 3. Соответственно, все потоки имеют один и тот же программный счетчик, и достигается схождение. ʺКомандаʺ в строке 3 является лишь меткой, и поэтому выполнение переходит к строке 4. Эта команда предписывает осуществлять доступ к памяти по адресу, хранящемуся в регистре 9, из основной памяти, и сохранять в регистре 8 значение данных по этому адресу. Как показано на фиг. 2, поскольку каждый из потоков сохраняет отдаленное значение адреса памяти в регистре 9 (например, поток T#0 сохраняет адрес 100 памяти, тогда как поток T#5 сохраняет адрес 200 памяти), каждый из потоков будет обращаться к отдельному адресу памяти и, таким образом, сохранять отдельное значение в их соответствующем регистре 8. Можно объединить обращения к памяти, которые нацеливают одну и ту же строку кэша или одну и ту же страницу памяти на единичного обращение к памяти, для экономии энергии и времени.
На фиг. 3 показан код, выполняющийся в двух потоках, причем код содержит совместно используемый ресурс, управление доступом к которому осуществляется посредством блокировки. При этом доступ к совместно используемому ресурсу осуществляется критически важным участком кода между строками 7 и 9. Совместно используемым ресурсом может быть все, необходимое критически важному участку кода, и для которого требуется монопольный доступ к ресурсу одним потоком за раз. Например, ресурсом может быть совместно используемая структура данных или использование аппаратного блока или устройства. Альтернативно, сам критически важный участок кода может рассматриваться как совместно используемый ресурс. В этом примере, блок 110 выбора выполнен с возможностью установления общего программного счетчика 120 на программный счетчик 184 потока для потока, имеющего наибольший счетчик 186 глубины вызова функции. Когда множественные потоки имеют наибольший счетчик 186 глубины вызова функции, общий программный счетчик 120 устанавливается на наименьший программный счетчик 184 из потоков, имеющих наибольший счетчик 186 глубины вызова функции. Как рассмотрено ранее, желательно, при нормальных условиях, чтобы потоки с наименьшим программным счетчиком могли выполняться в порядке предпочтения потокам с более высоким значением программного счетчика, чтобы обуславливать схождение потоков. Однако, как будет показано, этот механизм выбора программного счетчика обуславливает возникновение взаимоблокировки при наличии критически важного участка кода.
Несколько команд, показанных на фиг. 3, обращается к адресу в регистре x19. Этот адрес может соответствовать значению данных, указывающему, заблокирован ли потоком монопольный доступ к совместно используемому ресурсу. В этом примере, когда значение по адресу, указанному регистром x19, равно 0, это указывает, что не установлено никакой блокировки для ресурса, используемого критически важным участком кода в строках 7-9, и когда значение по этому адресу равно 1, блокировка установлена. Однако очевидно, что возможны другие пути представления, предоставлен ли монопольный доступ к ресурсу. Заметим, что когда потоки выполняют этот пример кода, разные потоки, выполняющие команды в строках 2 и 5, могут осуществлять доступ к разным версиям регистра x19 в соответствующих им наборах 182 регистров, которые могут содержать разные адреса памяти. Следовательно, совместно используемые ресурсы, доступа к которым ищут потоки могут различаться между потоками. С другой стороны, если существуют множественные потоки, для которых регистр x19 содержит один и тот же адрес, то возможен конфликт, как рассмотрено ниже.
Прежде всего, все потоки будут выполняться в жесткой конфигурации. Строка 0 содержит метку и, таким образом, не влияет на выполнение. Строка 1 предписывает сохранять значение данных 1 в регистре w1. Команда в строке 2 называется исключающей команде загрузки. Это обуславливает доступ к значению данных и установление монитора. Монитор обнаруживает, изменяется ли значение данных. Поэтому, в этом примере, осуществляется доступ к значению данных, сохраненному в адресе памяти, указанном в регистре x19, это значение сохраняется в регистре w0, и для этого адреса памяти устанавливается монитор. В строке 3, значение данных, сохраненное в регистре w0, сравнивается с числом 0. Другими словами, помимо установления монитора, строки 2 и 3 совместно определяют, равны ли 0 значения данных, сохраненные в адресе памяти, указанном в регистре x19. Команда в строке 4 предписывает выполнение перехода к метке retry_lock в строке 0, если значения данных не равны. Другими словами, если значение данных, сохраненное в регистре w0, не равно 0 (т.е. другой поток уже имеет блокировку на совместно используемом ресурсе), то управление обработкой возвращается к метке retry_lock, в противном случае, управление обработкой переходит к строке 5. Следовательно, команды в строках 2-4 проверяют, имел ли другой поток блокировку к моменту выполнения загрузки команда в строке 2.
С другой стороны, команды в строках 5-6 проверяют, получил ли блокировку другой поток в некоторый момент после выполнения исключающей команды загрузки в строке 2, но до начала критически важного участка кода. Это гарантирует, что множественные потоки не могут одновременно получить блокировку. Строка 5 является исключающей командой сохранения, которая предписывает сохранение значения данных, только если ранее установленный монитор указывает, что наблюдаемый адрес памяти не изменился. В этом примере, команда предписывает сохранение значения данных, хранящегося в регистре w1 (т.е. 1) в ячейке памяти, указанной регистром x19, только если значение данных, сохраненное в адресе памяти, указанном регистром x19, не изменилось, поскольку монитор был установлен исключающей командой загрузки в строке 2. Затем результат успешного или неуспешного сохранения сохраняется в регистре w2. В частности, если сохранение было успешным, то в w2 сохраняется значение 0. В противном случае, если сохранение было неуспешным, в w2 сохраняется ненулевое значение. Конечно, специалисту в данной области техники очевидно, что конкретное число, используемое для указания успеха или неудачи, играет важную роль, и что эти числа легко можно инвертировать. Поскольку операция сохранения осуществляется только, если другой поток не изменил значение данных, сохраненное в адресе, указанном регистром x19, если значение регистра x19 одинаково для всех потоков, то в точности один поток изменит значение данных. Если разные потоки требуют разных заблокированных ресурсов, то разные адреса можно помещать в регистре x19 для разных потоков, поэтому для более чем одного потока может успешно выполняться команда сохранения в строке 5. Поэтому результат исключающей команды сохранения для каждого потока указывает, получил ли этот поток блокировку. В строке 6, сравнение производится для определения, равно ли значение данных, сохраненное в регистре w2, 0 (т.е. была ли исключающая команда сохранения неуспешной). управление обработкой возвращается к метке retry_lock в строке 0, если значение данных, сохраненное в w2, не равно 0. В противном случае, процесс переходит к строке 7.
Строки 7-9 (не показанные на фиг. 3) представляют критически важный участок. Таким образом, на основании предыдущей последовательности блокирования, критически важный участок может выполняться только одним потоком для каждого совместно используемого ресурса за раз (множественные потоки могут выполнять критически важный участок, если они используют разные ресурсы). Поток должен заканчивать выполнение кода на критически важном участке, до поступления другого потока, требующего того же ресурса. Критически важный участок может включать в себя любые команды, использующие совместно используемый ресурс, например, команды загрузки/сохранения, обращающиеся к совместно используемой ячейке или совместно используемой структурой данных, монопольный доступ к которой требуется для поддержания согласованности данных, или команды, которые исполняются на аппаратном устройстве, которые могут использоваться только одним потоком за раз.
Последовательность разблокирования показана, начиная со строки 10. Этот код выполняется после выполнения критически важного участка. В строке 10, значение данных 0 сохраняется в регистре w1. В строке 11, значение данных, сохраненное в регистре w1 (т.е. 0), сохраняется в ячейке памяти, указанной в регистре x19, для указания, что этот поток больше не имеет блокировки. Это означает, что другой поток, достигающий команд в строках 2-4, теперь может успешно получить блокировку.
Как упомянуто выше, этот код для предоставления блокировки критически важному участку может приводить к возникновению взаимоблокировки в устройстве обработки данных SIMT, если множественные потоки пытаются получить такую же блокировку (т.е. одни и те же ячейки памяти указаны в соответствующих версиях регистра x19 в банках 182 регистров для разных потоков). Например, как показано на фиг. 3, поток T#0 может быть потоком, который получает доступ к блокировке, и, таким образом, переходит к строке 7 кода. Однако потоку T#1 (и другим потокам, нацеленным на один и тот же ресурс) не удастся получить блокировку. Соответственно, при первом выполнении кода, потоки, отличные от потока T#0, будут выполняться вплоть до строки 6 кода, до того, как неудача в получении блокировки приведет к возврату их управления обработкой к строке 0. Для последующих попыток, потоки, отличные от потока T#0, могут выполняться вплоть до строки 4, поскольку поток T#0 теперь сохраняет значение #1 по адресу, указанному в регистре x19. Все потоки имеют одно и то же значение счетчика глубины вызова функции, равное 1. Поэтому блок 110 выбора будет устанавливать общий программный счетчик 120 на наименьший программный счетчик 184 потока, связанный с каждый из потоков. Все потоки, отличные от потока T#0, имеют значение программного счетчика, равное 0, и поэтому значение общего программного счетчика 120 будет устанавливаться равным 0. Соответственно, будет разрешено выполнение потоков, отличных от потока T#0. Однако потоки, которым все же не удается получить блокировку критически важного участка, поскольку блокировка удерживается T#0. Поэтому в строке 4 управление обработкой для этих потоков будет переходить к строке 0. Опять же, когда выбор значения программного счетчика производится блоком 110 выбора, потоки, отличные от потока T#0 имеют значение программного счетчика (0), которое ниже, чем у потока T#0 (7). Соответственно, значение общего программного счетчика 120 будет устанавливаться равным 0, и будет разрешено выполнение потоков, отличных от потока T#0. Этот процесс будет продолжаться, возможно, всегда. Только поток T#0 способен разблокировать доступ к критически важному участку, и поток T#0 может разблокировать доступ только к критически важному участку после выполнения критически важного участка. Однако поток T#0 не способен выполнять критически важный участок, поскольку его значение программного счетчика выше, чем у других потоков, и поэтому общий программный счетчик 120 никогда не будет устанавливаться на программный счетчик 184 потока, связанный с потоком T#0. Поэтому, в этом примере, происходит взаимоблокировка. Ни один поток не может развиваться, и поэтому система останавливается.
На фиг. 4 показано решение этой проблемы взаимоблокировки. В этом варианте осуществления, счетчик 188 блокировки предусмотрен для каждого потока, и блок 110 выбора выполнен с возможностью выбора выбранного потока (программный счетчик потока которого устанавливается на общий программный счетчик) на основании счетчика блокировки помимо глубины вызова функции и программного счетчика потока. Общий программный счетчик 120 устанавливается на программный счетчик 184 потока, связанный с потоком, имеющим наибольший счетчик 188 блокировки. Если множественные потоки имеют наибольший счетчик 188 блокировки, то рассматриваются потоки, имеющие наибольший счетчик 186 глубины вызова функции из потоков, имеющих наибольший счетчик 188 блокировки. Если множественные потоки имеют наибольший счетчик 188 блокировки и наибольший счетчик 186 глубины вызова функции, то выбирается поток, имеющий наименьшее значение программного счетчика из этих потоков. Затем общий программный счетчик обновляется на основании программного счетчика потока выбранных потоков, и затем команда, указанная общим программным счетчиком, может выполняться для любых потоков с совпадающими параметрами потока (по меньшей мере, совпадающим программным счетчиком потока и, в необязательном порядке, также совпадающими глубиной вызова функции и параметром блокировки). Очевидно, что в других вариантах осуществления может применяться другой механизм, где конкретный программный счетчик потока или конкретная комбинация программного счетчика потока, параметра вызова функции и параметра блокировки выбирается напрямую (вместо выбора потока).
На фиг. 4 показан такой же код, как на фиг. 3 с добавлением двух новых команд в строках 6 и 12 соответственно. Эти команды предписывают условное увеличение и уменьшение счетчика 188 блокировки, связанного с потоком. В частности, команда 'cond_inc_lock_count w2' в строке 6 предписывает увеличение счетчика 188 блокировки связанный с потоком, если значение w2 равно нулю. Как объяснено со ссылкой на фиг. 3, значение w2 устанавливается равным 0 или 1, причем значение 0 представляет успешное завершение команды STXR (т.е. успешное получение блокировки потоком), и 1 представляет неудачное завершение команды STXR (т.е. потоку не удалось получить блокировку). Соответственно, команда в строке 6 предписывает увеличение счетчика 188 блокировки для конкретного потока, если этому потоку было предписано получить блокировку в предыдущей команде в строке 5. Команда 'dec_lock_count' в строке 12 уменьшает счетчик 188 блокировки для конкретного потока. Эта команда является безусловной. Таким образом, поскольку код в строках 8-12 выполняется только одним потоком за раз - в частности, потоком, который в данный момент удерживает блокировку и, таким образом, имеет доступ к критически важному участку. Следовательно, отсутствует неопределенность в отношении того, счетчик блокировки какого потока нужно уменьшить.
При выполнении кода, в результате команды в строке 6, счетчик блокировки потока, который получает блокировку (T#0), увеличивается. Напротив, счетчики блокировки других потоков не увеличиваются, поскольку их значение регистра w2 не равно нулю (им не удалось получить блокировку). В строке 7, поток T#0 переходит к строке 8, тогда как остальные потоки возвращаются к метке 'retry_lock' в строке 0. Как объяснено выше, в этом варианте осуществления блок 110 выбора выполнен с возможностью установления общего программного счетчика 120 на программный счетчик потока, имеющего наибольший счетчик блокировки. Соответственно, когда программный счетчик потока T#0 равен 8, этот поток способен продолжать выполнение на основании своего более высокого счетчика 188 блокировки, хотя его программный счетчик 182 выше, чем у других потоков. Поэтому поток T#0 способен продолжать выполнение и, в итоге, выполнить код последовательности разблокирования в строках 10-11, который снимает блокировку. Затем поток T#0 переходит к строке 12, где его счетчик блокировки уменьшается. В этот момент, счетчик блокировки каждого из потоков равен 0, глубина вызова функции каждого из потоков равна 1, и поэтому общий программный счетчик 120 устанавливается на наименьший программный счетчик 184 потока из всех потоков. Соответственно, потокам, отличным от потока T#0, разрешено выполняться, и они выполняют код между строками 0 и 7. В ходе этого выполнения, один из потоков получает блокировку, и его счетчик 188 блокировки увеличивается, как описано ранее. Эта последовательность будет выполняться, пока все потоки не пройдут критически важный участок кода. Соответственно, это позволяет избегать ситуации взаимоблокировки несмотря на присутствие критически важного участка кода.
В примере, приведенном на фиг. 4, команды cond_inc_lock_count и dec_lock_count влияют только на счетчик 188 блокировки, связанный с конкретным потоком. Однако очевидно, что эти команды могут осуществлять дополнительные операции. Например, команда условного увеличения может сочетаться либо с исключающей командой сохранения в строке 5, либо с командой сравнения и перехода в строке 7. В подобных случаях, команда условного увеличения осуществляется до или параллельно с операциями, относящимися к команде сравнения и перехода, и после операций, относящихся к исключающей команде сохранения. Аналогично, команда уменьшения счетчика блокировки может сочетаться с другими операциями. Например, команда уменьшения счетчика блокировки может сочетаться с командой, которая сохраняет численное значение 0 в адресе, указанном регистром x19.
Последовательность блокирования также можно осуществлять по-разному. В примере, приведенном на фиг. 4, используется комбинация исключающей команды загрузки в строке 2 и исключающей команды сохранения в строке 5. Механизм блокирования также может осуществляться путем использования команды сравнения и обмена (CMPXCHG). Команда сравнения и обмена является элементарным примитивом. Другими словами, команда не может прерываться в ходе выполнения, но, напротив, будучи запущенной, выполняется до завершения. Команда сравнения и обмена имеет три параметра. Одним из параметров является ячейка памяти. Дополнительным параметром является сравнительное значение, и еще одним параметром является сохраненное значение. Команда сравнения и обмена проверяет, равно ли значение данных в ячейке памяти сравнительному значению, и если да, записывает сохраненное значение в ячейку памяти и возвращает результат, указывающий, что операция увенчалась успехом. Если значение данных в ячейке памяти не равно сравнительному значению, в ячейку памяти ничего не записывается (в ячейке памяти остается начальное значение) и результат, напротив, указывает, что операция закончилась неудачей. Опять же, такая команда сравнения и обмена может сочетаться с другими операциями и может сочетаться с командой cond_inc_lock_count.
Операция барьера памяти может осуществляться до команды dec_lock_count и после критически важного участка в коде. В устройстве обработки данных, команды доступа к памяти можно переупорядочивать для эффективности. Однако такое переупорядочение не может происходить через барьер памяти. Следовательно, барьер памяти может помогать гарантировать, что операции доступа к памяти, которые являются частью критически важного участка кода, обрабатываются до операций доступа к памяти, которое были выданы по завершении критически важного участка.
Каждую из команды cond_inc_lock_count и команды dec_lock_count можно кодировать таким образом, что в заранее определенном наборе команд, кодирование команды cond_inc_lock_count и команды dec_lock_count соответствует команде NOOP. Например, набор команд, используемый устройством 100 обработки данных, может быть расширенной версией набора команд, который кодирует эти две команды как команды NOOP. Следовательно, на устройстве обработки данных, отличном от устройства 100 обработки данных, две команды могут не иметь никакого действия. Соответственно, код, предназначенный для использования с устройством 100 обработки данных, может быть обратно совместимым с другими устройствами обработки данных и может быть обратно совместимым с устройством обработки данных, которое не использует SIMT.
Фиг. 5 иллюстрирует способ выбора выбранного потока, программный счетчик потока которого используется в качестве общего программного счетчика 120. Способ начинается на этапе s200, на котором первый набор и второй набор устанавливаются как пустые. На этапе s205 выбирается следующий поток из всех потоков. Этот этап совместно с этапами s210, s215 и s220 совместно образуют цикл, который повторяется для всех потоков. На этапе s210 производится определение, равен ли параметр блокировки (т.е. счетчик 188 блокировки) потока, выбранный на этапе s205, наибольшему параметру блокировки всех потоков. Если параметр блокировки этого потока равен наибольшему параметру блокировки всех потоков, то процесс переходит к этапу s215, в противном случае процесс переходит к этапу s220. На этапе s210 предполагается, что устройству обработки данных известен наибольший параметр блокировки всех потоков. Если эта информация не является легкодоступной, ее можно определить, сначала перебирая все потоки, или сохраняя действующий счетчик наибольшего параметра блокировки, наблюдаемого из предыдущих потоков и отбрасывая потоки, уже добавленные в первый набор, когда встречается параметр блокировки, более высокий, чем предыдущий наибольший параметр блокировки. На этапе s215, выбранный поток добавляется в первый набор, и затем процесс переходит к этапу s220. На этапе s220, производится определение, существуют ли дополнительные перебираемые потоки. Если дополнительные потоки существуют, то процесс возвращается к этапу s205, на котором выбирается следующий поток. Если дополнительных потоков не существует, то процесс переходит к этапу s225. Следовательно, по окончании этапа s220 определяется первый набор потоков, который содержит потоки, имеющие параметр блокировки, равный более высокому параметру блокировки любого из потоков. На этап s225 производится определение, существует ли в первом наборе в точности один элемент. При наличии в точности одного элемента в первом наборе процесс переходит к этапу s230, где элемент в первом наборе возвращается в качестве выбранного потока. Таким образом, общий программный счетчик 120 устанавливается на программный счетчик 184 потока, связанный только с потоком в первом наборе. Если на этапе s225 установлено, что в первом наборе не существует в точности один элемент, то процесс переходит к этапу s235. Совместно, этапы s205 - s230 пытаются обосновать решение по выбору программного счетчика потока на параметре счетчика блокировки всех потоков. Если один из потоков имеет более высокий параметр счетчика блокировки, чем все остальные потоки, то этот поток является выбранным потоком, и общий программный счетчик 120 устанавливается на программный счетчик 184 потока, соответствующий потоку, имеющему более высокий параметр счетчика 188 блокировки. В противном случае, дополнительное сужение потоков осуществляется, как объяснено ниже.
На этапе s235 выбирается следующий поток из первого набора. Этапы s235 - s250 совместно образуют цикл, который повторяется для всех потоков в первом наборе. На этапе s240 производится определение, равна ли глубина вызова функции выбранного потока наибольшей глубине вызова функции всех потоков в первом наборе. Опять же, предполагается, что можно определить наибольшую глубину вызова функции всех потоков в первом наборе. Один способ определения этой информации предусматривает сначала перебор всех потоков в первом наборе, или поддержание значения действующего счетчика, как рассмотрено выше. Если на этапе s240 установлено, что глубина вызова функции выбранного потока равна наибольшей глубине вызова функции всех потоков в первом наборе, то процесс переходит к этапу s245. В противном случае, процесс переходит к этапу s250. На этапе s245, выбранный поток добавляется ко второму набору, и процесс переходит к этапу s250. На этапе s250, производится определение, существуют ли в первом наборе дополнительные потоки для перебора. Если в первом наборе существуют дополнительные потоки, то процесс возвращается к этапу s235 для продолжения цикла. В противном случае, процесс переходит к этапу s255, где производится определение, присутствует ли во втором наборе в точности один элемент. В случае определения на этапе s255 наличия в точности одного элемента во втором наборе, процесс переходит к этапу s260. На этапе s260 единичный элемент во втором наборе возвращается в качестве выбранного потока. Другими словами, общий программный счетчик 120 устанавливается на программный счетчик 184 потока, связанный с единичным потоком во втором наборе. Такая ситуация может возникать, например, если более одного потока совместно используют наибольший параметр счетчика 188 блокировки, но если только один из этих потоков имеет наибольший счетчик 186 глубины вызова функции. Соответственно, такому потоку разрешается выполняться путем установления общего программного счетчика 120 на программный счетчик 184 потока, связанный с этим потоком. Совместно, этапы s235 - s260 относятся ко второму критерию, который используется для определения общего программного счетчика 120.
При наличии не в точности одного элемента во втором наборе, то процесс переходит к этапу s265, где элемент во втором наборе с наименьшим программным счетчиком 184 возвращается в качестве выбранного потока. Другими словами, общий программный счетчик 120 устанавливается на наименьший из программных счетчиков 184 потока из всех потоков во втором наборе. Таким образом, этап s265 обеспечивает третий критерий для определения общего программного счетчика 120.
На фиг. 6 показано, как выбираются потоки, подлежащие выполнению в каждом цикле. На этапе s400 один из множества потоков (или, эквивалентно, один из программных счетчиков потока, соответствующих потокам) выбирается на основании параметров 188 блокировки (счетчиков блокировки), счетчиков 186 глубины функционального вызова и программных счетчиков 184 потока. Пример этого процесса показан со ссылкой на фиг. 5. На этапе s410 общий программный счетчик 120 устанавливается на программный счетчик потока для выбранного потока. Другими словами, общий программный счетчик 120 устанавливается совпадающим с программным счетчиком 184 потока, соответствующим потоку, выбранному на этапе s400. Окончательно, на этапе s420, команда, которая идентифицируется общим программным счетчиком 120 выполняется для всех потоков, параметры потока, связанные с которыми, совпадают с параметрами потока для выбранного потока (параметры потока могут содержать только программный счетчик 184 потока или может содержать комбинацию программного счетчика потока с одним или обоих из счетчика 188 блокировки и глубины 186 вызова функции). Этот процесс может приводить к изменению программного счетчика 184 потока, связанный с каждым потоком, и, соответственно, процесс может затем повторяться, начиная с этапа s400, предписывающего определять другое значение общего программного счетчика 120.
В примере, рассмотренном со ссылкой на фиг. 4, процессор оптимистически пытается получить блокировки для всех потоков в группе потоков и затем отсортировать порядок предпочтительного выполнения на основании того, какие потоки были способны получить блокировки.
Второй вариант осуществления описан со ссылкой на фиг. 7-9. В этом варианте осуществления, только одному потоку в группе разрешено удерживает блокировку каждый раз. Также, в то время как на фиг. 4 процессор оптимистически пытается получить блокировки для всех потоков с использованием последовательности блокирования, включающей в себя команду STXR, и затем только в случае успеха увеличивает счетчик блокировки для указания, что поток получил привилегию блокирования, на фиг. 7-9 порядок инвертируется, благодаря чему, сначала выполняется команда для запрашивания привилегии блокирования и обновления параметра блокировки, соответственно. В этот момент, процессор гарантирует, что только один поток может успешно выполнять команду, запрашивающую привилегию блокирования (для других потоков, выполнить эту команду не удается, и поэтому программный счетчик потока для этого потока не увеличивается). Получив привилегию блокирования, поток, который был успешен, затем выполняет последовательность блокирования для получения блокировки. Таким образом, только одному потоку в группе разрешено удерживать блокировки в любой момент времени. Последовательность разблокирования по-прежнему такая же, как на фиг. 4 - сначала снимают блокировку, затем отменяют привилегию блокирования. Блокировки можно запрашивать несколько раз в единичном потоке, удерживая при этом блокировку, и количество блокировок, удерживаемых потоком, может отслеживаться с использованием счетчика блокировки. Хотя второй вариант осуществления можно реализовать таким же образом, как первый вариант осуществления со счетчиком блокировки для каждого потока и механизмом выбора программного счетчика, который предпочитает более высокие счетчики блокировки, поскольку привилегия блокирования (предпочтение выполнения) отдается каждый раз одному потоку для каждой группы, эту схему можно упростить, просто сохраняя для группы в целом единичного указания, имеет ли какой-либо поток в группе привилегию блокирования, идентификацию этого потока и единичный счетчик блокировки для группы.
Таким образом, на фиг. 7 показан пример регистрового файла 180 и данных состояния для использования в этом втором варианте осуществления. Фиг. 7 отличается от регистрового файла на фиг. 1 тем, что счетчик 188 блокировки не обеспечен для каждого потока. Альтернативно, помимо общего программного счетчика 120 для группы потоков, несколько параметров блокировки совместно используется группой потоков:
- флаг 500 установки блокировки, указывающий, заблокирован ли какой-либо поток в группе для одного или более совместно используемых ресурсов;
- параметр 502 владельца блокировки, указывающий, какой поток из группы заблокировал один или более совместно используемых ресурсов; и
- параметр 504 счетчика блокировки, указывающий, сколько ресурсов заблокировано потоком, владеющим блокировкой, указанным параметром 502 владельца блокировки.
В некоторых примерах, флаг 500 установки блокировки может быть исключен и, альтернативно, параметр 502 владельца блокировки или параметр 504 счетчика блокировки можно использовать для указания, удерживает ли поток блокировку. Например, если параметр 504 счетчика блокировки равен нулю, то это может указывать, что ни один поток не удерживает блокировку, и если параметр 504 счетчика блокировки имеет ненулевое значение, то это может указывать, что поток удерживает блокировку. Альтернативно, параметр 502 владельца блокировки может иметь значение, соответствующее одному из потоков, если этот поток удерживает блокировку, и иметь значение, которое не соответствует никакому из потоков, если ни один поток не удерживает блокировку, поэтому это может эффективно указывать, установлена ли какая-либо блокировка. Однако иногда может быть полезно обеспечивать отдельный флаг 500 установки блокировки, который указывает, установлена ли какая-либо блокировка, например, поскольку флаг 500 установки блокировки может содержать единичный бит, который быстрее и легче проверять, чем многобитовые значения, соответствующий параметру 502 владельца блокировки или значению 504 счетчика блокировки.
На фиг. 8 показан следующий пример кода для второго варианта осуществления:
строка 0: метка, представляющая начало последовательности блокирования, которая не предписывает никакого конкретного действия на процессоре
строка 1: inc_lock_count является командой для запрашивания привилегии блокирования (право потока устанавливать одну или более блокировок ресурсов). Эта команда может успешно выполняться только для одного потока в группе. Следовательно, после этой команды один поток может переходить к следующей команде (при этом программный счетчик этого потока увеличивается к следующей команде), тогда как другим потокам эта команда не удается (и поэтому их программные счетчики потока остаются на той же команде inc_lock_count, пока они не смогут успешно выполнять ее). Если inc_lock_count успешно выполняется, установить флаг 500 установки блокировки для указания, что поток удерживает привилегию блокирования, установить параметр 502 владельца блокировки для указания идентификатора текущего потока, и увеличить счетчик 504 блокировки.
Строка 2: метка retry_lock для перехода к, если поток с привилегией блокирования не смог получить блокировку
строки 3-5: такие же, как строки 1-3 на фиг. 4, для проверки, получил ли уже другой процесс (например, поток вне текущей группы потоков или процесс, выполняющийся на другом процессоре, например, в многопроцессорной системе) блокировку для ресурса, идентифицированного адресом в регистре x19.
Строка 6: условный переход для перехода к ʺоткатуʺ последовательности в строках 10-12 в случае, когда другой процесс удерживает блокировку для адреса, идентифицированного в x19.
Строки 7-8: такие же, как строки 5 и 7 на фиг. 4. Исключающая команда сохранения для установления блокировки для адреса в регистре x19, и условный переход для перехода назад к строке 2, если исключающую команду сохранения не удается выполнить. В отличие от строки 6 на фиг. 4, отсутствует условная команда для увеличения счетчика блокировки, если блокировка успешно получена, поскольку на фиг. 8 счетчик блокировки уже увеличивается в строке 1.
Строка 9: если блокировка успешно получена, переход к строке 13, чтобы сделать что-то с использованием заблокированного ресурса.
Строка 10: метка ʺbackoff_lockʺ, представляющая начало последовательности отката для отказа от привилегии блокирования, если блокировка для ресурса, идентифицированного адресом в регистре x19, уже установлена. Благодаря отказу от привилегии блокирования, другой поток, который может иметь другой адрес в его версии регистра x19, имеют возможность успешно получать свою блокировку и развиваться.
Строка 11: уменьшение счетчика 504 блокировки. Если это приводит к обнулению счетчика 504 блокировки, также очистка флага 500 установки блокировки, благодаря чему, другой поток может получать привилегию блокирования. После строки 11, поток может ждать некоторое время, чтобы выиграть время для другого потока в той же группе для окончания своей обработки с использованием блокировки и освободить блокировку.
Строка 12: переход обратно к началу последовательности блокирования в строке 0 в попытке снова получить блокировку.
Строка 13: метка ʺlock_acquiredʺ, представляющая начало последовательности, выполняемой в случае успешного получения блокировки. После этого, любое количество команд может выполняться с использованием заблокированного ресурса.
Строка 14: по завершении обработки с использованием заблокированного ресурса, начать последовательность разблокирования
строки 15-17: такие же, как строки 10-12 на фиг. 4 для отказа от блокировки, за исключением того, что в этом случае, если команда dec_lock_count выполняется, и это приводит к обнулению счетчика 504 блокировки, то флаг 500 установки блокировки очищается.
Следовательно, согласно этому примеру, только один поток в одной и той же группе потоков может удерживать блокировку за раз, для обеспечения дополнительной защиты от взаимоблокировки.
На фиг. 9 показан способ выбора выбранного потока (и, таким образом, какой программный счетчик потока устанавливать на общий программный счетчик для группы потоков) при использовании второго варианта осуществления. Поскольку только один поток в группе может удерживать блокировки за раз, начальная часть процесса выбора программного счетчика упрощается. На этапе 600, блок 110 выбора определяет, указывает ли флаг 500 установки блокировки, удерживает ли какой-либо поток в группе блокировку. Если да, то на этапе 602 блок 110 выбора выбирает поток, указанный параметром 502 владельца блокировки в качестве выбранного потока.
С другой стороны, если флаг 500 установки блокировки указывает, что ни один поток в группе в данный момент не удерживает блокировку, то на этапе 604 все потоки из группы (поднабора) рассматриваются как часть ʺпервого набораʺ потоков. Затем способ переходит к этапу S225, показанный на фиг. 5, и после этого способ продолжается таким же образом, как на фиг. 5, для выбора выбранного потока на основании глубины вызова функции и программного счетчика потока.
После выбора выбранного потока, этапы S410 и S420, показанные на фиг. 6, могут применяться, как прежде.
В настоящей заявке, слова ʺвыполненный с возможностью …ʺ используются в том смысле, что элемент устройства имеет конфигурацию, способную осуществлять заданную операцию. В этом контексте, ʺконфигурацияʺ означает компоновку или организацию взаимосвязи оборудования или программного обеспечения. Например, устройство может иметь специализированное оборудование, которое обеспечивает заданную операцию, или процессор или другое устройство обработки может быть запрограммировано для осуществления функции. ʺВыполненный с возможностьюʺ не предполагает, что элемент устройства не нужно изменять никаким образом для обеспечения заданной операции.
Хотя иллюстративные варианты осуществления изобретения были описаны в настоящем документе подробно со ссылкой на прилагаемые чертежи, следует понимать, что изобретение не ограничивается этими конкретными вариантами осуществления, и что различные изменения и модификации могут быть осуществлены в них специалистом в данной области техники, без отклонения от объема и сущности изобретения, которая задана нижеследующей формулой изобретения.