Организация данных в определённом порядке, также известная как сортировка, — это важная вычислительная операция, выполняемая широким спектром систем. Традиционные аппаратные системы используют отдельные компоненты для хранения и сортировки данных, что ограничивает их скорость и энергоэффективность.

Исследователи из Пекинского университета недавно разработали новую реконфигурируемую систему сортировки в памяти, которая использует мемристоры для сортировки хранимых данных in situ. Предложенная ими система, описанная в статье, опубликованной в журнале Nature Electronics под руководством профессора Юйчао Яна, обеспечивает быстрое и энергоэффективное хранение и сортировку данных.

«Оригинальная идея исходит из того, что, хотя такие операции, как умножение матриц и свёртка, широко реализованы в системах CIM (вычисления в оперативной памяти), сортировка долгое время считалась «крепким орешком» в технологии вычислений в оперативной памяти из-за её уникальных вычислительных характеристик», — рассказал TechXplore Яоюй Тао, один из авторов статьи.

«Во-первых, традиционные аппаратные средства сортировки включают в себя обширную логику сравнения и выбора, условное ветвление или операции обмена, характеризующиеся нерегулярным потоком управления, который принципиально отличается от линейных операций, в которых CIM (Compute-in-Memory) превосходен. Во-вторых, сортировка с большими объёмами данных часто приводит к высокодинамичным шаблонам доступа к памяти, которые конфликтуют со структурированными схемами доступа к памяти CIM».

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

«Причина, по которой сортировка остается нерешенной проблемой при разработке CIM, заключается в ее «неструктурированной» и «требовательной к управлению» вычислительной природе, что по сути противоречит текущим принципам проектирования CIM, основанным на линейном ускорении в оперативной памяти», — пояснил Тао.

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

Новая реконфигурируемая система сортировки в памяти, разработанная Тао и его коллегами в рамках недавнего исследования, состоит из мемристорных матриц типа «один транзистор — один резистор» (1T1R) и периферийных схем. Периферийные схемы разделены на три отдельных модуля: цифровой процессор, селектор цифр и контроллер состояний.

«Эти компоненты можно перенастроить для доступа к массивам мемристоров 1T1R и поддержки переменных типов данных, описанных в литературе, включая беззнаковые, двоичные дополнительные числа, а также числа с фиксированной или плавающей точкой, имеющие знак и величину, что позволяет удовлетворять потребности реальных приложений сортировки», — пояснил Тао.

«Их уникальные преимущества/характеристики включают поддержку трёх различных методологий повышения параллелизма: многобанковую стратегию для более высокого параллелизма на числовом уровне, стратегию бит-слайсов для более высокого параллелизма на битовом уровне и многоуровневую стратегию для более высокого параллелизма внутри устройства».

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

«Эта схема реализует три стратегии повышения параллелизма, включая многобанковую, битовую и многоуровневую проводимость, и совместима с передовыми технологиями вычислений в памяти для умножения матриц на векторы», — сказал Тао. «Алгоритмы сортировки играют важнейшую роль в обработке данных, быстро ранжируя огромные объёмы данных-кандидатов для выявления наиболее релевантных элементов для дальнейшего анализа».

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

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

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

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