یک الگوریتم ادغام موازی در کامپیوترهای CRCW SM SIMD با مرتبه اجرایی O(١)

تئوری الگوریتم های موازی در راستای تسریع پردازش داده ها ارائه شده است و همانطور که می دانیم عمل ادغام یکی از عملیات مهم بر روی داده ها است که زمان اجرای آن بر روی یک سیستم تک پردازنده ای برابر روی کامپیوتر هایEREW ارائه شده است که زمان اجرای آن در کامپیوتر های SIMD برابر O(n/N+ log2n) و در کامپیوترهای CREW برابر O(n/N+ logn) می باشد. در این مقاله یک راهکار جدید برای ادغام دو رشته B,A به طولهای m,n بر روی کامپیوتر CRCW با تعداد N*M پردازنده ارائه می شود که عمل ادغام را در زمان O(١( انجام می دهد . سپس الگوریتم ارائه شده را برای حالتی که m>M و n>N باشد ، ،تعمیم می دهیم که در این حالت زمان اجرا برابر O(n/M , m/M) می باشد.

کلیدواژه ها:

ادغام ، SIMD ، CRCW-Merge