Определите характеристики доступных вам многопроцессорных
1.1. Определите характеристики доступных вам многопроцессорных машин. Сколько процессоров в каждой машине и каковы их рабочие частоты? Насколько велик размер их кэш-памяти, как она организована? Каково время доступа? Какой используется протокол согласования памяти? Как организована связующая сеть? Каково время удаленного доступа к памяти или передачи сообщения?
1.2. Многие задачи можно решить более эффективно с помощью параллельной, а не последовательной программы (конечно, при наличии соответствующего аппаратного обеспечения). Рассмотрите программы, которые вы писали раньше, и выберите две из них, которые можно переписать как параллельные. Одна из них должна быть итеративной, а другая— рекурсивной. Затем: а) запишите кратко условия задач и б) разработайте псевдокод параллельных программ, решающих поставленные задачи.
1.3. Рассмотрите умножение матриц в разделе 1.4:
а) напишите последовательную программу для решения этой задачи. Размер матрицы п должен быть аргументом командной строки. Инициализируйте каждый элемент матриц а и Ь значением 1. О (тогда значение каждого элемента результирующей матрицы с будет п);
б) напишите параллельную программу для решения этой задачи. Вычислите полосы результата параллельно, используя Р рабочих процессов. Размер матрицы п и число рабочих процессов Р должны быть аргументами командной строки. Вновь инициализируйте каждый элемент матриц а и b значением 1.0;
в) сравните производительность ваших программ. Поэкспериментируйте с разными значениями параметров n и р. Подготовьте график результатов и объясните, что вы заметили;
44 Глава 1. Обзор области параллельных вычислений
г) преобразуйте ваши программы для умножения прямоугольных матриц. Размер матрицы а должен быть pxq, а матрицы b — qxr. Тогда размер результирующей матрицы будет рхг. Повторите часть в данного упражнения для новых программ.
1.4.
2.1. Разберите эскиз программы в листинге 2.1, выводящей все строки с шаблоном pattern в файл:
а) разработайте недостающий код для синхронизации доступа к буферу buffer. Для программирования синхронизации используйте оператор await;
б) расширьте программу так, чтобы она читала два файла и выводила все строки, содержащие шаблон pattern. Определите независимые операции и используйте отдельный процесс для каждой из них. Напишите весь необходимый код синхронизации.
2.2. Рассмотрите решение задачи копирования массива в листинге 2.2. Измените код так, чтобы переменная р была локальной для процесса-производителя, а с — для потребителя. Следовательно, эти переменные нельзя использовать для синхронизации доступа к буферу buf. Вместо них используйте для синхронизации процессов две новые булевы переменные empty и full. В начальном состоянии переменная empty имеет значение true, full — false. Добавьте новый код для процессов потребителя и производителя. Для программирования синхронизации используйте оператор await.
2.3. Команда ОС Unix tee вызывается выполнением:
tee filename
Эта команда читает стандартный ввод и записывает его в стандартный вывод и в файл filename, т.е. создает две копии ввода:
а) запишите последовательную программу для реализации этой команды;
б) распараллельте вашу последовательную программу, чтобы она использовала три процесса: чтения из стандартного ввода, записи в стандартный вывод и записи в файл filename. Используйте стиль "со внутри while";
80 Часть 1. Программирование с разделяемыми переменными
в) измените свое решение из пункта 6, используя стиль "while внутри со". В частности, создайте процессы один раз. Используйте двойную буферизацию, чтобы можно было параллельно читать и писать. Для синхронизации доступа к буферам используйте оператор await.
2.4. Рассмотрите упрощенную версию команды ОС Unix di ff для сравнения двух текстовых файлов.
6.1. В многопроцессорном ядре, описанном в разделе 6.2, процессор выполняет процесс Idle (см. листинг 6.2), когда определяет, что список готовых к работе процессов пуст. На некоторых машинах есть бит в регистре (слове) состояния процессора. Его установка означает, что процессор должен бездействовать до возникновения прерывания (бит бездействия). В таких машинах есть и межпроцессорные прерывания, т.е. один процессор может быть прерван другим, в результате чего он входит в обработчик прерывания ядра на центральном процессоре.
• Измените многопроцессорное ядро в листинге 6.3 так, чтобы процессор сам устанавливал бит бездействия, когда список готовых к работе процессов пуст. Таким образом, для запуска процесса на одном процессоре потребуется выполнить команду на другом.
6.2. Предположим, что планирование процессов ведется одним главным процессором, выполняющим только процесс-диспетчер. Другие процессоры выполняют обычные процессы и процедуры ядра.
Разработайте процесс-диспетчер и соответственно измените многопроцессорное ядро в листинге 6.3. Определите все необходимые структуры данных. Помните, что бездействующий процессор не должен блокироваться внутри ядра, поскольку тогда в ядро не смогут войти остальные процессы.
6.3. Предположим, что все процессоры мультипроцессорной системы имеют собственные списки готовых к работе процессов и выполняют процессы только из них. Как было отмечено в тексте, возникает проблема балансировки нагрузки процессоров, поскольку новый процесс приходится назначать какому-нибудь из процессоров.
Существует много схем балансировки нагрузки процессоров, например, можно назначать новый процесс случайному процессору, "соседу" или поддерживать приблизительно одинаковую длину списков готовых к работе процессов. Выберите одну из схем, обоснуйте свой выбор и измените многопроцессорное ядро в листинге 6.3 так, чтобы в нем использовались несколько списков готовых к работе процессов и выбранная схема балансировки нагрузки процессоров.
10.1. Рассмотрим распределенное ядро в листингах 10.2 и 10.3:
а) расширьте реализацию, чтобы у канала могло быть несколько получателей. В частности, измените примитивы receiveChan и emptyChan, чтобы процесс на одной машине мог получать доступ к каналу, расположенному на другой;
б) измените ядро, чтобы примитив sendChan стал полу синхронным, т.е., вызывая sendChan, процесс должен дождаться постановки сообщения в очередь канала (или передачи получателю), даже если канал расположен на другой машине;
в) добавьте в ядро код определения окончания программы. Можно не учитывать ожидающий ввод-вывод. Вычисления завершены, когда все списки готовых к работе процессов пусты и сеть бездействует.
10.2. Реализация синхронной передачи сообщений в листинге 10.4 предполагает, что и процесс-источник, и процесс-приемник именуют друг друга. Обычно же процесс-приемник должен либо указывать источник, либо принимать сообщения от любого ис-
Глава 10. Реализация языковых механизмов 401
точника. Предположим, что процессы пронумерованы от 1 до п и индекс 0 используется процессом-приемником для указания, что он готов принять сообщение от любого источника. В последнем случае оператор ввода присваивает параметру source идентификатор процесса, приславшего сообщение.
Измените протоколы взаимодействия в листинге 10.4, чтобы они обрабатывали описанную ситуацию. Как и в листинге, основой для реализации описанной выше формы синхронной передачи сообщений должна служить асинхронная передача сообщений.
10.3. Разработайте реализацию в ядре примитивов синхронной передачи сообщений synch_send и synch_receive, определенных в начале раздела 10.2. Сначала постройте однопроцессорное ядро. Затем разработайте распределенное ядро со структурой, показанной в листинге 10.1. Все необходимые процедуры можно брать из листингов 10.2 и 10.3.
10.4. Даны процессы Р[ 1:п], каждый из которых содержит значение элемента a[i] массива из п значений.
11.1. В начале подраздела по последовательным итерациям Якоби представлена простая последовательная программа. Затем описаны четыре оптимизации, приводящие к программе в листинге 11.1, и еще две оптимизации:
а) постройте серию экспериментов для измерения индивидуального и совокупного эффекта от данных шести оптимизаций. Начните с измерения времени выполнения главного цикла вычислений в программе для метода итераций Якоби на сетках различных размеров, например 64x64, 128x128 и 256x256. Подберите такие значения EPSILON и/или iters, чтобы вычисления занимали несколько минут. (Время должно быть достаточно большим, чтобы заметить эффект от улучшений.) Затем добавляйте в код по одной оптимизации и измеряйте повышение производительности. Составьте краткий отчет с результатами измерений и выводами;
б) проведите эксперименты, позволяющие оценить все шесть оптимизаций по отдельности и в различных комбинациях друг с другом, в отличие от пункта а, где оптимизации добавлялись одна за другой. Какие оптимизации оказались наиболее продуктивными? Укажите, имеет ли значение порядок их применения;
в) рассмотрите другие способы оптимизации программы. Ваша цель — получить максимально быструю программу. Опишите и измерьте эффект от каждой дополнительной оптимизации, которую вы придумали.
11.2. Реализуйте программу для метода итераций Якоби с разделяемыми переменными (см. листинг 11.2) и измерьте ее производительность. Используйте разные размеры сеток и количества процессоров. Оптимизируйте программу своим способом и измерьте производительность улучшенной программы. Составьте отчет, в котором будут описаны все проделанные изменения, представлены результаты измерений и выводы.
11.3. Реализуйте неоптимизированную и оптимизированные программы для метода итераций Якоби с передачей сообщений (см. листинги 11.3 и 11.4) и измерьте их производительность. Используйте сетки разных размеров и разное количество процессоров. Затем оптимизируйте программы своим способом и измерьте производительность улучшенных программ.
12.1. В разделе 12. 1 представлены реализации метода итераций Якоби, в которых используются библиотеки Pthreads, MPI и ОрепМР. С помощью библиотек Pthreads, MPI и ОрепМР составьте параллельные программы:
а) для задачи п тел;
б) для реализации LU-разложения.
Для программ с Pthreads и ОрепМР используйте разделяемые переменные, а с MPI — обмен сообщениями. Последовательные части своих программ напишите на С для Pthreads и на С или Фортране для MPI и ОрепМР.
12.2. Рассмотрите последовательные программы для следующих задач:
а) метод итераций Якоби (листинг 11.1);
б) задача п тел (листинг 11.6);
в) LU-разложение (листинг 11.11);
г) прямой и обратный ход (листинг 11.12).
В каждой программе выделите все случаи: 1) потоковых зависимостей, 2) антизависимостей, 3) зависимостей по выходу. Укажите, какие из зависимостей находятся в циклах, а какие создаются циклами.
12.3. Рассмотрим следующие последовательные программы:
а) метод итераций Якоби (листинг 11.1);
б) задача п тел (листинг 11.6);
в) LU-разложение (листинг 11.11);
г) прямой и обратный ход (листинг 11.12).
На рис. 12.1 перечислены некоторые типы преобразований программ в распараллеливающих компиляторах. Для каждого преобразования и каждой из перечисленных выше последовательных программ определите, можно ли применить преобразование к программе, и, если можно, покажите, как это сделать. Каждое преобразование рассматривайте независимо от других.
12.4. Повторите предыдущее упражнение, применяя в каждой программе несколько преобразований. Предположим, что программа пишется для машины с разделяемой памятью, имеющей восемь процессоров, а размер задачи п кратен восьми. Ваша цель — создать программу, которую совсем просто превратить в параллельную программу со сбалансированной вычислительной нагрузкой, удачным распределением данных и небольшими накладными расходами синхронизации. Для каждой программы: 1) подберите последовательность преобразований, 2) покажите, как изменяется программа после каждого преобразования, и 3) объясните, почему вы считаете, что либо полученный код приведет к хорошей параллельной программе, либо из исходной программы получить хорошую параллельную программу нельзя.
