Алгоритм планирования заданий на процессорах

Согласно комментарию Эрлиха (кстати, спасибо), термин "планирование" может вводить в заблуждение, и это может быть более подходящим описанием: учитывая матрицу N*N, найдите перестановку строк, которая даст наибольшую диагональную сумму.

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

Я пытаюсь найти расписание (распределение 1-к-1), которое максимизирует общую сумму IPC. Я могу сделать это, перебрав все возможные расписания с O(N!), что нецелесообразно.

Затем я попытался использовать алгоритм «стабильного сопоставления» O (N ^ 2), используя IPC для сортировки рабочих нагрузок и предпочтений процессоров. Он работает очень быстро и возвращает приличное расписание, но не оптимальное.

Мои вопросы:

1) Я действительно ожидал, что алгоритм стабильного сопоставления сможет вернуть оптимальное назначение. Может кто-нибудь объяснить, почему это не удается? Мое лучшее предположение на данный момент — это существование связей между разными парами (задание, процессор). Я также безуспешно пробовал алгоритм «стабильного сопоставления с безразличием». Я должен упомянуть, что алгоритм не дает сбоев из-за моей реализации. Я ищу более теоретический ответ на вопрос, почему сам алгоритм не может решить эту проблему.

2) Знаете ли вы алгоритм, который я могу использовать для этого? Он вообще существует?


job-scheduling algorithm np-complete
person prodromou    schedule 29.06.2017    source источник
comment
Для этого есть целая отрасль информатики. На самом деле это изначально происходит от управления производством. Рекомендуем прочитать en.wikipedia.org/wiki/Scheduling_(computing) для начала.   -  person iehrlich    schedule 29.06.2017
comment
Спасибо, это выглядит весьма полезным. Однако после быстрого просмотра оказалось, что все представленные алгоритмы являются эвристическими и не гарантируют, что они вернут оптимальное расписание.   -  person prodromou    schedule 29.06.2017
comment
Я сказал для начала неспроста :) И еще, как проверить, оптимально ли расписание?   -  person iehrlich    schedule 29.06.2017
comment
Ой, подождите, значит, N рабочих мест и N процессоров не — это опечатка...   -  person iehrlich    schedule 29.06.2017
comment
Нет, это не опечатка. У меня одинаковое количество процессоров и заданий, и я ищу, чтобы каждому назначить ровно одно задание. Я запускаю алгоритм O(N!) на небольших входных данных (4,8,16 процессоров), чтобы определить оптимальное расписание. Я должен, вероятно, упомянуть, что все задания были ранее запущены и профилированы для каждого процессора, поэтому мне не нужно запускать их каждый раз. Я просто оцениваю возвращенный график.   -  person prodromou    schedule 29.06.2017
comment
Меня больше всего интересует, почему алгоритм стабильного сопоставления не может быть честным. Я почти уверен, что нет хорошего способа решить эту проблему. Венгерский алгоритм выглядит многообещающе ( O(N^4) ), но я не хочу его реализовывать только для того, чтобы понять, что он тоже не работает :).   -  person prodromou    schedule 29.06.2017
comment
В данном случае термин «планирование» вводит в заблуждение. На самом деле это не имеет никакого отношения к планированию заданий — это чисто математическая задача — данной матрице N*N найти перестановку строк, которая даст наибольшую диагональную сумму.   -  person iehrlich    schedule 29.06.2017
comment
Кроме того, если вас интересует, почему алгоритм дает сбой, вы должны предоставить сбойный код с вводом, фактическим выводом и желаемым выводом.   -  person iehrlich    schedule 29.06.2017
comment
Это очень похоже на проблему TSP, если вы используете динамическое программирование для ее решения.   -  person tnt    schedule 29.06.2017
comment
если вы просто хотите быстро создать прототип, в scipy есть реализация венгерского алгоритма, поэтому вам не нужно реализовывать его самостоятельно.   -  person c2huc2hu    schedule 29.06.2017

Ответы (1)


arrow_upward
2
arrow_downward

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

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

Венгерский алгоритм на самом деле является правильным для поиска глобально оптимального решения.

person btilly    schedule 29.06.2017
comment
Спасибо за объяснение! Я только что попробовал венгерский алгоритм, используя реализацию scipy. Он возвращает оптимальное расписание (я думаю, что реализация scipy может быть O (N ^ 3), но я не уверен). Спасибо iehrlich и user3080953 за очень ценные комментарии. И спасибо вам, конечно, btilly! - person prodromou; 29.06.2017
comment
Просто к вашему сведению, мне пришлось отказаться от измерений IPC, поскольку венгерский алгоритм минимизирует стоимость (вместо того, чтобы максимизировать ее). - person prodromou; 29.06.2017