محاسبات موازی

[ravegoat]

محاسبات موازی به دسته ای از فرآیند ها اطلاق می شود که هر کدام بخشی از پردازش یک مسئله ی محاسباتی را بر عهده می گیرند. روند کاری این فرآیند ها در نهایت منجر به حل مسئله می شود.
تصمیم ما در این قسمت به کارگیری محاسبات موازی برای رسیدن به هدف است. هر پروسه ی حسابی می تواند به طور مستقل تحت یک هسته ی پردازنده اجرا شود. دستورالعمل های MultiThreading در فناوری .Net تا حدی مدیریت این کار را بر عهده می گیرند. اما موضوع بحث ما غیر این است. ما قصد داریم هسته های پردازشی (از نوع نرم افزاری) را روی رایانه های مختلف قرار دهیم. رایانه ها بایستی در یک شبکه باشند تا هسته ها بتوانند با هم تعامل داشته باشند. این عمل از جهتی شبیه به محاسبات ابری (Cloud Computing) است.

نکته:
محاسبات موازی با پردازش موازی در GPU متفاوت است. GPU یا واحد پردازنده گرافیکی می تواند یک دستورالعمل را همزمان بر روی n داده اجرا کند. بهره گیری از این قابلیت GPU در قالب برنامه نویسی CUDA و امثالهم مطرح می شود که ما از شرح آن صرف نظر می کنیم. واحد پردازشی ما در این موضوع CPU است و الزامی وجود ندارد CPU ها که در یک شبکه قرار دارند، دستور های مشابهی را اجرا نمایند.

روش کلی:
نرم افزار برای پیاده سازی محاسبات موازی می تواند داری دو بخش باشد: هسته ی اصلی و هسته ی محاسباتی.
هسته ی اصلی داده های مسئله ها را از طریق شبکه به هسته های محاسباتی می دهد. هسته های محاسباتی داده ها را پردازش می کنند و نتایج را از راه شبکه، در اختیار هسته ی اصلی می گذارند. هسته ی اصلی اطلاعات دریافتی را تحلیل می کند و جواب مسئله را گزارش می دهد. به عبارتی دیگر در شبکه هر رایانه بخشی از پردازش را انجام می دهد گویی که پردازنده ها با هم ادغام شده اند.
توجه داشته باشید این روش زمانی بهینه است که نرخ تعامل اطلاعاتی در شبکه بین هسته های نرم افزار کم تر از بار پردازشی باشد.

مثال:
مسئله: به دست آوردن اعداد اول در بازه 1 تا 10 میلیون
تعداد رایانه ها در شبکه: 10 سیستم + یک سرور

ابتدا هسته ی اصلی را روی سرور اجرا می کنیم. هسته های پردازشی را روی کلاینت ها نصب می کنیم. آدرس IP کلاینت ها را به هسته ی اصلی می دهیم. حالا هسته ی اصلی وظیفه دارد پردازش کلی را بین 10 سیستم تقسیم کند. بدین ترتیب هسته ی پردازشی اول اعداد اول بین 1 تا یک میلیون را به دست مي آورد ، هسته ی دوم اعداد اول بین یک میلیون تا دو میلیون را و به همین ترتیب تا هسته ی دهم. هر هسته پس از پایان کارش، لیست اعداد اول به دست آمده را در قالب Array به هسته ی اصلی می فرستد. در نهایت هسته ی اصلی با مرتب کردن نتایج (Sort)، آن ها را گزارش می کند.

در پست آینده برای مثال بالا یک الگوریتم در VB.Net طراحی می کنیم. به علاوه طراحی ماژول هماهنگ با محاسبات موازی در VB.Net نیز آموزش داده می شود.

دوستان می توانند نظرات یا سوالات خود را در این جا بیان کنند.:1. (26):
آرمین:11():

[ravegoat]

با سلام!

توابعی که در محاسبات موازی به کار گرفته می شود باید این قابلیت را داشته باشند که بخشی از محاسبه را در محدوده ی تعیین شده انجام دهند. با توجه به مثال پست اول؛ تابع پویش گر اعداد اول طوری برنامه ریزی می شود تا اعداد را در یک بازه ی خاص بررسی کند. کد نویسی تابع بدین صورت است:





Imports System.Math
Public Class SimpleClass
Inherits MarshalByRefObject
Dim adder As Boolean

Public Function NumScan(ByVal firstno As Long, ByVal lastno As Long) As ArrayList
Dim comparr As New ArrayList()
comparr.Add(2)
For i As Integer = 3 To Int(Sqrt(lastno))
adder = True
For j As Integer = 0 To comparr.Count - 1
If Int(Sqrt(comparr(j))) >= i Then Exit For
If i Mod comparr(j) = 0 Then
adder = False
Exit For
End If
Next
If adder = True Then comparr.Add(i)
Next
For i As Long = firstno To lastno
adder = True
For j As Integer = 0 To comparr.Count - 1
If Int(Sqrt(comparr(j))) >= i And comparr(j) <> i Then Exit For
If i Mod comparr(j) = 0 Then
adder = False
Exit For
End If
Next
If adder = True Then NumScan.Add(i)
Next
End Function

End Class




کلاس SimpleClass (شامل (NumScan بر روی هسته ی محاسباتی قرار می گیرد و با توجه به آرگومان تابع، اعداد طبیعی بین firstno و lastno را بررسی می کند. اعدادی که در این بین اول باشند در ArrayList تعریف شده وارد می شوند.
الگوریتم یافتن اعداد بر اساس غربال اراتستن است. در این روش برای بهبود سرعت پردازش، ابتدا یک حلقه برای یافتن مقسوم علیه های اول در نظر گرفته شده است. حلقه ی دوم عمل اصلی را انجام می دهد.

هسته ی اصلی می تواند با توجه به تعداد هسته های محاسباتی، بازه های تفکیک شده به دست آورد و سپس هر بازه را با توجه به رابطه ی زیر به یک محاسبه گر نسبت دهد:

[First, Last] => ScanNum(First As Long, Last As Long)

در نهات با ارسال دستور، محاسبات موازی آغاز می شوند. در ادامه در مورد نحوه ی تعامل هسته ها در شبکه بحث می کنیم.:11():

[ravegoat]

با سلام!

در این بخش پیرامون تعامل هسته ی اصلی و هسته ی محاسبه گر تحت شبکه بحث می کنیم. ما برای برقراری ارتباط از TCP/IP کمک می گیریم. در این پروتکل به آدرس IP هسته ها و پورت TCP نیاز است. هسته ی محاسبه گر در حالت شنود (Listen Mode) روی پورت TCP قرار می گیرد و هسته ی اصلی داده ها را به روی این درگاه می فرستد. هسته ی محاسباتي پس از انجام پردازش، اطلاعات را به آدرس IP هسته ی اصلی می فرستد.
برای پیاده سازی TCP/IP در VB.Net از کنترل Winsock و یا کلاس Runtime Remoting استفاده می کنیم. برای استفاده از Winsock محدودیت هایی وجود دارد از جمله محدودیت در نرخ اطلاعات مبادله شده. پس به سراغ Runtime Remoting می رویم و Refrence آن را به پروژه اضافه می کنیم. اگر در تعریف توابع کلاس Remoting به درستی عمل کنیم، می توانیم هر نوع داده ای را با هر حجمی مبادله کنیم. کلاس Remoting در پذیرش ماژول ها منعطف است و مانند Winsock سبب هنگ کردن رابط گرافیکی برنامه نمی شود.
توجه کنید که در پست دوم یک ماژول برای یافتن اعداد اول تعریف شده است. این قطعه کد با نام SimpleClass.vb روی نرم افزار هسته ی محاسبه گر قرار می گیرد و برای طرفین ارتباط Remoting شناسانده می شود.

تحلیل سورس هسته ها:

تابع آماده سازی:


Dim sc As SimpleClass

Public Function Initialize() As Boolean
If sc Is Nothing Then
Dim chan As New TcpChannel()
ChannelServices.RegisterChannel(chan)
Dim t As Type = Type.GetType("Server.SimpleClass")
sc = Activator.GetObject(t, "tcp://localhost:9999/SimpleClass")
If sc Is Nothing Then
MsgBox("Could not initialize the Main Kernel. Check your configuration.")
Return False
End If
End If
Return True
End Function

این تابع هسته اصلی را آماده می کند تا دستورات را به پورت 9999 روی localhost و به سمت ماژول SimpleClass بفرستد.



If Not Initialize() Then Return
Dim recarrl As ArrayList = sc.NumScan(TextBox1.Text, TextBox2.Text)
MsgBox("Data is received from the Computing Kernel. Now press OK to sort data.", 64)
For i As Integer = 0 To recarrl.Count - 1
ListBox1.Items.Add(recarrl(i))
Next
recarrl = Nothing

این خطوط دستور را تنظیم و برای اجرا روی هسته ی محاسباتی ارسال می کنند.


sc.NumScan(TextBox1.Text, TextBox2.Text)
ابتدا و انتهای بازه را از طریق جعبه ی متنی دریافت و متد NumScan را فعال می کند. نتیجه ی پردازش در متغیر recarrl ذخیره شده و محتویات آن با یک لوپ وارد جعبه ی لیستی می شود.

حالت شنود:


Dim channel As New TcpChannel(9999)
ChannelServices.RegisterChannel(channel)
RemotingConfiguration.ApplicationName = "SimpleRemotingServer"
Dim t As Type = Type.GetType("Server.SimpleClass")
RemotingConfiguration.RegisterWellKnownServiceType (t, "SimpleClass", WellKnownObjectMode.SingleCall)]
این کد ها با بارگذاری نرم افزار هسته ی محاسباتی اجرا می شوند و پس از دریافت دستور، پردازش را آغاز می کنند.

بنده پروژه ی محاسبات موازی را در این جا پیوست کردم که به راحتی می توان آن را توسعه داد و عملیات های محاسباتی را روی این طرح پیاده نمود.:cool:

توجه داشته باشید در نمونه ی بالا هسته ی اصلی و هسته ی محاسباتی باید روی یک سیستم اجرا شوند چون آدرس localhost (127.0.0.1) برای اتصال تعریف شده است که به راحتی می توان آن را تغییر داد.

در آینده مسایل مربوط به تحلیل داده ها و مدیریت تبادل اطلاعات تشریح می شود.:11():

[ravegoat]

با سلام!

در این قسمت مدیریت تبادل اطلاعات تشریح می شود:

مهم ترین بخش، ارسال درخواست های محاسباتی است. هسته ی اصلی باید درخواست ها را به طور موازی کند. این ارسال باید به گونه ای صورت گیرد که فرستنده منتظر جواب هسته ی محاسباتی نباشد. یعنی با فرستادن درخواست به یک هسته، بلافاصله درخواست بعدی به یک هسته ی دیگر فرستاده شود. هسته ی اصلی پس از ارسال تمام درخواست ها منتظر پاسخ می ماند. اگر این طرح تحت دات نت پیاده شود، اختالالی در نتایج رخ نمی دهد.
نکته ی بعدی آدرس IP هسته های محاسبه گر است. در پروژه ی مثال، هسته ی اصلی با یک جعبه ی لیستی IP و شماره ی پورت را دریافت کرده سپس با استفاده از یک دسته بندی ساده، بازه هایی از اعداد اول را به سوی IP ها روانه می کند. به دلیل رعایت اصل ارسال درخواست های موازی، یک تایمر عمل فرستادن را بر عهده می گیرد.


برای استفاده از پروژه ی مثال که وظیفه ی یافتن اعداد اول در بردی معین را دارد:

1-ابتدا و انتهای بازه را در نرم افزار Main Kernel مشخص کنید (مقادیر را در جعبه ی متنی From و To قرار دهید.).

2-در ادامه با کلیک بر روی دکمه ی Add آی-پی و شماره ی پورت هسته های محاسبه گر را وارد کنید؛ مثلا" 192.168.0.2:9999
که 192.168.0.2 مقدار آی-پی و 9999 شماره ی پورت TCP است که با علامت نقل قول از IP جدا شده است.

3-اکنون نرم افزار Computing Kernel را روی رایانه هایی که به عنوان هسته ی محاسبه گر در نظر گرفته شده اند اجرا کنید. این برنامه ها روی پورت 9999 به حالت شنود می مانند.

4-در آخر در نرم افزار Main Kernel روی دکمه Compute کلیک کنید. پس انجام محسابات، اعداد اول در بخش Result نمایش داده می شوند.


پروژه ی مثال با سورس VB.Net 2008 پیوست شده است.:cool:

شکر خدا بحث محاسبات موازی به تمام رسید. البته این تاپیک فقط یک کلیت را از محاسبات موازی به مخاطبین ارائه می دهد. روند محاسباتی هر نرم افزار را می توان با روش های موازی سازی تسریع بخشید. قوانینی مثل قانون Amdahl یا Gustafson می توانند بازده ی موازی سازی در نرم افزار ها را مشخص کنند (توضیح این قوانین در این مقاله نمی گنجد.).

با سپاس
آرمین:11():