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

Действительно, примерно с 1970-го по 1985 год производительность процессоров росла преимущественно за счет совершенствования элементной базы и увеличения тактовой частоты. Затем, вплоть до 2000 года, основную роль стали играть архитектурные усовершенствования — конвейеризация, специализация, суперскалярность, спекулятивные вычисления, кэширование, увеличение разрядности. Все эти факторы не влияли на процесс проектирования большинства программ, которые продолжали оставаться прозрачными, линейными и преимущественно объектно-ориентированными. Даже без перекомпиляции они исполнялись на новых платформах значительно быстрее, и программисты считали, что так будет продолжаться вечно.

В 2001 году был исчерпан ресурс повышения тактовой частоты процессора. Для рядового пользователя это прошло незамеченным, поскольку организация массового производства процессоров с тактовой частотой более 3 ГГц растянулась на несколько лет. К 2005 году был освоен серийный выпуск 3-гигагерцевых процессоров, и оказались в основном исчерпанными ресурсы архитектурного совершенствования отдельно взятого процессора. В апреле 2005 года Intel и AMD одновременно приступили к продаже двухъядерных процессоров для персональных компьютеров — по сути, двух процессоров на одной подложке. Золотой век ПК закончился. Теперь забота о повышении скорости исполнения программ полностью ложится на плечи кодировщиков.

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

В погоне за супервычислителем

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

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

Производительность суперкомпьютеров увеличивается за счет совершенствования элементной базы и архитектурных решений. Элементная база определяет быстродействие транзисторов и рассеиваемую мощность, а основные архитектурные изменения направлены на распараллеливание обработки данных, то есть одновременное выполнение нескольких действий [1].

Физический параллелизм

Параллельная обработка имеет две разновидности: конвейерность и собственно параллельность. В том и другом случаях предполагается архитектурное вычленение из системы отдельных физических компонентов.

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

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

Кроме конвейеризации и физического распараллеливания используются следующие методы:

  • специализация (применение внутри процессоров блоков, оптимизированных под определенный вид вычислений, например математических сопроцессоров);
  • кэширование;
  • спекулятивные вычисления.

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

Программирование физически параллельных систем

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

  1. Алгоритм должен допускать распараллеливание.
  2. При вычленении параллельных участков, как правило, приходится придавать алгоритму специальную форму. Например, если необходимо определить сумму массива, при распараллеливании на первом шаге одновременно суммируются соседние четные и нечетные элементы массива, а на втором попарно суммируются результаты, полученные на первом шаге, и т.д. Компактно записать параллельный вариант на языке Си невозможно. В общем случае приведение алгоритма к форме, позволяющей сократить время вычислений, означает отход от формы, обеспечивающей наиболее наглядное представление.
  3. В многопроцессорной системе разбиение на слишком крупные части не позволяет равномерно загрузить процессоры и добиться минимального времени вычислений, а излишне мелкая «нарезка» означает рост непроизводительных расходов на связь и синхронизацию.
  4. Физическому параллелизму присуща зависимость глобальной структуры алгоритма от топологии вычислительной платформы. Процесс создания максимально эффективного алгоритма практически не автоматизируется и связан с большими трудозатратами на поиск специфической структуры алгоритма, оптимальной для конкретной топологии целевой системы. Найденная структура обеспечит минимальное время получения результата, но, скорее всего, будет неэффективна для другой конфигурации. Более суровое следствие зависимости структуры алгоритма от вычислительной платформы — тотальная непереносимость не только исполняемых кодов, но и самого исходного текста.

Данная зависимость легко демонстрируется на классическом примере сортировки. При O (N) сравнениях, необходимых для сортировки массива из N элементов, стоимость параллельных алгоритмов сортировок равна O (N2). В то же время быстрые последовательные алгоритмы сортировок обеспечивают стоимость O (N log N). Таким образом, чтобы отсортировать массив из 1 тыс. чисел на десяти вычислителях, надо разбить его на десять частей, отсортировать их с помощью эффективного последовательного алгоритма, а затем параллельно слить эти части в общий список (стоимость параллельного слияния — O (N)) [2].

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

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

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

Операционные системы

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

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

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

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

Преимущества «мелкозернистого» логического параллелизма

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

«Мелкозернистый» логический параллелизм эффективен в задачах управления сложным промышленным оборудованием. Необходимость отражения параллелизма процессов, осуществляемых на объекте управления, требует создания по меньшей мере сотни параллельно исполняемых процессов. Например, эквивалентное монолитное решение в виде одного процесса, предназначенное для управления выращиванием монокристаллического кремния [4], приводит к рассмотрению 1030 различных ситуаций. Сжатие информации достигается при логическом параллелизме за счет упрощенного описания комбинаций независимых случаев: описание алгоритма как набора независимых частей — это описание суммы ситуаций, а монолитное описание — это описание произведения ситуаций. Невообразимое число ситуаций (1030) можно получить лишь из сотни параллельно исполняемых компонентов с двумя состояниями, в то время как независимое описание алгоритма подразумевает рассмотрение всего 200 уникальных случаев.

Многопоточный логический параллелизм

Преимущества «мелкозернистого» логического параллелизма заставляют искать пути снижения накладных расходов, присущих многозадачности. Известные решения для операционных систем — легковесные процессы (light-weight process). Так, в Sun OS 5.x имеется облегченный вариант задач — потоки (thread), состояние которых полностью характеризуется значениями указателей на код и стек. Переключение процессора на поток минимизировано вплоть до операций сохранения/восстановления этих указателей. Планировщик по-прежнему присутствует и активизируется по прерываниям от таймера.

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

Step1(); /* действие */

