Конвейер (вычисления)

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

Концепция и мотивация

Конвейерная обработка — широко используемая концепция в повседневной жизни. Например, на сборочной линии автомобильного завода каждая конкретная задача, такая как установка двигателя, установка капота и установка колес, часто выполняется на отдельной рабочей станции. Станции выполняют свои задачи параллельно, каждая на своем автомобиле. Как только машина выполнила одну задачу, она движется к следующей станции. Изменения во времени, необходимом для выполнения задач, можно компенсировать путем «буферизации» (удержания одного или нескольких автомобилей в пространстве между станциями) и/или «остановки» (временной остановки вышестоящих станций) до тех пор, пока не станет доступной следующая станция. .

Предположим, что для сборки одной машины требуется три задачи, которые занимают 20, 10 и 15 минут соответственно. Тогда, если бы все три задачи выполнялись на одной станции, завод выпускал бы по одной машине каждые 45 минут. Используя конвейер из трех станций, завод будет выпускать первый автомобиль за 45 минут, а затем каждые 20 минут — новый.

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

В вычислительной технике

В вычислениях — конвейер или конвейер данных. ^{[ 1 ]} представляет собой набор элементов обработки данных , соединенных последовательно, где выход одного элемента является входом следующего. Элементы конвейера часто выполняются параллельно или с разделением по времени. некоторый объем буферной памяти Между элементами часто вставляется .

Конвейеры, связанные с компьютером, включают в себя:

Конвейеры инструкций , такие как классический конвейер RISC , которые используются в центральных процессорах (ЦП) и других микропроцессорах , чтобы обеспечить перекрытие выполнения нескольких инструкций с помощью одной и той же схемы . Схема обычно делится на этапы, и каждый этап обрабатывает определенную часть одной инструкции за раз, передавая частичные результаты на следующий этап. Примерами этапов являются декодирование инструкций, арифметика/логика и выборка регистров. Они связаны с технологиями суперскалярного выполнения , пересылки операндов , спекулятивного исполнения и исполнения вне порядка .
Графические конвейеры , присутствующие в большинстве графических процессоров (GPU), которые состоят из нескольких арифметических блоков или полных процессоров , которые реализуют различные этапы общих операций рендеринга ( перспективная проекция окна , обрезка , расчет цвета и освещения , рендеринг и т. д.). .
Программные конвейеры , которые состоят из последовательности вычислительных процессов (команд, запусков программ, задач, потоков, процедур и т. д.), концептуально выполняемых параллельно, при этом выходной поток одного процесса автоматически подается в качестве входного потока следующего. . Канал Unix системных вызовов является классическим примером этой концепции.
Конвейерная обработка HTTP — метод выдачи нескольких HTTP- запросов через одно и то же TCP-соединение без ожидания завершения предыдущего перед выдачей нового.

Рекомендации по проектированию

Балансировка этапов

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

Буферизация

В идеальных обстоятельствах, если все обрабатывающие элементы синхронизированы и обработка занимает одинаковое количество времени, то каждый элемент может быть получен каждым элементом так же, как он освобожден предыдущим, за один такт . Таким образом, предметы будут течь по трубопроводу с постоянной скоростью, как волны в водном канале. В таких «волновых трубопроводах» ^{[ 2 ]} между этапами не требуется никакой синхронизации или буферизации, кроме хранилища, необходимого для элементов данных.

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

Буфер между двумя каскадами может представлять собой просто аппаратный регистр с подходящей логикой синхронизации и сигнализации между двумя каскадами. Когда этап A сохраняет элемент данных в регистре, он отправляет сигнал «данные доступны» следующему этапу B. Как только B использует эти данные, он отвечает сигналом «данные получены» на A. Этап A останавливается в ожидании для этого сигнала перед сохранением следующего элемента данных в регистр. Этап B останавливается в ожидании сигнала «данные доступны», если он готов обработать следующий элемент, но этап A еще не предоставил его.

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

Нелинейные трубопроводы

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

Зависимости между элементами

В некоторых приложениях обработка элемента Y на этапе A может зависеть от результатов или эффекта обработки предыдущего элемента X на каком-либо более позднем этапе B конвейера. В этом случае этап A не сможет правильно обработать элемент Y, пока элемент X не пройдет этап B.

Такая ситуация очень часто возникает в конвейерах команд. Например, предположим, что Y — арифметическая инструкция, считывающая содержимое регистра, который должен был быть изменен более ранней инструкцией X. Пусть A — этап, на котором извлекаются операнды инструкции , а B — этап, на котором записывается результат. в указанный реестр. Если этап A попытается обработать инструкцию Y до того, как инструкция X достигнет этапа B, регистр все еще может содержать старое значение, и эффект Y будет неверным.

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

Остановка: каждый затронутый этап, например A, останавливается до тех пор, пока зависимость не будет устранена, то есть до тех пор, пока не станет доступна необходимая информация и/или не будет достигнуто требуемое состояние.
Изменение порядка элементов: вместо того, чтобы останавливаться, этап A может отложить элемент Y в сторону и искать любой последующий элемент Z в своем входном потоке, который не имеет каких-либо ожидающих зависимостей с каким-либо более ранним элементом. В конвейерах команд этот метод называется выполнением вне порядка .
Угадай и вернись. Одним из важных примеров зависимости между элементами является обработка инструкции условного перехода X конвейером команд. Первый этап A конвейера, который выбирает следующую инструкцию Y для выполнения, не может выполнить свою задачу до тех пор, пока X не получит свой операнд и не определит, следует ли переходить к переходу или нет. Это может занять много тактов, поскольку операнд X, в свою очередь, может зависеть от предыдущих инструкций, извлекающих данные из основной памяти.

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

Типичные реализации программного обеспечения

Для эффективной реализации конвейерам данных необходима стратегия планирования ЦП для распределения работы по доступным ядрам ЦП и использования структур данных , на которых будут работать этапы конвейера. Например, производные UNIX могут конвейеризировать команды, соединяющие стандартный ввод-вывод различных процессов, используя каналы, реализованные операционной системой. Некоторые операционные системы ^{[ нужен пример ]} может предоставить UNIX-подобный синтаксис для объединения нескольких запусков программы в конвейер, но реализовать последнее как простое последовательное выполнение, а не как настоящую конвейерную обработку, а именно, ожидая завершения каждой программы перед запуском следующей. ^{[ нужна ссылка ]}

Подходы более низкого уровня могут полагаться на потоки, предоставляемые операционной системой для планирования работы на этапах: реализации на основе пула потоков или реализация одного потока на этап жизнеспособны и существуют. ^{[ 3 ]}

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

Затраты и недостатки

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

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

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

Новые технологии

Это правда, что в последние годы требования к приложениям и их аппаратному обеспечению были значительными. Например, создание конвейеров с приложениями с одним узлом, которые просматривают данные строка за строкой, больше не представляется возможным с учетом объема и разнообразия больших данных . Однако с появлением механизмов анализа данных, таких как Hadoop или, в последнее время, Apache Spark , стало возможным распределять большие наборы данных по нескольким узлам обработки, что позволяет приложениям достигать высот эффективности, в несколько сотен раз превышающих то, что считалось возможным раньше. Результатом этого сегодня является то, что даже ПК среднего уровня, использующие распределенную обработку таким образом, могут справиться с созданием и запуском конвейеров больших данных. ^{[ 4 ]}

См. также

Ссылки

^ Разработка конвейера данных. Архивировано 24 мая 2018 г. на Wayback Machine. Опубликовано Dativa, получено 24 мая 2018 г.
^ О. Хаук; Сорин А. Хусс; М. Гарг (1999). «Двухфазные асинхронные волновые конвейеры и их применение в 2D-DCT». Слушания. Пятый международный симпозиум по перспективным исследованиям в области асинхронных цепей и систем . стр. 219–228. дои : 10.1109/ASYNC.1999.761536 . ISBN 0-7695-0031-5 . S2CID 206515615 .
^ «МДПТ» . Гитхаб . Сентябрь 2022 г.
^ Что такое конвейер данных? Опубликовано Data Pipelines, получено 11 марта 2021 г.

Библиография

Перес Гарсия, Пабло (2018). Pipeline DSL и dsl для создания конвейера CI/CD для ваших проектов . Аддисон-Уэсли. ISBN 978-0-134-69147-3 .
Стандартное обсуждение конвейерной обработки в параллельных вычислениях см. Куинн, Майкл Дж. (2004). Параллельное программирование на C с использованием MPI и openMP . Дубьюк, Айова: McGraw-Hill Professional. ISBN 0072822562 .
Погоньи, Роланд (февраль 2021 г.). «Что такое конвейер данных?» . Проверено 11 марта 2021 г.

[1] Разработка конвейера данных. Архивировано 24 мая 2018 г. на Wayback Machine. Опубликовано Dativa, получено 24 мая 2018 г.

[2] О. Хаук; Сорин А. Хусс; М. Гарг (1999). «Двухфазные асинхронные волновые конвейеры и их применение в 2D-DCT». Слушания. Пятый международный симпозиум по перспективным исследованиям в области асинхронных цепей и систем . стр. 219–228. дои : 10.1109/ASYNC.1999.761536 . ISBN 0-7695-0031-5 . S2CID 206515615 .

[3] «МДПТ» . Гитхаб . Сентябрь 2022 г.

[4] Что такое конвейер данных? Опубликовано Data Pipelines, получено 11 марта 2021 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]