В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)

@DaskOFF · Регистрация: 02.05.2012

Author24 — интернет-сервис помощи студентам

Есть задачка:

Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При i=1,..,M задание i требует ti времени для его выполнения. Определить оптимальный порядок заданий, т.е. такой, который дает возможность завершить все задания в кратчайшее время.

Я прикинул, и у меня есть 2 способа решения задачи, но 1 долгий, а второй рассматривает не все варианты.
1) Полный перебор перестановок, и вывод только тех последовательностей, время выполнения которых минимально, но допустим при 14 задачах мы имеем 87 178 291 200 вариантов последовательностей и они будут очень долго перебираться.

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

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?

@Dani · 23.07.2013, 22:18

Сообщение от DaskOFF

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

Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.

@DaskOFF · 23.07.2013, 22:27 **[ТС]**

Сообщение от Dani

Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.

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

Перестановки. Допустим изначальная последовательность загрузки задач следующая: {1, 2, 3, 4, 5}
вот варианты перестановок(всего их будет 5! = 120) : {1, 2, 3, 5, 4} {1, 2, 5, 3, 4} {1, 2, 5, 4, 3} и т.д.

@Dani · 23.07.2013, 22:29

DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...

@DaskOFF · 23.07.2013, 22:39 **[ТС]**

Сообщение от Dani

DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...

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

@Dani · 23.07.2013, 22:41

Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?

@DaskOFF · 23.07.2013, 22:50 **[ТС]**

Сообщение от Dani

Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?

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

а по моему варианту если будет (N - порядок задач, а T время их выполнения)
N = {3, 4, 1, 2}
T = {8, 8, 4, 3}
то тут уже получается 2 решения
1 - {3, 4, 1, 2}
2 - {4, 3, 1, 2}

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

@Kukurudza · 24.07.2013, 07:03

все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша):
сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример:
4 7 2 5 7 9 2 1 5 6 8 3 2 7 8
9 8 8 7 7 7 6 5 5 4 3 2 2 2 1
первый процессор получил: 9 7 4 3 2
второй процессор получил: 8 7 6 2
третий процессор получил: 8 7 5 2 1
вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше)

@salam · 24.07.2013, 07:08

ваша задача максимизировать количество таких моментов t_i, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно.
для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени.
то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N²), решается динамикой. N - количество процессов.

@Kukurudza · 24.07.2013, 07:16

Сообщение от salam

это требует O(N2), решается динамикой.

вы уверены в том что нельзя быстрее?

@Thinker · 24.07.2013, 07:56

ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным.
Посмотрите книгу

Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)

эта задача из темы экстремальных задач на графах.

@salam · 24.07.2013, 13:08

Сообщение от Kukurudza

вы уверены в том что нельзя быстрее?

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

Добавлено через 16 минут

Сообщение от Thinker

Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)
эта задача из темы экстремальных задач на графах.

я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?

@Dani · 24.07.2013, 13:12

Thinker, что значит "экстремальные задачи"? np-полные?

@salam · 24.07.2013, 13:29

Сообщение от Kukurudza

вы уверены в том что нельзя быстрее?

в общем получается что-то вроде O(N * SumT), где N - количество процессов, SumT - суммарное время их выполнения. в масштабах этой задачи время маленькое.

@Kukurudza · 24.07.2013, 13:37

Сообщение от salam

O(N * SumT)

а что тут делает SumT?
а можно алгоритм увидеть?

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

@Thinker · 24.07.2013, 15:03

Сообщение от salam

я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?

пусть имеется n камней (потоков) и m кучек (процессоров). сложность алгоритма $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(mn^2)$ Эта оценка приведена у Стивена Скиена.

Сообщение от Dani

Thinker, что значит "экстремальные задачи"? np-полные?

просто автор так главу назвал. В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"

NP-сложные задачи несколько иные.

@Dani · 24.07.2013, 15:18

Сообщение от Thinker

NP-сложные задачи несколько иные.

это я курсе

Мало ли кто-то доказал, что p = np

@DaskOFF · 24.07.2013, 16:20 **[ТС]**

Спасибо, сейчас почитаю книги, может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач? (про np-полные задачи, прочел на вики, но понял мало)

Сортировка по убыванию и правда не подходит, дали вот такой контрпример, который этот способ не проходит
{10 10 10 10 7 6 6}

Нашел алгоритм, который выполняется ~2 секунды(на моей машине) при 25 задачах, но я не понимаю, как этот алгоритм получен
функция получения следующей последовательности
seq - последовательность задающая порядок задач

C

int next(int *seq)
{
  static int t = 1;
  int i = M-2;
  while(i>=0 && seq[i] > seq[i+1])
    i--;
  
  if(i>=0)
  {
    int j = i+1;
    
    while(j<M-1 && seq[j+1] > seq[j])
      j++;
   
    swap(seq+i, seq+j);
   
    for(j=i+1; j<= (M+i-1)/2; j++)
      swap(seq+j, seq+(M-j+i));
  
    return 1;
  }
  else
    return 0;
}

@Thinker · 24.07.2013, 19:43

Сообщение от Dani

это я курсе Мало ли кто-то доказал, что p = np

Не по теме:

ну, да, в 2010 году чуть сенсацией не стала работа индийского математика (выкладываю ссылку, так как сам автор выложил в сеть свою статью)
http://www.win.tue.nl/~gwoegi/... alikar.pdf
ну а в ней нашли прорехи
http://www.open.by/it/33980

теперь непонятно будет ли разрешена эта проблема.

@DaskOFF · 25.07.2013, 20:15 **[ТС]**

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

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	24.07.2013, 07:56	11
	Сообщение было отмечено как решение Решение ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным. Посмотрите книгу Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247) эта задача из темы экстремальных задач на графах. 4

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
		1
	В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) 23.07.2013, 21:53. Показов 2895. Ответов 25 Метки нет (Все метки) Есть задачка: Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При i=1,..,M задание i требует ti времени для его выполнения. Определить оптимальный порядок заданий, т.е. такой, который дает возможность завершить все задания в кратчайшее время. Я прикинул, и у меня есть 2 способа решения задачи, но 1 долгий, а второй рассматривает не все варианты. 1) Полный перебор перестановок, и вывод только тех последовательностей, время выполнения которых минимально, но допустим при 14 задачах мы имеем 87 178 291 200 вариантов последовательностей и они будут очень долго перебираться. 2) Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково. Вопрос в том, правилен ли второй способ(или я что-то упустил)? И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)? 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	23.07.2013, 22:18	2
	Сообщение от DaskOFF Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково. Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его. 1

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
	23.07.2013, 22:27 [ТС]	3
	Сообщение от Dani Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его. процессоры одинаковые, следовательно, очередная задача выполняется одинаковое время на любом из них Перестановки. Допустим изначальная последовательность загрузки задач следующая: {1, 2, 3, 4, 5} вот варианты перестановок(всего их будет 5! = 120) : {1, 2, 3, 5, 4} {1, 2, 5, 3, 4} {1, 2, 5, 4, 3} и т.д. 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	23.07.2013, 22:29	4
	DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время... 1

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
	23.07.2013, 22:39 [ТС]	5
	Сообщение от Dani DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время... ну как, получаю перестановку и в этом порядке добавляю задачи на первый освобождающийся процессор 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	23.07.2013, 22:41	6
	Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14? 1

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
	23.07.2013, 22:50 [ТС]	7
	Сообщение от Dani Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14? ограничений нет, в том то и дело, заданий может быть 100, именно поэтому я и в растерянности, первый находит все варианты, но очень долго для 100 он несколько лет наверно будет подбирать последовательности. а по моему варианту если будет (N - порядок задач, а T время их выполнения) N = {3, 4, 1, 2} T = {8, 8, 4, 3} то тут уже получается 2 решения 1 - {3, 4, 1, 2} 2 - {4, 3, 1, 2} вот как эти все варианты перебрать из полученной последовательности N я не знаю, а если узнаю не факт, что это будет быстро, хотя и быстрее, чем порождать все перестановки 0

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 539
	24.07.2013, 07:03	8
	все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша): сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример: 4 7 2 5 7 9 2 1 5 6 8 3 2 7 8 9 8 8 7 7 7 6 5 5 4 3 2 2 2 1 первый процессор получил: 9 7 4 3 2 второй процессор получил: 8 7 6 2 третий процессор получил: 8 7 5 2 1 вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше) 1

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	24.07.2013, 07:08	9
	ваша задача максимизировать количество таких моментов t_i, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно. для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени. то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N²), решается динамикой. N - количество процессов. 1

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 539
	24.07.2013, 07:16	10
	Сообщение от salam это требует O(N2), решается динамикой. вы уверены в том что нельзя быстрее? 1

	25.07.2013, 20:15

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	24.07.2013, 13:08	12
	Сообщение от Kukurudza вы уверены в том что нельзя быстрее? я дал грубую оценку. сейчас попробую точнее определить сложность решения, которое я подразумевал. другого, более быстрого, решения этой задачи лично я не вижу. не могу отрицать, что оно существует. но вариант "отсортировать и попорядку..." точно не полностью корректный. Добавлено через 16 минут Сообщение от Thinker Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247) эта задача из темы экстремальных задач на графах. я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги? 1

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	24.07.2013, 13:12	13
	Thinker, что значит "экстремальные задачи"? np-полные? 1

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	24.07.2013, 13:29	14
	Сообщение от Kukurudza вы уверены в том что нельзя быстрее? в общем получается что-то вроде O(N SumT), где N - количество процессов, SumT* - суммарное время их выполнения. в масштабах этой задачи время маленькое. 1

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 539
	24.07.2013, 13:37	15
	Сообщение от salam O(N * SumT) а что тут делает SumT? а можно алгоритм увидеть? Добавлено через 52 секунды странно просто, если время задач измеряется в секундах то ок, если то же самое только в годах, то что-то не очень 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	24.07.2013, 15:03	16
	Сообщение от salam я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги? пусть имеется n камней (потоков) и m кучек (процессоров). сложность алгоритма $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(mn^2)$ Эта оценка приведена у Стивена Скиена. Сообщение от Dani Thinker, что значит "экстремальные задачи"? np-полные? просто автор так главу назвал. В книге Стивен Скиена. Алгоритмы. эта задача в главе "Динамическое программирование" NP-сложные задачи несколько иные. 1

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	24.07.2013, 15:18	17
	Сообщение от Thinker NP-сложные задачи несколько иные. это я курсе Мало ли кто-то доказал, что p = np 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	24.07.2013, 19:43	19
	Сообщение от Dani это я курсе Мало ли кто-то доказал, что p = np Не по теме: ну, да, в 2010 году чуть сенсацией не стала работа индийского математика (выкладываю ссылку, так как сам автор выложил в сеть свою статью) http://www.win.tue.nl/~gwoegi/... alikar.pdf ну а в ней нашли прорехи http://www.open.by/it/33980 теперь непонятно будет ли разрешена эта проблема. 1

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
	25.07.2013, 20:15 [ТС]	20
	Up может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач? 0

В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)

Решение