مقاله طراحی الگوریتم های موازی برای عملیات عدد صحیح ابر بلند مبتنی بر CPU های چند هسته ای
چکیده
در کاربردهای رمزنگاری، عمل های عدد صحیح ابر بلند اغلب مورد استفاده قرار می گیرد. اگرچه، الگوریتم های رمزنگاری بصورت کلی روی یک کامپیوتر با یک CPU تک هسته بکار برده می شود، و پردازش کامپیوتر مرتبط با آن یک نمونه از اجرای توالی می باشد. در این مقاله، طرز موازی کردن عمل های اعداد صحیح ابر بلند در محیط کامپیوتر چند هسته بیان می شود . اهمیت این مطالعه همجهت با پیشرفت دستگاههای محاسباتی چند هسته ای، و بهبود قابلیت محاسباتی چند هسته ای صورت می گیرد، نیاز به ایجاد محاسبات پایه ای از اعداد صحیح ابر بلند قابل اجرا بصورت موازی است، که مفهوم آن به ترتیب بلوک شدن اعداد صحیح ابر بلند، اجرای تمام داده های بلوک شده روی رشته های چند هسته، تبدیل اجرای توالی اصلی داخل محاسبات موازی چند هسته، و ذخیره ی نتایج چند رشته ای بعد از فرمت کردن آنها می باشد. مطابق با آزمایش های صورت گرفته مشاهده شده است که: در صورتی که زمان رشته ی برنامه ریزی بیشتر از محاسبات باشد، الگوریتم های موازی سریعتر عمل می نمایند; برخلاف این، الگوریتم های توالی بهتر هستند.بصورت کلی اینکه، الگوریتم های موازی توانایی محاسبات سخت افزاری چند هسته ای با کارایی بیشتر دارند.
I. مقدمه
در سیستم های رمزنگاری کلیدی عمومی]1[ و طرح واره های امضایی دیجیتالی، برای مثال، RSA[3]، ECC[4]،و REESSE1+[5,6]،حساب رسی اعداد صحیح ابر بلند نیاز اساسی می باشد. تعریف ثابتی از اعداد صحیح ابر بلند موجود نیست. بصورت کلی، اعداد صحیح ابر بلند همان عداد صحیح های هستند که طول آنها بزرگتر از 64 بیت می باشد، یا محدوده ی آنها بیشتر از کامپایلر زبان برنامه نویسی می باشد. عمل های اصلی شرح داده شده در این مقاله شامل جمع کردن، تفریق کردن، ضرب کردن، تقسیم کردن، و تبدیل سیستم های عددی می باشد. تمرکز روی تقسیم و ضرب می باشد، برای تفریق و تقسیم بوسیله ی اضافه کردن، ضرب کردن و شیف دادن]7[ می تواند صورت بگیرد. در انتهای این مقاله، به معرفی تبدیل یک سیستم عددی بصورت خلاصه پرداخته می شود. درک محاسبات موازی با استفاده از توانمندی کامپیوترهای چند هسته امکان پذیر می باشد، تجزیه ی پردازش حساب رسی اعداد صحیح ابر بلندی کنونی، و خود تجزیه از اعداد با فاصله ی یکسان بصورت بیت ها یا بصورت بخش بندی شده استفاده می نماید، همچنین از مکانیزم های چند رشته ای بهره می برد]8[، داده تجزیه شده به رشته ی متناظر تخصیص داده می شود، زمان اجرایی عمل های متوالی کاهش می یابد، بنابراین با این وضعیت استفاده کامل از توانایی پردازش چند هسته ای امکان پذیر می باشد. الگوریتم ما مناسب برای هر طول قابل محاسبه ی اعداد صحیح ابر بلند می باشد، و هیچ محدودیتی در حداقل طول ندارد. ( بخاطر زبان برنامه نویسی، نیاز به این است که حداکثر طول خروجی محدود شود، حداکثر بیت بکاررفته در حال حاضر 1500 می باشد.) در ادامه مفهوم نمادها در این الگوریتم ها نشان داده می شود.
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.
I. INTRODUCTION
In public key cryptosystems [1] and digital signature schemes [2], for example, RSA [3], ECC [4], and REESSE1+ [5, 6], super long integers arithmetic is a basic requirement. There is not a uniform definition of super long integers. In general, super long integers are those integers whose lengths are larger than 64 bits, or scopes exceed what is allowed by a programming language compiler. The basic operations discussed in this paper include addition, subtraction, multiplication, division, and conversion of number systems. We focus on addition and multiplication, for subtraction and division can be implemented by addition, multiplication and shift [7]. At the end of this paper, we will introduce conversion of number systems briefly. The realization of parallel computing uses the ability of multi-core computers, decomposes the existing super long integers arithmetic process, and the decomposition uses segmented or fixed interval number of bits, uses multithread mechanism [8], allocates the decomposed data to corresponding thread, reduces the running time of serial operations, so that make full use of multi-core processing ability. Our algorithms are applicable to any length of super long integers arithmetic, and have no minimum length limit. (Because of the programming language, we need to limit the maximum output length, the maximum bit we tested now is 1500.) The following shows the meaning of symbols in these algorithms.
چکیده
مقدمه
معرفی اعداد صحیح ابر بلند
نمونه ها
ذخیره ی داده و معرفی آن
طراحی الگوریتم های موازی
شرح الگوریتم موازی اضافی
شرح الگوریتم موازی تفریقی
شرح الگوریتم موازی ضربی
شرح الگوریتم موازی تقسیم
مثال ها
انتخاب رادیکس
جزء حل کردنی
برنامه موازی
مثالهای مربوط به محاسبه ی موازی اضافه
مثال هایی از محاسبات موازی ضربی
آنالیز نتیجه
نتیجه گیری
Abstract
INTRODUCTION
REPRESENTATION OF SUPER LONG INTEGERS
Samples
Data Storage and Representation
DESIGN OF PARALLEL ALGORITHMS
Description of Addition Parallel Algorithm
Description of Subtraction Parallel Algorithm
Description of Division Parallel Algorithm
EXAMPLES
Choose Radix
Resolve Particle
Parallel Program
Examples of Addition Parallel Computing
Examples of Multiplication Parallel Computing
EFFICIENCY ANALYSIS
Experimental Data
Result Analysis
CONCLUSIONS
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه