Поступила в редакцию

Математическая морфология.

Электронный математический и медико-биологический журнал. - Т. 13. -

Вып. 2. - 2014. - URL:

http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM

http://www.smolensk.ru/user/sgma/MMORPH/N-42-html/TITL-42.htm

http://www.smolensk.ru/user/sgma/MMORPH/N-42-html/cont.htm

УДК 621.391.161

СПОСОБЫ МОДЕЛИРОВАНИЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОСТВА С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ GPGPU

Ó 2014 г. Зернов М. М., Тимофеев С. С.

(zernov-3.doc)

В работе изложены способы моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU. Предлагаемые способы основаны на использовании параллельных вычислений на графическом процессоре (GPU). Рассмотрен способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и математического пакета для инженерных расчетов, способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и ОЗУ в качестве хранилища данных, а также способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и внутренней памяти GPU в качестве хранилища данных. Также проведен сравнительный анализ способов на эффективность по различным критериям. На основе данных способов моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU разработаны программные средства для моделирования.

Ключевые слова: моделирование, ассоциативное запоминающее устройства, параллельные вычисления, графический процессор GPU, технология GPGPU, математический пакет для инженерных вычислений.

1. Задача моделирования ассоциативного запоминающего устройства

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

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

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

В настоящий момент сложились две основные программные технологии GPGPU вычислений: NVIDIA CUDA и Open CL. Первая технология ориентирована на совместное применение с графическими процессорами компании NVIDIA, вторая – представляет собой открытый стандарт параллельного программирования на различных аппаратных платформах (включая GPU компаний NVIDIA, AMD, встроенное графическое ядро процессоров Intel).

Рассмотрим структуру моделируемого перспективного накопителя (рисунок 1).

$C:\Users\1\Pictures\untitled.png$

Рисунок 1 – Структура моделируемого ассоциативного запоминающего устройства

Ассоциативное запоминающее устройство представляет собой трехмерный массив ассоциативных ячеек с обозначениями осей по длине, высоте и ширине, D, H, W – соответственно. Каждому направлению соответствует свой блок регистровых плоскостей (см. рисунок 2), включающий плоскость фиксации реакции, плоскость маски, поискового аргумента, дополнительного входного аргумента. Особенностью является наличие у каждой плоскости фиксации реакции строки, столбца и регистровой ячейки фиксации реакции [1].

$C:\Users\1\Pictures\untitled.png$

Рисунок 2 – Структура плоскостей фиксации реакции накопителя

Предлагаемые способы моделирования ассоциативной памяти с использованием технологии GPGPU заключаются в использовании параллельных вычислений на графических процессорах GPU, а также использовании внутренней памяти GPU в качестве хранилища данных. Это позволяет существенно увеличить скорость выполнения ассоциативных операций [2,3]. Рассмотрим каждый из способов отдельно.

2. Способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и средств математического пакета для инженерных расчетов

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

Компании NVIDIA и MathWorks объединили усилия, чтобы обеспечить мощь GPU вычислений пользователям MATLAB. Поддерживаемое самым последним выпуском MATLAB ускорение при помощи NVIDIA GPU позволяет пользователям Parallel Computing Toolbox и MATLAB Distributed Computing Server получать результаты еще быстрее.

Поддерживаемые возможности GPU в MATLAB:

·работа с данными при помощи NVIDIA GPU;

·операции в MATLAB с GPU-ускорением;

·поддержку ядер CUDA собственной разработки в приложениях MATLAB;

·вычисления на нескольких NVIDIA GPU при помощи нескольких запущенных одновременно служб MATLAB благодаря Parallel Computing Toolbox в настольном ПК и MATLAB Distributed Computing Server в вычислительном кластере.

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

На рисунке 3 представлена схема взаимодействия программно-аппаратных средств, используемых в данном способе моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU.

$C:\Users\1\Pictures\untitled.png$

Рисунок 3 - Схема взаимодействия программно-аппаратных средств, используемых для моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и средств математического пакета для инженерных расчетов.

Рассмотрим механизм программно-аппаратного взаимодействия при использовании данного способа:

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

2. Эти команды поступают математическому пакету для инженерных расчетов Matlab, происходит обращение к рабочей области памяти.

3. Полученные данные передаются CUDA Parallel Computing Toolbox в качестве входных параметров и вызываются подготовленные ассоциативные функции обработки данных.

4. Результаты ассоциативной обработки записываются в переменные рабочей области математического пакета.

Рассмотрим основные преимущества данного способа:

1. Простота моделирования ассоциативного накопителя. Интуитивно понятный пользовательский интерфейс позволяет пользователю с должным уровнем знаний в области ассоциативной памяти быстро освоить программные средства для моделирования.

2. Широкое распространение математического пакета для инженерных вычислений Matlab.

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

4. Простота программной реализации. Вызов функций параллельной обработки данных благодаря CUDA Parallel Computing Toolbox является для разработчика несложной задачей.

Из минусов данного способа можно выделить следующие особенности:

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

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

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

3. Способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и использованием ОЗУ в качестве хранилища данных

Рассмотрим способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и использованием ОЗУ в качестве хранилища данных. Вычисления над массивами данных осуществляются в данном случае с помощью средств языка программирования OpenCL, предназначенного для программирования для графических процессоров, скомпилированных в dll библиотеку.

Суть способа состоит в следующем.

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

2. Структура данных ассоциативного накопителя находится в ОЗУ и принадлежит пользовательскому интерфейсу.

3. Команды ассоциативной обработки, написанные на языке OpenCL для параллельных вычислений, скомпилированы в GPGPU.dll. В этой библиотека скомпилированы все предусмотренные функции ассоциативной памяти.

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

5. После выполнения операций результаты пересылаются обратно из памяти GPU в ОЗУ.

На рисунке 4 представлена схема взаимодействия программно-аппаратных средств, используемых в данном способе моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU с использованием ОЗУ в качестве хранилища данных.

$C:\Users\1\Pictures\untitled.png$

Рисунок 4 - Схема взаимодействия программно-аппаратных средств, используемых для моделирования ассоциативного запоминающего устройства и использованием технологии GPGPU с использованием ОЗУ в качестве хранилища данных

Рассмотрим основные преимущества данного способа:

2. Сильная защищенность программных средств от неподготовленного пользователя. Наличие компиляции программного кода в виде *.dll приводит к тому, что пользователь не имеет возможность изменять ассоциативные операции по своему усмотрению, что позволяет сохранить систему в целости.

3. Использование параллельных вычислений на GPU в качестве вычислительного ресурса

4. Использование ОЗУ в качестве хранилища данных позволяет при использовании функций прямого доступа в память с использованием вычислений на CPU получить прирост в скорости за счет чтения данных из ОЗУ на CPU. Чтение из ОЗУ на CPU значительно быстрее, нежели чем из внутренней памяти графического процессора GPU на CPU.

5. Данный способ может также использоваться для оттачивания модели ассоциативного накопителя до записи структур данных во внутреннюю память GPU (см. способ моделирования АЗУ с использованием технологии GPGPU и внутренней памяти графического адаптера в качестве хранилища данных). Использование же внутренней памяти GPU является более сложной задачей.

Из минусов данного способа можно выделить следующие особенности:

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

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

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

4. Библиотека GPGPU.dll собирается для конкретного компилятора в отдельности – для графического адаптера от NVIDIA, или от ATI, или от Intel. При этом теряется свойство универсализма, свойственное OpenCL.

Данный способ наиболее подходит пользователю-программисту, желающему использовать методы GPGPU.dll в своем разрабатываемом продукте.

4. Способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и

использованием внутренней памяти графического адаптера в качества хранилища

Рассмотрим способ моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и использованием внутренней памяти графического адаптера в качества хранилища. Вычисления над массивами данных осуществляются с помощью средств языка GPGPU программирования, для примера возьмём более универсальный (относительно аппаратной платформы) язык OpenCL.

Суть способа состоит в следующем:

2. Эти команды поступают разработанному ПО на языке OpenCL. Происходит инициализация вычислительных ядер (потоков/нитей) и подготовка GPU к вычислениям.

3. Все содержимое ячеек ассоциативного накопителя находится во внутренней памяти GPU.

4. С использованием GPU выполняются ассоциативные операции над набором данных, при этом вычисления осуществляются параллельно. Результат операций также помещается во внутреннюю память GPU.

На рисунке 5 представлена схема взаимодействия программно-аппаратных средств, используемых в данном способе моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU с использованием внутренней памяти в качестве графического адаптера.

$C:\Users\1\Pictures\untitled.png$

Рисунок 5 - Схема взаимодействия программно-аппаратных средств, используемых для моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU и использованием внутренней памяти графического адаптера в качестве хранилища данных

Рассмотрим основные преимущества данного способа.

2. Сильная защищенность программных средств от неподготовленного пользователя. Наличие компиляции программного кода приводит к тому, что пользователь не имеет возможность изменять ассоциативные операции по своему усмотрению, что позволяет сохранить систему в целости.

3. Использование параллельных вычислений на GPU в качестве вычислительного ресурса

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

Из минусов данного способа можно выделить следующие особенности.

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

5. Оценка эффективности предложенных алгоритмов

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

Таким образом, исходя из вышесказанного, оценивать предложенные методы будем по следующим критериям:

1) скорость выполнения ассоциативных операций;

2) сложность реализации программного обеспечения на основе предложенных методов;

3) расширяемость программного обеспечения;

4) безопасность программного обеспечения в его взаимодействии с пользователем.

Скорость выполнения ассоциативных операций зависит в предложенных способах от количества операций, выполняемых на CPU и GPU. Наиболее быстрым способом является способ моделирования с использованием внутренней памяти GPU, ведь пересылка данных из ОЗУ в память GPU не происходит, все операции выполняются параллельно на GPU. Наиболее медленным способом является способ моделирования с использованием математических пакетов для инженерных вычислений. Способ моделирования с использованием ОЗУ в качестве хранилища данных лучше за счет меньшего количества пересылок данных из ОЗУ во внутреннюю память GPU. Запись данных в предложенном способе происходит единожды, а в способе с использованием математических пакетов каждая матрица, используемая в матричных операциях, пересылается отдельно.

Наибольшей сложностью реализации программного обеспечения обладает способ с использованием внутренней памяти GPU за счет сложности инициализации ядер CUDA и разрешения доступа к видеопамяти. Наиболее простым способом с точки зрения программной реализации является способ с использованием математического пакета и CUDA Parallel Toolbox. Данные средства хорошо документированы, а также разработка в математических пакетах проще, чем в C-подобных языках.

Способ с использованием математического пакета обладает и наибольшей расширяемостью. Это связано с отсутствием компиляции языка математического пакета для инженерных расчетов. Наименьшей же расширяемостью обладают способы с использованием ОЗУ и внутренней видеопамяти в качестве хранилища данных. Это связано с компиляцией программного кода.

Наиболее безопасным программным обеспечением является ПО, разработанное на основе способа с использованием ОЗУ в качестве хранилища данных за счет компиляции в библиотеку GPGPU.dll по причине недоступности изменения компилируемой библиотеки. Наименее безопасным продуктом является ПО, разработанное на основе способа с использованием математического пакета по причине простоты изменения исходного кода.

Заключение

Таким образом, представлены 3 отличных друг от друга способа моделирования ассоциативного запоминающего устройства с использованием технологии GPGPU, имеющие свою плюсы и минусы. Программные средства, реализованные на основе представленных способов, дают инструменты для научного исследования ассоциативных запоминающих устройств.

литература

1. Огнев И.В., Борисов В.В. Ассоциативные среды: - М.: Радио и связь, 2000 г. – 312 с.

2. Зернов М.М., Тимофеев С.С. Операции над бинарными матрицами в ассоциативных запоминающих устройствах // Сборник научных статей по итогам Третьей Международной научно-практической конференции (в трех томах) «Математика, математическое моделирование, экономика» Т.1, 2013, с.124-128.

3. Тимофеев С.С., Курдаков К.А. Системы массового параллелизма в иерархической ассоциативной памяти // Сборник трудов II Международной научно-техническая конференция «Энергетика, Информатика, Инновации-2012 (электроэнергетика и электротехника, теплоэнергетика и энергосбережение, математическое моделирование и совершенствование технических систем и технологических процессов, микроэлектроника и оптотехника)» Т.1, 2012, с.286-289

METHODS OF ASSOCIATIVE MEMORY MODELING USING GPGPU TECHNOLOGY

Zernov M. M., Timofeev S. S.

Methods of associative memory modeling using GPGPU technology offered. Methods are based on the use of parallel computing on the GPU, and using internal GPU memory for data storage. The method of associative memory modeling using GPGPU technology and mathematical package for engineering calculations, the method of associative memory modeling using GPGPU technology and RAM as data, the method of associative memory modeling using GPGPU technology and internal memory as GPU data. A comparative analysis of the effectiveness of methods according to various criteria. On the basis of data modeling techniques associative memory using GPGPU technology has developed a tool for modeling.

Key words: modeling, associative memory, parallel computing, GPU, technology GPGPU, mathematical package for engineering calculations.

Зернов Михаил Михайлович – к.т.н., филиал ФГБОУ ВПО "НИУ МЭИ" в г. Смоленске,

Курдаков Кирилл Андреевич – магистрант филиала ФГБОУ ВПО "НИУ МЭИ" в г. Смоленске.

Кафедра вычислительной техники

Филиал ФГБОУ ВПО "НИУ МЭИ" в г. Смоленске.

Поступила в редакцию 4.06.2014.