epsi1on
epsi1on
خواندن ۱۲ دقیقه·۳ سال پیش

مختصری از مهندسیِ نرم‌افزهایِ روش اجزاءِ محدود : انتخاب زبان برنامه‌نویسی

برای دیدن فهرست باقی نوشته‌های این مجموعه به قسمت اول (کلیات) بروید

مقدمه

بعضی‌ها میگن که زبان سی‌شارپ برای ساختن برنامه‌های المان‌محدود مناسب نیست چون سرعتش کمه ولی مثلا زبان ++C و یا Fortran مناسب برنامه های المان‌محدود هستند چون سرعتشون خیلی بالاتره. یا مثلا خودم شنیدم که دوستی بهم گفت نوشتن برنامه تحلیل اجزامحدود با زبان سی‌شارپ مثل کندن یک تونل با قاشقه!

مدل اجزا‌ء محدود! برای خالی نبودن عریضه...
مدل اجزا‌ء محدود! برای خالی نبودن عریضه...


توی این پست میخوام در مورد این مطلب صحبت کنم و میخوام بگم که چرا یک برنامه ی تحلیل اجزامحدودِ خوب میتونه با زبانی مثل سی‌شارپ نوشته شده باشه...


سی‌شارپ یا سی؟ مساله این است ...

سی vs سی‌شارپ (منبع عکس)
سی vs سی‌شارپ (منبع عکس)


زبانهای برنامه نویسی به چند نسل تقسیم میشن: نسل ۱ الی نسل ۶ (بیشتر). تفاوت این نسلها دسترسی هایی هست که به برنامه‌نویس توسط زبان داده میشه. یعنی چی؟ فرضا زبان اسمبلی (که نسل ۲) هست رو با زبان سی‌ (که نسل ۳ هست) مقایسه میکنیم. توی زبان اسمبلی، دستِ برنامه‌نویس خیلی باز هست و برنامه نویس روی جزییات سخت افزار خیلی تسلط داره. مثلا رجیسترهای CPU و شاید خیلی چیزهای دیگه. ولی از طرف دیگه نوشتن برنامه به زبان اسمبلی اولا نیازمند دانش در زمینه‌ی سخت‌افزار هست، و دوما نیازمند تمرکز بالای برنامه نویس. این قضیه یکجورهایی tradeoff (یا بده‌بستان خودمون) هست. یک چیزی میدیم و یک چیزی میگیریم. یعنی برنامه هایی که به زبان اسمبلی نوشته میشن سرعتشون فوق‌ِبالا هست! شاید بالاترین سرعتی که میشه بهش دست یافت و همچنین تسلط کامل روی سخت افزار داره و میتونه از قابلیت‌های سخت افزار تمام استفاده رو بکنه. ولی از طرفی برنامه نویسی باهاش سخته و کار هرکسی نیست، یا اگه بهتر بگم کار هیچکسی نیست :) البته بجز افراد اندکی که هم تمرکز بالا دارن و هم دانش سخت افزاری و صد البته تجربه. اینم بگم که بغیر از بعضی وقتها، درست نیست که با زبان اسمبلی کار کنیم. خودم تاحالا این کارو انجام ندادم :)

توی این ویدیو یک برنامه ساده زبان سی رو با زبان اسمبلی‌اش مقایسه میکنه. می‌تونید ببینید یک برنامه‌ی ۱۰-۱۵ خطی با زبانِ سی، اگر به زبان اسمبلی بخواد نوشته بشه چقدر عجیب و سخت‌خوانا میشه! البته برای من‌وشما، نه اهل فن :)

زبانهای برنامه‌نویسیِ نسل‌ِسوم شامل زبانهایی مثل سی و جاوا و سی‌پلاس‌پلاس و سی‌شارپ و کاتلین و گو و ... هست که در عکس زیر یک تعدادیشون رو میتونید ببینید.

 زبانهای برنامه نویسی نسل سوم (منبع عکس)
زبانهای برنامه نویسی نسل سوم (منبع عکس)

