34. Конвейерная обработка данных
Выполнение каждой команды складывается из ряда последовательных этапов (шагов, стадий), суть которых не меняется от команды к команде. С целью увеличения быстродействия процессора и максимального использования всех его возможностей в современных микропроцессорах используется конвейерный принцип обработкиинформации. Этот принцип подразумевает, что в каждый момент времени процессор работает над различными стадиями выполнения нескольких команд, причем на выполнение каждой стадии выделяются отдельные аппаратные ресурсы. По очередному тактовому импульсу каждая команда вконвейерепродвигается на следующую стадию обработки, выполненная команда покидаетконвейер, а новая поступает в него.
Конвейеризация (или конвейерная обработка) в общем случае основана на разделении подлежащей исполнению функции на более мелкие части, называемые ступенями, и выделении для каждой из них отдельного блока аппаратуры. Производительность при этом возрастает благодаря тому, что одновременно на различных ступенях конвейера выполняются несколько команд. Конвейерная обработка такого рода широко применяется во всех современных быстродействующих процессорах. Выполнение типичной команды можно разделить на следующие этапы:
С 1 – выборка команды (по адресу, заданному счетчиком команд, из памяти извлекается команда и помещается в буфер);
С 2 – декодирование команды (определение КОП и типа операндов);
С 3 – выборка операндов (определение местонахождения операндов и вызов их из регистров);
С 4 – выполнение команды;
С 5 – запись результата в нужный регистр.
Работу конвейера можно условно представить в виде временной диаграммы на которой обычно изображаются выполняемые команды, номера тактов и этапы выполнения команд. В качестве примера рассмотрим конвейерную машину с пятью этапами выполнения операций, которые имеют длительность 50, 50, 60, 50 и 50 нс соответственно. Пусть накладные расходы на организацию конвейерной обработки составляют 5 нс. Тогда среднее время выполнения команды в не конвейерной машине будет равно 260 нс. Если же используется конвейерная организация, длительность такта будет равна длительности самого медленного этапа обработки плюс накладные расходы, т.е. 65 нс. Это время соответствует среднему времени выполнения команды в конвейере. Таким образом, ускорение, полученное в результате конвейеризации, будет равно отношению:
Среднее время выполнения команды в не конвейерном режиме:
——- = 4 Среднее время выполнения команды в конвейерном режиме: 65
Рис. 12.2 Диаграмма работы простейшего конвейера
Рис. 12.3 Эффект конвейеризации – четырехкратное ускорение
Мы уже упоминали, что параллелизм нижнего уровня реализуется на однопроцессорных машинах. Название однопроцессорные предполагает, что подобные архитектуры выполняют только один поток команд. Классическим примером однопроцессорной архитектуры является архитектура фон Неймана со строго последовательным выполнением команд. По мере развития вычислительной техники архитектура фон Неймана обогатилась сначала конвейером фаз операций, а затем многофункциональной обработкой и получила обобщенное название SISD. Оба вида средств низкоуровнего параллелизма впервые были введены в компьютерах Control Data 6600 и 7600 в начале 70-х годов и с тех пор применяются во всех компьютерах повышенного быстродействия. Наибольшее развитие идеи SISD-параллелизма получили в RISC-архитектурах.
Однако, при конвейерной обработке часто возникают конфликты, которые препятствуют выполнению очередной команды в предназначенном для нее такте. Конфликты могут иметь различное происхождение, но в целом их можно охарактеризовать как структурные, поуправлениюи поданным.
Структурные конфликтывозникают в том случае, когда аппаратные средства процессора не могут поддерживать все возможные комбинации команд в режиме одновременного выполнения с совмещением. Эту ситуацию можно было бы ликвидировать двумя способами. Первый предполагает увеличение временитактадо такой величины, которая позволила бы все этапы любой команды выполнять за одинтакт. Однако при этом существенно снижается эффект конвейерной обработки, так как все этапы всех команд будут выполняться значительно дольше, в то время как обычно несколькихтактовтребует выполнение лишь отдельных этапов очень небольшого количества команд. Второй способ предполагает использование таких аппаратных решений, которые позволили бы значительно снизить затраты времени на выполнение данного этапа (например, использовать матричные схемы умножения). Но это приведет к усложнению схемы процессора и невозможности реализации на этой БИС других, функционально более важных, узлов.
Наиболее эффективным методом снижения потерь от конфликтов по управлениюслужитпредсказание переходов. Суть данного метода заключается в том, что при выполнении команды условного перехода специальный блок микропроцессора определяет наиболее вероятное направление перехода, не дожидаясь формирования признаков, на основании анализа которых этот переход реализуется. Процессор начинает выбирать из памяти и выполнять команды по предсказанной ветви программы (так называемоеисполнение по предположению, или «спекулятивное» исполнение). Однако так как направление перехода может быть предсказано неверно, то получаемые результаты с целью обеспечения возможности их аннулирования не записываются в память или регистры (то есть для них не выполняется этапWB), а накапливаются в специальном буфере результатов. Если после формирования анализируемых признаков оказалось, что направление перехода выбрано верно, все полученные результаты переписываются из буфера по месту назначения, а выполнение программы продолжается в обычном порядке. Если направление перехода предсказано неверно, то буфер результатов очищается. Также очищается иконвейер, содержащий команды, находящиеся на разных этапах обработки, следующие за командой условного перехода. При этом аннулируются результаты всех уже выполненных этапов этих команд.Конвейерначинает загружаться с первой команды другой ветви программы. Так как конвейерная обработка эффективна при большом числе последовательно выполненных команд, то перезагрузка конвейера приводит к значительным потерям производительности. Поэтому вопросам эффективного предсказания направления ветвления разработчики всех микропроцессоров уделяют большое внимание.
Методы предсказания переходов делятся на статические и динамические. При использовании статических методов до выполнения программы для каждой команды условного перехода указывается направление наиболее вероятного ветвления. Это указание делается или программистом с помощью специальных средств, имеющихся в некоторых языках программирования, по опыту выполнения аналогичных программ либо результатам тестового выполнения программы, или программой-компилятором по заложенным в ней алгоритмам. Методы динамического прогнозирования учитывают направления переходов, реализовывавшиеся этой командой при выполнении программы. Например, подсчитывается количество переходов, выполненных ранее по тому или иному направлению, и на основании этого определяется направление перехода при следующем выполнении данной команды. В современных микропроцессорах вероятность правильного предсказания направления переходов достигает 90-95 %.
Конфликты по даннымвозникают в случаях, когда выполнение одной команды зависит от результата выполнения предыдущей команды. Устранениеконфликтов по даннымтиповWARиWAWдостигается путем отказа от неупорядоченного исполнения команд, но чаще всего путем введения буфера восстановления последовательности команд.
Источник
К порядку: правила создания конвейеров обработки данных
К 2020 году вы не могли не заметить, что миром правят данные. И, как только речь заходит о работе с ощутимыми объёмами, появляется необходимость в сложном многоэтапном конвейере обработки данных.
Сам по себе конвейер обработки данных — это комплект преобразований, которые требуется провести над входными данными. Сложен он, например, потому, что информация всегда поступает на вход конвейера в непроверенном и неструктурированном виде. А потребители хотят видеть её в лёгкой для понимания форме.
В наших приложениях Badoo и Bumble конвейеры принимают информацию из самых разных источников: генерируемых пользователями событий, баз данных и внешних систем. Естественно, без тщательного обслуживания конвейеры становятся хрупкими: выходят из строя, требуют ручного исправления данных или непрерывного наблюдения.
Я поделюсь несколькими простыми правилами, которые помогают нам в работе с преобразованием данных и, надеюсь, помогут и вам.
Правило наименьшего шага
Первое правило сформулировать легко: каждое отдельное взятое преобразование должно быть как можно проще и меньше.
Допустим, данные поступают на машину с POSIX-совместимой операционной системой. Каждая единица данных — это JSON-объект, и эти объекты собираются в большие файлы-пакеты, содержащие по одному JSON-объекту на строку. Пускай каждый такой пакет весит около 10 Гб.
Над пакетом надо произвести три преобразования:
Проверить ключи и значения каждого объекта.
Применить к каждому объекту первую трансформацию (скажем, изменить схему объекта).
Применить вторую трансформацию (внести новые данные).
Совершенно естественно всё это делать с помощью единственного скрипта на Python:
Блок-схема такого конвейера не выглядит сложной:
Проверка объектов в transform.py занимает около 10% времени, первое преобразование — 70%, на остальное уходит 20% времени.
Теперь представим, что ваш стартап вырос и вам уже приходится обрабатывать сотни, а то и тысячи пакетов. И тут вы обнаружили, что в финальный этап логики обработки данных (занимающий 20% времени) закралась ошибка, — и вам нужно всё выполнить заново.
В такой ситуации рекомендуется собирать конвейеры из как можно более мелких этапов:
Блок-схема превращается в симпатичный паровозик:
конкретные преобразования проще понять;
каждый этап можно протестировать отдельно;
промежуточные результаты отлично кешируются;
систему легко дополнить механизмами обработки ошибок;
преобразования можно использовать и в других конвейерах.
Правило атомарности
К правилу наименьшего шага прилагается второе — правило атомарности. Оно звучит так: каждый шаг-преобразование либо должен случиться, либо нет. Никаких промежуточных состояний данных быть не должно.
Давайте вернёмся к первому примеру. Есть входные данные, над которыми мы проводим преобразование:
Что будет, если в процессе работы скрипт упадёт? Выходной файл будет повреждён. Или, что ещё хуже, данные окажутся преобразованы лишь частично, а следующие этапы конвейера об этом не узнают. Тогда на выходе вы получите лишь частичные данные. Это плохо.
В идеале данные должны быть в одном из двух состояний: готовые к преобразованию или уже преобразованные. Это называется атомарностью: данные либо переходят в следующее правильное состояние, либо нет:
Если какие-то этапы конвейера расположены в транзакционной базе данных, то атомарность легко достигается использованием транзакций. Если вы можете использовать такую базу данных, то не пренебрегайте этой возможностью.
В POSIX-совместимых файловых системах всегда есть атомарные операции (скажем, mv или ln), с помощью которых можно имитировать транзакции:
В этом примере испорченные промежуточные данные окажутся в файле *.tmp, который можно изучить позднее при проведении отладки или просто удалить.
Обратите внимание, как хорошо это правило сочетается с правилом наименьшего шага, ведь маленькие этапы гораздо легче сделать атомарными.
Правило идемпотентности
В императивном программировании подпрограмма с побочными эффектами является идемпотентной, если состояние системы не меняется после одного или нескольких вызовов.
Наше третье правило более тонкое: применение преобразования к одним и тем же данным один или несколько раз должно давать одинаковый результат.
Повторюсь: если вы дважды прогоните пакет через какой-то этап, результаты должны быть одинаковы. Если прогоните десять раз, результаты тоже не должны различаться. Давайте скорректируем наш пример, чтобы проиллюстрировать эту идею:
На входе у нас /input/batch.json, а на выходе — /output/batch.json. И вне зависимости от того, сколько раз мы применим преобразование, мы должны получить одни и те же данные:
Так что если только transform.py не зависит от каких-то неявных входных данных, этап transform.py является идемпотентным (своего рода перезапускаемым).
Обратите внимание, что неявные входные данные могут проявиться самым неожиданным образом. Если вы слышали про детерминированную компиляцию, то главные подозреваемые вам известны: временные метки, пути в файловой системе и другие разновидности скрытого глобального состояния.
Чем важна идемпотентность? В первую очередь это свойство упрощает обслуживание конвейера. Оно позволяет легко перезагружать подмножества данных после изменений в transform.py или входных данных в /input/batch.json. Информация будет идти по тем же маршрутам, попадёт в те же таблицы базы данных, окажется в тех же файлах и т. д.
Но помните, что некоторые этапы в конвейерах по определению не могут быть идемпотентными. Например, очистка внешнего буфера. Однако, конечно же, подобные процедуры всё равно должны оставаться маленькими™ и атомарными™.
Правило избыточности
Четвёртое правило: насколько возможно откладывайте удаление промежуточных данных. Зачастую это подразумевает использование дешёвого, медленного, но ёмкого хранилища для входных данных:
Сохраняйте сырые (input/batch.json) и промежуточные (/tmp/batch-1.json, /tmp/batch-2.json, /tmp/batch-3.json) данные как можно дольше — по меньшей мере до завершения цикла работы конвейера.
Вы скажете мне спасибо, когда аналитики решат поменять алгоритм вычисления какой-то метрики в transform3.py и вам придётся исправлять данные за несколько месяцев.
Другими словами: избыточность избыточных данных — ваш лучший избыточный друг.
Заключение
Давайте подведём итоги:
разбивайте конвейер на изолированные маленькие этапы;
стремитесь делать этапы атомарными и идемпотентными;
сохраняйте избыточность данных (в разумных пределах).
Так обрабатываем данные и мы в Badoo и Bumble: они приходят через сотни тщательно подготовленных этапов преобразований, 99% из которых атомарные, небольшие и идемпотентные. Мы можем позволить себе изрядную избыточность, поэтому держим данные в больших холодном и горячем хранилищах, а между отдельными ключевыми преобразованиями имеем и сверхгорячий промежуточный кеш.
Оглядываясь назад, могу сказать, что эти правила выглядят очевидными. Возможно, вы даже интуитивно уже следуете им. Но понимание лежащих в их основе причин помогает видеть границы применимости этих правил и выходить за них при необходимости.
А у вас есть свои правила обработки данных?
Источник