while (!EventOnStep1()); /* ожидание реакции на действие */

Step2(); /* следующее действие */

Если для реакции на действие требуется значительное время (например, событие — это реакция пользователя на запрос системы), то более приемлемая стратегия — передача управления после опроса. Этот подход используется при организации многопоточности методом циклического опроса (round-robin), который иногда обозначают термином «корпоративная многозадачность». При циклическом опросе потоки могут быть представлены просто функциями, которые опрашиваются в бесконечном цикле:

Main(){

for (;;) {

thread_1();

thread_2();

...

thread_N();

}

}

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

thread_i () {

switch (State_i) {

...

case STATE_1:

Step1(); /* действие */

if (EventOnStep1()) State_i = STATE_2; /* смена состояния */

break;

case STATE_2:

Step2(); /* следующее действие */

...

}

}

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

Например, в языке Рефлекс (диалект языка Си, предназначенный для описания алгоритмов управления) безопасность и невозможность разрушения программы языковыми средствами обеспечены на концептуальном уровне. В этом языке синтаксис и семантика Си расширены за счет понятия процесса — параллельно исполняемого участка кода, допускающего запуск, остановку и проверку своего состояния [4]. Автоматизированы рутинные операции, связанные с организацией параллелизма, и пользователь может полностью сосредоточиться на собственно алгоритме. Возможность обращения по произвольному адресу исключена. Переменные языка типизированы. При таком подходе конфликты памяти попросту невозможны.

Логический и физический параллелизм

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

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

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

Как преодолеть кризис?

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

Приходится констатировать, что архитектурные усовершенствования привели относительно однородную ИТ-индустрию к грани разделения на более мелкие области. Это вызвано тем, что физическое распараллеливание не работает в произвольном классе задач: увеличение разрядности процессора, использование гиперпотоковости (hyper-threading) и многоядерности могут дать эффект, противоположный ожидаемому, т.е. после распараллеливания время исполнения программы даже увеличится.

Не всякая задача допускает физическое распараллеливание [5]. Целые классы задач (например, быстрое Фурье-преобразование, обработка запроса к базе данных, быстрые алгоритмы сортировок и т.п.) не получают заметного выигрыша от распараллеливания либо не распараллеливаются в принципе. У разработчиков появляется альтернатива — вместо изменения структуры программы уделять больше внимания локальной оптимизации кода. До некоторого предела это окажется рабочим вариантом, причем будет поддержано ростом интереса к средствам разработки, ориентированным на высокоскоростное исполнение в рамках однопроцессорной архитектуры.

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

Не вполне ясен вопрос объектно-ориентированного программирования: нет исследований по совместимости объектно-ориентированного программирования с многоядерной архитектурой процессора. Текущий стандарт ISO на Си++ тактично обходит стороной физический параллелизм, а между тем, например, Intel пишет специализированные библиотеки на «чистом» Си.

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

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

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

Главной тенденцией программирования уже в ближайшее время станет создание новых языков и техник, совмещающих удобство разработки и физический параллелизм исполнения. Этого удастся добиться только за счет решения вопросов, связанных с физическим параллелизмом. Увы, существующие решения типа pthread и OpenMP можно расценивать лишь как паллиатив. Ручное управление физическим параллелизмом (explicit parallelism) отбрасывает программирование назад, в эпоху машинных кодов и ассемблеров, реанимируя привязанность структуры программы к физической архитектуре вычислительной платформы.

Автоматическое распараллеливание (implicit parallelism) для многоядерных архитектур в большинстве случаев обеспечивает ускорение лишь с некоторой вероятностью. Промежуточным решением могут быть уже упоминавшиеся реконфигурируемые библиотеки (Integrated Performance Primitives, MathKernelLibrary).

Наиболее перспективны языки и техники, которым естественно присущ логический параллелизм, независимость или слабая зависимость компонентов друг от друга. В первую очередь, речь идет о многозадачном логическом параллелизме. Существующие наработки — это, в сущности, «полуфабрикаты» для многоядерной платформы. Явный недостаток многозадачности состоит в том, что практически нереально придумать убедительный случай загрузки персонального компьютера достаточным количеством (десятком и более) действительно ресурсоемких задач.

Другая возможность — попытаться адаптировать к многоядерным архитектурам существующие техники и языки многопоточной организации программ. Опыт применения языка Рефлекс [4] в многопроцессорных системах показывает, что такое вполне допустимо. Правда, появляющиеся при этом сущности означают достаточно радикальное изменение программ на уровне машинных команд. Например, происходит очевидный отказ от использования стека при организации структуры программы. При создании программ меняется и восприятие процесса программирования: классические функции дополнены процессами, которые при их запуске порождают отдельный независимый поток команд и данных.

Время переосмыслить концепции

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

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

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

Литература

  1. Воеводин В.В. Параллельная обработка данных. Курс лекций. — Лаборатория параллельных информационных технологий НИВЦ МГУ, 2000.
  2. Макконнелл Дж. Основы современных алгоритмов. — М.: Техносфера, 2004.
  3. Легалов А., Кузьмин Д., Казаков Ф., Привалихин Д. На пути к переносимым параллельным программам // Открытые системы, 2003, № 5.
  4. Зюбин В.Е., Петухов А.Д. Распределение вычислительных ресурсов в средах c многопоточной реализацией гипер-автомата // Труды III Международной конференции «Идентификация систем и задачи управления» SICPRO?04. — Москва, 2004.
  5. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb?s Journal, March 2005.

Владимир Зюбин (zyubin@iae.nsk.su) — сотрудник Института автоматики и электрометрии СО РАН (Новосибирск).