Параллельное программирование как образ мышления

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

В середине XX века Мур сформулировал достаточно известный закон, который говорит о том, что каждые два года количество транзисторов в процессоре будет увеличиваться двукратно. У этого закона есть достаточно очевидные следствия. У нас есть некоторая плата, на которой есть процессор, внутри — транзисторы. И если это количество увеличивается, то либо они становятся меньше, либо процессор становится больше. Рост линейных размеров процессора по какой-то причине невыгоден производителям. И процессоры со временем становятся более плотными с точки зрения количества транзисторов. Это приводит к тому, что эти процессоры увеличиваются в разрядности: были 8-битные процессоры, 16, 32. Сейчас почти у всех в компьютерах 64-битные процессоры.

В 2002 году Intel предприняла последнюю попытку получить выгоду от многозадачности на одном ядре. У вас есть одно ядро, и вам надо сделать так, чтобы два независимых процесса начали работать на нем быстрее, чем если бы они работали порознь. Они выпустили такую технологию, как гиперпоточность, которая до сих пор применяется, однако была «костылем» в эволюции процессоров. В 2005 году произошел скачок, и процессоры стали двухъядерные. Сейчас они 4-, 8-ядерные и так далее. Надо сказать, что многопроцессорные системы существовали и гораздо раньше. Сеймур Крей разрабатывал суперкомпьютеры с распределенной памятью еще в глубокие 1970–1980 годы. И понятно, что в специфических областях (вычислительная наука) многопроцессорные системы существовали довольно давно. Именно поэтому в 1994 году появился стандарт MPI для параллельного программирования с распределенной памятью. В 1997 году оформился стандарт Open MP для параллельного программирования с общей памятью. Однако только в 2005 году фактически случился скачок, который привел к тому, что интересы суперкомпьютерных вычислений и интересы пользовательских вычислений сошлись к одной точке: мы наращиваем количество ядер на одной машине с общей памятью и решаем задачи одинаковыми способами.

Некоторые алгоритмы, которые обслуживают наше программное обеспечение, с удовольствием восприняли эти изменения. Это, например, алгоритмы обработки изображений, такие как размытие по Гауссу, выделение границ. Они с радостью кратно увеличили свою скорость, то есть на двух процессорах стали работать в два раза быстрее, на четырех — в четыре. Потом, когда алгоритмы узнали, что существуют такие графические платы, для которых были созданы довольно простые языки, подмножества языка С — языки Cuda и OpenCL, они переехали вычисляться на графические платы, потому что им это очень удобно. На одной графплате у вас могут находиться десятки ядер, и вы получите очень серьезный прирост производительности для таких алгоритмов. Часть алгоритмов очень плохо адаптируется к такому параллельному масштабированию, потому что задачу нельзя просто взять и разделить. Это задачи, связанные с сортировками данных, задачи, связанные с алгоритмами на графах. То есть какие-то из них получают прирост производительности, но не обязательно он будет кратный. А часть алгоритмов принципиально не масштабируется, она никак не хочет получать преимущество от того, что выпускается на большом количестве ядер. Например, такими задачами являются алгоритмы работы с разреженными матрицами или алгоритмы с физическими законами, такими как задача трех тел. Ее сложно решать на многопроцессорных системах. Или же, например, численный метод Ньютона не параллелится.