Многоядерные процессоры здесь, и они здесь, чтобы остаться. Отраслевые тенденции показывают, что каждое ядро может стать меньше и медленнее (см. Мой пост, чтобы понять причину). Повышение производительности одной программы с многоядерностью требует, чтобы программа была разделена на потоки, которые могут работать одновременно на нескольких ядрах. По сути, это ставит проблему нахождения параллелизма в коде для программистов. Я заметил, что многие разработчики оборудования не понимают проблем MT (так как они никогда не писали приложений MT). Этот пост должен показать им верхушку этого массивного айсберга.
Обновление 26.05.2011: я также написал пример для параллельного программирования, который может вас заинтересовать.
Почему найти параллелизм сложно?
Некоторые задания легко распараллелить, например, если одному парню нужно 8 часов, чтобы нарисовать комнату, то два парня, работающие параллельно, могут нарисовать ее за четыре часа. Аналогично, два программных потока могут преобразовывать изображение из цветного в оттенки серого в 2 раза быстрее, одновременно работая над разными половинами изображения. Примечание. Программы, попадающие в эту категорию, уже распараллеливаются, например, научные вычислительные нагрузки, графика, фотошоп и даже приложения с открытым исходным кодом, такие как ImageMagick .
Есть также другие программы, которые являются последовательными по своему характеру, например, два парня не смогут готовить в 2 раза быстрее, чем один парень, потому что задача не полностью распараллеливаема: существуют зависимости между задачами, и повара в конечном итоге ждут друг друга в раз. К сожалению, у многих программ есть искусственные зависимости между задачами, потому что программисты написали их с мыслью ST. Например, рассмотрим этот фрагмент кода из справочного кода H.264 (я удалил ненужные детали, чтобы подчеркнуть мою точку зрения):
|
1
2
3
4
5
6
7
8
9
|
macroclock_output_data mb; //Global variablefor (...) // The OUTER loop decode_slice(...); if(mb->last_mb_in_slice) break;void decode_slice(...) ... mb = ... |
Обратите внимание, как переменная mb записывается на каждой итерации, и ни одна итерация не использует mb, записанную предыдущими итерациями. Тем не менее, mb был объявлен как глобальная переменная, вероятно, чтобы избежать ее повторного размещения и освобождения. Это разумная оптимизация ST. Однако с точки зрения MT итерации цикла цикла OUTER теперь имеют зависимость друг от друга и не могут выполняться параллельно. Чтобы распараллелить этот код, программист должен сначала определить, что зависимость является искусственной. Затем он / она должен проверить тысячи строк кода, чтобы убедиться, что это предположение не ошибочно. Наконец, он / она должен изменить весь код, чтобы сделать mb локальной переменной для каждой итерации. Все это трудно достичь (я распараллелил H.264 для этой статьи).
Итак, вот статус: оставление искусственных зависимостей в коде ограничивает параллелизм, ошибочное удаление реального нарушает программу, а достижение идеального баланса требует чрезмерных усилий. Поскольку сложно определить все зависимости с первого раза, они делают ошибки и начинается отладка.
Почему отладка сложна?
Отладка многопоточного кода очень трудна, потому что ошибки появляются случайно. Учтите следующее:
Скажем, два потока T0 и T1 должны увеличивать переменную X. Код C / C ++ / JAVA для этого будет
|
1
|
X = X + 1 |
Их код сборки будет выглядеть следующим образом: (инструкции помечены как AF).
| T0 | T1 | ||
| Нагрузка X, R0 | D | Нагрузка A, R0 | |
| В | Инкремент R0 | Е | Инкремент R0 |
| С | Магазин R0, X | F | Магазин R0, A |
Программист хочет, чтобы X был увеличен на 2 после завершения обоих потоков. Однако когда потоки выполняются одновременно, их инструкции могут чередоваться в любом порядке. окончательное значение X зависит от перемежения (предположим, что X было 0 до того, как два потока попытались увеличить). Например,
ABCDEF: X = 2 (правильно)
DEAFBC: X = 1 (неверно)
ADBCEF: X = 1 (неверно)
По существу, существует зависимость, что D не должен выполняться до C (или A не должно происходить до F). Программист упустил эту зависимость. Однако в половине случаев код работает нормально, что делает невозможным отслеживание ошибки или тестирование исправления. Более того, традиционные методы отладки, такие как printf и gdb, становятся бесполезными, потому что они нарушают работу системы, тем самым изменяя поведение кода и часто маскируя ошибку.
Почему оптимизация производительности так важна и сложна?
Единственная цель МТ — производительность. Очень часто первая рабочая версия параллельного кода работает медленнее, чем последовательная версия. Есть две общие причины:
Все еще слишком много зависимостей (реальных или искусственных): программисты часто итеративно удаляют зависимости, а иногда даже переписывают всю программу, чтобы уменьшить эти зависимости.
Конфликт за аппаратный ресурс. Потоки также могут быть сериализованы, если существует конкуренция за некоторый аппаратный ресурс, такой как общий кэш. Программисты должны выявлять и уменьшать это утверждение. Обратите внимание, что выявление этих узких мест является особенно сложной задачей, поскольку счетчики производительности оборудования не являются надежными.
После нескольких итераций код становится достаточно хорошим для достижения цели производительности.
Работа на этом не заканчивается ..
В отличие от ST-кода, который ускоряется при каждом поколении процессов, MT-код имеет сложные недетерминированные взаимодействия, которые могут привести к значительным колебаниям производительности при изменении аппаратного обеспечения. Например, у меня был алгоритм ветвления и привязки (решатель из 16 головоломок), который замедлялся с большим количеством ядер, потому что алгоритм работал бы по другому пути, когда было запущено больше потоков. Даже простое ядро, такое как вычисление гистограммы, может вести себя очень по-разному при разных входах или конфигурации машины (см. Эту статью ). Таким образом, параллельные программисты также обременены задачей обеспечения устойчивости своего кода к изменениям.
Вывод
Моя цель здесь состояла не в том, чтобы научить параллельному программированию, а просто дать представление о том, что нужно для написания хорошей параллельной программы. Это действительно сложная работа, и я утверждаю, что невозможно оценить трудности без написания параллельной программы. Для тех, кто еще не написал, вот мой призыв к действию:
Напишите параллельную программу для вычисления точечного произведения двух массивов и его точного масштабирования, 4-кратного ускорения на 4-ядерном процессоре и т. Д. Это просто, но вы узнаете больше, чем ожидаете.
Ищите ключевые слова: pthreads или winthreads, чтобы узнать синтаксис в Linux или Windows соответственно. Поделитесь своим опытом!
Обновление 30.05.2011: Спасибо всем за ваши отзывы и читателей. Я написал третий пост по параллельному программированию. Описывается профильное решение для выбора наилучшей детализации задачи в параллельных программах.
Справка: Что делает параллельное программирование трудным? от нашего партнера JCG Aater Suleman в блоге Future Chips .