СПОСОБ И УСТРОЙСТВО ФОРМИРОВАНИЯ ОЧЕРЕДИ ПОТОКОВ Российский патент 2011 года по МПК G06F9/46 

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

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

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

ПЕРЕЧЕНЬ ЧЕРТЕЖЕЙ

Фиг.1 - блок-схема системы в соответствии с некоторыми вариантами осуществления.

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

Фиг.3А - блок-схема части системы обработки по Фиг.1 в соответствии с некоторыми вариантами осуществления.

Фиг.3В - блок-схема части системы обработки по Фиг.1 в соответствии с некоторыми вариантами осуществления.

Фиг.4 - блок-схема генератора потоков по Фиг.1 в соответствии с некоторыми вариантами осуществления.

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

Фиг.6 - схематичная диаграмма отношения потоков в соответствии с некоторыми вариантами осуществления.

Фиг.7 - схематичная диаграмма отношения потоков в соответствии с некоторыми вариантами осуществления.

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

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

ПОДРОБНОЕ ОПИСАНИЕ

Некоторые варианты осуществления, описанные здесь, ассоциированы с «системой обработки». Используемой здесь фразой «система обработки» может называться любая система, которая обрабатывает данные. В некоторых вариантах осуществления, система обработки ассоциирована с графической машиной, которая обрабатывает графические данные и/или другие типы мультимедийной информации. В некоторых случаях, рабочие характеристики системы обработки могут быть улучшены использованием исполняющего блока SIMD («один поток команд - много потоков данных). Например, исполняющий блок SIMD может одновременно выполнять одну SIMD-команду с плавающей точкой для множества каналов данных (например, для ускорения преобразования и/или рендеринга трехмерных геометрических форм). Другие примеры систем обработки включают в себя Центральный Процессорный Модуль (CPU) и Модуль Цифровой Обработки Сигналов (DSP).

Фиг.1 является блок-схемой системы 100 в соответствии с некоторыми вариантами осуществления. На Фиг.1 система 100 включает в себя устройство 110 ввода, систему 120 обработки и устройство 130 вывода. Устройство 110 ввода может соединяться с системой 120 обработки через линию 140 связи. Система 120 обработки может соединяться с устройством 130 вывода через линию 150 связи.

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

Упоминаемая здесь линия связи может быть любым типом линии связи, например, но не в ограничительном смысле, проводным (например, провода, оптоволоконные кабели) или беспроводным (например, акустическими линиями связи, электромагнитными линиями связи или любой их комбинацией, включая, например, но в не ограничительном смысле, микроволновые линии связи, спутниковые линии связи, инфракрасные линии связи), и/или их комбинацию, каждый из которых может быть общественным или частным, выделенным и/или совместно используемым (например, сеть). Линия связи может быть или может не быть постоянной линией связи. Линия связи может поддерживать любой тип информации в любой форме, например, но не в ограничительном смысле, аналоговый и/или цифровой (например, последовательность двоичных значений, т.е. строка битов) сигнал(ы) в последовательной и/или параллельной форме. Информация может или не может разделяться на блоки. При разделении на блоки количество информации в блоках может быть заранее определенным или динамически определенным и/или может быть фиксированным (например, одинаковым) или переменным. Линия связи может использовать протокол или комбинацию протоколов, включая, например, но не в ограничительном смысле, Интернет-Протокол (IP).

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

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

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

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

Фиг.3А является блок-схемой части системы обработки, в соответствии с некоторыми вариантами осуществления. На Фиг.3А, в некоторых вариантах осуществления, система обработки может включать в себя исполняющий блок 300 и средство формирования (генератор) 310 потоков. В некоторых вариантах осуществления исполняющий блок 300 может включать в себя таблицу 320 потоков, множество очередей 330 команд, множество декодеров 340, диспетчер 350 команд и конвейер 360 исполняющего блока.

В некоторых вариантах осуществления, команды могут подаваться на вход генератора 310 потоков по линии 140 связи. Команды могут подаваться от любого источника команд, включая, например, но не в ограничительном смысле, хост и/или устройство 110 ввода (Фиг.1). В некоторых вариантах осуществления генератор потоков может также принимать команды от конвейера 360 исполняющего блока по одной или более сигнальным линиям и/или шине 380. Генератор 310 потоков может обрабатывать команды, которые могут включать в себя запросы на формирование одного или более потоков и могут формировать один или более потоков в ответ на, по меньшей мере, эти команды. Один или более выходов генератора 310 потоков могут подавать один или более потоков, определение для которого в свою очередь может подаваться по одной или более сигнальным линиям 370, на один или более входов таблицы 320 потоков. Каждый поток может включать в себя набор команд, которые могут извлекаться из кэша команд или другой памяти, которая может хранить множество команд, определяющих одну, некоторые или все части одной или более программ, исполняемых и/или подлежащих исполнению процессорной системой. Команды для каждого потока, определенного таблицей потоков, могут подаваться в соответствующую одну из очередей 330 команд, размер каждой из которых может быть задан, например, для сохранения небольшого числа команд, например, шесть-восемь команд. Команды из каждой очереди 330 команд могут подаваться на вход соответствующего одного из декодеров 340. Декодеры 340 могут подавать декодированные команды на диспетчер 350 команд, который может подавать декодированные команды для одного или более потоков, исполняемых конвейером 360 исполняющего блока, который может выполнять декодированные команды.

Фиг.3В является блок-схемой части системы обработки в соответствии с некоторыми вариантами осуществления. На Фиг.3В в некоторых вариантах осуществления система обработки включает в себя исполняющий блок 390 и генератор 310 потоков. В некоторых вариантах осуществления исполняющий блок 390 может включать в себя множество исполняющих блоков, например исполняющие блоки 300A-300D. В некоторых вариантах осуществления, каждый из исполняющих блоков 300A-300D может быть идентичным и/или аналогичным исполняющему блоку 300 (Фиг.3А).

В некоторых вариантах осуществления команды могут подаваться на вход генератора 310 потоков по линии 140 связи. Команды могут подаваться от источника команд, включая, например, но не в ограничительном смысле, хост и/или устройство 110 ввода (Фиг.1). В некоторых вариантах осуществления, генератор потоков может также принимать команды от одного или более исполняющих блоков 300A-300D. Генератор 310 потоков может обрабатывать команды, которые могут включать запросы на формирование одного или более потоков, и может формировать один или более потоков в ответ на по меньшей мере эти команды. С одного или более выходов генератора 310 потоков могут подаваться один или более потоков, определение для которых в свою очередь может подаваться на один или более исполняющих блоков 300A-300D, например один или более входов одной или более таблиц потоков (см., например, таблицу 320 потока (Фиг.3А)) одного или более исполняющих блоков 300A-300D. В некоторых вариантах осуществления работа исполняющих блоков 300A-300D может быть идентична и/или аналогична работе исполняющего блока 300 (Фиг.3А), описанной выше.

В некоторых вариантах осуществления исполняющий блок (300А, 300В, 300С или 300D) может содержать исполняющий блок SIMD. В некоторых вариантах осуществления исполняющий блок SIMD может принимать команду (например, от модуля памяти команд) вместе с четырехкомпонентным вектором данных (например, компонентами вектора). Исполняющий блок может затем одновременно выполнять команду для всех компонент в векторе. Такой подход называется «горизонтальной», «канально-параллельной» или «Основывающейся на массиве структур (AOS)» реализацией. В некоторых вариантах осуществления исполняющий блок SIMD может принимать команду с четырьмя операндами данных, где каждый операнд ассоциирован с отличным от других вектором. Каждый вектор может включать в себя, например, три значения координат (например, X, Y и Z), ассоциированные с местоположением в трехмерной графике. Исполняющий блок может затем одновременно выполнять команду для всех операндов за один период команд. Такой подход называется «вертикальной», «канально-последовательной» или «Основывающейся на структуре массивов (SOA)» реализацией.

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

Фиг.4 является функциональной блок-схемой генератора 310 потоков в соответствии с некоторым вариантом осуществления. Согласно Фиг.4, в некоторых вариантах осуществления, генератор 310 потоков может включать в себя средство 402 поточной организации команд, видеопрепроцессор 404, средство 406 порождения потока, мультиплексор 410, память (иногда называемую здесь как унифицированный возвратный буфер (URB)) 412 и диспетчер 414 потоков.

Средство поточной организации команд может соединяться с видеопрепроцессором 404 и мультиплексором 410. Видеопрепроцессор 404 может соединяться со средством 406 порождения потока и мультиплексором 410. Мультиплексор может соединяться с унифицированным возвратным буфером, который может соединяться с диспетчером потоков.

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

Вход средства 402 поточной организации команд может принимать команды. Входные команды могут подаваться любым источником команд, включая, но не в ограничительном смысле, например, хост-процессор и/или устройство 110 ввода (Фиг.1). В некоторых вариантах осуществления средство 402 поточной организации команд содержит средство прямого доступа к памяти (DMA) для извлечения таких команд из памяти. В некоторых таких вариантах осуществления средство DMA сконфигурировано как кольцевой буфер.

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

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

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

