В вычислительной технике конвейер , также известный как конвейер данных , представляет собой набор элементов обработки данных , соединенных последовательно, где выход одного элемента является входом следующего. Элементы конвейера часто выполняются параллельно или в режиме временных срезов. Некоторое количество буферного хранилища часто вставляется между элементами.
Конвейеризация — это широко используемая концепция в повседневной жизни. Например, на сборочной линии автомобильного завода каждая конкретная задача, такая как установка двигателя, установка капота и установка колес, часто выполняется отдельной рабочей станцией. Станции выполняют свои задачи параллельно, каждая на отдельном автомобиле. После того, как автомобиль выполнил одну задачу, он перемещается на следующую станцию. Изменения во времени, необходимом для выполнения задач, можно компенсировать с помощью «буферизации» (удержания одного или нескольких автомобилей в пространстве между станциями) и/или «застревания» (временной остановки станций выше по потоку) до тех пор, пока не станет доступна следующая станция.
Предположим, что сборка одного автомобиля требует трех задач, которые занимают 20, 10 и 15 минут соответственно. Тогда, если бы все три задачи выполнялись одной станцией, завод выпускал бы один автомобиль каждые 45 минут. Используя конвейер из трех станций, завод выпускал бы первый автомобиль за 45 минут, а затем новый каждые 20 минут.
Как показывает этот пример, конвейеризация не уменьшает задержку , то есть общее время прохождения одного элемента через всю систему. Однако она увеличивает пропускную способность системы , то есть скорость, с которой обрабатываются новые элементы после первого.
В вычислительной технике конвейер или конвейер данных [1] — это набор элементов обработки данных , соединенных последовательно, где выход одного элемента является входом следующего. Элементы конвейера часто выполняются параллельно или в режиме временных срезов. Некоторое количество буферного хранилища часто вставляется между элементами.
Конвейеры, связанные с компьютерами, включают:
Поскольку пропускная способность конвейера не может быть выше, чем у его самого медленного элемента, проектировщик должен попытаться разделить работу и ресурсы между этапами так, чтобы все они тратили одинаковое время на выполнение своих задач. В приведенном выше примере сборки автомобиля, если бы три задачи заняли по 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 будет неверным.
Для того, чтобы правильно обрабатывать такие конфликты, конвейер должен быть снабжен дополнительной схемой или логикой, которая обнаруживает их и предпринимает соответствующие действия. Стратегии для этого включают:
Для эффективной реализации конвейерам данных требуется стратегия планирования ЦП для распределения работы по доступным ядрам ЦП и использование структур данных , на которых будут работать этапы конвейера. Например, производные UNIX могут конвейеризировать команды, соединяющие стандартный ввод-вывод различных процессов, используя конвейеры, реализованные операционной системой. Некоторые операционные системы [ требуется пример ] могут предоставлять синтаксис , подобный UNIX, для объединения нескольких программных запусков в конвейер, но реализовывать последний как простое последовательное выполнение, а не как настоящую конвейеризацию, а именно, ожидая завершения каждой программы перед запуском следующей. [ требуется цитата ]
Подходы более низкого уровня могут полагаться на потоки, предоставляемые операционной системой для планирования работы на этапах: обе реализации, основанные на пуле потоков , или на одном потоке на этап, являются жизнеспособными и существуют. [3]
Существуют и другие стратегии, основанные на кооперативной многозадачности , которым не нужны несколько потоков выполнения и, следовательно, дополнительные ядра ЦП, например, использование циклического планировщика с фреймворком на основе сопрограмм. В этом контексте каждый этап может быть инстанцирован собственной сопрограммой, возвращая управление планировщику после завершения своей циклической задачи. Этот подход может потребовать тщательного контроля над этапами процесса, чтобы они не злоупотребляли своим временным срезом.
Конвейерная система обычно требует больше ресурсов (элементов схемы, процессоров, памяти компьютера и т. д.), чем та, которая выполняет одну партию за раз, поскольку ее этапы не могут совместно использовать эти ресурсы, а также поскольку между элементами может потребоваться буферизация и дополнительная логика синхронизации.
Более того, передача элементов между отдельными элементами обработки может увеличить задержку, особенно для длинных конвейеров.
Дополнительные затраты на сложность конвейеризации могут быть значительными, если между обработкой различных элементов существуют зависимости, особенно если для их обработки используется стратегия «угадай и вернись». Действительно, затраты на реализацию этой стратегии для сложных наборов инструкций побудили некоторые радикальные предложения по упрощению архитектуры компьютера , такие как RISC и VLIW . Компиляторы также были обременены задачей переупорядочивания машинных инструкций для повышения производительности конвейеров инструкций.
Действительно, в последние годы требования к приложениям и их базовому оборудованию были значительными. Например, создание конвейеров с приложениями с одним узлом, которые прочесывают данные строка за строкой, больше не представляется возможным из-за объема и разнообразия больших данных . Однако с появлением аналитических движков данных, таких как Hadoop или, совсем недавно, Apache Spark , стало возможным распределять большие наборы данных по нескольким узлам обработки, что позволяет приложениям достигать высот эффективности в несколько сотен раз больше, чем считалось возможным ранее. Эффект этого сегодня заключается в том, что даже ПК среднего уровня, использующий распределенную обработку таким образом, может справиться с созданием и запуском конвейеров больших данных. [4]