[سوال] الگوریتم‌های همزمان\ thread

[sara.m12]

سلام.

من یکم با برنامه نویسی همروند در c مشکل دارم.

مثلا برای محاسبه ماکزیمم مقادیر یک آرایه طوری که ماکزیمم هر بخش از آرایه را یک thread انجام دهد باید چی‌ کار کنم ؟
ممنون

[shahmohammadi]

سلام.
در زبان سي به چند طريق مي شه نخ ايجاد كرد شما از كدوم روش مي خواهيد اين كارو انجام بديد.
الگوريتمش به اين صورته.

نخ اول از خانه 0 تا نصف آرايه رو پيمايش كنه و ماكس رو پيدا كنه.
نخ دوم هم همزمان از خونه نصف تا آخر رو بررسي كنه.
دو ماكس باهم مقايسه شند و بيشترينشون نشون داده شه.

[sara.m12]

man piadesazi barname aye ham ravand dar c va java ro mikham kar konam mamnoon.

[shahmohammadi]

براي C مي تونيد OpenMP ياد بگيريد.
و يا از توايع API ويندوز كمك بگيريد. البته روش و كتابخانه زياد هست. من خودم با UPC كه براي شما دردسرش زياده (دانلود و نصب لينوكس و بعد كامپايل سورس كد كامپايلر UPC و بعد چند دردسر ديگه) كار كردم.

براي استفاده از توابع API ويندوز به لينك زير رجوع كنيد:
اعمال چند نخی برای کد؟

در مورد جاوا هم چيزي نمي دونم.

راستي يكم تلاش كنيد برنامه شو هم مي نويسيد.

[babyy]

براي C مي تونيد OpenMP ياد بگيريد.

یکم در مورد این omp توضیح بدید ممنون میشیم

این مثالی که زده اینجا (تو بخش Thread creation) :
http://en.wikipedia.org/wiki/OpenMP
واسه من یدونه خروجی داد.چرا؟ چون cpu ی من یک هسته ای؟!؟

[shahmohammadi]

یکم در مورد این omp توضیح بدید ممنون میشیم

با راهنما های pragma توی سی یا فرترن موازی سازی می کنه. و یه تعداد متغیر برای خودش هم داره.
اینجا مرجع کاملش هست.
توی لینوکس قاصدک که من چیز اضافی برای اجراش دانلود و نصب نکردم با همون gcc که آماده توش نصب بود اجرا شد. ولی در DevCpp که توی ویندوز بود نتونستم فایل های اینکلودش رو ‍پیدا کنم. دنبالش رو هم نگرفتم.

واسه من یدونه خروجی داد.چرا؟ چون cpu ی من یک هسته ای؟!؟

توی لینوکس این دستور برای اون مثال برای من 4 تا Hello world چا‍پ کرد.

کد:

gcc -fopenmp hello.c -o hello
./hello

مطمینید که یک هسته ای هست؟ برای کامپایل از همون دستور استفاده کردید که اونجا گفته؟
این طوری تغییرش بدید ببینید درست شناخته OpenMP رو:

کد:

#include <stdio.h>

int main(void)
{
omp_set_num_threads(5);
#pragma omp parallel
printf("Hello, world.\n");

return 0;
}

این هم یک مثال دیگه با خروجیش:

کد:

#include <stdio.h>
#include <omp.h>


int main(){
#pragma omp parallel
{
printf("%d test1\n",omp_get_thread_num());
}
printf("test2\n");
return 0;
}

خروجیش به این صورت اومد:

کد:

3 test1
1 test1
0 test1
2 test1
test2

[shahmohammadi]

به عنوان یک مثال کاربردی تر این هم یک برنامه برای جمع اعداد از 1 تا 1000.

کد:

/*
Sum of 1 to N in OpenMp
*/

#include <stdio.h>
#include <omp.h>

#define N 1000 //sum of 1 to 1000 is 500500

int main()
{
    int sum = 0,//sum of all
        sum0,//sum for each thread
    i;

    #pragma omp parallel private(sum0)
    {
        sum0 = 0;

        #pragma omp for
        for(i=1; i<=N; i++)
            sum0 += i;

        #pragma omp critical
        {
            sum += sum0;
        }
    }

    printf("sum of 1 to %d is: %d\n", N, sum);

    return 0;
}

توضیح:
دستور زیر یک بلوک {} بعد از خورش رو تحت تاثیر قرار می ده و اونو موازی می کنه:

کد:

