현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

Linear Congruential Generator를 병렬화하고싶습니다.

Samuro의 이미지
글쓴이: Samuro / 작성시간: 금, 2016/05/20 - 4:06오후

우선 이렇게생긴 코드입니다.

#define MODLUS 2147483647
#define MULT1       24112
#define MULT2       26143
 
    long zi, lowprd, hi31;
 
    zi     = zrng[stream];
    lowprd = (zi & 65535) * MULT1;
    hi31   = (zi >> 16) * MULT1 + (lowprd >> 16);
    zi     = ((lowprd & 65535) - MODLUS) +
             ((hi31 & 32767) << 16) + (hi31 >> 15);
    if (zi < 0) zi += MODLUS;
 
    lowprd = (zi & 65535) * MULT2;
    hi31   = (zi >> 16) * MULT2 + (lowprd >> 16);
    zi     = ((lowprd & 65535) - MODLUS) +
             ((hi31 & 32767) << 16) + (hi31 >> 15);
    if (zi < 0) zi += MODLUS;
 
    zrng[stream] = zi;
 
    return (zi >> 7 | 1) / 16777216.0;

이 현재 만드는 프로그램에서 이LCG가 병목이어서 병렬화시키고 싶습니다. 숫자를 바꿀순 없고 저상태로 linear하게 실행했을때와 동일한 결과가 나와야 합니다.

합동식을 풀어서 병렬화 할수 있다고 하는데 도저히 모르겠네요 며칠째 이것만 보고있는데 수학이 약해서 그런지...

http://scicomp.stackexchange.com/questions/1274/how-can-i-seed-a-parallel-linear-congruential-pseudo-random-number-generator-for

이 질문에 답변을 보면 x(n)= a*x(n-1)+c 형태일때 병렬화 하는 방법이 나와있는데 위의 코드에도 가능한 방법인가요? 이해한것 같은데도 저 LCG는 병렬화 못하겠네요.

어떻게해야 저 코드를 병렬화 할 수 있을지, 그러니까 x(999) 까지 구하지않고 x(1000)을 구하려면 어떻게 해야 하는지.. 제발 도와주세요 ㅠㅠㅠ

Forums: 
프로그래밍 QnA
익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2016/05/22 - 10:54오전

1.
http://www.cs.uml.edu/~giam/Mikkeli/Inventory/lcgrand.c
참고해서 아래 코드로 테스트해 보았는데, 동일한 결과가 나옵니다. 속도는 한 25% 정도 더 빠릅니다. 아마도 인용하신 코드는 64bit 곱셈이 없거나, mod 연산이 느린 환경에 대비한 코드가 아닌가 생각합니다.

#include <stdint.h>
 
float lcgrand2(int stream)
{
    long zi;
 
    zi = zrng[stream];
    zi = (uint32_t)((630360016u * (uint64_t)zi) % 2147483647u); // 630360016 == 24112 * 26143
    zrng[stream] = zi;
 
    return (zi >> 7 | 1) / 16777216.0;
}

이 코드를 활용하면, 링크하신 글의 방법론을 적용하기 쉬울 거 같습니다.

2.
http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477

http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484

이 곳에 소개된 랜덤함수 중 하나를 테스트해 보았는데, 속도는 약간 빠른 정도인데, 랜덤 특성이 좋다고 하니까 참고해도 될 거 같습니다.

3.
http://www.reedbeta.com/blog/2013/01/12/quick-and-easy-gpu-random-numbers-in-d3d11/

가만히 생각해 보면 "난수라는 특성 상",
CPU나 GPU의 멀티 코어를 활용해서 난수 수열을 생성하기 위해서는 그냥 seed값을 공유하지 않게 구현해서 코어별로 난수를 생성해서 합쳐도 될 거 같습니다.
예를 들어 2CPU를 활용해서 x[0] ~ x[999]를 얻기 위해서는 CPU0으로 x[0] ~ x[499]를 생성하고 CPU1에서는 x[500] ~ x[999]를 생성하는 식으로요.
메모리 접근에 병목만 없다면 이상적으로는 코어 수에 비례해서 이득을 볼 수 있겠죠.
그런데 랜덤 함수가 이상적이 아니기 때문에 또 seed값을 어떻게 만들었느냐에 따라서, 이렇게 생성된 수열의 랜덤 특성이 떨어지게 되는 거 같습니다. 위 링크를 살펴 보시면 그걸 보강하는 방법을 소개하고 있습니다.

chanik의 이미지

글쓴이: chanik / 작성시간: 월, 2016/05/23 - 2:09오후

지나가다 잘 배웠습니다.

질문을 보고 저런 함수를 어떻게 병렬화할까 싶어서 수식으로 만들어보다가 집어던졌는데
저렇게 간단히 정리가 되는군요. 다른 자료도 좋네요.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.