Реальная производительность параллельных вычислительных систем

Анализ «узких мест» процесса решения задач и их влияния на реальную производительность

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

Эффективность — понятие многоплановое. Это - удобство использования тех­ники и программного обеспечения, наличие необходимого интерфейса, простота доступа и многое другое. Но главное — это достижение близкой к пиковой производительности вычислительных систем. Данный фактор настолько ва­жен, что всю историю развития вычислительной техники и связанных с ней областей можно описать как историю погони за наивысшей эффективно­стью решения задач.

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

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

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

Исследования показывают, что большинство из «узких» мест может быть объединено в три группы.

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

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

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

Если технология позволяет разложить программу на фрагменты, по которым почти всегда будет строиться эффективный код, то «узких» мест в этой группе может не быть. Такие технологии были разработаны для первых параллель­ных вычислительных систем. Но по мере усложнения вычислительной техники техно­логии компиляции становятся все менее и менее эффективными, и «узких» мест в третьей группе оказывается все больше и больше. Для больших рас­пределенных вычислительных систем «узкие» места компиляции начинают играть решающую роль в потере общей эффективности. Поэтому уже давно наметилось и те­перь почти воплотилось в реальность "компромиссное" разделение труда: наименее алгоритмизированные и сложно реализуемые этапы компиляции, в первую очередь, расщепление программы на параллельные ветви вычислений, распределение данных по модулям оперативной памяти и организацию пересылок данных возлагаются на пользователя. Проблем от этого не стало меньше. Просто о том, о чем раньше заботились разработчики компиляторов, теперь должны беспокоиться сами пользователи.

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

«Узкие» места, обусловленные иерархической структурой памяти

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

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

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

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

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

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

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

На стадии перевода программ в машинный код компилятор может выстраивать команды таким образом, чтобы эффект от использования регистровой и кэш-памяти был максимальным. Но это делается не всегда.

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

Если для реализации алгоритма нужно не просто составить какую-нибудь программу, а добиться, чтобы она работала максимально быстро, то соблю­дение этих правил может дать ощутимый эффект. Как уже отмечалось, многие вычислительные системы особенно быстро осуществляют доступ к словам с по­следовательными физическими адресами. Пусть, например, программа со­ставляется на языке Fortran. С точки зрения этого языка безразлично, про­водить обработку элементов массивов по строкам или столбцам. Безразлично это и с точки зрения сложности получаемой программы. Все различие сводится лишь к тому, что в одном случае мы имеем дело с преоб­разованием элементов каких-то матриц, а в другом — транспонированных к ним. Принимая во внимание специфику доступа к оперативной памяти, компиляторы с языка Fortran всегда располагают массивы в физической оперативной памяти последова­тельно по адресам, столбец за столбцом, слева направо и сверху вниз. Пред­положим, что реализуется алгоритм решения систем линейных алгебраиче­ских уравнений методом Гаусса. В этом случае время работы программы будет определяться ее трехмерными циклами. В зависимости от того, распо­ложена матрица системы в массиве по столбцам или строкам, внутренние циклы программы будут также осуществлять обработку элементов массивов по столбцам или строкам. Времена реализации обоих вариантов могут раз­личаться весьма заметно, иногда в несколько раз. Факт существенный, если речь идет о разработке оптимальных программ.

Дата добавления: 2014-01-04