5.2. Параллельная обработка

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

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

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

В таком классическом виде машина Тьюринга представляет собой систему Один поток Команд, Один поток ДанныхилиОКОД. Архитектура такого вида называетсяскалярной. Кроме нее существует векторная архитектура.

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

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

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

Теперь рассмотрим параллелизацию с применением этих вариантов.

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

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

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

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

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

В свете вышесказанного, существует следующее достаточно интересное решение. Если разрядность АЛУ достаточно высока и намного превышает разрядность обрабатываемых данных, мы можем одной командой обрабатывать несколько ячеек данных (в процессорах Intel такая технология получила название MMX). Такое решение не превращает скалярный процессор в векторный, так как таким образом процессор работает с данными меньшей разрядности, чем та, на которую он проектировался. Однако, это предоставляет возможность векторной обработки некоторых данных в скалярном процессоре. Недостаток этой технологии тот же – дополнительные команды и необходимость разработки специальных программ.

Конвейерная архитектура не дает уменьшения скорости выполнения одной команды. Казалось бы, зачем обрабатывать элемент данных в несколько этапов, если можно сделать каретку настолько сложной, что все этапы будут заменены на одно действие? На практике, достаточно сложная обработка, если пытаться выполнить ее за одну операцию, требует огромного усложнения АЛУ каретки. Реализовать такую операцию либо невозможно, либо крайне трудно. С помощью поэтапной (пошаговой) обработки можно реализовать сложные операции, которые при аналогичной одношаговой потребовали бы, например, сотни и тысячи раз большее количество элементов переключения. Выполняя одну операцию за несколько этапов, мы увеличили бы время выполнения. Однако конвейерная обработка позволяет исключить это увеличение. Ее эффект проистекает из того, что, когда для нас имеет значение скорость выполнения, мы обрабатываем содержимое не одной ячейки, а множества ячеек, которые постоянно поступают в наш процессор. Когда содержимое одной ячейки переходит от первого элемента конвейера ко второму, на вход первого элемента поступает содержимое следующей. Если конвейер состоит, например, из пяти узлов, на нем обрабатывается одновременно пять ячеек. Если время обработки одной ячейки равно сумме задержек на каждом узле конвейера, то для большого числа обрабатываемых ячеек это время обработки одной ячейки приближается к задержке на одном из узлов конвейера (на котором время обработки максимально).

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

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

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

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

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

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

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

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

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

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

Способ 1. Общая память. Некоторая память организована таким образом, что к ней могут получить одновременный доступ несколько устройств. Через эту общую память происходит обмен данными. Задача только в том, чтобы перед началом вычислений определить – где будут храниться данные, которые предназначены для обмена. Такой способ наиболее прост для программирования и дает наивысшую скорость обмена.

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

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

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

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

Способ 2. Массивно-параллельные системы. В таких системах компьютеры с классической архитектурой объединены некоторой коммуникационной средой. Главное достоинство такого способа – простота реализации. Кроме того, данная архитектура не ограничивает ни количество, ни состав устройств, входящих в параллельную систему.

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