نگهداري درخت دودويي متوازن IPR در يك محيط پردازش موازي با حافظه اشتراكي  Fulltext 

[ سيدآرش استادزاده ] - گروه مهندسي كامپيوتر، دانشكده فني و مهندسي دانشگاه آزاد اسلامي مشهد مشهد، ايران
[ سيدشروين استادزاده ] - گروه مهندسي كامپيوتر، دانشكده فني و مهندسي واحد علوم و تحقيقات دانشگاه آزاد اسلامي تهران، ايران

خلاصه مقاله:

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

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