Еще на школьных уроках информатики объяснялось интуитивное понятие алгоритма, которое в теории программирования постепенно трансформировалось в понятие модели программ, представляемой тройкой S =
Общего подхода, объединяющего и сводящего S в единое целое, как не было, так, увы, и нет. Каждый при этом «точит» свою ножку, и «стул» в результате получается или кривой, или совсем падает. В рамках последовательного программирования, благодаря его свойствам, все само собой получается устойчивым. Иное дело — параллельное программирование, где отсутствие единства всех компонентов тройки приводит к «падению» даже элементарных примеров. Пусть даны два оператора: c = a + b; a = b + c. Присвоим начальные значения переменным a, b и c соответственно 1, 1, 0 и запустим параллельно программу их вычисления. Логично ожидать, что после выполнения, к примеру, пяти циклических шагов мы должны получить следующий протокол работы:
a b c
0) 1.000 1.000 0.000
1) 1.000 1.000 2.000
2) 3.000 1.000 2.000
3) 3.000 1.000 4.000
4) 5.000 1.000 4.000
5) 5.000 1.000 6.000
В многопоточной программе, однако, можно получить все что угодно — здесь каждый поток живет своей жизнью, и если не приложить специальных усилий, то результат будет непредсказуемым. Любой поток может в любой момент времени как прочитать значение из общей памяти потоков, так и изменить его. В последовательной программе такой анархии быть не может, хотя и ее результат работы будет зависеть от порядка записи операторов.
Уже такой элементарный пример убеждает в том, что работа параллельных операторов и работа памяти должны быть синхронизированы. Результат работы был бы однозначным, если бы изменение памяти — выходных данных операторов — происходило только тогда, когда операторы завершили чтение своих входных данных. При этом он уже не зависел бы от последовательности исполнения операторов, даже в случае моделирования их параллельной работы в последовательной среде.
Если оба потока работают нормально, то еще нет гарантий, что их совместная работа будет столь же успешной. Такая ситуация определяется самой сутью определения понятия потока. Поэтому, чтобы добиться стабильного и правильного результата, нужно приложить усилия по синхронизации потоков, борьбе с гонками, клинчами, доступу к памяти и т. д. Но кроме того, что об этих проблемах нужно знать, необходимо еще и представлять конечный результат работы. А это порой непросто.
В контексте проблемы синхронизации работы потоков уже как-то даже неудобно рассматривать одну и ту же задачу — моделирования RS-триггера, однако с момента ее озвучивания и описания проблем, возникающих при ее «современном решении», прошло более пятнадцати лет, а дело не стронулось. Не пора ли от объяснения «на пальцах» переходить к строгому математическому доказательству режимов работы триггера при всех возможных комбинациях сигналов на его входах? При этом запрещенных комбинаций входных сигналов и неопределенных сигналов на выходах быть не должно.
Но, видимо, при нынешнем неспешном развитии «параллельной науки» формального доказательства работы триггера придется ждать еще долго. Да и как быть по-другому, если уровень теории обычно ограничен рассмотрением систем кодирования и в более сложном случае — булевой алгебры. Если первое нужно отнести к повторению школьных основ, то второе — это лишь та «арифметика», которая служит основой для более сложной «алгебры» параллельных систем. К ним, безусловно, относится и RS-триггер. Просто он представляет собой тот барьер, который обязательно нужно преодолеть.
|
Осторожно: многоядерный процессор
Мало кто сомневается в том, что надо что-то менять в современной организации параллельных вычислений. Что же должно кардинально изменить ситуацию и каким должно быть параллельное программирование? Вячеслав Любченко, Юрий Тяжлов |
Пока же можно еще раз подтвердить, что на текущий момент верного результата выполнения программы в параллельном режиме не получить. И в этом одна из основных проблем современного многопоточного параллельного программирования — «уговорить» программу правильно работать. Даже такую простейшую, как моделирование работы триггера с подсчетом еще и числа его переключений в отдельном потоке.
Современное параллельное программирование нужно лечить. Но как? Нужно программировать в рамках параллельной модели, объединяющей в единое целое (как и в случае последовательного программирования) память, операторы и управление параллельной программы. Есть ли такая модель? Как минимум одна — модель, в которой управление каждого отдельного процесса представлено моделью конечного автомата, а множество подобных процессов объединено в сеть конечных автоматов, работающих в едином дискретном времени. Естественно, что при этом не должно быть забыто о синхронной работе памяти, операторов и средств управления.
Тем не менее сегодня приходится сталкиваться с тем, что отвергается режим синхронной работы множества параллельных процессов, определяемый формальной параллельной моделью на базе сетевой автоматной модели в едином времени. Почему-то считается, что подобная система будет работать медленнее своего асинхронного аналога, в котором процессы вступают во взаимодействие только тогда, когда в этом возникает необходимость — асинхронной модели вычислений. Но, может, просто потому, что не предлагается других вариантов?
То, что асинхронные решения быстрее синхронных, — совершенно неправильно. В случае слабосвязанных процессов асинхронные механизмы могут уменьшить системные потери, возникающие в процессе синхронизации вычислений. Но чем больше связей, тем меньше будет такая экономия. Собственно многопоточные вычисления рассчитаны прежде всего на такой — слабосвязанный — класс вычислений. Однако, во-первых, мир сильнее связан, чем нам кажется. Во-вторых, современный мир вычислений базировался и все еще базируется на «синхронной электронике», так как все попытки создать быструю асинхронную схемотехнику до сей поры заканчивались неудачей. В-третьих (что, возможно, и объясняет эти неудачи) — если при современном уровне развития теории можно достаточно легко определить модель синхронных параллельных вычислений, адекватно описывающую мир реальных параллельных систем, то об аналогичной «асинхронной теории» пока речь не идет.
Безусловно, современные суперкомпьютеры решают прежде всего тяжелые вычислительные задачи, а там, где нужен тонкий инструмент, программист со своей «кувалдой» современного многопоточного и многоядерного программирования бессилен. Но, к счастью, это не означает, что современный многопроцессорный суперкомпьютер, «надорвавшись» на решении элементарного триггера, будет бессилен или не нужен при решении тяжелых задач параллелизма, если, конечно, его архитектуру не переложить на новые принципы. Просто в этом случае вычисления будут выполняться еще быстрее.
Так есть ли сегодня параллельные программы? Фактически их нет. Хотя, конечно, среди современных параллельных программистов можно найти гуру, которые запрограммируют любую задачу. Но инструмент у них пока один — «кувалда» нынешнего многопоточного программирования.
Механизмы организации единого времени, синхронизации работы автоматных процессов и памяти и т. д. — это то, о чем рассказать проще, чем реализовать. Но это все преодолимо — автоматная терапия в целом довольно непростое дело. Непростое уже потому, что необходимо не столько научиться автоматным азам (они не так уж сложны), сколько заставить себя мыслить по-другому. Когда со школьной скамьи вкладывается одно мышление, то переход к другому — параллельному, да еще и автоматному — представляет уже психологический барьер. За примерами ходить далеко не надо — то же объектное программирование.
Безусловно, для реализации автоматного параллелизма нужно преодолеть множество технических проблем — например, создать автоматный процесс, который будет параллелен аналогичным процессам, — а это не просто операция перевода обычного алгоритма в иную форму, которая, например, известна по SWITCH-технологии. Тем более недостаточно поместить такую программу в поток, сделав ее параллельной другим подобным программам. Кроме собственно автоматного языка, нужна соответствующая среда интерпретации и/или реализации автоматов — среда реализации сетевой автоматной модели. Системы реального времени — в какой-то мере близкий ей аналог.
Проблемы психологии и технологии можно решить, если есть цель — научиться легко и просто параллельно программировать, так, чтобы это было проще, чем программировать последовательно. Хотя владеть, например, алгеброй сложнее, чем арифметикой, но кто скажет, что с алгеброй жизнь тяжелее? Так и с алгеброй параллельного программирования. Никто не обещает, что будет легче, ведь нужно овладеть новой моделью и ее языком, изучить азы новой теории, понять новую технологию проектирования со всеми ее прелестями и возможностями. Так что легче будет вряд ли, но что появится больше возможностей и горизонт решений станет значительно шире — в этом сомнений нет.
Вячеслав Любченко (sllubch@mail.ru) — генеральный директор, завод «Радиоприбор» (Александров). Статья подготовлена на основе материалов доклада, представленного автором на IV Московский суперкомпьютерный форум (МСКФ-2013, грант РФФИ 13-07-06046 г).
