Форум программистов, компьютерный форум CyberForum.ru

Задача поиска множественных путей в графе - C++

Восстановить пароль Регистрация
 
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
06.07.2015, 16:46     Задача поиска множественных путей в графе #1
Добрый день.
Возникла задача поиска множественных путей в графе. Задача объемная и по объему вычислений и по памяти. По моему разумению задача может быть хорошо распараллелена.
Решил использовать многопоточность на C++ (VS 2010 х64). Написал тест с использованием API-шных функций по добавлению в vector элементов внутри каждого потока. Вроде как все работает без ошибок. Но возникло несколько вопросов.

1. Не могу, как не старался, загрузить все (ну или хотя бы почти все) ядра. У меня сервер - 4 процессора по 16 ядер в каждом. Максимум, что могу загрузить - 13 ядер одного процессора. При этом, если задаю количество потоков больше 64, то вообще все "ломается" - неправильно и не до конца работает добавление элементов к вектору.
2. Сравнил скорость расчета в однопоточном варианте и в многопоточном. У меня получается, что в однопоточном варианте суммарная скорость расчетов где-то в 2.5 раза быстрее чем в многопоточном, независимо от количества threads. В диспетчере задач наблюдал, что в однопоточном варианте одно ядро грузится под 100 процентов, а в многопоточном варианте несколько ядер загружаются на 15-20 процентов.

Буду очень признателен, если кто-нибудь сможет подсказать, что происходит и как это победить.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <tchar.h>
#include <cstdio>
 
#include <vector>
#include <cmath>
#include <string>
 
#include <process.h>
#include <windows.h>
#include <ctime>
using namespace std;
 
#define THREADS_NUMBER 17
 
#define ITERATIONS_NUMBER 10000000
 
#define PAUSE 10 /* ms */
 
DWORD dwCounter = 0;
vector<vector<int>> vt;
 
vector<vector<int>> vt_t;
 
 
    unsigned __stdcall ThreadProc(CONST LPVOID lpParam) {
    CONST HANDLE hMutex = (CONST HANDLE)lpParam;
   int iloc=0;
     WaitForSingleObject(hMutex, INFINITE);
     
     iloc=dwCounter;
     dwCounter++;
     ReleaseMutex(hMutex);
     Sleep(PAUSE);
 
   for(int i = 0; i < ITERATIONS_NUMBER; i++) {
       vt[iloc].push_back(i);     
   }
        //printf(" Into %d\n", iloc);
   ExitThread(0);
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    
unsigned int start_time1 =  clock(); 
// однопоточный тест
    for( int i1=0; i1< THREADS_NUMBER; i1++)
   {
        vector<int> vj;
       vt_t.push_back(vj);
   }
 
   for( int iloc=0; iloc< THREADS_NUMBER; iloc++)
   {
        for(int i = 0; i < ITERATIONS_NUMBER; i++) {
            vt_t[iloc].push_back(i);     
         }
   }
 
   unsigned int end_time1 =  clock(); 
 
 
    TCHAR szMessage[256];
    unsigned threadID;
 
   for( int i1=0; i1< THREADS_NUMBER; i1++)
   {
        vector<int> vj;
       vt.push_back(vj);
   }
 
   //многопоточность
   unsigned int start_time2 =  clock(); 
 
    int i;
   HANDLE hThreads[THREADS_NUMBER];
   CONST HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   CONST HANDLE hMutex = CreateMutex(NULL, FALSE, NULL);
   if(NULL == hMutex) {
     printf(" No Mutex\n");
   }
 
   for(i = 0; i < THREADS_NUMBER; i++) {
    hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, &ThreadProc, hMutex, 0, &threadID);
     if(NULL == hThreads[i]) {
        printf(" No thr\n");
     }
   }
 
   WaitForMultipleObjects(THREADS_NUMBER, hThreads, TRUE, INFINITE);
 
unsigned int end_time2 =  clock(); 
 
   int svt;
   int ival;
   // проверка правильности расчетов
   printf("Counter = %d\r\n", dwCounter);
   for(int iz=0; iz<vt.size(); iz++)
   {
        try {
       svt=vt[iz].size();
       ival=vt[iz][svt-1];
       printf("iz=%d ij=%d value=%d \n", iz, svt, ival);
        } catch (...)
        {
            printf("Counter = %d\r\n", dwCounter);
        }
   }
 
        printf(" time1 = %ld  time2= %ld \n", end_time1-start_time1, end_time2-start_time2);
   for(i = 0; i < THREADS_NUMBER; i++) {
     CloseHandle(hThreads[i]);
   }
   CloseHandle(hMutex);
   ExitProcess(0);
    
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
06.07.2015, 22:35     Задача поиска множественных путей в графе #2
1. Если тебе заранее известен размер массива, то инициализируй его под этот размер
C++
1
vt = std::vector< std::vector<int> >(N1, std::vector<int>(N2));
2. Базовые структуры vetor, map и т.п. потоконебезопасны на добавление/изменение, т.е. доступ к ним должен регулироваться.
3. Что-то странно выглядит твой мьютекс
4. Зачем слип?
5. Создание потоков требует времени, поэтому твоё заполнение теряет как здесь, так и на синхронизации кеша ядер и ОЗУ. Простую инициализацию лучше не распараллеливать.
6. Зачем тебе тут Win-потоки? Крайне не рекомендую. Либо обнови VS до нормальной поддержки С++11, либо используй OpenMP.
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
07.07.2015, 09:17  [ТС]     Задача поиска множественных путей в графе #3
Привет.
Спасибо за ответ.

1. Исходя из смысла задачи заранее размер массива не известен. Это всего лишь тест. В действительности мне приходится иметь дело чуть ли не с 4-х мерным массивом. Три размерности действительно инициализированы заранее. А вот четвертая не может быть заранее инициализирована; приходится динамически добавлять. Собственно для этого и писался тест.
2. Я хотел проверить, если каждый поток работает со своим набором первых трех размерностей, могут ли возникнуть коллизии с блокировкой и т.д. Я поэкспериментировал с WaitForSingleObject(hMutex, INFINITE) и ReleaseMutex(hMutex);. Оказалось, что так вроде можно работать из разных потоков. По крайней мере ничего не портится. Но в процессе эксперимента наткнулся на проблемы с производительностью.
3., 4. Хорошие вопросы ) Я честно говоря нашел в инете какую-то простейшую реализацию многопоточности ну и приспособил под себя. В "арифметике" и алгоритмах я немного разбираюсь, а вот в тонкостях C++ и тем более threads - полный профан. Хотелось бы, чтобы кто-нибудь подсказал, как правильно.
5. Да, я понимаю, что инициализация потока, переключение требуют времени. Собственно поэтому я написал большой цикл (кстати, реально отличающийся в меньшую сторону от того, что потребуется собственно в задаче), чтобы можно было пренебречь всеми этими процессами по сравнению со временем расчета. А вот инициализацию массива я не могу вынести за многопоточность, в этом суть задачки. Я в действительности в четвертую размерность добавляю каждый раз сложную структуру, описывающую путь и заранее не знаю, сколько таких маршрутов будет.
6. Согласен. С удовольствием бы воспользовался разумными обертками, где уже все прописано. НО: Вынужден работать в корпоративном стандарте, а у нас VS 2010 и апдейтить библиотеками или довести до 2013 не удастся.

Если возможно, укажите, где я неправильно пишу, и все-таки, почему проигрываю по производительности, как задействовать все доступные ядра ну, хотя бы процентов на 80? Собственно ради увеличения скорости расчетов раз в 10 я и затеял все это, иначе задача будет считаться сутками.
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
07.07.2015, 09:29     Задача поиска множественных путей в графе #4
Цитата Сообщение от Iakov Посмотреть сообщение
4 процессора по 16 ядер в каждом.
Тут враньё, как минимум половина из них Hyper-threading, т.е. не полноценные и рассчитанные на специальные команды процессора.

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

Поэтому по возможности выделяй память заранее. Это позволит, в частности, ускорить расчёты за счёт использования процессорного кеша.

OpenMP есть и в VS2010
Чего там нет, так это C++11
а использование VS2010 сейчас, нет никого смысла. Слишком много плюшек принёс C++11, которые стали использоваться и во многих сторонних библиотеках.
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
07.07.2015, 09:45  [ТС]     Задача поиска множественных путей в графе #5
1. На счет выделения памяти заранее, подумаю, как изменить алгоритм. В принципе это возможно, если "перезаложиться". Я просто хотел сэкономить память. А если все-таки придется выделять внутри, то я все же должен "обрамлять" операторы работы с массивом в WaitForSingleObject(hMutex, INFINITE) и ReleaseMutex(hMutex)? Я просто хотел избежать этого, чтобы лишний раз не тормозить другие потоки.
На сколько я понял, если память уже выделена, то я могу без этих "скобок" обращаться к ней, если другие потоки в эти элементы не лезут?
2. А где взять этот OpenMP?
3. И все же, как заставить выделенное ядро все время работать под данный поток, чтобы не было постоянной дерготни и его можно было загрузить желательно на 100%? Ведь в однопоточном режиме одно ядро загружается практически на 100 процентов
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
07.07.2015, 10:02     Задача поиска множественных путей в графе #6
1. Не надо ничего делать. ОС сама всё разрулит, заблокирует и разблокирует.Пробуй просто заранее выделять минимально необходимый объём.
2. Эта встроенная опция компилятора. https://msdn.microsoft.com/ru-ru/library/fw509c3b.aspx
Но помни, что он предназначен, только для определённого класса задач. почитай курсы на intuit.ru или т.п.
3. Не стоит этим парится. ОС сама решает какую порцию где считать. Кроме этого у тебя явно включен Hyper-threading. А это значит, что ты не сможешь использовать все ядра по 100%, максимум только половину из них.
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
07.07.2015, 10:07  [ТС]     Задача поиска множественных путей в графе #7
ОК, спасибо. Буду пробовать.
Остался последний вопрос. А как выключить этот самый Hyper-threading?
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
07.07.2015, 10:07     Задача поиска множественных путей в графе #8
В настройка BIOS-а
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
09.07.2015, 12:49  [ТС]     Задача поиска множественных путей в графе #9
Добрый день.
По сути решаемой мной задачи приходится динамически дополнять часть многомерного массива. Задача очень объемная и по времени счета и по памяти. Поэтому по подсказке форумчан решил использовать OpenMP в VS2010 для распараллеливания.
Упрощенная схема куска программы такая

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Route {}
typedef Route stR
typedef vector<Route> v_Route;
 
…
vector<v_Route> R;
 
for(i=0; i<N; i++)
{
    v_Route tmpR;
    R.push_back(tmpR);
}
 
…
// цикл для распараллеливания
for(int i=0;    i<N; i++) 
{
…
…
    for (int j=0; j< Z; j++)
    {
        …
        stR Route;      
        R[i].push_back(Route)
        …
    }
 
}
Количество добавленных структур Route зависит от i: Z=Z(i) и заранее не известно. Внутренность цикла j работает только с одним i. Причем, если заранее определить некоторое Z0 >= max(Z(i)), чтобы инициализировать вектор R вне цикла, то потребуется безумное количество памяти.
Вопрос: как можно безопасно добавлять элементы в массив при условии, что цикл I распараллелен.
Я попробовал самые элементарные вещи типа:
C++
1
2
3
4
5
6
#pragma omp parallel num_threads(15) 
{
    #pragma omp parallel for shared(TRoutes, NodeLegA, OArr)
    for(int i=0; i<NofNodes; i++)
    {
        …
(В shared перечислены внешние указатели на вектора, которые используются только для чтения)
Однако постоянно натыкаюсь на ошибки, связанные с памятью.
Кто-нибудь может подсказать «куда смотреть, что искать»?
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
09.07.2015, 14:00     Задача поиска множественных путей в графе #10
Iakov, замени
C++
1
2
3
4
5
6
7
vector<v_Route> R;
 
for(i=0; i<N; i++)
{
    v_Route tmpR;
    R.push_back(tmpR);
}
на
C++
1
vector<v_Route> R(N);
Далее, если перед циклом тебе уже известно Z, то
C++
1
2
3
4
5
6
7
    R[i] = v_Route(Z);
    for (int j=0; j< Z; j++)
    {
        …
        R[i][j]=route;
        …
    }
Ну и

C++
1
#pragma omp parallel num_threads(15)
Лишнее, удали его. А то ты в 15 потоков прогоняешь цикл for по всему диапазону.
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
09.07.2015, 14:25  [ТС]     Задача поиска множественных путей в графе #11
Я просто нарисовал очень упрощенную ситуацию. На самом деле, цикл известного размера, а вот сколько раз внутри цикла я буду делать push_back - неизвестно. Зависит от внешних переменных
Ну да, 15 осталось от экспериментирования. на самом деле система дает 64 потока.
Вот здесь один из реальных кусков кода который я хочу распараллелить:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#pragma omp parallel   
{
    #pragma omp parallel for shared(TRoutes, OArr, NodeLegA, NodeLegB) 
    for(int ist=0; ist<NofNodes; ist++)
    {
        vector<NodeFan> stNodes;
        int st_nlegs=NodeLegA[ist].size();
        // Выбираем все узлы на конце ребер из узла ist
        int i_i=0;
        for(int i=0; i<st_nlegs; i++)
        {
            NodeFan tmpNodeFan;
            int nn=NodeLegA[ist][i]; //
            if(OArr[nn].msc_finish != ist)
            {
                stNodes.push_back(tmpNodeFan);
                stNodes[i_i].Node=OArr[nn].msc_finish; //Запоминаем, каким узлом кончается ребро
                stNodes[i_i].NLeg=nn; // Здесь же храним адрес ребра в исходном массиве
                i_i++;
            }
        }
 
        for(int ifi=0; ifi<NofNodes; ifi++) // Для каждого конечного узла
        {
            if( ifi != ist)
            {
                vector<NodeFan> fiNodes;
                int fi_nlegs=NodeLegB[ifi].size();
                int i_i=0;
                // Выбираем все узлы в начале ребер из узла ifi
                for(int i=0; i<fi_nlegs; i++)
                {
                    NodeFan tmpNodeFan;
                    int nn=NodeLegB[ifi][i];
                    if(OArr[nn].msc_start != ist && OArr[nn].msc_start != ifi)
                    {
                        fiNodes.push_back(tmpNodeFan);
                        fiNodes[i_i].Node=OArr[nn].msc_start; //Запоминаем, каким узлом начинается ребро
                        fiNodes[i_i].NLeg=nn;
                        i_i++;
                    }
                }
                
                //теперь надо сравнить два массива на совпадения вершин
                int real_route=0;
                for( unsigned int ia=0; ia<stNodes.size(); ia++)
                {
                    for(unsigned int ib=0; ib<fiNodes.size(); ib++)
                    {
                        if(stNodes[ia].Node == fiNodes[ib].Node)
                        {
                            struct Route tmpRoute; //базовая структура, в которой описание маршрута
                            TRoutes[ist][ifi][1].push_back(tmpRoute);
                            TRoutes[ist][ifi][1][real_route].totcost=0.0;
                            TRoutes[ist][ifi][1][real_route].tottime=0.0;
                            //Адрес первого плеча в массиве всех плеч
                            int nn=stNodes[ia].NLeg;
                            TRoutes[ist][ifi][1][real_route].iorigF[0]=nn; 
                            TRoutes[ist][ifi][1][real_route].totcost+=OArr[nn].cost;
                            TRoutes[ist][ifi][1][real_route].tottime+=OArr[nn].time;
 
                            //Адрес второго плеча в массиве всех плеч
                            nn=fiNodes[ib].NLeg;
                            TRoutes[ist][ifi][1][real_route].iorigF[1]=nn; 
                            TRoutes[ist][ifi][1][real_route].totcost+=OArr[nn].cost;
                            TRoutes[ist][ifi][1][real_route].tottime+=OArr[nn].time;
 
                            TRoutes[ist][ifi][1][real_route].msc_start=ist;
                            TRoutes[ist][ifi][1][real_route].msc_finish=ifi;
                            TRoutes[ist][ifi][1][real_route].nlg=2;
                            real_route++;
                        }
                    }
                }
                
            } //if( ifi != ist)
        } //for(int ifi=0; ifi<NofNodes; ifi++)
    } //for(int ist=0; ist<NofNodes; ist++)
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2015, 09:09     Задача поиска множественных путей в графе
Еще ссылки по теме:

C++ Поиск кратчайших путей в графе
C++ Алгоритм поиска в глубину в ориентированном графе
Реализация поиска мостов на графе C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
13.07.2015, 09:09  [ТС]     Задача поиска множественных путей в графе #12
Добрый день.
Похоже, из-за того, что мне исправили название темы на не имеющее отношение к сути вопроса, никто сюда не заглядывает
На всякий случай повторю вопрос.
Кто-нибудь знает как внутри параллельных потоков (threads) безопасно динамически добавлять память (добавлять элементы vector) к уже существующему общему многомерному vector?
Спасибо заранее.
Yandex
Объявления
13.07.2015, 09:09     Задача поиска множественных путей в графе
Ответ Создать тему
Опции темы

Текущее время: 00:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru