Параллелизация

Предыдущая часть

С самодельным параллельным суперкомпьютером в рюкзаке Клаус Шультен терпеливо ждал в чикагском аэропорту О'Хара, надеясь, что после прибытия из Германии ему не составит труда пройти таможню. Это было летом 1988 года, и Шультен собирался начать новую работу в Университете Иллинойса. В разгар холодной войны, когда напряженность между США и Советским Союзом достигла наивысшего пика, суперкомпьютеры вызывали у администрации Рейгана большой ужас. Хотя Рейган, находясь на своем посту, усилил гонку вооружений и все сопутствующие ей технологические достижения, он хотел, чтобы бурно развивающиеся разработки суперкомпьютеров не попали в руки Советов, которые могли бы создать более совершенное оружие.

Оглавление

1. Пересматривая устоявшиеся подходы

2. Предтечи молекулярной динамики

3. Шультен-числодробитель

4. Рискованный план

5. Паяльник вместо экзамена

6. Транспортировка суперкомпьютера во время холодной войны

7. Невзгоды теоретической биологии

8. В поисках сотрудников

9. Бунт аспирантов

10. Отказ от платоновской информатики

11. Ингредиенты NAMD

12. Награда за декаду

13. Вычислительный микроскоп достигает совершеннолетия

14. NAMD в двадцать первом веке

---

В 1986 году правительство объявило о предполагаемой политике ограничения использования советскими учеными суперкомпьютеров, размещенных в университетах США. Все предельно прозрачно: никакого доступа для ученых из 20 стран коммунистического блока. Но реализация была не столь ясна. Университеты были возмущены этой политикой, беспокоясь о посягательствах на их академическую свободу и исследовательские инициативы, не понимая, как им стать исполнителями политики государственной безопасности.

Фотография самодельного суперкомпьютера, который Клаус Шультен перевозил в рюкзаке

Администрация Рейгана не только собиралась запретить советским ученым проводить моделирование на суперкомпьютерах, но и не хотела, чтобы советские ученые вообще находились рядом, опасаясь, что они могут научиться создавать свои собственные. Но в 1987 году два молодых студента-физика из Мюнхена взяли на себя именно такую миссию по созданию собственного параллельного суперкомпьютера, хотя ни один из них не имел формальной подготовки в этой области. Они не только воплотили свое стремление, но и стоимость их проекта составила около 60 000 долларов, что намного меньше, чем розничная цена Cray-2, популярного суперкомпьютера в конце 1980-х. Их научный руководитель, Клаус Шультен, решил рискнуть всеми грантовыми деньгами, хотя у него не было никаких гарантий, что проект ждет успех, и даже несмотря на то, что он не был экспертом в параллельных вычислениях.

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

Пересматривая устоявшиеся подходы

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

На курсах химии в колледже иногда, помимо учебников, требуются наборы для построения молекул. Студенты собирают молекулы из разноцветных атомов-шариков скрепляя их тонкими палочками. Результатом будет жесткая 3D-модель, которую можно повертеть в руках и рассмотреть со всех сторон. До 1977 года этот статический взгляд на биомолекулу все еще был распространен в некоторых научных кругах. Но постепенно начал происходить сдвиг в концептуальном понимании исследователей, после того, как 1977 год ознаменовался введением вычислительного метода, который прояснил движение атомов, составляющих биологические макромолекулы, что позволяло рассматривать их динамику. Этот сдвиг в сторону использования вычислительных методов для отражения такой динамики стал первым шагом в легитимации вычислительного микроскопа и дал стимул, побудивший Клауса Шультена создать свой собственный суперкомпьютер.

Предтечи молекулярной динамики

В 1968 году Мартин Карплюс был очень успешным химиком-теоретиком, работавшим в Гарварде, и он неожиданно понял, что пришло время вернуться к своей первой любви биологии.

Когда Карплюс был еще мальчиком, отец подарил ему микроскоп, что помогло воспитать в нем любовь к природе. Это пристрастие к природе только усилилось, когда Карплюс посетил лекцию в Бостонской публичной библиотеке под названием "Птицы и их идентификация в полевых условиях", что привлекло его к орнитологии. После, в средней школе, Карплюс был одним из победителей Westinghouse Science Talent Search со своим проектом по семейству чистиковых. Его любовь к биологии продолжалась и в студенческие годы в Гарварде, поскольку в своей автобиографической статье 2006 года он писал: "Я пришел к выводу, что для того, чтобы приблизиться к биологии на фундаментальном уровне (чтобы понять жизнь), необходимо иметь солидный опыт в химии, физике и математике, и поэтому я записался на программу по химии и физике." Однако его аспирантура по биологии не удалась, он перешел на химию и получил докторскую степень осенью 1953 года в Калтехе. (подробности можно найти в автобиографии "Шпинат на потолке: химик-теоретик возвращается в биологию")

Пятнадцать лет спустя, после больших успехов в теоретических исследованиях химии, Карплюс был готов возобновить свой интерес к биологии. Он остановился на Институте Вейцмана в Реховоте, Израиль, как на месте, где он мог проводить время в знаменитой библиотеке и обсуждать идеи в группе Шнейора Лифсона, и взял отпуск из Гарварда, чтобы перестроить свои исследовательские интересы.

Пребывание в Институте Вейцмана в 1969 году дало Карплюсу то, что он искал, и он вернулся в Гарвард с темами для изучения, а именно: происхождение связности гемоглобина, изучение ретинали в зрении и укладка белка.

К началу 1970-х годов один из его учеников, Брюс Гелин, разработал компьютерную программу для вычисления силовых взаимодействий белка просто из его аминокислотной последовательности, а также из координатной разметки его структуры (полученной из экспериментальных данных рентгеновской кристаллографии). Программа была использована в основной работе Гелина по гемоглобину, а затем для изучения ингибитора трипсина поджелудочной железы крупного рогатого скота.

С программой Брюса Гелина к середине 1970-х годов группа Карплюса подготовила почву для применения молекулярной динамики к биомолекулам. К моменту когда к группе присоединился Эндрю Маккаммон, код Гелина обрел законченную форму, реализуя уравнения Ньютона для расчета динамики или отдельных движений атомов белка.

Однако остальные коллеги не очень-то одобряли применение молекулярной динамики к биомолекулам. Как писал Карплюс в своей автобиографии 2006 года: "Когда я обсуждал свои планы с коллегами-химиками, они думали, что такие расчеты невозможны, учитывая сложность точного анализа нескольких атомных систем; коллеги-биологи считали, что даже если бы мы могли сделать такие расчеты, они были бы пустой тратой времени."

Но Карплюса это не разубедило. Он был воодушевлен двумя ответвлениями исследований более простых систем, которые сделали молекулярную динамику возможной для биомолекул. Первой была работа по расчету траекторий нескольких частиц для простых химических реакций, которую Карплюс изучал сам, когда занимался теоретической химией. Эти траекторные расчеты уходили корнями в 1930-е годы. Второе ответвление заключалось в изучении термодинамических свойств большого числа частиц - работа, начатая Берни Олдером и Томом Уэйнрайтом в конце 1950-х годов, когда они впервые применили молекулярную динамику к большой системе взаимодействующих частиц.

Карплюс знал не только о работах 1950-х годов по молекулярной динамике, но и о том, что в середине 1960-х и середине 1970-х годов другие исследователи использовали молекулярную динамику для моделирования жидкостей. Таким образом, с оглядкой на работы предшественников, Карплюс решил рискнуть сделать расчеты молекулярной динамики на биомолекуле, даже если его коллеги по биологии и химии не разделяли энтузиазма. Но преобладающее негативное отношение было не единственным, с чем столкнулись Карплюс и его сотрудники. Расчеты молекулярной динамики, которые они хотели провести, требовали серьезной вычислительной мощности. Карплюс утверждает, что в конце 1970-х годов было трудно получить компьютерное время для выполнения таких больших вычислений в Соединенных Штатах, поскольку большинство больших компьютеров предназначались исключительно для оборонных работ. Но когда возможность принять участие в семинаре в Европе пообещала доступ к компьютеру, Брюс Гелин и Эндрю Маккаммон принялись неустанно работать над подготовкой программы для запуска молекулярной динамики на небольшом белке.

Работа в CECAM (Center Europen Calcul Atomique et Molculaire) на большом компьютере прошла успешно, и троица, Маккаммон, Гелин и Карплюс, вскоре опубликовала свою статью по молекулярной динамике ингибитора трипсина поджелудочной железы крупного рогатого скота. Поскольку молекулярная динамика буквально показывает внутренние движения белка во времени, они смогли воспроизвести 9.2 пикосекунды времени жизни белка. В принципе, программа молекулярной динамики должна была бы воспроизвести время необходимое для развития биологического процесса. И хотя несколько пикосекунд могут показаться небольшим количеством времени для выяснения поведения белка, это послужит одной из направляющих сил в продвижении будущих исследователей к поиску более крупных и быстрых компьютеров. Ученые хотели продлить время моделирования расчета молекулярной динамики, то есть использовать вычислительный микроскоп для длительностей, выходящих за пределы пикосекундного диапазона.

Шультен-числодробитель

Шультен знал о работе Маккаммона, Гелина и Карплюса, потому что он заканчивал аспирантуру в Гарварде, где Карплюс был одним из его преподавателей, а Маккаммон и Гелин были сокурсниками, которых часто можно было встретить в коридоре. Статья 1977 года оказала определенное влияние на Шультена, который был обучен использовать теоретические и математические методы, такие как те, которые используются в химии и физике. "Я понял, что этот вычислительный подход, открывает новые двери для описания проблем, которые нельзя было сделать с чисто теоретическим подходом, который я использовал прежде."

Но принятие вычислительного метода вместо того, чтобы использовать исключительно чистую теорию, имело свои издержки, и вскоре он стал известен как "Шультен-числодробитель". "Я заплатил за это большую цену, потому что в основном на протяжении большей части моей карьеры люди считали меня глупым. Хотя я продолжал публиковать статьи, ориентированные на математику, для каждой статьи, ориентированной на вычисления, мне приходилось выкупать себя десятью теоретическими работами, и я не мог этого сделать." Шультен был не единственным в этой истории, кто был очернен своими коллегами за то, что отошел от чисто теоретических исследований.

На самом деле, доказательство полезности вычислительного микроскопа или молекулярно-динамического подхода на его самых ранних стадиях также была битвой, в которую пришлось ввязаться Шультену. В 1985 году, будучи еще профессором в Мюнхене, Шультен отправился в суперкомпьютерный центр в Иллинойсе, чтобы провести некоторые расчеты, и вернулся в Германию с фильмом, иллюстрирующим белок в движении, основанным на моделировании молекулярной динамики. Когда Шультен показал фильм, один из его коллег пришел в ярость. "Он так взбесился, когда увидел это, что чуть не дошло до рукоприкладства. Он всем говорил, что это самая большая чушь, которую он когда-либо видел в своей жизни. Он был кристаллографом, который в основном думал о белках как о каком-то готическом соборе, отлитом из камня."

Несмотря на многочисленные трудности, с которыми пришлось столкнуться Шультену, он был полон решимости использовать молекулярную динамику в своей работе; он был уверен, что это приведет его к новым открытиям, которые будут ценны для науки. "Моя любовь к научным открытиям, заставила меня заняться грязными вычислениями."

Рискованный план

Шультен хотел досконально разобраться в фотосинтезе, при котором солнечный свет превращается в биохимически пригодную энергию. Но важной макромолекулой в этом процессе является большой белок, который находится внутри мембраны. Имитировать белок сам по себе и пренебрегать мембраной и жидкостью, которая его окружает, было не желательно, потому что такая изоляция не является естественной средой для белка. Этот белок состоит примерно из 12 000 атомов, а мембрана и вода, окружающие его в естественной среде, добавляют еще 100 000. В конце 1980-х годов ни один суперкомпьютер даже близко не был способен справиться с этой задачей. Таким образом, Шультен решил сосредоточиться на понимании и моделировании только части мембраны в воде, когда выпала возможность выполнить расчет на Cray-XMP, но это позволило воспроизвести процессы всего в несколько пикосекунд, что натолкнуло на мысль: нужен свой суперкомпьютер на котором можно гонять расчеты год или больше, чтобы действительно понять механизм.

В то время как Шультен, преподававший физику в Мюнхенском техническом университете, задавался вопросом, как завести себе суперкомпьютер, молодой студент того же университета задавался вопросом, как получить возможность быстрый компьютер построить. На самом деле, теоретически, Гельмут Грубмюллер знал, как сделать компьютер быстрее, но ему было интересно, сможет ли он заставить кого-то другого оплатить это. При поступлении в Мюнхенский университет в 1985 году, двадцатилетний Грубмюллер осознал, как выбор специальности определил его цели: "Когда я начал заниматься физикой, я быстро понял, что для того, чтобы узнать больше о том, как работает природа, может потребоваться мощная вычислительная машина. В конечном счете, именно поэтому я был так очарован компьютерами; вы могли делать вычисления, которые иначе не осилить."

Во втором или третьем семестре он спаял многопроцессорный компьютер, который будет намного быстрее, чем то, что было доступно обычным студентам в те дни. Хотя технически это был параллельный компьютер, Грубмюллер просто назвал его мультипроцессором. Это была середина 1980-х, и не было никакой Всемирной паутины, чтобы проконсультироваться по техническим вопросам. Вместо этого он читал любые книги о микропроцессорах, какие только мог найти, и разговаривал по телефону с представителями компаний о технических характеристиках продаваемых ими деталей. В качестве наиболее важных для продвижения вперед источников информации для него были технические спецификации чипов, например, из линейки Motorola 68 000, которые он использовал в качестве процессора. Это увлечение быстро опустошило бюджет студента.

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

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

Одним из таких людей был Гельмут Геллер, который, как впоследствии узнал Шультен, пользовался некоторой славой в университете. Еще в старших классах Геллер начал сам изучать компьютеры. Он был счастливым обладателем одного из первых персональных компьютеров, PET 2001, представленный Commodore в конце 1970-х. Там было всего 8 килобайт оперативной памяти и кассета для архивирования данных. "Я начал с изучения BASIC с отладкой программ на этой машине. Потом же, начал писать машинный ассемблерный код", вспоминает Геллер. У него в родном городе было несколько друзей, которые тоже интересовались компьютерами и учили друг друга.

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

Клаус Шультен, Гельмут Грубмюллер, Гельмут Геллер и одна из плат самодельного суперкомпьютера,1988.

Лекционный зал был переполнен, хотя обычно была занята от силы четверть мест. Сбитый с толку, Шультен направился в соседний лекционный зал, но там никого не оказалось. Вернувшись обратно, он увидел Геллера, ожидавшего у входа, чтобы начать защищать свой проект. "Гельмут Геллер был настолько известен в университете как компьютерный гуру, что все, кроме меня, знали, что если он выступает, то лучше прийти."

Геллер сделал на компьютере сложный фильм про фракталы для этого задания. "Он показал нам, как он модифицировал компьютер, чтобы провести этот расчет. Даже сегодня я не в состоянии объяснить, что он на самом деле сделал." Наблюдение за тем, как Геллер играючи управляется с компьютером, действительно произвело впечатление на профессора. Шультен с удовольствием пригласил Геллера присоединиться к группе.

"Иногда приходится рисковать", оправдывает Шультен свое решение позволить Грубмюллеру и Геллеру построить параллельный суперкомпьютер. Риск для Шультена был огромен. Хотя у него был бы суперкомпьютер для моделирования молекулярной динамики, если бы это каким-то образом не сработало, ему было бы нечего показать. В то время он не был экспертом в области параллельных вычислений и имел мало сведений для оценки осуществимости проекта. Кроме того, ему придется объяснять финансирующему агентству, как он вложил десятки тысяч немецких марок в самодельный компьютер, тогда как деньги предназначались для оборудования, которое обычно поставлялось с гарантиями и контрактами на обслуживание.

Паяльник вместо экзамена

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

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

В конечном итоге компьютер был собран и назван T60. За основу использовался кластер процессоров, известных как транспьютеры, потому что якобы из них можно было так же легко собрать схему, как из блоков Lego. В результате вышло 60 узлов: десять самодельных плат, по шесть транспьютеров на каждую. Все компоненты были спроектированы, спаяны и собраны вместе: транспьютеры, оперативная память, источник питания, вентиляторы (аэраторы), корпус, шины питания, печатные платы и крепления.

Поскольку пайка каждой из десяти печатных плат занимала много времени, к работе подключились другие члены исследовательской группы Шультена. Каждый участник получал детали и лист инструкций и начинал паять плату, что занимало по крайней мере около шести недель, а затем подписывал на ней свое имя. "Это действительно показывало исследовательскую личность студента", утверждает Шультен. "Работа, которую каждый в группе должен был проделать, действительно очень близко отражала то, как они на самом деле будут вести себя в команде и позже в науке." На самом деле Шультен считает, что вся эта пайка была даже лучше, чем традиционные результаты экзаменов, в определении того, какие кандидаты будут хорошими аспирантами, чтобы принять их в группу.

Геллер вспоминает о трудностях, с которыми столкнулась команда при написании кода для параллельной машины, кода, который они назвали EGO. "Я помню, что когда я впервые сделал параллельные вычисления, которые хорошо масштабировались, я был очень взволнован, но вскоре я обнаружил, что все результаты были неправильными! У меня была быстрая параллельная программа, дающая неправильные результаты." Найти причину этого было нелегко. Шультен купил кусок промышленного марципана, до которого Геллер был большой любитель, и время от времени отрезал ему ломтики, чтобы побудить его продолжать. После долгих добродушных насмешек со стороны других членов группы за его быстрые, но неправильные вычисления, Геллер в конце концов понял, что ему нужно правильно синхронизировать параллельные задачи, так как сначала он дал им слишком много свободы; решение заняло много дней и долгих вечеров работы.

Транспортировка суперкомпьютера во время холодной войны

Проект по созданию и программированию Т60 начался в конце 1987 года. На пол пути к его завершению Шультен получил новую работу в Соединенных Штатах, в Университете штата Иллинойс в Урбана-Шампейн. Вместо того чтобы отправить Т60 в Соединенные Штаты и неделями ждать, пока он прибудет, а затем пройдет таможню, Шультен решил просто пронести компьютер в рюкзаке.

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

Существовал специальный список ограничений и запрещенных материалов для экспорта в коммунистические страны, который был составлен под эгидой COCOM, комитета, созданного после Второй мировой войны для ограничения поставок оружия в Советский Союз. Список был единогласно согласован Соединенными Штатами, союзниками по НАТО и Японией. В 1984 году, после долгих ожесточенных споров между Соединенными Штатами и Западной Европой, особенно по поводу экспорта компьютеров, COCOM пересмотрела свой список товаров и в основном разрешила свободно экспортировать персональные, но не суперкомпьютеры.

Администрация Рейгана не только хотела ограничить бизнес, как внутренний, так и зарубежный, от экспорта суперкомпьютерных технологий в СССР, она также хотела держать советских ученых подальше от своих недавно созданных суперкомпьютерных центров. В 1985 году Национальный научный фонд выделил четырем университетам 200 миллионов долларов на открытие суперкомпьютерных центров в их кампусах. Этот шаг был признан необходимым и санкционирован Конгрессом, чтобы предоставить академическим исследователям доступ к суперкомпьютерам, которые обычно ограничивались оборонными работами, выполняемыми Пентагоном и Национальными лабораториями. Как сказал один из ключевых ученых, лоббировавших правительство США, использование стандартных компьютеров вместо упрятанных за бюрократическими препонами суперкомпьютеров "похоже на езду на лошади и возу, когда над головой летают самолеты". Но в 1986 году администрация Рейгана предложила запретить доступ к этим суперкомпьютерным центрам советским ученым. Таков был климат летом 1988 года, когда Клаус Шультен решил взять свой самодельный суперкомпьютер на трансатлантический рейс и пронести его через таможню в Чикаго.

Шультен знал, что из-за скорости обработки данных компьютер Т60 должен быть зарегистрирован, особенно при экспорте или импорте. Он подошел к таможеннику и показал ему суперкомпьютер.

Что это? спросил таможенник.

Это компьютер, ответил Шультен.

Зачем Вы мне его показываете?

Это очень мощный компьютер, и он должен быть зарегистрирован у вас.

Затем Шультен объяснил офицеру некоторые технические детали машины. Наконец таможенник посмотрел на Шультена и сказал: "Пожалуйста, положите его обратно и ступайте."

Невзгоды теоретической биологии

Когда Шультен прибыл в Иллинойс, его ученики закончили собирать и программировать свой Т60. Программа, получившая название "EGO", была написана на языке OCCAM II языке, физическим воплощением которого, по сути, и являются транспьютеры. Точно так же, как создание T60 требовало больших усилий, написание параллельного кода было столь же трудной задачей. Одним из ключевых показателей в параллельном программировании является то, насколько хорошо масштабируется программное обеспечение; хорошее масштабирование (или параллелизуемость) означает, что время выполнения вычислений приближается к ускорению кратному количеству логических потоков. Например, сбор яблок человеком хорошо параллелизуется: по мере того, как все больше людей участвует в сборе, время выполнения работы уменьшается.

Мембранная структура, смоделированная на Т60 в течение двадцати месяцев, охватывала 24 000 атомов. Изображение из Heller et al., 1993.

Было очень важно, чтобы EGO хорошо масштабировалось, потому что расчет мембраны, который Шультен и его группа хотели запустить, был очень большой системой. На самом деле расчет занял двадцать месяцев безостановочных вычислений. Система, которую они изучали, мембрана из липидов, окруженная водой, состояла из 23 978 атомов. Для сравнения, число атомов в системе биомолекул, которую Маккаммон, Гелин и Карплюс изучали в 1977 году, было на два порядка меньше.

После таких невероятных усилий, приложенных к проблеме мембраны, можно представить себе удивление Шультена, когда их с Гельмутом Геллером и Михаэлем Шефером статья была отклонена в течение недели, хотя результаты хорошо согласовались с экспериментом. Статья содержала результаты теоретической биофизики. Шультен признает, что опубликовать теорию, связанную с биологией, очень сложно, особенно в журналах с высоким импакт-фактором. Он говорит, что даже сегодня у него больше шансов получить признание, если он объединится с экспериментаторами. В своей автобиографической статье 2006 года Мартин Карплюс суммирует препятствия, с которыми сталкиваются теоретики при публикации результатов, связанных с биологией: "Как и раньше, сегодня эта проблема все так же распространена, то есть, если теория согласуется с экспериментом, она не интересна, потому что результат уже известен, тогда как если кто-то делает прогноз, то он не может быть опубликован, потому что нет доказательств того, что прогноз верен."

Тайна отказа так и не была раскрыта. "Я до сих пор не знаю, почему ее отвергли", рассказывает Шультен. "Я был так взбешен, что, хотя я опубликовал много статей в этом журнале, я сказал им, что больше никогда не буду там публиковаться." Геллер, Шефер и Шультен в конце концов опубликовались в Journal of Physical Chemistry, и статья сейчас высоко цитируется.

Этот набег на молекулярную динамику такой гигантской для своего времени системы дал обоснование для использования параллельного компьютера в качестве вычислительного микроскопа. Было важно взять для анализа большой сегмент мембраны, потому что реальные клеточные мембраны непрерывны и не имеют края как такового. Другие типы обычных микроскопов не могли уловить некоторые критические особенности мембраны, которые проясняла молекулярная динамика. "Когда вы смотрите на мембрану в течении какого-то времени, то замечаете, что она вся текучая и движущаяся. Что довольно трудно рассмотреть с помощью микроскопов. А мы действительно видели с помощью компьютера сам процесс и могли провести сравнение с большим количеством экспериментов. Они измеряют некие усредненные характеристики, которые придавали нам убеждение в том, что то, что мы действительно видели с помощью компьютера, было правильной картиной." Успех вычислений только подогрел аппетит Шультена к изучению все больших и больших систем. Шультен не понимал, что его жажда массивных систем на параллельных машинах приведет к своего рода студенческому бунту и программному продукту под названием NAMD, который определит его карьеру.

В поисках сотрудников

В 1989 году Шультен основал группу теоретической биофизики [Theoretical Biophysics Group] (которая впоследствии стала группой теоретической и вычислительной биофизики) в Институте Бекмана Иллинойского университета. В 1990 году он получил двухлетний грант от Национального института здравоохранения, которого более или менее должно было хватить, чтобы центр заработал. К этому времени Шультен лучше разбирался в параллельных вычислениях, по сравнению с теми временами, когда он вложил все свои деньги в параллельную машину еще в Мюнхене; он понял, что может изучать массивные биомолекулы, используя преимущества параллельных машин. Уже существовали программные коды, некоторые даже в свободном доступе, которые занимались молекулярной динамикой, но Шультен понял, что его потребности намного превышают их возможности.

На самом деле, Шультен понял, что его потребности превышают даже его собственные возможности как вычислительного биофизика, если он хочет осуществить свой план по изучению более массивных биомолекул в их естественной среде. Шультен решил выйти за пределы своего поля. "На мой взгляд, это было некоторое предвидение с его стороны, начать искать опытных информатиков", вспоминает Лаксмикант Санджай Кале, один из ученых, к которым обратился Шультен. Мотивированное тремя причинами, суждение Шультена вынудило его обратиться за помощью к компьютерщикам в своем университете.

Во-первых, до 1991 года программированием молекулярной динамики в группе Шультена всегда занимались его студенты-физики. После того, как оба Гельмута написали EGO для самосборного компьютера, другой студент, Андреас Виндемут, написал код по молекулярной динамике для Connection Machine.

Как уже упоминалось ранее, в 1985 году в Соединенных Штатах были созданы четыре центра для предоставления академическим исследователям доступа к суперкомпьютерам. Четыре центра находились в Корнелле, Принстоне, Калифорнийском университете, Сан-Диего и Иллинойском университете, в Шампейн-Урбане, где находился Шультен. Иллинойский центр назывался NCSA, и группа Шультена имела доступ к Connection Machine, которая размещалась там. Видя программы для T60 и для Connection Machine Шультен понял, что ему нужны навыки разработки программного обеспечения в группе, чтобы убедиться, что программное обеспечение написано таким образом, чтобы в будущем оно было понятно и открыто для модификаций. Его студенты-физики просто не были обучены таким навыкам.

Во-вторых, Шультен понял, что методы программирования меняются, и особенно то, что FORTRAN, разработанный в 1950-х годах, возможно, не будет лучшим вариантом, поскольку начали приобретать известность другие языки. "Нам нужны были лучшие языки программирования, которые были бы более систематичными".

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

Имея в виду вышеупомянутые причины и необходимость получить более солидный грант на обновление своего центра, грант, который обеспечит финансирование на пять лет, а не только на два года, Шультен обратился к двум ученым-компьютерщикам из университета Иллинойса и попросил их принять участие в работе группы. Один из них, Боб Скил, был экспертом в области численных алгоритмов, а другой, Санджай Кале, был экспертом в параллельном программировании. В 1992 году Шультен получил пятилетний грант от Национального института здравоохранения и таким образом приступил к основам программного кода под названием NAMD.

Бунт аспирантов

На самом деле Шультен воспринимает раннюю работу над T60 как приготовление почвы для NAMD это вкупе со студенческим бунтом, который произошел в начале 1990-х годов. В это время Шультен надеялся продолжить использовать коды молекулярной динамики, которые были разработаны для Connection Machine и Т60. Аспирант Боба Скила, Марк Нельсон, изучал код Connection Machine, а аспиранты Шультена, Билл Хамфри и Эндрю Далк, изучали код Т60. Все трое были непомерно раздражены своей работой. "Я бился головой об этот код в течение нескольких месяцев, рассказывает Нельсон, и никуда не продвигался. Комментариев не было, и все имена переменных были сокращениями немецких названий, что как-то мне не помогало."

Трое аспирантов, Нельсон, Хамфри и Далк, решили, что их задача будет проще, если они просто напишут новый код с нуля. Они тайно работали около месяца, пока не получили жизнеспособный код. Взяв на себя большой риск перед своими научными руководителями, они представили на собрании группы идею создать совершенно новый код и оставить в покое предыдущие реализации, которые было бы сложно поддерживать. "Они хотели написать все на C++ и боялись, что профессор пристрелит их за дерзкий отказ от работы с проверенным кодом." смеется Шультен. Однако на самом деле, он был в восторге от этой инициативы. "Так что я сам был очень взволнован, потому что увидел здесь ситуацию, которая была почти такой же, как у Гельмутов до них. Студенты осознавали риск и были готовы взять на себя ответственность."

На тот момент группа Шультена уже была готова создать программный код с нуля, потому как в команде появились настоящие компьютерщики. Один из них, Санджай Кале, попал в проект в следствие случайного стечения обстоятельств и вскоре узнал, что ему будет нужна толстая кожа для того, что его ждет.

Отказ от платоновской информатики

В начале 1980-х годов, будучи аспирантом в SUNY Stony Brook в Нью-Йорке, Кале начал работать над параллельным логическим программированием. В частности, он использовал язык Пролог для изучения искусственного интеллекта. "Так уж получилось, вспоминает Кале, что если вы осмотритесь в этой области сейчас, то увидите огромное количество людей, которые в середине 1980-х годов кодили на Прологе."

Санджай Кале, специалист по компьютерам в Университете Иллинойса с 1985 года.

Когда он получил работу в Университете Иллинойса, он продолжал работать над параллельным логическим программированием и получил должность в 1991 году. Пока он занимался этим более или менее "чистым" исследованием, основанным на компьютерных науках, он начал обдумывать применение своей работы. "Я занимался поиском на основе состояний, искусственным интеллектом в общем, и его распараллеливанием в частности, задачами а ля коммивояжера и т. д.", рассказывает Кале об этом периоде времени. "Но мои интересы начали смещаться в сторону: как мы можем применить это к задачам, которые есть у инженеров и ученых?"

По удивительному совпадению, сразу после того, как Кале получил должность и собирался отправиться в академический отпуск в Индию на семестр, к нему подошел Клаус Шультен, чтобы спросить, будет ли Кале участвовать в гранте 1991 года в качестве эксперта по параллельным вычислениям. У Кейла внезапно появился прикладной проект, буквально на его собственном заднем дворе. Он провел часть своего отпуска, читая о биологии и биологическом моделировании, а когда вернулся из Индии, начал изучать две программы, которые Шультен использовал для параллельных вычислений молекулярной динамики.

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

Во-первых, он понял, что компьютерщики часто занимаются абстрактными исследованиями. "Это не работает, потому что вы не концентрируетесь на реальных проблемах", говорит Кале. Поэтому я называю это платоновскими компьютерными науками. Идея выглядит красиво, поэтому вы ее развиваете, а затем перебрасываете ее через забор в реальный мир. А реальному миру все равно, потому что он занят своими проблемами."

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

К началу 1990-х годов Кале работал над прикладными проектами: Клауса Шультена по молекулярной динамике и еще одним по гидродинамике с сотрудником в области машиностроения. Что касается молекулярной динамики, то Кале изучал предыдущие коды, разработанные группой Шультена. Примерно в 1994 году аспиранты предложили начать все сначала. "Мы решили явно оформить его как программу", вспоминает Кале. "Сделать шаг назад и разработать его как программу, а не позволять ему быть органически выращенным." Этот формальный дизайн привел к прототипу NAMD. Название первоначально было акронимом "Not Another Molecular Dynamics", который придумал аспирант Билл Хампри, вдохновленный названием компилятора аналогичной природы; вскоре аббревиатура стала обозначать "NAnoscale Molecular Dynamics". Явное требование NAMD быть параллельным с самого начала будет иметь долгосрочные последствия с точки зрения успеха программного обеспечения.

Хотя Кале исполнил свое желание работать над приложениями, последнее десятилетие века сопутствовалось тяжелым трудом. Кале и его аспиранты разработали язык параллельного программирования, названный ими Charm++, который стал очень важным и ценным для успеха NAMD. Его собственные исследования в области компьютерных наук в течение десятилетия были сосредоточены на этом. "То, что мы предлагали, было параллельным C++ или параллельным объектно-ориентированным языком, который был по-своему новым и существенно отличался от того, как люди занимались параллельным программированием", рассказывает Кале. "Так что это был мой вызов заставить людей принять это."

Этому предприятию также характерно большое число поражений. У Кале остались стопки отклоненных грантовых предложений в качестве напоминания. Рецензенты говорили, что то, что он предлагал, либо невозможно, либо устарело. Его публикации тоже не всегда ценились: "Мы писали статьи, и я говорил: "Это продемонстрировано в молекулярной динамике". А люди отвечали: "Это просто параллельный C++. Многие люди делают параллельный C++". Они не обращали внимание на элемент новизны. И работы продолжали игнорироваться".

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

Ингредиенты NAMD

Многие факторы формировали направления в которых развивался NAMD в 1994 году, не последним из которых было то, что теперь он хорошо финансировался грантом NIH. Аспиранты настаивали на использовании языка С++, относительного новичка в области программирования. "C++ предложил хорошую комбинацию объектно-ориентированного языка, заявляет бывший студент Марк Нельсон, но мы все равно могли бы написать ключевые вычислительные части на C и получить необходимую скорость." Использование C++ в NAMD сделало его уникальным среди солверов молекулярной динамики того времени.

Поскольку NAMD должен был быть адаптирован для параллельных машин, разработчики должны были учитывать, как многие процессоры, составляющие параллельную машину, будут взаимодействовать друг с другом при выполнении вычислений молекулярной динамики. Кале и Аттила Гурсой, его аспирант, работали над средой Charm++ и кое-чем, что называлось message-driven execution. Хотя технические детали выходят за рамки этой статьи, достаточно сказать, что Charm++ использовал message-driven execution, чтобы эффективно позволить процессорам общаться друг с другом во время выполнения молекулярной динамики.

В то время как C++ и Charm++ были уникальными элементами для NAMD, параллельный дизайн с нуля был еще одной отличительной чертой. В начале 1990-х годов другие очень успешные коды молекулярной динамики, такие как Amber и CHARMM (который является гарвардским продуктом и не следует путать его с Charm++, который был разработан в Иллинойсе), приняли другую тактику, когда стало очевидно, что программное обеспечение должно быть разработано для параллельных компьютеров.

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

Санджай Кале приводит преимущества, которые дизайн с нуля давал NAMD: программное обеспечение хорошо масштабировалось и могло обрабатываться любыми новыми машинами, которые быстро появлялись на рынке. "Этот дизайн выдержал испытание временем и до сих пор актуален", размышляет Кале. "В значительной степени архитектура параллельной программы осталась прежней, хотя в то время мы работали на кластере HP, с восемью процессорами. А теперь мы работаем на 200 000 с лишним процессорах.

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

Награда за декаду

Почти через десять лет после того, как Кале начал свою одиссею в мир параллельных вычислений, он, наконец, был вознагражден. Каждый год проводится международная конференция Supercomputing. Премия Гордона Белла вручается ежегодно на конференции в знак признания достижений в области параллельных вычислений. И в 2002 году она была присуждена разработчикам NAMD.

Хотя Кале, возможно, работал в течение многих лет над такими прикладными проектами, как молекулярное моделирование и гидродинамика, он также занимался более или менее чистыми исследованиями в области компьютерных наук. Он считает, что премия Гордона Белла принесла его группе заслуженную славу. "На самом деле, я очень благодарен за это, отмечает Кале, потому что наши идеи в области информатики остались бы недооцененными. И было бы трудно добиться их признания, если бы не успех NAMD". Из-за своей репутации в NAMD у Кале теперь есть проекты в области моделирования погоды, вычислительной астрономии и вычислительной химии.

Вычислительный микроскоп достигает совершеннолетия

К этому времени вычислительный микроскоп стал более сложным. В 1977 году было проведено первое моделирование молекулярной динамики на небольшом белке в вакууме, которое отображало 9,2 пикосекунды. К 1996 году NAMD моделировал систему с 36 000 атомами, рецептор эстрогена с сегментом ДНК в соленой воде, в течение 50 пикосекунд. Расчет выполнялся в течение двух-трех дней на 8-процессорном кластере. В 2004 году для системы аквапорин-1, состоящей из 81 065 атомов, расчет проводился в течение 22,4 часов на параллельной машине с 128 процессорами и отобразил 5 наносекунд времени жизни системы.

Эти достижения утвердили вычислительный микроскоп для научного сообщества. "В прежние времена компьютерное моделирование не было таким точным", вспоминает Шультен. Поэтому было бы высокомерием просто сказать: 'Это вычислительный микроскоп', люди посмеялись бы над нами и сказали бы: 'У вас очень плохой микроскоп'.

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

Часто вычислительный микроскоп правильно предсказывал то, что наблюдал эксперимент; иногда он опережал эксперимент. Одним из таких случаев был пример использования NAMD для запуска моделирования "управляемой молекулярной динамики". В управляемой молекулярной динамике можно применить внешние силы к белку и отобразить его последующее поведение во времени. Анкириновый повтор это определенная последовательность аминокислот, и эта последовательность содержится в более чем 400 белках человека. В 2005 году Маркос Сотомайр, Дэвид П. Кори и Клаус Шультен изучали упругие свойства этих анкириновых повторов с помощью управляемой молекулярной динамики, в конечном счете, чтобы лучше понять слух и чувство равновесия; год спустя, в 2006 году, эксперимент подтвердил их результаты моделирования. В высоко цитируемой научной статье 2007 года Одномолекулярные эксперименты in Vitro и in Silico Сотомайр и Шультен утверждают, что эксперименты in silico "стали мощным инструментом, дополняющим и направляющим эксперименты in vitro". Термин 'in silico' относится к исследованию, выполненному с помощью компьютерного анализа. Обоснование вычислительного микроскопа как мощного инструмента только усиливалось по мере того, как этот эксперимент предвосхитил результаты эксперимента in vitro.

NAMD в двадцать первом веке

NAMD появился на свет в начале 1990-х годов, и семя его восходит к самодельному параллельному компьютеру, построенному в конце 1980-х годов, и программе EGO, которая была написана для этого конкретного суперкомпьютера. Шультен хотел управлять все большими и большими системами, и поэтому NAMD родился, а затем вырос, потому что он хорошо финансировался. Ключевым игроком, стоящим за успехом NAMD, является ведущий разработчик Джим Филлипс, бывший аспирант Шультена в 1990-х годах. Теперь Шультен называет Филлипса "отцом NAMD", поскольку Филлипс разрабатывал творческие решения для параллельного программного обеспечения почти два десятилетия.

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

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

Коллапс пустого капсида. Три снимка сверху взяты из моделирования всех атомов , а шесть внизу-из крупнозернистого моделирования.

Кроме того, было обнаружено, что вирус птичьего гриппа H5N1 также обладает устойчивостью к Тамифлю. Используя NAMD, а также молекулярную динамику и управляемую молекулярную динамику, сотрудники Университета Иллинойса и Университета Юты объединили усилия, чтобы найти основу для этой лекарственной устойчивости. Их открытие, согласно их публикации 2010 года, "предполагает, как мутации нарушают связывание лекарств и как новые лекарства могут обойти механизмы устойчивости."

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

Вирусы это очень примитивные частицы, и многие из них состоят только из белковой оболочки, или капсида, окружающего нить ДНК или РНК. Для размножения вирус проникает в клетку-хозяина и захватывает ее механизмы, чтобы создать больше вирусных частиц. В то время как капсид играет роль защиты вируса, он также должен каким-то образом стать нестабильным и высвободить свои внутренние компоненты в клетку-хозяина для размножения. Распознавание движения белков, составляющих капсид во время такого высвобождения, является приоритетной целью, и исследование, проведенное в 2006 году, изучало динамику различных капсидов. Относительно новый метод крупнозернистая молекулярная динамика, позволял моделировать целые капсиды, которые до этого времени были недоступны. Ученые из Университета Иллинойса усовершенствовали метод крупнозернистой молекулярной динамики и использовали NAMD для иллюстрации стабильности капсида для нескольких вирусов. С помощью новой техники стало возможным моделировать капсиды размером более 10 нанометров и наблюдать переходы между стабильными и нестабильными структурами. Эта работа может дать полезную информацию для борьбы с вирусными заболеваниями.

Будущее для NAMD выглядит радужным. Цель Клауса Шультена понять биологическую организацию, саму суть того, что делает клетку живой, маячит на горизонте после сорока лет самоотверженности и творчества. "Так что теперь я могу потихоньку заняться тем, о чем мечтал, замечает Шультен о биологической организации, ближе к отставке. И другие люди следующие за мной могут использовать наработки сейчас и могут делать это намного лучше. И это, конечно, тоже делает меня счастливым." И вычислительный микроскоп продолжает прояснять все большие и большие системы. "Сегодня у нас есть симуляция на 20 миллионов атомов", хвастается Шультен. "И у нас есть симуляция, чтобы быть готовыми к следующему поколению компьютеров, которые потянут 100 миллионов атомов." Сочетание понимания и принятия риска, безусловно, окупилось с точки зрения научных открытий. От выяснения рецептора эстрогена, чтобы лучше понять рак молочной железы, до освещения вирусов, чтобы лучше бороться с болезнями, вычислительные проекты, ставшие возможными с помощью параллельных компьютеров, будут продолжать раздвигать границы. И до тех пор, пока смелые ученые идут на большой личный риск, пытаясь сделать то, что никогда не делалось раньше, и продолжают переосмысливать новые пути для того, чтобы компьютер действовал как научный инструмент, помогающий исследователям, будущее вычислительного микроскопа, кажется, наверняка принесет больше открытий.

Продолжение следует...

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

Ниже приведена иллюстрация процесса выявления параллелизма для простейшего случая вычисления выражения axb+a/c (a, b, c входные данные).

а) облако операторов (последовательность выполнения не определена), б) полностью последовательное выполнение, не определена), б) полностью последовательное выполнение, в) параллельное исполнение

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

