stringtranslate.com

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

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

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

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

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

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

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

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

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

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

Поскольку пропускная способность конвейера не может быть лучше, чем у его самого медленного элемента, проектировщику следует постараться разделить работу и ресурсы между этапами так, чтобы все они тратили одинаковое время на выполнение своих задач. В приведенном выше примере сборки автомобиля, если каждая из трех задач занимала по 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 будет неверным.

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  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 г.

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