RU2011117765A

RU2011117765A - Устройство (варианты) и способ реализации двухпроходного планировщика задач линейной сложности

Info

Publication number: RU2011117765A
Application number: RU2011117765/08A
Authority: RU
Inventors: Юрий Сергеевич Шуткин (RU); Юрий Сергеевич Шуткин; Павел Александрович Алисейчик (RU); Павел Александрович Алисейчик; Эльяр Эльдарович Гасанов (RU); Эльяр Эльдарович Гасанов; Илья Владимирович Незнанов (RU); Илья Владимирович Незнанов; Андрей Павлович Соколов (RU); Андрей Павлович Соколов; Павел Анатольевич Пантелеев (RU); Павел Анатольевич Пантелеев
Original assignee: ЭлЭсАй Корпорейшн (US); ЭлЭсАй Корпорейшн
Priority date: 2011-05-05
Filing date: 2011-05-05
Publication date: 2012-11-10
Also published as: US20120284731A1; US8850437B2

Abstract

1. Способ реализации двухпроходного планировщика задач линейной сложности, включающий: ! (A) присвоение каждой из названных задач соответствующему одному или нескольким из множества процессоров при первом прохождении названных задач, где названное первое прохождение является неитеративным; ! (B) перераспределение названных задач среди названных процессоров для сокращения соответствующей нагрузки на один или несколько из названных процессоров при втором прохождении названных задач, где названное второе прохождение (i) является неитеративным и (ii) начинается после завершения первого прохождения; и ! (C) генерирование графика в ответ на вышеупомянутое присвоение и вышеупомянутое перераспределение, где названный график закрепляет названные задачи за названными процессорами. ! 2. Способ по п.1, отличающийся тем, что сложность планирования названных задач является линейной в зависимости, как от числа названных задач, так и от числа названных процессоров. ! 3. Способ по п.1, дополнительно включающий генерирование списка вышеупомянутых задач перед вышеупомянутым первым прохождением, где названный список сортируется по множеству соответствующих длин названных задач. ! 4. Способ по п.3, отличающийся тем, что вышеупомянутое присвоение названных задач вышеупомянутым процессорам при названном первом прохождении выполняется в порядке, определенном вышеупомянутым списком. ! 5. Способ по п.4, отличающийся тем, что самая длинная из названных задач назначается первой, а самая короткая из названных задач назначается последней. ! 6. Способ по п.1, отличающийся тем, что во время вышеупомянутого первого прохождения (i) вышеупомян�

Claims

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

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

(B) перераспределение названных задач среди названных процессоров для сокращения соответствующей нагрузки на один или несколько из названных процессоров при втором прохождении названных задач, где названное второе прохождение (i) является неитеративным и (ii) начинается после завершения первого прохождения; и

(C) генерирование графика в ответ на вышеупомянутое присвоение и вышеупомянутое перераспределение, где названный график закрепляет названные задачи за названными процессорами.

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

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

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

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

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

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

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

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

10. Устройство для реализации двухпроходного планировщика задач линейной сложности, содержащее:

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

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

11. Устройство по п.10, отличающееся тем, что сложность планирования названных задач является линейной в зависимости, как от числа названных задач, так и от числа названных процессоров.

12. Устройство по п.10, отличающееся тем, что (i) названная схема дополнительно сконфигурирована для генерирования списка вышеупомянутых задач перед вышеупомянутым первым прохождением и (ii) названный список сортируется по множеству соответствующих длин названных задач.

13. Устройство по п.12, отличающееся тем, что вышеупомянутое присвоение названных задач вышеупомянутым процессорам при названном первом прохождении выполняется в порядке, определенном вышеупомянутым списком.

14. Устройство по п.13, отличающееся тем, что самая длинная из названных задач назначается первой, а самая короткая из названных задач назначается последней.

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

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

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

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

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

20. Устройство для реализации двухпроходного планировщика задач линейной сложности, содержащее:

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

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

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