Фиг.6 является схематичной диаграммой отношения потоков в соответствии с некоторыми вариантами осуществления. Согласно Фиг.6, в некоторых вариантах осуществления отношение потоков может включать в себя единую древовидную структуру 600. Единая древовидная структура 600 может включать в себя один корневой поток 602, который образует множество дочерних потоков 604-612. Некоторые дочерние потоки могут образовывать последующие дочерние потоки. Например, дочерний поток 606 может образовывать дочерние потоки 614, 616. Дочерний поток 608 может образовывать дочерние потоки 618, 620. Дочерний поток 610 может образовывать дочерний поток 622. Корневые потоки 608, 610, 612 зависят от корневого потока 602 и упоминаются как синхронизированные корневые потоки, которые далее описываются.

Фиг.7 является схематичной диаграммой отношения потоков в соответствии с некоторыми вариантами осуществления. Согласно Фиг.7, в некоторых вариантах осуществления отношение потоков может включать в себя множество несвязанных деревьев 700, 701. Первое дерево 700 имеет первый корневой поток 702, имеющий дочерние потоки 704, 706. Дочерний поток 706 может образовывать дочерние потоки 714, 716. Корневой поток 708 может иметь родственные корневые потоки 710, 712. Корневой поток 708 может образовывать дочерние потоки 718, 720. Корневой поток 702 может иметь родственные корневые потоки 708, 710, 712. Корневой поток 702 и родственные корневые потоки 708, 710, 712 являются независимыми и упоминаются как несинхронизированные корневые потоки, которые далее описываются.

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

Запросы потоков от средства 406 порождения потока могут подаваться на первый вход диспетчера 414 потоков, описываемого далее.

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

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

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

В некоторых вариантах осуществления один или более разделов памяти могут располагаться на том же чипе, что и средство 402 поточной организации команд, видеопрепроцессор 404, средство 406 порождения потока и/или диспетчер 414 потоков.

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

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

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

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

Команда 512 указателей состояний может «косвенно» предоставлять информацию состояний, которая управляет фиксированными функциями в конвейере (например, видеопрепроцессор 404 и/или средство 406 порождения потока) посредством предоставления по меньшей мере одного указателя для дескриптора состояния, который содержит информацию состояния. В некоторых вариантах осуществления команда указателей состояний может включать в себя указатель 514 состояния VFE, который может указывать на дескриптор 520 состояния VFE. В некоторых таких вариантах осуществления дескриптор состояния VFE может включать в себя указатель базы дескрипторов интерфейса, который может указывать на базу дескрипторов интерфейса.

Команда 516 неконвейерного состояния может «напрямую» обеспечивать информацию состояния, которая управляет фиксированными функциями и памятью, ассоциированными с конвейером. Один тип команды неконвейерного состояния может конфигурировать разделение памяти на разделы, которая, как указано выше, может располагаться на том же самом чипе, что и средство 402 поточной организации команд, видеопрепроцессор 404, средство 406 порождения потока и/или диспетчер 414 потоков. Другим типом команды неконвейерного состояния является команда констант, иногда называемая здесь как команда URB констант, которая может задавать данные констант, например одну или более констант. В некоторых вариантах осуществления, данные могут быть заданы косвенно (например, идентифицироваться одним или более указателями на память) и/или вложенным образом (например, включены в команду).

Простая команда 518 является любым типом команды, которая может использоваться. В некоторых вариантах осуществления простая команда может использоваться для запроса формирования одного или более потоков. В некоторых вариантах осуществления простая команда может включать в себя информацию, т.е. информацию управления и/или данные, для одного или более потоков, подлежащих формированию. В некоторых вариантах осуществления информация управления может включать в себя информацию, которая может использоваться для конфигурирования потока(ов), например для конфигурирования и/или назначения количества регистров, которые могут требоваться для потока(ов). В некоторых вариантах осуществления информация управления может включать в себя сдвиг дескриптора интерфейса для формируемого потока. В некоторых вариантах осуществления указатель дескриптора интерфейса для потока может определяться на основе сдвига дескриптора интерфейса и указателя базы дескрипторов интерфейса (как указано выше, в некоторых вариантах осуществления на видеопрепроцессор 404 может подаваться команда указателей состояний, которая включает в себя указатель 514 состояния VFE, который может указывать на дескриптор 520 состояния VFE, который может включать в себя указатель базы дескрипторов интерфейса.

Дескрипторы 510 интерфейса могут использоваться для задания информации, относящейся к потоку. Модель дескрипторов и интерфейс состояний может включать в себя указатель 522 базы дескрипторов интерфейса и множество дескрипторов 524 интерфейса. Указатель 522 базы дескрипторов интерфейса может обеспечивать положение одного или более дескрипторов интерфейса (например, первого дескриптора интерфейса) из упомянутого множества дескрипторов 524 интерфейса.

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

В некоторых вариантах осуществления каждый из множества дескрипторов 524 интерфейса может включать в себя указатель 526 потока и дескриптор 528 источника потока, указатель 530 состояния дискретизатора, указатель 532 таблицы связывания и/или один или более других указателей, которые могут использоваться для доступа к памяти и/или доступа к другим аппаратным функциям. Указатель 526 потока может обеспечивать положение одной или более команд (например, первой команды) для потока. Дескриптор 528 ресурсов потока может указывать ресурсы, которые могут требоваться потоку, например количество файлов регистра, которые могут требоваться для потока и/или режима с плавающей точкой. Указатель 530 состояния дискретизатора может обеспечивать место положение одного или более дескрипторов (например, первого дескриптора) в таблице 534 состояний дискретизатора. В некоторых вариантах осуществления, таблица 534 состояний дискретизатора может включать в себя до шестнадцати дескрипторов состояния дискретизатора. В некоторых вариантах осуществления один или более дескрипторов состояния дискретизатора используются в связи с трехмерной графикой. В некоторых вариантах осуществления один или более дескрипторов состояния дискретизатора обеспечивают одно или более состояний устройств(а) дискретизации (например, блока дискретизации для работы с графическими текстурами (не показан)).

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

Каждый из дескрипторов 524 интерфейса может храниться в его собственной ячейке(ах) памяти, т.е. одной или более ячейках памяти, которые отличаются от ячеек памяти, в которых хранятся другие дескрипторы интерфейса. Ячейка конкретного дескриптора 524 интерфейса может быть определена посредством добавления индекса или сдвига, иногда называемого здесь как индекс дескриптора интерфейса, к указателю базы дескрипторов интерфейса. Таким образом, согласно одному или более аспектам модели можно использовать два уровня адресации. Кроме того, один или более из таких уровней адресации может содержать адресацию по принципу база + сдвиг.

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

Согласно опять же Фиг.4, в некоторых вариантах осуществления команды, подаваемые на средство 402 поточной организации команд, являются идентичными и/или аналогичными командам, показанными на и/или описанными со ссылкой на Фиг.5. В некоторых таких вариантах осуществления средство 402 поточной организации команд может сначала принимать команду указателей состояний. По приему команды 512 указателей состояний (Фиг.5) средство 402 поточной организации команд может доставлять указатель состояния, который может указывать местоположение дескриптора 520 состояния VFE (Фиг.5), на видеопрепроцессор. Средство поточной организации команд может после этого принимать одну или более простых команд. Как указано выше, в некоторых вариантах осуществления простая команда может представлять запрос на формирование одного или более потоков. В некоторых вариантах осуществления простая команда может включать в себя информацию, т.е. информацию управления и/или данные, для одного или более формируемых потоков. В некоторых вариантах осуществления информация управления может включать в себя информацию, которая может использоваться для конфигурирования потока(ов), например, для конфигурирования и/или назначения количества регистров, которые могут потребоваться потоку(ам). В некоторых вариантах осуществления информация управления может включать в себя сдвиг дескриптора интерфейса для формируемого потока. В некоторых вариантах осуществления указатель дескриптора интерфейса для потока может определяться на основе сдвига дескриптора интерфейса и указателя базы дескрипторов интерфейса (как указано выше в некоторых вариантах осуществления, на видеопрепроцессор 404 может подаваться команда указателей состояния, которая включает в себя указатель 514 состояния VFE, который может указывать дескриптор 520 состояния VFE, который может включать в себя указатель базы дескрипторов интерфейса). В некоторых вариантах осуществления видеопрепроцессор 4 04 может определять указатель дескриптора интерфейса для потока на основе сдвига дескриптора интерфейса (который, как указано выше, может быть включен в простую команду 518 (Фиг.5), и указателя 522 базы дескрипторов интерфейса (как указано выше, в некоторых вариантах осуществления, на видеопрепроцессор может подаваться команда указателей состояния, которая включает в себя указатель 514 состояния VFE, который может указывать на дескриптор 520 состояния VFE, который может включать в себя указатель 522 базы дескрипторов интерфейса).

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

Фиг.8 является функциональной блок-схемой средства 406 порождения потока в соответствии с некоторыми вариантами осуществления. Согласно Фиг.8, в некоторых вариантах осуществления запрос корневого потока, выданный видеопрепроцессором 404 (Фиг.4), может подаваться на вход очереди 802 запросов корневого потока. В некоторых вариантах осуществления очередь 802 запросов корневого потока может содержать буфер обратного магазинного типа (FIFO), что означает, что первый запрос корневого потока, помещаемый в очередь 802, также является первым запросом корневого потока, извлекаемым из очереди 802. В некоторых таких вариантах осуществления очередь 802 запросов корневого потока может включать в себя входной буфер 804, выходной буфер 806 и один или более буферов, например, буферы 808-814, соединенные между собой. Выходной буфер 806 иногда называется здесь как головная часть 806 очереди 802. В некоторых вариантах осуществления выходной буфер 806 или головная часть очереди могут хранить запрос корневого потока, который будет следующим извлекаемым из очереди 802 запросов корневого потока.

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

В некоторых вариантах осуществления блок 816 управления может управлять временными характеристиками выдачи запроса корневого потока из очереди 802 запросов корневого потока. В некоторых вариантах осуществления блок 816 управления может обеспечивать один или более сигналов для синхронизации и/или арбитража, как будет описываться далее. Один или более сигналов от блока 816 управления могут подаваться в очередь 802 запросов корневого потока. Кроме того, один или более сигналов от блока 816 управления могут подаваться на один или более входов управления мультиплексора 818.

В некоторых вариантах осуществления средство 404 порождения потока может дополнительно включать в себя очередь 822 запросов порождения потока, вход которой может принимать запросы порождения потока, поданные от исполняющего блока. Очередь 822 запросов порождения потока может быть очередью запросов порождения потока, поданных в нее. В некоторых вариантах осуществления очередь 822 запросов порождения потока может содержать буфер обратного магазинного типа (FIFO). В некоторых таких вариантах осуществления очередь 822 запросов порождения потока может включать в себя входной буфер 824, выходной буфер 826 и один или более буферов, например буферы 828-834, соединенные между собой. Выходной буфер 826 иногда называется здесь как головная часть очереди или головная часть буфера очереди. В некоторых вариантах осуществления выходной буфер 82 6 или головная часть очереди может сохранять запрос порождения потока, который будет следующим извлекаемым из очереди 822 запросов порождения потока.

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

Запрос потока, выдаваемый очередью 822 запросов порождения потока, может подаваться на второй вход мультиплексора 818.

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

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

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

В этом отношении, в некоторых вариантах осуществления, блок 816 управления может подавать один или более сигналов управления в очередь 802 запросов корневого потока и/или один или более сигналов управления в очередь 822 запросов порождения потока для управления очередью 802 запросов корневого потока и/или очередью 822 запросов порождения потока таким образом, что только один запрос потока передается единовременно (т.е. один запрос потока из очереди 802 запросов корневого потока или один запрос потока из очереди 822 запросов порождения потока). В таких вариантах осуществления блок 816 управления может также подавать один или более сигналов управления на мультиплексор 818 для управления мультиплексором 818 таким образом, чтобы запрос потока подавался на выход этого мультиплексора 818.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые варианты осуществления описаны здесь в отношении исполняющего блока SIMD. Отметим, однако, что варианты осуществления могут быть ассоциированы с другими типами исполняющих блоков, таких как исполняющий блок MIMD (Множество потоков Команд - Множество потоков Данных).

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

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

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

2. Способ по п.1, в котором при приеме запроса на формирование первого потока принимают первый указатель.

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

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

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

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

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

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

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

10. Устройство по п.7, в котором схема содержит схему для приема первого указателя.

11. Устройство по п.10, в котором схема содержит схему для извлечения первого множества команд в ответ, по меньшей мере, частично на первый указатель и для выполнения этой, по меньшей мере, одной из первого множества команд.

12. Устройство по п.11, в котором схема для извлечения первого множества команд в ответ, по меньшей мере, частично на первый указатель содержит схему для извлечения первого множества команд в ответ, по меньшей мере, частично на первый указатель и второй указатель.

13. Устройство по п.7, в котором схема содержит первую очередь.

14. Устройство по п.13, в котором схема дополнительно содержит вторую очередь.

15. Устройство п.14, котором схема дополнительно содержит схему для арбитража между запросом в первой очереди и запросом во второй очереди.

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

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

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

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

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

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

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