بهینه سازی ساخت درخت به روش ماتریس مجاورت با الگوریتم موازی

در سال های اخیر زبان های برنامه نویسی کاربردی به طور فزاینده ای محبوب شده اند. مزیت اصلی آنها سادگی تبدیل یک برنامهمتوالی به صورت موازی است. همان طور که می دانیم مفهوم درخت در زمینه های گوناگون علم ریاضی بیشتر از یک قرن مورداستفاده بوده است و همواره تلاش های بسیاری برای موازی سازی الگوریتم های ترتیبی ساخت انواع درخت ها انجام شده است. دراین مقاله ما ساخت درخت را به روش ماتریس مجاورت با استفاده از زبان برنامه نویسی C++ با الگوریتم ترتیبی پیاده سازی کردیمو میانگین زمان اجرای الگوریتم ترتیبی را به دست آوردیم و سپس با ابزار موازی سازی mpi الگوریتم موازی درخت را پیاده سازیکردیم و میانگین زمان اجرای الگوریتم را با تعداد پردازنده و تعداد گره های متفاوت بدست آوردیم و نتایج زمان اجرای دو الگوریتمترتیبی و موازی را با هم مقایسه کردیم و مشاهده شد که بهترین بهبود در حالت ۴ هسته ای بدست آمده است و با افزایش بارکاری (تعداد گره ها) میزان بهبود هم بیشتر بوده است.

کلیدواژه ها:

ساخت درخت ، ماتریس مجاورت ، الگوریتم ترتیبی ، الگوریتم موازی ، بهینه سازی.