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

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

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

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

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

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

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

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

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

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

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

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

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

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

• чтение на первых курсах трех-четырех лекций "Введение в параллельные вычисления";
• введение в базовые циклы по математике и программированию начальных сведений о параллельных вычислениях;
• существенная перестройка цикла лекций по численным методам с обязательным описанием информационной структуры каждого алгоритма;
• организация практикума по параллельным вычислениям;
• чтение специального курса " Параллельная структура алгоритмов";
• чтение специального курса "Параллельные вычисления".

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

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

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

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

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

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

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

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

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

Другой аргумент связан с возможной перспективой развития вычислительной техники. Скорости решения больших задач приходится повышать сегодня и заведомо придется повышать в будущем. Как правило, основные надежды связываются с созданием на основе различных технологических достижений более скоростных универсальных систем. Но повышать скорость работы вычислительной техники можно и за счет ее специализации . Уже давно практикуется использование спецпроцессоров, осуществляющих очень быструю реализацию алгоритмов быстрого преобразования Фурье, обработки сигналов, матричных операций и т.п. А теперь вспомним гипотезу о типовых структурах. Если она верна, то в конкретных прикладных областях можно будет выделить наиболее часто используемые алгоритмы и для них тоже построить спецпроцессоры. Тем самым открывается путь создания специализированных вычислительных систем для быстрого и сверхбыстрого решения задач из заданной предметной области .

Основная трудность введения в практикум заданий, связанных с изучением структуры алгоритмов, является отсутствие в настоящий момент доступного и простого в использовании программного обеспечения для построения графов алгоритмов и проведения на их основе различных исследований. По существу есть только одна система, которая реализует подобные функции. Это система V-Ray, разработанная в Научно- исследовательском вычислительном центре МГУ. Она дает возможность для различных классов программ строить графы алгоритмов и изучать их параллельную структуру. Система V-Ray реализована на персональном компьютере и не зависит от целевого компьютера. Последнее обстоятельство исключительно важно для организации практикума, поскольку частый выход с мелкими задачами на большие вычислительные системы не очень реален даже для вузов с хорошим техническим оснащением. На персональных же компьютерах время освоения задач практикума практически неограниченно. В настоящее время V-Ray представляет сложную исследовательскую систему. Далеко не все ее функции нужны для организации практикума. Со временем система V-Ray станет доступной для широкого использования. Информацию о ней и ее возможностях можно получить

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

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

Способы синхронизации параллельного взаимодействия

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

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

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

Типичные задачи, допускающие параллельные вычисления

• map - выполнение одной и той же функции над каждым элементом массива входных данных, с получением равного по мощности массива результатов вычисления
• reduce - выполнение одной и той же функции для добавления вклада каждого элемента входных данных в одно итоговое значение

Программные инструменты параллелизма

• OpenMP - стандарт интерфейса приложений для параллельных систем с общей памятью.
• POSIX Threads - стандарт реализации потоков (нитей) выполнения.
• Windows API - многопоточные приложения для C++.
• PVM (Parallel Virtual Machine) позволяет объединить разнородный (но связанный сетью) набор компьютеров в общий вычислительный ресурс.
• MPI (Message Passing Interface) - стандарт систем передачи сообщений между параллельно исполняемыми процессами.

См. также

Напишите отзыв о статье "Параллельные вычисления"

Литература

• Словарь по кибернетике / Под редакцией академика В. С. Михалевича . - 2-е. - Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. - 751 с. - (С48). - 50 000 экз. - ISBN 5-88500-008-5 .
• . - IBM RedBook, 1999. - 238 с. (англ.)
• Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. - СПб: БХВ-Петербург, 2002. - 608 с. - ISBN 5-94157-160-7 .
• Оленев Н. Н. . - М .: ВЦ РАН, 2005. - 80 с. - ISBN 5201098320 .

Примечания

Ссылки

• (англ.)
• (англ.)

Отрывок, характеризующий Параллельные вычисления

Так называемая партизанская война началась со вступления неприятеля в Смоленск.
Прежде чем партизанская война была официально принята нашим правительством, уже тысячи людей неприятельской армии – отсталые мародеры, фуражиры – были истреблены казаками и мужиками, побивавшими этих людей так же бессознательно, как бессознательно собаки загрызают забеглую бешеную собаку. Денис Давыдов своим русским чутьем первый понял значение той страшной дубины, которая, не спрашивая правил военного искусства, уничтожала французов, и ему принадлежит слава первого шага для узаконения этого приема войны.
24 го августа был учрежден первый партизанский отряд Давыдова, и вслед за его отрядом стали учреждаться другие. Чем дальше подвигалась кампания, тем более увеличивалось число этих отрядов.
Партизаны уничтожали Великую армию по частям. Они подбирали те отпадавшие листья, которые сами собою сыпались с иссохшего дерева – французского войска, и иногда трясли это дерево. В октябре, в то время как французы бежали к Смоленску, этих партий различных величин и характеров были сотни. Были партии, перенимавшие все приемы армии, с пехотой, артиллерией, штабами, с удобствами жизни; были одни казачьи, кавалерийские; были мелкие, сборные, пешие и конные, были мужицкие и помещичьи, никому не известные. Был дьячок начальником партии, взявший в месяц несколько сот пленных. Была старостиха Василиса, побившая сотни французов.
Последние числа октября было время самого разгара партизанской войны. Тот первый период этой войны, во время которого партизаны, сами удивляясь своей дерзости, боялись всякую минуту быть пойманными и окруженными французами и, не расседлывая и почти не слезая с лошадей, прятались по лесам, ожидая всякую минуту погони, – уже прошел. Теперь уже война эта определилась, всем стало ясно, что можно было предпринять с французами и чего нельзя было предпринимать. Теперь уже только те начальники отрядов, которые с штабами, по правилам ходили вдали от французов, считали еще многое невозможным. Мелкие же партизаны, давно уже начавшие свое дело и близко высматривавшие французов, считали возможным то, о чем не смели и думать начальники больших отрядов. Казаки же и мужики, лазившие между французами, считали, что теперь уже все было возможно.
22 го октября Денисов, бывший одним из партизанов, находился с своей партией в самом разгаре партизанской страсти. С утра он с своей партией был на ходу. Он целый день по лесам, примыкавшим к большой дороге, следил за большим французским транспортом кавалерийских вещей и русских пленных, отделившимся от других войск и под сильным прикрытием, как это было известно от лазутчиков и пленных, направлявшимся к Смоленску. Про этот транспорт было известно не только Денисову и Долохову (тоже партизану с небольшой партией), ходившему близко от Денисова, но и начальникам больших отрядов с штабами: все знали про этот транспорт и, как говорил Денисов, точили на него зубы. Двое из этих больших отрядных начальников – один поляк, другой немец – почти в одно и то же время прислали Денисову приглашение присоединиться каждый к своему отряду, с тем чтобы напасть на транспорт.
– Нет, бг"ат, я сам с усам, – сказал Денисов, прочтя эти бумаги, и написал немцу, что, несмотря на душевное желание, которое он имел служить под начальством столь доблестного и знаменитого генерала, он должен лишить себя этого счастья, потому что уже поступил под начальство генерала поляка. Генералу же поляку он написал то же самое, уведомляя его, что он уже поступил под начальство немца.
Распорядившись таким образом, Денисов намеревался, без донесения о том высшим начальникам, вместе с Долоховым атаковать и взять этот транспорт своими небольшими силами. Транспорт шел 22 октября от деревни Микулиной к деревне Шамшевой. С левой стороны дороги от Микулина к Шамшеву шли большие леса, местами подходившие к самой дороге, местами отдалявшиеся от дороги на версту и больше. По этим то лесам целый день, то углубляясь в середину их, то выезжая на опушку, ехал с партией Денисов, не выпуская из виду двигавшихся французов. С утра, недалеко от Микулина, там, где лес близко подходил к дороге, казаки из партии Денисова захватили две ставшие в грязи французские фуры с кавалерийскими седлами и увезли их в лес. С тех пор и до самого вечера партия, не нападая, следила за движением французов. Надо было, не испугав их, дать спокойно дойти до Шамшева и тогда, соединившись с Долоховым, который должен был к вечеру приехать на совещание к караулке в лесу (в версте от Шамшева), на рассвете пасть с двух сторон как снег на голову и побить и забрать всех разом.
Позади, в двух верстах от Микулина, там, где лес подходил к самой дороге, было оставлено шесть казаков, которые должны были донести сейчас же, как только покажутся новые колонны французов.
Впереди Шамшева точно так же Долохов должен был исследовать дорогу, чтобы знать, на каком расстоянии есть еще другие французские войска. При транспорте предполагалось тысяча пятьсот человек. У Денисова было двести человек, у Долохова могло быть столько же. Но превосходство числа не останавливало Денисова. Одно только, что еще нужно было знать ему, это то, какие именно были эти войска; и для этой цели Денисову нужно было взять языка (то есть человека из неприятельской колонны). В утреннее нападение на фуры дело сделалось с такою поспешностью, что бывших при фурах французов всех перебили и захватили живым только мальчишку барабанщика, который был отсталый и ничего не мог сказать положительно о том, какие были войска в колонне.
Нападать другой раз Денисов считал опасным, чтобы не встревожить всю колонну, и потому он послал вперед в Шамшево бывшего при его партии мужика Тихона Щербатого – захватить, ежели можно, хоть одного из бывших там французских передовых квартиргеров.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

• Введение
• 1. Актуальность темы
• 2. Увеличение количества ядер
• 3. Технология NVIDIA CUDA
• 4. Разница между CPU и GPU
• Заключение
• Введение
• Распараллеливании вычислений - это разделение больших задач на более маленькие, которые могут выполняться одновременно. Обычно для параллельных вычислений требуются некоторые координированные действия. Параллельные вычисления бывают нескольких форм (на уровне инструкций, битов, данных, задач). Параллельные вычисления находили своё применение на протяжении многих лет в основном в высокопроизводительных вычислениях. Но ситуация в последнее время изменилась. Появился спрос на такие вычисление из-за физических ограничений роста тактовой частоты процессора. Параллельные вычисления стали доминирующей идеей в архитектуре компьютера. Она приобрела форму многоядерных процессоров.
• Использование параллельных вычислительных систем обусловлено стратегическим направлениям развития в компьютерной индустрии. Главным обстоятельством послужило не только ограничение возможностей быстродействия машин, основанных на последовательной логике, сколь и наличием задач, для которых наличие вычислительной техники не является ещё достаточным. К задачам данной категории можно отнести моделирование динамических процессов.
• Появление процессоров с несколькими ядрами явилось скачком развития эффективных супервычислений, которые могут похвастаться более высокими показателями производительность/стоимость, по сравнению с системами на базе супер ЭВМ. Использование многоядерных процессоров даёт гибкую возможность, в частности варьирования конфигураций, а также масштабирования мощности в вычислительных системах - начиная от PC, серверов, рабочих станций и заканчивая кластерными системами.
• 1. Актуальность темы
• В последние годы появилось большое количество дешевых кластерных параллельных вычислительных систем, которые привели к быстрому развитию параллельных вычислительных технологий, в том числе и в области высокопроизводительных вычислений. Большинство основных производителей микропроцессоров стали переходить на многоядерные архитектуры, что повлияло на изменение ситуации в области параллельных вычислительных технологий. Изменение аппаратной базы влечёт за собой изменение построений параллельных алгоритмов. Для реализации в многоядерных архитектурах вычислительных нужны новые параллельные алгоритмы, учитывающих новые технологии. Эффективность использования вычислительных ресурсов будет зависеть от качества собственно параллельных приложений и специализированных библиотек, ориентированных на многоядерные архитектуры.
• Применение высокопроизводительной техники в моделировании реальных технических, экономических, и других процессов, описываемых системами обыкновенных дифференциальных уравнений большой размерности, не только оправдано, но и необходимо. Распараллеливании вычислений в многопроцессорных и параллельных структурах является эффективным способов повышения производительности. Так что, применение параллельных вычислительных систем довольно важное направление развития вычислительной техники.

2. Увеличение количества ядер

Первым процессором для массового использования был POWER4 с двумя ядрами PowerPC на одном кристалле. Выпущен компанией IBM в 2001 году.

Производители процессоров Intel, AMD, IBM, ARM признали увеличение число ядер как одно из приоритетных направлений увеличения производительности.

В 2011 году выпустили в производство 8-ядерные процессоры для домашних PC, и 16-ядерные для серверных систем.

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

2-х ядерные процессоры существовали ранее, например IBM PowerPC-970MP (G5Н). Но такие процессоры применялись в узком круге специализированных задач.

В апреле 2005 года AMD представила 2-ядерный процессор Opteron. архитектура AMD64. предназначен для серверов. В мае 2005 года Intel представила процессор Pentium D. Архитектуры x86-64. Стал первым 2-х ядерным процессором для домашних PC.

В марте 2010 года AMD представила 12-ядерные серийные серверные процессоры Opteron 6100 (архитектура x86/x86-64).

В августе 2011 года AMD представила 16-ядерные серийные серверные процессоры Opteron серии 6200. Процессор Interlagos в одном корпусе содержит два 8-ядерных (4-модульных) чипа и является совместимым с платформой AMD Opteron серии 6100 (Socket G34).

3. Технология NVIDIA CUDA

Большое количество параллельных вычислений связано с трёхмерными играми. Параллельные векторные вычисления на универсальных устройствах с многоядерными процессорами используются в 3D-графике, достигая высокой пиковой производительности. Универсальным процессорам это не под силу. Максимальная скорость достигается только в ряде удобных задач, имея некоторые ограничения. Но всё равно такие устройства широко применяются в сферах, где изначально не предназначались. Например, процессор Cell, разработки альянса Sony-Toshiba-IBM в игровой приставке Sony PlayStation 3, или, современные видеокарты от компаний NVIDIA и AMD.

Ещё несколько лет назад начали появляться технологии неграфических расчётов общего назначения GPGPU для 3D видеоускорителей. Современные видеочипы имеют сотни математических исполнительных блоков, такая мощь может помочь для значительного ускорения множества вычислительно интенсивных приложений. Нынешние поколения GPU имеют гибкую архитектуру, которая вместе с программно-аппаратными архитектурами и высокоуровневыми языками даёт возможность делать их намного более доступными.

Появление достаточно быстрых и гибких шейдерных программ заинтересовало разработчиков создать GPGPU, которые способны выполнять современные видеочипы. Разработчики захотели на GPU рассчитывать не только изображения в игровых и 3D приложениях, но и применять в других областях параллельных вычислений. Для этого использовали API графических библиотек OpenGL и Direct3D. Данные в видеочип передавались в качестве текстур, расчётные программы помещались в виде шейдеров. Главным недостатком такого способа является значительная сложность программирования, низкий обмен данными между GPU и CPU, и некоторые другие ограничения.

Ведущие производители видеочипов NVIDIA и AMD представили платформы для параллельных вычислений - CUDA и CTM, соответственно. В видеокартах появилась аппаратная поддержка прямого доступа к вычислительным ресурсам. CUDA является расширением языка программирования С. CTM более похож на виртуальную машину, которая выполняет только ассемблерный код. Обе платформы убрали ограничениz предыдущих версий GPGPU, которые использовали традиционный графический конвейер, ну и конечно графические библиотеки Direct3D и Open GL.

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

Именно это постигнуло компанию NVIDIA выпустить платформу CUDA -- C-подобный язык программирования, наделённый своим компилятором, а также имеющий в наборе библиотеками для вычислений на GPU. Написание хорошего кода для видеочипов очень не простое занятие, но CUDA даёт больше контроля над аппаратными средствами видеокарты. CUDA появилась с видеокарт серии 8. Появилась CUDA версии 2.0, которая поддерживает расчёты с двойной точность в 32- и 64- битных ОС Windows, Linux, MacOS X.

4. Разница между CPU и GPU

Рост тактовой частоты закончилось из-за высокого энергопотребления. Увеличение производительности происходит за счёт увеличения кол-ва ядер на одном чипе. На данный момент для домашних пользователей продаются процессоры до восьми ядер, и количеством потоков до 16. В таких процессорах каждое ядро работает отдельно.

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

В чипах NVIDIA основной блок - это мультипроцессор с 8-10 ядрами и около сотней ALU с несколькими тысячами регистров и большой общей памятью. Видеокарта имеет глобальную память с доступом из всех мультипроцессоров, локальная память в каждом мультипроцессоре, а также имеется память для констант.

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

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

Политика разработчиков CPU: добиться выполнения большего числа инструкций параллельно, для увеличения производительности. Поэтому, начиная с процессоров Intel Pentium, появилась технология суперскалярного выполнения, которая представляет собой выполнение 2-х инструкций за такт, а процессор Pentium Pro отличился внеочередным выполнением инструкций.

У видеочипов работа более простая и распараллелена изначально. Чип принимает группу полигонов, все необходимые операции, и выдаёт пиксели. Обработка полигонов и пикселей независима независимо друг от друга. Поэтому в GPU такое большое кол-во процессоров. Также современные GPU способны выполнить больше одной инструкции за такт.

Другое отличие CPU от GPU: принцип доступа к памяти. В GPU Он связный и предсказуемы, т.к. если считались текстуры, значит через некоторое время придёт очередь соседних текстур. Поэтому организация памяти у видеокарты и центрального процессора разные. И видеочипу по этой причине не надо кэш-память большого размера, а для текстур требуются лишь около 128-256 кБ.

Работа с памятью также различная. CPU имеют встроенные контроллеры памяти, у GPU обычно их по несколько, вплоть до восьми 64-бит каналов. Кроме того применяется очень быстрая память, следовательно, пропускная способность памяти выше, что является плюсом для параллельных расчётов, оперирующие с огромными потоками данных.

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

Кэширование. CPU использует кэш для уменьшения задержек доступа к памяти, следствие чего, происходит увеличение производительности. GPU использует кэш для увеличения пропускной способности. CPU снижает задержки доступа к памяти за счёт большого кэша и предсказания ветвлений кода. Эти аппаратные части являются большими ни чипе, следовательно, они потребляют много энергии. GPU решают проблему задержки доступа к памяти другим способом: исполнение тысяч потоков одновременно. Когда один поток ожидает данные, другой поток выполняет вычисления без ожидания и задержек.

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

5. Первое применение расчётов на графических ускорителях

История применения чипов для математических расчётов началось давно. Самые первые попытки были примитивными и использовали некоторые функции из Z-буферизации и растеризации. Но с появлением шейдеров началось ускорение. В 2003г. на SIGGRAPH появилась новая секция под вычисления, и она получила GPGPU.

BrookGPU. Известный компилятор языка программирования Brook. Является потоковым. Был специально разработан для вычислений на GPU. Разработчики использовали API: Direct3D или OpenGL. Это существенной ограничивало применения GPU, т.к. шейдеры и текстуры применялись в 3D графике, а специалисты по параллельному программированию ничего знать не обязаны. Они используют тока потоки и ядра. Brook смог немного помочь в этой задачи. Расширения к языку С помогли скрыть от программистов трёхмерный API, и предоставить видеочип в качестве параллельного сопроцессора. Компилятор компилировал код и привязывал к библиотеке DirectX, OpenGL или x86.

6. Области применения параллельных расчётов на графических ускорителях

Приведём усреднённые цифры прироста производительности вычислений, полученные исследователями по всему миру. При переходе на GPU прирост производительности составляет в среднем в 5-30 раз, а в некоторых примерах доходит и до 100 раз (как правило это код, который непригоден для расчётов при помощи SEE.

Вот некоторые примеры ускорений:

· Флуоресцентная микроскопия - в 12 раз;

· Молекулярная динамика - в 8-16 раз;

· Электростатика (прямое и многоуровневое суммирование Кулона) - в 40-120 раз и 7 раз.

ядро процессор графический

Заключение

В реферате удалось рассмотреть параллельные вычисления на многоядерных процессорах, а также технологиях CUDA и CTM. Были рассмотрены разница между CPU и GPU, какие были сложности применения видеокарт в параллельных вычислениях без технологии CUDA, рассмотрены области применения.

В реферате не было рассмотрело применение параллельных вычислений в центральных процессорах с интегрированным видеоядром. Это процессоры фирмы AMD серии А (AMD A10, AMD A8, AMD A6, AMD A4) и процессоры фирмы Intel серии i3/i5/i7 со встроенным видеоядром HD Graphics.

Список использованной литературы

1. Сайт ixbt.com, владелец Byrds Research and Publishing, Ltd

2. Сайт wikipedia.org, владелец Фонд Викимедиа

3. Сайт nvidia.ru, владелец NVIDIA corporation

Размещено на Allbest.ru

Подобные документы

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

презентация , добавлен 10.02.2014


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

презентация , добавлен 22.02.2016


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

курсовая работа , добавлен 18.07.2012


Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.

курсовая работа , добавлен 15.12.2010


Развитие концепций и возможностей ОС. Параллельные компьютерные системы и особенности их ОС. Симметричные и асимметричные мультипроцессорные системы. Виды серверов в клиент-серверных системах. ОС для облачных вычислений. Кластерные вычислительные системы.

лекция , добавлен 24.01.2014


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

презентация , добавлен 10.02.2014


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

контрольная работа , добавлен 02.06.2014


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

курсовая работа , добавлен 21.06.2013


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

дипломная работа , добавлен 09.09.2010


Однопроцессорные вычислительные системы не справляются с решением военно-прикладных задач в реальном времени, поэтому для повышения производительности вычислительных систем военного назначения используются многопроцессорные вычислительные системы (МВС).

Плаксин М.А.

Национальный исследовательский университет Высшая школа экономики (Пермский филиал), г.Пермь, к.ф.м.н., доцент кафедры информационных технологи в бизнесе, mapl @ list. ru

«СУПЕРКОМПЬЮТЕРЫ» VS «ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ». «ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ» VS «СОВМЕСТНАЯ ДЕЯТЕЛЬНОСТЬ». КАК ИЗУЧАТЬ ТЕМУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ» В СРЕДНЕЙ ШКОЛЕ?

КЛЮЧЕВЫЕ СЛОВА

Информатика, параллельное программирование, параллельные вычисления, параллельные алгоритмы, суперкомпьютеры, начальная школа, средняя школа, ТРИЗформашка.

АННОТАЦИЯ

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

Современный этап развития computer science связан с массовым распространением параллелизма вычислений на всех уровнях (многомашинные кластеры, многопроцессорные ЭВМ, многоядерные процессоры).

Массовое распространение параллелизма влечет серьезные последствия, которые еще предстоит выявить и проанализировать. Начнем с перечисления некоторых теоретических проблем.

Современная теория алгоритмов создавалась в расчете на понятие последовательного алгоритма. Каким образом отразится на понятии алгоритма отказ от требования последовательности выполнения шагов?

По крайней мере последние 20 лет понятие «алгоритм» вводилось в школе в неразрывной связке с понятием «исполнитель». Для последовательного алгоритма это естественно. Как быть с алгоритмом параллельным? Его выполняет один исполнитель или группа исполнителей? Для конкретности в качестве примера рассмотрим компьютерную обучающую программу «Танковый экипаж» . В этой программе от учащегося требуется запрограммировать действия экипажа танка, состоящего из трех человек: наводчика, водителя и заряжающего. Каждый из них имеет свою систему команд. Для того, чтобы выполнить боевую задачу (поразить все цели), все члены экипажа должны действовать согласованно. Пример игрового поля программы «Танковый экипаж» см. на рис.1.

Вопрос: надо ли рассматривать этих трех действующих лиц как независимых исполнителей или как три составные части (устройства) одного сложного исполнителя? Для экипажа танка более естественным представляется второй вариант, поскольку ни один персонаж сам по себе выполнить задание не в состоянии. Но как быть, если игра будет усложнена, и боевая задача будет поставлена сразу для двух танков? Для трех танков? Трех членов одного экипажа вполне можно рассматривать как три части одного исполнителя. Но каждый экипаж очевидно является самостоятельным исполнителем. Значит, параллельный алгоритм для нескольких танков будет выполняться сразу группой исполнителей. Получается, что для параллельного алгоритма рассматривать надо обе возможности: выполнение параллельных действий одним исполнителем и группой исполнителей. В случае танкового экипажа границу провести просто. Исполнитель - это тот, кто в состоянии решить поставленную задачу. Этот исполнитель может состоять из нескольких компонент, каждая из которых выполняет некую часть задания, но не может самостоятельно без помощи других компонент выполнить задание целиком. Но всегда ли разделение «целых исполнителей» и частей сложного исполнителя будет также просто - сейчас сказать нельзя.

Файл 1*ра Окне О программе

Вьполиеть все

Bbno.n«fTb до выделенной строки

Вернуть в начальное попаже**»

быпопнлтъ пошагово (после выполнения «.ладом команды несйкоа^« будет наждтъ кнопки гВ ыголг«п-ъ следующий uwr")

Ё ЬГВД iTHWTt. спеауюшнй шаг

Осглноснть пошаговое

Рис.1. Фрагмент игрового поля программы «Танковый экипаж»

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

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

Ш. Алгоритм

н Наезд1«; Водитель Заряжающий

1 Пмер^ть орун* по «освой сгклл V Стоп V Зарядить 1

г Пци V Стоп V Зарядить 2

3 Опт! V Повернуться прет« часовой стрелки на 90 градусов V Зарядить 1 V

Л V В перш V Зарядить? V

5 Огонь! V Стоп V Зарядить 1

Í П^чм V Ст*п V Зарясь? V

7 Огонь! V Стоп V Зарядить 1 V

3 Па^ V Повернуться па часовой стрелке на 45 градусов V Зарядить 2 V

S Пауя V Вперйа V Пауза V

10 Пвдэа V Вперед V Пауза ¿d

11 Плрл V Вперед V Пауза V

12 Паум V Повернуться по часовой стрелке на 45 градусов V Пауза V

13 Падм V Вперед V Пауза V

14 V n&stpHyTbtft то чксевн стрелке на 45 градус« V Зар^а^ьТ V

Рис.2. Фрагмент программы для «Танкового экипажа» (пример линеек команд) Требует доработки традиционное понятие «системы команд исполнителя» (СКИ) и само понятие команды. Если мы считаем, что три члена танкового экипажа образуют единого исполнителя, то что считать СКИ этого исполнителя? И что считать командой? Или оставить понятие СКИ для каждого персонажа? То есть это уже не система команд ИСПОЛНИТЕЛЯ, а система команд одной из компонент исполнителя (для которой еще нет названия)?

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

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

Отдельный вопрос - методы распараллеливания уже существующих последовательных алгоритмов.

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

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

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

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

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

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

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

Исторически первая попытка включения тематики параллельных вычислений в школьный курс информатики была сделана еще двадцать лет назад. Двадцать лет назад в курсе под названием «Алгоритмика» был описан исполнитель «Директор строительства», который командовал параллельными действиями нескольких бригад, строящих сооружение из блоков прямоугольной и треугольной формы. Более того, для этого исполнителя была создана программная реализация. Увы! Эта замечательная методическая разработка в середине 90-х оказалась не востребована. Она почти на двадцать лет опередила свое время!

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

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

Организационную поддержку со стороны суперкомпьютерного сообщества. Каждое лето на факультете вычислительной математики и кибернетики МГУ проводится Летняя Суперкомпьютерная Академия . И каждое лето в рамках этой Академии организуется школьный трек для учителей информатики. Обучение проводится бесплатно. Иногородние слушатели обеспечиваются жильем на весьма льготных условиях. На конференции Russian Supercomputing Days в сентябре 2015 г. была организована школьная секция и мастер-класс для учителей информатики. Последовательная организационная работа привела к выявлению и формированию группы учителей, заинтересованных в продвижении данной тематики;

Наличие яркого харизматичного лидера, каковым является Владимир Валентинович Воеводин - доктор физико-математических наук, профессор, член-корреспондент РАН, заместитель директора Научно-исследовательского вычислительного центра Московского государственного университета;

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

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

Естественным расширением суперкомпьютерной тематики является изучение параллельного программирования. В настоящее время для выполнения параллельных программ совсем не обязательно иметь суперЭВМ. Достаточно многоядерного процессора или видеокарты с набором графических ускорителей. А это доступно уже почти всем. Из работ в этом направлении отметим кандидатскую диссертацию М.А. Соколовской по методике обучения будущих учителей информатики основам параллельного программирования и опыт Е.Ю. Киселевой по освоению школьниками технологии CUDA .

По мнению автора данной статьи сосредоточение внимания на спуерЭВМ и параллельном программировании существенно обедняет и усложняет тему параллельных вычислений, отвлекает учащихся от множества важных и доступных вопросов. Целью темы «параллельные

вычисления» в средней школе является не обучение «реальному» параллельному программированию (изучение соответствующих языковых конструкций, языков программирования и технологий), а ознакомление учащихся с соответствующим набором понятий и понимание особенностей параллельной работы. Мир вокруг и внутри нас представляет собой сложную параллельную систему. И эта система сама по себе дает массу материала для освоения понятий и механизмов параллелизма. Никакие сложные искусственные конструкции типа технологий MPI и OpenMP для этого не нужны. Школьная информатика должна воспитать мышление, настроенное на «параллельный лад». А дальше университет пусть закладывает в это мышление профессиональные знания, умения, навыки. В школе акцентировать имеет смысл не знакомство с суперкомпьютерами и изучение параллельного программирования, а освоение механизмов «совместной деятельности», постоянно и широко используемых в жизни. В курсе предлагается отразить следующие вопросы:

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

2) Виды параллелизма: параллелизм истинный и псевдопараллелизм (один процессор выполняет частями несколько программ).

3) Исполнители однотипные (землекопы) и разнотипные (экипаж танка).

4) Работы однотипные и разнотипные.

5) Соотношение «исполнители - работы»: 1 исполнитель - 1 работа, 1 исполнитель - N работ (псевдопараллельное выполнение или истинный параллелизм при наличии нескольких обрабатывающих устройств для разных работ), N исполнителей - 1 работа, N исполнителей - N работ.

6) Согласование деятельности исполнителей. Виды согласования: по частям работы, по времени, по результатам деятельности, по ресурсам.

