نگهداری درخت دودویی متوازن IPR در یک محیط پردازش موازی با حافظه اشتراکی
Publish place: 13th Annual Conference of Computer Society of Iran
Publish Year: 1386
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 2,488
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI13_117
تاریخ نمایه سازی: 25 آبان 1386
Abstract:
درخت جستجوی دودویی به عنوان یکی از پرکاربردترین ساختارهای نگهداری داده مطرح است. این ساختمان داده کارامد، دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات می باشد و به عنوان یک شاخص استاندارد، جهت پیاده سازی عملیات لغتنامه ای مورد استفاده قرار می گیرد. روشهای متفاوتی جهت متوازن سازی این نوع درخت پیشنهاد شده است، ولی در این بین، روش کاهش طول مسیر داخلی یا درخت،IPR متوازن ترین شکل درخت جستجوی دودویی را ایجاد می کند. ما در اینجا، الگوریتم هایی برای انجام عملیات موازی جستجو و درجk کلید به صورت همزمان، در درخت ،IPR ارائه داده ایم که جهت پیاده سازی در یک محیط پردازش موازی با حافظه اشتراکی، مناسب است. برای بررسی میزان کارایی و تعیین مرتبه زمانی الگوریتم ها از مدل محاسباتی موازیEREW PRAM استفاده شده ، است. نتایج بیانگر آن است که عملیات مذکور با هزینه بهینه، و به کارگیریk پردازشگر در زمان O(log k+log n) قابل اجرا است، که nتعداد گره های موجود را در درخت ،IPRمشخص می کند . جهت جلوگیری از تداخل و دسترسی همزمان به حافظه اشتراکی، PRAM یک روش زمانبندی عملی پردازشگرها، پیشنهاد کرده ایم، که احتیاج به حافظه اضافی ندارد و در مرتبه زمانی الگوریتم ها، نیز بی تاثیر است.
Keywords:
Authors
سیدآرش استادزاده
گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی دانشگاه آزاد اسلامی واحد مشهد
سیدشروین استادزاده
گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی واحد علوم و تحقیقات دانشگ
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :