Параллельные вычислительные системы

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Параллельные вычислительные системы — физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.[1]

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

Идея распараллеливания вычислений основана на том, что большинство задач может быть разделено на набор меньших задач, которые могут быть решены одновременно. Обычно параллельные вычисления требуют координации действий. Параллельные вычисления существуют в нескольких формах: параллелизм на уровне битов, параллелизм на уровне инструкций, параллелизм данных, параллелизм задач. Параллельные вычисления использовались много лет в основном в высокопроизводительных вычислениях, но в последнее время к ним возрос интерес вследствие существования физических ограничений на рост тактовой частоты процессоров. Параллельные вычисления стали доминирующей парадигмой в архитектуре компьютеров, в основном в форме многоядерных процессоров.[2]

Писать программы для параллельных систем сложнее, чем для последовательных[3], так как конкуренция за ресурсы представляет новый класс потенциальных ошибок в программном обеспечении (багов), среди которых состояние гонки является самой распространённой. Взаимодействие и синхронизация между процессами представляют большой барьер для получения высокой производительности параллельных систем. В последние годы также стали рассматривать вопрос о потреблении электроэнергии параллельными компьютерами.[4] Характер увеличения скорости программы в результате распараллеливания объясняется законами Амдала и Густавсона.

Типы параллелизма

[править | править код]

Параллелизм на уровне битов

[править | править код]

Эта форма параллелизма основана на увеличении размера машинного слова. Увеличение размера машинного слова уменьшает количество операций, необходимых процессору для выполнения действий над переменными, чей размер превышает размер машинного слова. К примеру: на 8-битном процессоре нужно сложить два 16-битных целых числа. Для этого вначале нужно сложить младшие 8 бит чисел, затем сложить старшие 8 бит и к результату их сложения прибавить значение флага переноса. Итого 3 инструкции. С 16-битным процессором можно выполнить эту операцию одной инструкцией.

Исторически 4-битные микропроцессоры были заменены 8-битными, затем появились 16-битные и 32-битные. 32-битные процессоры долгое время были стандартом в повседневных вычислениях. С появлением технологии x86-64 для этих целей стали использовать 64-битные процессоры.

Параллелизм на уровне инструкций

[править | править код]

Компьютерная программа — это, по существу, поток инструкций, выполняемых процессором. Но можно изменить порядок этих инструкций, распределить их по группам, которые будут выполняться параллельно, без изменения результата работы всей программы. Данный приём известен как параллелизм на уровне инструкций. Продвижения в развитии параллелизма на уровне инструкций в архитектуре компьютеров происходили с середины 1980-х до середины 1990-х.

Классический пример пятиступенчатого конвейера на RISC-машине (IF = выборка инструкции, ID = декодирование инструкции, EX = выполнение инструкции, MEM = доступ к памяти, WB = запись результата в регистры).

Современные процессоры имеют многоступенчатый конвейер команд. Каждой ступени конвейера соответствует определённое действие, выполняемое процессором в этой инструкции на этом этапе. Процессор с N ступенями конвейера может иметь одновременно до N различных инструкций на разном уровне законченности. Классический пример процессора с конвейером — это RISC-процессор с 5-ю ступенями: выборка инструкции из памяти (IF), декодирование инструкции (ID), выполнение инструкции (EX), доступ к памяти (MEM), запись результата в регистры (WB). Процессор Pentium 4 имеет конвейер в 31 ступень[5].

Пятиступенчатый конвейер суперскалярного процессора, способный выполнять две инструкции за цикл. Может иметь по две инструкции на каждой ступени конвейера, максимум 10 инструкций могут выполняться одновременно.

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

Параллелизм данных

[править | править код]

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

Параллелизм задач

[править | править код]

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

Распределённые операционные системы

[править | править код]

Распределённая ОС, динамически и автоматически распределяя работы по различным машинам системы для обработки, заставляет набор сетевых машин обрабатывать информацию параллельно. Пользователь распределённой ОС, вообще говоря, не имеет сведений о том, на какой машине выполняется его работа.[6]

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

Работы в направлении создания параллельных вычислительных систем в США и СССР велись интенсивно с 1960-х гг. Разработкой технологии параллельной обработки данных и созданием параллельных электронно-вычислительных систем в Соединённых Штатах по заказу Агентства по перспективным оборонным научно-исследовательским разработкам США занимались исследовательские подразделения компаний и университетов:[7]

Руководство за ходом работ осуществлялось бюро вычислительных расчётов и обработки информации АРПА в Пентагоне, Виргиния, и Научно-исследовательским центром ВВС США в Роме, Нью-Йорк.

В Советском Союзе работы аналогичного характера велись учреждениями в структуре Государственного комитета по радиоэлектронике (позже преобразованного в Министерство радиопромышленности), Министерства обороны и Академии наук СССР:[8]

Биологический мозг как массово-параллельная вычислительная машина

[править | править код]

В начале 1970-х годов в Лаборатории искусственного интеллекта Массачусетского технологического университета Марвин Минский и Сеймур Пейперт начали разрабатывать теорию, названную ими «Обществом Разума», которая рассматривает биологический мозг как массово-параллельную вычислительную машину. В 1986 году Минский опубликовал популярную книгу «Общество Разума», в которой утверждает, что «разум мозга формируется из многих маленьких агентов, не имеющих разума сами по себе».[9] Теория попыталась объяснить, как то, что мы называем интеллектом, может быть продуктом взаимодействия простых частей, называемых агентами, которые сами являются неразумными. Минский утверждал, что самым большим источником идей о теории «общества разума» была его работа в попытке создать машину, которая собирала бы детские блоки, используя роботизированную руку, видеокамеру и компьютер.[10] Книга о теории «Общество Разума» была написана для широкой публики, в отличие от большинства ранее опубликованных работ Минского.

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

Примечания

[править | править код]
  1. Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.
  2. Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley Архивная копия от 29 февраля 2008 на Wayback Machine. University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. 18 декабря 2006: «Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance… Even representatives from Intel, a company generally associated with the „higher clock-speed is better“ position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit.»
  3. David A. Patterson and John L. Hennessy. Computer Organization and Design (Second Edition) Morgan Kaufmann Publishers, 1998. ISBN 1-55860-428-6, pg 715
  4. Asanovic et al: Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are «free».
  5. НОУ ИНТУИТ | Лекция | Конвейерная организация работы микропроцессора. Дата обращения: 27 июня 2017. Архивировано 28 мая 2017 года.
  6. Эндрю Таненбаум, Мартин ван Стеен. Распределенные системы. Принципы и парадигмы = Andrew S. Tanenbaum, Maarten van Steen. "Destributed systems. Principles and paradigms". — Санкт-Петербург: Питер, 2003. — 877 с. — (Классика computer science). — ISBN 5-272-00053-6.
  7. Statement of Dr. Stephen J. Lukasik, Director, Advanced Research Projects Agency. / Department of Defense Appropriations for Fiscal Year 1972. — April 30, 1971. — P. 741 — 1090 p.
  8. Тихонов С. Г. Оборонные предприятия СССР и России : в 2 т. — М. : ТОМ, 2010. — Т. 2. — С. 47-48, 82-83. — 608 с. — 1000 экз. — ISBN 978-5-903603-03-9.
  9. Minsky, Marvin. The Society of Mind (неопр.). — New York: Simon & Schuster, 1986. — С. 17. — ISBN 0-671-60740-5.
  10. Minsky, Marvin. The Society of Mind (неопр.). — New York: Simon & Schuster, 1986. — С. 29. — ISBN 0-671-60740-5.
  11. Blakeslee, Thomas[англ.]. Beyond the Conscious Mind. Unlocking the Secrets of the Self (англ.). — 1996. — P. 6—7.
  12. Gazzaniga, Michael; LeDoux, Joseph[англ.]. The Integrated Mind (неопр.). — 1978. — С. 132—161.
  13. Gazzaniga, Michael. The Social Brain. Discovering the Networks of the Mind (англ.). — 1985. — P. 77—79.
  14. Ornstein, Robert[англ.]. Evolution of Consciousness: The Origins of the Way We Think (англ.). — 1992. — P. 2.
  15. Hilgard, Ernest[англ.]. Divided consciousness: multiple controls in human thought and action (англ.). — New York: Wiley, 1977. — ISBN 978-0-471-39602-4.
  16. Hilgard, Ernest[англ.]. Divided consciousness: multiple controls in human thought and action (expanded edition) (англ.). — New York: Wiley, 1986. — ISBN 0-471-80572-6.
  17. Kaku, Michio. The Future of the Mind: The Scientific Quest to Understand, Enhance, and Empower the Mind (англ.). — 2014.
  18. Успенский, Пётр. Глава 3 // В Поисках Чудесного. Фрагменты Неизвестного Учения. — 1992. — С. 72—83.
  19. Официальный сайт Нейрокластерной Модели Мозга. Дата обращения: 22 июля 2017. Архивировано 21 июля 2017 года.