7) Ресурсы. Ресурсы разделяемые и неразделяемые, расходуемые и повторно используемые. Утилизация потребленных ресурсов («сборка мусора» в широком смысле).

8) Выполнение одной и той же работы одним исполнителем и группой исполнителей. Зависимость скорости работы от количества исполнителей. Зависимость стоимости работы от количества исполнителей. Нелинейный рост скорости работы при росте количества исполнителей. Критический путь. Оптимальное количество исполнителей. Оптимальная загрузка исполнителей. Оптимальный порядок действий. Балансировка нагрузки.

9) Конкуренция исполнителей за ресурсы. Блокировка. Клинч (тупик).

10) Механизмы согласования действий исполнителей.

11) Псевдопараллельное выполнение процессов на компьютере (разделение между исполнителями-процессами одного ресурса - процессора).

12) Пригодность алгоритмов к распараллеливанию. Возможная степень распараллеливания. Существование алгоритмов, не поддающихся распараллеливанию.

Отметим, что приведенный список представляет собой частное мнение автора статьи и открыт для обсуждения, дополнения и корректировки. Более того, по мнению автора было бы очень полезно, чтобы «суперкомпьютерное сообщество» сформулировало «социальный заказ» для школы: какие именно знания-умения-навыки оно хочет видеть в выпускниках школы. Чем выпускник школы «суперкомпьютерного мира» должен отличаться от выпускника сегодняшнего? Будет заказ - будет и результат. Свежий пример. В первый день Russian Supercomputing Days-2015 в двух докладах прозвучала мысль, что быстродействие современных суперЭВМ определяется не мощностью процессоров (которая находится в центре внимания публики), а быстродействием оперативной памяти. Именно она становится бутылочным горлышком, пропускная способность которого определяет продуктивность всей системы. В результате на второй день конференции участники учительского мастер-класса обкатывали придуманную автором данной статьи игру, демонстрирующую взаимодействие центрального процессора, оперативной памяти и кэш-памяти. Порядок и форма изложения материала - вопрос открытый.

Материал должен быть продемонстрирован на примерах, не связанных с работой ЭВМ. Исполнители должны манипулировать материальными объектами.

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

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

Работу над подготовкой методики изучения параллельных вычислений автор данной статьи начал в 2013 г. в ходе подготовки конкурса «ТРИЗформашка-2013» и продолжил в последующие годы .

(«ТРИЗформашка» - межрегиональный Интернет-конкурс по информатике, системному анализу и ТРИЗ. Проводится ежегодно во второй половине марта. Возраст участников - с I класса до IV курса. География - от Владивостока до Риги. Среднее число участников - 100 команд (300 чел.), максимальное - 202 команды (более 600 чел.). Сайт конкурса www. trizformashka . ru.) Тогда, в 2013 г. цель работы была сформулирована следующим образом:

1. В течение двух-трех лет подготовить описание исполнителей, набор игр и задач, связанных с параллельными вычислениями;

2. Предложить их (по частям, ежегодно) участникам конкурса;

3. Проанализировать их реакцию (оценить количество решавших, их возраст, успешность решения, типичные ошибки, обнаруженные неточности в формулировке задач и т.д.). Конкурс «ТРИЗформашка» оказался удобным инструментом отладки задач, поскольку

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

За прошедшие годы был подготовлен следующий набор методических инструментов и площадок для их апробации.

1. Задания на параллелизм, начиная с 2013 г., вошли в конкурс «ТРИЗформашка» (начиная с 2013 г., конкурс имеет подзаголовок «Параллельные вычисления»). Список типов заданий приведен ниже;

2. Подготовлена глава про параллелизм для новой версии учебника информатики для 4 класса . Материал прошел апробацию в 3-х и 4-х классах Лицея №10 г.Перми;

3. Разработана и с 2014 г. используется в конкурсе «ТРИЗформашка» компьютерная игра «Танковый экипаж» ;

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

Согласование деятельности исполнителей. Различные виды согласования;

Выполнение одной и той же работы одним исполнителем и группой исполнителей. Зависимость скорости работы от количества исполнителей. Нелинейный рост скорости работы при росте количества исполнителей. Критический путь. Оптимальное количество исполнителей. Оптимальная загрузка исполнителей. Оптимальный порядок действий;

Ресурсы. Ресурсы разделяемые и неразделяемые;

Конкуренция исполнителей за ресурсы. Блокировка. Клинч (тупик). Были предложены и опробованы следующие типы задач :

1. Задачи на виды согласования. (Какие виды согласования существуют в школьной столовой?);

2. Игра «Танковый экипаж». Задание на построение параллельного алгоритма;

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

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

5. Сетевой график. Дан сетевой график. Требуется изобразить (схематически) сооружение, которое будет построено, определить, сколько дней потребуется для строительства при том или ином числе бригад, какая часть работы будет выполнена к определенному времени;

6. Ярусно-параллельные формы. Планирование работ по разным критериям. Дано задание на работу, производительность работников, правила оплаты. Требуется определить количество работников, нужных, чтобы выполнить работу в заданное время, определить срок работы при заданном количестве работников, определить количество работников, нужное для минимизации стоимости работ;

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

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

На сегодня имеем в наличии следующие результаты:

1. Сформулирован подход с изучению темы «параллельные вычисления»: идти не от проблем computer science, а «от жизни», делать акцент на «совместной деятельности»;

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

3. Сформулированы некоторые классы задач. На основании накопленного опыта можно оценить, какого рода задачи стоит придумывать;

4. Подготовлен набор задач названных классов. Задачи прошли апробацию в конкурсах «ТРИЗформашка» за 2013, 2014, 2015 гг. и/или в начальной школе (на занятиях с учениками третьих-четвертых классов лицея №10 г.Перми);

5. Подготовлен набор деловых игр. Игры прошли апробацию в начальной школе и на ряде мероприятий для учителей. В частности, были представлены на школьном треке Летней Суперкомпьютерной Академии ВМК МГУ в 2014 г., на мастер-классе для учителей на Russian Supercomputing Days-2015, на нескольких других конференциях (в том числе, на конференции ИТ-0бразование-2015 ассоциации АПКИТ) и других мероприятиях для учителей информатики;

6. Подготовлен набор текстов про параллелизм для учебника IV класса. Тексты прошли апробацию в лицее №10 г.Перми;

7. Подготовлена компьютерная игра «Танковый экипаж». Игра прошла апробацию в конкурсах «ТРИЗформашка» 2014 и 2015;

8. Конкурс «ТРИЗформашка» оправдал себя в качестве апробационной площадки;

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

10. Есть потребность, желание и возможность продолжать работу.

Литература

1. Алгоритмика: 5-7 классы: Учебник и задачник для общеобразоват. учебных заведений /А.К. Звонкин, А.Г. Кулаков, С.К. Ландо, А.Л. Семенов, А.Х. Шень. - М.: Дрофа, 1996.

2. Босова Л.Л. Параллельные алгоритмы в начальной и основной школе. //Информатика в школе. 2015, №2. С.24-27.

3. Воеводин В.В. Вычислительная математика и структура алгоритмов: 10 лекция о том, поему трудно решать задачи на вычислительных системах параллельной архитектуры и что надо знать дополнительно. чтобы успешно преодолевать эти трудности: учебник. М.: Изд-во МГУ 2010.

4. Гаврилова И.В. Первое путешествие в «параллельный мир». //Информатика в школе. 2015, №6. С.16-19.

5. Дитер М.Л., Плаксин М.А. Параллельные вычисления в школьной информатике. Игра «Стройка». //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. - Пермь, 2014. - С.258-261.

6. Иванова Н.Г., Плаксин М.А., Русакова О.Л. ТРИЗформашка. //Информатика. N05 Проверено 10.10.2015.

14. Плаксин М.А. Информатика: учебник для 4 класса: в 2 ч. /М.А.Плаксин, Н.Г.Иванова, О.Л.Русакова. - М.: БИНОМ. Лаборатория знаний, 2012.

15. Плаксин М.А. О методике начального знакомства с параллельными вычислениями в средней школе. //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. - Пермь, 2014. - С.256-258.

16. Плаксин М.А. Комплекс деловых игр для знакомства с параллельными вычислениями в начальной школе. //Преподавание информационных технологий в Российской Федерации: материалы Тринадцатой открытой Всероссийской конференции «ИТ-0бразование-2015» (г.Пермь, 14-15 мая 2015 г.). Пермский государственный национальный исследовательский университет, - Пермь, 2015. С.60-62.

17. Плаксин М.А., Иванова Н.Г., Русакова О.Л. Набор заданий для знакомства с параллельными вычислениями в конкурсе «ТРИЗформашка». //Преподавание информационных технологий в Российской Федерации: материалы Тринадцатой открытой Всероссийской конференции «ИТ-Образование-2015» (г.Пермь, 14-15 мая 2015 г.). Пермский государственный национальный исследовательский университет, - Пермь, 2015. С. 232-234.

18. Соколовская М.А. Методическая система обучения основам параллельного программирования будущих учителей информатики.: автореф. дис. ... канд. пед. наук, Красноярск, 2012.

Транскрипт

1 Часть 3. Методы параллельных вычислений 6. Принципы разработки параллельных методов 6. Принципы разработки параллельных методов Моделирование параллельных программ Этапы разработки параллельных алгоритмов Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование набора подзадач Распределение подзадач между процессорами Параллельное решение гравитационной задачи N тел Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислений Краткий обзор раздела Обзор литературы Контрольные вопросы Задачи и упражнения Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную проблему. Для снижения сложности рассматриваемой темы оставим в стороне математические аспекты разработки и доказательства сходимости алгоритмов эти вопросы в той или иной степени изучаются в ряде "классических" математических учебных курсов. Здесь же мы будем полагать, что вычислительные схемы решения задач, рассматриваемых далее в качестве примеров, уже известны 1). С учетом высказанных предположений последующие действия для определения эффективных способов организации параллельных вычислений могут состоять в следующем: Выполнить анализ имеющихся вычислительных схем и осуществить их разделение (декомпозицию) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга, Выделить для сформированного набора подзадач информационные взаимодействия, которые должны осуществляться в ходе решения исходной поставленной задачи, Определить необходимую (или доступную) для решения задачи вычислительную систему и выполнить распределение имеющего набора подзадач между процессорами системы. При самом общем рассмотрении понятно, что объем вычислений для каждого используемого процессора должен быть примерно одинаков это позволит обеспечить равномерную вычислительную загрузку (балансировку) процессоров. Кроме того, также понятно, что распределение подзадач между процессорами должно быть выполнено таким образом, чтобы наличие информационных связей (коммуникационных взаимодействий) между подзадачами было минимальным. 1) Несмотря на то, что для многих научно-технических задач на самом деле известны не только последовательные, но и параллельные методы решения, данное предположение является, конечно, очень сильным, поскольку для новых возникающих задач, требующих для своего решения большого объема вычислений, процесс разработки алгоритмов составляет существенную часть всех выполняемых работ.

2 Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование подзадач Распределение подзадач между процессорами Рис Общая схема разработки параллельных алгоритмов После выполнения всех перечисленных этапов проектирования можно оценить эффективность разрабатываемых параллельных методов для этого обычно определяются значения показателей качества порождаемых параллельных вычислений (ускорение, эффективность, масштабируемость). По результатам проведенного анализа может оказаться необходимым повторение отдельных (в предельном случае всех) этапов разработки следует отметить, что возврат к предшествующим шагам разработки может происходить на любой стадии проектирования параллельных вычислительных схем. В этом отношении часто выполняемым дополнительным действием в приведенной выше схеме проектирования является корректировка состава сформированного множества задач после определения имеющегося количества процессоров подзадачи могу быть укрупнены (агрегированы) при наличии малого числа процессоров или, наоборот, детализированы в противном случае. В целом, данные действия могут быть определены как масштабирование разрабатываемого алгоритма и выделены в качестве отдельного этапа проектирования параллельных вычислений. Для применения получаемого в конечном итоге параллельного метода необходимо выполнить разработку программ для решения сформированного набора подзадач и разместить разработанные программы по процессорам в соответствии с выбранной схемой распределения подзадач. Для проведения вычислений программы запускаются на выполнение (программы на стадии выполнения обычно именуются процессами), для реализации информационных взаимодействий программы должны иметь в своем распоряжении средства обмена данными (каналы передачи сообщений). Следует отметить, что каждый процессор обычно выделяется для решения одной единственной подзадачи, однако при наличии большого количества подзадач или использовании ограниченного числа процессоров это правило может не соблюдаться и, в результате, на процессорах может выполняться одновременно несколько программ (процессов). В частности, при разработке и начальной проверке параллельной программы для выполнения всех процессов может использоваться один процессор (при расположении на одном процессоре процессы выполняются в режиме распределения времени). Рассмотрев внимательно разработанную схему проектирования и реализации параллельных вычислений, можно отметить, что данный подход в значительной степени ориентирован на вычислительные системы с распределенной памятью, когда необходимые информационные взаимодействия реализуются при помощи передачи сообщений по каналам связи между процессорами. Тем не менее, данная схема может быть использована без потери какой-либо эффективности параллельных вычислений и для разработки параллельных методов для систем с общей памятью в этом случае механизмы передачи сообщений для обеспечения информационных взаимодействий должны быть заменены операциями доступа к общим (разделяемым) переменным Моделирование параллельных программ Рассмотренная схема проектирования и реализации параллельных вычислений дает способ понимания параллельных алгоритмов и программ. На стадии проектирования параллельный метод может быть представлен в виде графа "подзадачи сообщения", который представляет собой не что иное, как укрупненное (агрегированное) представление графа информационных зависимостей (графа "операции-операнды" см. раздел 2). Аналогично на стадии выполнения для описания параллельной программы может быть использована модель в виде графа "процессы каналы", в которой вместо подзадач используется понятие процессов, а информационные зависимости заменяются каналами 2

3 передачи сообщений. В дополнение, на этой модели может быть показано распределение процессов по процессорам вычислительной системы, если количество подзадач превышает число процессоров см. рис процесс - канал - операции приема (передачи) - входные (выходные) каналы для взаимодействия процессов Рис Модель параллельной программы в виде графа "процессы-каналы" Использование двух моделей параллельных вычислений 2) позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов. Первая модель граф "подзадачи - сообщения" позволяет сосредоточиться на вопросах выделения подзадач одинаковой вычислительной сложности, обеспечивая при этом низкий уровень информационной зависимости между подзадачами. Вторая модель граф "процессы каналы" концентрирует внимание на вопросах распределения подзадач по процессорам, обеспечивая еще одну возможность снижения трудоемкости информационных взаимодействий между подзадачами за счет размещения на одних и тех же процессорах интенсивно взаимодействующих процессов. Кроме того, эта модель позволяет лучше анализировать эффективность разработанного параллельного метода и обеспечивает возможность более адекватного описания процесса выполнения параллельных вычислений. Дадим дополнительные пояснения для используемых понятий в модели "процессы-каналы": Под процессом в рамках данного учебного материала будем понимать выполняемую на процессоре программу, которая использует для свой работы часть локальной памяти процессора и которая содержит ряд операций приема/передачи данных для организации информационного взаимодействия между выполняемыми процессами параллельной программы, Канал передачи данных с логической точки зрения может рассматриваться как очередь сообщений, в которую один или несколько процессов могут отправлять пересылаемые данные и из которой процесс-адресат может извлекать сообщения, отправляемые другими процессами. В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема/передачи с каналом. По степени общности, канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами-источниками сообщений. Следует отметить важное достоинство рассмотренной модели "процессы-каналы" в этой модели проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и 2) В Foster (1995) рассматривается только одна модель модель "задача-канал" для описания параллельных вычислений, которая занимает некоторое промежуточное положение по сравнению с изложенными здесь моделями. Так, в модели "задачаканал" не учитывается возможность использования одного процессора для решения нескольких подзадач одновременно. 3

4 действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ Этапы разработки параллельных алгоритмов Рассмотрим более подробно изложенную выше методику разработки параллельных алгоритмов. В значительной степени данная методика опирается на подход, впервые рассмотренный в Foster (1995), и, как отмечалось ранее, включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы (см. рис. 6.1). Для демонстрации приводимых рекомендаций далее будет использоваться учебная задача поиска максимального значения среди элементов матрицы A (такая задача возникает, например, при численном решении систем линейных уравнений для определения ведущего элемента метода Гаусса): y = max a. 1 i, j N i j Такая задача носит полностью иллюстративный характер, и после рассмотрения этапов разработки в оставшейся части раздела будет приведен более полный пример использования данной методики для разработки параллельных алгоритмов. Кроме того, данная схема разработки будет применена и при изложении всех далее рассматриваемых методов параллельных вычислений Разделение вычислений на независимые части Выбор способа разделения вычислений на независимые части основывается на анализе вычислительной схемы решения исходной задачи. Требования, которым должен удовлетворять выбираемый подход, обычно состоят в обеспечении равного объема вычислений в выделяемых подзадачах и минимума информационных зависимостей между этими подзадачами (при прочих равных условиях нужно отдавать предпочтение редким операциям передачи большего размера сообщений по сравнению с частыми пересылками данных небольшого объема). В общем случае, проведение анализа и выделение задач представляет собой достаточно сложную проблему ситуацию помогает разрешить существование двух часто встречающихся типов вычислительных схем: а) б) Рис Разделение данных для матрицы A: а) ленточная схема, б) блочная схема Для большого класса задач вычисления сводятся к выполнению однотипной обработки элемент элементов большого набора данных к такому виду задач относятся, например, матричные вычисления, численные методы решения уравнений в частных производных и др. В этом случае говорят, что существует параллелизм по данным, и выделение подзадач сводится к разделению имеющихся данных. Так, например, для нашей учебной задачи поиска максимального значения при формировании подзадач исходная матрица A может быть разделена на отдельные строки (или последовательные группы строк) ленточная схема разделения данных (см. рис. 6.3) или на прямоугольные наборы элементов блочная схема разделения данных. Для большого количества решаемых задач разделение вычислений по данным приводит к порождению одно-, двух- и трех- мерных наборов подзадач, для которых информационные связи существуют только между ближайшими соседями (такие схемы обычно именуются сетками или решетками), 4

5 Рис Регулярные одно-, двух- и трех- мерные структуры базовых подзадач после декомпозиции данных Для другой части задач вычисления могут состоять в выполнении разных операций над одним и тем же набором данных в этом случае говорят о существовании функционального параллелизма (в качестве примеров можно привести задачи обработки последовательности запросов к информационным базам данных, вычисления с одновременным применением разных алгоритмов расчета и т.п.). Очень часто функциональная декомпозиция может быть использована для организации конвейерной обработки данных (так, например, при выполнении каких-либо преобразований данных вычисления могут быть сведены к функциональной последовательности ввода, обработки и сохранения данных). Важный вопрос при выделении подзадач состоит в выборе нужного уровня декомпозиции вычислений. Формирование максимально возможного количества подзадач обеспечивает использование предельно достижимого уровня параллелизма решаемой задачи, однако затрудняет анализ параллельных вычислений. Использование при декомпозиции вычислений только достаточно "крупных" подзадач приводит к ясной схеме параллельных вычислений, однако может затруднить эффективное использование достаточно большого количества процессоров. Возможное разумное сочетание этих двух подходов может состоять в использовании в качестве конструктивных элементов декомпозиции только тех подзадач, для которых методы параллельных вычислений являются известными. Так, например, при анализе задачи матричного умножения в качестве подзадач можно использовать методы скалярного произведения векторов или алгоритмы матрично-векторного произведения. Подобный промежуточный способ декомпозиции вычислений позволит обеспечить и простоту представления вычислительных схем, и эффективность параллельных расчетов. Выбираемые подзадачи при таком подходе будем именовать далее базовыми, которые могут быть элементарными (неделимыми), если не допускают дальнейшего разделения, или составными в противном случае. Для рассматриваемой учебной задачи достаточный уровень декомпозиции может состоять, например, в разделении матрицы A на множество отдельных строк и получении на этой основе набора подзадач поиска максимальных значений в отдельных строках; порождаемая при этом структура информационных связей соответствует линейному графу см. рис Для оценки корректности этапа разделения вычислений на независимые части можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти? Возможна ли при выбранном способе декомпозиции равномерная загрузка всех имеющихся процессоров? Достаточно ли выделенных частей процесса вычислений для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества)? Выделение информационных зависимостей При наличии вычислительной схемы решения задачи после выделения базовых подзадач определение информационных зависимостей между подзадачами обычно не вызывает больших затруднений. При этом, однако, следует отметить, что на самом деле этапы выделения подзадач и информационных зависимостей достаточно сложно поддаются разделению. Выделение подзадач должно происходить с учетом возникающих информационных связей; после анализа объема и частоты необходимых информационных обменов между подзадачами может потребоваться повторение этапа разделения вычислений. При проведении анализа информационных зависимостей между подзадачами следует различать (предпочтительные формы информационного взаимодействия выделены подчеркиванием): Локальные и глобальные схемы передачи данных для локальных схем передачи данных в каждый момент времени выполняются только между небольшим числом подзадач (располагаемых, как 5

6 правило, на соседних процессорах), для глобальных операций передачи данных в процессе коммуникации принимают участие все подзадачи, Структурные и произвольные способы взаимодействия для структурных способов организация взаимодействий приводит к формированию некоторых стандартных схем коммуникации (например, в виде кольца, прямоугольной решетки и т.д.), для произвольных структур взаимодействия схема выполняемых операций передач данных не носит характер однородности, Статические или динамические схемы передачи данных для статических схем моменты и участники информационного взаимодействия фиксируются на этапах проектирования и разработки параллельных программ, для динамического варианта взаимодействия структура операции передачи данных определяется в ходе выполняемых вычислений, Синхронные и асинхронные способы взаимодействия для синхронных способов операции передачи данных выполняются только при готовности всех участников взаимодействия и завершаются только после полного окончания всех коммуникационных действий, при асинхронном выполнении операций участники взаимодействия могут не дожидаться полного завершения действий по передаче данных. Для представленных способов взаимодействия достаточно сложно выделить предпочтительные формы организации передачи данных: синхронный вариант, как правило, более прост для использования, в то время как асинхронный способ часто позволяет существенно снизить временные задержки, вызванные операциями информационного взаимодействия. Как уже отмечалось в предыдущем пункте, для учебной задачи поиска максимального значения при использовании в качестве базовых элементов подзадач поиска максимальных значений в отдельных строках исходной матрицы A структура информационных связей имеет вид, представленный на рис Рис Структура информационных связей учебной задачи Как и ранее, для оценки правильности этапа выделения информационных зависимостей можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий? Является ли одинаковой интенсивность информационных взаимодействий для разных подзадач? Является ли схема информационного взаимодействия локальной? Не препятствует ли выявленная информационная зависимость параллельному решению подзадач? Масштабирование набора подзадач Масштабирование разработанной вычислительной схемы параллельных вычислений проводится в случае, если количество имеющихся подзадач отличается от числа планируемых к использованию процессоров. Для сокращения количества подзадач необходимо выполнить укрупнение (агрегацию) вычислений. Применяемые здесь правила совпадают с рекомендациями начального этапа выделения подзадач определяемые подзадачи, как и ранее, должны иметь одинаковую вычислительную сложность, а объем и интенсивность информационных взаимодействий между подзадачами должны оставаться на минимально-возможном уровне. Как результат, первыми претендентами на объединение являются подзадачи с высокой степенью информационной взаимозависимости. При недостаточном количестве имеющегося набора подзадач для загрузки всех доступных к использованию процессоров необходимо выполнить детализацию (декомпозицию) вычислений. Как 6

7 правило, проведение подобной декомпозиции не вызывает каких-либо затруднений, если для базовых задач методы параллельных вычислений являются известными. Выполнение этапа масштабирования вычислений должно свестись, в конечном итоге, к разработке правил агрегации и декомпозиции подзадач, которые должны параметрически зависеть от числа процессоров, применяемых для вычислений. Для рассматриваемой учебной задачи поиска максимального значения агрегация вычислений может состоять в объединении отдельных строк в группы (ленточная схема разделения матрицы см. рис. 6.3а), при декомпозиции подзадач строки исходной матрицы A могут разбиваться на несколько частей (блоков). Список контрольных вопросов, предложенный в Foster (1995) для оценки правильности этапа масштабирования, выглядит следующим образом: Не ухудшится ли локальность вычислений после масштабирования имеющегося набора подзадач? Имеют ли подзадачи после масштабирования одинаковую вычислительную и коммуникационную сложность? Соответствует ли количество задач числу имеющихся процессоров? Зависят ли параметрически правила масштабирования от количества процессоров? Распределение подзадач между процессорами Распределение подзадач между процессорами является завершающим этапом разработки параллельного метода. Надо отметить, что управление распределением нагрузки для процессоров возможно только для вычислительных систем с распределенной памятью, для мультипроцессоров (систем с общей памятью) распределение нагрузки обычно выполняется операционной системой автоматически. Кроме того, данный этап распределения подзадач между процессорами является избыточным, если количество подзадач совпадает с числом имеющихся процессоров, а топология сети передачи данных вычислительной системы представляет собой полный граф (т.е., все процессоры связаны между собой прямыми линиями связи). Основной показатель успешности выполнения данного этапа эффективность использования процессоров, определяемая как относительная доля времени, в течение которого процессоры использовались для вычислений, связанных с решением исходной задачи. Пути достижения хороших результатов в этом направлении остаются прежними как и ранее, необходимо обеспечить равномерное распределение вычислительной нагрузки между процессорами и минимизировать количество сообщений, передаваемых между процессорами. Точно так же, как и на предшествующих этапах проектирования, оптимальное решение проблемы распределения подзадач между процессорами основывается на анализе информационной связности графа "подзадачи - сообщения". Так, в частности, подзадачи, между которыми имеются информационные взаимодействия, целесообразно размещать на процессорах, между которыми существуют прямые линии передачи данных. Следует отметить, что требование минимизации информационных обменов между процессорами может противоречить условию равномерной загрузки процессов. Так, мы можем разместить все подзадачи на одном процессоре и полностью устранить межпроцессорную передачу сообщений, однако, понятно, загрузка большинства процессоров в этом случае будет минимальной. Для нашей учебной задачи поиска максимального значения распределение подзадач между процессорами не вызывает каких-либо затруднений достаточно лишь обеспечить размещение подзадач, между которыми имеются информационные связи, на процессорах, для которых существуют прямые каналы передачи данных. Поскольку структура информационной связей учебной задачи имеет вид линейного графа, выполнение данного требования может быть обеспечено практически при любой топологии сети вычислительной системы. Решение вопросов балансировки вычислительной нагрузки значительно усложняется, если схема вычислений может изменяться в ходе решения задачи. Причиной этого могут быть, например, неоднородные сетки при решении уравнений в частных производных, разреженность матриц и т.п. 3). Кроме того, используемые на этапах проектирования оценки вычислительной сложности решения подзадач могут иметь приближенный характер и, наконец, количество подзадач может изменяться в ходе вычислений. В таких ситуациях может потребоваться перераспределение базовых подзадач между 3) Можно отметить, что даже для нашей простой учебной задачи может наблюдаться различная вычислительная сложность сформированных базовых задач. Так, например, количество операций при поиске максимального значения для строки, в которой максимальное значение имеет первый элемент, и строки, в которой значения являются упорядоченными по возрастанию, будет различаться в два раза. 7

8 процессорами уже непосредственно в процессе выполнения параллельной программы (или, как обычно говорят, придется выполнить динамическую балансировку вычислительной нагрузки). Данные вопросы являются одними из наиболее сложных (и наиболее интересных) в области параллельных вычислений к сожалению, рассмотрение данных вопросов выходит за рамки данного учебного материала (дополнительная информация может быть получена, например, в Buyya (1999) и Wilkinson and Allen (1999)). В качестве примера дадим краткую характеристику широко используемого способа динамического управления распределением вычислительной нагрузки, обычно именуемого схемой "менеджер - исполнитель" (manager-worker scheme). При использовании данного подхода предполагается, что подзадачи могут возникать и завершаться в ходе вычислений, при этом информационные взаимодействия между подзадачами либо полностью отсутствует, либо минимальны. В соответствии с рассматриваемой схемой для управления распределением нагрузки в системе выделяется отдельный процессор-менеджер, которому доступна информация обо всех имеющихся подзадачах. Остальные процессоры системы являются исполнителями, которые для получения вычислительной нагрузки обращаются к процессору-менеджеру. Порождаемые в ходе вычислений новые подзадачи передаются обратно процессору-менеджеру и могут быть получены для решения при последующих обращениях процессоров-исполнителей. Завершение вычислений происходит в момент, когда процессорыисполнители завершили решение всех переданных им подзадач, а процессор-менеджер не имеет какихлибо вычислительных работ для выполнения. Предложенный в Foster (1995) перечень контрольных вопросов для проверки этапа распределения подзадач состоит в следующем: Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных затрат? Существует ли необходимость динамической балансировки вычислений? Не является ли процессор-менеджер "узким" местом при использовании схемы "менеджерисполнитель"? 6.3. Параллельное решение гравитационной задачи N тел Многие вычислительные задачи в области физики сводятся к операциям обработки данных для каждой пары объектов имеющейся физической системы. Такой задачей является, в частности, проблема, широко известная в литературе как гравитационная задача N тел (или просто задача N тел) см., например, Andrews (2000) В самом общем виде, задача может быть описана следующим образом. Пусть дано большое количество тел (планет, звезд и т.д.), для каждого из которых известна масса, начальное положение и скорость. Под действием гравитации положение тел меняется, и требуемое решение задачи состоит в моделировании динамики изменения системы N тел на протяжении некоторого задаваемого интервала времени. Для проведения такого моделирования заданный интервал времени обычно разбивается на временные отрезки небольшой длительности и далее на каждом шаге моделирования вычисляются силы, действующие на каждое тело, а затем обновляются скорости и положения тел. Очевидный алгоритм решения задачи N тел состоит в рассмотрении на каждом шаге моделирования всех пар объектов физической системы и выполнении для каждой получаемой пары всех необходимых расчетов. Как результат, при таком подходе время выполнения одной итерации моделирования будет составлять 4) T = τ N(N 1) / 2, 1 где τ есть время перевычисления параметров одной пары тел. Как следует из приведенного описания, вычислительная схема рассмотренного алгоритма является сравнительно простой, что позволяет использовать задачу N тел в качестве еще одной наглядной демонстрации применения методики разработки параллельных алгоритмов. 4) Следует отметить, что для решения задачи N тел существует и более эффективные последовательные алгоритмы, однако их изучение может потребовать достаточно больших усилий. С учетом данного обстоятельства для дальнейшего рассмотрения выбирается именно данный "очевидный" (но не самый быстрый) метод, хотя, в общем случае, безусловно, для распараллеливания следует выбирать наилучшие схемы выполнения расчетов. 8

9 Разделение вычислений на независимые части Выбор способа разделения вычислений не вызывает каких-либо затруднений - очевидный подход состоит в выборе в качестве базовой подзадачи всего набора вычислений, связанных с обработкой данных одного какого-либо тела физической системы Выделение информационных зависимостей Выполнение вычислений, связанных с каждой подзадачей, становится возможным только в случае, когда в подзадачах имеются данные (положение и скорости передвижения) обо всех телах имеющейся физической системы. Как результат, перед началом каждой итерации моделирования каждая подзадача должна получить все необходимые сведения от всех других подзадач системы. Такая процедура передачи данных, как отмечалось в разделе 3, именуется операцией сбора данных (single-node gather). В рассматриваемом алгоритме данная операция должна быть выполнена для каждой подзадачи такой вариант передачи данных обычно именуется как операция обобщенного сбора данных (multi-node gather or all gather). Определение требований к необходимым результатам информационного обмена не приводит к однозначному установлению нужного информационного обмена между подзадачами достижение требуемых результатов может быть обеспечено при помощи разных алгоритмов выполнения операции обобщенного сбора данных. Наиболее простой способ выполнения необходимого информационного обмена состоит в реализации последовательности шагов, на каждом из которых все имеющиеся подзадачи разбиваются попарно и обмен данными осуществляется между подзадачами образовавшихся пар. При надлежащей организации попарного разделения подзадач (N-1)-кратное повторение описанных действий приведет к полной реализации требуемой операции сбора данных. Рассмотренный выше метод организации информационного обмена является достаточно трудоемким для сбора всех необходимых данных требуется (N-1) итераций, на каждой из которых выполняется одновременно (N/2) операций передачи данных. Для сокращения требуемого количества итераций можно обратить внимание на факт, что после выполнения первого шага операции сбора данных подзадачи будут уже содержать не только свои данные, но и данные подзадач, с которыми они образовывали пары. Как результат, на второй итерации сбора данных можно будет образовывать пары подзадач для обмена данными сразу о двух телах физической системы тем самым, после завершения второй итерации каждая подзадача будет содержать сведения о четырех телах системы и т.д. Как можно заметить, данный способ реализации обменов позволяет завершить необходимую процедуру за log 2 N итераций. Следует отметить, что при этом объем пересылаемых данных в каждой операции обмена удваивается от итерации к итерации на первой итерации между подзадачами пересылаются данные об одном теле системы, на второй итерации о двух телах и т.д. Использование рассмотренного способа реализации операции обобщенного сбора данных приводит к определению структуры информационных связей между подзадачами в виде N-мерного гиперкуба Масштабирование и распределение подзадач по процессорам Как правило, число тел физической системы N значительно превышает количество процессоров p. Как результат, рассмотренные ранее подзадачи следует укрупнить, объединив в рамках одной подзадачи вычисления для группы (N/p) тел. После проведения подобной агрегации число подзадач и количество процессоров будет совпадать, и при распределении подзадач между процессорами останется лишь обеспечить наличие прямых коммуникационных линий между процессорами с подзадачами, между которыми имеются информационные обмены при выполнении операции сбора данных Анализ эффективности параллельных вычислений Оценим эффективность разработанных способов параллельных вычислений для решения задачи N тел. Поскольку предложенные варианты отличаются только методами выполнения информационных обменов, для сравнения подходов достаточно определить длительность операции обобщенного сбора данных. Используем для оценки времени передачи сообщений модель, предложенную Хокни (см. раздел 3), тогда длительность выполнения операции сбора данных для первого варианта параллельных вычислений может быть выражена как 1 T p (comm) = (p 1)(α + m (N / p) / β), где α, β есть параметры модели Хокни (латентность и пропускная способность сети передачи данных), а m задает объем пересылаемых данных для одного тела физической системы. 9

10 Для второго способа информационного обмена, как уже отмечалось ранее, объем пересылаемых данных на разных итерациях операции сбора данных различается. На первой итерации объем пересылаемых сообщений составляет (mn/p), на второй итерации этот объем увеличивается вдвое и оказывается равным 2(mN/p) и т.д. В общем случае, для итерации с номером i объем сообщений оценивается как 2 i-1 (mn/p). Как результат, длительность выполнения операции сбора данных в этом случае может быть определена при помощи следующего выражения T 2 p log p i= 1 i 1 (comm) = (α + 2 m(N / p) / β) = α log p + m (N / p)(p 1) / β. Сравнение полученных выражений показывает, что второй разработанный способ параллельных вычислений имеет существенно более высокую эффективность, несет меньшие коммуникационные затраты и допускает лучшую масштабируемость при увеличении количества используемых процессоров Краткий обзор раздела В разделе была рассмотрена методика разработки параллельных алгоритмов, предложенная в Foster (1995). Данная методика включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы. При применении методики предполагается, что вычислительная схема решения рассматриваемой задачи уже является известной. Основные требования, которые должны быть обеспечены при разработке параллельных алгоритмов, состоят в обеспечении равномерной загрузки процессоров при низком информационном взаимодействии сформированного множества подзадач. Для описания получаемых в ходе разработки вычислительных параллельных схем рассмотрены две модели. Первая из них модель "подзадачи-сообщения" может быть использована на стадии проектирования параллельных алгоритмов, вторая модель "процессы-каналы" может быть применена на стадии реализации методов в виде параллельных программ. В завершение раздела показывается применение рассмотренной методики разработки параллельных алгоритмов на примере решения гравитационной задачи N тел Обзор литературы Рассмотренная в разделе методика разработки параллельных алгоритмов впервые была предложена в Foster (1995). В этой работе изложение методики проводится более детально; кроме того, в работе содержится несколько примеров использования методики для разработки параллельных методов для решения ряда вычислительных задач. Полезной при рассмотрении вопросов проектирования и разработки параллельных алгоритмов может оказаться также работа Quinn (2004). Гравитационная задача N тел более подробно рассматривается в Andrews (2000) Контрольные вопросы 1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов? 2. Каковы основные этапы проектирования и разработки методов параллельных вычислений? 3. Как определяется модель "подзадачи-сообщения"? 4. Как определяется модель "процессы-каналы"? 5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов? 6. В чем состоят основные действия на этапе выделения подзадач? 7. Каковы основные действия на этапе определения информационных зависимостей? 8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач? 9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы? 10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"? 11. Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел? 10

11 12. Какой способ выполнения операции обобщенного сбора данных является более эффективным? 6.7. Задачи и упражнения 1. Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см. раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI. 2. Выполните реализацию рассмотренных способов выполнения обобщенной операции сбора данных и сравните время их выполнения. Сопоставьте получаемые временные характеристики с имеющими теоретическими оценками. Выполните сравнение со временем выполнения функции MPI_Allgather библиотеки MPI. 3. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов: для задачи поиска максимального значения среди минимальных элементов строк матрицы (такая задача имеет место для решения матричных игр) y = max min a, 1 i N 1 j N ij (обратите особое внимание на ситуацию, когда число процессоров превышает порядок матрицы, т.е. p>n), для задачи вычисления определенного интеграла с использованием метода прямоугольников b N 1 y = f (x) dx h fi, a i= 0 f i = f (x), x = i h, h = (b a) / N. i i (описание методов интегрирования дано, например, в Kahaner, Moler and Nash (1988)) 4. Выполните реализацию разработанных параллельных методов для задач п Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов. Литература Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming.. Reading, MA: Addison-Wesley (русский перевод Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом "Вильямс", 2003) Bertsekas, D.P., Tsitsiklis, J.N. (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (русский перевод Каханер Д., Моулер Л., Нэш С. Численные методы и программное обеспечение. М.: Мир, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11

ГЛАВА 3 ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ МЕТОДОВ Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную

Методы и алгоритмы параллельных вычислений Проектирование параллельных алгоритмов Кулаков Кирилл Александрович 2016 Петрозаводск Цели проектирования Балансировка нагрузки Масштабируемость Эффективность

Высокопроизводительные вычисления Лекция 2. Оценка максимально возможного параллелизма Обеспечение наилучших наилучшего ускорения S T = эффективности E = 1 возможно не для всех вычислительно T трудоемких

Лекции Лекция 1. Принципы построения параллельных вычислительных систем.............................. 23 Лекция 2. Моделирование и анализ параллельных вычислений...... 49 Лекция 3. Оценка коммуникационной

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 9. Параллельные

Проект комиссии Президента по модернизации и технологическому развитию экономики России «Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного

Тема: Распараллеливание выражений на примере арифметических Основные характеристики сложности и параллельности Что подлежит распараллеливанию? Задача (декомпозиция на подзадачи меньшей размерности) 2Метод

ВОПРОСЫ К ТЕСТУ ПО КУРСУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ» 1. Принципы построения параллельных вычислительных систем (15) 1. Схемы многопроцессорных систем с однородным и неоднородным доступом. 2.

Проектирование параллельных алгоритмов Лекция 3.1 29.03.2012 Т.Ю.Лымарь 1 3.1 Методология проектирования Разделение Установление связей Агрегирование Привязка к конкретной ЭВМ 29.03.2012 Т.Ю.Лымарь 2 3.1.1

Московский государственный университет им. М.В. Ломоносова История и методология параллельного программирования 9. Проектирование параллельных алгоритмов Разработчики: Л.Б. Соколинский, д.ф.-м.н., профессор

Федеральное агентство по образованию Нижегородский государственный университет им. Н.И. Лобачевского Национальный проект «Образование» Инновационная образовательная программа ННГУ. Образовательно-научный

Нижегородский государственный университет им. Н.И.Лобачевского Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ Лаборатория «Информационные технологии» ItLab Практический

Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Лекция. Моделирование параллельных вычислений Гергель В.П., декан ВМК ННГУ Суперкомпьютерные

Алгоритмы для параллельных вычислительных систем 1. Типы параллелизма и методы синтеза параллельных алгоритмов. 2. Оценка эффективности параллельных алгоритмов. 1. Типы параллелизма и методы синтеза параллельных

СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения

Оценка эффективности параллельных алгоритмов Лекция 4. 29.03.2012 Т.Ю. Лымарь 1 Введение Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

Оценка эффективности параллельных алгоритмов Лекция 7 Т.Ю. Лымарь Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма: Оценка максимально возможного

ОСНОВНЫЕ ПОНЯТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Параллельные вычисления (параллельная обработка) это использование нескольких или многих вычислительных устройств для одновременного выполнения разных частей одной

Математические модели и методы эффективного использования распределенных Цифровая вычислительных 3D-медицина систем Заголовок Результаты Подзаголовок в области компьютерной презентации графики и геометрического

УДК 681.5 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ СОДУ Назарова И.А. Донецкий национальный технический университет Запропоновано паралельні чисельні алгоритми однокрокових методів для

ГЛАВА МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ При разработке параллельных алгоритмов решения сложных научнотехнических задач принципиальным моментом является анализ эффективности использования параллелизма,

1. Цели и задачи дисциплины: Суперкомпьютерные технологии и высокопроизводительные вычисления с использованием многопроцессорных вычислительных систем (МВС) становятся важным фактором научно-технического

Построение статистических моделей эффективности параллельных программ В.Н.Белецкий, С.А.Резникова, А.А.Чемерис Институт проблем моделирования в энергетике им. Г.Е.Пухова НАН Украины В статье рассмотрен

Информатика, управление, экономика ТРУДЫ МФТИ 2 Том 2, (5) УДК 59687+475 АС Хританков Московский физико-технический институт (государственный университет) Математическая модель характеристик производительности

АЛГОРИТМЫ БАЛАНСИРОВКИ ЗАГРУЗКИ ПРОЦЕССОРОВ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Бельков Д.В. Донецкий национальный технический университет, г. Донецк кафедра вычислительной математики и программирования

Вычислительные машины и программное обеспечение УДК 681.3.06 П.А. Павлов ЭФФЕКТИВНОСТЬ РАСПРЕДЁЛЕННЫХ ВЫЧИСЛЕНИЙ В МАСШТАБИРУЕМЫХ СИСТЕМАХ Масштабируемость (scalability) является одним из важнейших требований

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

ДИАГОНАЛЬНЫЙ МЕТОД УМНОЖЕНИЯ ПЛОТНЫХ МАТРИЦ Князькова Т.В., к.т.н., доцент, ВятГУ, г. Киров Сегодня с ростом мощностей вычислительных систем и современных суперкомпьютеров в широком спектре отраслей экономики

Введение 1 Глава 1 Задания 1.1 Разминка Первое задание на написание программы, использующей библиотеку MPI, одно на всех. 1.1.1 Вычисление числа π Вычислить число π по следующей формуле: 1 1 dx 4 1 + x

Лабораторная работа 4 Параллельная реализация метода Якоби в трехмерной области Цель работы: практическое освоение методов распараллеливания численных алгоритмов на регулярных сетках на примере реализации

Р. И. Идрисов ВРЕМЕННАЯ РАЗВЁРТКА ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ IR2 ЯЗЫКА SISAL 3.1 * На сегодняшний день увеличение вычислительных мощностей связано уже не с ускорением отдельного, а с добавлением дополнительных

Стратегия оптимизационного исследования и методы решения задач статической и динамической оптимизации технологических объектов Задачи статической оптимизации технологических объектов традиционно формулируются

ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ (Получение параллельных последовательностей зернистых вычислений) Приведем примеры получения параллельных алгоритмов, множества операций которых

ПАРАЛЛЕЛЬНЫЕ СВОЙСТВА АЛГОРИТМА Параллельные компьютеры (суперкомпьютеры) предназначены для быстрого решения больших задач. Чем мощнее компьютер, тем потенциально быстрее можно решить на нем задачу. Помимо

Каляев А.В. ПРОГРАММИРОВАНИЕ ВИРТУАЛЬНЫХ АРХИТЕКТУР И ОРГАНИЗАЦИЯ СТРУКТУРНО- ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ 1 Аннотация НИИ многопроцессорных вычислительных

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

Распределение памяти Распределение памяти - это процесс, в результате которого отдельным элементам исходной программы ставятся в соответствие адрес, размер и атрибуты области памяти, необходимой для размещения

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ вида Численное решение нелинейных алгебраических или трансцендентных уравнений. заключается в нахождении значений

«Алгебра и геометрия» 13. Системы линейных алгебраических уравнений (СЛАУ). Теорема Кронекера-Капелли. Общее и частное решения СЛАУ. 14. Кривые второго порядка: эллипс, гипербола, парабола, и их свойства.

УДК 681.32 ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ КЛАСТЕРОВ РАБОЧИХ СТАНЦИЙ С ИСПОЛЬЗОВАНИЕМ ВЕЕРНОГО РАСПРЕДЕЛЕНИЯ ДОПОЛНИТЕЛЬНЫХ ЗАДАНИЙ НА ПРОСТАИВАЮЩЕЕ ОБОРУДОВАНИЕ 2012 В. М. Довгаль 1, С. Г. Спирин 2 1 профессор

Граф алгоритма и параллельные вычисления. Внутренний параллелизм программ. Лекция 3 12.04.2012 (С) Л.Б.Соколинский 1 3.1 Внутренний параллелизм Программа содержит параллелизм, если некоторые ее части (операторы)

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА

Лекция 5 5 Теорема существования и единственности решения задачи Коши для нормальной системы ОДУ Постановка задачи Задача Коши для нормальной системы ОДУ x = f (, x), () состоит в отыскании решения x =

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 2. Моделирование

Глава 5. МЕТОДЫ НЕЯВНОГО ПЕРЕБОРА Рассмотрим общую постановку задачи дискретной оптимизации mi f (x), (5.) x D в которой -мерный искомый вектор x принадлежит конечному множеству допустимых решений D.

ОГЛАВЛЕНИЕ Введение.... 12 Ч а с т ь I. Основы распараллеливания Лекция 1. О постановке задачи распараллеливания... 17 1.1. Введение.... 17 1.2. О некоторых вычислительных задачах.... 19 1.3. Численный

УДК 68.3.06 ОПРЕДЕЛЕНИЕ ЧИСЛА И ТОПОЛОГИИ РАЗМЕЩЕНИЯ СТАНЦИЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ А.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected] Рассмотрены задачи

ЭКСТРАПОЛЯЦИОННЫЕ БЛОЧНЫЕ ОДНОШАГОВЫЕ МЕТОДЫ ЧИСЛЕННОГО ВЫСОКОТОЧНОГО РЕШЕНИЯ ЗАДАЧИ КОШИ Кулаков В.В. Назарова И. А.Фельдман Л.П. Донецкий национальный технический университет Рассматриваются параллельные

Труды ИСА РАН, 2008. Т. 32 О понятии производительности в распределенных вычислительных системах М. А. Посыпкин, А. С. Хританков Институт системного анализа Российской академии наук (ИСА РАН) В данной

2007 НАУЧНЫЙ ВЕСТНИК МГТУ ГА 26 серия Радиофизика и радиотехника УДК 6236:6239 ОЦЕНКА ЦЕЛЕСООБРАЗНОСТИ РАСПАРАЛЛЕЛИВАНИЯ ИНФОРМАЦИОННО-ЗАВИСИМЫХ ЗАДАЧ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РН АКИНШИН Статья представлена

Максимальное распараллеливание алгоритмов на основе концепции Q-детерминанта Валентина Николаевна Алеева Южно-Уральский государственный университет (НИУ) Новосибирcк, 2015 ВВЕДЕНИЕ В докладе рассматривается

Министерство образования и науки Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского В.П. Гергель ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОПРОЦЕССОР- НЫХ МНОГОЯДЕРНЫХ

ЛК 1. Моделирование. 1. Основные понятия. 2 Принципы моделирования. 3 Свойства моделей 4 Классификация методов моделирования. 5. Математическое моделирование 1. ОСНОВНЫЕ ПОНЯТИЯ. Моделирование замещение

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Новосибирский государственный университет» (НГУ) Факультет информационных технологий

Нижегородский государственный университет им. Н.И. Лобачевского Научно исследовательский университет Создание учебной библиотеки параллельных методов Parlib Выполнили: Козинов Е.А. Кутлаев М.В. Осокин

УДК 681.3.06 ПРОЕКТИРОВАНИЕ СТРУКТУРЫ ЛОКАЛЬНОЙ СЕТИ ДЛЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ А.В. Погребной, Д.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected]

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ЦИКЛИЧЕСКОЙ ПРОГОНКИ Головашкин Д.Л., Филатов М. В. Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет Аннотация Работа посвящена

УДК 519.856; 519.854; 519.85 СТАТИСТИЧЕСКИЙ ПОИСК СТРУКТУР ИНФОРМАЦИОННО- ВЫЧИСЛИТЕЛЬНОЙ СЕТИ В.В. Малыгин Исследованы свойства сходимости функции оценки структуры информационно вычислительной сети. На

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

12.1. Ввод-вывод по опросу готовности устройства Готовность или неготовность внешнего устройства к вводу-выводу проверяется в регистре состояния внешнего устройства Для программно-управляемого ввода/вывода

ТАКСОНОМИЯ ФЛИННА Кириллова Юлия 6057/2 22.11.11 Таксономия Флинна общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. предложена в 1972 г. Майклом Флинном.

Лабораторная работа 4 Решение задачи Пуассона методом Якоби в трехмерной области Цель - практическое освоение методов распараллеливание алгоритмов задач, решаемых сеточными методами на примере решения