Применение технологии nvidia CUDA для обучения и декодирования Скрытых Марковских моделей. Технология cuda реферат

Реферат nvidia cuda

Реферат на тему:

План:

Введение
• 1 Программная архитектура
• 2 Оборудование
• 3 Преимущества
• 4 Ограничения
• 5 Поддерживаемые GPU и графические ускорители[3]
• 6 Особенности и спецификации различных версий
• 7 Пример
• 8 CUDA как предмет в вузах
Примечания

Введение

CUDA (англ. Compute Unified Device Architecture) — программно-аппаратная архитектура, позволяющая производить вычисления с использованием графических процессоров NVIDIA, поддерживающих технологию GPGPU (произвольных вычислений на видеокартах). Архитектура CUDA впервые появились на рынке с выходом чипа NVIDIA восьмого поколения — G80 и присутствует во всех последующих сериях графических чипов, которые используются в семействах ускорителей GeForce, Quadro и Tesla.

CUDA SDK позволяет программистам реализовывать на специальном упрощённом диалекте языка программирования Си алгоритмы, выполнимые на графических процессорах NVIDIA, и включать специальные функции в текст программы на Cи. CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью, организовывать на нём сложные параллельные вычисления.

1. Программная архитектура

Первоначальная версия CUDA SDK была представлена 15 февраля 2007 года. В основе CUDA API лежит язык Си с некоторыми ограничениями. Для успешной трансляции кода на этом языке, в состав CUDA SDK входит собственный Си-компилятор командной строки nvcc компании Nvidia. Компилятор nvcc создан на основе открытого компилятора Open64 и предназначен для трансляции host-кода (главного, управляющего кода) и device-кода (аппаратного кода) (файлов с расширением .cu) в объектные файлы, пригодные в процессе сборки конечной программы или библиотеки в любой среде программирования, например в NetBeans.

Использует grid-модель памяти, кластерное моделирование потоков и SIMD инструкции. Применим в основном для высокопроизводительных графических вычислений и разработок NVIDIA-совместимого графического API. Включена возможность подключения к приложениям, использующим OpenGL и Microsoft Direct3D 9. Создан в версиях для Linux, Mac OS X, Windows.

22 марта 2010 года nVidia выпустила CUDA Toolkit 3.0, который содержал поддержку OpenCL.[1]

2. Оборудование

Первая серия оборудования, поддерживающая CUDA SDK, G8x, имела 32-битный векторный процессор одинарной точности, использующий CUDA SDK как API (CUDA поддерживает тип double языка Си, однако сейчас его точность понижена до 32-битного с плавающей запятой). Более поздние процессоры GT200 имеют поддержку 64-битной точности (только для SFU), но производительность значительно хуже, чем для 32-битной точности (из-за того что SFU всего 2 на каждый потоковый мультипроцессор, а скалярных процессоров 8). Графический процессор организует аппаратную многопоточность, что позволяет задействовать все ресурсы графического процессора. Таким образом, открывается перспектива переложить функции физического ускорителя на графический ускоритель (пример реализации — nVidia PhysX). Также открываются широкие возможности использования графического оборудования компьютера для выполнения сложных неграфических вычислений: например, в вычислительной биологии и в иных отраслях науки.

3. Преимущества

По сравнению с традиционным подходом к организации вычислений общего назначения посредством возможностей графических API, у архитектуры CUDA отмечают следующие преимущества в этой области:

• Интерфейс программирования приложений CUDA (CUDA API) основан на стандартном языке программирования Си с некоторыми ограничениями. По мнению разработчиков, это должно упростить и сгладить процесс изучения архитектуры CUDA[2]
• Разделяемая между потоками память (shared memory) размером в 16 Кб может быть использована под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур
• Более эффективные транзакции между памятью центрального процессора и видеопамятью
• Полная аппаратная поддержка целочисленных и побитовых операций

4. Ограничения

• Все функции, выполнимые на устройстве, не поддерживают рекурсии (в версии CUDA Toolkit 3.1 поддерживает указатели и рекурсию) и имеют некоторые другие ограничения
• Архитектуру CUDA поддерживает и развивает только производитель NVidia

5. Поддерживаемые GPU и графические ускорители[3]

Перечень устройств от производителя оборудования Nvidia с заявленной полной поддержкой технологии CUDA приведён на официальном сайте Nvidia: CUDA-Enabled GPU Products (англ.).

Фактически же, в настоящее время на рынке аппаратных средств для ПК поддержку технологии CUDA обеспечивают следующие периферийные устройства[3]:

Модели Tesla C1060, Tesla S1070, Tesla C2050/C2070, Tesla M2050/M2070, Tesla S2050 позволяют производить вычисления на GPU с двойной точностью.

6. Особенности и спецификации различных версий

7. Пример

Этот пример кода на C загрузки текстур из изображения в массив на GPU:

Пример программы на языке Python, перемножающий матрицы средствами GPU. Взаимодействие идёт с использованием PyCUDA [5]

8. CUDA как предмет в вузах

По состоянию на декабрь 2009 года, программная модель CUDA преподается в 269 университетах по всему миру. В России обучающие курсы по CUDA читаются в Санкт-Петербургском Политехническом Университете, Московском, Нижегородском, Санкт-Петербургском, Казанском, Новосибирском, Омском и Пермском государственных университетах, Международном университете природы общества и человека «Дубна», Объединённом институте ядерных исследований, Московском институте электронной техники, Ивановском государственном энергетическом университете, БГТУ им. В. Г. Шухова, МГТУ им. Баумана, РХТУ им.Менделеева, Российском научном центре «Курчатовский институт», Межрегиональном суперкомпьютерном центре РАН, Таганрогском технологическом институте (ТТИ ЮФУ).[6] Кроме того, в декабре 2009 года было объявлено о начале работы первого в России научно-образовательного центра «Параллельные вычисления», расположенного в городе Дубна, в задачи которого входят обучение и консультации по решению сложных вычислительных задач на GPU.[6]

На Украине курсы по CUDA читаются в Киевском институте системного анализа.[6]

Категории: API, GPGPU.

wreferat.baza-referat.ru

Использование технологий CUDA для высокопроизводительных вычислений

Основные  ограничения CUDA:

• отсутствие поддержки рекурсии для выполняемых функций;
• минимальная ширина блока в 32 потока;
• закрытая архитектура CUDA, принадлежащая NVIDIA.

Слабыми местами  программирования при помощи предыдущих методов GPGPU является то, что эти методы не используют блоки исполнения вершинных шейдеров в предыдущих неунифицированных архитектурах, данные хранятся в текстурах, а выводятся во внеэкранный буфер, а многопроходные алгоритмы используют пиксельные шейдерные блоки. В ограничения GPGPU можно включить: недостаточно эффективное использование аппаратных возможностей, ограничения полосой пропускания памяти, отсутствие операции scatter (только gather), обязательное использование графического API.

Основные  преимущества CUDA по сравнению с предыдущими методами GPGPU вытекают из того, что эта архитектура спроектирована для эффективного использования неграфических вычислений на GPU и использует язык программирования C, не требуя переноса алгоритмов в удобный для концепции графического конвейера вид. CUDA предлагает новый путь вычислений на GPU, не использующий графические API, предлагающий произвольный доступ к памяти (scatter или gather). Такая архитектура лишена недостатков GPGPU и использует все исполнительные блоки, а также расширяет возможности за счёт целочисленной математики и операций битового сдвига.

Кроме того, CUDA открывает некоторые аппаратные возможности, недоступные из графических API, такие как разделяемая память. Это память небольшого объёма (16 килобайт на мультипроцессор), к которой имеют доступ блоки потоков. Она позволяет кэшировать наиболее часто используемые данные и может обеспечить более высокую скорость, по сравнению с использованием текстурных выборок для этой задачи. Что, в свою очередь, снижает чувствительность к пропускной способности параллельных алгоритмов во многих приложениях. Например, это полезно для линейной алгебры, быстрого преобразования Фурье и фильтров обработки изображений.

Удобнее в  CUDA и доступ к памяти. Программный код в графических API выводит данные в виде 32-х значений с плавающей точкой одинарной точности (RGBA значения одновременно в восемь render target) в заранее предопределённые области, а CUDA поддерживает scatter запись — неограниченное число записей по любому адресу. Такие преимущества делают возможным выполнение на GPU некоторых алгоритмов, которые невозможно эффективно реализовать при помощи методов GPGPU, основанных на графических API.

Также, графические  API в обязательном порядке хранят данные в текстурах, что требует предварительной упаковки больших массивов в текстуры, что усложняет алгоритм и заставляет использовать специальную адресацию. А CUDA позволяет читать данные по любому адресу. Ещё одним преимуществом CUDA является оптимизированный обмен данными между CPU и GPU. А для разработчиков, желающих получить доступ к низкому уровню (например, при написании другого языка программирования), CUDA предлагает возможность низкоуровневого программирования на ассемблере. 

Состав NVIDIA CUDA

CUDA включает два API: высокого уровня (CUDA Runtime API) и низкого (CUDA Driver API), хотя в одной программе одновременное использование обоих невозможно, нужно использовать или один или другой. Высокоуровневый работает «сверху» низкоуровневого, все вызовы runtime транслируются в простые инструкции, обрабатываемые низкоуровневым Driver API. Но даже «высокоуровневый» API предполагает знания об устройстве и работе видеочипов NVIDIA, слишком высокого уровня абстракции там нет.

Есть и  ещё один уровень, даже более высокий  — две библиотеки:

CUBLAS — CUDA вариант BLAS (Basic Linear Algebra Subprograms), предназначенный для вычислений задач линейной алгебры и использующий прямой доступ к ресурсам GPU;

CUFFT — CUDA вариант библиотеки Fast Fourier Transform для расчёта быстрого преобразования Фурье, широко используемого при обработке сигналов. Поддерживаются следующие типы преобразований: complex-complex (C2C), real-complex (R2C) и complex-real (C2R).

Рассмотрим  эти библиотеки подробнее. CUBLAS — это переведённые на язык CUDA стандартные алгоритмы линейной алгебры, на данный момент поддерживается только определённый набор основных функций CUBLAS. Библиотеку очень легко использовать: нужно создать матрицу и векторные объекты в памяти видеокарты, заполнить их данными, вызвать требуемые функции CUBLAS, и загрузить результаты из видеопамяти обратно в системную. CUBLAS содержит специальные функции для создания и уничтожения объектов в памяти GPU, а также для чтения и записи данных в эту память. Поддерживаемые функции BLAS: уровни 1, 2 и 3 для действительных чисел, уровень 1 CGEMM для комплексных. Уровень 1 — это векторно-векторные операции, уровень 2 — векторно-матричные операции, уровень 3 — матрично-матричные операции.

CUFFT — CUDA вариант функции быстрого преобразования Фурье — широко используемой и очень важной при анализе сигналов, фильтрации и т.п. CUFFT предоставляет простой интерфейс для эффективного вычисления FFT на видеочипах производства NVIDIA без необходимости в разработке собственного варианта FFT для GPU. CUDA вариант FFT поддерживает 1D, 2D, и 3D преобразования комплексных и действительных данных, пакетное исполнение для нескольких 1D трансформаций в параллели, размеры 2D и 3D трансформаций могут быть в пределах [2, 16384], для 1D поддерживается размер до 8 миллионов элементов. 

Основы  создания программ на CUDA

Для понимания  дальнейшего текста следует разбираться  в базовых архитектурных особенностях видеочипов NVIDIA. GPU состоит из нескольких кластеров текстурных блоков (Texture Processing Cluster). Каждый кластер состоит из укрупнённого блока текстурных выборок и двух-трех потоковых мультипроцессоров, каждый из которых состоит из восьми вычислительных устройств и двух суперфункциональных блоков. Все инструкции выполняются по принципу SIMD, когда одна инструкция применяется ко всем потокам в warp (термин из текстильной промышленности, в CUDA это группа из 32 потоков — минимальный объём данных, обрабатываемых мультипроцессорами). Этот способ выполнения назвали SIMT (single instruction multiple threads — одна инструкция и много потоков).

Каждый из мультипроцессоров имеет определённые ресурсы. Так, есть специальная разделяемая  память объемом 16 килобайт на мультипроцессор. Но это не кэш, так как программист  может использовать её для любых  нужд, подобно Local Store в SPU процессоров Cell. Эта разделяемая память позволяет обмениваться информацией между потоками одного блока. Важно, что все потоки одного блока всегда выполняются одним и тем же мультипроцессором. А потоки из разных блоков обмениваться данными не могут, и нужно помнить это ограничение. Разделяемая память часто бывает полезной, кроме тех случаев, когда несколько потоков обращаются к одному банку памяти. Мультипроцессоры могут обращаться и к видеопамяти, но с большими задержками и худшей пропускной способностью. Для ускорения доступа и снижения частоты обращения к видеопамяти, у мультипроцессоров есть по 8 килобайт кэша на константы и текстурные данные.

Мультипроцессор использует 8192-16384 (для G8x/G9x и GT2xx, соответственно) регистра, общие для всех потоков всех блоков, выполняемых на нём. Максимальное число блоков на один мультипроцессор для G8x/G9x равно восьми, а число warp — 24 (768 потоков на один мультипроцессор). Всего топовые видеокарты серий GeForce 8 и 9 могут обрабатывать до 12288 потоков единовременно. GeForce GTX 280 на основе GT200 предлагает до 1024 потоков на мультипроцессор, в нём есть 10 кластеров по три мультипроцессора, обрабатывающих до 30720 потоков. Знание этих ограничений позволяет оптимизировать алгоритмы под доступные ресурсы.

Первым шагом  при переносе существующего приложения на CUDA является его профилирование и определение участков кода, являющихся «бутылочным горлышком», тормозящим работу. Если среди таких участков есть подходящие для быстрого параллельного исполнения, эти функции переносятся на Cи расширения CUDA для выполнения на GPU. Программа компилируется при помощи поставляемого NVIDIA компилятора, который генерирует код и для CPU, и для GPU. При исполнении программы, центральный процессор выполняет свои порции кода, а GPU выполняет CUDA код с наиболее тяжелыми параллельными вычислениями. Эта часть, предназначенная для GPU, называется ядром (kernel). В ядре определяются операции, которые будут исполнены над данными.

Видеочип получает ядро и создает копии для каждого элемента данных. Эти копии называются потоками (thread). Поток содержит счётчик, регистры и состояние. Для больших объёмов данных, таких как обработка изображений, запускаются миллионы потоков. Потоки выполняются группами по 32 штуки, называемыми warp'ы. Warp'ам назначается исполнение на определенных потоковых мультипроцессорах. Каждый мультипроцессор состоит из восьми ядер — потоковых процессоров, которые выполняют одну инструкцию MAD за один такт. Для исполнения одного 32-поточного warp'а требуется четыре такта работы мультипроцессора (речь о частоте shader domain, которая равна 1.5 ГГц и выше).

Мультипроцессор не является традиционным многоядерным процессором, он отлично приспособлен для многопоточности, поддерживая до 32 warp'ов единовременно. Каждый такт аппаратное обеспечение выбирает, какой из warp'ов исполнять, и переключается от одного к другому без потерь в тактах. Если проводить аналогию с центральным процессором, это похоже на одновременное исполнение 32 программ и переключение между ними каждый такт без потерь на переключение контекста. Реально ядра CPU поддерживают единовременное выполнение одной программы и переключаются на другие с задержкой в сотни тактов.

Модель  программирования CUDA

Повторимся, что CUDA использует параллельную модель вычислений, когда каждый из SIMD процессоров  выполняет ту же инструкцию над разными  элементами данных параллельно. GPU является вычислительным устройством, сопроцессором (device) для центрального процессора (host), обладающим собственной памятью и обрабатывающим параллельно большое количество потоков. Ядром (kernel) называется функция для GPU, исполняемая потоками (аналогия из 3D графики — шейдер).

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

Модель программирования в CUDA предполагает группирование потоков. Потоки объединяются в блоки потоков (thread block) — одномерные или двумерные сетки потоков, взаимодействующих между собой при помощи разделяемой памяти и точек синхронизации. Программа (ядро, kernel) исполняется над сеткой (grid) блоков потоков (thread blocks), см. рисунок ниже. Одновременно исполняется одна сетка. Каждый блок может быть одно-, двух- или трехмерным по форме, и может состоять из 512 потоков на текущем аппаратном обеспечении.

Блоки потоков  выполняются в виде небольших  групп, называемых варп (warp), размер которых — 32 потока. Это минимальный объём данных, которые могут обрабатываться в мультипроцессорах. И так как это не всегда удобно, CUDA позволяет работать и с блоками, содержащими от 64 до 512 потоков.

Группировка блоков в сетки позволяет уйти от ограничений и применить ядро к большему числу потоков за один вызов. Это помогает и при масштабировании. Если у GPU недостаточно ресурсов, он будет  выполнять блоки последовательно. В обратном случае, блоки могут  выполняться параллельно, что важно  для оптимального распределения  работы на видеочипах разного уровня, начиная от мобильных и интегрированных.  

Среда программирования

В состав CUDA входят runtime библиотеки:

общая часть, предоставляющая встроенные векторные  типы и подмножества вызовов RTL, поддерживаемые на CPU и GPU;

CPU-компонента, для управления одним или несколькими  GPU;

GPU-компонента, предоставляющая специфические  функции для GPU.

Основной  процесс приложения CUDA работает на универсальном процессоре (host), он запускает несколько копий процессов kernel на видеокарте. Код для CPU делает следующее: инициализирует GPU, распределяет память на видеокарте и системе, копирует константы в память видеокарты, запускает несколько копий процессов kernel на видеокарте, копирует полученный результат из видеопамяти, освобождает память и завершает работу.

В качестве примера для понимания приведем CPU код для сложения векторов, представленный в CUDA:  

Функции, исполняемые  видеочипом, имеют следующие ограничения: отсутствует рекурсия, нет статических переменных внутри функций и переменного числа аргументов. Поддерживается два вида управления памятью: линейная память с доступом по 32-битным указателям, и CUDA-массивы с доступом только через функции текстурной выборки.

Программы на CUDA могут взаимодействовать с  графическими API: для рендеринга данных, сгенерированных в программе, для считывания результатов рендеринга и их обработки средствами CUDA (например, при реализации фильтров постобработки). Для этого ресурсы графических API могут быть отображены (с получением адреса ресурса) в пространство глобальной памяти CUDA. Поддерживаются следующие типы ресурсов графических API: Buffer Objects (PBO / VBO) в OpenGL, вершинные буферы и текстуры (2D, 3D и кубические карты) Direct3D9.

student.zoomru.ru

"Применение технологии nvidia CUDA для обучения и декодирования Скрытых Марковских моделей"

Выдержка из работы

УДК 004. 934ПРИМЕНЕНИЕ ТЕХНОЛОГИИ NVIDIA CUDA ДЛЯ ОБУЧЕНИЯ И ДЕКОДИРОВАНИЯ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙЗацепин Павел Михайлович,канд. физ. -мат. наук, доцент, заведующий кафедрой вычислительной техники и электроники Физико-технического факультета Алтайского Государственного университета, Россия, 656 049, г. Барнаул, пр. Ленина, 61.E-mail: zpm@phys. asu. ruГефке Денис Алексеевич,аспирант кафедры вычислительной техники и электроники Физико-технического факультета Алтайского Государственного университета, Россия, 656 049, г. Барнаул, пр. Ленина, 61. E-mail: bspugda@mail. ruАктуальность работы обусловлена необходимостью оптимизации алгоритмов обработки больших речевых баз данных при разработке качественных систем автоматического распознавания речи. Развитие современных многоядерных процессоров, в частности графических процессоров GPU, позволяет получить существенный прирост производительности при реализации сложных ресурсоемких алгоритмов цифровой обработки сигналов и значительно сократить время обработки данных.Цель работы: оптимизация алгоритмов обучения (Baum-Welch re-estimation) и декодирования (Витерби) Скрытых Марковских Моделей с помощью технологии параллельного программирования NVIDIA CUDA и оценка прироста производительности относительно центрального процессора.Методы исследования: определение участков алгоритмов обучения и декодирования Скрытых Марковских Моделей, подходящих для эффективной параллельной реализации с учетом особенности программной модели CUDA, с последующей реализацией. Результаты: Получена практическая параллельная реализация алгоритмов обучения и декодирования Скрытых Марковских Моделей с помощью графического процессора GPU. Произведена оценка прироста производительности относительно центрального процессора для различных параметров модели (количества состояний и размерности параметрического вектора). Результаты данной работы могут быть полезны как инженерам, работающим над созданием и улучшением систем автоматического распознавания речи, так и исследователям, работающим в области обработки сигналов и искусственного интеллекта.Ключевые слова:Распознавание речи, параллельные вычисления, Скрытые Марковские Модели, NVIDIA CUDA, алгоритм Витерби, алгоритм Баума~Велча.ВведениеМатематический аппарат Скрытых Марковских Моделей (СММ) представляет собой универсальный инструмент моделирования стохастических процессов, для описания которых не существует точных математических моделей, а их свойства меняются с течением времени в соответствии с некоторыми статистическими законами. Наиболее широкое применение СММ нашли при решении таких задач, как распознавание речи, анализа последовательностей ДНК и ряда других [1].Современные системы распознавания речи предполагают наличие нескольких сотен, а то и тысяч Скрытых Марковских Моделей и их сочетаний, вследствие чего работа со СММ связана со значительными вычислительными затратами, как на этапе обучения — при обработке огромного массива речевых данных, так и при последующем декодировании — в зависимости от сложности языковой модели. Например, обучение хорошей помехозащищенной дикторо-независимой системы распознавания слитной речи может занять несколько недель, а то и месяцев. Поэтому задача оптимизации алгоритмов обработки СММ остается актуальной в настоящее время [2, 3].Применение современных технологий параллельного программирования, в частности графиче-ских мультипроцессоров, позволяет получить значительный прирост производительности и перейти на качественно более высокий уровень в решении задач распознавания речи.Целью данной работы является оптимизация алгоритмов обучения Скрытых Марковских Моделей (Ваит^е1сЬ re-estemation и ^та^-Ьаск-ward) и алгоритма декодирования (обобщенный алгоритм Витерби) с помощью графического процессора (CUDA) и оценка прироста производительности относительно центрального процессора (СРи).Структура Скрытой Марковской МоделиВ основе Скрытой Марковской Модели лежит конечный автомат, состоящий из N состояний. Переходы между состояниями в каждый дискретный момент времени t не являются детерминированными, а происходят в соответствии с некоторым вероятностным законом и описываются матрицей вероятностей переходов Лщ. Схематическое изображение диаграммы переходов между состояниями в СММ приведено на рис. 1 [4].При каждом переходе в новое состояние I в момент времени t происходит генерация выходного значения в соответствии с функцией распределения Результатом работы СММ является последо-вательность параметрических векторов {x1,x2,^, xT} длиной T [5].Рис. 1. Структурная схема переходов в СММНа практике, как правило, решается обратная задача: при известной структуре Марковской Модели требуется определить, какова вероятность, что наблюдаемая последовательность {xj, x2,…, xT} может быть сгенерирована данной СММ [6].Таким образом, основными параметрами СММ являются:1) N — количество состояний-2) матрица вероятностей переходов ANN между состояниями-3) N функций плотности вероятностиf (x). Функция плотности вероятности f (x) описывается, как правило, взвешенной Гауссовой смесью:Mf (X) =? WiPi (X),/=1где M — количество компонент смеси- wt — вес компонента смеси, аp (x) — нормальное распределение вероятностей для. D-мерного случая:*(Х) = еХР{& quot-2(x-*,) 1 Г (x-V,)]¦где v — вектор математического ожидания- -матрица ковариации.Работа со Скрытыми Марковскими Моделями, как и с любой другой адаптивной системой, осуществляется в 2 этапа: обучение — алгоритм Бау-ма-Велча (Baum-Welch re-estemation), декодирование — алгоритм максимума правдоподобия (Ви-терби) [7].В качестве параметрического вектора чаще всего используют мел-частотные кепстральные коэффициенты [8] (MFCC — mel-frequency cepstral coefficients), либо коэффициенты линейного предсказания [9] (LPC — linear prediction coefficients), а также их первые и вторые производные. Данные преобразования, в силу их гармонической природы, позволяют с высокой достоверностью локализовать вокализованные составляющие сигнала (гласные звуки) [10]. В тоже время, речевой сигнал имеет более сложную природу и помимо вокализованных звуков содержит ударные, шипящие и прочие составляющие. Поэтому для обработки речевого сигнала представляется перспективным применение других операторов, например Вейвлет-преобразований [11], рассмотрение которых выходит за рамки данной работы, т. к. реализованные алгоритмы являются универсальными и не зависят от природы параметрического вектора.Сравнение Скрытой Марковской Модели и искусственных нейронных сетей при решении задачи автоматического распознавания речиВ настоящее время Скрытые Марковские Модели являются основой большинства успешных систем автоматического распознавания речи. Это связано с наличием ряда важных свойств, которыми обладают СММ по сравнению с основной альтернативной моделью классификации — искусственными нейронными сетями [12, 13]:1) возможность моделирования длительных временных последовательностей (слов или целых высказываний), в то время как искусственные нейронные сети (ИНС) хорошо подходят для классификации кратковременных акустико-фонетических единиц, а их эффективность сильно снижается, когда на входе появляется некоторая динамика, т. е. образы подвержены, например, нелинейным изменениям во времени-2) обучение ИНС при построении систем автоматического распознавания речи происходит, как правило, с учителем и требует точной временной разметки на фонемы обучающей выборки, что является чрезвычайно трудоемкой задачей для современных речевых баз данных. В тоже время обучение СММ может производиться без точной временной разметки-3) возможность объединения, совместного обучения и декодирования набора СММ, представляющих отдельные фонемы, в соответствии с языковой моделью. Говоря простым языком, СММ хорошо адаптированы для построения составных моделей из исходных «примитивных» языковых элементов — фонем.В то же время СММ обладают существенным недостатком по сравнению с ИНС — слабой дискриминантной мощностью, т. е. возможностью разделять классы образов. Особенно это проявляется при обучении с использованием критерия максимума правдоподобия. В связи с этим в последнее время исследования в области построения систем автоматического распознавания речи направлены на поиск гибридных моделей, объединяющих достоинства СММ и ИНС [14].Рассмотрение гибридных моделей СММ/ИНС выходит за рамки данной статьи. Однако в их основе по-прежнему лежат СММ, поэтому результаты данных работы (оптимизация алгоритмов обучения и декодирования СММ с помощью GPU) могут быть успешно применены и при построении гибридных моделей.Краткое описание алгоритма обучения Скрытой Марковской МоделиПроцесс обучения Скрытой Марковской Модели заключается в определении на основе набора обучающих образцов следующих параметров:1) матрицы вероятностей переходов между состояниями Аш-2) параметров Гауссовых смесей (математическое ожидание, матрица ковариации и весового коэффициента) для каждого состояния.Для решения этих задач совместно применяются два итерационных алгоритма: forward-backward и Baum-Welch re-estemation [2].В алгоритме forward-backward вводятся две функции: прямого распространения вероятности a (t) и обратного P (t).Значение величины aj (t) представляет собой вероятность наблюдения последовательности векторов {xj, x2,…, xT} и нахождения СММ в состоянии j в момент времени t:aj (t) = P (Xi, x2,…, X, | state, = j). (1)Величины aj (t) и a (t-1) связаны итерационным выражением:aj (t) =Z a (t -1) Ajf, (x)¦(2)Обратная функция р^) представляет собой вероятность нахождения СММ в состоянии ] в момент времени I с последующим наблюдением последовательности |хж х№ 2,…, хт|:в (О = р (Х,+1,х1+2,…, Х | = ]). (3)Величины р^) и в^+1) связаны аналогичным тождеством:в (t) = Z Af (xt +i)e (t +1).(4)1A =Z ,=1 P Z «a (t) Ajf (x-+1)Pr (t+1)(5)Для каждого состояния — и для каждой компоненты Гауссовой смеси т математическое ожидание, матрица ковариации и вес определяются следующими выражениямиZ1, Z!, j (t) x:zI z h j (t) '(6)Z Z T= 1 j (t)(x: -Vjm)(x -Vjm)TZR ZT: L- (t)sL^: =1^ t=1 Jmy '-w Z1. Z ^! j (t)j = ZR=1 ZT=1 Lj (t).(7)(8)Величины а (Ь) и Р (1-) позволяют определить вероятность нахождения СММ в состоянии ] в момент времени I при наблюдении последовательности |х1, х2,***, хт}:11)=р, а в)'где Р=аЖ^) — общая вероятность наблюдения последовательности |х (+1,х (+2,…, хт| данной СММ.Алгоритм Баума-Велча (Bаum-Welch re-este-таМоп) на очередном шаге обучения позволяет, используя вышеприведенные выражения, сделать переоценку параметров модели [2].Пусть имеется Ё обучающих образцов, тогда вероятность перехода из состояния I в состояние ] определяется как:Для качественного обучения Скрытой Марковской Модели требуется множество образцов сигнала: от нескольких десятков до нескольких сотен и тысяч экземпляров. Также необходимо соблюдать условие линейной независимости обучающих образцов, в противном случае в процессе обучения происходит вырождение матрицы ковариации, следствием чего является полная неработоспособность модели [2].Алгоритм максимума правдоподобия (Витерби)Суть алгоритма декодирования СММ заключается в поиске последовательности состояний, при прохождении которой наблюдаемая входная последовательность имела бы максимальную вероятность. Схема переходов и выбора цепочки состояний в момент времени I изображена на рис. 2.Pn (t) = Pi (t -1) + q2Pl2(t) = Pi (t -1) + а22Pin (t) = Pn (t «Ч + an2P2(t) = max[pii (t), P22 (t)v? Pin (t)](S1 (c)-Ж S2)П2 (Sn 1 t-1 © tРис. 2. Алгоритм декодирования ВитербиВ момент времени t осуществляется переход в состояние I из всех предыдущих состояний, после чего выбирается последовательность, имеющая максимальную суммарную вероятность в моменты времени1 и t. Время выполнения алгоритма пропорционально длине последовательности Ь и квадрату количества состояний N. Алгоритм имеет сложность О (Ж2Ь).Декодирование последовательности одной моделью не является ресурсоемкой задачей. Однако при наличии сложной языковой модели СММ объединяются вместе в виде графа, в зависимости от последовательностей следования фонем, и процесс декодирования осуществляется одновременно для множества моделей. В связи с чем алгоритмическая сложность задачи резко возрастает [3].Особенности параллельного программированияна CUDAПрименение современных графических процессоров позволяет получить многократный прирост производительности при решении ряда научных и технических задач. Однако для достижения наилучших результатов необходимо учитывать ряд особенностей [15−18]:i=21) графический процессор (GPU) состоит из нескольких мультипроцессоров, которые, в свою очередь, состоят из ядер. Каждое ядро одновременно выполняет 32 потока (warp). Например, NVidia GeForce GTX 480 состоит из 15×32=480 ядер и параллельно может выполнять до 15 360 легковесных потоков. Потоки объединяются в блоки и сетки блоков. Каждый поток имеет идентифицирующие его координаты-2) максимальной производительности удается достичь при выполнении однотипных действий над большим числом обрабатываемых единиц данных-3) архитектура памяти имеет сложную организацию: глобальная память (объемная, но медленная), локальная память, разделяемая память (быстрая), память констант и т. д. -4) особенности доступа к памяти: для получения максимальной пропускной способности все запросы к памяти должны быть выровнены. Подробное описание и особенности примененияграфических процессоров можно найти в соответствующих руководствах [17].Реализация декодера СММ на CUDAПусть N=(8,16,32) — количество состояний модели- L=50 — длина последовательности- С=32 -число одновременно декодируемых последовательностей одной СММ- Nnn — матрица вероятностей переходов между состояниями- BlN — матрица вероятности наблюдения вектора последовательности XL в состоянии N (C матриц рассчитываются заранее).Для декодирования одной последовательности используются N параллельных потоков, каждый из которых декодирует свое состояние 1… N. Данная схема изображена на рис. 3. Итоговая вероятность выбирается как максимум вероятностей, полученных каждым потоком. Сложность алгоритма для одного потока — O (NxL) [19].Один вычислительный блок CUDA одновременно декодирует C последовательностей (для одной СММ). Таким образом, для декодирования СММ из 32 состояний задействовано NxC=1024 потока, что соответствует максимальному количеству потоков на один мультипроцессор для CUDA версии 2.0.Каждый мультипроцессор используется для декодирования отдельной СММ. В итоге на GPU параллельно происходит декодирование 32×15=480 последовательностей для видеопроцессора NVidia GeForce GTX 480.Разделяемая (быстрая) память используется для хранения матрицы вероятностей A и промежуточных вероятностей для N состояний. Объем необходимой памяти [19] - O (N2+NxC).Реализация алгоритма обучения СММс помощью CUDAПусть R — количество обучающих образцов для одной СММ (32) — N — количество состояний модели (8, 16, 32) — M — количество компонент Гауссовой смеси (16) — D — размерность параметрического вектора (16, 32).Предварительный анализ показал, что в процедуре forward-backward основную долю времени (порядка 95%), при вычислении вероятностей aj (t) и ej (t), занимает расчет вероятности наблюдения вектора xt в состоянии j для модели r — f (xrt). В тоже время эта часть вычислений является менее сложной с алгоритмической точки зрения [2].Размерность параметрического вектора D выбиралась равной warp или половине warp (количеству потоков, выполняемых ядром CUDA одновременно). Это же количество потоков (D) использовалось для реализации матричных операций при вычислении функции плотности вероятностиPi (x) =1D/2 ½(2п) 7exp12(x -Ii)Т 7-x -I)где вектора x, i имеют размерность D, и матрица 7- имеет размерность DxD.Для видеопроцессора GeForce GTX 4В0 каждый мультипроцессор содержит 32 ядра CUDA. Таким образом, на одном мультипроцессоре производится одновременный расчет значений функции вероятности для 32 последовательностей в одном из состояний. Вычисления производятся по всей длине последовательности — т. В свое время, каждый мультипроцессор обрабатывает одно из N состояний. Итоговая схема расчета приведена на рис. 4.Поток 1 Поток 2Рис. 3. Параллельная схема декодированияг=0- 32 потока — fx)1=1- 32 потока -fx)г=31- 32 потока — fx)г=0- 32 потока — fx)г=1- 32 потока — fx)г=31- 32 потока — f (x)г=0- 32 потока -fx)г=1- 32 потока -fx)г=31- 32 потока — fx)1 Мультипроцессор — 2 Мультипроцессор — NСостояние — 2 Состояние — NРис. 4. Параллельная схема вычисления значений вероятности модели во всех состояниях для всех обучающих образцовМультипроцессор -Состояние — 1В результаты работы алгоритма получается массив вероятностейДх,(), который затем используется для вычисления окончательных а (Ь) и в (Ь) на СРи в соответствии с итеративными формулами (1−4). В процессе вычисления одновременно задействовано 32×32×16=16 384 потока.В алгоритме Баума-Велча (формулы 5−8) схема распределения вычислений по ядрам аналогична. Векторные и матричные операции для каждого обучающего образца используют по 32 потока (размерность параметрического вектора). При этом каждый мультипроцессор обрабатывает одновременно 32 обучающих образца. После чего осуществляется редуцирование (свертка) для окончательного расчета величин математического ожидания /лЯ и матрицы ковариации аЯ. Каждый мультипроцессор независимо обрабатывает одно из Ы-состояний модели.Расчет вероятностей переходов между состояниями Ап и весов компонент Гауссовых смесей wiЯ осуществляется с помощью СРи, т. к. все входящие в формулы (5) и (8) величины были предварительно рассчитаны, и для получения окончательных значений не требуются существенные вычислительные затраты [20].ТестированиеДля тестирования алгоритма использовалась вычислительная машина следующей конфигурации:Таблица 1. Результаты тестирования алгоритмов forward-backward и Baum~We!ch re-estimation1Intel CoreЦентральный процессор i7 930 2,8 ГГц.Операционная система — Windows 7 64-Bit. Оперативная память — Kingston 12 Gb RAM DDR3.Видеокарта — NVidia GeForce GTX 580 (1536 Mb, 512 ядер CUDA).Версия CUDA — 4.0.Компилятор Microsoft Visual Studio 2008 (векторизация SSE2).Тип данных — double (64 разряда).Результаты тестирования алгоритмов обучения [19] и декодирования [20] приведены в табл. 1,2 соответственно.N D CPU FB, GPU CPU/GPU CPU GPU CPU/GPUс. FB, с. FB BW, с. BW, с. BW8 16 8,688 1,494 5,815 21,926 5,118 4,28416 16 17,286 1,965 8,797 44,753 5,890 7,59832 16 33,881 3,778 8,968 95,077 11,574 8,2158 32 27,578 2,594 10,631 72,714 8,276 8,78616 32 55,241 3,153 17,520 146,278 9,537 15,33832 32 109,676 6,006 18,261 302,857 18,473 16,395Таблица 2. Результаты тестирования алгоритма декодирования СММЧисло состояний (N) Про- цес- сор Коли- чество СММ Количество декодируемых последовательностей Время, мс CPU/GPU8 1 1,54 50,764 1,2216 CPU 1 32 5,70 41,964 3,7332 1 2,120 58,264 1,930Примечание к табл. 1, 2: FB — Forward-Backward. BW -Baum~We!ch. CPU/GPU — отношение времени выполнения CPU к GPU. Время пересылки в память GPU включено в общее время. Наибольший прирост производительности достигается при размере параметрического вектора D=32 и N=32 состояниях модели, т. к. в этом случае задействованы все ресурсы GPU.ВыводыПрименение современных графических процессоров для реализации математического аппарата Скрытых Марковских Моделей позволяет получить существенный прирост производительности относительно центрального процессора, как на этапе обучения, так и при декодировании СММ, особенно при построении моделей с большим количеством состояний.Однако с практической точки зрения целесообразно оптимизировать лишь те участки алгоритма, на которых выполняются ресурсоемкие матричные и векторные операции, в частности вычисление значений функции Гауссовой смеси для обрабатываемых последовательностей и расчет матрицы ковариации. Итеративная часть алгоритма for-ward-backward (формулы 2 и 4) занимает малую часть от общего времени вычисления и сложна в реализации на GPU, поэтому ее оптимизация не представляется целесообразной. Такой же вывод можно сделать относительно расчета матрицы вероятностей переходов между состояниями и весов компонент Гауссовой смеси (формулы 5 и 8).СПИСОК ЛИТЕРАТУРЫ1. Jurafsky D., Martin J.H. Speech and Language processing. 2nd ed. — Englewood Cliffs, New Jersey: Pretince Hall Inc., 2008. — 302 p.2. Hidden Markov Model Toolkit Book. — Cambridge: Cambridge University Engineering Department, 2001−2009. — 399 p.3. Rabiner L.R. A tutorial on Hidden Markov Models and selected applications in speech recognition // Proceedings of The IEEE. -1989. — V. 77. — № 2. — P. 257−286.4. Rabiner L.R., Juang B.H. Fundamentals of Speech Recognition. -Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1993. — 553 p.5. Rabiner L.R., Levinson S.E. Isolated and Connected word Recognition — Theory and Selected Applications // IEEE Transactions on communications. — 1981. — V. 29. — № 5. — P. 301−315.6. Vaseghi S.V. Advanced digital signal processing and noise reduction. 3rd ed. — Chichester, England: John Wiley & amp- Sons, 2006. -453 p.7. Huandg Xuedong. Spoken language processing: a guide to theory, algorithm, and system development. — Englewood Cliffs, New Jersey: Prentice Hall Inc., 2001. — 480 p.8. Айфичер Э. С., Джервис Б. У. Цифровая обработка сигналов: практический подход, 2-е изд. / пер. с англ. — М.: Изд. дом «Вильямс», 2004. — 992 с.9. Vaidyanathan P.P. The Theory of Linear Prediction. — California: Morgan & amp- Claypool, 2008. — 198 p.10. Сорокин В. Н., Цыплихин А. И. Сегментация и распознавание гласных // Информационные процессы. — 2004. — Т. 4. -№ 2. — С. 202−220.11. Гефке Д. А., Зацепин П. М. Применение нейронных сетей для классификации сигналов звукового диапазона // Нейроинформатика, ее приложения и анализ данных: XVII Всеросс. семинар. — Красноярск, 2009. — С. 37−40.Повышение итоговой производительности в несколько десятков раз позволит применять более сложные Марковские Модели, а также увеличить объем материала, используемого при обучении, что представляется перспективным с точки зрения реализации более качественных систем распознавания речи.12. Хайкин С. Нейронные сети: полный курс, 2-е изд. / пер. с англ. — М.: Изд. дом «Вильямс», 2006. — 1104 с.13. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / пер. с польск. И. Д. Рудинского. — М.: Телеком, 2006. — 452 с.14. Маковкин К. А. Гибридные модели — Скрытые марковские модели/Многослойный персептрон — и их применение в системах распознавания речи // Речевые технологии. — 2012. — № 3. -С. 58−83.15. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах. Введение в программирование графических процессоров. — М.: ДМК Пресс, 2011. — 256 c.16. Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. — М.: ДМК Пресс, 2011. — 232 c.17. NVIDIA CUDA SDK 4.0 // NVIDIA Corporation. URL: http: //www. nvidia. com/object/cuda_sdks. html (дата обращения: 10. 07. 2013).18. Гефке Д. А. Применение технологии CUDA для частотного разделение каналов широкополосного тракта // Многоядерные процессоры и параллельное программирование: Регион. науч-но-практ. конф. — Барнаул, 2011. — С. 12−15.19. Гефке Д. А., Зацепин П. М. Применение технологии CUDA для декодирования Скрытых Марковских Моделей // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов: сборник статей II регион. научно-практ. конф. — Барнаул, 2012. — С. 45−51.20. Гефке Д. А., Зацепин П. М. Применение технологии CUDA для обучения Скрытых Марковских Моделей // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов: сборник статей III Всеросс. научно-практ. конф. — Барнаул, 2013. — С. 30−39.Поступила 10. 07. 2013 г.UDC 004. 934NVIDIA CUDA APPLICATION TO TRAIN AND DECODE THE HIDDEN MARKOV MODELSPavel M. Zatsepin,Cand. Sc., Altai State University, 61, Lenin Avenue, 656 049, Barnaul, Russia.E-mail: zpm@phys. asu. ruDenis A. Gefke,Altai State University, 61, Lenin Avenue, 656 049, Barnaul, Russia. E-mail: bspugda@mail. ruThe urgency of the discussed issue is caused by the need of optimization of huge speech corpus'-s processing algorithms required for developing robust automatic speech recognition systems. The evolution of modern multicore processors, specifically graphical processor units GPU, allows improving sufficiently the performance of difficult and resource-intensive digital signal processing algorithms and reducing sufficiently a data processing time.The main aim of the study is to optimize education (Baum~Welch re-estimation) and decoding (Viterbi) algorithms of Hidden Markov Models by parallel programming technology NVIDIA CUDA and to estimate performance increase in comparison within the CPU.The methods used in the study: the search of education and decoding algorithm'-s parts suitable for effective parallel realization by NVIDIA CUDA and its implementation.The results: The authors have developed parallel realization of education and decoding Hidden Markov Models algorithms by GPU and have estimated the performance increase in comparison within the CPU for different model'-s parameters (the number of model state and dimension of a feature vector). The results of the paper can be used both by engineers developing and improving the automatic speech recognition systems and by explorers working on a digital signal processing and artificial intelligence systems.Key words:Speech recognition, parallel computing, Hidden Markov Models, NVIDIA CUDA, Viterbi algorithm, Baum-Welch re-estimation algorithm.REFERENCES1. Jurafsky D., Martin J.H. Speech and Language processing. 2nd ed. Englewood Cliffs, New Jersey: Pretince Hall Inc., 2008. 302 p.2. Hidden Markov Model Toolkit Book. Cambridge, Cambridge University Engineering Department, 2001−2009. 399 p.3. Rabiner L.R. A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE. 1989, vol. 77, no. 2, pp. 257−2864. Rabiner L.R., Juang B.H. Fundamentals of Speech Recognition. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1993. 553 p.5. Rabiner L.R., Levinson S.E. Isolated and Connected word Recognition — Theory and Selected Applications. IEEE Transactions on communications, 1981. vol. 29, no. 5, pp. 301−315.6. Vaseghi S.V. Advanced digital signal processing and noise reduction. 3rd ed. Chichester, England, John Wiley & amp- Sons, 2006. 453 p.7. Huandg Xuedong. Spoken language processing: a guide to theory, algorithm, and system development. Englewood Cliffs, New Jersey, Prentice Hall Inc., 2001. 480 p.8. Ifeachor E.C., Jervis B.W. Digital Signal Processing. A practical approach. 2nd ed. Englewood Cliffs, New Jersey, Pretince Hall Inc., 2004. 992 p.9. Vaidyanathan P.P. The Theory of Linear Prediction. California, Morgan & amp- Claypool, 2008. 198 p.10. Sorokin V.N., Tsyplikhin A.I. Segmentatsiya i raspoznovanie glas-nykh [Segmentation and vocal recognition]. Informatsionnye prot-sessy — Informational processes, 2004, vol. 4, no. 2, pp. 202−220.11. Gefke D.A., Zatsepin P.M. Primenenie neyronnykh setey dlya klassifikatsii signalov zvukovogo diapazona [The application of neural networks for voice signal classification]. NeAroinformati-ka, ee primenenie i analiz dannykh. XVII Vserossiysky seminar [Neuroinformatic, its application and data analyze. XVII Russian conference]. Krasnoyarsk, 2009. pp. 37−40.12. Haykin S. Neural Networks — A Comprehensive Foundation. 2nd ed. New Jersey, Pearson Education Inc., 1999. 823 p.13. Rutkovskaya D., Pilinskiy M., Rutkovskiy L. Neironnie sistemy, geneticheskie algoritmy i nechetkie sistemy [Neural networks, genetic algorithms and fuzzy systems]. Moscow, Telekom, 2006. 452 p.14. Makovkin K.A. Gibridnye modeli — Skrytye Markovskie Modely/ Mnogosloyny pertseptron — i ikh primenenie v sistemakh avtoma-ticheskogo raspoznavaniya rechi [The Hybrid models — Hidden Markov Models/Multi-Layer Perceptron — and its application in automatic speech recognition systems]. Rechevye tekhnologii -Speech Technologies, 2012, no. 3, pp. 58−83.15. Sanders J., Kandrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming Code. Boston, Addison-Wes-ley Professional, 2010. 312 p.16. Boreskov A.V., Harlamov A.A. Osnovy raboty s CUDA [Basic usage of CUDA]. Moscow, DMK Publ., 2011. 232 p.17. NVIDIA CUDA SDK 4.0. NVIDIA Corporation. Avaible at: http: //www. nvidia. com/object/cuda_sdks. html (accessed 10 July 2013).18. Gefke D.A., Zatsepin P.M. Primenenie tekhnology CUDA dlya de-kodirovaniya Skrytykh Markovskikh Modeley [The application of CUDA technology for decoding Hidden Markov Models]. Mnogoy-adernye protsessory, parallelnoe programmirovanie, PLIS, siste-my obrabotki signalov. Sbornik statey III Regionalnoy konferent-sii [Multicore processors, parallel programming, PLD, digital signal processing systems. Paper collection of the III Regional science-practical conference]. Barnaul, 2012. pp. 45−51.19. Gefke D.A., Zatsepin P.M. Primenenie tekhnology CUDA dlya ob-ucheniya Skrytykh Markovskikh Modeley [The application of CU-DA technology for education of Hidden Markov Models]. Mnogo-yadernye processory, parallelnoe programmirovanie, PLIS, siste-my obrabotki signalov. Sbornik statey III Vserossiyskoy konfe-rentsii [Multicore processors, parallel programming, PLD, digital signal processing systems. Paper collection of the III Russian science-practical conference]. Barnaul, 2013. pp. 30−3920. Gefke D.A. Primenenie tekhnologii CUDA dlya chastotnogo raz-deleniya kanalov shirokopolosnogo trakta [The application of CUDA technology for frequency-separation of wideband signal]. Mnogoyadernye protsessory i parallelnoe programmirovanie. Re-gionalnaya nauchno-prakticheskaya konferentsiya [Multicore processors and parallel programming. Regional science-practical conference]. Barnaul, 2011. pp. 12−15.

westud.ru

Реферат cuda

Реферат на тему:

План:

Введение
• 1 Программная архитектура
• 2 Оборудование
• 3 Преимущества
• 4 Ограничения
• 5 Поддерживаемые GPU и графические ускорители[3]
• 6 Особенности и спецификации различных версий
• 7 Пример
• 8 CUDA как предмет в вузах
Примечания

Введение

CUDA (англ. Compute Unified Device Architecture) — программно-аппаратная архитектура, позволяющая производить вычисления с использованием графических процессоров NVIDIA, поддерживающих технологию GPGPU (произвольных вычислений на видеокартах). Архитектура CUDA впервые появились на рынке с выходом чипа NVIDIA восьмого поколения — G80 и присутствует во всех последующих сериях графических чипов, которые используются в семействах ускорителей GeForce, Quadro и Tesla.

CUDA SDK позволяет программистам реализовывать на специальном упрощённом диалекте языка программирования Си алгоритмы, выполнимые на графических процессорах NVIDIA, и включать специальные функции в текст программы на Cи. CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью, организовывать на нём сложные параллельные вычисления.

1. Программная архитектура

Первоначальная версия CUDA SDK была представлена 15 февраля 2007 года. В основе CUDA API лежит язык Си с некоторыми ограничениями. Для успешной трансляции кода на этом языке, в состав CUDA SDK входит собственный Си-компилятор командной строки nvcc компании Nvidia. Компилятор nvcc создан на основе открытого компилятора Open64 и предназначен для трансляции host-кода (главного, управляющего кода) и device-кода (аппаратного кода) (файлов с расширением .cu) в объектные файлы, пригодные в процессе сборки конечной программы или библиотеки в любой среде программирования, например в NetBeans.

Использует grid-модель памяти, кластерное моделирование потоков и SIMD инструкции. Применим в основном для высокопроизводительных графических вычислений и разработок NVIDIA-совместимого графического API. Включена возможность подключения к приложениям, использующим OpenGL и Microsoft Direct3D 9. Создан в версиях для Linux, Mac OS X, Windows.

22 марта 2010 года nVidia выпустила CUDA Toolkit 3.0, который содержал поддержку OpenCL.[1]

2. Оборудование

Первая серия оборудования, поддерживающая CUDA SDK, G8x, имела 32-битный векторный процессор одинарной точности, использующий CUDA SDK как API (CUDA поддерживает тип double языка Си, однако сейчас его точность понижена до 32-битного с плавающей запятой). Более поздние процессоры GT200 имеют поддержку 64-битной точности (только для SFU), но производительность значительно хуже, чем для 32-битной точности (из-за того что SFU всего 2 на каждый потоковый мультипроцессор, а скалярных процессоров 8). Графический процессор организует аппаратную многопоточность, что позволяет задействовать все ресурсы графического процессора. Таким образом, открывается перспектива переложить функции физического ускорителя на графический ускоритель (пример реализации — nVidia PhysX). Также открываются широкие возможности использования графического оборудования компьютера для выполнения сложных неграфических вычислений: например, в вычислительной биологии и в иных отраслях науки.

3. Преимущества

По сравнению с традиционным подходом к организации вычислений общего назначения посредством возможностей графических API, у архитектуры CUDA отмечают следующие преимущества в этой области:

• Интерфейс программирования приложений CUDA (CUDA API) основан на стандартном языке программирования Си с некоторыми ограничениями. По мнению разработчиков, это должно упростить и сгладить процесс изучения архитектуры CUDA[2]
• Разделяемая между потоками память (shared memory) размером в 16 Кб может быть использована под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур
• Более эффективные транзакции между памятью центрального процессора и видеопамятью
• Полная аппаратная поддержка целочисленных и побитовых операций

4. Ограничения

• Все функции, выполнимые на устройстве, не поддерживают рекурсии (в версии CUDA Toolkit 3.1 поддерживает указатели и рекурсию) и имеют некоторые другие ограничения
• Архитектуру CUDA поддерживает и развивает только производитель NVidia

5. Поддерживаемые GPU и графические ускорители[3]

Перечень устройств от производителя оборудования Nvidia с заявленной полной поддержкой технологии CUDA приведён на официальном сайте Nvidia: CUDA-Enabled GPU Products (англ.).

Фактически же, в настоящее время на рынке аппаратных средств для ПК поддержку технологии CUDA обеспечивают следующие периферийные устройства[3]:

Модели Tesla C1060, Tesla S1070, Tesla C2050/C2070, Tesla M2050/M2070, Tesla S2050 позволяют производить вычисления на GPU с двойной точностью.

6. Особенности и спецификации различных версий

7. Пример

Этот пример кода на C загрузки текстур из изображения в массив на GPU:

Пример программы на языке Python, перемножающий матрицы средствами GPU. Взаимодействие идёт с использованием PyCUDA [5]

8. CUDA как предмет в вузах

По состоянию на декабрь 2009 года, программная модель CUDA преподается в 269 университетах по всему миру. В России обучающие курсы по CUDA читаются в Санкт-Петербургском Политехническом Университете, Московском, Нижегородском, Санкт-Петербургском, Казанском, Новосибирском, Омском и Пермском государственных университетах, Международном университете природы общества и человека «Дубна», Объединённом институте ядерных исследований, Московском институте электронной техники, Ивановском государственном энергетическом университете, БГТУ им. В. Г. Шухова, МГТУ им. Баумана, РХТУ им.Менделеева, Российском научном центре «Курчатовский институт», Межрегиональном суперкомпьютерном центре РАН, Таганрогском технологическом институте (ТТИ ЮФУ).[6] Кроме того, в декабре 2009 года было объявлено о начале работы первого в России научно-образовательного центра «Параллельные вычисления», расположенного в городе Дубна, в задачи которого входят обучение и консультации по решению сложных вычислительных задач на GPU.[6]

На Украине курсы по CUDA читаются в Киевском институте системного анализа.[6]

wreferat.baza-referat.ru

"Применение технологии nvidia CUDA для обучения и декодирования Скрытых Марковских моделей"

Выдержка из работы

УДК 004. 934ПРИМЕНЕНИЕ ТЕХНОЛОГИИ NVIDIA CUDA ДЛЯ ОБУЧЕНИЯ И ДЕКОДИРОВАНИЯ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙЗацепин Павел Михайлович,канд. физ. -мат. наук, доцент, заведующий кафедрой вычислительной техники и электроники Физико-технического факультета Алтайского Государственного университета, Россия, 656 049, г. Барнаул, пр. Ленина, 61.E-mail: zpm@phys. asu. ruГефке Денис Алексеевич,аспирант кафедры вычислительной техники и электроники Физико-технического факультета Алтайского Государственного университета, Россия, 656 049, г. Барнаул, пр. Ленина, 61. E-mail: bspugda@mail. ruАктуальность работы обусловлена необходимостью оптимизации алгоритмов обработки больших речевых баз данных при разработке качественных систем автоматического распознавания речи. Развитие современных многоядерных процессоров, в частности графических процессоров GPU, позволяет получить существенный прирост производительности при реализации сложных ресурсоемких алгоритмов цифровой обработки сигналов и значительно сократить время обработки данных.Цель работы: оптимизация алгоритмов обучения (Baum-Welch re-estimation) и декодирования (Витерби) Скрытых Марковских Моделей с помощью технологии параллельного программирования NVIDIA CUDA и оценка прироста производительности относительно центрального процессора.Методы исследования: определение участков алгоритмов обучения и декодирования Скрытых Марковских Моделей, подходящих для эффективной параллельной реализации с учетом особенности программной модели CUDA, с последующей реализацией. Результаты: Получена практическая параллельная реализация алгоритмов обучения и декодирования Скрытых Марковских Моделей с помощью графического процессора GPU. Произведена оценка прироста производительности относительно центрального процессора для различных параметров модели (количества состояний и размерности параметрического вектора). Результаты данной работы могут быть полезны как инженерам, работающим над созданием и улучшением систем автоматического распознавания речи, так и исследователям, работающим в области обработки сигналов и искусственного интеллекта.Ключевые слова:Распознавание речи, параллельные вычисления, Скрытые Марковские Модели, NVIDIA CUDA, алгоритм Витерби, алгоритм Баума~Велча.ВведениеМатематический аппарат Скрытых Марковских Моделей (СММ) представляет собой универсальный инструмент моделирования стохастических процессов, для описания которых не существует точных математических моделей, а их свойства меняются с течением времени в соответствии с некоторыми статистическими законами. Наиболее широкое применение СММ нашли при решении таких задач, как распознавание речи, анализа последовательностей ДНК и ряда других [1].Современные системы распознавания речи предполагают наличие нескольких сотен, а то и тысяч Скрытых Марковских Моделей и их сочетаний, вследствие чего работа со СММ связана со значительными вычислительными затратами, как на этапе обучения — при обработке огромного массива речевых данных, так и при последующем декодировании — в зависимости от сложности языковой модели. Например, обучение хорошей помехозащищенной дикторо-независимой системы распознавания слитной речи может занять несколько недель, а то и месяцев. Поэтому задача оптимизации алгоритмов обработки СММ остается актуальной в настоящее время [2, 3].Применение современных технологий параллельного программирования, в частности графиче-ских мультипроцессоров, позволяет получить значительный прирост производительности и перейти на качественно более высокий уровень в решении задач распознавания речи.Целью данной работы является оптимизация алгоритмов обучения Скрытых Марковских Моделей (Ваит^е1сЬ re-estemation и ^та^-Ьаск-ward) и алгоритма декодирования (обобщенный алгоритм Витерби) с помощью графического процессора (CUDA) и оценка прироста производительности относительно центрального процессора (СРи).Структура Скрытой Марковской МоделиВ основе Скрытой Марковской Модели лежит конечный автомат, состоящий из N состояний. Переходы между состояниями в каждый дискретный момент времени t не являются детерминированными, а происходят в соответствии с некоторым вероятностным законом и описываются матрицей вероятностей переходов Лщ. Схематическое изображение диаграммы переходов между состояниями в СММ приведено на рис. 1 [4].При каждом переходе в новое состояние I в момент времени t происходит генерация выходного значения в соответствии с функцией распределения Результатом работы СММ является последо-вательность параметрических векторов {x1,x2,^, xT} длиной T [5].Рис. 1. Структурная схема переходов в СММНа практике, как правило, решается обратная задача: при известной структуре Марковской Модели требуется определить, какова вероятность, что наблюдаемая последовательность {xj, x2,…, xT} может быть сгенерирована данной СММ [6].Таким образом, основными параметрами СММ являются:1) N — количество состояний-2) матрица вероятностей переходов ANN между состояниями-3) N функций плотности вероятностиf (x). Функция плотности вероятности f (x) описывается, как правило, взвешенной Гауссовой смесью:Mf (X) =? WiPi (X),/=1где M — количество компонент смеси- wt — вес компонента смеси, аp (x) — нормальное распределение вероятностей для. D-мерного случая:*(Х) = еХР{& quot-2(x-*,) 1 Г (x-V,)]¦где v — вектор математического ожидания- -матрица ковариации.Работа со Скрытыми Марковскими Моделями, как и с любой другой адаптивной системой, осуществляется в 2 этапа: обучение — алгоритм Бау-ма-Велча (Baum-Welch re-estemation), декодирование — алгоритм максимума правдоподобия (Ви-терби) [7].В качестве параметрического вектора чаще всего используют мел-частотные кепстральные коэффициенты [8] (MFCC — mel-frequency cepstral coefficients), либо коэффициенты линейного предсказания [9] (LPC — linear prediction coefficients), а также их первые и вторые производные. Данные преобразования, в силу их гармонической природы, позволяют с высокой достоверностью локализовать вокализованные составляющие сигнала (гласные звуки) [10]. В тоже время, речевой сигнал имеет более сложную природу и помимо вокализованных звуков содержит ударные, шипящие и прочие составляющие. Поэтому для обработки речевого сигнала представляется перспективным применение других операторов, например Вейвлет-преобразований [11], рассмотрение которых выходит за рамки данной работы, т. к. реализованные алгоритмы являются универсальными и не зависят от природы параметрического вектора.Сравнение Скрытой Марковской Модели и искусственных нейронных сетей при решении задачи автоматического распознавания речиВ настоящее время Скрытые Марковские Модели являются основой большинства успешных систем автоматического распознавания речи. Это связано с наличием ряда важных свойств, которыми обладают СММ по сравнению с основной альтернативной моделью классификации — искусственными нейронными сетями [12, 13]:1) возможность моделирования длительных временных последовательностей (слов или целых высказываний), в то время как искусственные нейронные сети (ИНС) хорошо подходят для классификации кратковременных акустико-фонетических единиц, а их эффективность сильно снижается, когда на входе появляется некоторая динамика, т. е. образы подвержены, например, нелинейным изменениям во времени-2) обучение ИНС при построении систем автоматического распознавания речи происходит, как правило, с учителем и требует точной временной разметки на фонемы обучающей выборки, что является чрезвычайно трудоемкой задачей для современных речевых баз данных. В тоже время обучение СММ может производиться без точной временной разметки-3) возможность объединения, совместного обучения и декодирования набора СММ, представляющих отдельные фонемы, в соответствии с языковой моделью. Говоря простым языком, СММ хорошо адаптированы для построения составных моделей из исходных «примитивных» языковых элементов — фонем.В то же время СММ обладают существенным недостатком по сравнению с ИНС — слабой дискриминантной мощностью, т. е. возможностью разделять классы образов. Особенно это проявляется при обучении с использованием критерия максимума правдоподобия. В связи с этим в последнее время исследования в области построения систем автоматического распознавания речи направлены на поиск гибридных моделей, объединяющих достоинства СММ и ИНС [14].Рассмотрение гибридных моделей СММ/ИНС выходит за рамки данной статьи. Однако в их основе по-прежнему лежат СММ, поэтому результаты данных работы (оптимизация алгоритмов обучения и декодирования СММ с помощью GPU) могут быть успешно применены и при построении гибридных моделей.Краткое описание алгоритма обучения Скрытой Марковской МоделиПроцесс обучения Скрытой Марковской Модели заключается в определении на основе набора обучающих образцов следующих параметров:1) матрицы вероятностей переходов между состояниями Аш-2) параметров Гауссовых смесей (математическое ожидание, матрица ковариации и весового коэффициента) для каждого состояния.Для решения этих задач совместно применяются два итерационных алгоритма: forward-backward и Baum-Welch re-estemation [2].В алгоритме forward-backward вводятся две функции: прямого распространения вероятности a (t) и обратного P (t).Значение величины aj (t) представляет собой вероятность наблюдения последовательности векторов {xj, x2,…, xT} и нахождения СММ в состоянии j в момент времени t:aj (t) = P (Xi, x2,…, X, | state, = j). (1)Величины aj (t) и a (t-1) связаны итерационным выражением:aj (t) =Z a (t -1) Ajf, (x)¦(2)Обратная функция р^) представляет собой вероятность нахождения СММ в состоянии ] в момент времени I с последующим наблюдением последовательности |хж х№ 2,…, хт|:в (О = р (Х,+1,х1+2,…, Х | = ]). (3)Величины р^) и в^+1) связаны аналогичным тождеством:в (t) = Z Af (xt +i)e (t +1).(4)1A =Z ,=1 P Z «a (t) Ajf (x-+1)Pr (t+1)(5)Для каждого состояния — и для каждой компоненты Гауссовой смеси т математическое ожидание, матрица ковариации и вес определяются следующими выражениямиZ1, Z!, j (t) x:zI z h j (t) '(6)Z Z T= 1 j (t)(x: -Vjm)(x -Vjm)TZR ZT: L- (t)sL^: =1^ t=1 Jmy '-w Z1. Z ^! j (t)j = ZR=1 ZT=1 Lj (t).(7)(8)Величины а (Ь) и Р (1-) позволяют определить вероятность нахождения СММ в состоянии ] в момент времени I при наблюдении последовательности |х1, х2,***, хт}:11)=р, а в)'где Р=аЖ^) — общая вероятность наблюдения последовательности |х (+1,х (+2,…, хт| данной СММ.Алгоритм Баума-Велча (Bаum-Welch re-este-таМоп) на очередном шаге обучения позволяет, используя вышеприведенные выражения, сделать переоценку параметров модели [2].Пусть имеется Ё обучающих образцов, тогда вероятность перехода из состояния I в состояние ] определяется как:Для качественного обучения Скрытой Марковской Модели требуется множество образцов сигнала: от нескольких десятков до нескольких сотен и тысяч экземпляров. Также необходимо соблюдать условие линейной независимости обучающих образцов, в противном случае в процессе обучения происходит вырождение матрицы ковариации, следствием чего является полная неработоспособность модели [2].Алгоритм максимума правдоподобия (Витерби)Суть алгоритма декодирования СММ заключается в поиске последовательности состояний, при прохождении которой наблюдаемая входная последовательность имела бы максимальную вероятность. Схема переходов и выбора цепочки состояний в момент времени I изображена на рис. 2.Pn (t) = Pi (t -1) + q2Pl2(t) = Pi (t -1) + а22Pin (t) = Pn (t «Ч + an2P2(t) = max[pii (t), P22 (t)v? Pin (t)](S1 (c)-Ж S2)П2 (Sn 1 t-1 © tРис. 2. Алгоритм декодирования ВитербиВ момент времени t осуществляется переход в состояние I из всех предыдущих состояний, после чего выбирается последовательность, имеющая максимальную суммарную вероятность в моменты времени1 и t. Время выполнения алгоритма пропорционально длине последовательности Ь и квадрату количества состояний N. Алгоритм имеет сложность О (Ж2Ь).Декодирование последовательности одной моделью не является ресурсоемкой задачей. Однако при наличии сложной языковой модели СММ объединяются вместе в виде графа, в зависимости от последовательностей следования фонем, и процесс декодирования осуществляется одновременно для множества моделей. В связи с чем алгоритмическая сложность задачи резко возрастает [3].Особенности параллельного программированияна CUDAПрименение современных графических процессоров позволяет получить многократный прирост производительности при решении ряда научных и технических задач. Однако для достижения наилучших результатов необходимо учитывать ряд особенностей [15−18]:i=21) графический процессор (GPU) состоит из нескольких мультипроцессоров, которые, в свою очередь, состоят из ядер. Каждое ядро одновременно выполняет 32 потока (warp). Например, NVidia GeForce GTX 480 состоит из 15×32=480 ядер и параллельно может выполнять до 15 360 легковесных потоков. Потоки объединяются в блоки и сетки блоков. Каждый поток имеет идентифицирующие его координаты-2) максимальной производительности удается достичь при выполнении однотипных действий над большим числом обрабатываемых единиц данных-3) архитектура памяти имеет сложную организацию: глобальная память (объемная, но медленная), локальная память, разделяемая память (быстрая), память констант и т. д. -4) особенности доступа к памяти: для получения максимальной пропускной способности все запросы к памяти должны быть выровнены. Подробное описание и особенности примененияграфических процессоров можно найти в соответствующих руководствах [17].Реализация декодера СММ на CUDAПусть N=(8,16,32) — количество состояний модели- L=50 — длина последовательности- С=32 -число одновременно декодируемых последовательностей одной СММ- Nnn — матрица вероятностей переходов между состояниями- BlN — матрица вероятности наблюдения вектора последовательности XL в состоянии N (C матриц рассчитываются заранее).Для декодирования одной последовательности используются N параллельных потоков, каждый из которых декодирует свое состояние 1… N. Данная схема изображена на рис. 3. Итоговая вероятность выбирается как максимум вероятностей, полученных каждым потоком. Сложность алгоритма для одного потока — O (NxL) [19].Один вычислительный блок CUDA одновременно декодирует C последовательностей (для одной СММ). Таким образом, для декодирования СММ из 32 состояний задействовано NxC=1024 потока, что соответствует максимальному количеству потоков на один мультипроцессор для CUDA версии 2.0.Каждый мультипроцессор используется для декодирования отдельной СММ. В итоге на GPU параллельно происходит декодирование 32×15=480 последовательностей для видеопроцессора NVidia GeForce GTX 480.Разделяемая (быстрая) память используется для хранения матрицы вероятностей A и промежуточных вероятностей для N состояний. Объем необходимой памяти [19] - O (N2+NxC).Реализация алгоритма обучения СММс помощью CUDAПусть R — количество обучающих образцов для одной СММ (32) — N — количество состояний модели (8, 16, 32) — M — количество компонент Гауссовой смеси (16) — D — размерность параметрического вектора (16, 32).Предварительный анализ показал, что в процедуре forward-backward основную долю времени (порядка 95%), при вычислении вероятностей aj (t) и ej (t), занимает расчет вероятности наблюдения вектора xt в состоянии j для модели r — f (xrt). В тоже время эта часть вычислений является менее сложной с алгоритмической точки зрения [2].Размерность параметрического вектора D выбиралась равной warp или половине warp (количеству потоков, выполняемых ядром CUDA одновременно). Это же количество потоков (D) использовалось для реализации матричных операций при вычислении функции плотности вероятностиPi (x) =1D/2 ½(2п) 7exp12(x -Ii)Т 7-x -I)где вектора x, i имеют размерность D, и матрица 7- имеет размерность DxD.Для видеопроцессора GeForce GTX 4В0 каждый мультипроцессор содержит 32 ядра CUDA. Таким образом, на одном мультипроцессоре производится одновременный расчет значений функции вероятности для 32 последовательностей в одном из состояний. Вычисления производятся по всей длине последовательности — т. В свое время, каждый мультипроцессор обрабатывает одно из N состояний. Итоговая схема расчета приведена на рис. 4.Поток 1 Поток 2Рис. 3. Параллельная схема декодированияг=0- 32 потока — fx)1=1- 32 потока -fx)г=31- 32 потока — fx)г=0- 32 потока — fx)г=1- 32 потока — fx)г=31- 32 потока — f (x)г=0- 32 потока -fx)г=1- 32 потока -fx)г=31- 32 потока — fx)1 Мультипроцессор — 2 Мультипроцессор — NСостояние — 2 Состояние — NРис. 4. Параллельная схема вычисления значений вероятности модели во всех состояниях для всех обучающих образцовМультипроцессор -Состояние — 1В результаты работы алгоритма получается массив вероятностейДх,(), который затем используется для вычисления окончательных а (Ь) и в (Ь) на СРи в соответствии с итеративными формулами (1−4). В процессе вычисления одновременно задействовано 32×32×16=16 384 потока.В алгоритме Баума-Велча (формулы 5−8) схема распределения вычислений по ядрам аналогична. Векторные и матричные операции для каждого обучающего образца используют по 32 потока (размерность параметрического вектора). При этом каждый мультипроцессор обрабатывает одновременно 32 обучающих образца. После чего осуществляется редуцирование (свертка) для окончательного расчета величин математического ожидания /лЯ и матрицы ковариации аЯ. Каждый мультипроцессор независимо обрабатывает одно из Ы-состояний модели.Расчет вероятностей переходов между состояниями Ап и весов компонент Гауссовых смесей wiЯ осуществляется с помощью СРи, т. к. все входящие в формулы (5) и (8) величины были предварительно рассчитаны, и для получения окончательных значений не требуются существенные вычислительные затраты [20].ТестированиеДля тестирования алгоритма использовалась вычислительная машина следующей конфигурации:Таблица 1. Результаты тестирования алгоритмов forward-backward и Baum~We!ch re-estimation1Intel CoreЦентральный процессор i7 930 2,8 ГГц.Операционная система — Windows 7 64-Bit. Оперативная память — Kingston 12 Gb RAM DDR3.Видеокарта — NVidia GeForce GTX 580 (1536 Mb, 512 ядер CUDA).Версия CUDA — 4.0.Компилятор Microsoft Visual Studio 2008 (векторизация SSE2).Тип данных — double (64 разряда).Результаты тестирования алгоритмов обучения [19] и декодирования [20] приведены в табл. 1,2 соответственно.N D CPU FB, GPU CPU/GPU CPU GPU CPU/GPUс. FB, с. FB BW, с. BW, с. BW8 16 8,688 1,494 5,815 21,926 5,118 4,28416 16 17,286 1,965 8,797 44,753 5,890 7,59832 16 33,881 3,778 8,968 95,077 11,574 8,2158 32 27,578 2,594 10,631 72,714 8,276 8,78616 32 55,241 3,153 17,520 146,278 9,537 15,33832 32 109,676 6,006 18,261 302,857 18,473 16,395Таблица 2. Результаты тестирования алгоритма декодирования СММЧисло состояний (N) Про- цес- сор Коли- чество СММ Количество декодируемых последовательностей Время, мс CPU/GPU8 1 1,54 50,764 1,2216 CPU 1 32 5,70 41,964 3,7332 1 2,120 58,264 1,930Примечание к табл. 1, 2: FB — Forward-Backward. BW -Baum~We!ch. CPU/GPU — отношение времени выполнения CPU к GPU. Время пересылки в память GPU включено в общее время. Наибольший прирост производительности достигается при размере параметрического вектора D=32 и N=32 состояниях модели, т. к. в этом случае задействованы все ресурсы GPU.ВыводыПрименение современных графических процессоров для реализации математического аппарата Скрытых Марковских Моделей позволяет получить существенный прирост производительности относительно центрального процессора, как на этапе обучения, так и при декодировании СММ, особенно при построении моделей с большим количеством состояний.Однако с практической точки зрения целесообразно оптимизировать лишь те участки алгоритма, на которых выполняются ресурсоемкие матричные и векторные операции, в частности вычисление значений функции Гауссовой смеси для обрабатываемых последовательностей и расчет матрицы ковариации. Итеративная часть алгоритма for-ward-backward (формулы 2 и 4) занимает малую часть от общего времени вычисления и сложна в реализации на GPU, поэтому ее оптимизация не представляется целесообразной. Такой же вывод можно сделать относительно расчета матрицы вероятностей переходов между состояниями и весов компонент Гауссовой смеси (формулы 5 и 8).СПИСОК ЛИТЕРАТУРЫ1. Jurafsky D., Martin J.H. Speech and Language processing. 2nd ed. — Englewood Cliffs, New Jersey: Pretince Hall Inc., 2008. — 302 p.2. Hidden Markov Model Toolkit Book. — Cambridge: Cambridge University Engineering Department, 2001−2009. — 399 p.3. Rabiner L.R. A tutorial on Hidden Markov Models and selected applications in speech recognition // Proceedings of The IEEE. -1989. — V. 77. — № 2. — P. 257−286.4. Rabiner L.R., Juang B.H. Fundamentals of Speech Recognition. -Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1993. — 553 p.5. Rabiner L.R., Levinson S.E. Isolated and Connected word Recognition — Theory and Selected Applications // IEEE Transactions on communications. — 1981. — V. 29. — № 5. — P. 301−315.6. Vaseghi S.V. Advanced digital signal processing and noise reduction. 3rd ed. — Chichester, England: John Wiley & amp- Sons, 2006. -453 p.7. Huandg Xuedong. Spoken language processing: a guide to theory, algorithm, and system development. — Englewood Cliffs, New Jersey: Prentice Hall Inc., 2001. — 480 p.8. Айфичер Э. С., Джервис Б. У. Цифровая обработка сигналов: практический подход, 2-е изд. / пер. с англ. — М.: Изд. дом «Вильямс», 2004. — 992 с.9. Vaidyanathan P.P. The Theory of Linear Prediction. — California: Morgan & amp- Claypool, 2008. — 198 p.10. Сорокин В. Н., Цыплихин А. И. Сегментация и распознавание гласных // Информационные процессы. — 2004. — Т. 4. -№ 2. — С. 202−220.11. Гефке Д. А., Зацепин П. М. Применение нейронных сетей для классификации сигналов звукового диапазона // Нейроинформатика, ее приложения и анализ данных: XVII Всеросс. семинар. — Красноярск, 2009. — С. 37−40.Повышение итоговой производительности в несколько десятков раз позволит применять более сложные Марковские Модели, а также увеличить объем материала, используемого при обучении, что представляется перспективным с точки зрения реализации более качественных систем распознавания речи.12. Хайкин С. Нейронные сети: полный курс, 2-е изд. / пер. с англ. — М.: Изд. дом «Вильямс», 2006. — 1104 с.13. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / пер. с польск. И. Д. Рудинского. — М.: Телеком, 2006. — 452 с.14. Маковкин К. А. Гибридные модели — Скрытые марковские модели/Многослойный персептрон — и их применение в системах распознавания речи // Речевые технологии. — 2012. — № 3. -С. 58−83.15. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах. Введение в программирование графических процессоров. — М.: ДМК Пресс, 2011. — 256 c.16. Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. — М.: ДМК Пресс, 2011. — 232 c.17. NVIDIA CUDA SDK 4.0 // NVIDIA Corporation. URL: http: //www. nvidia. com/object/cuda_sdks. html (дата обращения: 10. 07. 2013).18. Гефке Д. А. Применение технологии CUDA для частотного разделение каналов широкополосного тракта // Многоядерные процессоры и параллельное программирование: Регион. науч-но-практ. конф. — Барнаул, 2011. — С. 12−15.19. Гефке Д. А., Зацепин П. М. Применение технологии CUDA для декодирования Скрытых Марковских Моделей // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов: сборник статей II регион. научно-практ. конф. — Барнаул, 2012. — С. 45−51.20. Гефке Д. А., Зацепин П. М. Применение технологии CUDA для обучения Скрытых Марковских Моделей // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов: сборник статей III Всеросс. научно-практ. конф. — Барнаул, 2013. — С. 30−39.Поступила 10. 07. 2013 г.UDC 004. 934NVIDIA CUDA APPLICATION TO TRAIN AND DECODE THE HIDDEN MARKOV MODELSPavel M. Zatsepin,Cand. Sc., Altai State University, 61, Lenin Avenue, 656 049, Barnaul, Russia.E-mail: zpm@phys. asu. ruDenis A. Gefke,Altai State University, 61, Lenin Avenue, 656 049, Barnaul, Russia. E-mail: bspugda@mail. ruThe urgency of the discussed issue is caused by the need of optimization of huge speech corpus'-s processing algorithms required for developing robust automatic speech recognition systems. The evolution of modern multicore processors, specifically graphical processor units GPU, allows improving sufficiently the performance of difficult and resource-intensive digital signal processing algorithms and reducing sufficiently a data processing time.The main aim of the study is to optimize education (Baum~Welch re-estimation) and decoding (Viterbi) algorithms of Hidden Markov Models by parallel programming technology NVIDIA CUDA and to estimate performance increase in comparison within the CPU.The methods used in the study: the search of education and decoding algorithm'-s parts suitable for effective parallel realization by NVIDIA CUDA and its implementation.The results: The authors have developed parallel realization of education and decoding Hidden Markov Models algorithms by GPU and have estimated the performance increase in comparison within the CPU for different model'-s parameters (the number of model state and dimension of a feature vector). The results of the paper can be used both by engineers developing and improving the automatic speech recognition systems and by explorers working on a digital signal processing and artificial intelligence systems.Key words:Speech recognition, parallel computing, Hidden Markov Models, NVIDIA CUDA, Viterbi algorithm, Baum-Welch re-estimation algorithm.REFERENCES1. Jurafsky D., Martin J.H. Speech and Language processing. 2nd ed. Englewood Cliffs, New Jersey: Pretince Hall Inc., 2008. 302 p.2. Hidden Markov Model Toolkit Book. Cambridge, Cambridge University Engineering Department, 2001−2009. 399 p.3. Rabiner L.R. A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE. 1989, vol. 77, no. 2, pp. 257−2864. Rabiner L.R., Juang B.H. Fundamentals of Speech Recognition. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1993. 553 p.5. Rabiner L.R., Levinson S.E. Isolated and Connected word Recognition — Theory and Selected Applications. IEEE Transactions on communications, 1981. vol. 29, no. 5, pp. 301−315.6. Vaseghi S.V. Advanced digital signal processing and noise reduction. 3rd ed. Chichester, England, John Wiley & amp- Sons, 2006. 453 p.7. Huandg Xuedong. Spoken language processing: a guide to theory, algorithm, and system development. Englewood Cliffs, New Jersey, Prentice Hall Inc., 2001. 480 p.8. Ifeachor E.C., Jervis B.W. Digital Signal Processing. A practical approach. 2nd ed. Englewood Cliffs, New Jersey, Pretince Hall Inc., 2004. 992 p.9. Vaidyanathan P.P. The Theory of Linear Prediction. California, Morgan & amp- Claypool, 2008. 198 p.10. Sorokin V.N., Tsyplikhin A.I. Segmentatsiya i raspoznovanie glas-nykh [Segmentation and vocal recognition]. Informatsionnye prot-sessy — Informational processes, 2004, vol. 4, no. 2, pp. 202−220.11. Gefke D.A., Zatsepin P.M. Primenenie neyronnykh setey dlya klassifikatsii signalov zvukovogo diapazona [The application of neural networks for voice signal classification]. NeAroinformati-ka, ee primenenie i analiz dannykh. XVII Vserossiysky seminar [Neuroinformatic, its application and data analyze. XVII Russian conference]. Krasnoyarsk, 2009. pp. 37−40.12. Haykin S. Neural Networks — A Comprehensive Foundation. 2nd ed. New Jersey, Pearson Education Inc., 1999. 823 p.13. Rutkovskaya D., Pilinskiy M., Rutkovskiy L. Neironnie sistemy, geneticheskie algoritmy i nechetkie sistemy [Neural networks, genetic algorithms and fuzzy systems]. Moscow, Telekom, 2006. 452 p.14. Makovkin K.A. Gibridnye modeli — Skrytye Markovskie Modely/ Mnogosloyny pertseptron — i ikh primenenie v sistemakh avtoma-ticheskogo raspoznavaniya rechi [The Hybrid models — Hidden Markov Models/Multi-Layer Perceptron — and its application in automatic speech recognition systems]. Rechevye tekhnologii -Speech Technologies, 2012, no. 3, pp. 58−83.15. Sanders J., Kandrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming Code. Boston, Addison-Wes-ley Professional, 2010. 312 p.16. Boreskov A.V., Harlamov A.A. Osnovy raboty s CUDA [Basic usage of CUDA]. Moscow, DMK Publ., 2011. 232 p.17. NVIDIA CUDA SDK 4.0. NVIDIA Corporation. Avaible at: http: //www. nvidia. com/object/cuda_sdks. html (accessed 10 July 2013).18. Gefke D.A., Zatsepin P.M. Primenenie tekhnology CUDA dlya de-kodirovaniya Skrytykh Markovskikh Modeley [The application of CUDA technology for decoding Hidden Markov Models]. Mnogoy-adernye protsessory, parallelnoe programmirovanie, PLIS, siste-my obrabotki signalov. Sbornik statey III Regionalnoy konferent-sii [Multicore processors, parallel programming, PLD, digital signal processing systems. Paper collection of the III Regional science-practical conference]. Barnaul, 2012. pp. 45−51.19. Gefke D.A., Zatsepin P.M. Primenenie tekhnology CUDA dlya ob-ucheniya Skrytykh Markovskikh Modeley [The application of CU-DA technology for education of Hidden Markov Models]. Mnogo-yadernye processory, parallelnoe programmirovanie, PLIS, siste-my obrabotki signalov. Sbornik statey III Vserossiyskoy konfe-rentsii [Multicore processors, parallel programming, PLD, digital signal processing systems. Paper collection of the III Russian science-practical conference]. Barnaul, 2013. pp. 30−3920. Gefke D.A. Primenenie tekhnologii CUDA dlya chastotnogo raz-deleniya kanalov shirokopolosnogo trakta [The application of CUDA technology for frequency-separation of wideband signal]. Mnogoyadernye protsessory i parallelnoe programmirovanie. Re-gionalnaya nauchno-prakticheskaya konferentsiya [Multicore processors and parallel programming. Regional science-practical conference]. Barnaul, 2011. pp. 12−15.

bakalavr-info.ru

Технология CUDA в примерах: введение в программирование графических процессоров - 17 Октября 2013

Предисловие Вступление Благодарности Об авторах Глава 1. Почему CUDA? Почему именно теперь? 1.1. О чем эта глава 1.2. Век параллельной обработки    1.2.1. Центральные процессоры 1.3. Развитие GPU-вычислений    1.3.1. Краткая история GPU    1.3.2. Ранние этапы GPU-вычислений 1.4. Технология CUDA    1.4.1. Что такое архитектура CUDA?    1.4.2. Использование архитектуры CUDA 1.5. Применение CUDA    1.5.1. Обработка медицинских изображений    1.5.2. Вычислительная гидродинамика    1.5.3. Науки об окружающей среде 1.6. Резюме Глава 2. Приступая к работе 2.1. О чем эта глава 2.2. Среда разработки    2.2.1. Графические процессоры, поддерживающие архитектуру CUDA    2.2.2. Драйвер устройства NVIDIA    2.2.3. Комплект средств разработки CUDA Development Toolkit    2.2.4. Стандартный компилятор       Windows       Linux       Macintosh OS X 2.3. Резюме Глава 3. Введение в CUDA C 3.1. О чем эта глава 3.2. Первая программа    3.2.1. Здравствуй, мир!    3.2.2. Вызов ядра    3.2.3. Передача параметров 3.3. Получение информации об устройстве 3.4. Использование свойств устройства 3.5. Резюме Глава 4. Параллельное программирование на CUDA C 4.1. О чем эта глава 4.2. Параллельное программирование в CUDA    4.2.1. Сложение векторов       Сложение векторов на CPU       Сложение векторов на GPU    4.2.2. Более интересный пример       Вычисление фрактала Джулиа на CPU       Вычисление фрактала Джулиа на GPU 4.3. Резюме Глава 5. Взаимодействие нитей 5.1. О чем эта глава 5.2. Расщепление параллельных блоков    5.2.1. И снова о сложении векторов       Сложение векторов на GPU с использованием нитей       Сложение более длинных векторов на GPU       Сложение векторов произвольной длины HaGPU    5.2.2. Создание эффекта волн на GPU с использованием нитей 5.3. Разделяемая память и синхронизация    5.3.1. Скалярное произведение    5.3.1. Оптимизация скалярного произведения (неправильная)    5.3.2. Растровое изображение в разделяемой памяти 5.4. Резюме Глава 6. Константная память и события 6.1. О чем эта глава 6.2. Константная память    6.2.1. Введение в метод трассировки лучей    6.2.2. Трассировка лучей на GPU    6.2.3. Трассировка лучей с применением константной памяти    6.2.4. Производительность версии с константной памятью 6.3. Измерение производительности с помощью событий    6.3.1. Измерение производительности трассировщика лучей 6.4. Резюме Глава 7. Текстурная память 7.1. О чем эта глава 7.2. Обзор текстурной памяти 7.3. Моделирование теплообмена    7.3.1. Простая модель теплообмена    7.3.2. Обновление температур    7.3.3. Анимация моделирования    7.3.4. Применение текстурной памяти    7.3.5. Использование двумерной текстурной памяти 7.4. Резюме Глава 8. Интероперабельность с графикой 8.1. О чем эта глава 8.2. Взаимодействие с графикой 8.3. Анимация волн на GPU с применением интероперабельности с графикой    8.3.1. Структура GPUAnimBitmap    8.3.2. И снова об анимации волн на GPU 8.4. Моделирование теплообмена с использованием интероперабельности с графикой 8.5. Интероперабельность с DirectX 8.6. Резюме Глава 9. Атомарные операции 9.1. О чем эта глава 9.2. Вычислительные возможности    9.2.1. Вычислительные возможности NVIDIA GPU    9.2.2. Компиляция программы для GPU с заданным минимальным уровнем вычислительных возможностей 9.3. Обзор атомарных операций 9.4. Вычисление гистограмм    9.4.1. Вычисление гистограммы на CPU    9.4.2. Вычисление гистограммы на GPU       Ядро вычисления гистограммы с применением атомарных операций с глобальной памятью       Ядро вычисления гистограммы с применением атомарных операций с глобальной и разделяемой памятью 9.5. Резюме Глава 10. Потоки 10.1. О чем эта глава 10.2. Блокированная память CPU 10.3. Потоки CUDA 10.4. Использование одного потока CUDA 10.5. Использование нескольких потоков CUDA 10.6. Планирование задач на GPU 10.7. Эффективное использование потоков CUDA 10.8. Резюме Глава 11. CUDA C на нескольких GPU 11.1. О чем эта глава 11.2. Нуль-копируемая память CPU    11.2.1. Вычисление скалярного произведения с применением нуль-копируемой памяти    11.2.2. Производительность нуля-копирования 11.3. Использование нескольких GPU 11.4. Переносимая закрепленная память 11.5. Резюме Глава 12, Последние штрихи 12.1. О чем эта глава 12.2. Инструментальные средства CUDA    12.2.1. CUDA Toolkit    12.2.2. Библиотека CUFFT    12.2.3. Библиотека CUBLAS    12.2.4. Комплект NVIDIA GPU Computing SDK    12.2.5. Библиотека NVIDIA Performance Primitives    12.2.6. Отладка программ на языке CUDA C       CUDA-GDB       NVIDIA Parallel Nsight    12.2.7. CUDA Visual Profiler 12.3. Текстовые ресурсы    12.3.1. Programming Massively Parallel Processors: A Hands-On Approach    12.3.2. CUDA U       Материалы университетских курсов       Журнал DR.DOBB'S    12.3.3. Форумы NVIDIA 12.4. Программные ресурсы    12.4.1. Библиотека CUDA Data Parallel Primitives Library    12.4.2. CULAtools    12.4.3. Интерфейсы к другим языкам 12.5. Резюме Приложение А. Еще об атомарных операциях А.1. И снова скалярное произведение    А. 1.1. Атомарные блокировки    А.1.2. Возвращаясь к скалярному произведению: атомарная блокировка А.2. Реализация хеш-таблицы    А.2.1. Обзор хеш-таблиц    А.2.2. Реализация хеш-таблицы на CPU    А.2.3. Многонитевая реализация хеш-таблицы    А.2.4. Реализация хеш-таблицы на GPU    А.2.5. Производительность хеш-таблицы А.3. Резюме Предметный указатель

radiosit.ru

Смотрите также

• 
  Термопреобразователь сопротивления реферат
• 
  Сурдопедагогика реферат қазақша
• 
  Спецслужбы франции реферат
• 
  Социология кино реферат
• 
  Роберт манделл реферат
• 
  Реферат оливер твист
• 
  Реферат диктатура суллы
• 
  Реферат венецианское стекло
• 
  Радиоприемные устройства реферат
• 
  Психология подсудимого реферат
• 
  Почвенная коррозия реферат