ارائه يك معماري جديد قابل بازپيكربندي براي پياده سازي الگوريتم هاي مرتب سازي با استفاده از مدارهاي مجتمع قابل برنامه ريزي

كارشناسي ارشد

مرتب سازي روش پردازش داده مرسومي است كه در بسياري از كاربردها استفاده مي شود. پياده سازي شتاب دهنده سخت افزاري براي تسريع مرتب سازي داده هاي بزرگ و استفاده از تمام پهناي باند حافظه اصلي، موضوعي است كه اخيراً مورد علاقه بسياري از محققان قرار گرفته است. مرتب سازهاي سخت افزاري موازي به منظور افزايش كارايي ارائه شده اند كه پياده سازي آنها در مدارهاي مجتمع با كاربرد خاص و مدارهاي مجتمع قابل برنامه ريزي ترجيح داده مي شود. شبكه مرتب ساز ادغامي بايتونيك يكي از بهترين الگوريتم هاي مرتب سازي موازي بر پايه ادغام است. منابع سخت افزاري مورد نياز اين شبكه مرتب ساز به واحد هاي مقايسه و مبادله(CAS) وابسته است. با افزايش تعداد ركوردهاي ورودي به شبكه مرتب ساز، تعداد واحدهاي CAS افزايش يافته و منابع مورد نياز افزايش و فركانس كاري كاهش مي يابد. در سيستم هاي بلادرنگ ثابت بودن زمان اجرا ترجيح داده مي شود و زمانبند بايد بدترين زمان اجراي مرتب سازي را بداند. در اين پايان نامه، قصد معرفي روش ابتكاري براي مرتب سازي ركوردهاي ورودي به صورت جزئي را داريم كه با افزايش ركوردهاي ورودي به ارائه زمان اجرا ثابت نزديك شويم. نتايج نشان داده اند كه تعداد جداول جستجو روش ارائه شده نسبت به مرتب ساز بايتونيك متداول 70.2 درصد و نسبت به جديدترين معماري مرتب ساز 87.3 درصد كاهش يافته است. همچنين تعداد ثبات مورد نياز روش ارائه شده نسبت به جديدترين معماري مرتب-ساز 94.8 درصد كاهش يافته است.

192395

دانشگاه علم و صنعت ايران

معماري سيستم هاي كامپيوتري

دكتر حاكم بيت الهي