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

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

تعداد صفحات: ۵

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

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

چکیده:

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