Параллелизм и конвейеризация вычислений

1. Параллелизм и конвейеризация вычислений

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

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

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

Проблемы распараллеливания:

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

Решение вопросов взаимодействия параллельных процессоров (например, обмен с памятью, межпроцессорный обмен, синхронизация и др.)

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

Конвейеризация вычислений - разбиение вычислений на последовательные этапы с целью реализации этих этапов на отдельных ступенях конвейера для повышения производительности.

Конвейер - устройство, состоящее из N последовательно соединенных частей

(ступеней конвейера), каждая из которых выполняет очередной шаг вычислений за время t (такт конвейера).

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

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

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

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

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

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

Конвейеризация вычислений - разбиение вычислений на последовательные этапы с целью реализации этих этапов на отдельных ступенях конвейера для повышения производительности.

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

Билет №31

Полусумматор

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

Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды двоичного числа, при этом результатом будут два бита S,C, где S — это бит суммы по модулю, а C — бит переноса.

Однако, как можно заметить, для построения схемы двоичного сумматора (трёхразрядный сумматор, тринарный сумматор) необходимо иметь элемент, который суммирует три бита A, B и C, где C — бит переноса из предыдущего разряда, таким элементом является полный двоичный сумматор, который как правило состоит из двух полусумматоров и логического элемента 2ИЛИ.

Двоичный полусумматор

Представляет собой объединение двух бинарных (двухоперандных) двоичных логических функций: сумма по модулю два - S и разряд переноса при двоичном сложении - C.

Троичный полусумматор

Троичный полусумматор представляет собой объединение двух троичных бинарных логических функций - «сложение по модулю 3» и «разряд переноса при троичном сложении». Так как существуют две троичных системы счисления - несимметричная, в которой в разряде переноса не бывает значения больше "1" и симметричная (Фибоначчи), в которой в разряде переноса возможны все три состояния трита, и, как минимум, три физических реализации троичных систем - трёхуровневая однопроводная, двухуровневая двухпроводная (BCT) и двухуровневая трёхбитная одноединичная, то и троичных полусумматоров может быть большое множество.

SISD и SIMD системы.

SISD (англ. Single Instruction, Single Data) или ОКОД (Одиночный поток Команд, Одиночный поток Данных) — архитектура компьютера, в которой один процессор выполняет один поток команд, оперируя одним потоком данных. Относится к фон-Неймановской архитектуре.

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

SIMD (англ. single instruction, multiple data — одиночный поток команд, множественный поток данных, ОКМД) — принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных.

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

Билет №32

Четвертьсумматор.

Простейшим двоичным суммирующим элементом является четверть сумматор. Происхождение названия этого элемента следует из того, что он имеет в два раза меньше выходов и в два раза меньше строк в таблице истинности по сравнению с полным двоичным одноразрядным сумматором. Наиболее известны для данной схемы названия: элемент “сумма по модулю 2” и элемент “исключающее ИЛИ”. Имеет два входа а и b для двух слагаемых и один выход S для суммы.

MISD и MIMD системы.

MISD-Архитектура (англ. Multiple Instruction stream, Single Data stream, Множественный поток Команд, Одиночный поток Данных, МКОД) — тип архитектуры параллельных вычислений, где несколько функциональных модулей (два или более) выполняют различные операции над одними данными.

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

Было создано немного ЭВМ с MISD-архитектурой, поскольку MIMD и SIMD чаще всего являются более подходящими для общих методик параллельных данных. Они обеспечивают лучшее масштабирование и использование вычислительных ресурсов, чем архитектура MISD.

MIMD (англ. Multiple Instruction stream, Multiple Data stream — Множественный поток Команд, Множественный поток Данных, сокращённо МКМД) — концепция архитектуры компьютера, используемая для достижения параллелизма вычислений.

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

MIMD-архитектуры могут быть использованы в целом ряде областей, таких как системы автоматизированного проектирования / автоматизированное производство, моделирование, а также комуникатор связей (communication switches).

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

Поиск по сайту: