Конференція Високопродуктивні обчислення, Київ, 13-15 жовтня 2014

Ефективне обчислення власних значень тензора на GPU

Задача знаходження власних значень тензора має багато важливих застосувань, створюючи як математичний, так і прикладний інтерес до їх властивостей та способів обчислень.

Тензор – це n-вимірна матриця, узагальнене поняття звичайної матриці (двовимірного масиву). Kolda та Mayo недавно опублікували узагальнення матричного степеневого методу для обчислення власних чисел та векторів дійснозначного симетричного тензора.

У даній роботі розглядається ефективна реалізація наведеного алгоритму, який використовує симетрію для економії пам’яті, зменшення кількості переміщень даних та обчислень. Для програми, яка обчислює велику кількість задач на власні значення для малих тензорів, описується метод прискорення обчислень на GPU. На NVidia Tesla C2050 на тестових даних досягнуто рівень продуктивності 318 GFlops (31% від пікової продуктивності для одинарної точності).

Висновки

У роботі розглянуто застосування алгоритму SS-HOPM, реалізованого на GPU. Описано, яким чином використати симетрію для економії пам’яті та обчислень у двох головних процедурах алгоритму. У випадку обчислення великої кількості задач на власні значення для малих тензорів показано, яким чином це організувати на GPU.

Для тестового набору даних отримано велике прискорення за рахунок розпаралелювання,  у порівнянні з послідовним кодом, використовуючи низькорівневу оптимізацію (без оптимізації використання пам’яті).

Є надія, що методи використання симетрії можна поширити на інші обчислення, які включають симетричні тензори, але при цьому залишається багато відкритих питань про те, як писати послідовну та паралельні реалізації для обчислювальних ядер, які масштабуються для більших порядків та розмірностей тензорів.

Для обчислень Axm та Ax(m-1) ми сподіваємось отримати таку саму продуктивність для тензорів загального розміру. Основні проблеми реалізації полягають у класифікації різноманітних форм з блоків, які з’являються (для кожного порядку m), таким чином, щоб кожну форму можна було обчислювати окремо, а також визначенні неявного порядку унікальних входжень тензорів, при якому досягається найкраща поведінка кеша.

Grey Ballard, Tamara Kolda, Todd Plantenga. Efficiently Computing Tensor Eigenvalues on a GPU. Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), IEEE Computer Society Washington, DC, 2011, pages 1340-1348. [doi: 10.1109/IPDPS.2011.287] [PDF]

Теги: GPU, NVidia, математика

Матеріали за темою:

Коментарі