masterspammer (masterspammer) wrote,
masterspammer
masterspammer

Немножко про планирование

Итак, описывая языком обычным.

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

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

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

А теперь начинается самое интересное...



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

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

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

Дальше-больше - пусть теперь у работников разная производительность (или даже пусть она одинаковая сама по себе, но один работник всё время делает перекуры, второй успевает ответить на 4-5 телефонных звонков, а третий после завершения собственно покраски пишет отчёт о том, как всё было хорошо и в срок покрашено.

В таком случае время выполнения работы начинает зависеть и от того, кто её делает. Закрепим за каждым работником его "участок" - пусть каждый делает одну и ту же часть работы в следующий раз. Точно так же будем менять размер этой части в зависимости от относительной скорости её выполнения. Всё как и раньше (пока мы считали производительность работников одинаковой), но есть приятные моменты:

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

Теперь начинается программистская жесть:

Есть массив указателей [0...N), на элементы, которые надо обработать и K процессоров/ядер. Поделим задачу на K частей (по примерно (N+1)/K элементов) и запустим их параллельно.

Элементы не равны между собой по вычислительной сложности и если один поток отработал в 2 раза быстрее, чем остальные, работавшие равное время, то 1/2K процессорного времени потеряно. Если же в 2 раза дольше - потерялось (K-1)/2K; обычно всё не так фатально, но 5-10% восьмипроцессорной системы идут вникуда.

Алгоритм такой - после завершения всех потоков измерить разницу по времени выполнения между самым быстрым и самым медленным потоками; если она велика (например больше 10%), то от самого медленного отнять сколько-то элементов, от второго по медленности - отнять в 2 раза меньше; аналогично добавить двум самым быстрым
если она мала (иначе) - от самого медленного отнять один элемент и отдать самому быстрому.

Пример - пусть у нас есть 100 элементов и 4 потока, тогда распределение сначала будет (25,25,25,25)
Пусть первый поток работал немного медленнее, а последний - быстрее, тогда распределение для следующего шага станет (24,25,25,26).

Измерение времени - microtime.
Привязка потока к процессору (cpu affinity) - pthreads - как и сама многопоточность.

P.S. А было это к последнему абзацу (не считая P.S.) отсюда.

Tags: awav, Планы
Subscribe

  • 3D в La Scala

    Это вот про такую картинку - где сзади стенки сходятся и зажимают треугольный рассекатель. И вот ещё про что.…

  • Немарксизм (не путать с неомарксизмом)

    Есть у меня такая привычка - сомневаться, что классы это классы; другими словами, что из принадлежности к классу следуют нетривиальные выводы,…

  • (no subject)

    Прокрастинация она прокрастинация и есть... а у меня она на остатках сил и в последнюю очередь (ну не умею я) - "заточил" 8 деталек под 62…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments