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

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Шахтинский институт (филиал) ЮРГТУ (НПИ)

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ»

Шахты- 2010

Введение

Основные понятия

1. Общие вопросы решения ";больших задач";

1.1 Современные задачи науки и техники, требующие для решения суперкомпьютеры

1.2.2 Абстрактные модели параллельных вычислений

1.2.3 Способы параллельной обработки данных, погрешность вычислений

1.3 Понятие параллельного процесса и гранулы распараллеливания

1.4 Взаимодействие параллельных процессов, синхронизация процессов

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

2.3 Классификация параллельных вычислительных систем

2.4 Многопроцессорные вычислительные системы c распределенной памятью

2.4.1 Массивно-параллельные суперкомпьютеры серии Cry T3

2.4.2 Кластерные системы класса BEOWULF

Заключение

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

Введение

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

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

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

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

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительностью посредством сети Internet. На сегодняшний день применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Развитие ";железа"; с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент – технологий параллельного программирования.

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

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

Рассмотрим два основных вопроса:

1. Многопроцессорные вычислительные системы – (массивно-параллельные суперкомпьютеры) Cray T3D(E) с количеством процессоров от 40 до 2176. Это суперкомпьютеры с распределенной памятью на RISC-процессорах типа Alpha21164A, с топологией коммуникационной сети – трехмерный тор, операционной системой UNIX с микроядром и трансляторами для языков FORTRAN, HPF, C/C++. Поддерживаемые модели программирования: MPI, PVM, HPF.

2. Беовульф-кластеры рабочих станций. Кластеры рабочих станций – совокупность рабочих станций, соединенных в локальную сеть. Кластер – вычислительная система с распределенной памятью и распределенным управлением. Кластерная система может обладать производительностью, сравнимой с производительностью суперкомпьютеров. Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster – по одноименному проекту), связанны локальной сетью Ethernet и используют операционную систему Linux.

Основные понятия

Наиболее распространенной технологией программирования для кластерных систем и параллельных компьютеров с распределенной памятью в настоящее время является технология MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии – Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. MPI поддерживает работу с языками Фортран и Си. Полная версия интерфейса содержит описание более 125 процедур и функций.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты, гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с так называемыми ";нитями";.

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

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

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

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Фортран тип integer (в языке Си – предопределенный тип MPI Comm).

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

Процессоры с сокращенным набором команд (RISC). В основе RISC-архитектуры (RISC – Reduced Instruction Set Computer) процессора лежит идея увеличения скорости его работы за счет упрощения набора команд.

Исследования показали, что 33% команд типичной программы составляют пересылки данных, 20% – условные ветвления и еще 16% – арифметические и логические операции. В подавляющем большинстве команд вычисление адреса может быть выполнено быстро, за один цикл. Более сложные режимы адресации используются примерно в 18% случаев. Около 75% операндов являются скалярными, то есть переменными целого, вещественного, символьного типа и т. д., а остальные являются массивами и структурами. 80% скалярных переменных – локальные, а 90% структурных являются глобальными. Таким образом, большинство операндов – это локальные операнды скалярных типов. Они могут храниться в регистрах.

Согласно статистике, большая часть времени тратится на обработку операторов ";вызов подпрограммы"; и ";возврат из подпрограммы";. При компиляции эти операторы порождают длинные последовательности машинных команд с большим числом обращений к памяти, поэтому даже если доля этих операторов составляет всего 15%, они потребляют основную часть процессорного времени. Только около 1% подпрограмм имеют более шести параметров, а около 7% подпрограмм содержат более шести локальных переменных.

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

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

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

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

1. Общие вопросы решения ";больших задач";

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

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

1.1. Современные задачи науки и техники, требующие

для решения суперкомпьютеры

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

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

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

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

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

Науки о материалах

Построение полупроводниковых приборов

Сверхпроводимость

Разработка фармацевтических препаратов

Генетика человека

Астрономия

Транспортные задачи большой размерности

Гидро и газодинамика

Управляемый термоядерный синтез

Разведка нефти и газа

Вычислительные задачи наук о мировом океане

Распознавание и синтез речи, распознавание изображений

Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6×106 (сетка с шагом 10 по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6×107 числами. При шаге дискретизации по времени 10 минут за моделируемый промежуток времени необходимо определить 5×104 ансамблей (то есть 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102÷103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016÷1017.

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

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

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

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

Недостатком метода оценки пиковой производительности как числа выполняемых компьютером команд в единицу времени (MIPS, Million Instruction Per Second) дает только самое общее представление о быстродействии, так как не учитывает специфику конкретных программ (трудно предсказуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа).

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

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

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

При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10).

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

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

Контраргумент. Аналогичное развитие свойственно и параллельным системам.

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

Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные ";устоявшиеся"; способы обеспечения параллелизма. Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). PVM и MPI используются в суперкомпьютерах Cray-T3.

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

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

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

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

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

1.2 Параллельная обработка данных

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

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

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

Плаксин М.А.

Национальный исследовательский университет Высшая школа экономики (Пермский филиал), г.Пермь, к.ф.м.н., доцент кафедры информационных технологи в бизнесе, 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.

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

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

Размещено на 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


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

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

Введение

Близился закат эры 32-битных камней, и было очевидно, что надо повышать не только мощность, но и разрядность. Разработчики процессоров столкнулись с рядом проблем в увеличении тактовой частоты: невозможно рассеивать выделяемую кристаллом теплоту, нельзя дальше уменьшать размер транзисторов, однако главной проблемой стало то, что при увеличении тактовой частоты быстродействие программ не повышалось. Причиной этому явилась параллельная работа современных компьютерных систем, а один процессор, каким бы мощным бы он ни был, в каждый момент времени может выполнять только одну задачу. Для примера, у меня в системе Windows 7 в момент написания статьи выполняется 119 процессов. Хотя они далеко не все находятся в бэкграунде, им не всем нужна высокая мощность. На одном камне выполнение нескольких процессов/потоков может быть только конкурентным. То есть их работа чередуется: после того как определенный поток отработает свой квант времени, в течение которого он выполнил полезную нагрузку, его текущее состояние сохранится в памяти, а он будет выгружен из процессора и заменен следующим находящимся в очереди на выполнение потоком - произойдет переключение контекста, на что тратится драгоценное время. А пока идет обмен данными между процессором и оперативной памятью, из-за ограниченной пропускной способности системной шины микропроцессор нервно курит бамбук, в сторонке ожидая данные. На помощь могут прийти аппаратный и программный (например, из операционной системы) планировщики, чтобы подгружать данные в кеш. Однако кеш очень ограничен по объему, поэтому такое решение не может служить панацеей. Выходом стала параллельная обработка, при которой в реальном времени одновременно выполняются несколько процессов. А чтобы ее реализовать, потребовалось фундаментально перепроектировать и перестроить камень - совместить в одном корпусе два исполняющих кристалла и более.

Планирование

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

Аппаратные решения

Прежде чем перейти к многоядерности, разработчики процессоров выяснили, что при выполнении одного потока процессорное ядро загружается не полностью (думаю, для этого не надо быть провидцем). И поскольку для выполнения второго программного потока используются не все ресурсы микропроцессора (так как аппаратное состояние - исполнительные устройства, кеш - может храниться в одном экземпляре), то в дублировании нуждается только область состояния программной архитектуры (логика прерываний). Эта технология получила название гиперпоточности (Hyper-Threading). Гиперпоточность - аппаратный механизм, в котором несколько независимых аппаратных потоков выполняются в одном такте на единственном суперскалярном процессорном ядре. С ее помощью один физический процессор представляется как два логических, то есть так его видит операционная система, потому что планирование и выполнение, по сути, осуществляется с расчетом на два ядра. Это происходит благодаря непрерывному потоку команд, выполняющихся на совместном оборудовании. Эта технология была добавлена к архитектуре NetBurst, реализованной в процессорах Pentium 4. Поэтому гиперпоточность была реализована еще в последних версиях Pentium 4, но мне в то время как-то не удалось ее застать. Зато сейчас я могу наблюдать ее в процессоре Atom, установленном в нетбуке. В этом камне, помимо гиперпоточности, реализована многоядерность (в количестве двух штук), поэтому в операционной системе я наблюдаю четыре камня. Но, например, в Core 2 Duo гиперпоточность отсутствует, равно как и в Core i5. С помощью гиперпоточности скорость исполнения оптимизированных для многопоточности программ удалось повысить на 30%. Подчеркну, что прирост производительности будет иметь место только в специально подготовленных приложениях.

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

Затем были изобретены многоядерные процессоры, которые ныне используются повсеместно. Многоядерные процессоры поддерживают мультипроцессорную обработку на кристалле. В этой архитектуре два ядра или более реализуются в одном процессоре, устанавливаемом в один сокет. В зависимости от конструкции эти ядра могут совместно использовать большой кеш на том же кристалле. Многоядерные процессоры также требуют совместимого чипсета. Так как каждое ядро представляет собой самостоятельный исполняющий модуль, то многоядерные процессоры обеспечивают истинный параллелизм - выполнение каждого потока в обособленной среде. В случае присутствия нескольких исполняющих ядер должен быть способ обмена информацией между ними, без чего попросту невозможно создать параллельную систему, причем нужен специальный ресурс. Для этого был изобретен усовершенствованный программируемый контроллер прерываний (APIC). Он выполняет обмен информации между процессорами/ядрами, используя механизм межпроцессорного прерывания (Interprocessor Interrupt). Последний, в свою очередь, используется операционной системой для планирования/выполнения потоков.

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

Программные решения

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

• пользовательского уровня - создается в пользовательской программе (на уровне пользователя). Эти потоки в Windows NT проецируются на потоки уровня ядра, так их видит процессор;
• поток ядра - управляется ядром операционной системы;
• аппаратный поток - единица, исполняемая на процессоре.

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

Примитивы параллельного кодинга

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

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

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

Для обмена информацией между процессами/потоками используются сообщения, подразделяемые на три группы: внутрипроцессные (для передачи информации между потоками одного процесса), межпроцессные (для передачи инфы между процессами - с зависимостью от потоков) и процесс - процесс (поточно независимая передача инфы между процессами).
В то же время при использовании блокировок для избегания гонок могут наступить мертвые (dead lock) и живые (live lock) блокировки. Мертвая блокировка имеет место, когда один поток заблокирован на ожидании определенного ресурса от другого потока, но тот не может дать его (например, ожидает результат от первого). Мертвая блокировка может произойти при выполнении четырех хорошо определенных условий (мы не будем разбирать эти условия в данной статье). Поэтому при написании многопоточного кода у программиста есть возможность избежать дидлока, но на практике это выглядит гораздо сложнее. Живая блокировка хуже мертвой тем, что в первом случае потоки заблокированы, а во втором они постоянно конфликтуют.

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

Win32 threads

После появления первой версии Windows NT многопоточное программирование в ней улучшалось от версии к версии, одновременно улучшался связанный с потоками API. Итак, когда стартует процесс посредством функции CreateProcess, он имеет один поток для выполнения команд. Поток состоит из двух объектов: объект ядра (через него система управляет потоком) и стек, в котором хранятся параметры, функции и переменные потока. Чтобы создать дополнительный поток, надо вызвать функцию CreateThread. В результате создается объект ядра - компактная структура данных, используемая системой для управления потоком. Этот объект, по сути, не является потоком. Также из адресного пространства родительского процесса для потока выделяется память. И поскольку все потоки одного процесса будут выполняться в его адресном пространстве, то они будут разделять его глобальные данные. Вернемся к функции CreateThread и рассмотрим ее параметры. Первый параметр - указатель на структуру PSECURITYATTRIBUTES, которая определяет атрибуты защиты и свойства наследования, для установки значений по умолчанию достаточно передать NULL. Второй параметр типа DW0RD определяет, какую часть адресного пространства поток может использовать под свой стек. Третий параметр PTHREAD START_ROUTIME pfnStartAddr - указатель на функцию, которую необходимо привязать к потоку и которую он будет выполнять. Эта функция должна иметь вид DWORD WINAPI ThreadFunc(PVOID pvParam), она может выполнять любые операции; когда она завершится, то возвратит управление, а счетчик пользователей объекта ядра потока будет уменьшен на 1, в случае, когда этот счетчик будет равен 0, данный объект будет уничтожен. Четвертый параметр функции CreateThread - указатель на структуру PVOID, содержащую параметр для инициализации выполняемой в потоке функции (см. описание третьего параметра). Пятый параметр (DWORD) определяет флаг, указывающий на активность потока после его создания. Последний, шестой параметр (PDWORD) - адрес переменной, куда будет помещен идентификатор потока, если передать NULL, тем самым мы сообщим, что он нам не нужен. В случае успеха функция возвращает дескриптор потока, с его помощью можно манипулировать потоком; при фейле функция возвращает 0.

Существуют четыре пути завершения потока, три из которых нежелательные: это завершение потока через вызов функции ExitThread, через вызов TerminateThread, при завершении родительского процесса без предварительного завершения потока. Лишь 1 путь – самозавершение потока, которое происходит при выполнении назначенных ему действий, является благоприятным. Потому что только в этом случае гарантируется освобождение всех ресурсов операционной системы, уничтожение всех объектов C/C++ с помощью их деструкторов.

Еще пара слов о создании потока. Функция CreateThread находится в Win32 API, при этом в библиотеке Visual C++ имеется ее эквивалент _beginthreadex, у которой почти тот же список параметров. Рекомендуется создавать потоки именно с ее помощью, поскольку она не только использует CreateThread, но и выполняет дополнительные операции. Кроме того, если поток был создан с помощью последней, то при уничтожении вызывается _endthreadex, которая очищает блок данных, занимаемый структурой, описывающей поток.

Потоки планируются на выполнение с учетом приоритета. Если бы все потоки имели равные приоритеты, то для выполнения каждого (в WinNT) выделялось бы по 20 мс. Но это не так. В WinNT имеется 31 (от нуля) поточный приоритет. При этом 31 - самый высокий, на нем могут выполняться только самые критичные приложения - драйверы устройств; 0, самый низкий, зарезервирован для выполнения потока обнуления страниц. Тем не менее разработчик не может явно указать номер приоритета для выполнения своего потока. Зато в Windows есть таблица приоритетов, где указаны символьные обозначения сгруппированных номеров приоритетов. При этом конечный номер формируется не только на основе этой таблицы, но и на значениях приоритета родительского процесса. Значения скрыты за символьными константами по той причине, что Microsoft оставляет за собой право их изменить и пользуется им от версии к версии своей операционки. При создании поток получает обычный (normal) уровень приоритета. Его можно изменить функцией SetThreadPriority, принимающей два параметра: HANDLE hThread - дескриптор изменяемого потока, int nPriority - уровень приоритета (из таблицы). С помощью функции GetThreadPriority можно получить текущий приоритет, передав в нее дескриптор нужного потока. Перед изменением приоритета потока его надо приостановить, это делается функцией SuspendThread. После изменения приоритета поток надо снова отдать планировщику для планирования выполнения функцией ResumeThread. Обе функции получают дескриптор потока, с которым работают. Все описанные операции кроме приостановки и возобновления применимы и к процессам. Они не могут быть приостановлены/возобновлены, поскольку не затрачивают процессорное время, поэтому не планируются.

Избегание гонок в Win32

В многопоточных приложениях надо везде по возможности использовать атомарные - неделимые операции, в выполнение которых не может встрять другой поток. Такие функции в Win32 API имеют префикс Interlocked, например, для инкремента переменной вместо i++ использовать InterlockedExchangeAdd(&i, 1). Помимо операций увеличения/уменьшения, еще есть операции для атомарного сравнения, но мы их оставим в качестве твоего домашнего задания.

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

CRITICAL_SECTION g_cs; DWORD WINAPI ThreadRun(PVOID pvParam) { EnterCriticalSection(&g_cs); // Что-то вычисляем LeaveCriticalSection(&g_cs); return 0; }

Критические секции в Win32 не просто код, который может выполняться несколькими потоками, это целый механизм синхронизации данных. Критические секции должны быть как можно меньше, то есть включать как можно меньше вычислений.
Чтобы позволить читать значение переменной нескольким потокам, а изменять одному, можно применить структуру «тонкой блокировки» SRWLock. Первым делом надо инициализировать структуру вызовом InitializeSRWLock с передачей указателя на нее. Затем во время записи ограничиваем ресурс эксклюзивным доступом:

AcquireSRWLockExclusive(PSRWLOCK SRWLock); // Записываем значение ReleaseSRWLockExclusive(PSRWLOCK SRWLock);

С другой стороны, во время чтения осуществляем расшаренный доступ:

AcquireSRWLockShared(PSRWLOCK SRWLock); // Читаем значение ReleaseSRWLockShared(PSRWLOCK SRWLock);

Обрати внимание: все функции принимают проинициализированную структуру SRWLock в качестве параметра.
С помощью условных переменных удобно организовать зависимость «поставщик - потребитель» (см. декомпозицию по информационным потокам), то есть следующее событие должно произойти в зависимости от предыдущего. В этом механизме используются функции SleepConditionVariableCS и SleepConditionVariableSRW, служащие для блокировки критической секции или структуры «тонкой блокировки». Они принимают три и четыре параметра соответственно: указатель на условную переменную, ожидаемую потоком, указатель на критическую секцию либо SRWLock, применимую для синхронизации доступа. Следующий параметр - время (в миллисекундах) для ожидания потоком выполнения условия, если условие не будет выполнено, функция вернет False; последний параметр второй функции - вид блокировки. Чтобы пробудить заблокированные потоки, надо из другого потока вызвать функцию WakeConditionVariable или WakeAllConditionVariable. Если выполненная в результате вызова этих функций проверка подтвердит выполнение условия, передаваемого в качестве параметра данным функциям, поток будет пробужден.

В приведенном описании мы познакомились с общими определениями механизмов семафор и мьютекс. Сейчас посмотрим, как они реализованы в Win32. Создать семафор можно с помощью функции CreateSemaphore. Ей передаются такие параметры: указатель на структуру PSECURITY_ATTRIBUTES, содержащую параметры безопасности; максимальное число ресурсов, обрабатываемых приложением; количество этих ресурсов, доступных изначально; указатель на строку, определяющую имя семафора. Когда ожидающий семафора поток хочет получить доступ к ресурсу, охраняемому семафором, то wait-функция потока опрашивает состояние семафора. Если его значение больше 0, значит, семафор свободен и его значение уменьшается на 1, а поток планируется на выполнение. Если же при опросе семафор занят, его значение равно 0, тогда вызывающий поток переходит в состояние ожидания. В момент, когда поток покидает семафор, вызывается функция ReleaseSemaphore, в которой значение семафора увеличивается на 1. Мьютексы, как и семафоры, - объекты ядра. Функционирование мьютексов похоже на критические секции Win32, с разницей в том, что последние выполняются в пользовательском режиме. В каждый момент времени мьютекс разрешает выполняться только одному потоку и предоставляет доступ только к одному ресурсу. При этом он позволяет синхронизировать несколько потоков, храня идентификатор потока, который захватил ресурс и счетчик количества захватов. Чтобы создать мьютекс, можно воспользоваться функцией CreateMutex, ее параметры аналогичны рассмотренным выше. Когда ожидание мьютекса потоком успешно завершается, последний получает монопольный доступ к защищенному ресурсу. Все остальные потоки, пытающиеся обратиться к этому ресурсу, переходят в состояние ожидания. Когда поток, занимающий ресурс, заканчивает с ним работать, он должен освободить мьютекс вызовом функции ReleaseMutex. Эта функция уменьшает счетчик рекурсии в мьютексе на 1. Выбор используемого механизма синхронизации во многом зависит от времени его исполнения и кода, в котором он используется.

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

Заключение

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

В этой статье сначала мы разобрались с примитивами параллельного кодинга - общими понятиями, затем разобрались, как они исполнены в конкретном API - Win 32 threads. Рамки статьи не позволили нам рассмотреть другие API для многопоточного кодинга. Будем надеяться, что у нас еще будет возможность когда-нибудь продолжить обсуждение этой нужной темы.

Желаю удачи, до встречи!

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

Зако́н Амдала - иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей.

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

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

Пусть процессоры однородны по производительности. Т 0 – время выполнения последовательной части параллельного алгоритма, например, генерирование начальных данных и обработка полученного при решении задачи результата. Т 1 , Т 2 , ... Т p – время последовательной работы, выполняемой каждым процессором без взаимодействия между собой. Тогда время выполнения задачи на p процессорах определяется неравенством:

где i=1, 2, ... p. Равенство получается, когда Тi равны между собой . Отсюда, подставляя
T seq – T 0 , где T seq есть время выполнения задачи на одном процессоре , получаем T par ≥ T 0
.

Делим на T seq и, обозначая через f = T 0 / T seq - долю (fraction) последовательного участка в общем объеме вычислений, получим:
.(1.1)

Ускорение (Speedup ) – это отношение времени выполнения задачи в последовательном режиме (на 1 процессоре), ко времени выполнения задачи в параллельном режиме (на p процессорах).

, используя неравенство (1.1), получим
(1.2)

Отсюда видно, что при f=0 и равенстве T i получим S=p, при f >0 и p → ∞, получим
. Данная функция является монотонно-возрастающей по p и, значит, достигает максимума на бесконечности. Следовательно, ни на каком числе процессоров ускорение счета не может превысить обратной величины доли последовательного участка .

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

Эффективность распараллеливания- это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

(1.2)

Т.е. если ускорение S = p (максимально возможное на p процессорной машине), то эффективность распараллеливания задачи равна 100%. Используя закон Амдаля получаем верхнюю оценку эффективности:

E ≤ 100%
(1.3)

Например, E ≤ 52.25% для p=100 и f=0.01 и E ≤ 9.1% для p=1000 и f=0.01.

Вывод . При малой долипоследовательной работыувеличение количества процессов приводит к ухудшению параллельной эффективности (причина – с ростом процессов растет количество обменов). Например, если f=0.01 (1%), то Е<100 и использовать для решения параллельной задачи более 100 процессоров нецелесообразно. Для повышения эффективности , как правило, не распараллеливают управляющие части программы или небольшие участки вычислений, которые требуют интенсивной синхронизации процессов.

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

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

Масштабируемость – этопропорциональное увеличение объема задачи с увеличением числа используемых для ее решения процессоров. Наличие масштабируемости задач является важным свойством тестовых систем оценки производительности параллельных вычислительных систем.

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

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

Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма T 0 = P *Tp − T 1 , где T 1 - время выполнения последовательного алгоритма задачи, T p - время выполнения алгоритма задачи на P процессорах.

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

Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:

Tp = (T 1 + T 0 )/P , Sp = T 1 / Tp = (P* T 1 )/(T 1 + T 0 )

Тогда эффективность использования процессоров можно выразить как

E P = Sp/P = T 1 / (T 1 + T 0 ) = 1/(1+ T 1 /T 0 )

Тогда, если сложность решаемой задачи является фиксированной (T 1 =const ), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0 . При фиксированном числе процессоров, эффективность можно улучшить путем повышения сложности решаемой задачи T 1 , поскольку предполагается, что при увеличении сложности накладные расходы T 0 растут медленнее, чем объем вычислений T 1 .

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

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

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

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

1. Примеры топологий сети передачи данных

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

Полный граф (completely-connected graph or clique) – система, в которой между любой парой процессоров существует прямая линия связи, поэтому данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров.

Линейка (linear array or farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений).

Кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки.

Звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений.

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

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

а) два процессора имеют соединение, если двоичные представления их номеров имеют

только одну различающуюся позицию;

б) N-мерный гиперкуб может быть разделен на два (N-1)-мерных гиперкуба (всего возможно N различных разбиений);

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

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