Основы параллельных вычислений (1119586)

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

Текст из файла

Основы параллельных вычисленийDMVN Corporation15 мая 2006 г.Этот текст представляет собой введение в параллельное программирование, ориентированное в основном настудентов третьего курса МехМата. Естественно, оно ни в коем случае не претендует на полноту изложенияматериала.

На эту тему написано немало книг, но многие из них, в частности, «Основы параллельных вычислений» в двух томах за авторством К. Ю. Богачёва, рассчитаны, по мнению автора данного текста, на студентов,которые сравнительно хорошо знают архитектуру компьютера и принципы функционирования современных(многозадачных) операционных систем. Добавим к этому тот непреложный факт, что читать целую книжкудолго и скучно, особенно если хоть что-нибудь в ней непонятно. Так вот, сей материал предназначен для тех,кто хочет сдать зачёт, не утруждая штудированием богачёвских книг. Я считаю, что основы параллельногопрограммирования можно изложить на нескольких страницах.

Ну что-ж, глубоко вздохнём и приступим. . .Последняя компиляция: 15 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.1. Что такое параллельное программирование?Одна из задач, которую может поставить перед собой программист, — это сделать так, чтобы его программаработала быстро. Добиться этого можно многими способами. Например, можно совершенствовать алгоритм так,чтобы уменьшить число элементарных операций и тем самым сократить время выполнения задачи. Но предположим, однако, что мы довели алгоритм «до предела», и не можем в общем случае снизить число требуемыхопераций.

Тогда мы начинаем оптимизировать программу на низком уровне, то есть за счёт особенностей архитектуры той системы, на которой всё это работает. Как правило, тут нельзя обойтись языком высокого уровня(типа C/C++), и приходится некоторые участки программы (а иногда и всю целиком) переписывать на языкенизкого уровня (то есть ассемблере — языке машинных команд). Ну, хорошо, допустим, мы её переписали.

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

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

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

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

д.), и чтобы процессоры не ждали другдруга.После такого введения читателю может показаться, что всё очень сложно. На самом деле, половину вышеперечисленных проблем возьмёт на себя операционная система, так что нам остаётся лишь понять, какие блокив нашей программе могут выполняться параллельно. А как это понять — читайте дальше.12. Процессы и потоки2.1. Понятие процессаПочти все современные операционные системы, такие как Windows или Unix, являются многозадачными.Это значит, что в один и тот же момент времени на компьютере может независимо выполняться несколькопрограмм одновременно. Но это не есть критерий многозадачности.

Например, старые версии Windows (3.x)позволяли запускать одновременно несколько приложений, но истинной параллельности выполнения там небыло. Там происходило примерно следующее: очередная программа получает от системы сообщение и начинает обрабатывать его. Когда сообщение обработано, программа передаёт управление системе, затем система«кормит» сообщениями следующую по списку программу, и так далее по циклу.

Но если какая-то программа зависает, то вместе с ней зависает и вся система, ибо управление в результате зацикливания так никогда к системеи не вернётся. Кроме того, программы разделяли одни и те же системные ресурсы (например, память). А вотв Windows 95 (и тем более в Windows NT) всё стало намного лучше: система не ждёт, пока каждая программазавершит обработку сообщения, а сама отбирает управление и передаёт его другой программе, так что «подвесить» систему уже несколько сложнее.

Более того, в Windows 95 появилось понятие процесса, представляющегособой пару p = (P, R), где P — программа, а R — используемые ею ресурсы. Причём есть два процесса p(P1 , R1 )и q(P2 , R2 ), то R1 ∩ R2 = ∅, т. е. разные процессы задействуют разные ресурсы. Например, два процесса немогут использовать один и тот же блок памяти — если блок выделен одним процессом, то только он имеет кнему доступ.1Итак, из вышесказанного должно быть ясно, что процесс — это сама программа (то есть её код) и некоторыйнабор используемых системных ресурсов. Запуск программы эквивалентен созданию процесса, её завершение —уничтожению всей информации о процессе в недрах системы и освобождение ранее занимаемых программойсистемных ресурсов.2.2. Shared memoryТеперь вернёмся к поставленной задаче: распараллелить наши вычисления. Самое простое, что приходитна ум, это запустить несколько процессов — пусть они чего-то считают, каждый сам по себе, а управлениемих параллельного выполнения пускай занимается операционная система (ежели она многозадачная).

Но этотспособ не самый удобный. В самом деле, пусть наша программа занимается умножением двух матриц огромнойразмерности. Не совсем понятно, куда записывать массивы с этими матрицами: если мы их положим в памятьодного процесса, то другой процесс их «не увидит» (а точнее, не будет иметь к ним доступа на чтение и запись).Тут есть выход из положения: в Linux существует так называемая разделяемая память (shared memory), то естьпамять, к которой могут иметь доступ несколько процессов, если все они знают некоторое число, называемоеключом (key) общей области памяти.

Этот ключ представляет собой что-то вроде пароля: знаешь пароль — пишина здоровье, а не знаешь — не запишешь и не прочтёшь. Общий блок памяти выделяется с помощью функцииshmget (от слов Shared Memory Get). Я не хотел бы подробно рассматривать данный способ распараллеливания,так как он в целом весьма неудобен и приводит усложнению программы без особой необходимости. Но общаяидея довольно проста: выделяется общий блок памяти, затем вызывается функция fork(), которая «раздваивает» процесс (создаёт точную его копию), и далее оба процесса производят вычисления (независимо друг отдруга) в общей области памяти. Однако ещё раз подчеркнём, что сей метод годится только для Unix-подобныхсистем, и, таким образом, универсальным не является, поэтому мы на нём останавливаться не будем.2.3.

ПотокиВ переводе с английского слово «thread» означает «нить». Тут надо сразу предупредить читателя, что авторуизвестно по меньшей мере ТРИ различных перевода этого термина, а именно: нить, поток и задача. Последнийперевод используется в книге Богачёва; два остальных (гораздо более правильные!!!) встречаются во многихдругих книгах весьма авторитетных авторов.В среде Windows есть ещё такое понятие, как fiber, которое разумнее всего перевести как «волокно». Этоназвание ещё больше запутывает терминологию, но. .

. так уж исторически сложилось. Иерархия процессов,потоков и fiber’ов выглядит так: один процесс может иметь несколько нитей, а каждая нить, в свою очередь,несколько fiber’ов. Что касается последней, самой мелкой, так сказать, «единицы многозадачности», то мы ихздесь рассматривать не будем опять-таки в связи с тем, что присущи только семейству Windows.

Упомянутыони были только для того, чтобы читатель не удивлялся, встретив такое слово в программистской литературе.Ну, что же у нас осталось из средств осуществления многозадачности? Только одно: потоки (то бишь нити).Здесь и далее эти слова означают одно и то же. Так всё-таки, что такое поток и с чем его едят? Как написано1 На самом деле оно не совсем так, но мне не хочется вдаваться в детали механизма распределения памяти в Windows, так какв других операционных системах он реализован несколько иначе.2в справочной системе MSDN, «a thread is the basic unit to which the operating system allocates processor time».Смысл тут ясен: это самая маленькая «часть» процесса, для которой отдельно выделяется процессорное время, то есть время, которое процессор извёл на выполнение потока.

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

Замечу также, что потокивнутри процесса равноправны — среди них на самом деле нет ни главных, ни подчинённых.Ну вот, кажется, вся теория изложена. Надо бы теперь показать, как всё это работает.3. Реализация многопоточного приложенияЗдесь будет рассказано о том, как создавать и завершать потоки, и как осуществлять их взаимодействие.Естественно, список системных функций для управления потоками приводится только для системы Linux, хотяимеет смысл отметить, что в Windows механизм потоков устроен очень похожим образом — отличаются, посути, только названия самих функций.3.1. Функции управления потокамиДля начала подключим заголовочный файл pthread.h — именно в нём описаны все функции для работы спотоками. Их весьма много, но нам пригодится всего две из них. При компиляции программы нужно подключитьбиблиотеку pthread, например:g++ main.cpp -lpthreadС точки зрения программиста, поток — это просто отдельная функция, запускаемая особым образом.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы