The 16 reference contexts in paper A. Golovkov A., G. Ivanova S., А. Головков А., Г. Иванова С. (2016) “Оптимизация вычислений над связными множествами в CUDA // Optimization of Computations on Related Sets in CUDA” / spz:neicon:technomag:y:2015:i:0:p:271-287

  1. Start
    1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.
    (check this in PDF content)

  2. Start
    1846
    Prefix
    При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров. Так в
    Exact
    [8]
    Suffix
    показано, что оценка ускорения параллельных алгоритмов для основных операций преобразования графов прямо пропорциональна количеству вершин и ребер графа. Как правило, любые теоретические оценки основываются на следующих допущениях:  количество одновременно выполняющихся потоков (нитей) равно необходимому количеству потоков для алгоритма;  все по
    (check this in PDF content)

  3. Start
    3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы
    (check this in PDF content)

  4. Start
    3149
    Prefix
    Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA
    Exact
    [12, 13, 23]
    Suffix
    , и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и
    (check this in PDF content)

  5. Start
    3373
    Prefix
    достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно
    Exact
    [13]
    Suffix
    CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и параллельных частей (device-код), выполняемых на графических процессорах (GPU).
    (check this in PDF content)

  6. Start
    4378
    Prefix
    На современных процессорах GPU архитектуры Maxwell это число может достигать десятков тысяч, что позволяет говорить о возможности достижения высокого реального ускорения особенно при реализации операций над графами больших размерностей. Все потоки CUDA выполняются варпами (англ. warp)
    Exact
    [12]
    Suffix
    – группами по 32 потока, при этом потоки в варпе выполняются синхронно по принципу «одна команда – множество данных» (SIMD – Single Instruction Multiple Data). В связи с этим при разработке программ могут возникать определенные сложности, допустим, стандартная реализация мьютекса, необходимая для синхронизации потоков при работе со сложной структурой данных
    (check this in PDF content)

  7. Start
    5427
    Prefix
    Поскольку потоки в варпе будут выполнять код синхронно, только один поток выполнит код в строке 2, захватив мьютекс, и будет ожидать остальных, но они не смогут выполнить захват мьютекса, т.к. первый поток никогда его не освободит. В случае ветвлений в варпе возникает ситуация дивергенции потоков (англ. thread divergence) – ветвление логики исполнения
    Exact
    [12]
    Suffix
    . В силу синхронного выполнения кода, все потоки последовательно выполняют все возможные пути ветвлений, что негативно сказывается на производительности. Дивергенция особенно проявляется при работе многих потоков со сложными структурами данных.
    (check this in PDF content)

  8. Start
    6371
    Prefix
    Для синхронизации потоков CUDA предоставляет функции барьерной синхронизации в пределах блока. Синхронизация всех блоков может быть обеспечена только при условии их одновременного выполнения, когда количество блоков меньше либо равно количеству мультипроцессоров GPU
    Exact
    [21]
    Suffix
    . 2. Работа с CUDA-потоками Количество необходимых потоков в алгоритмах может превышать не только число реально работающих потоков , но и логическое количество потоков, которые можно инициализировать при вызове параллельной функции.
    (check this in PDF content)

  9. Start
    12214
    Prefix
    Поскольку при одновременной работе многих потоков с одной структурой данных могут возникать конфликты, необходимо предусмотреть надежный механизм синхронизации и обеспечения атомарности операций структуры данных. Целесообразно использовать lock-free
    Exact
    [16, 18, 19]
    Suffix
    структуры данных, основанные на неблокирующей синхронизации, однако принципы lock-free подходят не для всех типов структур. В этом случае возможно использовать модифицированные для CUDA механизмы синхронизации.
    (check this in PDF content)

  10. Start
    15652
    Prefix
    Структуры данных для представления графов Перед непосредственной реализацией параллельных алгоритмов необходимо определить структуры данных, необходимые для представления графов в памяти GPU. Множества графа и т.д., используемые для описания любых графовых моделей
    Exact
    [1, 2]
    Suffix
    , могут быть представлены в матричной форме или аналитически множествами и множествами множеств образов графа по отношениям инцидентности и смежности . Будем основываться на аналитическом представлении, учитывая преимущества и недостатки обоих методов описания [3].
    (check this in PDF content)

  11. Start
    15938
    Prefix
    Множества графа и т.д., используемые для описания любых графовых моделей [1, 2], могут быть представлены в матричной форме или аналитически множествами и множествами множеств образов графа по отношениям инцидентности и смежности . Будем основываться на аналитическом представлении, учитывая преимущества и недостатки обоих методов описания
    Exact
    [3]
    Suffix
    . Определим как минимальный набор множеств, определяющих граф. Прямые и обратные отношения смежности и могут быть определены через эти множества. В общем случае все связи вершин и ребер с точки зрения структур данных симметричны относительно друг друга.
    (check this in PDF content)

  12. Start
    16634
    Prefix
    Нет необходимости четко разделять вершину или ребро от их ориентированных или неориентированных связей с ребрами или вершинами соответственно, поэтому будем представлять общую структуру графа множествами и , при этом в каждой вершине и ребре содержится соответствующее множество и
    Exact
    [9]
    Suffix
    . Реализация операций над графами предусматривает отсутствие ограничений на размерность, тип, ориентированность графа, а также какую-либо его модификацию. Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений.
    (check this in PDF content)

  13. Start
    17166
    Prefix
    Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений. В таком случае в качестве множества как единицы построения графа можно взять любую структуру данных, описанную в
    Exact
    [3, 4, 9]
    Suffix
    , однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах [15, 17, 20, 22, 24], заслуживает отдельного исследования.
    (check this in PDF content)

  14. Start
    17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол
    (check this in PDF content)

  15. Start
    19057
    Prefix
    Входными данными для операции являются:  идентификатор разбиваемой вершины;  новые вершины и , а также идентификаторы входящих и исходящих ребер;  вводимое ребро , идентификаторы входящих и исходящих вершин. Алгоритм операции, подробно описанный в
    Exact
    [7]
    Suffix
    , представляет собой совокупность последовательно выполняющихся параллельных операций: удаление вершины, добавления и удаления вершин и ребер [8]. Предложим реализацию параллельного алгоритма удаления вершины: 1 2 3 4 5 6 7 8 9 10 // функция удаляет вершину с идентификатором id void deleteVertex(ID id) { // удаление вершины с идентификатором id из множеств исходящ
    (check this in PDF content)

  16. Start
    19220
    Prefix
    Алгоритм операции, подробно описанный в [7], представляет собой совокупность последовательно выполняющихся параллельных операций: удаление вершины, добавления и удаления вершин и ребер
    Exact
    [8]
    Suffix
    . Предложим реализацию параллельного алгоритма удаления вершины: 1 2 3 4 5 6 7 8 9 10 // функция удаляет вершину с идентификатором id void deleteVertex(ID id) { // удаление вершины с идентификатором id из множеств исходящих вершин всех ребер графа, выполняется на EdgesCount потоках – количество ребер графа deleteVertexConnections <EdgesCount> (id); // удаление вершины с идентиф
    (check this in PDF content)