خوب بین همین زبان‌های برنامه‌نویسیِ نسل سوم، باز هم یک دسته‌بندی ای وجود داره. مثل همون بده‌بستان (tradeoff) که بالاتر گفتیم. مثلا دوتا زبان سی و سی‌شارپ رو در نظر بگیرید. توی زبانِ سی ما به خیلی چیزها راحت تر دسترسی داریم و حتی میتونیم کدهای اسمبلی رو بصورت inline توی برنامه بیاریم یا از اشاره‌گرها استفاده کنیم که خوب خیلی قابلیتهای خوبی هستن. ولی توی سی‌شارپ از این خبرها نیست که بخواید کد اسمبلی کنار کدمون بیاریم! یا اینکه مثلا توی زبان سی خیلی راحت میشه از قابلیت SIMD پردازنده استفاده کرد و برنامه رو اصطلاحا vectorize کرد و سرعت رو (طبق تئوری) چند برابر کرد ولی تا همین چند سال پیش توی سی‌شارپ همچین قابلیتی بطور رسمی وجود نداشت. از طرف دیگه سی‌شارپ به ما شی‌گرایی رو میده که سی نداره و این قابلیت شی‌گرایی میتونه توی برنامه‌های پیچیده بهمون خیلی کمک کنه. و سی‌شارپ چیز دیگری بنام BCL (یا همون Base Class Library) رو بصورت رسمی بهمون میده که بازهم توی برنامه‌های عملی خیلی کمک کننده هست.

خوب تا اینجا در مورد تفاوتهای دو زبان سی و سی‌شارپ مقدمه گفتیم و توضیحاتی دادیم. امیدوارم حوصلتون سر نرفته باشه...

به همین دلایلی که بالاتر گفتیم خیلی‌ها میگن با زبان سی‌شارپ نمیشه (یا نباید) یک برنامه محاسباتی سنگین رو نوشت. چون سرعتش کمه... ولی به نظرم این همه‌ی ماجرا نیست. به نظرم انتخاب زبان برنامه نویسی مناسب تنها یکی از چند عاملی است که روی کارایی یک نرم افزار محاسباتی سنگین - نظیر تحلیل FEM - اثر میگذاره و چندین عامل دیگر هم وجود داره که به تجربه و دفعات دیده ام. مهمترین مواردش اینها هستند:

انتخاب الگوریتم بهینه و مناسب

معمولا برای یک مساله شناخته شده (مثل مساله هشت وزیر) یا مساله ی یافتن دترمینان ماتریس با ابعاد دلخواه، الگوریتمهای متفاوتی ارایه میشه که از نظر سرعت و دقت و پیچیدگی با هم تفاوت دارند. یک مثال رو بررسی میکنیم. فرضا ما میخوایم یک برنامه بنویسیم که بره دنبال اعداد اول (prime) کوچکتر از ۱۰۰۰ بگرده و برامون نمایشش بده. این مثال رو قبلا دیده بودم و در ادامه می‌بینید اش

مثال یافتن اعداد اول

خوب ما میتونیم یک تابع (یا method) بنویسیم که یک عدد صحیح رو بعنوان ورودی میگیره و تعیین میکنه آیا این عدد جزو اعداد اول هست یا خیر. ویکی‌پدیا عدد اول رو اینطوری تعریف کرده : عددی که غیر از خودش و عدد ۱ به عدد دیگری بخش پذیر نباشد. پس میتونیم یک حلقه بنویسیم و توش از یک تا خود عدد رو چک کنیم و باقیمانده ورودی رو نسبت به اون عدد بگیریم (با عملگر % توی سی‌شارپ) اگر باقیمانده صفر بود یعنی بخش‌پذیره و اگر بخش‌پذیر بود چک میکنیم که عدد ۱ و خود عدد ورودی نباشه و اگر نبود میفهمیم عددمون اول نیست. میشه کد اینطوری نوشت:

//s برای تعیین اینکه ایا عدد ورودی جز اعداد اول است یا خیر public bool IsPrimeNumber(int x) { int counter = 0; int to = x; for(var i=2; i <to ;i++) if(x % i == 0) return false; return true; }

میتونیم از یک تابع دیگه هم استفاده کنیم:


public static Main(string[] args) { for(int i=0;i<=1000;i++) if( IsPrimeNumber(i)) Console.Write(i+&quot is prime&quot); }

خوب این کد برامون لیست اعداد صحیح کوچکتر از ۱۰۰۰ رو در میاره از لحاظ منطقی هم هیچ ایرادی نداره و کارش رو به درستی انجام میده. ما میتونیم از یک StopWatch استفاده کنیم تا بتونیم مدت زمانی که طول میکشه تا برنامه اجرا بشه رو اندازه بگیریم.

