Восемь простых правил разработки многопоточных приложений

 

Клэй Бреширс (Clay Breshears)

 

Введение


Методы реализации многопоточности, используемые специалистами Intel, включают в себя четыре основных этапа: анализ, разработка и реализация, отладка и настройка производительности. Именно такой подход используется для создания многопоточного приложения из последовательного программного кода. Работа с программными средствами в ходе выполнения первого, третьего и четвертого этапов освещена достаточно широко, в то время как информации по реализации второго шага явно недостаточно.

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

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

 

Правило 1. Выделите операции, выполняемые в программном коде независимо друг от друга


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

Рассмотрим ещё один пример – рабочий цикл пункта проката DVD-дисков, в который приходят заказы на определённые фильмы. Заказы распределяются между работниками пункта, которые ищут эти фильмы на складе. Естественно, если один из работников возьмёт со склада диск, на котором записан фильм с участием Одри Хепбёрн, это никоим образом не затронет другого работника, ищущего очередной боевик с Арнольдом Шварценеггером, и уж тем более не повлияет на их коллегу, находящегося в поисках дисков с новым сезоном сериала «Друзья». В нашем примере мы считаем, что все проблемы, связанные с отсутствием фильмов на складе, были решены до того, как заказы поступили в пункт проката, а упаковка и отправка любого заказа не повлияет на обработку других.

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

 

Правило 2. Применяйте параллельность с низким уровнем детализации


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

В подходе «снизу-вверх» реализуется многопоточная обработка «горячих» точек кода. Если параллельное разделение найденных точек невозможно, нужно исследовать стек вызовов приложения, чтобы определить другие сегменты, доступные для параллельного разделения и выполняющиеся достаточно долгое время. Предположим, вы работаете над приложением, предназначенным для сжатия графических изображений. Сжатие можно реализовать с помощью нескольких независимых параллельных потоков, обрабатывающих отдельные сегменты изображения. Однако даже если вам удалось реализовать многопоточность «горячих» точек, не пренебрегайте анализом стека вызовов, в результате которого можно найти доступные для параллельного разделения сегменты, находящиеся на более высоком уровне программного кода. Таким образом, вы сможете увеличить степень детализации параллельной обработки.

В подходе «сверху-вниз» анализируется работа программного кода, и выделяются его отдельные сегменты, выполнение которых приводит к завершению всей поставленной задачи. Если явная независимость основных сегментов кода отсутствует, проанализируйте их составляющие части для поиска независимых вычислений. Проанализировав программный код, вы сможете определить модули кода, на выполнение которых уходит больше всего процессорного времени. Рассмотрим реализацию поточной обработки в приложении, предназначенном для кодирования видео. Параллельная обработка может быть реализована на самом низком уровне – для независимых пикселей одного кадра, или на более высоком – для групп кадров, которые можно обработать независимо от других групп. Если приложение создаётся для одновременной обработки нескольких видеофайлов, параллельное разделение на таком уровне может оказаться ещё проще, а детализация будет иметь самую низкую степень.

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

 

Правило 3. Закладывайте в свой код возможности масштабирования, чтобы его производительность росла с ростом количества ядер.


Не так давно, помимо двухъядерных процессоров, на рынке появились четырёхъядерные. Более того, Intel уже объявила о создании процессора с 80 ядрами, способного выполнять триллион операций с плавающей точкой в секунду. Поскольку количество ядер в процессорах будет со временем только расти, ваш программный код должен иметь соответствующий потенциал для масштабируемости. Масштабируемость – параметр, по которому можно судить о способности приложения адекватно реагировать на такие изменения, как увеличение системных ресурсов (количество ядер, объём памяти, частота шины и проч.) или увеличение объёма данных. Учитывая, что количество ядер в процессорах будущего увеличится, создавайте масштабируемый код, производительность которого будет расти благодаря увеличению системных ресурсов.

Перефразируя один из законов Норткота Паркинсона (C. Northecote Parkinson), можно сказать, что «обработка данных занимает все доступные системные ресурсы». Это означает, что при увеличении вычислительных ресурсов (например, количества ядер), все они, вероятнее всего, будут использоваться для обработки данных. Вернёмся к приложению для сжатия видео, рассмотренному выше. Появление у процессора дополнительных ядер вряд ли скажется на размере обрабатываемых кадров – вместо этого увеличится число потоков, обрабатывающих кадр, что приведёт к уменьшению количества пикселей на поток. В результате, из-за организации дополнительных потоков, возрастет объем служебных данных, а степень детализации параллелизма снизится. Ещё одним более вероятным сценарием может стать увеличение размера или количества видеофайлов, которые нужно будет кодировать. В этом случае организация дополнительных потоков, которые будут обрабатывать более объёмные (или дополнительные) видеофайлы, позволит разделить весь объём работ непосредственно на том этапе, где произошло увеличение. В свою очередь, приложение с такими возможностями будет иметь высокий потенциал для масштабируемости.

Разработка и реализация параллельной обработки с использованием декомпозиции данных обеспечивает повышенную масштабируемость по сравнению с использованием функциональной декомпозиции. Количество независимых функций в программном коде чаще всего ограничено и не меняется в процессе выполнения приложения. Поскольку каждой независимой функции выделяется отдельный поток (и, соответственно, процессорное ядро), то с увеличением количества ядер дополнительно организуемые потоки не вызовут прироста производительности. Итак, модели параллельного разделения с декомпозицией данных обеспечат повышенный потенциал для масштабируемости приложения благодаря тому, что с увеличением количества процессорных ядер возрастёт объём обрабатываемых данных.

Даже если в программном коде организована поточная обработка независимых функций, вероятна возможность использования дополнительных потоков, запускаемых при увеличении входной нагрузки. Вернёмся к примеру со строительством дома, рассмотренному выше. Своеобразная цель строительства – завершить ограниченное количество независимых задач. Однако, если поступило указание возвести в два раза больше этажей, вам наверняка захочется нанять дополнительных рабочих некоторых специальностей (маляров, кровельщиков, сантехников и проч.). Следовательно, вам нужно разрабатывать приложения, которые могут адаптироваться под декомпозицию данных, возникающую в результате увеличения нагрузки. Если в вашем коде реализована функциональная декомпозиция, предусмотрите организацию дополнительных потоков при увеличении количества процессорных ядер.

 

Правило 4. Применяйте поточно-ориентированные библиотеки


Если для обработки данных в «горячих» точках кода может понадобиться какая-либо библиотека, обязательно подумайте об использовании готовых функций вместо собственного кода. Одним словом, не пытайтесь изобрести велосипед, разрабатывая сегменты кода, функции которых уже предусмотрены в оптимизированных процедурах из состава библиотек. Многие библиотеки, в том числе Intel® Math Kernel Library (Intel® MKL) и Intel® Integrated Performance Primitives (Intel® IPP), уже содержат многопоточные функции, оптимизированные под многоядерные процессоры.

Стоит заметить, что при использовании процедур из состава многопоточных библиотек необходимо убедиться, что вызов той или иной библиотеки не повлияет на нормальную работу потоков. То есть, если вызовы процедур осуществляются из двух различных потоков, в результате каждого вызова должны возвращаться правильные результаты. Если же процедуры обращаются к общим переменным библиотеки и обновляют их, возможно возникновение «гонки данных», которая пагубно отразится на достоверности результатов вычислений. Для корректной работы с потоками библиотечная процедура добавляется как новая (то есть не обновляет ничего, кроме локальных переменных) или синхронизируется для защиты доступа к общим ресурсам. Вывод: перед тем, как использовать в своём программном коде какую-либо библиотеку стороннего производителя, ознакомьтесь с приложенной к ней документацией, чтобы убедиться в ее корректной работе с потоками.

 

Правило 5. Используйте подходящую модель многопоточности


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

Минусом явной многопоточности является невозможность точного управления потоками.

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

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

 

Правило 6. Результат работы программного кода не должен зависеть от последовательности выполнения параллельных потоков


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

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

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

 

Правило 7. Используйте локальное хранение потоков. При необходимости назначайте блокировки на отдельные области данных


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

Необходимость совместного использования временных переменных разными потоками возникает достаточно редко. Такие переменные необходимо объявлять или выделять локально каждому потоку. Переменные, значения которых являются промежуточными результатами выполнения потоков, также должны быть объявлены локальными для соответствующих потоков. Для суммирования этих промежуточных результатов в какой-то общей области памяти потребуется синхронизация. Чтобы минимизировать возможные нагрузки на систему, предпочтительно обновлять эту общую область как можно реже. Для методов явной многопоточности предусмотрены прикладные программные интерфейсы локального хранения потоков, обеспечивающие целостность локальных данных с начала выполнения одного многопоточного сегмента кода до начала выполнения следующего сегмента (или в процессе обработки одного вызова многопоточной функции до следующего выполнения этой же функции).

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

Как поступить, если возникла необходимость синхронизировать доступ к большому объёму данных, например, к массиву, состоящему из 10000 элементов? Организовать единственную блокировку для всего массива – значит наверняка создать узкое место в приложении. Неужели придётся организовывать блокировку для каждого элемента в отдельности? Тогда, даже если к данным будут обращаться 32 или 64 параллельных потока, придётся предотвращать конфликты доступа к довольно большой области памяти, причём вероятность возникновения таких конфликтов – 1%. К счастью, существует своеобразная золотая середина, так называемые «блокировки по модулю». Если используется N блокировок по модулю, каждая из них будет синхронизировать доступ к N-й части общей области данных. Например, если организовано две таких блокировки, одна из них будет предотвращать доступ к чётным элементам массива, а вторая – к нечётным. В таком случае, потоки, обращаясь к необходимому элементу, определяют его чётность и устанавливают соответствующую блокировку. Количество блокировок по модулю выбирается с учётом количества потоков и вероятности одновременного обращения нескольких потоков к одной и той же области памяти.

Заметим, что для синхронизации доступа к одной области памяти не допускается одновременное использование нескольких механизмов блокировки. Вспомним закон Сегала: «Человек, имеющий одни часы, твердо знает, который час. Человек, имеющий несколько часов, ни в чём не уверен». Предположим, что доступ к переменной контролируют две различные блокировки. В этом случае первой блокировкой может воспользоваться один сегмент кода, а второй – другой сегмент. Тогда потоки, выполняющие эти сегменты, окажутся в ситуации гонки за общие данные, к которым они одновременно обращаются.

 

Правило 8. Измените программный алгоритм, если это требуется для реализации многопоточности


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

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

В качестве иллюстрации последнего утверждения рассмотрим умножение двух квадратных матриц. Алгоритм Штрассена имеет один из лучших асимптотических порядков выполнения: O(n2.81), который намного лучше, чем порядок O(n3) алгоритма с обычным тройным вложенным циклом. Согласно алгоритму Штрассена, каждая матрица делится на четыре подматрицы, после чего производится семь рекурсивных вызовов для перемножения n/2 × n/2 подматриц. Для распараллеливания рекурсивных вызовов можно создать новый поток, который последовательно выполнит семь независимых перемножений подматриц, пока они не достигнут заданного размера. В таком случае количество потоков будет экспоненциально возрастать, а степень детализации вычислений, выполняемых каждым вновь образованным потоком, будет повышаться с уменьшением размера подматриц. Рассмотрим другой вариант – организацию пула из семи потоков, работающих одновременно и выполняющих по одному перемножению подматриц. По завершению работы пула потоков происходит рекурсивный вызов метода Штрассена для умножения подматриц (как и в последовательной версии программного кода). Если в системе, выполняющей такую программу, будет больше восьми процессорных ядер, часть из них будет простаивать.

Алгоритм перемножения матриц гораздо проще подвергать параллельному разделению с помощью тройного вложенного цикла. В этом случае применяется декомпозиция данных, при которой матрицы делятся на строки, столбцы или подматрицы, а каждый из потоков выполняет определённые вычисления. Реализация такого алгоритма осуществляется с помощью прагм OpenMP, вставляемых на каком-либо уровне цикла, или явной организацией потоков, выполняющих деление матриц. Для реализации этого более простого последовательного алгоритма потребуется гораздо меньше доработок в программном коде, по сравнению с реализацией многопоточного алгоритма Штрассена.

 

Выводы


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

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

 

 

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.