конфигурируемое разделение для параллельных данных

Формула изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

11. Система по п.8, при этом система содержит множество логических процессоров.

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

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

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

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

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

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

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

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

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

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

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

Описание изобретения к патенту

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

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

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

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

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

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

Описание чертежей

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

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

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

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

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

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

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

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

Обзор

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

Например, если структура данных поддерживает случайный доступ, может быть ситуация, когда она может разделить свое содержимое на крупные фрагменты и полагаться на указатели, которые обеспечивают 0(1) - доступ к данным, т.е. постоянный по времени доступ, чтобы извлекать элементы данных. Это разделение данных может быть очень эффективным для массивов и для структур данных, таких как Microsoft®.NET Framework IList<T> (товарные знаки корпорации Microsoft), и могут даже разделять данные способом, который улучшает пространственное местонахождение. Альтернативно, это может быть случай, когда указатели в действительности не являются 0(1), и существует более эффективный способ доступа к данным. Например, рассмотрим дерево, которое реализует интерфейс списка, но для каждого доступа требуется O(log n) обход, чтобы найти требуемый узел. При таких вычислительных затратах на обход можно искать альтернативный способ доступа.

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

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

Самым неблагоприятным сценарием может быть структура данных, которая нуждается в поддержке случайного доступа, в контексте, где инфраструктура обработки общего назначения будет нуждаться в использовании одного линейного счетчика, доступ к которому синхронизирован. Это относится к любому Microsoft®.NET Framework IEnumerable<T>, например, и сильно ограничивает масштабируемость.

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

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

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

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

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

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

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

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

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

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

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

Операционные окружения

Со ссылкой на фиг. 1, операционное окружение 100 для варианта осуществления может включать в себя, например, компьютерную систему 102, которая может быть многопоточной или нет и многопроцессорной или нет. Пользователи 104 могут взаимодействовать с компьютерной системой 102 или с другой компьютерной системой в варианте осуществления с помощью экранов, клавиатур и других периферийных устройств 106. Устройства хранения информации и/или подключенные к сети устройства могут считаться периферийным оборудованием в некоторых вариантах осуществления. Другие компьютерные системы (не показаны), которые сами могут быть многопоточными или нет и многопроцессорными или нет, могут взаимодействовать с компьютерной системой 102 или с другим вариантом осуществления системы с помощью одного или более соединений с сетью 108 через сетевое интерфейсное оборудование, например.

Компьютерная система 102 включает в себя, по меньшей мере, один логический процессор 110. Компьютерная система 102, подобно другим подходящим системам, также включает в себя одно или более запоминающих устройств 112. Запоминающие устройства 112 могут быть энергозависимыми, энергонезависимыми, закрепленными на месте, съемными, магнитными, оптическими и/или других типов. В частности, сконфигурированный носитель 114, такой как CD, DVD, карта памяти или другой съемный энергонезависимый запоминающий носитель, может стать функциональной частью компьютерной системы 102 (когда вставлен или иным образом установлен), делая свое содержимое доступным для использования посредством процессора 110. Съемный сконфигурированный носитель 114 является примером запоминающего устройства 112. Другие примеры запоминающего устройства 112 включают в себя встроенное RAM, ROM, жесткие диски и другие устройства хранения информации, которые нелегко снять пользователям 104.

Носитель 114 сконфигурирован с инструкциями 116, которые исполняются посредством процессора 110. Носитель 114 также сконфигурирован с данными 118, которые создаются, модифицируются, указываются и/или иным образом используются при исполнении инструкций 116. Инструкции и данные формируют часть кода 120, предназначенного для обработки параллельных данных. Код 120 может вызываться приложениями 122 и/или операционными системами 124, например. Данные 118 могут включать в себя структуры данных, содержащие параллельные данные 130, некоторые из которых могут быть организованы посредством разделов 126 данных, каждый из которых имеет особую организационную структуру 128.

Инструкции 116 и данные 118 конфигурируют запоминающее устройство 112/носитель 114, на котором они находятся; когда это запоминающее устройство является функциональной частью данной компьютерной системы, инструкции 116 и данные 118 также конфигурируют эту компьютерную систему. Для ясности иллюстрации, запоминающие устройства 112 показаны в одном блоке на фиг. 1, но будет понятно, что запоминающие устройства могут быть различных физических типов, и что код 120, параллельные данные 130 и другие данные 118, приложения 122 и другие элементы, показанные на чертежах, могут находиться частично или полностью в одном или более запоминающих устройствах 112, таким образом, конфигурируя эти запоминающие устройства.

В данном операционном окружении компьютерная система 102 или другая компьютерная система может запускать одно или более приложений 122, может запускать операционную систему 124 и может использовать любое сетевое интерфейсное оборудование, известное в настоящее время или разработанное в будущем. В частности, приложения 122 могут быть встроенными. Параллельные данные 130 могут присутствовать или могут ожидать извлечения из другого местоположения. Другое программное обеспечение и/или аппаратные средства 132, явно не указанные выше, также могут присутствовать в данной конфигурации.

Операционное окружение может включать в себя одну или более многопоточных компьютерных систем или немногопоточных компьютерных систем. Эти компьютерные системы могут быть кластерными, клиент-серверными сетевыми и/или одноранговыми сетевыми. Некоторые операционные окружения включают в себя автономную (несетевую) компьютерную систему.

Некоторые из подходящих операционных окружений для некоторых вариантов осуществления включают в себя среду Microsoft®.NET (товарные знаки корпорации Microsoft). В частности, предполагается, что некоторые операционные окружения включают в себя программное обеспечение, известное в настоящее время как Parallel Extensions (PFX) для .NET Framework для обработки параллельных компонентов данных, такие библиотеки как Parallel LINQ (PLINQ) или Task Parallel Library (TPL), чтобы допускать включение настраиваемых поставщиков разделения непосредственно в Parallel Extensions для общих типов данных, в .NET Framework (например, для других типов данных типа XML-документов) и в код конечного разработчика. Некоторые подходящие операционные окружения включают в себя окружения Java® (товарный знак Sun Microsystems, Inc.), а некоторые включают в себя окружения, которые используют такие языки как C++ или C-Sharp.

Системы

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

Некоторые варианты осуществления включают в себя сконфигурированный машиночитаемый носитель 114 хранения информации, который является примером запоминающего устройства 112. Запоминающее устройство 112 может включать в себя диски (магнитные, оптические или иные), RAM, EEPROMS или другие ROM и/или другое конфигурируемое запоминающее устройство. Запоминающее устройство 112 общего назначения, которое может быть съемным или нет и может быть энергозависимым или нет, может быть сконфигурировано в вариант осуществления, использующий такие компоненты, как интерфейс 202 разделения данных и программная реализация 204 разделения данных, в форме соответствующих данных 118 и инструкций 116, считываемых со съемного носителя 114 и/или другого источника, такого как сетевое соединение, чтобы таким образом формировать сконфигурированный носитель в форме сконфигурированного запоминающего устройства 112, которое может инструктировать компьютерной системе выполнять этапы способа разделения данных и предоставлять возможности разделения данных способом агностического типа, как раскрыто в данном документе. Фиг. 1-5, таким образом, помогают иллюстрировать варианты осуществления сконфигурированных носителей хранения информации и варианты осуществления способа, а также варианты осуществления системы.

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

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

Как иллюстрировано на фиг. 2, компьютерная система 102 может быть сконфигурирована с интерфейсом 202 разделения данных и программной реализацией 204 разделения данных. Также в иллюстрированной конфигурации присутствуют части 208 данных, содержащие элементы 210 данных. Части 208 данных определены в разделе 126 данных. Раздел 126 данных может рассматриваться как совокупность частей 208 данных, как схема для создания совокупности частей 208 данных или и то, и другое, в зависимости от того, обслуживается ли лучше контекст структурным видом или процедурным видом. Потоки 206 могут использовать процедуры в программной реализации разделения данных, чтобы пытаться осуществлять доступ к отдельным элементам 210 данных данной части 208 данных. Результат 212, возвращаемый посредством попытки доступа, может включать в себя элемент 210 данных, код состояния или и то, и другое.

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

Фиг. 3 показывает несколько возможных заголовков 300 процедур для интерфейса 202 разделения данных. Заголовок 302 процедуры создания раздела определяет интерфейс для одной или более программ, которые будут пытаться создать раздел 126 данных, в котором элементы 210 данных назначаются частям 208 данных. Заголовок 304 процедуры получения элемента данных определяет интерфейс с одной или более программами, которые пытаются извлекать элемент 210 данных из части 208 данных для обработки. Заголовок 310 процедуры поддержки порядковых позиций определяет интерфейс с одной или более программами, которые пытаются предоставить результат, указывающий, может ли быть осуществлен доступ к отдельным элементам 210 данных посредством идентификации их соответствующих порядковых позиций в наборе данных. Заголовок 312 процедуры поддержки динамического разделения определяет интерфейс с одной или более программами, которые пытаются предоставить результат, указывающий, поддерживает ли данный раздел 126 данных добавление и/или удаление частей 208 данных и/или перемещение элементов 210 данных между частями 208 данных после первоначального назначения элементов 210 данных частям 208 данных. Заголовок 320 процедуры уведомления о входе в заблокированное состояние и заголовок 322 процедуры уведомления о выходе из заблокированного состояния определяют интерфейс с одной или более программами, которые пытаются предоставить состояние выполнения (заблокированное/незаблокированное) рабочего потока 206 в коде 120 для обработки параллельных данных 130.

Фиг. 3 также показывает несколько интерфейсов в интерфейсе 202 разделения данных. Интерфейс 306 помощи при разделении, который может включать в себя или передавать значения 308 для помощи при разделении, пытается предоставлять подсказки или руководящие указания для использования при создании раздела 126 данных. Интерфейс 314 получения текущей части пытается предоставить текущий раздел 126 данных. Интерфейс 316 отдельной части данных пытается предоставить доступ к части 208 данных в разделе 126 данных. Интерфейс 318 получения следующего элемента данных пытается получить элемент данных из части данных раздела данных и обновляет переменную состояния, которая используется, чтобы обходить элементы данных, чтобы получать каждый элемент данных по очереди.

Любой или все интерфейсы 306, 314, 316, 318 могут содержать заголовки 300 процедур. В действительности, данный вариант осуществления интерфейса 306, 314, 316, 318 может включать в себя переменные и/или один или более заголовков процедур. Также, переменные могут использоваться в дополнение к, или вместо, заголовкам 302, 304, 310, 312, 320, 322 процедур в некоторых вариантах осуществления. Однако в таком языке, как C-Sharp или Java, сохранение интерфейса 202 разделения данных свободным от предположений о какой-либо конкретной организационной структуре 128 разделения данных может выполняться очень легко в некоторых случаях посредством предпочтительного использования заголовков процедур, а не других способов.

Фиг. 4 показывает некоторые из возможных тел 400 процедур программной реализации 204 разделения данных, которые реализуют операции, представленные в интерфейсе 202 разделения данных. Данный интерфейс 202 разделения данных может иметь более чем одну соответствующую программную реализацию 204 разделения данных, поскольку организационные структуры 128 разделов 126 данных точно не определены в интерфейсе 202 разделения данных, но определены в процедурах программной реализации 204 разделения данных. Тело 402 процедуры создания раздела осуществляет программу, которая пытается создать раздел 126 данных, в котором элементы 210 данных назначены частям 208 данных. Тело 404 процедуры получения элемента данных реализует программу, которая пытается извлечь элемент 210 данных из части 208 данных для обработки. Тело 410 процедуры поддержки порядковых позиций реализует программу, которая пытается предоставить результат, указывающий, может ли быть осуществлен доступ к отдельным элементам 210 данных посредством идентификации их соответствующих порядковых позиций в наборе данных. Тело 412 процедуры поддержки динамического разделения реализует программу, которая пытается предоставить результат, указывающий, поддерживает ли данный раздел 126 данных добавление частей 208 данных и/или перемещение элементов 210 данных между частями 208 данных после первоначального назначения элементов 210 данных частям 208 данных. Тело 420 процедуры уведомления о входе в заблокированное состояние и тело 422 процедуры уведомления о выходе из заблокированного состояния реализуют программы, которые пытаются предоставить состояние выполнения (заблокированное/незаблокированное) рабочего потока 206 в коде 120 для обработки параллельных данных 130.

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

Фиг. 4 также показывает несколько реализаций интерфейсов в программной реализации 204 разделения данных. Программная реализация 406 помощи при разделении пытается предоставлять подсказки или руководящие указания для использования при создании раздела 126 данных. Программная реализация 414 получения текущей части пытается предоставить текущий раздел 126 данных. Программная реализация 416 отдельной части данных пытается предоставить доступ к части 208 данных в разделе 126 данных. Программная реализация 318 получения следующего элемента данных пытается получить элемент данных из части данных раздела данных и в случае успеха обновляет переменную состояния, которая используется, чтобы обходить элементы данных, чтобы получать каждый элемент данных по очереди.

Фиг. 5 показывает конфигурацию с приложением 122, кодом 120 для обработки параллельных данных, параллельные данные 130 для разделения и результаты 212 обработки. В одном варианте осуществления код 120 включает в себя библиотеку параллельной обработки, такую как одна из библиотек поддержки параллельной обработки Microsoft Parallel Extensions для.NET, например, библиотеку Microsoft Parallel LINQ (PLINQ) или Task Parallel Library (TPL), подходящим образом модифицированную согласно учению данного документа. В иллюстрированной конфигурации код 120 для обработки параллельных данных включает в себя код 502 для динамического разделения, но будет понятно, что не каждый вариант осуществления поддерживает динамическое разделение. Код для динамического разделения является одним типом кода 504 разделителя; другие типы кода 504 разделителя могут создавать раздел данных, но делают это без поддержки динамического разделения.

В некоторых вариантах осуществления код 120 для параллельной обработки запрашивает у приложения 122 части 208 данных, затем обрабатывает данные 130, предоставленные приложением, таким образом, создавая результаты 212 вычислений. Хотя фиг. 5 явно показывает результаты 212, возвращенные кодом 120 для параллельной обработки, будет понятно, что другое программное обеспечение, не в последнюю очередь приложение 122, также, как правило, создает результаты вычислений. Действительно, результаты 212, возвращенные кодом 120 параллельной обработки, могут быть переданы программе в приложении 122, которое передает этот результат 212 (или другой результат на основе этого результата 212) другой части приложения 120, таким образом, делая результаты частью приложения 122.

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

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

Обзор методов

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

Во время этапа 602 получения интерфейса разделения данных разработчик программного обеспечения (или код, действующий от лица разработчика) получает интерфейс 202 разделения данных. Этап 602 получения может выполняться посредством включения в него файла, содержащего код, который реализует интерфейс 202 разделения данных, посредством указания по ссылке такого файла, посредством загрузки такого файла или посредством любого механизма для привнесения возможностей программного обеспечения в окружение или в отдельную программу. Понятно, что разработчик - это отдельный тип пользователя 104; конечные пользователи также считаются пользователями 104.

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

Во время этапа 606 ассоциирования программной реализации разделения данных программная реализация 204 разделения данных ассоциируется с интерфейсом 202 разделения данных. Этап 606 ассоциирования может выполняться посредством создания класса, посредством указания по ссылке, посредством установки указателей адреса для программ или посредством любого другого механизма для ассоциирования тела 400 процедуры с заголовком 300 процедуры, так что вызов заголовка процедуры передает управление (а в некоторых случаях может также передавать и параметры) телу процедуры.

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

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

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

Во время этапа 614 попытки получения элемента данных, который может быть результатом этапа 610 вызова, выполняется попытка получить элемент 210 данных. То, какой элемент получается, зависит от программной реализации и текущего содержимого частей 208 данных. Если отдельный элемент должен быть удален, тогда критерии поиска могут быть указаны на этапе 614. Этап 614 попытки получения элемента данных возвращает полученный элемент, если он получен, и может возвращать код состояния. Этап 614 попытки может включать в себя вызов тела 400 процедуры программной реализации 204 разделения данных, такого как тело 404 процедуры получения элемента данных.

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

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

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

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

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

Во время этапа 626 использования процедуры уведомления о блокировке, который может быть результатом этапа 610 вызова, программное обеспечение конфигурируется, чтобы вызывать инструкции программной реализации разделения данных, которые будут помогать коду 120 динамического разделения запрашивать некоторые или все из каких-либо еще не обработанных элементов блока данных, представленного заблокированным потоком 206, и предоставлять их другим потокам, таким образом, поддерживая сбалансированный по нагрузке раздел 126 данных. Этап 624 использования может включать в себя вызов тела 400 процедуры программной реализации 204 разделения данных, такого как одно из тел 420, 422 процедуры уведомления о блокировке.

Во время этапа 628 использования интерфейса помощи при разделении, который может быть результатом этапа 610 вызова, программное обеспечение может предоставлять код 120, например, по меньшей мере, с одним значением 308 для помощи при разделении, чтобы помогать в создании (или в некоторых случаях, динамической корректировке) раздела 126 данных. Этап 628 использования может включать в себя вызов тела 400 процедуры программной реализации 204 разделения данных, такого как тело процедуры в программной реализации 406 помощи при разделении.

Во время этапа 630 исполнения инструкции 116 в программной реализации 204 разделения данных исполняются одним или более процессорами 110.

Во время этапа 632 определения конструктор класса определяется с помощью языка, который поддерживает классы например, C-Sharp или Java.

Примерный код

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

Пример включает в себя три новых интерфейса, использующих C-Sharp в качестве языка программирования:

public interface IPartitionableCollection<T> {

IPartitionedCollection<T> GetInitialPartitions(int p, bool needsOrdinalPosition);

bool SupportsTrackingOrdinalPositions { get; }

bool SupportsDynamicPartitioning { get; }

}

public interface IPartitionedCollection<T> {

IPartition<T>[] CurrentPartitions { get; }

IPartition<T> AddDynamicPartition();

void RemoveDynamicPartition(IPartition<T> p);

}

public interface IPartition<T> {

bool MoveNext(ref T elem);

bool MoveNext(ref T elem, ref int index);

bool TrackingOrdinalPositions { get; }

}

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

