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

Идея параллельной обработки возникла одновременно с появлением первых вычислительных машин. В начале 50-х гг. амери-канский математик Дж. фон Нейман предложил архитектуру по-следовательной ЭВМ, которая приобрела классические формы и применяется практически во всех современных ЭВМ. Однако фон Нейман разработал также принцип построения процессорной матрицы, в которой каждый элемент был соединен с четырьмя соседними и имел 29 состояний. Он теоретически показал, что такая матрица может выполнять все операции, поскольку она моделирует поведение машины Тьюринга.
Практическая реализация основных идей параллельной обработки началась только в 60-х гг. нашего столетия. Это связано с появлением транзистора, который благодаря малым размерам и высокой надежности по сравнению с электронными лампами позволил строить машины, состоящие из большого количества логических элементов, что принципиально необходимо для реализации любой формы параллелизма.
Появление параллельных ЭВМ с различной организацией (конвейерные ЭВМ, процессорные матрицы, многопроцессорные ЭВМ) вызвано различными причинами. Совершенствование этих ЭВМ происходило по внутренним законам развития данного типа машин.
Рассмотрим основные этапы совершенствования параллельных ЭВМ для каждого типа структур.
Конвейерные ЭВМ. Основополагающим моментом для развития конвейерных ЭВМ явилось обоснование академиком С.А.Лебедевым в 1956 г. метода, названного "принципом водопровода" (позже он стал называться конвейером). Прежде всего был реализован конвейер команд, на основании которого практи-чески одновременно были построены советская ЭВМ БЭСМ-6 (1957-1966 гг., разработка Института точной механики и вычислительной техники АН СССР) и английская машина ATLAS (1957-1963 гг.). Конвейер команд предполагал наличие многоблочной памяти и секционированного процессора, в котором на разных этапах обработки находилось несколько команд.
Конвейер команд позволил получить в ЭВМ БЭСМ-6 быстродействие в 1 млн. оп/с. В дальнейшем конвейеры команд совершенствовались и стали необходимым элементом всех быстродействующих ЭВМ, в частности, использовались в известных семействах ЭВМ IBM/360 и ЕС ЭВМ.
Следующим заметным шагом в развитии конвейерной обработки, реализованном в ЭВМ CDC-6600 (1964 г.), было введение в состав процессора нескольких функциональных устройств, позволяющих одновременно выполнять несколько арифметико-логических операций: сложение, умножение, логические операции.
В конце 60-х гг. был введен в использование арифметический конвейер, который нашел наиболее полное воплощение в ЭВМ CRAY-1 (1972-1976 гг.). Арифметический конвейер предполагает разбиение цикла выполнения арифметико-логической операции на ряд этапов, для каждого из которых отводится собственное оборудование. Таким образом, на разных этапах обработки нахо-дится несколько чисел, что позволяет производить эффективную обработку вектора чисел.