Параллельная вычислительная система включает несколько вычислителей (арифметико-логических устройств), объединённых общей или локальной оперативной памятями и кэшами. Современные параллельные системы часто имеют не только гомогенное, но и гетерогенное вычислительное поле. Задача распределения вычислений между отдельными вычислителями приводит к разработке расписания (плана) вычислений. Проблемой является многозначность расписаний параллельного выполнения алгоритма в общем случае это NP-полная задача [2], точное решение (при заданных оптимизационных требованиях) которой можно получить только методом полного перебора (что нереально при числе операторов уже более сотен-тысяч). Выходом является использование эвристических методов, исходя из сложности данную область знания можно обоснованно отнести к наиболее сложным случаям Науки о данных (Data Science).

Параметрам выполнения распространенных алгоритмов в параллельном варианте посвящен известный ресурс AlgoWiki [3].

Особенно интересен, с точки зрения автора, вариант параллелизации для языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-Level Parallelism, параллелизм на уровне команд, с реализацией посредством вычислительной архитектуры EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд). При этом аппаратное обеспечение вычислительных систем сильно упрощается и все проблемы выявления параллелизма и построение собственно расписания выполнения программы для заданной конфигурации параллельной вычислительной системы ложатся на компилятор, что ведет к его усложнению и снижению скорости компиляции.

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

Одной из важных процедур выявления параллелизма по заданному ИГА является получения его исходной (обладающей свойством каноничности) Ярусно-Параллельной Формы (ЯПФ), [4]. При этом условием расположением операторов на едином ярусе является независимость их друг от друга по информационным связям (необходимое условие их параллельного выполнения).

Получение такой (без условия ограниченности количества операторов на ярусах) ЯПФ требует O(N2) действий, где N число операторов (вершин графа), ее высота (общее число ярусов) равна увеличенной на единицу длине критического пути в ИГА. Напрямую использовать такую ЯПФ в качестве основы для построения расписания выполнения параллельной программы обычно затруднительно (ширина некоторых ярусов часто сильно превышает число имеющихся параллельных вычислителей). Но т.к. вычисление такой ЯПФ вычислительно малозатратно, во многих случаях целесообразно начинать анализ именно с ее получения и в дальнейшем проводить модификацию этой ЯПФ с учетом конкретных задач. При этом при каждой модификации ЯПФ получаем новую форму, полностью соответствующую исходному ИГА.

Определенным недостатком использования метода построения ЯПФ для получения расписания является невозможность учета времени исполнения операторов, однако для современных микроархитектур характерно всемерное стремление к одинаковости времен выполнения всех операторов, что как раз повышает удобство использования ЯПФ.

На рис. ниже приведен несложный случай алгоритма вычисления вещественных корней полного квадратного уравнения ax2+bx+c=0.

На рисунке -ярусно-параллельная форма алгоритма решения полного квадратного уравнения в вещественных числах в канонической форме (номера ярусов ЯПФ расположены справа)

Показанная ЯПФ уже является расписание выполнения параллельной программы (выполнение начинается сверху вниз, требует 6 относительных единиц времени и 4-х параллельных вычислителей). При этом число задействованных вычислителей по ярусам крайне неравномерно (важно при однозадачном режиме работы вычислительной системы) на 1-м ярусе задействованы все 4, на 2,3,4 - только один и по два на 5- и 6 ярусах. Однако легко видеть, что простейшее преобразование (показанные красным пунктиром допустимые перестановки операторов с яруса на ярус) позволяют выполнить тот же алгоритм за то же (минимальное из возможных) время всего на двух вычислителях! Не для любого алгоритма получается столь идеально часто для снижения требуемого числа параллельных вычислителей единственным путем является увеличение времени выполнения алгоритма (возрастание числа ярусов ЯПФ).

Для решения задач определения рационального (на основе заданных критериев) расписания выполнения произвольных алгоритмов создан инструментальный программный комплекс, включающая два модуля - D-F и SPF@home. Свободная выгрузка инсталляционных файлов доступна с ресурсов http://vbakanov.ru/dataflow/content/installdf.exe и http://vbakanov.ru/spf@home/content/installspf.exe соответственно (дополнительная информация по теме - http://vbakanov.ru/dataflow/dataflow.htm и http://vbakanov.ru/spf@home/spf@home.htm).

На рисунке - схема инструментального комплекса (*.set и *.gv программный файл и файл информационного графа анализируемой программы соответственно, *.mvr, *.med файлы метрик вершин и дуг графа алгоритма соответственно, *.cls, *.ops файлы параметров вычислителей и операторов программы соответственно, *.lua текстовый файл на языке Lua, содержащий методы реорганизации

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

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

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

Родительское приложение создано с использованием языка программирования С++, является GUI Win32-программой и доступно для свободной выгрузки и использования (как и исходные тексты) через GIT-репозиторий. Вывод данных осуществляется на экран в текстовом и графическом форматах и в файлы (также в структурированной текстовой форме).

Сочетание компилируемой родительской программы и встроенного интерпретатора скриптового языка позволило обеспечить высокую производительность и гибкость (Lua-вызовы фактически являются обертками для API-функций модуля SPF@home).

Копии экранов обсуждаемого комплекса приведены на изображениях ниже (программные модули D-F и SPF@home соответственно).

Модуль D-F (Data-Flow) является фактически универсальным вычислителем, выполняющим программу на ассемблероподобном языке на заданном числе параллельных вычислителей. При их числе большем 1 вычисления ведутся по принципу Data-Flow (реализуется статическая потоковая архитектура), операторы выполняются по условию готовности их к выполнению (ГКВ), что является следствием присвоенности значений все операндам данного оператора; при единичном вычислителе реализуется обычное последовательное выполнение. В случае превышения числа ГКВ-операторов числа свободных вычислители используется задаваемая система приоритетов их выполнения, условное выполнение реализуется предикатным выполнением, для реализации циклов используется система макросов, разворачивающая циклические структуры. Модуль D-F имеет встроенную систему проверку корректности ИГА, для контроля выполнения используется динамическая цветовая индикация выполненности операторов.

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

Такая программа может рассматриваться как результат компиляции с языков программирования высокого уровня, не содержащих явных указаний на параллелизацию вычислений. В модуле D-F программа отлаживается, результат выдается в файл ИГА-формата для обработки в модуле SPF@home. В модуле SPF@home для получения ЯПФ из gv-файла (стандартный формат текстовых файлов описаний графов), запоминания его во внутреннем представлении системы, создание ЯПФ и запоминание его в Lua-массиве для дальнейшей обработки может быть выполнен следующий код (наклоном выделены API-вызовы системы, двойной дефис означает начало комментария до конца строки):

CreateTiersByEdges("EdgesData.gv")  -- создать ЯПФ по файлу EdgesData.gv -- с подтянутостью операторов вверх-- CreateTiersByEdges_Bottom("EdgesData.gv")  -- создать ЯПФ по файлу EdgesData.gv -- с подтянутостью операторов вниз--OpsOnTiers={} -- создаём пустой 1D-массив OpsOnTiers for iTier=1,GetCountTiers() do -- по ярусам ЯПФ   OpsOnTiers[iTier]={} -- создаём iTier-тую строку 2D-массива OpsOnTiers   for nOp=1,GetCountOpsOnTier(iTier) do -- по порядковым номерам операторов на ярусе iTier        OpsOnTiers[iTier][nOp]=GetOpByNumbOnTier(nOp,iTier) -- взять номер оператора nOpend end -- конец циклов for по iTier и for по nOp

Для удобства данные метрик операторов и дуг графа выведены из gv-файлов и расположены в текстовых mvr и med-файлах, для моделирования выполнения программ на гетерогенном поле параллельных вычислителей служат cls и ops-файлы сопоставления возможностей выполнения определенных операторов на конкретных вычислителях. Преимуществом такого подхода является возможность задания нужных параметров целой группе объектов (списком типа от-до, причем список может быть и вырожденным) одной строкой файла. Задавать параметры можно по практически неограниченному количеству тегов, определяемых разработчиком.

Модуль SPF@home также позволяет определять время жизни данных между ярусами ЯПФ, что необходимо для определения/оптимизации параметров устройств временного хранения данных (обычно регистров процессора). Собственно размер данных при этом берется из med-файлов.

Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

Т.о. процедура составления расписания параллельного выполнения программы заключается в составлении Lua-программы, реализующей процедуры реорганизации ЯПФ в соответствие с заданными требованиями. Тремя типовыми встречающимися подзадачами (в реальном случае обычно требуется выполнение нескольких из этих подзадач одновременно) являются:

I. Балансировка числа операторов по всем ярусам заданной ЯПФ без увеличения ее высоты (минимизируется требуемое для решения задачи число параллельных вычислителей).

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

III. Получение расписания выполнения программы на гетерогенном поле параллельных вычислителей.

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

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

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

1) Получение исходной (не имеющей ограничений по ширине ярусов) ЯПФ.

2) Модификация этой ЯПФ в нужном направлении путем целенаправленной перестановки операторов с яруса на ярус при сохранении исходных связей в информационном графе алгоритма.

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

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

Методы достижения цели могут быть собственно разработанными эристиками (обычно ограниченной сложности для возможности использования в режиме реального времени) или стандартными - метод ветвей и границ, генетические, муравьиные и др. (чаще используются при исследовательской работе). Возможности системы включают использование оберток многофункциональных системных Windows-вызовов WinExec, ShellExecute и CreateProcess, так что исследователь имеет возможность вызова и управления любыми внешними программами (например, использовать тот же METIS в качестве процесса-потомка), файловое обслуживание при этом осуществляется средствами Lua.

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

На рис. показаны линейчатые диаграммы ширин ярусов реальных ЯПФ из копий экранов при работе системы SPF@home (средне-арифметическое значение ширин показано пунктиром, a) и символическая схема действия метода Bulldozer - б)

Многочисленные вычислительные эксперименты показывают, что во многих случаях удается значительно (до 1,5-2 раз) снизить ширину ЯПФ без увеличения высоты, но почти никогда до минимальной величины (средне-арифметическое значение ширин ярусов).

Т.о. истинной ценностью данного исследования являются именно эвристические методы (реализованные на языке Lua) создания расписаний выполнения параллельных программ при определённых ограничениях (напр., c учетом заданного поля параллельных вычислителей, максимума скорости выполнения, минимизации или ограничения размеров временного хранения данных и др.).

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

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

Список литературы

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-етербург, 2002. 608 c.

2. Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. : Мир, Книга по Требованию, 2012. 420 c.

3. AlgoWiki. Открытая энциклопедия свойств алгоритмов. URL: http://algowiki-project.org (дата обращения 31.07.2020).

4. ФедотовИ.Е.Параллельное программирование. Модели и приёмы. М.: СОЛОН-Пресс, 2018. 390 с.

5. Roberto Ierusalimschy. Programming in Lua. Third Edition. PUC-Rio, Brasil, Rio de Janeiro, 2013. 348 p.

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

В публикации на Habrе Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом от 26.11.2020 г. (http://personeltest.ru/aways/habr.com/ru/post/530078/) описан исследовательский программный комплекс для анализа произвольного алгоритма на наличие скрытого потенциала параллелизма и инструментарий для построения рационального каркаса расписания параллельной программы.

Комплекс включает модуль программного симулятора универсального вычислителя, реализующий Data-Flow (далее D-F) подход к управлению последовательностью вычислений [1] с использованием архитектуры SMP (Symmetric MultiProcessing, симметричная мультипроцессорность), позволяющий выполнять произвольную программу, разработанную на языке программирования уровня Ассемблера [2], причем порядок операндов соответствует стилю AT&T. Программная модель использует трёхадресные команды, условность выполнения осуществляется предикатным методом, [3]). D-F симулятор позволяет гибко управлять параметрами потокового выполнения программ в соответствии с концепцией ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд) и автоматически (в физической реализации на аппаратном уровне) генерировать план выполнения параллельной программы [4].

В вычислителях потоковой архитектуры процесс выбора операторов для исполнения удобно представить результатом взаимодействия некоторых сущностей, асинхронно выполняющих определенные действия актёров [5], при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов.

Второй модуль комплекса (SPF@home, далее SPF) служит для выявления в Информационном Графе Алгоритма (далее ИГА) скрытого параллелизма методом построения Ярусно-параллельной Формы (далее ЯПФ) алгоритма [5] c последующей реорганизацией ЯПФ путём последовательных целенаправленных изменений без нарушения информационных связей [6] для составления рационального каркаса расписания выполнения параллельной программы. Одной из важных целей реорганизации ЯПФ является повышение плотности кода (формально определяемой в данном случае равномерностью заполнения ярусов ЯПФ операторами). Т.к. задачи составления расписаний относят к классу NP-полных [7], в данной работе использован метод разработки, основанный на создании и итерационном улучшении основанных на эвристическом подходе сценариев реорганизации ЯПФ [8] (собственно сценарии разрабатываются с использованием скриптового языка Lua [9]).

Исходными данными для модуля SPF служат ИГА-файлы стандартного формата, которые могут быть получены путём импорта из системы D-F или любым иным (в общем случае уровень операторов может быть любым необязательно соответствующим концепции ILP).

Исходя из сложности алгоритмов обработки данную область исследований можно обоснованно отнести к наиболее сложным областям Науки о данных (Data Science).

Все вышеописанные программные модули полностью Open Source, свободная выгрузка инсталляционных файлов доступна с ресурсов http://vbakanov.ru/dataflow/content/install_df.exe и http://vbakanov.ru/spf@home/content/install_spf.exe соответственно (дополнительная информация - http://vbakanov.ru/dataflow/dataflow.htm и http://vbakanov.ru/spf@home/spf@home.htm).

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

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

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

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

Набор API-вызовов системы SPF позволяет получить информацию о требуемых при выполнении заданного алгоритма параметрах (времени жизни данных, далее ВЖД). Эти данные появляются следствием выполнения отдельных операторов и, в свою очередь, служат входными операндами для иных операторов (метафорически можно сказать, это такие ВЖД живут между ярусами ЯПФ).

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

На рис.1 и 2 показаны расписания выполнения в форме ЯПФ (причём, как и было принято ранее, выполнение осуществляется в направлении увеличения номеров ярусов) алгоритма решения полного квадратного уравнения в вещественных числах (аналогично рис.2 предыдущей статьи для исходной и модифицированной ЯПФ соответственно; при этом номера операторов в овалах (111-116) соответствуют операциям присвоения (или передачи из внешних модулей) начальных значений для расчёта. Диаграммы ВЖД приведены в форме отдельных блоков, включающих циклы генерация использование уничтожение данных, поэтому некоторые номера операторов дублируются.

Рисунок1Исходная ЯПФ алгоритма (слева) и соответствующая диаграмма ВЖД (справа, формула одновременно существующих данных 6-5-4-3-3-3-2)

Рисунок2Модифицированная (один из вариантов) ЯПФ рис.1 и соответствующая ВЖД данных (формула 6-7-5-3-3-3-2)

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

Анализ ВЖД в случае полностью последовательного характера выполнения показанного на рис.3 алгоритма (линейчатые графики распределения количества данных отрисовываются непосредственно системой SPF@home). Собственно ЯПФ здесь вырождена, имеет ширину 1 и содержит 11 исполняемых операторов (плюс уровни исходных и выходных данных).

Рисунок3Количество одновременно существующих данных для трёх (слева направо) вариантов последовательного выполнения алгоритма рис. 1 (слева от диаграммы промежуток ярусов с указанием номеров операторов в формате предыдущий / последующий; in и out входные и выходные данные соответственно, в прямоугольниках диаграммы количество данных)

Первыми (не единственными!) претендентами на линейность исполнения являются находящиеся на ярусах 1,5,6 (рис. 1) операторы, причем вследствие ортогональности по данным они могут быть выполнены в любой последовательности. При этом достигаются разные качества распределения ВЖЛД (на рис. 3 варианта, локальным оптимумом из которых является последний, характеризующийся максимумом числа данных 6 единиц). В данном случае вычислительная сложность процедуры реорганизации ЯПФ явилась незначительной - оказалось достаточным всего двух перестановок операторов (изменения в положении коснулись операторов 101,102,103. Даже в таком простом примере результат оптимизации стоит свеч, для более сложных случаев качество оптимизации будет более значительным.

Следующим этапом определения параметров устройства временного хранения данных является определение необходимых объемов (данные поочередно используют одни и те же области памяти) этого устройства (например, числа регистров общего назначения); для этого применяются известные приемы (напр., метод раскраски графов, [10]). Такие возможности не поддерживаются API модуля SPF@home и могут быть реализованы средствами встроенного языка Lua или внешними модулями.

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

Список литературы

1. J.B.Dennis, D.P.Misunas. A Preliminary Architecture for a Basic Data-Flow Processor. In Proc. Second Annual Symp. Computer Architecture, pр. 126-132, Houston, Texas, January, 1975.

2. БакановВ.М.Параллелизация обработки данных на вычислителях потоковой (Data-Flow) архитектуры. //Журнал Суперкомпьютеры, M.: 2011, 5, с.54-58.

3. Э.Таненбаум, Т.Остин. Архитектура компьютера. СПб.: Изд. Питер, 2019. 816 c.

4. БакановВ.М.Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. //Журнал Программная инженерия", М.: 2015, 9, c. 20-24.

5. ФедотовИ.Е.Параллельное программирование. Модели и приёмы. М.: СОЛОН-Пресс, 2018. 390 с.

6. БакановВ.М. Программный комплекс для разработки методов построения оптимального каркаса параллельных программ. //Журнал Программная инженерия", М.: 2017, том 8,2, c. 58-65.

7. M.R.Gary, D.S.Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H.Freeman and Company, San Francisco, 1979. 338 pp.

8. V.M.Bakanov. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Computer Science, Volume 8, Issue 1, Pages 228234, ISSN (Online) 2299-1093, DOI: https://doi.org/10.1515/comp-2018-0019.

9. Roberto Ierusalimschy. Programming in Lua. Third Edition. PUC-Rio, Brasil, Rio de Janeiro, 2013. 348 p.

10. Карпов В.Э. Теория компиляторов. Часть 2. Двоичная трансляция. URL: http://www.rema44.ru/resurs/study/compiler2/Compiler2.pdf (дата обращения 15.12.2020).

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

Естественным перед началом анализа будет указание ограничений на ширину и глубину исследований. Принимаем, что многозадачность в рассматриваемых параллельных системах осуществляется простейшим путём - перегрузкой всего блока (связки) выполняющихся операторов (одновременное выполнение операторов разных программ не предполагается) или же система работает в однозадачном режиме; в противном случае высказанное в предыдущей фразе утверждение может быть неверным. Минимизация объёма устройств временного хранения данных (описано здесь http://personeltest.ru/aways/habr.com/ru/post/534722/) проводиться не будет. На этом этапе исследований также не учитываются задержки времени на обработку операторов и пересылку данных между ними (для системы SPF@home формально эти параметры могут быть заданы в файлах с расширениями med и mvr).

В предыдущей публикации http://personeltest.ru/aways/habr.com/ru/post/540122/ была описана технология получения ПВПП на основе модели потокового (Data-Flow) вычислителя. Обычно считают, что правила выбора операторов для выполнения в такой машине подчиняются логике действия некоторых сущностей, совместно выполняющих определённые действия актёров (actors); при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов. В общем случае при этом отдельные операторы выполняются асинхронно. В публикации показано, что описанный принцип получения ПВПП приемлем (при выполнении несложных условий) и для машин архитектуры VLIW (Very Long Instruction Word, сверхдлинное машинное слово), отличающихся требованием одновременности начала выполнения всех операторов в связке. В расчётах использовали модель ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд).

В рассматриваемый программный комплекс http://personeltest.ru/aways/habr.com/ru/post/530078/ включен модуль SPF@home, позволяющей работать с гранулами параллелизма любого размера (оператор любой сложности). Основным инструментом этого модуля является метод получения ярусно-параллельной формы (ЯПФ) графа алгоритма (здесь используется информационный граф, в котором вершинами являются узлы преобразования информации, а дугами её передачи).

Реформирование ЯПФ может дать результат, идентичный полученному моделированием выполнения программы на Data-Flow -машине, но в некоторых случаях результаты расходятся. В самом деле, это во многом различные подходы. Не столь сложно представить себе рой самостоятельных, взаимодействующих программ-актёров, выполняющих действия по поиску готовых к выполнению операторов, свободных в данный момент отдельных вычислителей и назначающих обработку выбранных операторов конкретному вычислителю etc etc, но действия эти логично производятся в RunTime и именно на границе (линии фронта) между уже выполненными и ещё не выполненными операторами (метафора поиска в ширину, а не в глубину в теории графов). При этом естественным образом создаётся очень подробный план выполнения параллельной программы с точными временными метками начала и конца выполнения операторов с привязкой их к конкретным вычислителям. Такой план хорош (с точностью до математической модели, которая в конечном счёте всегда в чём-то ограничена), однако автор сомневается в степени достаточной безумности практического использования полученного т.о. ПВПП

Метод обработки ЯПФ в целом более теоретичен и от многих особенностей абстрагирован, однако он может ещё до выполнения программы (DesignTime) показать ПВПП сверху (учитывая не только параллельный фронт выполнения операторов, но и всю карту боевых действий). Следствием большего абстрагирования ЯПФ-метода является субъективность интерпретации связи моментов обработки операторов с собственно ярусом ЯПФ. В самом деле, можно рассмотреть несколько укрупнённых подходов к таким интерпретациям; см. рис. ниже слева варианты a) и б) соответственно. На этом рисунке операторы показаны красными прямоугольниками, а яруса (в целях большей выразительности сказанного) - горизонтальными линиями:

• выполнение всех принадлежащих конкретному ярусу операторов начинается одновременно (тогда это фактически VLIW-идеологема и ПВПП изначально обладает ограниченностью, связанной с потерями времени на ожидание выполнения наиболее длительного оператора на ярусе; точное решение получается лишь при одинаковости времён выполнения всех операторов на ярусе);

• промежуток времени выполнения операторов может плавать относительно связанного с ярусом момента времени (возможна даже ограниченная асинхронность выполнения операторов).

При использовании ЯПФ в своих изысканиях Исследователь должен сам выбрать определённую модель и далее ей следовать. В рамках системы SPF@home, например, имеется возможность целевой реорганизации ЯПФ с конечной целью собрать на ярусах операторы с наиболее близкими длительностями обработки. Именно использование ЯПФ как нельзя лучше отвечает идеологеме EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд), позволяющей параллельной вычислительной системе выполнять инструкции согласно плану, заранее сформированному компилятором. Не следует игнорировать и субъективный фактор - бесспорным преимуществом ЯПФ является возможность простой и недвусмысленной визуализации собственно ПВПП.

Исходными данными для модуля SPF@home служат описания информационных графов алгоритма (программы) в стандартной DOT-форме (расширения файлов gv, могущие быть полученными импортом из модуля Data-Flow или иными путями). Допустимые (не нарушающие информационные связи в алгоритме) преобразования ЯПФ управляются программой на языке Lua, реализующей разработанные методы реструктуризации ЯПФ (дополнительная информация приведена в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/). Эти методы неизбежно будут являться эвристическими вследствие невозможности прямого решения поставленных (относящихся к классу NP-полных) задач.

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

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

В качестве пациентов использовались имеющиеся в наличии информационные графы алгоритмов, в основном класса линейной алгебры (как одни из наиболее часто встречающиеся в современных задачах обработки данных). По понятным причинам исследования проводились на данных небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в форме информационного графа в модуль SPF@home.

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

Ниже приведены результаты моделирования трёх наиболее часто встречающихся типов задач (в реальном случае обычно требуется выполнение нескольких из них одновременно):

1.Расписание выполнения программ на минимальном числе параллельных вычислителей при сохранении высоты ЯПФ

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

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

Эмпирический метод 1-01_bulldozer имеет целью получение наиболее равномерного распределения операторов по ярусам ЯПФ без возрастания её высоты (сохранение времени выполнения программы); операторы переносятся только вниз (первоначально ЯПФ строится в верхнем варианте). Для этого метод старается перенести операторы с ярусов шириной выше среднего на яруса с наименьшей шириной. На каждом ярусе операторы перебираются в порядке очередности слева направо.

Метод 1-02_bulldozer является модификацией предыдущего с адаптацией. Для оператора с максимумом вариативности (назовём так диапазон возможного размещения операторов по ярусам ЯПФ без изменения информационных связей в графе алгоритма) в пределах яруса вычисляются верхний и нижний пределы его возможного расположения по ярусам.

В результирующей табл.1 рассматриваются: mnk_N программа аппроксимации методом наименьших квадратов N точек прямой, mnk_2_N то же, но квадратичной функцией, korr_N вычисление коэффициента парной корреляции по N точкам, slau_N решение системы линейных алгебраических уравнений порядка N прямым (не итерационным) методом Гаусса, m_matr_N - программа умножения квадратных матриц порядка N традиционным способом, m_matr_vec_N умножение квадратной матрицы на вектор, squa_equ_2 решение полного квадратного уравнения в вещественных числах, squa_equ_2.pred то же, но с возможностью получения вещественных и мнимых корней при использовании метода предикатов для реализации условного выполнения операторов, e17_o11_t6, e313_o206_t32, e2367_o1397_t137, e451_o271_t30, e916_o624_t89, e17039_o9853_t199 сгенерированные специальной программой по заданным параметрам информационного графа. Вычислительную трудность преобразования будем характеризовать числом перемещений операторов с яруса на ярус. Неравномерность распределения числа операторов по ярусам ЯПФ характеризуется коэффициентом неравномерности (отношение числа операторов на наиболее и наименее нагруженных ярусов соответственно).

Для удобства анализа в таблице цветом выделены ячейки, соответствующие случаю достижению снижения ширины без возрастания высоты ЯПФ, а жирным начертанием цифр величины для сравнения.

Как видно из табл.1, во многих случаях удается значительно (до 1,5-2 раз) снизить ширину ЯПФ, но почти никогда до минимальной величины (средне-арифметическое значение ширин ярусов). В целом эвристика 1-02_bulldozer несколько более эффективна, но проигрывает по вычислительной сложности. В большинстве случаев увеличение размера обрабатываемых данных повышает эффективность балансировки (очевидно, это связано с повышением числа степеней свободы ЯПФ).

Интересно, что для некоторых алгоритмов (напр., slau_N) ни один из предложенных методов не дал результата. Сложность балансировки ЯПФ связана с естественным стремлением разработчиков алгоритмов создавать максимально плотные записи последовательности действий.

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

Практический интерес представляют методы с увеличением высоты ЯПФ (см. табл.2, в которой дано сравнение двух методов с метафорическими названиями Dichotomy и WidthByWidth); при этом приходится смириться с увеличение времени выполнения программы. В ходе вычислительных экспериментов задавалась конечная ширина преобразованной ЯПФ (отдельные столбцы в правой части табл.2). Количественные параметры преобразований выдавались в форме частного, где числитель и знаменатель показывают число перемещений (первая строка), высоту ЯПФ (вторая) и коэффициент ковариации CV (третья строка) для каждого исследованного графа. Характеризующий неравномерность распределения ширин ярусов коэффициент ковариации рассчитывался как CV=/W, где - среднеквадратичное отклонение числа операторов по всем ярусам ЯПФ, W - среднеарифметическое числа операторов по ярусам.

Эвристика Dichotomy предполагает для разгрузки излишне широких ярусов перенос половины операторов на вновь созданный ярус под текущим, эвристика WidthByWidth реализует постепенный перенос операторов на вновь создаваемые яруса ЯПФ. Из табл.2 видно, что метод WidthByWidth в большинстве случаев приводит к лучшим результатам, нежели Dichotomy (например, высота преобразованной ЯПФ существенно меньше что соответствует снижению времени выполнения параллельной программы притом за меньшее число перемещений операторов).

3.Расписание выполнения программ на фиксированном числе гетерогенных параллельных вычислителей

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

Модуль SPF@home поддерживает эту возможность путём сопоставления информации из двух файлов для операторов и вычислителей (*.ops и *.cls соответственно). Имеется возможность задавать совпадение по множеству свободно назначаемых признаков для любого диапазона операторов/вычислителей. Условием выполнимости данного оператора на заданном вычислителе является minVal_1Val_1maxVal_1 для одинакового параметра (Val_1, minVal_1, maxVal_1 числовые значения данного параметра для оператора и вычислителя соответственно).

Разработка расписания для выполнения программы на гетерогенном поле параллельных вычислителей является более сложной процедурой относительно вышеописанных и здесь упор делается на программирование на Lua (API-функции системы SPF@home обеспечивают минимально необходимую поддержку). Т.к. на одном ярусе ЯПФ могут находиться операторы, требующие для выполнения различных вычислителей, полезным может служить концепция расцепления ярусов ЯПФ на семейства подъярусов, каждое из которых соответствует блоку вычислителей c определёнными возможностями (т.к. все данного операторы яруса обладают ГКВ-свойством, последовательность выполнения их в пределах яруса/подъяруса в первом приближении произвольна). На схеме ниже слева показано расщепление операторов на одном из ярусов ЯПФ в случае наличия 6 параллельных вычислителей 3-х типов.

Пример плана выполнения программы на поле из 3-х типов параллельно работающих вычислителей (c количествоv 5,3,4 штук соответственно и номерами 1-5, 6-8, 9-12 по типам, всего 12 штук) приведён в табл.3. При расчёте в качестве исходной использовался конкретный алгоритм, характеризующийся ЯПФ с числом операторов 206 и дуг 323, ярусов 32 (после расчета подъярусов получилось 48). Первый столбец таблицы показывает (разделитель символ прямого слеша) номер яруса/подъяруса; в ячейках таблицы приведены номера операторов, сумма их числа по подъярусам равно числу операторов на соответствующем ярусе ЯПФ.

Моделирование, результат которого приведён в табл.3, может быть использовано в форме решения обратной задачи при определении оптимального числа параллельных вычислителей различного типа для выполнения заданных алгоритмов (групп алгоритмов).

В самом деле, в рассматриваемом случае общее время T решения задачи определяется суммой по всем ярусам максимальных значений времён выполнения операторов на подъярусах данного яруса, т.к. группы операторов на подъярусах выполняются последовательно (первая сумма берётся по j, вторая по i, максимум по k_j):

T=(maxt_ik),

где j - число ярусов ЯПФ, i - число подъярусов на данном ярусе, k_{j -} типы вычислителей на j-том ярусе, t_{ik -} время выполнения оператора типа i на вычислителе типа k. Если ставится задача достижения максимальной производительности, вполне возможно определить число вычислителей конкретного типа, минимизирующее T (напр., для показанного табл.3 случая количество вычислителей типа II полезно увеличить в пику вычислителяv типа I).

Задача минимизации общего времени решения T усложняется в случае возможности выполнения каждого оператора на нескольких вычислителях вследствие неоднозначности t_ik в вышеприведённом выражении; здесь необходима дополнительная балансировка по подъярусам.

Описание параметров операторов располагается в файлах с расширением ops, параметров вычислителей cls; соответствующая API-функция (обёрнутая Lua-вызовом) возвращает значение, разрешающее или запрещающее выполнение данного оператора на заданном вычислителе. Описанные файлы являются текстовыми (формат данных определён в документации), что даёт возможность разработки внешних программ для генерации требуемого плана эксперимента с использованием модуля SPF@home в режиме командной строки.

---

В порядке обсуждения небезынтересно будет рассмотреть вариант ЯПФ в нижней форме (при этом все операторы перемещены максимально в сторону окончания выполнения программы). Такая ЯПФ может быть получена из верхней перемещениями операторов по ярусам как можно ниже или проще построением ЯПФ в направлении от конца программы к её началу. Ниже проиллюстрировано сравнение распределения ширин ЯПФ в верхней и нижней формах (изображения в строке слева и справа соответственно в 4-х рядах) для алгоритма умножения матриц традиционным способом при порядках матриц N=3,5,7,10. Здесь H, W и W высота, ширина и среднеарифметическая ширина ЯПФ (последняя показана на рисунках пунктиром; символ прямого слеша разделяет параметры для верхней и нижней ЯПФ (фиолетовый цвет ярус максимальной ширины, красный минимальной).

Соответствующие иллюстрации для процедуры решения систем линейных алгебраических уравнения порядков N=3,5,7,10 безытерационным методом Гаусса представлены ниже.

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

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

---

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

Выше использованные количественные характеристики неравномерности не дают информации о форме кривой, обладающей этой неравномерностью. В качестве дополнительной оценки неравномерности распределения операторов по ярусам ЯПФ может быть признан известный графо-аналитического метод определения дифференциации доходов населения, заключающегося в расчёте численных параметров расслоения (кривая Лоренца и коэффициент Джини), несмотря на зеркально-противоположную форму анализируемых кривых. Удобство сравнения ЯПФ различных алгоритмов достигается нормированием обоих осей графиков на общую величину (единицу или 100%).

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

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

Итак, программная система SPF@home выполняет практическую задачу по составлению расписаний выполнения заданных алгоритмов (программ) на заданном поле параллельных вычислителей и дает возможность проводить различного типа исследования свойств алгоритмов (в данном случае оценивать вычислительную сложность методов составления расписаний). Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

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

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

---

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

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021).

Основные данные вычислительных экспериментов по реорганизации ярусно-параллельной формы (ЯПФ) информационных графов алгоритмов (ТГА) приведены в предыдущей публикации (http://personeltest.ru/aways/habr.com/ru/post/545498/). Цель текущей публикации показать окончательные результаты исследований разработки расписаний выполнения параллельных программ в показателях вычислительной трудоёмкости собственно преобразования и качества полученных расписаний. Данная работа является итогом вполне определённого цикла исследований в рассматриваемой области.

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

Т.к. в принятой модели ЯПФ фактически определяет порядок выполнения операторов параллельной программы (операторы выполняются группами по ярусам поочерёдно), в целях сокращения будем иногда использовать саму аббревиатуру ЯПФ в качестве синонима понятия плана (расписания) выполнения параллельной программы. По понятным причинам исследования проводились на данных относительно небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в формате информационного графа в модуль SPF@home для дальнейшей обработки.

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

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

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

Полученные результаты предназначаются для улучшения качества разработки расписаний выполнения параллельных программ в распараллеливающих компиляторах будущих поколений. При этом внутренняя реализация данных конечно, совсем не обязана предусматривать явного построения ЯПФ в виде двумерного массива, как для большей выпуклости показано на рис.2 в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/ и выдаётся программным модулем SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe). Она может быть любой удобной для компьютерной реализации например, в наивном случае устанавливающей однозначное соответствие между формой ИГА в виде множества направленных дуг {k,l} (матрица смежности) и двоек номеров вершин i_k,j_k и i_l,j_l, где i,j номера строк и столбцов в ЯПФ (процедуру преобразования ИГА в начальную ЯПФ провести всё равно придётся, ибо в данном случае именно она выявляет параллелизм в заданном ИГА алгоритме; только после этого можно начинать любые преобразования ЯПФ).

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

Для каждой из группы рассматриваемых задач (преобразования с сохранением высоты исходной ЯПФ или при возможности увеличения высоты оной) рассмотрим по две методики (эвристики, ибо так согласились именовать разработки) для перового случая это 1-01_bulldozer vs 1-02_bulldozer, для второго - WidthByWidtn vs Dichotomy. Мне стыдно повторять это, но высота ЯПФ определяет время выполнения программы

1. Получение расписания параллельного выполнения программ при сохранении высоты ЯПФ

Сохранение высоты исходной ЯПФ равносильно выполнению алгоритма (программы) за минимально возможное время. Наиболее равномерная нагрузка на все вычислители параллельной системы будет при одинаковой ширине всех ярусов ЯПФ (среднеарифметическое значение). В ЯПФ реальных алгоритмов и размерности обрабатываемых данных среднеарифметическое значение является довольно большим (практически всегда много большим числа отдельных вычислителей в параллельной системе). Т.о. рассматриваемый случай не часто встречается в практике, но всё же должен быть разобран.

Для сравнения выберем часто анализируемые ранее алгоритмы и два эвристических метода целенаправленного преобразования их ЯПФ эвристики 1-01_bulldozer и 1-02_bulldozer.

Результаты применения этих эвристик приведены на рис. 1-3; обозначения на этих рисунках (по осям абсцисс отложены показатели размерности обрабатываемых данных):

• графики a), b) и с) ширина ЯПФ, коэффициент вариации (CV ширин ярусов ЯПФ), число перемещений (характеристика вычислительной трудоёмкости) операторов соответственно;

• сплошные (красная), пунктирные (синяя) и штрих-пунктирные (зелёная) линии исходные данные, результат применения эвристик 1-01_bulldozer и 1-02_bulldozer cответственно.

Рисунок 1. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма умножения квадратных матриц 2,3,5,7,10-го порядков (соответствует нумерации по осям абсцисс) классическим методомРисунок 2. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма вычисления коэффициента парной корреляции по 5,10,15,20-ти точкам (соответствует нумерации по осям абсцисс)Рисунок 3. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма решения системы линейных алгебраических уравнений (СЛАУ) для 2,3,4,5,7,10-того порядка (соответствует нумерации по осям абсцисс) прямым (неитерационным) методом Гаусса

Данные рис. 1-3 показывают, что во многих случаях удаётся приблизиться к указанной цели. Напр., рис. 1a) иллюстрирует снижение ширины ЯПФ до 1,7 раз (метод 1-01_bulldozer) и до 3 раз (метод 1-02_bulldozer) при умножении матриц 10-го порядка.

Коэффициент вариации ширин ярусов ЯПФ (рис. 1b) приближается к 0,3 (граница однородности набора данных) при использовании эмпирики 1-02_bulldozer и, что немаловажно, достаточно стабилен на всём диапазоне размерности данных.

Трудоёмкость достижения результата (рис. 1c) при использовании метода 1-02_bulldozer значительно ниже (до 3,7 раз при порядке матриц 10) метода 1-01_bulldozer.

Важно, что эффективность метода возрастает с ростом размерности обрабатываемых данных.

Не менее эффективным показал себя метод 1-02_bulldozer на алгоритме вычисления коэффициента парной корреляции (рис. 2).

Попытка реорганизации ЯПФ алгоритма решения системы линейных алгебраических уравнений (СЛАУ) порядка до 10 обоими методами (рис. 3) оказалась малополезной. Ширину ЯПФ снизить не удалось вообще (рис. 3a), снижение CV очень мало (рис. 3b), однако метод 1-02_bulldozer немного выигрывает в трудоёмкости (рис. 3c).

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

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

Эта постановка задачи максимально близка к реальному случаю составления расписания для VLIW-машины с заданным числом процессорных команд в машинном слове (размер связки, бандла сверхдлинного машинного слова). При этом достигается и повышение плотности кода.

Ниже рассматривается распространенный случай выполнения программы на заданном гомогенном поле из W параллельных вычислителей (от W=W₀ до W=1, где W₀ ширина ЯПФ, а нижняя граница соответствует полностью последовательному выполнению). Сравниваем два метода реорганизации ЯПФ Dichotomy и WidthByWidtn:

• Dichotomy. Цель получить вариант ЯПФ с c шириной не более заданного W c увеличением высоты методом перенесения операторов с яруса на вновь создаваемый ярус ниже данного. Если ширина яруса выше W, ровно половина операторов с него переносится на вновь создаваемый снизу ярус и так далее, пока ширина станет не выше заданной W. Метод работает очень быстро, но грубо (высота ЯПФ получается явно излишней и неравномерность ширин ярусов высока).

• WidthByWidtn. Подлежат переносу только операторы яруса с числом операторов выше заданного N>W путём создания под таким ярусом число ярусов М, равное:

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

На рис. 4,5 показаны результаты выполнения указанных эвристик в применении к двум распространенным алгоритмам линейной алгебры - умножение квадратных матриц классическим методом и решение системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса; красные и синие линии на этих и последующих рисунках соответствуют эвристикам WidthByWidtn и Dichotomy соответственно. Не забываем, что ширина реформированной ЯПФ здесь соответствует числу команд в связке сверхдлинного машинного слова.

Рисунок 4. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм умножения квадратных матриц классическим методом 5 и 10-го порядков рис. a) и b) соответственноРисунок 5. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм решения системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса 5 и 10-го порядков рис. a) и b) соответственно

Как видно из рис. 4 и 5, оба метода на указанных алгоритмах приводят к близким результатам (из соображений представления ЯПФ плоской таблицей и инвариантности общего числа операторов в алгоритме это, конечно, гипербола!). При большей высоте ЯПФ увеличивается время жизни данных, но само их количество в каждый момент времени снижается.

Однако при всех равно-входящих соответствующие методу WidthByWidtn кривые расположены ниже, нежели по методу Dichotomy; это соответствует несколько большему быстродействию. Полученные методом WidthByWidtn результаты практически совпадают с идеалом высоты ЯПФ, равным N_сумм./W_средн. , где N_сумм. общее число операторов, W_средн. среднеарифметическое числа операторов по ярусам ЯПФ при заданной ширине ея.

Рисунок 6. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма умножения квадратных матриц 10-го порядка классическим методом (ось абсцисс ширина ЯПФ после реформирования)Рисунок 7. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма решения системы линейных алгебраических уравнений 10-го порядка прямым (неитерационным) методом Гаусса (ось абсцисс ширина ЯПФ после реформирования)

Анализ результатов, приведённый на рис. 6 и 7, более интересен (хотя бы потому, что имеет чисто практический интерес вычислительную трудоёмкость преобразования ЯПФ). Как видно из рис. 6 и 7, для рассмотренных случаев метод WidthByWidtn имеет меньшую (приблизительно в 3-4 раза) вычислительную трудоёмкость (в единицах числа перестановок операторов с яруса на ярус) относительно метода Dichotomy (хотя на первый взгляд ожидается обратное). Правда, при этом метод (эвристика) WidthByWidtn обладает более сложной внутренней логикой по сравнению с Dichotomy (в последнем случае она примитивна).

Т.о. проведено сравнение методов реорганизации (преобразования) ЯПФ конкретных алгоритмов с целью их параллельного выполнения на заданном числе вычислителей. Сравнение проведено по критериям вычислительной трудоёмкости преобразований и неравномерности загрузки параллельной вычислительной системы.

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

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

---

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

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021)

• Параллелизм и плотность кода (http://personeltest.ru/aways/habr.com/ru/post/545498/, 05.03.2021)

• Сколько стоит расписание (http://personeltest.ru/aways/habr.com/ru/post/551688/, 10.04.2021) - текущая