public static Main(string[] args) { var watch = System.Diagnostic.StopWatch.StartNew(); for(int i=0;i<=1000;i++) if( IsPrimeNumber(i)) Console.Write(i+&quot is prime&quot); console.writeline(watch.elapsedMilisecs + &quot miliseconds&quot); }

وقتی من برنامه رو اجرا کردم این نتیجه رو دیدم:

برنامه کمتر از ۱ میلی ثانیه طول میکشه تا اجرا بشه و اینطوری نمیشه دقیق اندازه بگیریم برای همین بجای اعداد زیر ۱۰۰۰ ما دنبال اعداد زیر ۱۰۰۰۰۰۰ (یک میلیون) می‌گردیم و بجای نشون دادن هر عدد در کنسول، تعداد اعداد اول رو مینویسیم. صرفا جهت اطلاع تعداد اعداد اول بین ۰ و یک میلیون ۷۸۴۹۸تا هست (از گوگل یا چت جی‌پی‌تی پرسیدم). بعد از تغییر این نتیجه رو میبینیم:

زمان ۱۰۲ ثانیه
زمان ۱۰۲ ثانیه

میبینیم که اجرای برنامه حدود ۱۰۲ ثانیه طول کشید. خوب حالا ما میتونیم برنامه رو بهینه تر کنیم. چطور؟ طبق نظریه‌ اعداد ما لازم نیست از ۲ تا خود عدد رو چک کنیم، میتونیم از ۲ تا نصف عدد رو چک کنیم. یعنی در تابع IsPrimeمون اینطوری تغییر میدیم:

var to = x/2;//instead of var to = x;

و بعد از اجرا میبینیم که:

زمان ۴۷ ثانیه
زمان ۴۷ ثانیه

برنامه در عرض حدودا ۴۷ ثانیه اجرا شد. یعنی الگوریتم رو بهینه تر کردیم و باعث شد یک خط کدمون رو تغییر بدیم و سرعت دو برابر شد. به نظر منطقی هم میاد چون تعداد چکهامون نصف شد. حتی میتونیم الگوریتم رو بهینه تر هم بکنیم. بازم طبق نظریه اعداد میشه بجای نصف از جذر عدد هم استفاده کرد یعنی:

var to = (int)Math.Sqrt(x);// instead of var to = x/2;

و بعد از اجرا:

سرعت اجرا ۲۰۸ میلی ثانیه
سرعت اجرا ۲۰۸ میلی ثانیه

در این حالت زمان اجرای برنامه به ۲۰۸ میلی‌ثانیه کاهش پیدا میکنه. اگر دقت کنید حدودا سرعت برنامه‌ی ما ۵۰۰ برابر شد! همینطوری که میبینیم هر قدر الگوریتم رو بهینه تر کنیم طبیعتا سرعت بالاتر میره و البته بهینه کردن الگوریتم مستلزم دانش بیشتر هست، مثلا توی اینجا ما با دانش نظریه‌ی‌اعداد تونستیم الگوریتم رو بهینه کنیم.

این مثال رو زدم که بگم انتخاب الگوریتم، میتونه هم‌اندازه‌ی خود زبان برنامه‌نویسی مهم باشه. به زبان خودمونی: الگوریتم درست رو بردارد.

استفاده از ابزار (الگوریتم) مناسب
استفاده از ابزار (الگوریتم) مناسب


استفاده‌ی کامل از منابع سخت‌افزاری

امروزه سخت افزارها نسبت به قبلا، پیچیده تر شدن. و برای حداکثر استفاده از اونها باید کمی با جزییاتشون اشنا بود. مهمترینش به نظرم استفاده از پردازش چند هسته ای هست. یک پردازنده جدید مثل اینتل 12700 دارای ۸ هسته قوی هست. اگر برنامه مستقیما از قابلیت پردازش چند هسته ای استفاده نکنه معنی اش این هست که فقط روی یک هسته اجرا میشه و این یعنی در بهترین حالت از یک هشتم توان پردازشگر استفاده میشه. مورد دیگه استفاده از پردازش واحد گرافیک GPU هست. واحد GPU تعداد هسته های خیلی بیشتر از CPU داره و برای بعضی مسایل بهتر عمل میکنه ولی پیچیده تره و پیچیدگی برنامه رو هم زیاد میکنه. موارد دیگه ای هست که کمتر روی بورسهُ مثل استفاده از قابلیت SIMD پردازشگر ...

معماری CPU و GPU
معماری CPU و GPU


برگردیم به همون مثال اعداد اول که توش میخواستیم تعداد اعداد اول زیر ۱م (بخوانید یک میلیون) رو بفهمیم. اگر یادتون باشه با یک الگوریتم ساده اولیه شروع کردیم و هی الگوریتم رو بهینه کردیم و سرعتمون افزایش پیدا کرد. حالا میخوایم از قابلیت مالتی‌کور پردازنده هم استفاده کنیم. پس باید کدمون رو یک سری تغییرات بدیم و در نهایت این شکلی میشه:

static void Main(string[] args) { var cnt = 0; var max = 1000000; var sp = System.Diagnostics.Stopwatch.StartNew(); var opt = new ParallelOptions() { MaxDegreeOfParallelism = 8 }; Parallel.For(2, max, opt, i => { if (IsPrimeNumber(i)) cnt++; } ); sp.Stop(); Console.WriteLine(&quot{0} number found in {1} ms&quot, cnt, sp.ElapsedMilliseconds); } static bool IsPrimeNumber(int n) { var m = (int)Math.Sqrt(n) ; for (var i = 2; i <= m; i++) if (n % i == 0) return false; return true; }

و بعد از اجرای برنامه:

اجرا با الگوریتم بهینه‌شده‌ی چند‌هسته‌ای
اجرا با الگوریتم بهینه‌شده‌ی چند‌هسته‌ای


همینطور که میبینید سرعت اجرا‌ی برنامه بازهم بالاتر رفت و زمان اجرا به ۱۱۷ میلی‌ثانیه رسید و سرعت نسبت قبل ۲ برابر شد. خیلی مهمه دقت کنید پردازنده ی من بین ۶ تا ۸ هسته داره (دقیق نمیدونم)ولی وقتی از مالتی‌کور استفاده میکنم الزاما سرعتم۶ تا ۸ برابر نمیشه بلکه اینجا ۲ برابر شده/


استفاده از فنون شناخته‌شده در کد نویسی

۳- فنون شناخته شده کد نویسی: جالبه بدونید خود کدنویسی و فنون کد نویسی هم تاثیر گذاره. فنونی مانند بازکردن حلقه (Loop unrolling)، کد نویسی بصورت Cache Friendly به نحوی که از حافظه cache پردازنده استفاده بیشتری بشه یک سری مسایل دیگه وابسته به هر زبان.



با این کار اصطلاحا حلقه‌ی loopمون رو unroll (یا باز) کردیم. و با این کار هم تعداد مقایسه هامون رو کم کردیم چون هر بار اجرای حلقه یک بار باید مقایسه انجام بشه. و هم اینکه از حافظه کَش پردازنده استفاده بهینه کردیم یا اصطلاحا کدمون Cache Friendly هست. این بحثش کمی طولانیه که میتونید در موردش سرچ کنید.

با یک مثال ادامه میدیم. این مثال از کتاب What Every programmer should know about memory برداشته شده. فرض کنید که میخوایم یک برنامه بنویسیم که دو ماتریس مربعی A و B (هردو با ابعاد ۱۰۰۰ در ۱۰۰۰) رو در هم ضرب کنه. برای کسایی که ریاضی یادشون رفته: درایه‌ی سطر iام و ستون jام ماتریسِ حاصلضرب، برابر هست با ضرب داخلی سطر iام ماتریس A و ستون jام ماتریس B. میشه کدش رو اینطوری نوشت:

for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) res[i][j] += mul1[i][k] * mul2[k][j];

توی این کد ماتریسهای mul1 و mul2 ماتریسهای ورودی‌مون هستن و فرض کردیم که ماتریس حاصلظربمون که اسمش res هست با درایه‌های صفر پر شده. ما میتونیم یک ماتریس بنام tmp درست کنیم برای خودمون و ترانهاده‌ی ماتریس mul2 رو داخلش بریزیم و اون وقت کدمون به این تبدیل میشه:

double tmp[N][N]; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) tmp[i][j] = mul2[j][i]; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) res[i][j] += mul1[i][k] * tmp[j][k];

کاری که ما کردیم بجای اینکه ستون jام ماتریس mul2 رو استفاده کنیم، سطر jام ترانهاده ی mul2 رو استفاده کردیم. از لحاظ منطقی جفتش یک نتیجه داره و نتیجه اش حاصلضرب دو ماتریس ورودیه. ولی وقتی سرعتهای این دو کد رو مقایسه میکنیم می‌بینیم که کد دوم چهار برابر سرعت بیشتری داره! دلیلش اینه که روش دوم Cache Friendly تر از روش اول هست. برای دیدم جزییات کامل این قسمت میتونید به کتاب What Every programmer should know about memory قسمت 6.2.1 صفحه ی ۴۹ مراجعه کنید (روی لینک کلیک کنید).

بعنوان یک جمع بندی، اگر یادتون باشه ما یک مثال رو بررسی کردیم که مثال اعداد اول بود. توی اون مثال با بهینه کردن الگوریتم‌مون، اول تونستیم سرعت برنامه رو ۵۰۰ برابر کنیم و با استفاده از قابلیت چند هسته ای هم سرعت رو دوبرابر کردیم و در مجموع سرعت برنامه چیزی در حدود ۱۰۰۰ برابر شد. خوب طبیعیه ما اینجا یک مثال خیلی فاحش رو بررسی کردیم، ولی باور کنید توی دنیای واقعی ممکنه به مورد مشابهی برخورد کنید. منظورم موردیه که با تغییر یک خط کد سرعت برنامه ۲۰٪ افزایش پیدا کنه! خودم به این مورد برخورد کردم تابحال.

برنامه ی المان محدود و جمع بندی

بیایید در ادامه یک برنامه ی تحلیل المان محدود خطی رو فرض کنیم. روند اجرای ایران برنامه به ۳ مرحله تقسیم میشه:

۱- پیش پردازش: مانند تشکیل ماتریس سختی، مش بندی و اعمال قیود بروی ماتریس سختی

۲- پردازش اصلی: حل دستگاه معادلات بدست امده از مرحله ۱

۳- پس پردازش: تعیین نیروی داخلی اجزا و تفسیر انها


بسته به پیچیدگی مدل معمولا قسمت بزرگتر محاسبات در مرحله ی دوم یعنی پردازش اصلی هست. یعنی حل دستگاه معادلات خطی. بسته به مدل، باقی مراحل شاید ۱۰ درصد زمان تحلیل رو می‌گیرند. یعنی ۹۰٪ زمان صرف صرف پردازش اصلی و ۱۰٪ زمان صرف پیش‌پردازش و پس‌پردازش میشه.

به تفاوت مقدار محاسبات دقت کنید، یعنی تاثیر ۵٪ بهبودِ سرعت توی قسمت پردازش اصلی برابر ۵۰ درصد بهبودِ سرعت در دو قسمت دیگه هست. چون قسمت پردازش اصلی خیلی زمانگیر هست و همونطور که گفتیم مساله ی شناخته شده ای هم هست، میشه برای این قسمت، از زبانهای سطح پایین تر مانند C و فرترن استفاده کرد. بعلاوه اینکه بسته‌های نرم‌افزاریِ آماده و پرقدرتی مانند Intel MKL هم وجود دارند که میشه از اونها استفاده کرد. برنامه ای مثل MKL یا CSparse یا eigen بهینه هستند و از الگوریتمهای بهینه استفاده کردند و در نتیجه بعنوان بهینه ترین راه حل ها در نظر گرفته میشن. یعنی میشه مراحل پس پردازش و پیش پردازش رو با زبانهای سطح بالاتری مثل #C یا جاوا نوشت که در این صورت از سادگی کد استفاده میکنیم چون کدمون به زبان آدمیزاد نزدیکتره. و قیمت پردازش اصلی رو با زبان سطح پایین تر مثل C مینویسیم یا از بسته های مثل MKL استفاده میکنیم. اینطوری از ابزار مناسب برای کار مناسب استفاده میشه. یعنی قدرت زبان سطح پایین تر در کنار سادگی زبان سطح بالاتر.

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

گره ای که با دست باز میشه رو با دندون باز نمیکنن
اجزا محدودالگوریتمزبان برنامه نویسبرنامه نویسیزبان برنامه‌نویسی
ذره‌ای کوچک در هستی
شاید از این پست‌ها خوشتان بیاید