article

Re: using rand() function with OpenMP

	От:	Sergey Chadov
	Дата:	23.05.09 05:46
	Оценка:	+1

Здравствуйте, wotker, Вы писали:

W>Добрый вечер.
W>Помогите разобраться: почему матрица, инициализированная с помощью процедуры initMatrix, в результате имеет одинаковые строки?
W>Спасибо.

Потому что seed для rand() у каждого потока свой. Поэтому у тебя будет столько одинаковых последовательностей сколько ты используешь потоков.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

Re[4]: using rand() function with OpenMP

	От:	Sergey Chadov
	Дата:	24.05.09 09:48
	Оценка:	+1

Здравствуйте, Кодт, Вы писали:

SC>>Если бы функция rand сохраняла свое состояние в глобальной переменной, то при вызове ее из разных потоков были бы та-а-акие фейерверки. Поэтому каждый поток имеет свой seed.

К>Ну прямо уж феерверки.
Если никак не защищать — то прямо фейерверки. Я сам наблюдал на самодельном генераторе.

К> Что, сложно сделать атомарный доступ к семечку? На interlocked?
Тоже вариант.

К>Конечно, TLS — это тоже решение: у каждого потока семечко своё.
Там ведь структура ptd не только для rand нужна, поэтому почему бы еще и seed туда не запихать, я такое решение вполне понимаю.

К>Но ведь требования о независимости случайных последовательностей в разных потоках в Стандарте не записаны, так что это самодеятельность MS.
Обратного там тоже не записано. Значит MS действует здесь в рамках стандарта.

К>Ладно бы поведение нереентерабельной функции было не определено при реентере. (Как, скажем, printf с двух рук стрелять).
К>Это легко исправляется, если мы поместим вызов такой функции в критическую секцию.
К>

К>CCriticalSectrion csRand;
К>int tsrand() { CCritSecLock lock(&csRand); return rand(); }
К>

К>Однако, хотя вызовы строго сериализованы, эффект прежний — у нас не одна последовательность, а много, на каждый поток своя.

Если критическая секция без спинкаунта — это сильный удар по производительности. Если со спинкаунтом — то конечно значительно менее сильный, но что-то мне кажется что решение с tls проще и эффективнее.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

using rand() function with OpenMP

	От:	wotker
	Дата:	22.05.09 17:32

void initMatrix(int** m, int H, int W)
{     
    #pragma omp parallel 
    {
        #pragma omp for               
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j)
            {          
                
                #pragma omp critical
                {
                    cout << ::omp_get_thread_num() <<" ";
                    m[i][j] = rand()%15;
                    cout << ::omp_get_thread_num() << endl;
                }
            }
    }
}

Добрый вечер.
Помогите разобраться: почему матрица, инициализированная с помощью процедуры initMatrix, в результате имеет одинаковые строки?
Спасибо.

Re: using rand() function with OpenMP

	От:	_Vasilyev
	Дата:	23.05.09 13:00

Здравствуйте, wotker, Вы писали:

W>

W>void initMatrix(int** m, int H, int W)
W>{     
W>    #pragma omp parallel 
W>    {
W>        #pragma omp for               
W>        for (int i = 0; i < H; ++i)
W>            for (int j = 0; j < W; ++j)
W>            {          
                
W>                #pragma omp critical
W>                {
W>                    cout << ::omp_get_thread_num() <<" ";
W>                    m[i][j] = rand()%15;
W>                    cout << ::omp_get_thread_num() << endl;
W>                }
W>            }
W>    }
W>}
W>

W>Добрый вечер.
W>Помогите разобраться: почему матрица, инициализированная с помощью процедуры initMatrix, в результате имеет одинаковые строки?
W>Спасибо.

а задай как-нибудь так :

#pragma omp parallel 
{
    srand( omp_get_thread_num() * 1000/*сколько-то*/ );
        
    //....

    m[i][j] = rand();
    
    //....

    //////////////////////////////// и убери критическую секцию
    #pragma omp critical
    {
        cout << ::omp_get_thread_num() <<" ";
        m[i][j] = rand()%15;
        cout << ::omp_get_thread_num() << endl;
    }
}

Re: using rand() function with OpenMP

	От:	wotker
	Дата:	23.05.09 21:23

Потому что seed для rand() у каждого потока свой. Поэтому у тебя будет столько одинаковых последовательностей сколько ты используешь потоков.

Не очень понятно. Ведь функция rand сохраняет свое состояние (которое используется для генерации следующего числа) в глобальной переменной (а как же еще?). Эта переменная является разделяемой. Следовательно, если функция была вызвана в 2х потоках, то и возвращаемые значения тоже должны быть разными.

а задай как-нибудь так

Да, спасибо. Все работает корректно.

Re[2]: using rand() function with OpenMP

	От:	Sergey Chadov
	Дата:	24.05.09 06:42

Здравствуйте, wotker, Вы писали:

W>Не очень понятно. Ведь функция rand сохраняет свое состояние (которое используется для генерации следующего числа) в глобальной переменной (а как же еще?). Эта переменная является разделяемой. Следовательно, если функция была вызвана в 2х потоках, то и возвращаемые значения тоже должны быть разными.

Если бы функция rand сохраняла свое состояние в глобальной переменной, то при вызове ее из разных потоков были бы та-а-акие фейерверки. Поэтому каждый поток имеет свой seed.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

Re[3]: using rand() function with OpenMP

	От:	wotker
	Дата:	24.05.09 07:04

Здравствуйте, Sergey Chadov, Вы писали:

W>Если бы функция rand сохраняла свое состояние в глобальной переменной, то при вызове ее из разных потоков были бы та-а-акие фейерверки. Поэтому каждый поток имеет свой seed.

Мне не понятна Ваша фраза "Поэтому каждый поток имеет свой seed.". Меня интересует, как это реализовано. Если Вам не сложно, приведите кусок кода на С (т.к. я уже не понимаю как openMP определяет, какие одни переменные должны быть локальными, а другими — общими).
Касательно фейверков:

The rand() function need not be reentrant. A function that is not required to be reentrant is not required to be thread-safe.

Поэтому, нет гарантии, что они не случатся в других реализациях.

Re[4]: using rand() function with OpenMP

	От:	Sergey Chadov
	Дата:	24.05.09 07:42

Здравствуйте, wotker, Вы писали:

W>Мне не понятна Ваша фраза "Поэтому каждый поток имеет свой seed.". Меня интересует, как это реализовано. Если Вам не сложно, приведите кусок кода на С

Так почитайте исходники CRT, благо их никто не скрывает.

int __cdecl rand (
        void
        )
{

        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );

}

_ptiddata __cdecl _getptd_noexit (
        void
        )
{
    _ptiddata ptd;
    DWORD   TL_LastError;

    TL_LastError = GetLastError();

    /*
     * Initialize FlsGetValue function pointer in TLS
     */
    __set_flsgetvalue();

    if ( (ptd = FLS_GETVALUE(__flsindex)) == NULL ) {
        /*
         * no per-thread data structure for this thread. try to create
         * one.
         */
       [...skipped...] 
    }

    SetLastError(TL_LastError);

    return(ptd);
}

где

   
#define FLS_GETVALUE ((PFLS_GETVALUE_FUNCTION)TlsGetValue(__getvalueindex))

Это майкрософтовские, но не суть.

W> (т.к. я уже не понимаю как openMP определяет, какие одни переменные должны быть локальными, а другими — общими).
OpenMP здесь не причем.

W>Касательно фейверков:
W>

W>The rand() function need not be reentrant. A function that is not required to be reentrant is not required to be thread-safe.

W>Поэтому, нет гарантии, что они не случатся в других реализациях.

Стандарт С++ вообще не определяет никакой потокобезопасности. Поэтому, строго говоря, ни одна функция стандартной библиотеки потокобезопасной не является. Однако есть еще и здравый смысл, благодаря которому оно все же работает так как работает.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

Re[4]: using rand() function with OpenMP

	От:	Аноним 872
	Дата:	24.05.09 07:50

W>Мне не понятна Ваша фраза "Поэтому каждый поток имеет свой seed.". Меня интересует, как это реализовано.
thread local storage

Re[5]: using rand() function with OpenMP

	От:	wotker
	Дата:	24.05.09 08:10

Вопросов нет. Спасибо.

Re[3]: using rand() function with OpenMP

	От:	Кодт модератор
	Дата:	24.05.09 08:57

Здравствуйте, Sergey Chadov, Вы писали:

SC>Если бы функция rand сохраняла свое состояние в глобальной переменной, то при вызове ее из разных потоков были бы та-а-акие фейерверки. Поэтому каждый поток имеет свой seed.

Ну прямо уж феерверки. Что, сложно сделать атомарный доступ к семечку? На interlocked?
Конечно, TLS — это тоже решение: у каждого потока семечко своё.
Но ведь требования о независимости случайных последовательностей в разных потоках в Стандарте не записаны, так что это самодеятельность MS.

Ладно бы поведение нереентерабельной функции было не определено при реентере. (Как, скажем, printf с двух рук стрелять).
Это легко исправляется, если мы поместим вызов такой функции в критическую секцию.

CCriticalSectrion csRand;
int tsrand() { CCritSecLock lock(&csRand); return rand(); }

Однако, хотя вызовы строго сериализованы, эффект прежний — у нас не одна последовательность, а много, на каждый поток своя.

Перекуём баги на фичи!

Re[5]: using rand() function with OpenMP

	От:	Кодт модератор
	Дата:	24.05.09 18:22

Здравствуйте, Sergey Chadov, Вы писали:

SC>Если критическая секция без спинкаунта — это сильный удар по производительности. Если со спинкаунтом — то конечно значительно менее сильный, но что-то мне кажется что решение с tls проще и эффективнее.

Оно не проще, оно иначе. У него семантика другая. Функция-то с побочным эффектом.
А критическая секция — просто пример, как сделать сериализацию.

Перекуём баги на фичи!

Re[5]: using rand() function with OpenMP

	От:	Кодёнок
	Дата:	26.05.09 06:30

Здравствуйте, Sergey Chadov, Вы писали:

SC>Если никак не защищать — то прямо фейерверки. Я сам наблюдал на самодельном генераторе.

Можно подробнее, какие эффекты появляются?

Re[6]: using rand() function with OpenMP

	От:	Sergey Chadov
	Дата:	26.05.09 11:52

Здравствуйте, Кодёнок, Вы писали:

SC>>Если никак не защищать — то прямо фейерверки. Я сам наблюдал на самодельном генераторе.

Кё>Можно подробнее, какие эффекты появляются?

Случайность сильно страдает

Представь несколько тысяч потоков ломятся к одному seed'у. Некоторые получают его до того как он изменился(между read и write) — имеем кучу одинаковых значений, потом все дружно ломятся его писать ну и так далее

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

Re[6]: using rand() function with OpenMP

	От:	Кодт модератор
	Дата:	27.05.09 08:20

Lock-free алгоритм

long seed;

int rand()
{
    for( ; ; )
    {
        long s0 = GET(&seed);
        long s1 = (s0 * 214013) + 2531011;
        if(CAS(&seed, s0, s1))
            return (s1>>16) & 0x7FFF;
    }
}

inline long GET(long* source)
{
    return *source;
    // или для параноиков - заведомо атомарная операция
    return InterlockedCompareExchange(source, 0, 0);
}

inline bool CAS(long* destination, long oldValue, long newValue)
{
    return InterlockedCompareExchange(destination, newValue, oldValue) == oldValue;
}

Правда, он не wait-free; если между GET и CAS кто-то будет всё время вламываться и выполнять rand() полностью, то получим голодание.
Как допилить до wait-free — надо подумать.

... << RSDN@Home 1.2.0 alpha 4 rev. 1207>>

Перекуём баги на фичи!