Сглаживающее преобразование

Тема этой статьи может не соответствовать общему руководству Википедии по значимости . Пожалуйста, помогите продемонстрировать значимость темы, ссылаясь на надежные вторичные источники , которые независимы от темы и обеспечивают ее значительное освещение, выходящее за рамки простого тривиального упоминания. Если значимость не может быть показана, статья, скорее всего, будет объединена , перенаправлена ​​или удалена . Найти источники:  «Flattening transformation» – новости  · газеты  · книги  · ученый  · JSTOR ( январь 2023 г. ) ( Узнайте, как и когда удалить это сообщение )

Преобразование выравнивания — это алгоритм , который преобразует вложенный параллелизм данных в плоский параллелизм данных. Он был впервые предложен Гаем Блеллохом как часть языка программирования NESL . ^[1] Преобразование выравнивания также иногда называют векторизацией , но оно совершенно не связано с автоматической векторизацией . Первоначальный алгоритм выравнивания был связан исключительно с многомерными массивами первого порядка, содержащими примитивные типы, но был расширен для обработки типов данных более высокого порядка и рекурсивных типов в работе над Data Parallel Haskell. ^[2]

Сглаживание работает путем поднятия функций для работы с массивами, а не с отдельными значениями. Например, функция поднимается до функции . Это означает, что выражение может быть заменено применением поднятой функции: . Интуитивно понятно, что сглаживание таким образом работает путем замены всех применений функций применениями соответствующей поднятой функции.${\displaystyle f:A\rightarrow B}$${\displaystyle f':[A]\rightarrow [B]}$${\displaystyle map~f~x}$${\displaystyle f'~x}$

После выравнивания массивы представляются как одномерный вектор значений V , содержащий скалярные элементы, наряду со вспомогательной информацией, записывающей вложенную структуру, обычно в форме вектора булевых флагов F. Вектор флагов указывает для соответствующего элемента в векторе значений, является ли он началом нового сегмента . Например, двумерный нерегулярный массив может быть представлен как вектор данных рядом с вектором флагов .${\displaystyle A=[[1,2,3],[4,5],[],[6]]}$${\displaystyle V=[1,2,3,4,5,6,7]}$${\displaystyle F=[1,0,0,1,0,1,1]}$

Этот вектор флага необходим для правильного выравнивания вложенного параллелизма. Например, он используется при выравнивании суммы префикса до сегментированного сканирования .

Сглаживание может увеличить асимптотическую работу и сложность пространства исходной программы, что приведет к гораздо менее эффективному результату. ^[3]

Первоначально метод Flattening был разработан для векторных машин, таких как Connection Machine , и часто создает код, который не очень хорошо подходит для современных многоядерных процессоров. ^[4] Однако принципы, лежащие в основе его более простых случаев, можно найти в таких конструкциях, как vmapв Google Jax .