Наборы планируемых заданий в планировщике

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

 

Уровень техники

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

Сущность изобретения

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

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

Краткое описание чертежей

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

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

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

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

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

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

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

Подробное описание

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

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

Фиг.1 - блок-схема, иллюстрирующая вариант осуществления планировщика контекста выполнения 22 в процессе 12 рабочей среды 10. Планировщик 22 содержит совокупность наборов планируемых заданий 40(1)-40(L), где L - целое число, которое больше или равно двум и обозначает L-й набор планируемых заданий 40. Каждый набор планируемых заданий 40(1)-40(L) соответствует соответствующему узлу планирования 30(1)-30(L).

Рабочая среда 10 представляет собой режим выполнения программ в вычислительной системе, такой как варианты осуществления 100А и 100В вычислительной системы 100, изображенной на Фиг.6А и 6В и описанной ниже более подробно, в котором вычислительная система выполняет команды. Вычислительная система формирует рабочую среду 10 из платформы выполнения, такой как платформа выполнения 122, изображенная на Фиг.6А и описанная ниже более подробно.

Рабочая среда 10 включает, по меньшей мере, один вызываемый процесс 12, уровень управления ресурсами 14 и совокупность аппаратных потоков 16(1)-16(М), где М - целое число, которое больше или равно двум и обозначает М-й аппаратный поток 16. Рабочая среда 10 позволяет осуществлять выполнение заданий процесса 12 вместе с заданиями других процессов, которые существуют одновременно с процессом 12 (не показан), с помощью уровня управления ресурсами 14 и совокупности аппаратных потоков 16(1)-16(М). Рабочая среда 10 функционирует во взаимодействии с уровнем управления ресурсами 14, чтобы процесс 12 мог получить ресурсы процессора и прочие ресурсы вычислительной системы (например, аппаратные потоки 16(1)-16(М)).

Рабочая среда 10 включает в себя функцию планировщика, которая формирует планировщик 22. В одном варианте осуществления функция планировщика реализована в виде прикладного программного интерфейса (API) планировщика. В другом варианте осуществления функция планировщика может быть реализована с помощью других подходящих программных структур. При вызове функция планировщика создает планировщик 22 в процессе 12, при этом планировщик 22 производит операции по планированию заданий процесса 12 для выполнения одним или более аппаратных потоков 16(1)-16(М). Рабочая среда 10 может использовать мелкомодульный параллелизм, который разработки приложений или библиотек отражают в своих программах (например, процесс 12) с помощью сопутствующих инструментальных средств, которые знают о возможностях, обеспечиваемых функцией планировщика.

Процесс 12 включает распределение ресурсов обработки и прочих ресурсов, которые ведут один или более контекстов выполнения (а именно, потоков). Процесс 12 получает доступ к обработке и прочим ресурсам вычислительной системы (например, к аппаратным потокам 16(1)-16(М)) от уровня управления ресурсами 14. Процесс 12 обеспечивает выполнение заданий с помощью ресурсов обработки и прочих ресурсов.

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

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

Уровень управления ресурсами 14 выделяет ресурсы обработки на процесс 12 путем выделения одного или более аппаратных потоков 16 на процесс 12. Уровень управления ресурсами 14 существует отдельно от операционной системы вычислительной системы (на Фиг.1 не показана) в изображенном на Фиг.1 варианте осуществления. В других вариантах осуществления уровень управления ресурсами 14 либо некоторые или все их функции могут входить в операционную систему.

Аппаратные потоки 16 находятся в исполнительных модулях совокупности либо одного, либо более блоков процессора (например, блоков процессоров 102, показанных на Фиг.6 и описанных ниже более подробно) вычислительной системы. Каждый аппаратный поток 16 настроен на выполнение команд независимо или практически независимо от других исполнительных модулей и включает в себя состояние машины. Аппаратные потоки 16 могут входить в один блок процессора или могут быть распределены по множеству блоков процессоров. Каждый исполнительный модуль в блоке процессора может содержать один или более аппаратных потоков 16.

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

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

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

Рабочая среда 10 создает планировщик 22 с информацией о лежащей в его основе топологии вычислительной системы. Рабочая среда 10 выдает на уровень управления ресурсами 14 и/или планировщик 22 информацию об узле вычислительной системы. Информация об узле выявляет аппаратные узлы вычислительной системы непосредственно либо включает достаточную информацию о топологии вычислительной системы, чтобы уровень управления ресурсами 14 и/или планировщик 22 могли осуществлять разбиение аппаратных ресурсов на узлы планирования 30 на основе одного или более показателей выполнения. Показатели выполнения могут содержать скорость, тип и/или конфигурацию ресурсов обработки (например, аппаратных потоков 16), ресурсы памяти и/или прочие ресурсы вычислительной системы.

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

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

Рабочая среда 10 обеспечивает включение планировщиком 22 совокупности двух или более узлов планирования 30(1)-30(L) на основе информации об узлах. Каждый узел планирования 30 включает выделенные ресурсы обработки в виде виртуальных процессоров 32 и аппаратных потоков 16. Узел планирования 30(1) включает виртуальные процессоры 30(1)-30(N _l), которые преобразуются в аппаратные потоки 16(1)-16(m _l), где N _l - целое число, которое больше или равно единице и означает (N _l)-й виртуальный процессор 30, а m _l - меньше или равно М и означает (m _l)-й аппаратный поток 16. Узел планирования 30(L) включает виртуальные процессоры 30(l)-30(N _L), которые преобразуются в аппаратные потоки 16(m _m)-16(M), где N _L - целое число, которое больше или равно единице и означает (N _L)-й виртуальный процессор 30, а m _m - меньше или равно М и больше m _l и означает (m _m)-й аппаратный поток 16.

Планировщик 22 создает набор планируемых заданий 40 для каждого узла планирования 30. В соответствии с этим наборы планируемых заданий 40(1)-40(L) должны соответствовать соответствующим узлам планирования 30(1)-30(L), как показано стрелками 37(1)-37(L). Планировщик 22 преобразует наборы планируемых заданий 40 в очередность полного или частичного поиска на основе одного или более показателей выполнения и использует указанную очередность поиска для поиска заданий для выполнения при освобождении ресурсов обработки, как будет описано ниже более подробно.

Совокупность контекстов выполнения в планировщике 22 содержит совокупность контекстов выполнения 34 с соответствующими связанными с ними заданиями 36, которые выполняются соответствующими виртуальными процессорами 32 в каждом узле планирования 30, а в каждом наборе планируемых заданий 40 - совокупность нуля или более готовых к выполнению контекстов выполнения 38 и совокупность нуля или более заблокированных (т.е. зависимых от ожидания) контекстов выполнения 40. Каждый контекст выполнения 34, 38 и 40 содержит информацию о состоянии, которая указывает на то, является ли контекст ожидания 34, 38 и 40 выполняющимся, готовым к выполнению (например, в ответ на разблокирование или добавление в планировщик 22) или заблокированным. Контексты выполнения 34, которые являются выполняющимися, присоединены к виртуальному процессору 32 и в настоящее время выполняются. Контексты выполнения 38, которые являются готовыми к выполнению, содержат сопряженное задание 39 и готовы к выполнению свободным виртуальным процессором 32. Контексты выполнения 40, которые заблокированы, содержат сопряженное задание 41 и ожидают данные, сообщение или событие, которое сформировано или будет сформировано другим контекстом выполнения 34, 38 или 40.

Каждый контекст выполнения 24, выполняющийся на виртуальном процессоре 32, в процессе своего выполнения может формировать дополнительные задания 42, которые организуются любым целесообразным способом (например, добавляются к очередям работ (на Фиг.1 не показаны)). Работа может быть создана путем использования либо прикладного программного интерфейса (API), обеспечиваемого рабочей средой 10, либо функций языка программирования и соответствующих средств в одном варианте осуществления. При освобождении ресурсов обработки для планировщика 22 задания назначаются контекстам выполнения 34 или 38, которые выполняют их до завершения на виртуальных процессорах 32 перед выбором новых заданий. Контекст выполнения 34, выполняющийся на виртуальном процессоре 32, может также разблокировать другие контексты выполнения 40 путем формирования данных, сообщения или события, которое будет использоваться другим контекстом выполнения 40.

Каждое задание в планировщике 22 может быть выполнено (например, выполненные задания 36 и 39), что указывает на то, что контекст выполнения 34 или 38 был или будет присоединен к заданию и задание готово к выполнению. Выполненные задания, как правило, содержат разблокированные контексты выполнения и запланированные агенты. Задание, которое не выполнено, называется невыполненным. Невыполненные задания (например, задания 42) могут формироваться в виде порожденных заданий, генерируемых путем выполнения порождающих заданий и могут генерироваться параллельными структурами (например, parallel, parallel for, begin и finish). Каждый набор планируемых заданий 40 в планировщике 22 может быть организован в один или более синхронизированных наборов (например, стек и/или очередь) для логически независимых заданий с контекстами выполнения (т.е., выполненными заданиями) вместе со списком разбросанных очередей для зависимых заданий (т.е., невыполненных заданий), как показано в изображенном на Фиг.5А варианте осуществления, описанном ниже.

После завершения, блокирования или иного прерывания (например, явного возврата или принудительного прерывания обслуживания) контекста выполнения 34, запущенного на виртуальном процессоре 32, виртуальный процессор 32 освобождается для выполнения другого выполненного задания 39 или невыполненного задания 42. Планировщик 22 ищет готовый к выполнению контекст выполнения 38 или невыполненное задание 42 для присоединения к свободному виртуальному процессору 32 с целью выполнения. Планировщик 22 продолжает присоединение контекстов выполнения 38 к свободным виртуальным процессорам 32 с целью выполнения до тех пор, пока не будут выполнены все контексты выполнения 38 планировщика 22.

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

Фиг.2 - схема последовательности операций, иллюстрирующая вариант осуществления способа создания и заполнения наборов планируемых заданий 40 в планировщике 22. Изображенный на Фиг.2 способ будет описан со ссылкой на вариант осуществления планировщика 22 на Фиг.1.

На Фиг.2 рабочая среда 10 и/или уровень управления ресурсами 14 выявляет узлы планирования 30 на основе одного или более показателей выполнения в соответствии с блоком 52. Показатели выполнения могут представлять собой любые подходящие меры выполнения команд в вычислительной системе и могут включать следующие характеристики обработки и других ресурсов вычислительной системы: быстродействие, пропускная способность и время задержки памяти. С помощью показателей выполнения, определенных для различных совокупностей компонентов вычислительной системы, рабочая среда 10 и/или уровень управления ресурсами 14 разбивает обработку и другие ресурсы вычислительной системы и использует разбиения для выявления узлов планирования 30 для планировщика 22. Каждый из узлов планирования 30 содержит группы одинаковых или различных совокупностей ресурсов обработки и других ресурсов вычислительной системы.

В одном примере вычислительная система может содержать процессоры, которые включают в себя множество аппаратных потоков 16. В этом примере рабочая среда 10 и/или уровень управления ресурсами 14 могут разбивать каждый блок процессора на отдельные узлы и создавать узел планирования 30 для каждого узла.

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

В другом примере рабочая среда 10 и/или уровень управления ресурсами 14 могут разбивать произвольные или частично произвольные совокупности ресурсов процессора в вычислительной системе на узлы и создавать узел планирования 30 для каждого узла.

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

В соответствии с блоком 54 рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 создают соответствующий набор планируемых заданий 40 для каждого узла планирования 30. Как показано на Фиг.1, планировщик 22 создает наборы планируемых заданий 40(1)-40(L), которые соответствуют соответствующим узлам планирования 30(1)-30(L). Каждый набор планируемых заданий 40 образует в памяти вычислительной системы структуру данных для хранения заданий, при этом указанная структура данных доступна для поиска виртуальными процессорами 32 из соответствующего узла планирования 30 и виртуальными процессорами 32 из других узлов планирования 30.

В соответствии с блоком 56 рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 преобразует наборы планируемых заданий 40(1)-40(L) в очередность полного или частичного поиска на основе одного или более показателей выполнения. Планировщик 22 использует эти показатели выполнения для сравнения расходов на выполнение между различными узлами планирования 30. Расходы на выполнение могут быть описаны с точки зрения межузловых расстояний, при этом различные межузловые расстояния отражают разные характеристики выполнения между данным узлом планирования 30 и другими узлами планирования 30. По межузловым расстояниям узлы планирования 30 с более низкими расходами на выполнение относительно данного узла планирования 30 описываются как расположенные ближе к данному узлу планирования 30, а узлы планирования 30 с более высокими расходами на выполнение относительно данного узла планирования 30 описываются как расположенные дальше от данного узла планирования 30. В одном варианте осуществления планировщик 22 преобразует наборы планируемых заданий 40(1)-40(L) в очередность полного или частичного поиска с помощью межузловых расстояний.

Для создания очередности поиска планировщик 22 группирует совокупности наборов планируемых заданий 40 в подсовокупности одного или более наборов планируемых заданий 40 на основе межузловых расстояний. Каждый набор планируемых заданий 40 имеет нулевое межузловое расстояние от соответствующего узла планирования 30. В соответствии с этим каждый набор планируемых заданий 40 образует подсовокупность планируемых заданий 40 первого уровня (например, подсовокупность 0-го уровня) для соответствующего узла планирования 30. Для подсовокупности наборов планируемых заданий 40 следующего уровня (например, подсовокупности 1-го уровня) планировщик 22 группирует совокупность одного или более наборов планируемых заданий 40 с наименьшим диапазоном межузловых расстояний от данного узла планирования 30. Затем планировщик 22 группирует совокупность одного или более наборов планируемых заданий 40 со следующим наименьшим диапазоном межузловых расстояний от данного узла планирования 30 в подсовокупность наборов планируемых заданий 40 следующего уровня (например, подсовокупность 2-го уровня). Планировщик 22 продолжает группировать совокупности одного или более наборов планируемых заданий 40 с последующими диапазонами межузловых расстояний от данного узла планирования 30 в подсовокупности наборов планируемых заданий 40 последующих уровней до тех пор, пока все необходимые наборы планируемых заданий 40 в совокупности наборов планируемых заданий 40 не будут включены в очередность поиска.

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

Фиг.3А-3В - схема и таблица, соответственно, иллюстрирующие вариант осуществления очередности частичного поиска 60 в вычислительной системе с NUMA 61 с четырьмя блоками процессоров, содержащими соответствующие совокупности четырех аппаратных потоков 16. Соответствующая локальная память подключается к каждому процессору (не показан). Поскольку каждый аппаратный поток 16 в блоке процессора имеет аналогичные показатели выполнения, каждый блок процессора образует узел 0-го уровня в примере, изображенном на Фиг.3А-3В. В соответствии с этим узел планирования 0-го уровня 30(1) содержит аппаратные потоки 16(1)-16(4), узел планирования 0-го уровня 30(2) содержит аппаратные потоки 16(5)-16(8), узел планирования 0-го уровня 30(3) содержит аппаратные потоки 16(9)-16(12), а узел планирования 0-го уровня 30(4) содержит аппаратные потоки 16(9)-16(12). Узлы планирования 0-го уровня 30(1)-30(4) соответствуют соответствующим подсовокупностям наборов планируемых заданий 40(1)-40(4) 0-го уровня.

В соответствии с Фиг.3А узлы планирования 30(1)-30(2) совместно используют соединение 62(1) между узлами 30(1)-30(2), узлы планирования 30(1)-30(3) совместно используют соединение 62(2) между узлами 30(1)-30(3), узлы планирования 30(2)-30(4) совместно используют соединение 62(3) между узлами 30(2)-30(4), а узлы планирования 30(3)-30(4) совместно используют соединение 62(4) между узлами 30(3)-30(4). Предполагается, что в изображенном на Фиг.3А примере соединения 62(1)-62(4) имеют одинаковые характеристики быстродействия и полосы пропускания.

Межузловые расстояния между любыми двумя узлами 30, совместно использующими соединения 62, меньше межузловых расстояний между любыми двумя узлами 30, не использующими совместно соединения 62. Например, узел 30(1) осуществляет доступ к узлу 30(4) с помощью либо обоих соединений 62(1) и 62(3), либо обоих соединений 62(2) и 62(4). Подобным образом, узел 30(2) осуществляет доступ к узлу 30(3) с помощью либо обоих соединений 62(1) и 62(2), либо обоих соединений 62(3) и 62(4).

Со стороны узла 30(1) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(2)-40(3), которые соответствуют узлам планирования 30(2)-30(3), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(4), который соответствует узлу планирования 30(4).

Со стороны узла 30(2) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(1)-40(4), которые соответствуют узлам планирования 30(1)-30(4), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(3), который соответствует узлу планирования 30(3).

Со стороны узла 30(3) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(1)-40(4), которые соответствуют узлам планирования 30(1)-30(4), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(2), который соответствует узлу планирования 30(2).

Со стороны узла 30(4) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(2)-40(3), которые соответствуют узлам планирования 30(2)-30(3), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(1), который соответствует узлу планирования 30(1).

В соответствии Фиг.2 планировщик 22 заполняет наборы планируемых заданий 40(1)-40(М) соответствующими совокупностями заданий, как показано в блоке 58. Каждая совокупность одного или более заданий, представленных в планировщике 22, может быть создана явно процессом 12 или неявно рабочей средой 10 (например, путем создания агента без порождающего элемента или введения контекста выполнения операционной системы в контекст выполнения планировщика 22). Планировщик 22 вносит совокупности заданий в наборы планируемых заданий 40 в соответствии с каким-либо подходящим алгоритмом или в соответствии с топологией узлов планирования 30. Например, планировщик 22 может вносить совокупности заданий в наборы планируемых заданий 40 в круговом порядке. В другом примере планировщик 22 может вносить совокупности заданий в наборы планируемых заданий в соответствии с топологией узлов планирования 30.

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

В соответствии с блоком 72 планировщик 22 определяет, освобождается ли виртуальный процессор 32. Планировщик 22 может выполнять эту функцию постоянно при обеспечении выполнения процесса 12. После завершения, блокирования или иного прерывания (например, явного возврата или принудительного прерывания обслуживания) контекста выполнения 34, запущенного на виртуальном процессоре 32, виртуальный процессор 32 освобождается для выполнения нового задания.

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

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

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

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

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

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

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

Фиг.5А - блок-схема, иллюстрирующая вариант осуществления 40А набора планируемых заданий 40, который содержит совокупность групп планов 90(1)-90(Р), где Р - целое число, большее или равное единице и обозначающее Р-ю группу планов 90. Совокупность групп планов 90(1)-90(Р) расположена в кольцевой схеме, как показано стрелкой 96. Каждая группа планов 90 содержит готовый к выполнению набор 92, очередь работ 93 и совокупность нуля или более разбросанных очередей 94. Каждый готовый к выполнению набор 92 содержит список готовых к выполнению заданий или контекстов выполнения. Планировщик 22 добавляет контекст выполнения к готовому к выполнению набору 92, когда контекст выполнения становится заблокированным, или процесс 12 выдает планировщику 22 новый готовый к выполнению контекст выполнения (возможно, созданный по запросу). Очередь работ 93 содержит список разбросанных очередей 94, как показано стрелкой 95, и отслеживает контексты выполнения, которые выполняют задания из разбросанных очередей 93. Каждая разбросанная очередь 94 содержит одно или более невыполненных заданий без назначенного контекста выполнения.

Планировщик 22 заполняет наборы планируемых заданий 40А (Фиг.1) соответствующими совокупностями нуля или более групп планов 90 в любой момент времени (например, в ответ на выполнение других заданий), при этом каждая группа планов 90 содержит совокупность заданий процесса 12. В таких вариантах осуществления планировщик 22 может осуществлять поиск в каждой группе планов 90 в наборе планируемых заданий 40А перед проведением поиска задания в другом наборе планируемых заданий 40 или 40А.

Планировщик 22 может попытаться локализовать задание для выполнения в группе планов 90, из которой свободный виртуальный процессор 32 совсем недавно получил выполнимое задание, или в группе планов 90, обозначенной индексом 97 (например, круговым индексом). В каждой группе планов 90 планировщик 22 может осуществлять поиск выполненных заданий в готовом к выполнению наборе 92 группы планов 90 перед осуществлением поиска выполненного задания в других группах планов 90 (например, в круговом порядке). Если выполненное задание не найдено, то планировщик 22 может осуществлять поиск невыполненных заданий в разбросанных очередях 94 группы планов 90 перед осуществлением поиска невыполненного задания в других группах планов 90 (например, в круговом порядке). Планировщик 22 может обновлять индекс 97 для выявления группы планов 90, в которой было найдено выполнимое задание.

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

Фиг.5В - блок-схема, иллюстрирующая вариант осуществления 40В набора планируемых заданий 40, который содержит локальные наборы заданий 44(1)-44(N), соответствующие соответствующему виртуальному процессору 32(1)-32(N).

В вариантах осуществления, в которых один или более наборов планируемых заданий 40 содержит локальные наборы 44, совокупность контекстов выполнения в планировщике 22 также содержит совокупности готовых к выполнению контекстов выполнения 46(1)-46(N) в соответствующих локальных совокупностях 44(1)-44(N). Каждый контекст выполнения 46 имеет сопряженное задание 47, которое было разблокировано выполнением задания 36, при этом задание 36 было выполнено или в настоящее время выполняется на виртуальном процессоре 32, соответствующем локальному набору 44, который содержит контекст выполнения 46.

Планировщик 22 сначала может попытаться локализовать задание в локальном наборе 44, соответствующем свободному виртуальному процессору 32, перед осуществлением поиска где-либо еще в наборе планируемых заданий 40В. Локальные наборы 44 могут позволить планировщику 22 использовать локальность памяти и прочие эффекты, которые могут произойти с аппаратными потоками 16. В процессе выполнения 12 планировщик 22 может назначать каждый зависимый от ожидания контекст выполнения, который становится заблокированным для локального набора 44, соответствующего виртуальному процессору 32, который обеспечил разблокирование контекста выполнения. При освобождении виртуального процессора 32 виртуальный процессор 32 может попытаться выполнить совсем недавно добавленный контекст выполнения в соответствующем локальном наборе 44, чтобы попробовать использовать данные, хранящиеся в иерархии памяти, соответствующей виртуальному процессору 32.

Если в локальном наборе 44, соответствующем свободному виртуальному процессору 32, выполнимое задание не найдено, то планировщик 22 может попытаться локализовать выполнимое задание в локальном наборе 44, соответствующем другому виртуальному процессору 32 узла планирования 30. Планировщик 22 осуществляет доступ к локальным наборам 44, соответствующим другим виртуальным процессорам 32 в круговом или ином подходящем порядке, и может выполнить совсем недавно добавленный контекст выполнения в локальном наборе 44, в котором было найдено выполнимое задание.

В других вариантах осуществления другие наборы планируемых заданий 40 могут содержать как группы планов 90 набора планируемых заданий 40А (Фиг.5А), так и локальные наборы 44 набора планируемых заданий 40В (Фиг.5В).

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

В соответствии с Фиг.6А вычислительная система 100А содержит один или более блоков процессора 102, запоминающую систему 104, ноль или более устройств ввода-вывода 106, ноль или более устройств отображения 108, ноль или более периферийных устройств 110 и ноль или более сетевых устройств 112. Блоки процессоров 102, запоминающая система 104, устройства ввода-вывода 106, устройства отображения 108, периферийные устройства 110 и сетевые устройства 112 осуществляют обмен данными с помощью совокупности соединений 114, которая включает в себя любой подходящий тип, количество и конфигурацию контроллеров, шин, интерфейсов и/или иных проводных или беспроводных соединений.

Вычислительная система 100А представляет собой любое устройство обработки, настроенное на общее применение или специальное применение. К примерам вычислительной системы 100А относятся сервер, персональный компьютер, ноутбук, планшетный компьютер, карманный персональный компьютер (PDA), мобильный телефон и аудио/видеоустройство. Компоненты вычислительной системы 100А (т.е., блоки процессоров 102, запоминающая система 104, устройства ввода-вывода 106, устройства отображения 108, периферийные устройства 110, сетевые устройства 112 и соединения 114) могут быть помещены в общий кожух (не показан) или любое подходящее число отдельных кожухов (не показаны).

Блоки процессоров 102 содержат аппаратные потоки 16(1)-16(М). Каждый аппаратный поток 16 в блоке процессора 102 настроен на осуществление доступа и выполнение команд, хранящихся в запоминающей системе 104. Указанные команды могут включать в себя базовую систему ввода-вывода (BIOS) или аппаратно реализованное программное обеспечение (не показано), операционную систему (OS) 120, платформу рабочей среды 122, приложения 124 и уровень управления ресурсами 14 (показан также на Фиг.1). Каждый аппаратный поток 16 может выполнять команды в соответствии с информацией (или в ответ на информацию), полученной от устройств ввода-вывода 106, устройств отображения 108, периферийных устройств 110 и/или сетевых устройств 112.

Вычислительная система 100А загружает и выполняет OS 120. OS 120 содержит команды, выполняемые блоками процессоров 102 для управления компонентами вычислительной системы 100А и обеспечения набора функций, позволяющих приложениям 124 осуществлять доступ к компонентам и использовать их. В одном варианте осуществления OS 120 является операционной системой Windows. В других вариантах осуществления OS 120 является другой операционной системой, подходящей для использования с вычислительной системой 100А.

Уровень управления ресурсами 14 содержит команды, выполняемые в соответствии с OS 120 с целью распределения ресурсов вычислительной системы 100А, включая аппаратные потоки 16, как было описано выше со ссылкой на Фиг.1. Уровень управления ресурсами 14 может входить в вычислительную систему 100А в виде библиотеки функций, находящейся в распоряжении одного или более приложений 124, либо в виде неотъемлемой части OS 120.

Платформа рабочей среды 122 содержит команды, выполняемые в соответствии с OS 120 и уровнем управления ресурсами 14 с целью формирования рабочей среды 10 и обеспечения функций рабочей среды для приложений 124. Указанные функции рабочей среды включают в себя функцию планировщика, как описано выше более подробно со ссылкой на Фиг.1. Функции рабочей среды могут входить в вычислительную систему 100А в виде части приложения 124, в виде библиотеки функций, находящейся в распоряжении одного или более приложений 124, либо в виде неотъемлемой части OS 120 и/или уровня управления ресурсами 14.

Каждое приложение 124 содержит команды, выполняемые в соответствии с OS 120, уровнем управления ресурсами 14 и/или платформой рабочей среды 122 с целью обеспечения выполнения необходимых операций вычислительной системой 100А. Каждое приложение 124 представляет собой один или более процессов, таких как процесс 12, описанный выше, который может выполняться планировщиком 22 в соответствии с платформой рабочей среды 122.

Запоминающая система 104 содержит любой подходящий тип, число и конфигурацию энергозависимых или энергонезависимых запоминающих устройств, настроенных на хранение команд и данных. Запоминающие устройства запоминающей системы 104 представляют собой машиночитаемый носитель записи, хранящий машиночитаемые команды, включая OS 120, уровень управления ресурсами 14, платформу рабочей среды 122 и приложения 124. Команды выполняются вычислительной системой для осуществления функций и методов OS 120, уровня управления ресурсами 14, платформы рабочей среды 122 и приложений 124, описанных в настоящем документе. К примерам запоминающих устройств в запоминающей системе 104 относятся носители записи на жестком диске, оперативное запоминающее устройство (RAM), постоянное запоминающее устройство (ROM), флэш-носители записи и флэш-карты, а также магнитные и оптические диски.

Запоминающая система 104 хранит команды и данные, полученные от блоков процессоров 102, устройств ввода-вывода 106, устройств отображения 108, периферийных устройств 110 и сетевых устройств 112. Запоминающая система 104 выдает хранящиеся в памяти команды и данные в блоки процессоров 102, устройства ввода-вывода 106, устройства отображения 108, периферийные устройства 110 и сетевые устройства 112.

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

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

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

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

Фиг.6В - блок-схема, иллюстрирующая вариант осуществления 100В вычислительной системы 100. Вычислительная система 100В также содержит, по меньшей мере, блоки процессоров 102 и запоминающую систему 104. Блоки процессоров 102 включают в себя блоки процессоров 102(1)-102(R), а запоминающая система 104 включает в себя совокупность запоминающих устройств 128(1)-128(R), где R - целое число, которое больше или равно двум и соответствует R-му блоку процессора 102 и R-й совокупности запоминающих устройств 128. OS 120, платформа рабочей среды 122, приложения 124 и уровень управления ресурсами 14 - каждое из перечисленного может храниться на любых подходящих запоминающих устройствах 104(1)-104(R).

В изображенном на Фиг.6В варианте осуществления каждый блок процессора 102(1)-102(R) и соответствующая совокупность запоминающих устройств 128(1)-128(R) образуют узел. Узлы связаны с помощью любого подходящего типа, числа и/или комбинации межузловых соединений 130. Быстродействие и/или полоса пропускания соединений 130 узлов может различаться.

Каждый блок процессора 102 содержит совокупность аппаратных потоков 16(1)-16(4), в которой каждый аппаратный поток содержит кэш L1 (первого уровня) (не показан). Каждый блок процессора 102 также содержит совокупность кэшей L2 (второго уровня) 132(1)-132(4), которые соответствуют соответствующим аппаратным потокам 16(1)(1)-16(1)(4). Каждый блок процессора 102 содержит, кроме того, кэш L3 (третьего уровня), находящийся в распоряжении совокупности аппаратных потоков 16(1)-16(4), интерфейс системных ресурсов 136, координатный переключатель 138, контроллер памяти 140 и узловой интерфейс 142. Интерфейс системных ресурсов 136 обеспечивает доступ к узловым ресурсам (не показаны). Координатный переключатель 138 соединяет интерфейс системных ресурсов 136 с контроллером памяти 140 и узловым интерфейсом 142. Контроллер памяти 140 соединяется с запоминающим устройством 128. Узловой интерфейс 142 соединяется с одним или более межузловых соединений 130.

Поскольку узел содержит локальную память (т.е., совокупность запоминающих устройств 104), доступ блоков процессоров 102 в узле к локальной памяти может осуществляться быстрее, чем доступ к памяти в других узлах. Кроме того, доступ к памяти в других узлах может зависеть от скорости соединения, полосы пропускания, топологии кэша и/или межузлового расстояния NUMA соединений 130 между узлами. Например, некоторые узлы могут быть подключены к относительно быстрому соединению 130, такому как шина Hyper Transport компании Advanced Micro Devices или шина CSI компании Intel, хотя другие узлы могут быть подключены к одному или более относительно медленных соединений 130.

В других вариантах осуществления каждый блок процессора 102 может содержать другие конфигурации и/или количества кэшей. Например, каждый аппаратный поток 16 в других вариантах осуществления может содержать два или более кэшей L1, а кэши L2 и/или L3 в других вариантах осуществления могут или не могут использоваться совместно. В другом примере другие варианты осуществления могут содержать дополнительные кэши (например, кэш четвертого уровня (L4)), либо меньшее число кэшей, либо не содержать кэшей.

В соответствии с вариантами осуществления, описанными выше на Фиг.1-5В, задержки памяти и межсоединений в вычислительной системе 100В обеспечивают узловые расстояния, которые могут учитываться рабочей средой 10, уровнем управления ресурсами 14 и/или планировщиком 22 при образовании узлов планирования 30. Например, рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 могут создавать узел планирования 30 для каждого узла в вычислительной системе 100В вместе с соответствующим набором планируемых заданий 40. Рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 могут преобразовывать наборы планируемых заданий 40 в очередность полного или частичного поиска на основе топологии межсоединений между узлами. Например, любые два узла, подключенные к относительно быстрому соединению 130, могут быть сгруппированы в один и тот же уровень узла планирования и подсовокупность наборов планируемых заданий, а узлы с относительно медленными соединениями 130 могут быть сгруппированы в уровень узла планирования и подсовокупность наборов планируемых заданий, которые выше уровня узла планирования и подсовокупности наборов планируемых заданий, содержащих относительно быстрое соединение 130.

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

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

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

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

1. Способ планирования, реализуемый планировщиком (22) в процессе (12) вычислительной системы (100А/100 В), причем упомянутый способ включает в себя:
в ответ на один из первого множества ресурсов (16/32) обработки в первом освобождающемся узле (10) планирования, поиск первого задания (39/42) для выполнения в первом наборе (40) планируемых заданий, соответствующем первому узлу планирования; и
в ответ на не нахождение первого задания для выполнения в первом наборе планируемых заданий, выполнение с помощью одного из первого множества ресурсов обработки, второго задания (39/42) из второго набора (40) планируемых заданий, соответствующего второму узлу (10) планирования, который содержит второе множество ресурсов (16/32) обработки, причем первый и второй узлы планирования выявляют для планировщика на основе одного или более показателей выполнения для соответствующих совокупностей компонентов вычислительной системы, причем первый и второй наборы планируемых заданий преобразуют в очередность, по меньшей мере, частичного поиска с помощью сравнения расходов на выполнение между, по меньшей мере, первым и вторым узлами планирования.

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

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

4. Способ по п.3, дополнительно содержащий:
поиск второй совокупности групп (90) планов для второго задания во втором наборе планируемых заданий.

5. Способ по п.1, в котором один из первого множества ресурсов обработки включает в себя первый виртуальный процессор (32) и первый аппаратный поток (16).

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

7. Способ по п.1, дополнительно содержащий:
поиск третьего задания (39/42) для выполнения в локальном наборе (44), соответствующем одному из первого множества ресурсов обработки; и
в ответ на нахождение третьего задания для выполнения в локальном наборе, выполнение третьего задания с помощью одного из первого множества ресурсов обработки.

8. Способ по п.1, в котором поиск первого задания в первом наборе планируемых заданий дополнительно содержит:
поиск выполненного задания (39) в совокупности групп (90) планов в первом наборе планируемых заданий; и
в ответ на не нахождение выполненного задания для выполнения в совокупности групп планов, поиск невыполненного задания (42) в совокупности групп планов.

9. Машиночитаемый носитель записи (104/128/132/134), хранящий машиночитаемые команды, которые, при выполнении их вычислительной системой (100А/100В), осуществляют способ, содержащий:
выявление первого и второго узлов (30) планирования для планировщика (22) в процессе (12), выполняемом в вычислительной системе, на основе одного или более показателей выполнения для соответствующих совокупностей компонентов вычислительной системы, причем первый и второй узлы планирования содержат соответствующие первую и вторую совокупности ресурсов обработки;
создание первого и второго наборов (40) планируемых заданий, соответствующих первому и второму узлам планирования, соответственно;
преобразование первого и второго наборов планируемых заданий в очередность, по меньшей мере, частичного поиска с помощью сравнения расходов на выполнение между, по меньшей мере, первым и втором узлами планирования; и
заполнение первого и второго наборов планируемых заданий первой и второй совокупностями заданий (39/40/42), соответственно.

10. Машиночитаемый носитель записи по п.9, в котором очередность частичного поиска основана на одном или более показателях выполнения, связанных с первым и вторым узлами планирования.

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

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

13. Машиночитаемый носитель записи по п.9, в котором один или более показателей выполнения включает в себя расстояние доступа к неоднородной памяти (NUMA).