Алгоритм оптимального распараллеливания задач на несколько потоков

@Suppir · Регистрация: 08.08.2011

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

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

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

Кто знает, есть ли подобные готовые алгоритмы?

@korep · 25.06.2014, 17:17

конечно есть.
вот это например посмотрите

@Suppir · 25.06.2014, 17:17 **[ТС]**

Алгоритм должен учитывать:
1) количество ядер в процессоре;
2) список задач. Для каждой задачи известна сложность (например, программа обрабатывает файлы, известны размеры файлов);

Добавлено через 13 секунд
korep,
не открывается ссылка.

@korep · 25.06.2014, 17:20

алгоритм оптимизации потоков процессора
это в гугле введите там куча ссылок.

@Dmitriy_M · 26.06.2014, 10:43

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

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

Не факт. Сложная задача может задействовать и все ядра.

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

2) список задач. Для каждой задачи известна сложность (например, программа обрабатывает файлы, известны размеры файлов);

Размер файла это не сложность, это объем данных, и не всегда есть зависимость между объемом работ и сложностью.

@Suppir · 26.06.2014, 12:11 **[ТС]**

Размер файла для примера привел. Допустим, задача - написать парсер для файлов. Время обработки файла обычно пропорционально его размеру. Известен список файлов, размеры каждого файла.

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

@Dmitriy_M · 26.06.2014, 12:26

Suppir, про thread pool не слышал?
Создаешь количество потоков равное количество потоков процессора + 1.

@Suppir · 26.06.2014, 12:30 **[ТС]**

Я сейчас как раз использую ThreadPool. Но он неоптимально распределяет - загрузка процессора не более 60 - 70% получается.

А зачем создавать количество потоков процессора +1?

И использую просто количество логических ядер процессора:

C#

1 2	int cores = Environment.ProcessorCount; ThreadPool.SetMaxThreads(cores, cores);

@Igor3D · 26.06.2014, 14:50

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

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

Как правило неизвестно заранее сколько времени будет выполняться та или иная задача. Если известно - да, лучше большие первыми как Вы сказали.

Основная проблема (о которой не упоминалось) в том что не так уж просто "дать следующую задачу", это довольно затратно если кластеры малы. У Вас мин время = 1 сек т.е. огромно, и этой проблемы нет. Поэтому не буду пускаться в дальнейшие объяснения

@Dmitriy_M · 26.06.2014, 14:54

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

Но он неоптимально распределяет - загрузка процессора не более 60 - 70% получается.

Он вообще не распределяет.
Возможно стоит поиграться с количеством потоков.

@Suppir 28 / 28 / 11 Регистрация: 08.08.2011 Сообщений: 1,173
		1
	Алгоритм оптимального распараллеливания задач на несколько потоков 25.06.2014, 17:11. Показов 807. Ответов 9 Метки нет (Все метки) Имеем 4-ядерный процессор и 100 задач. Задачи разные по сложности - могут выполняться от 1 до 10 секунд каждая. Необходимо равномерно загружать 4 ядра процессора задачами - таким образом, чтобы постоянно была максимальная загрузка, ядра процессора не простаивали, и общее время работы было минимальным. Мне представляется, что, например, сложные задачи (которые медленно выполняются) нужно накидывать на процессор в первую очередь. Потому что если сначала раскидать мелкие задачи, а потом останется одна сложная, то она загрузит только одно ядро процессора, а остальные три будут простаивать. Ну, и много аналогичных оптимизаций можно учесть. Кто знает, есть ли подобные готовые алгоритмы? 0

@korep 52 / 45 / 18 Регистрация: 06.01.2013 Сообщений: 626
	25.06.2014, 17:17	2
	конечно есть. вот это например посмотрите 0

@Suppir 28 / 28 / 11 Регистрация: 08.08.2011 Сообщений: 1,173
	25.06.2014, 17:17 [ТС]	3
	Алгоритм должен учитывать: 1) количество ядер в процессоре; 2) список задач. Для каждой задачи известна сложность (например, программа обрабатывает файлы, известны размеры файлов); Добавлено через 13 секунд korep, не открывается ссылка. 0

@korep 52 / 45 / 18 Регистрация: 06.01.2013 Сообщений: 626
	25.06.2014, 17:20	4
	алгоритм оптимизации потоков процессора это в гугле введите там куча ссылок. 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	26.06.2014, 10:43	5
	Сообщение от Suppir Потому что если сначала раскидать мелкие задачи, а потом останется одна сложная, то она загрузит только одно ядро процессора, а остальные три будут простаивать Не факт. Сложная задача может задействовать и все ядра. Сообщение от Suppir 2) список задач. Для каждой задачи известна сложность (например, программа обрабатывает файлы, известны размеры файлов); Размер файла это не сложность, это объем данных, и не всегда есть зависимость между объемом работ и сложностью. 0

@Suppir 28 / 28 / 11 Регистрация: 08.08.2011 Сообщений: 1,173
	26.06.2014, 12:11 [ТС]	6
	Размер файла для примера привел. Допустим, задача - написать парсер для файлов. Время обработки файла обычно пропорционально его размеру. Известен список файлов, размеры каждого файла. Добавлено через 27 секунд Один файл можно обрабатываться только в рамках одного потока. 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	26.06.2014, 12:26	7
	Suppir, про thread pool не слышал? Создаешь количество потоков равное количество потоков процессора + 1. 0

@Igor3D 1864 / 764 / 105 Регистрация: 01.10.2012 Сообщений: 4,121
	26.06.2014, 14:50	9
	Сообщение от Suppir Имеем 4-ядерный процессор и 100 задач. Задачи разные по сложности - могут выполняться от 1 до 10 секунд каждая. Необходимо равномерно загружать 4 ядра процессора задачами - таким образом, чтобы постоянно была максимальная загрузка, ядра процессора не простаивали, и общее время работы было минимальным. Как правило неизвестно заранее сколько времени будет выполняться та или иная задача. Если известно - да, лучше большие первыми как Вы сказали. Основная проблема (о которой не упоминалось) в том что не так уж просто "дать следующую задачу", это довольно затратно если кластеры малы. У Вас мин время = 1 сек т.е. огромно, и этой проблемы нет. Поэтому не буду пускаться в дальнейшие объяснения 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	26.06.2014, 14:54	10
	Сообщение от Suppir Но он неоптимально распределяет - загрузка процессора не более 60 - 70% получается. Он вообще не распределяет. Возможно стоит поиграться с количеством потоков. 0