سال انتشار: ۱۳۸۶

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۱۰

نویسنده(ها):

سیدآرش استادزاده – گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی دانشگاه آزاد اسلامی واحد مشهد
سیدشروین استادزاده – گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی واحد علوم و تحقیقات دانشگ

چکیده:

درخت جستجوی دودویی به عنوان یکی از پرکاربردترین ساختارهای نگهداری داده مطرح است. این ساختمان داده کارامد، دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات می باشد و به عنوان یک شاخص استاندارد، جهت پیاده سازی عملیات لغتنامه ای مورد استفاده قرار می گیرد. روشهای متفاوتی جهت متوازن سازی این نوع درخت پیشنهاد شده است، ولی در این بین، روش کاهش طول مسیر داخلی یا درخت،IPR متوازن ترین شکل درخت جستجویدودویی را ایجاد می کند. ما در اینجا، الگوریتم هایی برای انجام عملیات موازی جستجو و درجk کلید به صورت همزمان، در درخت ،IPR ارائهداده ایم که جهت پیاده سازی در یک محیط پردازش موازی با حافظه اشتراکی، مناسب است. برای بررسی میزان کارایی و تعیین مرتبه زمانی الگوریتم ها از مدل محاسباتی موازیEREW PRAM استفاده شده ،است. نتایج بیانگر آن است که عملیات مذکور با هزینه بهینه، و به کارگیریk پردازشگر در زمان O(log k+log n) قابل اجرا است، که nتعداد گره های موجود را در درخت ،IPRمشخص می کند . جهتجلوگیری از تداخل و دسترسی همزمان به حافظه اشتراکی، PRAMیک روش زمانبندی عملی پردازشگرها، پیشنهاد کرده ایم، کهاحتیاج به حافظه اضافی ندارد و در مرتبه زمانی الگوریتم ها، نیز بی تاثیر است.