نگهداری درخت دودویی متوازن IPR در یک محیط پردازش موازی با حافظه اشتراکی

سال انتشار: 1386
محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران
کد COI اختصاصی: ACCSI13_117
زبان مقاله: فارسی
تعداد مشاهده: 2635

نویسندگان

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

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

چکیده

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

کلیدواژه ها

درخت،IPR درخت جستجوی متوازن، رایانش ، موازی، عملیات لغتنامه ایPRAM

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.