طراحی الگوریتم های موازی برای عملیات عدد صحیح ابر بلند مبتنی بر CPU های چند هسته ای

Design of Parallel Algorithms for Super Long Integer Operation Based on Multi-core CPUs

مجله آی تریپل ای – IEEE

سال ۲۰۱۵

چکیده

در کاربردهای رمزنگاری، عمل های عدد صحیح ابر بلند اغلب مورد استفاده قرار می گیرد. اگرچه، الگوریتم های رمزنگاری بصورت کلی روی یک کامپیوتر با یک CPU تک هسته بکار برده می شود، و پردازش کامپیوتر مرتبط با آن یک نمونه از اجرای توالی می باشد. در این مقاله، طرز موازی کردن عمل های اعداد صحیح ابر بلند در محیط کامپیوتر چند هسته بیان می شود . اهمیت این مطالعه همجهت با پیشرفت دستگاههای محاسباتی چند هسته ای، و بهبود قابلیت محاسباتی چند هسته ای صورت می گیرد، نیاز به ایجاد محاسبات پایه ای از اعداد صحیح ابر بلند قابل اجرا بصورت موازی است، که مفهوم آن به ترتیب بلوک شدن اعداد صحیح ابر بلند، اجرای تمام داده های بلوک شده روی رشته های چند هسته، تبدیل اجرای توالی اصلی داخل محاسبات موازی چند هسته، و ذخیره ی نتایج چند رشته ای بعد از فرمت کردن آنها می باشد. مطابق با آزمایش های صورت گرفته مشاهده شده است که: در صورتی که زمان رشته ی برنامه ریزی بیشتر از محاسبات باشد، الگوریتم های موازی سریعتر عمل می نمایند; برخلاف این، الگوریتم های توالی بهتر هستند.بصورت کلی اینکه، الگوریتم های موازی توانایی محاسبات سخت افزاری چند هسته ای با کارایی بیشتر دارند.

Abstract

In cryptographic applications, super long integer operations are often used. However, cryptographic algorithms generally run on a computer with a single-core CPU, and the related computing process is a type of serial execution. In this paper, we investigate how to parallelize the operations of super long integers in multi-core computer environment. The significance of this study lies in that along with the promotion of multi-core computing devices, and the enhancement of multi-core computing ability, we need to make the basic arithmetic of super long integers run in paralleling, which means blocking super long integers, running all data blocks on multi-core threads respectively, converting original serial execution into multi-core parallel computation, and storing multi-thread results after formatting them. According to experiments we have observed: if scheduling thread time is longer than computation, parallel algorithms execute faster; on the contrary, serial algorithms are better. On the whole, parallel algorithms can utilize the computing ability of multicore hardware more efficiently.

دانلود رایگان مقاله انگلیسی

خرید ترجمه آماده ورد