Структура данных возвращает объект IPartitionedCollection<T>, который предоставляет результат операции разделения; возвращенный объект может впоследствии быть использован для осуществления доступа к получившимся в результате частям. Возвращенный объект IPartitionedCollection<T> может также быть использован, чтобы добавлять новые динамические части или удалять существующие части, если динамическое разделение поддерживается, как указывается посредством SupportsDynamicPartitioning, возвращающего значение "истина" при запросе. Программная реализация может также быть в форме вспомогательного класса, т.е. она не должна быть реализована посредством структуры данных, содержащей данные. Например, если имеется структура GroceryShoppingList данных, тогда GroceryShoppingList может реализовывать IPartitionableCollection<T>, или GroceryShoppingListPartitioner может реализовывать IPartitionableCollection<T> и передавать GroceryShoppingList в partition.Note, так что IPartition<T> очень похож на IEnumerator<T>, а в действительности может быть одним и тем же в приемлемой реализации, хотя этот пример использует отдельный интерфейс, чтобы сокращать ненужные вызовы методы интерфейса. Например, традиционный вызов IEnumerator<T>.MoveNext, за которым следует Current, становится единственным вызовом IPartition<T>.MoveNext.

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

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

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

Когда код 120, такой как механизм типа PLINQ или TPL, необходим, чтобы разделять такую структуру, содержащую параллельные данные 130, код 120 вызывает GetInitialPartitions по IPartitionableCollection<T>. Вызов передает в качестве параметров p число требуемых частей и указание того, должна ли отслеживаться порядковая позиция. Получающийся в результате разделенный объект содержит p частей в массиве CurrentPartitions. Части 208 данных могут быть идентифицированы посредством номера, дескриптора, строки или другого идентификатора, выбранного кодом разделения данных.

Многие технологии разделения могут заведомо поддерживать доступ к порядковой позиции, но для тех, которые не поддерживают, SupportsTrackingOrdinalPositions будет возвращать ложное значение (означающее, что совокупность не знает порядкового распределения), и альтернативная стратегия может быть использована, чтобы назначать указатели. Один подход предоставляет условие по умолчанию, при котором все части осуществляют доступ к одному и тому же совместно используемому внутреннему счетчику по IPartitionedCollection<T>:

bool MoveNext(ref T elem, ref int index) {

MyPartitionedCollection<T> mpc= ;

if ( has more ) {

elem= next element ;

index=Interlocked.Increment(ref mpc.m_sharedPrivateIndex);

}

return false;

}

Это условие по умолчанию будет использоваться, если GetInitialPartitions вызывался со значением "истина" для needsOrdinalPosition, тем не менее, сама лежащая в основе совокупность возвратила значение "ложь" для SupportsTrackingOrdinalPositions.

В качестве простого примера поставщика рассмотрим поставщика разделения, который работает по List<T>:

class PartitionableList<T>: IParallelPartitionableCollection<T> {

private IList<T> m_list;

public PartitionableList<T>(IList<T> list) { m_list=

list; }

public IPartitionedCollection<T> GetInitialPartitions(

int p, bool needsOrdinalPosition) {

return new PartitionedList<T>(m_list, p);

}

public bool SupportsTrackingOrdinalPositions { get {

return true; } }

public bool SupportsDynamicPartitioning { get { return false; } }

class PartitionedList: IPartitionedCollection<T> {

private List<IPartition<T>> m_parts;

internal PartitionedList(IList<T> list, int p) {

int stride=list.Count/p;

m_parts=new List<IPartition<T>>();

for (int i=0; i < p; i++)

m_parts[i]=new ListPartition<T>(

list, stride*i,

Math.Min(stride*(i+1),data.Length);

}

public IPartition<T>[] CurrentPartitions { get { return m_parts.ToArray(); } }

public IPartition<T> AddDynamicPartition(){throw new NotSupportedException();}}

class ListPartition<T>: IPartition<T> {

private IList<T> m_list;

private int m_curr;

private int m_to;

internal ListPartition(IList<T> list, int from, int to) {

m_list=list;

m_curr=from;

m_to=to;

}

public bool MoveNext(ref T elem, ref int index) {

if (m_curr < m_to) {

elem=m_list[m_curr];

index=m_curr;

m_curr++;

}

return true;

}

public bool TrackingOrdinalPositions { get { return true; } }

}

}

Можно использовать различных готовых внутренних поставщиков для общих типов данных: IList<T>, IEnumerable<T> и массивы, в частности. Другие поставщики Microsoft.Net Framework возможно станут поставщиками разделения общих данных для XML-документов, наборов данных (DataSet) и т.д. Множество API, которые принимают другие типы данных, могут подходить для использования очень эффективных способов по умолчанию, таких как AsParallel библиотеки PLINQ, ForEach библотеки TPL и т.д.

Как правило, ожидается, что неизменным среди всех частей, возвращенных посредством первоначального разделения плюс каких-либо последующих динамических добавлений (через AddDynamicPartition объекта IPartitionedCollection<T>) будет то, что объединение всех элементов 210, перечисленных всеми частями 208 (до тех пор пока MoveNext по ним не возвратит ложное значение), будет законченным набором данных, содержащимся в лежащей в основе совокупности. Также, ожидается, что пересечение будет нулевым. Это также свойственно динамическим добавлениям и удалениям, так что добавление новой части динамически или удаление существующей части не позволит счетчикам двух частей видеть один и тот же элемент. Если первоначальная совокупность содержит два идентичных объекта, в целях этого разделения они рассматриваются как уникальные элементы.

Что касается динамического разделения, рассмотрим примерный код в связи со списком. Простая стратегия разделения элементов на p одинаковых по размеру частей может работать, когда p точно выбрано, когда объем работы, предназначенный для обработки этих p частей, одинаков, и когда существует несколько внешних факторов влияния на исполнение кода, как, например, другие приложения, работающие на тех же ресурсах, потребляющих машинное время. Когда это не так, несбалансированность вычислительной нагрузки может стать проблемой, например, некоторые части могут возвращать ложное значение из MoveNext значительно быстрее, чем другие части. Следовательно, хорошо продуманные программные реализации могут совместно использовать состояние в самом IPartitionedCollection<T>, например, между частями 208, чтобы балансировать нагрузку по итерациям.

Более того, если определяется, что первоначальный размер p был неправильным - например, из-за блокировки потока 206 после обработки части - разделенная на части совокупность, которая поддерживает динамические добавления, позволяет некоторым системам (типа PLINQ или TPL) добавлять новую часть 208. Любые подходящие способы синхронизации могут быть использованы, чтобы обеспечивать часть структуры данных для обработки, в том числе те же механизмы балансировки нагрузки, что и упомянутые выше. В последнем аспекте, например, после того как вышеупомянутый поток разблокируется, эти дополнительные динамические части могут быть удалены, если они больше не считаются необходимыми для оптимальной производительности.

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

Например, предположим, что конкретный код 504 разделителя предусматривает PFX-библиотеку поддержки в коде 120 с четырьмя частями 208 данных почти равного размера, обозначенными P1, P2, P3, P4. Предположим, что PFX запустила исполнение по этим частям с помощью четырех рабочих потоков 206. Предположим также гипотетический профиль исполнения из следующих трех фаз.

Фаза 1 - от T=0 мс до T=50 мс. Предположим, что нет блокировки, и предположим, что каждая из частей наполовину обработана, т.е., половина элементов 210 данных в каждой части обработана в течение фазы 1.

Фаза 2 от T=50 мс до T=100 мс. Первый рабочий поток выполняет блокировку вызова операционной системы (например, операция чтения файла), которая удерживает этот поток заблокированным в течение 50 мс. Другие три рабочих потока 206 продолжают обработку как обычно. В конце этой фазы части P2, P3 и P4 будут полностью обработаны посредством соответствующих рабочих потоков.

Фаза 3 от T=100 мс до T=150 мс. Теперь, когда первый рабочий поток не заблокирован (т.е., вызов чтения файла возвращен), первый рабочий поток продолжает обработку части P1. Поскольку обработка была наполовину выполнена, когда первый рабочий поток стал заблокированным, обработка будет восстановлена с того момента, где она была прекращена, и, следовательно, занимает точно 50 мс, чтобы закончить часть P1, что, в свою очередь, обозначает завершение обработки параллельных данных в этом примере.

Теперь рассмотрим профили использования CPU в этом примере. Во время фазы 1 мы имели 100% использование по всем четырем логическим процессорам 110, поскольку все рабочие потоки 206 работали. Во время фазы 2 один поток был заблокирован, а три продолжали работать, таким образом, использование было равно 75%. Во время фазы 3 только один поток фактически оставался рабочим, таким образом, использование для этого последнего периода, равного 100 мс, упало до 25%.

Причина несбалансированности в том, что первый рабочий поток 206 удерживал абсолютное монопольное использование части P1 в моменты времени, когда этот поток не имел возможности делать какую-либо реальную работу, а также в моменты времени, когда он мог передавать некоторые из данных другим потокам, чтобы ускорить работу. Например, разделяя оставшуюся работу поровну между четырьмя потоками вместо оставления всей работы первому потоку, фаза 3 может закончиться последней из обработки в одну четвертую времени, т.е. в течение 12,5 мс вместо 50 мс.

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

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

Interface IPartition

{

void NotifyBlockingEntry();

void NotifyBlockingExit();

}

Соответствующие тела 420, 422 процедур будут отправлять сигнал, устанавливать флаг или иначе делать известной доступность для других потоков элементов данных, расположенных в настоящий момент в части данных, назначенной разрешающему потоку, который собирается стать заблокированным. Эти уведомления управляются кодом-разделителем 504 данных, так что логика динамического разделения может потребовать какие-либо еще не обработанные элементы 210 блока данных, представленного этим экземпляром IPartition, и предоставлять их другим потокам, потенциально в качестве новых объектов IPartition. Это разрешение совместного использования продолжается только до тех пор, пока соответствующий вызов NotifyBlockingExit() не будет выполнен из PFX, после чего IPartition.MoveNext() будет продолжать работать как обычно, за исключением того, что если какие-либо элементы 210 этой части 208 были переданы в другие потоки, первоначальный владелец этой части (разрешающий поток) никогда не примет эти элементы из MoveNext() после разблокировки.

Больше информации о вариантах осуществления

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

Некоторые варианты осуществления предоставляют способ, который может быть использован разработчиком программного обеспечения, чтобы конфигурировать разделение параллельных данных 130. Способ включает в себя этап 602 получения интерфейса 202 разделения данных, такого как IPartitionableCollection<T>, IPartitionedCollection<T> и IPartition<T>, в качестве группы, или иначе некоторой группы из другого интерфейса(ов), которые предоставляют похожую функциональность. В частности, способ включает в себя получение 604, по меньшей мере, одного заголовка 300 процедуры для вызова процедуры, чтобы создавать раздел 126 данных, и получение 604, по меньшей мере, одного заголовка 300 процедуры для вызова процедуры, чтобы получать элемент 210 данных из части 208 данных, определенной разделом данных. "Процедура" может быть закодирована как функция или как пустая процедура, например.

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

Способ этих вариантов осуществления также включает в себя ассоциирование 606 с интерфейсом 202 разделения данных программной реализации 204 разделения данных, такой как PartitionableList<T>, PartitionedList и ListPartition<T>. В частности, способ включает в себя ассоциирование 608, по меньшей мере, одного тела 400 процедуры, которая реализует создание раздела 126 данных, и, по меньшей мере, одного тела 400 процедуры, которая реализует получение элемента 210 данных из части 208 данных. Организационная структура раздела 126 данных, включающая в себя структуру данных, которая содержит элементы данных и правила или эвристику для разделения элементов данных между частями, точно указывается в программной реализации 204 разделения данных.

Некоторые способы дополнительно включают в себя конфигурирование 616 программного обеспечения, чтобы вызывать инструкции программной реализации разделения данных, такие как IPartitionableCollection<T>.SupportsTrackingOrdinalPosition, чтобы указывать, поддерживает ли раздел 126 данных доступ к элементу 210 данных на основе порядковой позиции элемента данных.

Некоторые способы дополнительно включают в себя конфигурирование 618 программного обеспечения, чтобы вызывать инструкции программной реализации разделения данных, такие как IPartitionableCollection<T>.SupportsDynamicPartitioning, чтобы указывать, поддерживает ли раздел данных динамическое разделение. Некоторые способы включают в себя конфигурирование программного обеспечения, такого как код 502 динамического разделения, чтобы вызывать инструкции программной реализации разделения данных, которые выполняют динамическое разделение, чтобы содействовать балансировке нагрузки.

Некоторые способы дополнительно включают в себя конфигурирование программного обеспечения, чтобы использовать 628 интерфейс 306 помощи при разделении, чтобы передавать, по меньшей мере, одно значение 308 для помощи при разделении в инструкции программной реализации разделения данных, например, код 504 разделителя. Некоторые примеры значения 308 для помощи при разделении включают в себя: время обработки в сравнении с числом распределений элементов данных; предпочтительные схемы разделения; схемы разделения, которых необходимо избегать; заблокированное/незаблокированное состояние потока, предоставленное посредством механизма 424 перераспределения; нумерация возможных характеристик обработки элементов данных (постоянные издержки на элемент, {линейно, экспоненциально} x {увеличение, уменьшение}, непостоянные ) без какой-либо параметризации; и параметрическое описание характеристик обработки (например, "непостоянная с верхней границей X и нижней границей Y").

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

Некоторые способы включают в себя определение 632 конструктора для класса, который реализует конкретную организационную структуру разделения данных, такую как ListPartition<T>.

Некоторые варианты осуществления предоставляют компьютерную систему 102 с параллельными данными 130, организованными в разнородные части (например, согласно множественным организационным структурам 128). Система включает в себя, по меньшей мере, одно запоминающее устройство 112, сконфигурированное, по меньшей мере, с исполняемыми инструкциями 116, и, по меньшей мере, один логический процессор 110, сконфигурированный, чтобы исполнять, по меньшей мере, часть инструкций для разделения данных; некоторые системы включают в себя множество логических процессоров.

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

Некоторые системы также включают в себя одну программную реализацию 204 разделения данных. Другие системы включают в себя две или более программных реализаций 204 разделения данных в запоминающем устройстве, каждая из которых, однако, согласуется и ассоциирована с одним и тем же интерфейсом 202 разделения данных. Первая программная реализация 204 разделения данных включает в себя инструкции, которые реализуют создание первого раздела 126 данных, и инструкции, которые реализуют получение элемента 210 данных из части 208 данных первого раздела данных. Первый раздел данных имеет первую организационную структуру 128, которая указывается в первой программной реализации разделения данных. Также, вторая программная реализация 204 разделения данных включает в себя инструкции, которые реализуют создание второго раздела 126 данных, и инструкции, которые реализуют получение элемента 210 данных из части 208 данных второго раздела данных. Второй раздел данных имеет вторую организационную структуру 128, которая указывается во второй программной реализации разделения данных и которая также отличается от первой организационной структуры. Например, первая организационная структура может быть разделенной на слои, в то время как вторая - разделенной на порции, но оба раздела данных создаются с помощью одного и того же интерфейса 202.

В некоторых системах интерфейс 202 разделения данных включает в себя заголовок 310 процедуры поддержки порядковых позиций, такой как IPartitionableCollection<T>.SupportsTrackingOrdinalPositions, для вызова инструкций 116 программной реализации 204 разделения данных, таких как ListPartition<T>.TrackingOrdinalPositions(), которые указывают, поддерживает ли раздел 126 данных доступ к элементу 210 данных части 208 данных на основе порядковой позиции элемента данных.

В некоторых системах интерфейс 202 разделения данных включает в себя заголовок 312 процедуры поддержки динамического разделения, такой как IPartitionableCollection<T>.SupportsDynamicPartitioning(), для вызова инструкций 116 программной реализации 204 разделения данных, таких как PartitionedList.AddDynamicPartition(), которые указывают, поддерживает ли раздел 126 данных динамическое разделение в форме добавления части 208 данных к ранее созданной группе частей данных в разделе 126 данных.

В некоторых системах интерфейс 202 разделения данных включает в себя определение интерфейса для получения текущего раздела данных, такой как интерфейс 314 получения текущих частей, содержащий свойство получения текущих частей, как, например, IPartitionedCollection.CurrentPartitions[]. "Определение интерфейса" может быть, например, открытым интерфейсом C-Sharp или классом с открытыми свойствами или может быть похожей конструкцией на другом языке программирования.

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

В некоторых системах интерфейс 202 разделения данных включает в себя определение интерфейса для получения текущего раздела данных, такой как интерфейс 318 получения следующего элемента данных, содержащий свойство получения следующего элемента данных, как, например, один из способов IPartition<T>.MoveNext().

Сконфигурированные носители

Некоторые варианты осуществления предоставляют носитель хранения информации, сконфигурированный с компьютерными данными и компьютерными инструкциями, такими как данные 118 и инструкции 116, для выполнения способа предоставления семантики ограничения блокировки, как обсуждалось выше. Носитель хранения информации, который конфигурируется, может быть запоминающим устройством 112, например, и в частности, может быть съемным носителем 114 хранения информации, таким как CD, DVD или флэш-память.

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

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

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

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

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

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

В некоторых вариантах осуществления способ включает в себя исполнение инструкций, таких как тела 420, 422 процедур уведомления о блокировке или некоторый другой код, реализующий механизм 424 повторного разделения, посредством которого разрешающий поток 206 может предоставлять другим потокам разрешение на обработку элементов 210 данных, которые ранее были назначены разрешающему потоку. В некоторых вариантах осуществления подсказки о блокировке потока будут нацелены скорее на интерфейс разделения данных (например, IPartition), чем на интерфейс разделителя (например, IPartitionableCollection), или, по самой меньшей мере, подсказки о блокировке ассоциируются с конкретным экземпляром части данных. В некоторых вариантах осуществления значения 308 подсказок предоставляются для конфигурирования конкретного интерфейса разделителя, например, так, что разделитель на порции совместно используемой библиотеки может отлично работать, скажем, с монотонно увеличивающимися распределениями.

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

Заключение

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

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

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

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

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

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

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

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