#pragma omp parallel private(sum0)‍

تمام نخ ها به طور مستقل این بلوک رو از اول تا آخر اجرا می کنند.
عبارت private(sum0)‍ در این دستور باعث می شه که در کل بلوک sum0 یک متغیر خصوصی باشه.
یعنی در داخل بلوک هر کدوم از نخ ها (هر تعداد که می خواد باشه) یک sum0 دارند که مقادیرشون متفاوت از همه. اگه نخ اول sum0 رو تغییر بده sum0 خودش رو تغییر داده. اما sum مشترکه و اگه یکی از نخ ها اونو تغییر بده همه‌ی نخ ها می بینند که اون تغییر کرده.
با رسیدن به دستور اول بلوک همه‌ی نخ‌ها sum0 خودشون رو 0 می‌کنند.

کد:

#pragma omp for
        for(i=1; i<=N; i++)
            sum0 += i;

یک for موازی تشکیل می‌شه. هر کدوم از نخ ها که رودتر برسه تکرار اول رو اجرا می کنه. و sum0 خودش رو بعلاوه‌ی 1 می‌کنه. در همین حین نخ های دیگر هم زمان با این کار یکی دیگه از تکرار ها رو انجام می‌دهند. وبعد به تکرار بعدی می‌روند.تا اینکه این فور تموم می‌شه.

کد:

#pragma omp critical
        {
            sum += sum0;
        }

از اونجایی که sum مشترک هست اگه هم زمان دوتا نخ بخاند روش بنویسند اشتباه می‌شه و خروجیش غیر قابل ‍پیش‌بینی در می‌آد. بنابراین وقتی که می خواهیم روش بنویسیم باید اون قطعه کد رو بحرانی (critical) کنیم. وقتی یک نخی رفت به ناحیه‌ی بحرانی باید نخ های دیگر هنگام رسیدن به اون جا منتظر بمونند تا نخی که در اون ناحیه هست اونجا رو ترک کنه و بعد یکی دیگه بره به اون ناحیه.

حالا sum مجموع اعداد از 1 تا N (که در اینجا 1000 بود) رو داره.

[sara.m12]

میتونید راهنمایی کنید مراحل نصب جاوا در لینوکس به چه صورت هست?

[babyy]

مطمینید که یک هسته ای هست؟ برای کامپایل از همون دستور استفاده کردید که اونجا گفته؟
این طوری تغییرش بدید ببینید درست شناخته OpenMP رو:

کد:

#include <stdio.h>

int main(void)
{
omp_set_num_threads(5);
#pragma omp parallel
printf("Hello, world.\n");

return 0;
}

سلام
خروجی این برنامه شد ۵ تا عبارت Hello, world.


-------------
خروجی برنامه دومیتون که با خروجیش گذاشته بودید شد :

کد php:

0 test1
test2 


مشکل از که اینطوری میشه؟

---

میتونید راهنمایی کنید مراحل نصب جاوا در لینوکس به چه صورت هست?

این سوال تو بخش نرم افزار های آزاد؛ لینوکس؛ بپرسید جواب داده میشه

[shahmohammadi]

با سلام دوباره.
مي‌بخشيد كه يكم دير به اين تاپيك اومدم.
اينطور كه معلومه كامپايلرتون از OpenMp پشتيباني مي‌كنه. تو يه جا خوندم كه تمام كامپايلرهاي مدرن ازش حمايت مي‌كنند. كامپايلر GCC ويندوز من هم ديدم چون نسخه‌ش 2 هست اونو نداشت.
حالا كه شما كامپايلرتون ازش حمايت مي كنه حتما سي‌پي‌يو تون يك‌هسته‌اي هست. براي اطمينان از اين موضوع مي تونيد در taskManager در زبانه‌ي Processes بر روي يكي از پردازه‌ها راست كليك كرده و گذينه‌ي Set Affinity رو بزنيد. اين كار براي اين هست كه براي پردازه هاي مختلف، هسته‌هايي رو كه دلتون مي خاد رو بديد. ولي ما ازش استفاده مي كنيم تا تعداد هسته ها رو ببينيم و بعد پنجره رو ببنديم. در پنجره اي كه گفتم به تعداد هسته‌هاي پردازنده تون چك‌بوكس فعال داريد.
اگه ديديد يك‌هسته‌اي هست OpenMp تون درست كار مي‌كنه و ايرادي نداره و در برنامه‌هاتون مي تونيد ازش استفاده كنيد.