The 24 references with 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
Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: МГТУ им. Н.Э. Баумана, 2014. 423 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=15652
    Prefix
    Структуры данных для представления графов Перед непосредственной реализацией параллельных алгоритмов необходимо определить структуры данных, необходимые для представления графов в памяти GPU. Множества графа и т.д., используемые для описания любых графовых моделей
    Exact
    [1, 2]
    Suffix
    , могут быть представлены в матричной форме или аналитически множествами и множествами множеств образов графа по отношениям инцидентности и смежности . Будем основываться на аналитическом представлении, учитывая преимущества и недостатки обоих методов описания [3].

2
Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: МГТУ им. Н.Э. Баумана, 2001. 288 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=15652
    Prefix
    Структуры данных для представления графов Перед непосредственной реализацией параллельных алгоритмов необходимо определить структуры данных, необходимые для представления графов в памяти GPU. Множества графа и т.д., используемые для описания любых графовых моделей
    Exact
    [1, 2]
    Suffix
    , могут быть представлены в матричной форме или аналитически множествами и множествами множеств образов графа по отношениям инцидентности и смежности . Будем основываться на аналитическом представлении, учитывая преимущества и недостатки обоих методов описания [3].

3
Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники: дис. ... докт. техн. наук. М., 2007. 416 с.
Total in-text references: 3
  1. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

  2. In-text reference with the coordinate start=15938
    Prefix
    Множества графа и т.д., используемые для описания любых графовых моделей [1, 2], могут быть представлены в матричной форме или аналитически множествами и множествами множеств образов графа по отношениям инцидентности и смежности . Будем основываться на аналитическом представлении, учитывая преимущества и недостатки обоих методов описания
    Exact
    [3]
    Suffix
    . Определим как минимальный набор множеств, определяющих граф. Прямые и обратные отношения смежности и могут быть определены через эти множества. В общем случае все связи вершин и ребер с точки зрения структур данных симметричны относительно друг друга.

  3. In-text reference with the coordinate start=17166
    Prefix
    Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений. В таком случае в качестве множества как единицы построения графа можно взять любую структуру данных, описанную в
    Exact
    [3, 4, 9]
    Suffix
    , однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах [15, 17, 20, 22, 24], заслуживает отдельного исследования.

4
Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для представления графов при решении комбинаторно-оптимизационных задач // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2001. No 2 (43). C. 39-51.
Total in-text references: 1
  1. In-text reference with the coordinate start=17166
    Prefix
    Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений. В таком случае в качестве множества как единицы построения графа можно взять любую структуру данных, описанную в
    Exact
    [3, 4, 9]
    Suffix
    , однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах [15, 17, 20, 22, 24], заслуживает отдельного исследования.

5
Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. No 10. Режим доступа: http://technomag.bmstu.ru/doc/132769.html (дата обращения 07.10.2015).
Total in-text references: 2
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

6
Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 2) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. No 11. Режим доступа: http://technomag.bmstu.ru/doc/133223.html (дата обращения 07.10.2015).
Total in-text references: 2
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

7
Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 3) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. No 12. Режим доступа: http://technomag.bmstu.ru/doc/134335.html (дата обращения 07.10.2015).
Total in-text references: 3
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

  3. In-text reference with the coordinate start=19057
    Prefix
    Входными данными для операции являются:  идентификатор разбиваемой вершины;  новые вершины и , а также идентификаторы входящих и исходящих ребер;  вводимое ребро , идентификаторы входящих и исходящих вершин. Алгоритм операции, подробно описанный в
    Exact
    [7]
    Suffix
    , представляет собой совокупность последовательно выполняющихся параллельных операций: удаление вершины, добавления и удаления вершин и ребер [8]. Предложим реализацию параллельного алгоритма удаления вершины: 1 2 3 4 5 6 7 8 9 10 // функция удаляет вершину с идентификатором id void deleteVertex(ID id) { // удаление вершины с идентификатором id из множеств исходящ

8
Иванова Г.С., Головков А.А. Оценка эффективности параллельных алгоритмов операций преобразования графовой модели // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. No 11. С. 535-554. DOI: 10.7463/1114.0741563
Total in-text references: 4
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=1846
    Prefix
    При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров. Так в
    Exact
    [8]
    Suffix
    показано, что оценка ускорения параллельных алгоритмов для основных операций преобразования графов прямо пропорциональна количеству вершин и ребер графа. Как правило, любые теоретические оценки основываются на следующих допущениях:  количество одновременно выполняющихся потоков (нитей) равно необходимому количеству потоков для алгоритма;  все по

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

  4. In-text reference with the coordinate 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); // удаление вершины с идентиф

9
Головков А.А., Иванова Г.С. Структура данных для представления графов на параллельных вычислительных системах и параллельные алгоритмы операций над графами // Инженерный вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. No 11. С. 625-632. Режим доступа: http://engbul.bmstu.ru/doc/751611.html (дата обращения 07.10.2015).
Total in-text references: 3
  1. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

  2. In-text reference with the coordinate start=16634
    Prefix
    Нет необходимости четко разделять вершину или ребро от их ориентированных или неориентированных связей с ребрами или вершинами соответственно, поэтому будем представлять общую структуру графа множествами и , при этом в каждой вершине и ребре содержится соответствующее множество и
    Exact
    [9]
    Suffix
    . Реализация операций над графами предусматривает отсутствие ограничений на размерность, тип, ориентированность графа, а также какую-либо его модификацию. Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений.

  3. In-text reference with the coordinate start=17166
    Prefix
    Рассматривая граф, как совокупность ранее определенного минимального набора множеств, можно утверждать, что множества также должны соответствовать этому набору ограничений. В таком случае в качестве множества как единицы построения графа можно взять любую структуру данных, описанную в
    Exact
    [3, 4, 9]
    Suffix
    , однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах [15, 17, 20, 22, 24], заслуживает отдельного исследования.

10
Головков А.А. Представление графовых моделей в системах параллельной обработки // Молодежный научно-технический вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. No 7. Режим доступа: http://sntbul.bmstu.ru/doc/727773.html (дата обращения 07.10.2015).
Total in-text references: 1
  1. In-text reference with the coordinate start=3089
    Prefix
    архитектурные особенности систем параллельной обработки, преимущества и недостатки различных моделей и технологий параллельного программирования с целью использования лучших подходов, приемов и методов. Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями
    Exact
    [3, 5-10]
    Suffix
    при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), вы

11
Гергель В.П. Теория и практика параллельных вычислений: учеб. пособие. М.: Интернет-университет Информационных технологий; БИНОМ. Лаборатория знаний, 2013. 423 с.
Total in-text references: 1
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

12
Wilt N. The CUDA Handbook: A Comprehensive Guide to GPU Programming. AddisonWesley, 2013. 512 p.
Total in-text references: 3
  1. In-text reference with the coordinate start=3149
    Prefix
    Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA
    Exact
    [12, 13, 23]
    Suffix
    , и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и

  2. In-text reference with the coordinate start=4378
    Prefix
    На современных процессорах GPU архитектуры Maxwell это число может достигать десятков тысяч, что позволяет говорить о возможности достижения высокого реального ускорения особенно при реализации операций над графами больших размерностей. Все потоки CUDA выполняются варпами (англ. warp)
    Exact
    [12]
    Suffix
    – группами по 32 потока, при этом потоки в варпе выполняются синхронно по принципу «одна команда – множество данных» (SIMD – Single Instruction Multiple Data). В связи с этим при разработке программ могут возникать определенные сложности, допустим, стандартная реализация мьютекса, необходимая для синхронизации потоков при работе со сложной структурой данных

  3. In-text reference with the coordinate start=5427
    Prefix
    Поскольку потоки в варпе будут выполнять код синхронно, только один поток выполнит код в строке 2, захватив мьютекс, и будет ожидать остальных, но они не смогут выполнить захват мьютекса, т.к. первый поток никогда его не освободит. В случае ветвлений в варпе возникает ситуация дивергенции потоков (англ. thread divergence) – ветвление логики исполнения
    Exact
    [12]
    Suffix
    . В силу синхронного выполнения кода, все потоки последовательно выполняют все возможные пути ветвлений, что негативно сказывается на производительности. Дивергенция особенно проявляется при работе многих потоков со сложными структурами данных.

13
Farber R. CUDA Application Design and Development. Waltham, MA, USA: Morgan Kaufmann, 2011. 336 p.
Total in-text references: 2
  1. In-text reference with the coordinate start=3149
    Prefix
    Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA
    Exact
    [12, 13, 23]
    Suffix
    , и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и

  2. In-text reference with the coordinate start=3373
    Prefix
    достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA [12, 13, 23], и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно
    Exact
    [13]
    Suffix
    CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и параллельных частей (device-код), выполняемых на графических процессорах (GPU).

14
Merrill D., Garland M., Grimshaw A. Scalable GPU Graph Traversal // Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP '12). ACM New York, NY, USA, 2012. P. 117-128. DOI: 10.1145/2145816.2145832
Total in-text references: 1
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

15
Hussein M., Varshney A., Davis L. On Implementing Graph Cuts on CUDA // First Workshop on General Purpose Processing on Graphics Processing Units, 2007. Available at: http://www-lb.cs.umd.edu/gvil/papers/hussein_GPGPU07.pdf, accessed 07.10.2015.
Total in-text references: 1
  1. In-text reference with the coordinate start=17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол

16
Dechev D., Pirkelbauer P., Stroustrup B. Lock-Free Dynamically Resizable Arrays // Principles of Distributed Systems. Springer-Verlag Berlin Heidelberg, 2006. P. 142-156. (Ser. Lecture Notes in Computer Science; vol. 4305). DOI: 10.1007/11945529_11
Total in-text references: 1
  1. In-text reference with the coordinate start=12214
    Prefix
    Поскольку при одновременной работе многих потоков с одной структурой данных могут возникать конфликты, необходимо предусмотреть надежный механизм синхронизации и обеспечения атомарности операций структуры данных. Целесообразно использовать lock-free
    Exact
    [16, 18, 19]
    Suffix
    структуры данных, основанные на неблокирующей синхронизации, однако принципы lock-free подходят не для всех типов структур. В этом случае возможно использовать модифицированные для CUDA механизмы синхронизации.

17
Luo L., Wong M., Wen-mei Hwu. An Effective GPU Implementation of Breadth-First Search // Proceedings of the 47th Design Automation Conference (DAC '10). ACM New York, NY, USA, 2010. P. 52-55. DOI: 10.1145/1837274.1837289
Total in-text references: 1
  1. In-text reference with the coordinate start=17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол

18
Misra P., Chaudhuri M. Performance Evaluation of Concurrent Lock-free Data Structures on GPUs // Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems. IEEE Publ., 2012. P. 53-60. DOI: 10.1109/ICPADS.2012.18
Total in-text references: 1
  1. In-text reference with the coordinate start=12214
    Prefix
    Поскольку при одновременной работе многих потоков с одной структурой данных могут возникать конфликты, необходимо предусмотреть надежный механизм синхронизации и обеспечения атомарности операций структуры данных. Целесообразно использовать lock-free
    Exact
    [16, 18, 19]
    Suffix
    структуры данных, основанные на неблокирующей синхронизации, однако принципы lock-free подходят не для всех типов структур. В этом случае возможно использовать модифицированные для CUDA механизмы синхронизации.

19
Cederman D., Gidenstam A., Ha P., Sundell H., Papatriantafilou M., Tsigas P. Lock-free Concurrent Data Structures // Programming Multi-Core and Many-Core Computing Systems / ed. by S. Pllana, F. Xhafa. Wiley-Blackwell, 2013. (Wiley Series on Parallel and Distributed). Available at: http://arxiv.org/pdf/1302.2757.pdf, accessed 07.10.2015.
Total in-text references: 1
  1. In-text reference with the coordinate start=12214
    Prefix
    Поскольку при одновременной работе многих потоков с одной структурой данных могут возникать конфликты, необходимо предусмотреть надежный механизм синхронизации и обеспечения атомарности операций структуры данных. Целесообразно использовать lock-free
    Exact
    [16, 18, 19]
    Suffix
    структуры данных, основанные на неблокирующей синхронизации, однако принципы lock-free подходят не для всех типов структур. В этом случае возможно использовать модифицированные для CUDA механизмы синхронизации.

20
Schaeffer S.E. Graph clustering // Computer Science Review. 2007. Vol. 1, iss. 1. P. 27-64. DOI: 10.1016/j.cosrev.2007.05.001
Total in-text references: 1
  1. In-text reference with the coordinate start=17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол

21
Shucai Xiao, Wu-chun Feng. Inter-block GPU communication via fast barrier synchronization // 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE Publ., 2010. P. 1-12. DOI: 10.1109/IPDPS.2010.5470477
Total in-text references: 1
  1. In-text reference with the coordinate start=6371
    Prefix
    Для синхронизации потоков CUDA предоставляет функции барьерной синхронизации в пределах блока. Синхронизация всех блоков может быть обеспечена только при условии их одновременного выполнения, когда количество блоков меньше либо равно количеству мультипроцессоров GPU
    Exact
    [21]
    Suffix
    . 2. Работа с CUDA-потоками Количество необходимых потоков в алгоритмах может превышать не только число реально работающих потоков , но и логическое количество потоков, которые можно инициализировать при вызове параллельной функции.

22
Якобовский М.В. Введение в параллельные методы решения задач: учеб. пособие. М.: Изд-во Московского ун-та, 2013. 328 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1453
    Prefix
    Ключевые слова: операция над графом, параллельный алгоритм, CUDA, оптимизация, поток, мьютекс, структура данных Введение Многие алгоритмы решения задач структурного анализа и синтеза на графовых моделях
    Exact
    [1, 2, 5-8, 11, 14, 22]
    Suffix
    имеют большой запас внутреннего параллелизма, так как включают однотипные операции, выполняемые над множествами вершин, ребер и/или их отображениями. При этом с теоретической точки зрения ускорение зависит только от размерности входных данных задачи при реализации на параллельной системе с достаточным количеством процессоров.

  2. In-text reference with the coordinate start=17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол

23
Линев А.В., Богопелов Д.К., Бастраков С.И. Технологии параллельного программирования для процессоров новых архитектур: учебник. М.: Изд-во Московского ун-та, 2010. 160 с.
Total in-text references: 1
  1. In-text reference with the coordinate start=3149
    Prefix
    Целью настоящей работы является выявление факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями [3, 5-10] при использовании параллельной системы GPGPU CUDA
    Exact
    [12, 13, 23]
    Suffix
    , и выработка рекомендаций, следование которым приведет к снижению непроизводительных временных затрат. 1. Особенности модели исполнения программ в графических процессорах CUDA Согласно [13] CUDA-программа, написанная на языках C++, C или Fortran, состоит из последовательных частей (host-код), выполняемых на обычном центральном процессоре (CPU), и

24
Pawan Harish, Vibhav Vineet and P. J. Narayanan. Large Graph Algorithms for Massively Multithreaded Architectures. Technical Report no. IIIT/TR/2009/74. Centre for Visual Information Technology, International Institute of Information Technology, Hyderabad - 500 032, INDIA, February 2009. Available at: http://cvit.iiit.ac.in/papers/pawan09GraphAlgorithms.pdf, accessed 07.10.2015.
Total in-text references: 1
  1. In-text reference with the coordinate start=17488
    Prefix
    построения графа можно взять любую структуру данных, описанную в [3, 4, 9], однако для эффективной реализации необходимо разработать структуру на основе особенностей архитектуры и программирования в CUDA. Оптимальный выбор структур данных, основанный на особенностях алгоритмов решения конкретных задач, а также специфике представления графов в этих задачах
    Exact
    [15, 17, 20, 22, 24]
    Suffix
    , заслуживает отдельного исследования. В качестве динамической структуры данных, удовлетворяющей всем требованиям и ограничениям, предложим динамический массив указателей. Основные операции модификации структуры: удаление, добавление и вставка элемента должны быть реализованы атомарно, поскольку может возникнуть конфликтная ситуация, когда часть работы дол