Параллельный способ выполнения операций

Распараллеливание задач. Случай «идеальной параллельности». Часть 1

Распараллеливание кода без зависимостей

Введение

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

Рассмотрим некоторый цикл, в котором обрабатываются данные:

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

Такое же определение можно отнести и к аналогичному foreach-циклу; из него же вытекает, что порядок вычисления итераций неважен.

Подходы к реализации параллельного цикла

Попробуем реализовать сами метод для выполнения цикла параллельно, и посмотрим, с какими трудностями мы при этом столкнёмся.

Итак, мы собираемся создать метод наподобие такого:

1. public static void ParallelFor ( int from, int to, Action int > body ) ;

Он должен будет выполнить body для всех значений в интервале от from до to (не включая последнее), при этом распараллелив их выполнение на несколько потоков, чтобы добиться максимальной производительности. Насколько же возможно это распараллелить?

Определение степени параллелизма

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

Такой подход — по потоку на ядро во многих случаях верен, хотя и базируется на идеалистичной модели вычислений, когда все потоки занимаются только вычислениями на процессоре. Однако, иногда может быть полезно иметь и больше потоков. Например, в случае, если потоки в своей работе половину времени проводят в ожидании ресурсов, то процессор всё равно простаивает в это время, и увеличение количества рабочих потоков может привести к улучшению производительности.

Таким образом, выходит что стоит начинать с простого варианта «один поток на ядро», но быть готовым к рассмотрению и других стратегий.

Для того, чтобы получить количество доступных ядер, мы можем воспользоваться свойством System.Environment.ProcessorCount. Надо отметить, что оно возвращает количество ядер с учётом Hyper-threading, то есть, в случае его наличия, будет возвращено «логическое», уже удвоенное количество ядер.

С учётом вышесказанного, вот логичная (хотя несколько наивная) реализация:

1. public static void ParallelFor ( int from, int to, Action int > body )
2. <
3. // определяемся с количество потоков и размером блока данных для каждого потока
4. int size = to — from ;
5. int numProcs = Environment. ProcessorCount ;
6. int range = size / numProcs ;
7. // разбиваем данные, запускаем все потоки и ждём завершения
8. var threads = new List Thread > ( numProcs ) ;
9. for ( int p = 0 ; p numProcs ; p ++ )
10. <
11. int start = p * range + from ;
12. int end = ( p == numProcs — 1 ) ?
13. to : start + range ;
14. threads. Add ( new Thread ( ( ) =><
15. for ( int i = start ; i end ; i ++ ) body ( i ) ;
16. > ) ) ;
17. >
18. foreach ( var thread in threads ) thread. Start ( ) ;
19. foreach ( var thread in threads ) thread. Join ( ) ;
20. >

Важным недостатком такой версии является создание/завершение новых потоков каждый раз, так как это довольно затратная операция (в частности, каждый поток резервирует 1М памяти в стеке, даже если в данный момент не выполняется ни одной функции на нём).

Другая проблема тоже вытекает из создания новых потоков. Предположим, что в body нам передали некий код, который тоже содержит вызов ParallelFor. В таком случае, в процессе выполнения будет создано уже не numProcs потоков, а в два раза больше, и может возникнуть ситуация, когда затраты на переключение между потоками будут слишком велики («чрезмерная многопоточность»).

Статическое распредение итераций

1. public static void ParallelFor ( int from, int to, Action int > body )
2. <
3. int size = to — from ;
4. int numProcs = Environment. ProcessorCount ;
5. int range = size / numProcs ;
6. int remaining = numProcs ;
7. // объект синхронизации, для определения завершения работы
8. using ( ManualResetEvent mre = new ManualResetEvent ( false ) )
9. <
10. // создаём все задания
11. for ( int p = 0 ; p numProcs ; p ++ )
12. <
13. int start = p * range + from ;
14. int end = ( p == numProcs — 1 ) ? to : start + range ;
15. ThreadPool. QueueUserWorkItem ( delegate <
16. for ( int i = start ; i end ; i ++ )
17. body ( i ) ;
18. // проверяем, не последнее ли это задание выполнилось
19. if ( Interlocked. Decrement ( ref remaining ) == 0 )
20. mre. Set ( ) ;
21. > ) ;
22. >
23. // Ждём, пока все задания выполнятся
24. mre. WaitOne ( ) ;
25. >
26. >

Такое решение уже лишено проблем с чрезмерной многопоточностью и с затратами на создание потоков. Что ещё может помешать в данной ситуации максимально быстрой отработке данного цикла?

В случае, если все итерации небольшие по времени и приблизительно одинаково затратные, приведённый подход близок к оптимальному.

А если мы представим себе, что некоторые итерации завершаются быстро, а некоторые — во много раз дольше, то в таком случае тот поток из пула, которому не повезло быть исполнителем большего количества «долгих» итераций, будет работать в несколько раз дольше остальных. При этом, так как время работы всей параллельной операции определяется временем работы самой медленной её составляющей, то в итоге остальные потоки будут простаивать, сделав всю «свою» работу, в то время как один «невезучий» будет задерживать всех.

Чтобы в такой ситуации обеспечить минимальное время работы, нужно

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

Динамическое распределение итераций

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

Такой подход можно проиллюстрировать этим кодом:

1. public static void ParallelFor ( int from, int to, Action int > body )
2. <
3. int numProcs = Environment. ProcessorCount ;
4. // количество оставшихся
5. int remainingWorkItems = numProcs ;
6. int nextIteration = from ;
7. using ( ManualResetEvent mre = new ManualResetEvent ( false ) )
8. <
9. // создаём задания
10. for ( int p = 0 ; p numProcs ; p ++ )
11. <
12. ThreadPool. QueueUserWorkItem ( delegate
13. <
14. int index ;
15. // отбираем по одному элементу на выполнение
16. while ( ( index = Interlocked. Increment ( ref nextIteration ) — 1 ) to )
17. <
18. body ( index ) ;
19. >
20. if ( Interlocked. Decrement ( ref remainingWorkItems ) == 0 )
21. mre. Set ( ) ;
22. > ) ;
23. >
24. // ждём, пока отработают все задания
25. mre. WaitOne ( ) ;
26. >
27. >

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

Сбалансированный подход

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

Вот вариант её кода. Идея в том, что «порцию» мы делаем несколько больше, чем просто один элемент, но меньше, чем в случае статического распределения.

1. public static void ParallelFor ( int from, int to, Action int > body )
2. <
3. int numProcs = Environment. ProcessorCount ;
4. int remainingWorkItems = numProcs ;
5. int nextIteration = from ;
6. // размер «порции» данных
7. const int batchSize = 3 ;
8. using ( ManualResetEvent mre = new ManualResetEvent ( false ) )
9. <
10. for ( int p = 0 ; p numProcs ; p ++ )
11. <
12. ThreadPool. QueueUserWorkItem ( delegate <
13. int index ;
14. while ( ( index = Interlocked. Add ( ref nextIteration, batchSize ) — batchSize ) to )
15. <
16. int end = index + batchSize ;
17. if ( end >= to )
18. end = to ;
19. for ( int i = index ; i end ; i ++ )
20. body ( i ) ;
21. >
22. if ( Interlocked. Decrement ( ref remainingWorkItems ) == 0 )
23. mre. Set ( ) ;
24. > ) ;
25. >
26. mre. WaitOne ( ) ;
27. >
28. >

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

Заключение

В любом случае, оптимальные настройки для конкретного случая определяются природой вычислений. Но компромиссный вариант с динамической раздачей более-менее крупных «порций» работы может оказаться вполне приемлемым для большинства ситуаций. Именно так реализованы библиотечные методы параллельного выполнения циклов в .NET 4, о которых пойдёт речь во второй части статьи.

Источник

Технологическая операция Последовательный параллельный и последовательно параллельный способы выполнения (стр. 1 из 3)

1.Теоретический вопрос. Технологическая операция. Последовательный, параллельный и последовательно-параллельный способы выполнения операций

Список использованных источников

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

Классический марксизм придавал большое значение изучению роли техники в развитии общества, рассматривая ее познание как основу познания производительных сил и постижения социальных явлений. Именно это обстоятельство имел в виду К. Маркс, когда писал: «Технология вскрывает активное отношение человека к природе , непосредственный процесс производства его жизни, а вместе тем и его общественных деловой жизни и проистекающих из них духовных представлений». [1]

Если, с одной стороны, техника и технология формируются в полном соответствии с законами объективного мира, как его часть, то с другой стороны, в них запечатлевается также и вся «субъективность» человеческой деятельности (цели, опыт, науки, принципы, организации и разделения труда).

Цель контрольной работы – ознакомиться с теоретическим материалом предмета «Системы технологий» и приобрести практические навыки в решении задач данной дисциплины.

Технологическая операция. Последовательный, параллельный и последовательно–параллельный способы выполнения операций.

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

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

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

Объектом могут быть глина, руда, свекла, волокно, ткань, заготовки. То есть сырье.

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

Если же объектом обработки является минеральное сырье, например, руда, то дробление руды является операцией.

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

Технологические операции разделяются на отдельные составляющие. Наиполный набор составляющих имеют технологические операции резанье, к которым относится заточка. Во время изготовления детали резаньем на токарном станке составляющими операции заточки являются выставлением, технологический и дополнительный переходы.

Операция производственная — обособленная и законченная часть (элемент) трудового процесса, выполняемая одним или группой исполнителей на одном рабочем месте при неизменном предмете труда. По отношению к предмету труда или назначению Операция производственная классифицируются на: технологические — выполнение которых изменяет качественное состояние, форму, размеры или расположение в пространстве предмета труда; транспортные —связанные с перемещением предмета труда в заданном направлении; обслуживающие — направленные на обеспечивание необходимых условий для нормального хода производственного процесса и безопасности людей; контрольно-учетные — для установления соответствия свойств предметов труда заданным требованиям, приемки (сдачи) работ или продукции; по хранению — выполняемые в период образования запасов предмета труда на промежуточных или конкретных складах. По степени механизации и автоматизации производственного процесса или участия в нем рабочего Операции производственные делятся на ручные, ручные механизированные, машинно-ручные, машинные, автоматизированные и аппаратурные. Различают операции по связи с производством (основные, вспомогательные и обслуживающие), по месту исполнения, применяемым машинам и другим признакам. Классификация Операция производственная позволяет решать вопросы совершенствования производственного процесса, создания машин и оборудования, способствующих сокращению производственного цикла. Количество операций, без осуществления которых невозможно превращать предметы труда в готовую продукцию, должно быть минимальным. Операции группируются в комплексы или фазы — их совокупность, обособленную составом применяемого оборудования, содержанием выполняемой работы или местом ее исполнения. При изучении и проектировании операции расчленяют: в трудовом отношении — на приемы, трудовые действия и движения; в технологическом — на переходы и проходы. Прием (трудовой) — это законченная совокупность трудовых действий исполнителя, характеризующаяся непрерывным выполнением и целевой направленностью, неизменным предметом труда. Это четко обозначенная часть Операция производственная. При более углубленном изучении способов выполнения отдельных приемов их расчленяют не только на трудовые действия, но и на трудовые движения. Трудовое движение — однократное перемещение исполнителя, его корпуса, головы, ног, рук или пальцев в процессе трудовой деятельности (один поворот рукоятки управления, один шаг, взяться за деталь и т.п.). Трудовое действие — совокупность трудовых движений, выполняемых без перерыва для осуществления части приема. Переход (технологический) —часть производственной операции, выполняемая над одной или одновременно несколькими поверхностями одним или одновременно несколькими инструментами без изменения режима работы (настройки) оборудования, технологии и объема работ. Переходы расчленяются на проходы —покоряющиеся части перехода, например снятие слоя металла (материала) с обрабатываемой поверхности. Степень расчленения Операции производственной на элементы зависит от конкретных задач и требуемой точности изучения затрат рабочего времени.

По способу выполнения технологических операций различают – параллельный, последовательный и параллельно-последовательный способ выполнения операций. (Рис. 1)

Рис. 1 Способы выполнения операций.

в) последовательно- параллельный.

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

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

Стратегической программой развития предприятия намечено производство нового вида продукции. С этой целью был объявлен конкурс вариантов внедрения новой технологии. Ограничивающим условием являлся максимальный размер капитальных вложений (сумма собственных и заемных средств). Были представлены два варианта проекта внедрения технологической линии по производству новой продукции. На основании приведенных в проектах данных:

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

2. определить критическую программу выпуска, при которой затраты по каждому из вариантов равны, и проиллюстрировать решение графически:

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

Исходные данные к задаче 1

Вариант контрольной работы №
№п/п	Наименование показателя	Един.измер.	Условн.обозн.	Проект 1	Проект 2
1	Годовая производительность технологической линии	тыс. ед.	D	620	380
2	Общий объем капитальных затрат	тыс. грн.	K	460	760
3	Нормативный срок окупаемости затрат	лет	T	4	4
Технологическая себестоимость
4	Условно постоянные расходы, мес	тыс. грн.	C	140	136
5	Переменные расходы на еденицу продукции	грн.	V	3.35	0.81

1. Суммарные годовые затраты по каждому проекту вычисляются согласно формуле (1.1)

Источник