пятница, 11 мая 2012 г.

Часть 1. История развития параллельной обработки и классификация современных подходов

В 1946 году трое ученых, одним из которых был Джон фон Нейман, опубликовали статью, в которой изложили 5 принципов заложивших основу современных компьютеров. Два других автора: Артур Бёркс и Герман Голдстайн, и тогда были не очень известны, а т.к. эти принципы, в силу известности фон Неймана, получили название в его честь, то про этих двух авторов сейчас мало кто и знает.
Одним из принципов предложенным в этой статье, был принцип «Последовательного программного управления», который гласит: «Программа состоит из набора команд, которые выполняются процессором автоматически друг за другом в определенной последовательности». И этот постулат, надолго определил основное направление развития процессоров, да и вычислительной техники. И только относительно недавно, когда увеличивать тактовую частоту процессоров стало технологически не выгодно, основные взоры обратились из последовательного выполнения команд, в параллельное.



Пытливый читатель спросит, как же так, ведь уже Windows 95 позволяла выполнять несколько задач одновременно: слушать музыку, работать в Word и, например, копировать файлы? Да, но все равно процессор там был фон Неймоновский, и в единицу времени выполнялась только одна команда. Как это происходило? Давайте обсудим.
Начнем мы даже немного раньше 1995 года, а именно с 1965, когда на рынке компьютеров появился IBM/360. Данная машина относилась к третьему поколению компьютеров и была построена с применением интегральных схем. Именно на этих машинах, на которые легла задача не только научных вычислений, но и коммерческой обработки данных, выяснилось, что загрузка и выгрузка данных может занимать время сопоставимое с их обработкой. На IBM 7094 (предшественнице IBM/360) время загрузки/выгрузки составляло 5-10%, научные расчеты были трудоемки, процессор медленен и всё, всех устраивало. Здесь же сложилась ситуация, что данных много, алгоритмы просты и загрузка/выгрузка занимала 80-90% времени решения задачи, или, говоря другими словами, процессор использовался на 10-20%. Само собой, это не устраивало бизнес, который покупал эти машины. Сложившаяся ситуация подтолкнула программистов на такой режим обработки данных, при котором можно было бы загрузить процессор на 100%.
В чем же заключалось это решение? Да очень просто. В память компьютера загружалась не 1 задача, а сразу несколько:
Пока первая задача ожидала загрузки данных, вторая выполняла обработку на процессоре. Так, просто и красиво получилось загрузить процессор на 100%. Но у данного подхода оказался один существенный дефект. Чтобы все это заработало, все программы должны быть загружены в память сразу, а результат будет получен только тогда, когда дорешаются все задачи. Соответственно, вы подготовили программу, отдали в вычислительный центр, несколько таких программ собрали в пакет и загрузили в вычислительную машину. Уже в самом начале ваша программа выполнила недопустимую операцию и прекратила расчет. Об этом печальном факте вы узнаете через пару часов, когда отработает весь пакет. Получите результаты, исправите программу, принесете в вычислительный центр, и опять ждать результата пару часов. Представляете себе отладку приложений в таком режиме?
Именно из-за таких проблем, многие инженеры, программисты, с ностальгией вспоминали времена, когда компьютер решал только одну задачу, и если что-то шло не так, можно было вмешаться сразу. Это желание и привело к появлению систем с режимом разделения времени. Как я уже сказал, компьютер стал достаточно мощным, и его производительности было очень много для 1 пользователя, так почему бы не подключить к нему 50 терминалов и пока 30 пользователей пьют кофе, обсуждают погоду, думают над алгоритмом решения, то остальным 20 ресурсов вполне хватало. Да и к тому же, вспомните по себе, сколько раз вы отдавали компьютеру небольшую задачу: переименовать файл, вставить строку текста, перекомпилировать небольшую dll; и сколько раз большую: провести индексацию 10 млн. записей, провести рендеринг 3D сцены? Вот в этом и заключается идея, давайте давать ресурс машины всем, но по небольшому кванту времени. Первая такая система (CTSS – Compatible Time Sharing System) была разработана Массачусетском технологическом институте.
Принцип работы такой системы достаточно прост, каждому пользователю процессоры выделял небольшой интервал времени – квант. В рамках которого и решались задачи поставленные пользователем, затем такой же квант выделялся второму пользователю, затем  третьему и т.д. Т.к. компьютер был достаточно производительным, и время от кванта выделенного пользователю до следующего выделенного ему же было достаточно мало, то создавалось ощущение, что пользователь работает с системой один:
В то время, никто не мог себе представить, что буквально через 30 лет, компьютеры, гораздо мощнее существовавших в то время мэйнфреймов, будут продаваться миллионами по цене меньше $1000. Ну, это как сейчас, утверждать, что через 30 лет, будут вместо автомобилей продаваться звездолеты, позволяющие развивать скорость превышающую скорость света в сотни раз.
В начале 80-х годов прошлого века компания IBM решила выпустить на рынок персональный компьютер – IBM PC. К тому времени, компания Digital Research имела достаточно хорошо зарекомендовавшую себя на процессорах Intel 8080 операционную систему CP/M (Control System for Microcomputers). Ничего удивительно, что когда к Биллу Гейтсу пришли представители IBM для покупки разработанного им языка BASIC, и спросили, какую операционную систему он им посоветует, то были отправлены в Digital Research. Там дело темное, говорят,  что на встречу с представителем IBM пришел не директор, а один из рядовых сотрудников, да и адвокат Digital Research отказался подписывать NDA о том, что IBM планирует выпуск персоналок. В общем, когда представитель IBM пришел к Гейтсу второй раз, он сказал, что сделает свою. Таким образом, первая версия DOS была куплена у Seattle Computer Products, доработана и под маркой DOS/BASIC передана IBM. По пожеланиям IBM операционная система дорабатывалась, и, с ростом Microsoft, куда перешел и один из разработчиков версии DOS от Seattle Computer Products, получила название MS DOS.
Затем был первый графический пользовательский интерфейс (GUI) от Xerox. Первый провал Стива Джобса с проектом Lisa, его же успех с проектом Apple Macintosh, в котором он донес все достоинства GUI до конечного пользователя. Затем, надстройка для MS DOS  с названием Windows 3 (чуть позже 3.1 и самой стабильной 3.11). Но все это было однозадачно, т.е. если вы переключались из игры в калькулятор, то игра приостанавливалась, до тех пор, пока вы не сделаете ее окно активным (я сейчас говорю про MacOS 6 и Windows 3), с MS DOS все обстояло еще хуже.
Вот собственно мы и дошли до MS Windows 95, которая благодаря защищенному режиму процессора (появился на процессорах 80386) могла обеспечить многозадачность с разделением времени. Принцип тот же, что и у CTSS, но процессор делиться не между задачами разных пользователей, а между задачами одного пользователя. Это была, конечно, не параллельная обработка данных, а последовательная. Ведь параллелизма можно достичь только тогда, когда у вас 2 и более процессора (ну или 1 процессор с двумя и более ядрами). Но работало для того времени просто замечательно. Кстати, в то время ходил вот такой анекдот:
Сын: Папа, а правда, что Windows 95 многозадачная операционная система?
Папа: Да, сынок. Вот доформатирую дискету и покажу.
Ладно, давайте заканчивать с историей вопроса и немного поговорим о том, как принято разделять виды параллелизма. К настоящему времени выделились два способа распараллеливания: на основе задач (task parallelism) и на основе данных (data parallelism).
Если поискать определения этих способов, то мы увидим что-то вроде этого:
Параллелизм задач – возможность одновременно выполнять различные локальные задачи внутри глобальной задачи.
Параллелизм данных – возможность одновременной работы с несколькими единицами данных внутри локальной задачи.
Все вроде понятно, но давайте на конкретном пример. У нас с вами есть процессоры (аппаратная часть), несколько массивов (данные) и необходимость найти в каждом массиве позицию на которой находится значение X (задачи).
Если у нас процессор 1, то сначала будет последовательно просмотрен первый массив, затем второй и т.д. Такой способ решения называется последовательной обработкой:
Хорошо, процессоров у нас 2. И здесь и начинается различие между двумя подходами. В параллелизме данных, первый процессор будет искать в первой половине массива, второй во второй половине, по окончании меньший из двух индексов найденных процессорами будет принят за ответ:
Параллелизм задач, подразумевает, что у нас задача по поиску в первом массиве выполняется на первом процессоре, а задача по поиску на втором массиве на, соответственно, втором процессоре:
И у первого и у второго подхода есть свои плюсы и минусы, в первом надо собрать результаты со всех процессоров и как то привести к общему знаменателю, зато время нахождения решения на первом массиве T/2, на втором T, следовательно, среднее время решения ¾*T. Во втором подходе, ничего синхронизировать нет необходимости, но время решения и первой и второй задачи, да и среднее равно T.
Ладно, давайте на этом на сегодня закончим, а в следующий раз поговорим о процессах и потоках.

2 комментария:

  1. Ну раз уж меня тема параллельных вычислений зацепит очень плотно в следующем учебном году буду комментировать  и вносить дополнения.
    Хотелось бы добавить, что возможны сочетания параллелизма по данным и параллелизма задач, тогда соответственно можно выделить четыре типа систем:
    1. (SISD)Single Instructions Single Data – та самая классическая архитектура Фон-Неймана.
    2. (MISD)Multi Instructions Single Data – множество параллельных процессоров с единственной общей памятью, если честно не могу привести примеров.
    3. (SIMD)Single Instructions Multi Data – это класс систем в которых несколько процессоров, но выполняющий одни и те же команды синхронно над разными данными, похоже на конвейерную обработку, применяемую в современных видеокарточках.
    4. (MIMD) Multi Instructions Multi Data – системы содержащие множество процессоров, асинхронно трудящимися над разными данными, это уже соответственно класс многопроцессорных систем.

    Кстати классифицировать вычислительные системы по потокам данных и потокам команд предложил в 1966 г. профессор Стенфордского университета М.Д.Флин (M.J.Flynn) http://ru.wikipedia.org/wiki/Флинн,_Майкл.

    ОтветитьУдалить