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

Сглаживающее преобразование — это алгоритм , который преобразует параллелизм вложенных данных в параллелизм плоских данных. Впервые он был разработан Гаем Блеллохом как часть языка программирования NESL . Сглаживающее преобразование также иногда называют векторизацией , но оно совершенно не связано с автоматической векторизацией . Исходный алгоритм выравнивания касался исключительно многомерных массивов первого порядка, содержащих примитивные типы, но был расширен для обработки рекурсивных типов данных более высокого порядка в работе над Data Parallel Haskell .

Обзор

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

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

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

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

Использование

Первоначально выравнивание было разработано для векторных машин, таких как Connection Machine , и часто создает код, который не подходит для современных многоядерных процессоров. Однако принципы, лежащие в основе его более простых случаев, можно найти в таких конструкциях, как vmap в Гугл Джаксе .