Оптимизация сортировки в устройствах Edge Computing для более быстрой обработки данных
Краевычислительные устройства все более важны для обработки данных, близких к источнику, снижения задержки и использования полосы пропускания. Одним из ключевых факторов повышения их производительности является оптимизация алгоритмов сортировки, используемых в этих устройствах. Более быстрая сортировка приводит к более быстрому анализу данных и принятию решений, что важно для таких приложений, как автономные транспортные средства, датчики IoT и аналитика в реальном времени. В то время как сортировка является хорошо изученной проблемой в информатике, граничные среды накладывают уникальные ограничения - ограниченная память, более низкие тактовые частоты и работа с батарейным питанием - что делает выбор алгоритмов и оптимизацию критически важной инженерной задачей. В этой статье рассматривается важность эффективной сортировки на грани, обзор общих алгоритмов с акцентом на их пригодность для ограниченного ресурсом оборудования и представлены действенные стратегии для ускорения сортировки, включая аппаратную разгрузку и адаптивные методы.
Важность эффективной сортировки в устройствах Edge
Эффективная сортировка данных имеет решающее значение, поскольку она напрямую влияет на скорость обработки данных. В периферийных устройствах, где ресурсы, такие как мощность процессора и память, ограничены, выбор правильного метода сортировки может иметь существенное значение. Эффективная сортировка уменьшает время обработки, сохраняет энергию и улучшает общую отзывчивость системы. Например, система LiDAR автономного транспортного средства должна сортировать измерения расстояния, чтобы идентифицировать препятствия в миллисекундах; задержка сортировки может привести к столкновению. Аналогичным образом, промышленный датчик IoT, который собирает показания температуры от сотен узлов, нуждается в сортировке с низкой задержкой, чтобы вызвать тревогу до того, как будут нарушены пороги. В облачных средах сортировка может использовать обширные кластеры серверов и высокоскоростные межсоединения, но периферийные устройства могут работать с микроконтроллерами или системами на чипах (SoC), которые имеют только килобайты до нескольких мегабайт оперативной памяти и работают на частотах ниже 2 ГГц. Это несоответствие означает, что алгоритм, который эффективно работает на сервере, может вызвать трэш памяти
Алгоритмы сортировки, используемые в Edge Computing
Выбор правильного алгоритма зависит от характеристик данных и аппаратных ограничений. Ниже мы рассмотрим четыре широко используемых алгоритма сортировки, их типичные профили производительности и конкретные соображения для развертывания края.
Быстрый сорт
Quick sort славится своей средней сложностью времени O(n log n) и разделением на месте, что делает его память эффективной. В периферийных устройствах опора быстрого сорта на рекурсию может быть проблематичной, потому что каждый рекурсивный вызов потребляет пространство стека. На микроконтроллерах с ограниченной глубиной стека (до 512 байт в некоторых процессорах ARM Cortex-M) глубокая рекурсия может вызвать переполнение стека. Однако итеративные реализации быстрого сортирования, используя явный стек, могут смягчить это. Кроме того, выбор поворота должен быть надежным, чтобы избежать худшего случая O(n2) поведения. Случайный поворот или медиана из трех стратегий помогают, но они вводят дополнительные циклы процессора. На практике быстрый сорт является сильным кандидатом для наборов данных, которые полностью подходят для ОЗУ, но тщательная настройка глубины рекурсии и выбор поворота необходим для краевых систем.
Сортировка слияний
Сортировка слияний обеспечивает стабильную сортировку и согласованную производительность O(n log n) независимо от распределения входов. Его основным недостатком является необходимость дополнительной памяти, пропорциональной размеру входа (O(n) вспомогательное пространство). Для краевых устройств с ограниченным бюджетом памяти это может быть запретительным. Однако в сценариях, где данные хранятся в связанных структурах (например, связанные списки или дескрипторы файлов), сортировка слияний может выполняться без случайного доступа, что выгодно для некоторых потоков данных датчиков. Гибридные подходы, такие как timsort (используемый в сортировке Python), сочетают сорт слияний с сортировкой вставок для небольших прогонов, уменьшая накладные расходы памяти. Для краевых систем, которые могут сэкономить около 50% дополнительной памяти, сорт слияния обеспечивает предсказуемое поведение, которое бесценно для планирования в реальном времени.
Сорт кулака
Сортировка кучи - это алгоритм на месте с O(n log n) наихудшей сложностью времени и O(1) дополнительным пространством. Он избегает рекурсии, делая его стек-дружественным. Компромисс заключается в том, что сорт кучи не стабилен, а его постоянные факторы выше, чем быстрая сортировка на практике из-за операций с двоичной кучой. На устройствах с ограниченным объемом памяти, где даже несколько килобайт вспомогательной памяти слишком дороги, сорт кучи - отличный по умолчанию. Например, сортировка набора показаний датчиков в микроконтроллере ОЗУ 32 КБ может быть надежно выполнена с сортировкой кучи. Кроме того, сорт кучи может быть легко модифицирован для создания очереди приоритета, что полезно для событийных рабочих нагрузок кромки.
Сортировка
Сортировка счетчиков — это несравнительный алгоритм, который сортирует целые числа во времени O(n + k), где k — диапазон входных значений. Для этого требуется вспомогательный массив размера k, ограничивающий его применимость к ситуациям, где диапазон мал. В краевых приложениях многие показания датчиков выдают целые значения в ограниченном диапазоне (например, 8-битные или 16-битные). Для датчика температуры, который выводит значения от —40 до 125 градусов (166 различных значений), сортировка счетчиков может сортировать сотни показаний в микросекундах. Стоимость памяти для массива счетчиков (166 × 2 байт = 332 байта) приемлема даже на крошечных устройствах. Сорт подсчета также стабилен и может быть расширен до сортировки радикса для многозначных чисел. Однако она не подходит для данных с плавающей точкой или больших диапазонов (например, 32-битные временные метки) из-за взрыва памяти.
Стратегии оптимизации сортировки в устройствах Edge
Помимо выбора алгоритма, несколько системных стратегий могут значительно улучшить производительность сортировки в периферийных вычислительных устройствах.
Выбор алгоритма на основе характеристик данных
Не все данные равны. Разработчики должны профилировать размер данных, распределение и тип перед выбором алгоритма сортировки. Для небольших наборов данных (менее 64 элементов) сортировка вставки часто превосходит алгоритмы деления и завоевания из-за более низких накладных расходов. Для средних массивов с известным диапазоном оптимальна сортировка подсчета. Для больших наборов данных, где память плотная, сорт кучи безопасен. Для общих случаев с умеренной памятью идеален гибридный алгоритм, такой как интрозорт (быстрый сорт переключается на сорт кучи, когда глубина рекурсии превышает логарифм n). Многие программные рамки регрессии теперь включают адаптивные функции сортировки, которые выбирают лучший алгоритм во время выполнения на основе размера ввода - например, C++ , как правило, вариант интрозорта.
Предварительная обработка данных для уменьшения сложности
Предварительная обработка может упростить задачу сортировки. Одним из распространенных методов является фильтрация : удаление дублирующих или нерелевантных данных перед сортировкой. Например, предиктивный датчик обслуживания, который генерирует тысячи точек данных в секунду, может потребоваться только для сортировки 100 лучших аномалий. Выбор на основе кучи топ-к может извлечь самые большие или самые маленькие элементы в O (n log k) без сортировки всего набора данных. Другой метод - это ведра на основе ключа, а затем сортировать каждое ведро индивидуально. Это особенно эффективно, когда данные почти сортируются или имеют известное распределение. Например, данные временных рядов от датчика фиксированной частоты поступают в естественном порядке; простая сортировка вставки для вставки выпадающих в сортированный список быстрее, чем повторно сортировать с нуля.
Параллельная обработка на многоядерных крайних SoC
Многие современные периферийные устройства имеют многоядерные процессоры (например, ARM Cortex-A series). Параллельная сортировка может использовать эти ядра для сокращения времени настенных часов. Типичный подход разделяет массив ввода на куски, сортирует каждый куск самостоятельно (например, с быстрой сортировкой), а затем сливает каждый куск самостоятельно (например, сортирует сортированные куски). Шаг слияния также может быть параллелизирован с помощью дерева турниров или алгоритма параллельного слияния. Однако параллелизм вводит накладные расходы от синхронизации потоков и движения данных. Для эффективной параллельной сортировки на краю набор данных должен быть достаточно большим, чтобы амортизировать начальные затраты (по крайней мере, несколько тысяч элементов на ядро). Кроме того, некоторые периферийные устройства поддерживают инструкции SIMD (Single Instruction, Multiple Data) (например, NEON на ARM). SIMD может ускорить операции сравнения и свопа в сортировке, но реализация сортировки SIMD-ауре требует низкоуровневого программирования. Библиотеки, такие как Intel
Управление памятью для предотвращения бутылок
Алгоритмы сортировки часто страдают от плохой локализации кэша, что приводит к остановкам процессора. На периферийных устройствах с небольшими кэшами (обычно 16-32 КБ L1, 128-512 КБ L2) промахи кэша дороги. Алгоритмы, не замечающие кэша, такие как блокированная сортировка слияния или сортировка образца, могут улучшить локальность, сортируя данные по частям, которые подходят для кэша. Другая стратегия заключается в использовании алгоритма на месте (например, сорт кэша), чтобы избежать выделения дополнительной памяти, тем самым снижая давление кэша от динамического распределения. Если вспомогательная память неизбежна, предварительное распределение буфера фиксированного размера за пределами функции сортировки предотвращает повторное распределение памяти. Для систем с ребрами в реальном времени разработчики также должны гарантировать, что сортировка не вызывает фрагментацию памяти, которая может ухудшить будущие распределения. Техники, такие как пулы памяти или распределение на основе стека (alloca) могут помочь во встроенном коде C / C++
Сортировка по бенчмаркингу на Edge Hardware
Для иллюстрации рассмотрим три общих краевых устройства: Nordic Semiconductor nRF52840 (Cortex-M4, 64 MHz, 256 KB RAM), Raspberry Pi 4 (Cortex-A72, 1,5 GHz, 2 ГБ ОЗУ) и NVIDIA Jetson Nano (Cortex-A57 + GPU, 4 ГБ ОЗУ). Сортировка 10 000 целых чисел с использованием быстрой сортировки (оптимизированная для каждой платформы) может занять 150 мс на nRF52840, 0,5 мс на Pi и 0,1 мс на Jetson. Но эти сырые числа могут вводить в заблуждение: на nRF52840 куча сорт может быть только на 10% медленнее и использовать на 50% меньше стека, в то время как сортировка подсчета (если диапазон ≤ 256) может закончиться в 5 мс - улучшение в 30 раз. Разработчики должны ориентироваться на сортировку со своими конкретными размерами и типами данных, а также измерение потребления энергии. Инструменты, такие как ] Армейский цикл счетчик
Пример: Сортировка в автономной обработке данных транспортных средств
Автономные транспортные средства обрабатывают петабайты данных датчиков в час, но бортовой компьютер Edge AI имеет жесткие ограничения в реальном времени. Ключевой задачей является сортировка облачных данных точек от LiDAR для поиска ближайшего препятствия. Облако точек содержит миллионы координат x,y,z, часто хранящихся в виде 32-битных поплавков. Поскольку z-диапазон (расстояние) мал (0-200 метров), сортировка радикса (обобщение сортировки подсчета) может сортировать все облако за время O (n) с минимальными накладными расходами. Сортировка Radix по целым представлениям поплавков (с использованием манипуляции с битами IEEE 754) на NVIDIA Jetson AGX Orin может достигать 3-4× более быстрой сортировки, чем быстрая сортировка, что позволяет ранее обнаруживать столкновения. Кроме того, реализации CUDA на GPU могут сортировать миллионы точек параллельно, как показано в библиотеке CUB. Без оптимизированной сортировки транспортному средству потребуется более мощный (и дорогой) GPU
Ускорение аппаратного обеспечения для сортировки
Для периферийных устройств с фиксированными рабочими нагрузками аппаратные ускорители могут полностью разгрузить сортировку, освободив ЦПУ для других задач. FPGAs (Field-Programmable Gate Arrays) могут реализовать сортировочные сети, которые являются детерминированными и чрезвычайно быстрыми. Параллельная сортировочная сеть, такая как битоновая сортировка, может сортировать N входов в O(log2 N) стадиях. Например, сортировщик на базе FPGA на Intel Arria 10 может сортировать 1024 32-битных целых числа менее чем за 2 микросекунды, на порядок быстрее, чем ЦПУ. ASICs (Application-Specific Integrated Circuits) со встроенными сортировочными движками появляются на рынке датчиков; чип SmartSorter от стартапа претендует на сортировку
Адаптивное и машинное обучение - управляемое сортирование
Недавние исследования исследуют использование машинного обучения для прогнозирования оптимального алгоритма сортировки для данного набора данных. Легкий классификатор (например, дерево решений), работающий на краю, может исследовать особенности входного массива - размер, энтропия, диапазон min/max и то, что он уже почти отсортирован - и выбрать алгоритм, который минимизирует прогнозируемое время выполнения. Например, TensorFlow Lite Micro от Google был использован для реализации небольшой нейронной сети на Cortex-M4, которая выбирает между сортировкой вставки, быстрой сортировкой и сортом подсчета с точностью 90%. Классификация накладных расходов (около 0,1 мс) намного меньше, чем сэкономленное время (до 10 мс). Этот подход позволяет краевым устройствам адаптироваться к изменяющимся шаблонам данных без вмешательства человека. Другой метод - выборка нескольких элементов, оценка распределения, а затем ведро остальное. Это особенно полезно для неоднородных данных, которые могут вызвать быстрый сорт для ухудшения. Размер образца можно динамически настраивать с помощью обучения усилению для максимизации пропускной способности при минимизации
Энергоэффективность и соображения в реальном времени
Краевые устройства часто работают от батареи и должны соответствовать мягким или жестким срокам в реальном времени. Сортировка может быть значительным потребителем энергии, особенно если это заставляет CPU оставаться активным дольше. Исследование, опубликованное в IEEE Транзакции на устойчивых вычислениях , показало, что использование кэш-оптимизированной сортировки слияний вместо наивной сортировки пузырьков, уменьшающей энергию на сорт на 60% на процессоре Cortex-M3. Чтобы минимизировать энергию, разработчики должны рассмотреть: (а) использование сортировки с использованием режима сна - если CPU может перейти в состояние с низким энергопотреблением ранее из-за более быстрой сортировки, энергия, сэкономленная, перевешивает повышенную тактовую частоту; (b) динамическое напряжение и частотное масштабирование (DVFS) - если данные малы, недовольствуют ядром во время сортировки; (c) избегать ненужной сортировки путем поддержания сортированных структур данных (например, управление самолетом), время выполнения в худ
Новые тенденции и будущие направления
Несколько новых технологий обещают дальнейшие улучшения в эффективности сортировки для краевых вычислений. В памяти вычисления с использованием мемристоров или обработки в памяти (PIM) могут сортировать данные непосредственно в массиве хранения, не перемещая их в ЦП. Это идеально подходит для очень больших наборов данных (например, 10 МБ), которые в противном случае перегружают краевую оперативную память. Оптическая сортировка с использованием фотонных схем чисто теоретическая для края, но может предложить почти нулевую энергию для сравнения. Аппаратные средства-программное обеспечение co-design облегчают сортировку специализированных сопроцессоров, включенных в современные SoC (например, Neural Processing Unit в Rockchip RK3588 может быть перепрофилирован для сортировки с помощью пользовательских прошивок). Кроме того, ограниченные ресурсами периферийные операционные системы, такие как FreeRTOS и Zephyr, включают
По мере того, как краевые вычисления продолжают развиваться, оптимизация алгоритмов сортировки останется критической областью фокусировки. Реализуя изложенные стратегии - от тщательного выбора алгоритма и предварительной обработки данных до параллельной обработки, аппаратного ускорения и адаптации машинного обучения - разработчики могут обеспечить более быструю, более надежную обработку данных, открывая новые возможности для краевых приложений в различных отраслях. Независимо от того, является ли целью сбрить миллисекунды с времени реакции автономного транспортного средства или продлить срок службы батареи удаленного датчика на месяцы, внимание к оптимизации сортировки является высокопроизводительной деятельностью, которая приносит дивиденды в производительности и эффективности системы.