Сочетание многофункциональности, арифметического конвейера для каждого функционального блока и малой длительности такта синхронизации позволяет получить быстродействие в десятки и сотни миллионов операций в секунду. Такие ЭВМ называются суперЭВМ.
Процессорные матрицы. Идея получения сверхвысокого быстродействия в первую очередь связывалась с процессорными матрицами (ПМ). Предполагалось, что, увеличивая в нужной степени число процессорных элементов в матрице, можно получить любое заранее заданное быстродействие. Именно этим объясняется большой объем теоретических разработок по организации процессорных матриц.
В 60-х гг. в Институте математики Сибирского отделения АН СССР под руководством доктора технических наук Э.В.Евреинова сформировалось комплексное научное направление "Однородные системы, структуры и среды", которое получило развитие не толь-ко в СССР, но и за рубежом. Книга "Однородные универсальные вычислительные системы высокой производительности", изданная в 1966 г., была одной из первых в мире монографий, посвященных этой теме. В работах по однородным средам и системам исследовались матрицы с различными связями между элементами и конфигурацией, а также с элементами разной сложности и составом функций.
Поскольку в 60-е гг. логические схемы с большим уровнем интеграции отсутствовали, то напрямую реализовать принципы функционирования процессорной матрицы, содержащей множество элементарных процессоров, не представлялось возможным. Поэтому для проверки основных идей строились однородные системы из нескольких больших машин. Так, в 1966 г. была построена система Минск-222, спроектированная совместно с Институтом математики Сибирского отделения АН СССР и минским заводом ЭВМ им. Г.К.Орджоникидзе. Система содержала до 16 соединенных в кольцо ЭВМ Минск-2. Для нее было разработано специальное математическое обеспечение.
Другое направление в развитии однородных сред, основанное на построении процессорных матриц, состоящих из крупных процессорных элементов с достаточно большой локальной памятью, возникло в США и связано с именами Унгера, Холланда, Слотника. Была создана ЭВМ ILLIAC-IV (1966-1975 гг.), которая надолго определила пути развития процессорных матриц. В машине использовались матрицы 8*8 процессоров, каждый с быстродействием около 4 млн. оп/с и памятью 16 кбайт. Для ILLIAC-IV были разработаны кроме Ассемблера еще несколько параллельных языков высокого уровня. ЭВМ ILLIAC-IV позволила отработать вопросы коммутации, связи с базовой ЭВМ, управления вычислительным процессом. Особенно ценным является опыт разработки параллельных алгоритмов вычислений, определивший области эффективного использования подобных машин.
Примерно в то же время в СССР была разработана близкая по принципам построения ЭВМ М-10. Затем процессорные матрицы стали разрабатываться и выпускаться в ряде стран в большом количестве. Широко известной советской ЭВМ этого класса являлась машина ПС-2000, разработанная Институтом проблем управления АН СССР и запущенная в 1982 г. в производство.
Одной из наиболее сложных частей процессорных матриц является система коммутации. Самые простые ее варианты - кольцо и регулярная матрица соединений, где каждый узел связан только с двумя или четырьмя соседними, сильно ограничивают класс эффективно решаемых задач. Поэтому на протяжении всего времени существования параллельной обработки разрабатывались коммутаторы с более широкими возможностями: многомерные кубы, универсальные коммутаторы, коммутационные среды. В СССР работы, связанные с коммутаторами для ПМ, наибольшее развитие получили в Таганрогском радиотехническом институте.
Многопроцессорные ЭВМ. Одной из первых полномасштабных многопроцессорных систем явилась система D825 фирмы "BURROUGHS". Начиная с 1962 г. было выпущено большое число экземпляров и модификаций D825.
Выпуск первых многопроцессорных систем, в частности D825, диктовался необходимостью получения не высокого быстродействия, а высокой живучести ЭВМ, встраиваемых в военные командные системы и системы управления. С этой точки зрения параллельные ЭВМ считались наиболее перспективными.
Система D825 содержала до четырех ПЭ и 16 модулей памяти, соединенных матричным коммутатором, который допускал одновременное соединение любого процессора с любым блоком памяти.
Существует мнение, что система D825 получила широкое распространение потому, что для нее впервые была разработана полноценная операционная система ASOR, обеспечившая синхронизацию процессов и распределение ресурсов.
В дальнейшем в СССР и на Западе были разработаны многопроцессорные системы, в которых все большее внимание уделялось операционным системам, языкам программирования, параллельной вычислительной математике.
Совершенствование микроэлектронной элементной базы, появление в 80-х годах БИС и СБИС позволили перейти к реализации структур с очень большим количеством ПЭ. Появились разработки по систолическим массивам, реализации многопроцессорных систем с программируемой архитектурой, ЭВМ с управлением от потока данных.
Большая плотность упаковки транзисторов на кристалле позволила разместить в одной микросхеме несколько АЛУ. Это по-зволило реализовать принцип суперскалярной обработки.
Если в последовательной ЭВМ пользователь в процессе программирования задачи в основном следит за логикой метода вычислений, то в параллельной ЭВМ ему приходится дополнительно заниматься размещением данных и синхронизацией вычислительных процессов. Это означает, что процесс программирования существенно усложняется, особенно если программирование ведется на уровне Ассемблера, чтобы повысить эффективность использования дорогостоящих параллельных ЭВМ. Такое программирование доступно только профессионально подготовленным программистам.
По мере удешевления и более широкого распространения параллельных ЭВМ доступ к ним получили пользователи, которые не являются профессиональными программистами, поэтому вопрос о системах программирования значительно обострился. Для облегчения программирования для каждой ЭВМ стали создаваться параллельные ЯВУ. Так, для ILLIAC-IV было создано несколько языков: TRANQUIL, IVTRAN, GLYPNIR; для ЭВМ Эльбрус - язык ЭЛЬ-76 и адаптированы языки Алгол-68, Фортран, Паскаль и PL-1. Применение ЯВУ освобождает пользователя от знания многих деталей структуры конкретной ЭВМ. Однако полностью освободиться от влияния структуры ЭВМ на язык не удается, поэтому возникла проблема мобильности программного обеспечения, под которой понимают возможность переноса программ с одной параллельной ЭВМ на другую с минимум переделок или вообще без них.
Очевидным средством обеспечения мобильности является разработка и использование (в качестве стандартных) проблемно-ориентированных языков, включающих средства описания параллельных вычислений. К ним относятся языки Алгол-68, ADA, Фортран-8X.
Большое внимание уделяется разработке автоматических рас-параллеливателей последовательных программ для исполнения на параллельных машинах различных типов.
Наиболее радикальный путь автоматизации программирования вообще и параллельного в частности состоит в использовании методов искусственного интеллекта. В СССР это направление получило широкое развитие, разработаны системы программирования ДИЛОС, СПОРА, ПРИЗ.

Основной характеристикой при классификации [3] параллельных вычислительных систем является способ организации памяти :

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

Можно выделить следующие классы параллельных систем :

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

PVP - параллельные векторные системы.
( NEC SX-4/SX-5, CRAY J90/T90)
Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров. Как правило, несколько таких процессоров работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций.

MPP - системы массового параллелизма.
(МВС-1000, IBM RS/6000 SP2, SGI/CRAY T3E)
MPP состоит из нескольких однородных вычислительных узлов; Каждый такой узел имеет свою локальную память (прямой доступ к памяти других узлов невозможен), один или несколько центральных процессоров( иногда - жесткий диск). Узлы обычно связаны специальной высокоскоростной сетью. Общее число процессоров в таких системах может достигать нескольких тысяч.

NUMA - системы с неоднородным доступом к памяти.
(SGI Origin2000, Sun HPC 10000)
NUMA (Non Uniform Memory Access) представляет собой нечто среднее между SMP и MPP. В NUMA память физически распределена, но логически общедоступна. Масштабируемость NUMA-систем ограничивается объемом адресного пространства и возможностями операционной системы.

Кластеры - дешевый вариант MPP.
( Avalon, Beowulf)
Обычно это сеть из серийных PC или рабочих станций общего назначения, которая объединяется в ''виртуальную многопроцессорную машину''. Для связи узлов используется одна из стандартных сетевых технологий (Ethernet, Myrinet).

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

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

Предсказание переходов
В любой более-менее сложной программе присутствуют команды условного перехода. С точки зрения скорости выполнения кода программы современным процессором, поддерживающим внеочередное исполнение, любая команда условного перехода — препятствие, так как, до тех пор, пока не станет известно, какой участок кода после условного перехода окажется «актуальным» — его невозможно начать декодировать и исполнять. Для того чтобы как-то примирить концепцию внеочередного исполнения с командами условного перехода, предназначается специальный блок: блок предсказания ветвлений. Как понятно из его названия, он пытается предсказать, на какой участок кода укажет команда условного перехода, ещё до того, как она будет исполнена. В соответствии с его указаниями, процессором производятся действия: «предсказанный» участок кода загружается в кэш (если он там отсутствует), и даже начинается декодирование и выполнение его команд. Причём среди выполняемых команд также могут содержаться инструкции условного перехода, и их результаты тоже предсказываются, что порождает целую цепочку из пока не проверенных «предсказаний». Разумеется, если блок предсказания ветвлений ошибся, вся проделанная в соответствии с его предсказаниями работа просто аннулируется.
На самом деле, алгоритмы, по которым работает блок предсказания ветвлений, преимущественно просты. Потому, что чаще всего команда условного перехода встречается в циклах: некий счётчик принимает значение X, и после каждого прохождения цикла значение счётчика уменьшается на единицу. Соответственно, до тех пор, пока значение счётчика больше нуля — осуществляется переход на начало цикла, а после того, как он становится равным нулю — исполнение продолжается дальше. Блок предсказания ветвлений просто анализирует результат выполнения команды условного перехода, и считает, что если N раз подряд результатом стал переход на определённый адрес — то и в N+1 случае будет осуществлён переход туда же. Однако, несмотря на весю простоту, данная схема работает: например, в случае, если счётчик принимает значение 100, а «порог срабатывания» предсказателя ветвлений (N) равен двум переходам подряд на один и тот же адрес — легко заметить, что 97 переходов из 98 будут предсказаны правильно!
Несмотря на достаточно высокую эффективность простых алгоритмов, механизмы предсказания ветвлений в современных CPU всё равно постоянно совершенствуются.

Спекулятивные вычисления
Суперскалярные вычислительные системы, как правило, просматривают команды "вперед", чтобы лучше использовать ресурсы и, возможно, переставлять операции, добиваясь оптимальной производительности (Out-of-Order Execution). Поскольку все связи между операциями описываются именами (регистрами), основную сложность здесь представляют так называемые ложные зависимости. Наконец, суперскалярная архитектура характеризуется еще и так называемым спекулятивным характером вычислений (Speculative Execution). Система доходит до условного перехода (условие перехода при этом еще не известно) и выбирает одну из ветвей. Если повезло - есть выигрыш по скорости, иначе выполнение ошибочных потоков будет прекращено, а все результаты их деятельности будут аннулированы. Процессор возвращается в то же состояние, в котором он находился до начала выполнения этих потоков.
Мультискалярные микропроцессоры
Посути это одновременное выполнение нескольких параллельных потоков комманд (нитей).
Есть два случая реализации: в первом случае используется один регистровый файл и один набот функциональных устройств, здесь можно говрить о реализации много нитевого мультискалярного процессора. Это позволяет эффективно распределять ресурсы при выполнении программ с сильными зависимостями между нитями.
Во втором случае каждая нить выполняется на отдельном процессоре. Это позволяет выполнять слабосвязанные нити от одной или нескольких программ.

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

Мультиядерные микропроцессоры и гипертрейдинг.
Анонсированная в 2002 году компанией Intel технология Hyper-Threading –пример многопоточной обработки команд. Данная технология является чем-то средним между многопоточной обработкой, реализованной в мультипроцессорных системах, ипараллелизмом на уровне инструкций, реализованном в однопроцессорных системах.Фактически технология Hyper-Threading позволяет организовать два логическихпроцессора в одном физическом. Таким образом, с точки зрения операционной системы и запущенного приложения в системе существует два процессора, что даёт возможность распределять загрузку задач между ними.
Посредством реализованного в технологии Hyper-Threading принципа параллельности можно обрабатывать инструкции в параллельном (а не в последовательном) режиме, то есть для обработки все инструкции разделяются на два параллельных потока. Это позволяет одновременно обрабатывать два различных приложения или два различных потока одного приложения и тем самым увеличить количество инструкций, выполняемых процессором в секунду, что сказывается на росте его производительности.
В конструктивном плане процессор с поддержкой технологии Hyper-Threading состоит из двух логических процессоров, каждый из которых имеет свои регистры и контроллер прерываний. А значит, две параллельно исполняемые задачи работают со своими собственными независимыми регистрами и прерываниями, но при этом используют одни и те же ресурсы процессора для выполнения своих задач. После активизации каждый из логических процессоров может самостоятельно и независимо от другого процессора выполнять свою задачу, обрабатывать прерывания либо блокироваться. Таким образом, от реальной двухпроцессорной конфигурации новая технология отличается только тем, что оба логических процессора используют одни и те же исполняющие ресурсы, одну и ту же разделяемую между двумя потоками кэш-память и одну и ту же системную шину.
Использование двух логических процессоров позволяет усилить процесс параллелизма на уровне потока, реализованный в современных операционных системах и высокоэффективных приложениях. Команды от исполняемых параллельно потоков одновременно посылаются для обработки ядру процессора. Используя технологию out-of-order (исполнение командных инструкций не в порядке их поступления), ядро процессора способно параллельно обрабатывать оба потока за счѐт использования нескольких исполнительных модулей.
Идея технологии Hyper-Threading тесно связана с микроархитектурой NetBurst процессора Pentium 4 и является в каком-то смысле еѐ логическим продолжением. Микроархитектура Intel NetBurst позволяет получить максимальный выигрыш производительности при выполнении одиночного потока инструкций, то есть при выполнении одной задачи. Однако, даже в случае специальной оптимизации программы, не все исполнительные модули процессора оказываются задействованными на протяжении каждого тактового цикла. В среднем, при выполнении кода, типичного для набора команд IA-32, реально используется только 35% исполнительных ресурсов процессора, а 65% исполнительных ресурсов процессора простаивают, что означает неэффективное использование возможностей процессора. Было бы логично реализовать работу процессора таким образом, чтобы в каждом тактовом цикле максимально использовать его возможности. Именно эту идею и реализует технология Hyper-Threading, подключая незадействованные ресурсы процессора к выполнению параллельной задачи.