بخشی از مقاله
نگهداری درخت دودویی متوازن IPR در یک محیط پردازش موازی با حافظه اشتراکی
چکیده: درخت جستجوی دودویی به عنوان یکی از پرکاربردترین ساختارهای نگهداری داده مطرح است. این ساختمان داده کارامد، دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات میباشد و به عنوان یک شاخص استاندارد، جهت پیاده سازی عملیات لغتنامه ای مورد استفاده قرار می گیرد. روشهای متفاوتی جهت متوازنسازی این نوع درخت پیشنهاد شده است، ولی در این بین، روش کاهش طول مسیر داخلی یا درخت IPR ، متوازن ترین شکل درخت جستجوی دودویی را ایجاد می کند. ما در اینجا، الگوریتمهایی برای انجام عملیات موازی جستجو و درج k کلید به صورت همزمان، در درخت IPR، ارائه داده ایم که جهت پیاده سازی در یک محیط پردازش موازی با حافظه اشتراکی، مناسب است. برای بررسی میزان کارایی و تعیین مرتبه زمانی الگوریتمها از مدل محاسباتی موازی EREW PRAM ، استفاده شده است. نتایج بیانگر آن است که عملیات مذکور با هزینه بهینه، و بهکارگیری k پردازشگر در زمان O(log k+log n) قابل اجرا است، که n تعداد گره های موجود را در درخت IPR، مشخص میکند. جهت جلوگیری از تداخل و دسترسی همزمان به حافظه اشتراکی PRAM ، یک روش زمانبندی عملی پردازشگرها، پیشنهاد کردهایم، که احتیاج به حافظه اضافی ندارد و در مرتبه زمانی الگوریتمها، نیز بیتاثیر است.
واﮊه های کلیدی: درخت IPR، درخت جستجوی متوازن، رایانش موازی، عملیات لغتنامهای، .PRAM
۱- مقدمه
درخت های IPR١ یکی از انواع درختهای متوازن از نظر ارتفاع هستند که برای اولین بار توسط [1] Gonnet معرفی شدند. این درخت ها نیز همانند درختهای معروف [2] AVL که پیشتر ارائه شدند، درختهای جستجوی دودویی هستند که به صورت محلی متوازن گردیدهاند، بدین معنی که اختلاف ارتفاع زیردرخت های چپ و راست برای هر نود حداکثر مقدار یک خواهد بود. با اینکه در تحقیقات انجام گرفته [3,4]، درخت های AVL به عنوان یکی از موثرترین و کارامدترین ساختارهای متوازن سازی درختهای جستجوی دودویی مطرح شدهاند، این بدان معنا نیست که ساختار به نسبت مناسب این درخت ها غیر قابل بهبود است. در حقیقت، هدف از بازسازی درختهای جستجوی دودویی و به تبع انجام تبدیلات و چرخشهایی بدین منظور، تنها کاهش میانگین زمان لازم جهت بازیابی یک کلید در درخت است. این هدف با کاهش میانگین عمق یک گره در درخت به صورت بهینه محقق می شود. درختهای متوازن از نظر ارتفاع دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات هستند. آنها به عنوان شاخصهای استاندارد در سیستمهای بانکهای اطلاعاتی، سیستمهای عامل و کامپایلرها به خدمت گرفته میشوند .[5]
ارتفاع درخت IPR، O(log n) است و بنابراین عملیات لغتنامهای٢ یعنی جستجو، درج و حذف با زمان O( log n) در مدل محاسباتی سری، قابل انجام خواهد بود، که n تعداد کلیدها در درخت است. درخت های متوازن مشهور دیگری نیز مانند AVL ، درخت ۳-۲ و درخت قرمز- سیاه [6] در این مورد عملکردی مشابه درخت IPR دارند. نوع کارامدتر درخت های متوازن که به صورت خا ص جهت مدیریت تعداد زیادی کلید در حافظه جانبی، کاربرد دارند، با عنوان [7] B-tree و مشتقات آن شناخته می شوند، که در دسته درختان کاملاﹰ متوازن قرار میگیرند. ارتفاع B-tree برابر O(logB n) است که در آن n تعداد کلیدها و B پارامتری است که درجه درخت را مشخص میکند. عملیات لغتنامهای در زمان O(B logB n) بر روی این درختها قابل انجام است.
تحقیقات گسترده ای در زمینه انجام عملیات دسترسی و به روز رسانی درختهای جستجوی متوازن، به شکل موازی انجام گرفته است. [8] Ellis انجام عملیات موازی جستجو و درج را بر روی درختهای AVL با به کارگیری مکانیزمی جهت قفل کردن گره ها، پیشنهاد داد. Kung و [9] Lehman با افزودن پیوندهای اضافی به گرهها، انجام عملیات لغتنامهای را مورد بررسی قرار دادند. کار آنها توسط Manber و [10] Ladner بهبود یافت. تمام الگوریتمهای مذکور جهت انجام p عمل موازی بر روی درخت با وجود p پردازشگر در بدترین حالت دارای مرتبه زمانی O(p+log n) بودند که عدم بهینه شدن هزینه اجرای عملیات را در پی داشت، مگر در شرایطی که تعداد عملیات محدود و رشد آن در برابر log n قابل چشمپوشی باشد.
Medidi و [11] Deo با به کار گیری الگوریتمی جهت زمانبندی پردازشگرها، برای حل مساله دسترسی همزمان و معرفی چرخشها و تبدیلات جدید، تمامی عملیات لغتنامهای درخت AVL را در زمان بهینه O(log n+log p) بر روی مدل EREW PRAM به انجام رساندند. برای ساختن موازی درخت ۳-۲ با هزینه بهینه میتوان به کار Wang و Chen اشاره کرد .[12]
Paul و همکارانش [13] الگوریتمهایی برای انجام عملیات موازی لغتنامهای بر روی درختهای ۳-۲ با به کار گیری تکنیک خط لوله٣ در مرتبه زمانی بهینه O(log p+log n) روی مدل EREW PRAM پیشنهاد دادند. به طور مشابه، الگوریتمهای بهینهای نیز برای درخت قرمز- سیاه وجود دارد .[14]
B-tree به دلیل ویژگیهای منحصر بفرد، همواره مورد توجه محققین بوده است. الگوریتمهای موازی زیادی جهت ساختن و انجام عملیات لغتنامه ای بر روی این درختها پیشنهاد شده است. Wang و همکارانش [15] ساختن موازی آن را مورد بررسی قرار دادهاند. Higham و [16] Schenk برای انجام p عمل موازی جستجو زمان
، برای انجام p عمل درج، زمان و برای p عمل حذف زمان را بر روی مدل EREW PRAM با p پردازشگر، بدست آوردند. در کل به علت عمومیت B-tree عملیات لغتنامهای به اندازه پارامتر B/log B کندتر نسبت به درختهای AVL، ۳-۲ و قرمز- سیاه، انجام میگیرد. در نتیجه الگوریتمهای موازی ارائه شده در [16] بجز الگوریتم حذف بهینه هستند. Park و همکارانش [17] الگوریتم موازی حذف بهینه برای B-tree با مرتبه زمانی O(B(log p+logB n)) ، روی مدل EREW PRAM ارائه دادند.
گرچه برای انواع درخت های متوازن، الگوریتمهای موازی جهت انجام عملیات دسترسی و به روز رسانی وجود دارند، اما درخت IPR کمتر مورد توجه قرار گرفته و تا آنجایی که ما اطلاع داریم، هیچ کار علمی منتشر شده در رابطه با انجام عملیات لغتنامهای بر روی درخت IPR وجود ندارد و پژوهش فعلی سرآغازی در این زمینه است. این درخت شباهتهایی به درخت AVL دارد، لیکن الگوریتمهای ارائه شده، به صورت مستقیم بر روی IPR قابل پیاده سازی نیست. ما در این مقاله، انجام عملیات موازی جستجو و درج k کلید را روی درخت IPR در مدل EREW PRAM بررسی میکنیم. اعمال لغتنامهای مذکور در مرتبه زمانی بهینه O(log k+log n) با k پردازشگر قابل پیادهسازی است. n تعداد گرههای موجود در درخت است. با توجه به اینکه عملیات جستجو و درج، تابع ارتفاع درخت هستند و با زمان O(log n) در مدل محاسباتی سری، انجام می گیرند، انجام k عمل در این مدل با هزینه O( k log n) قابل پیادهسازی است، که این با هزینه اجرای عملیات در الگوریتمهای موازی پیشنهادی ما برابری دارد و تاییدی بر بهینه بودن مرتبه زمانی الگوریتمهای مذکور است. ادامه ساختار این مقاله به صورت زیر است. در بخش ۲ ، تعاریف پایه ای و یک سری ویژگیهای درخت IPR مورد بررسی قرار می گیرد. بخش ۳ به توصیف الگوریتم جستجوی موازی می پردازد. در بخش ۴ ، الگوریتم درج موازی بیان میگردد و در نهایت، بخش ۵ به نتیجهگیری اختصاص دارد.
۲- تعاریف پایهای
در این بخش ابتدا به بیان ویژگیهای درخت IPR می پردازیم و سپس تعاریف لازم برای واﮊگان به کار رفته در بخشهای بعدی مقاله و مفروضات مورد نیاز، ذکر میگردد.
۲-۱- ویژگیهای درخت IPR
درخت IPR، یک درخت جستجوی دودویی است، که در آن ارتفاع زیردرخت های چپ و راست هر گره تقریباﹰ یکسان نگه داشته می شود. این عمل با دستکاری طول مسیر داخلی٤ برای زیر درخت ها، انجام می گیرد. کارایی و عملکرد درخت IPR در اکثر مواقع از درخت AVL بهتر است و در هیچ شرایطی بدتر از آن عمل نمی کند .[1] جدول ۱ نشان می دهد که ارتفاع یک درخت IPR هیچگاه بیشتر از درخت AVL متناظر آن نیست، اما طول مسیر داخلی (که بهترین معیار سنجش توازن درخت است) در بدترین حالت برای یک درخت IPR، ده درصد بهتر از درخت AVL متناظر آن است.
درخت های IPR همانند تمام درختهای جستجوی دودویی، هنگامی که تعداد گره ها خیلی زیاد باشند، کارایی قابل قبولی ندارند. همانطور که در جدول ۱ دیده می شود، در بدترین حالت تعداد جستجوها جهت دستیابی به یک گره، ضریبی از log n است، که n نشان دهنده تعداد گره ها در درخت است B-tree .[1] جایگزین مناسبی برای این مواقع است.
معیاری که در درخت IPR جهت آزمون توازن درخت استفاده می شود، از پارامتر ضریب توازن در درخت AVL ، مفهوم تر است. با این حال یک عیب درخت IPR آن است که بعد از درج یک گره جدید در درخت، ممکن است به منظور ایجاد توازن، بیش از یک تبدیل نیاز باشد. عمل تبدیل در درخت، در هر زمان که امکان کاهش طول مسیر داخلی میسر باشد، انجام می گیرد. در درخت IPR نیز همانند درخت AVL چهار قالب کلی تبدیل وجود دارد .[1] تفاوت عمده ساختن درخت IPR نسبت به AVL این است که در IPR تعداد گره ها در زیر درخت مورد توجه قرار می گیرد، در صورتیکه در AVL ، اندازه ارتفاع زیر درخت مد نظر است. شکل ۱ مقایسه درختهای IPR و AVL را با دادههای یکسان نشان میدهد. برای اطلاع از جزییات ساختن درخت های مذکور به [1,2] مراجعه کنید. در ادامه این مقاله فرض بر این است که خواننده با نحوه ساختن درخت IPR آشنایی دارد.
علاوه بر مزایای ذکر شده در درخت IPR ، ویژگی انعطاف پذیری نیز برای این درخت قابل بررسی است. امکان تنظیم درجه توازن به دلخواه توسط کاربر، وجود دارد. چارچوب کلی آزمون توازن درخت، امکان توسعه آن را جهت تعریف درختهای متوازن با ضریب توازن k، در اختیار ما قرار می دهد٥. می توان شروط انجام تبدیلات در درخت را به شکل کلی nc-na > k-1 و nb-na > k-1 بیان کرد، که در آن هر چه مقدار k بیشتر باشد، درجه توازن درخت کمتر است، اما عملیات تبدیل کمتری نیز انجام خواهد شد. na ، nb و nc نشاندهنده تعداد گرهها در زیر درختهای یک گره مورد آزمایش جهت کم کردن طول مسیر داخلی درخت، است. در درخت IPR مقدار k برابر یک است، بنابراین درختهای IPR یکی از انواع درختهای HB(1) هستند.
امکان تنظیم شروط انجام تبدیل، بر اساس بزرگی درخت نیز وجود دارد. به عنوان مثال در یک درخت با هزاران گره، کاهش طول مسیر داخلی به اندازه یک واحد، ارزش هزینه و زمان لازم را برای انجام عملیات تبدیل، ندارد. در نتیجه می توان شروط انجام عملیات تبدیل را به صورت زیر تغییر داد:
۲-۲- مجموعه واﮊگان و مفروضات
ما در این مقاله، مقدار کلید ذخیره شده در هر گره v از درخت IPR را با key(v) و آدرس فرزندان سمت چپ و راست یک گره را به ترتیب با left(v) و right(v) نشان میدهیم. گرچه هر عنصر قرار گرفته در درخت (گره ها) می تواند نشاندهنده یک رکورد باشد، با این حال بدون مخدوش شدن کلیت موضوع، ما در اینجا از یک کلید به عنوان جایگزینی برای یک عنصر استفاده میکنیم.
فرض کنید یک درخت IPR، T با n گره و آرایه keys از کلیدهای keyi , 1≤ i ≤ k در حافظه مشترک PRAM قرار دارند. keyi ها ممکن است جز داده های درخت باشند، یا در درخت موجود نباشند. فرض کنید که پردازشگرهای pi , 1≤ i ≤k از مکان داده keyi در آرایه keys اطلاع دارند. با استفاده از الگوریتم مرتب سازی موازی میتوان دادههای keyi , 1≤ i ≤ k را در زمان O(log k) روی مدل EREW PRAM با k پردازشگر مرتب کرد .[18] در صورت وجود کلیدهای تکراری در آرایه keys ، نیز میتوان با الگوریتم مشابه در مرتبه زمانی O(log k) آنها را از مجموعه حذف کرد. علاوه بر داده های فوق، مقدار IPRroot که آدرس ریشه درخت IPR را دارا است، در حافظه مشترک PRAM ذخیره شده است.
ما عملیات لغتنامهای جستجو و درج همزمان کلیدهای آرایه keys را در زمان بهینه O( log k+log n) روی مدلEREW PRAM به انجام میرسانیم. k برابر تعداد کلیدهای آرایه keys و تعداد پردازشگرهای ماشین موازی و n نشاندهنده تعداد گرههای درخت IPR است.
۳- الگوریتم جستجوی موازی
جستجوی موازی کلیدها در درخت بر روی مدلی از PRAM که امکان خواندن همزمان گره ها را فراهم میکند((CR، بسیار ساده است و در زمان O(log n) قابل پیادهسازی است. کافیست هر پردازشگر از ریشه شروع و مسیر مناسب را تا رسیدن به کلید مورد نظر ادامه دهد، که در بدترین حالت تعداد اعمال خواندن به ارتقاع درخت محدود میشود. اما با توجه به اینکه خواندن همزمان روی مدل ER مجاز نیست باید از الگوریتم دیگری برای پیش بردن پردازشگرها به سمت کلیدهای مورد نظرشان و شبیهسازی خواندن همزمان، استفاده کرد.
تکنیک خواندن زنجیره ای مشابه روش Paul و همکارانش [13] و Medidi و [11] Deo می تواند در مورد درخت IPR نیز بررسی شود. روش مطرح شده در [11] برای جستجوی موازی روی درخت AVL ، تنها برای حالت خاصی که درخت AVL خارجی٦ داشته باشیم، قابل پیاده سازی است. این مهم محدودیتی برای عمومیت درختهای جستجوی معمولی ایجاد می کند. به علاوه در روش پیشنهادی مذکور، هنگامیکه تعدادی از پردازشگرها در یک زنجیره به یک برگ از درخت می رسند (حالتی که برخی از کلیدها در درخت موجود نباشند)، باید توسط یک روش دوبرابرسازی بازگشتی٧ که در زمان O(log k) قابل پیاده سازی
