چکیده:
معماری سیستولیکی یکی از پرکاربردترین معماری های پردازش موازی به حساب می آید. درآرایه سیستولیکی واحدهای ALU بصورت آرایه کنار هم قرار می گیرند. آرایه سیستولیکی به صورت سنکرون عمل می کند بصورتی که با نگاشت مناسب ورودی ها به آن قادر است محاسبات دارای معادله بازگشتی را بطور موازی انجام دهد. در این مقاله آرایه سیستولیکی برای یکی از الگوریتمهای استفادهشده در نمایش (تجزیه) تنک بنام الگوریتم SL0 طراحی شده و با شبیه سازی نرم افزاری مورد ارزیابی واقع گردید. نتایج حاکی از آن است اجرای الگوریتم مذکور با تک پردازنده با فرض 4 کلاک برای انجام هر بار معادله بازگشتی کلاکی معادل 4N^3+9.7N^2+3.2N+18لازم دارد در حالیکه انجام آن با آرایه سیستولیکی به دلیل انجام محاسبات به صورت موازی و پایپ لاین، کلاکی معادل 48N+32 لازم دارد. در این مقاله آرایه سیستولیکی برای یکی از الگوریتمهای استفادهشده در نمایش (تجزیه) تنک بنام الگوریتم SL0 طراحی شده و با شبیه سازی نرم افزاری مورد ارزیابی واقع گردید. نتایج حاکی از آن است اجرای الگوریتم مذکور با تک پردازنده با فرض 4 کلاک برای انجام هر بار معادله بازگشتی کلاکی معادل 4N^3+9.7N^2+3.2N+18لازم دارد در حالیکه انجام آن با آرایه سیستولیکی به دلیل انجام محاسبات به صورت موازی و پایپ لاین، کلاکی معادل 48N+32 لازم دارد.
Systolic architecture is one of most important parallel processing architectures.In the systolic array, ALU units are arranged as an array. This array acts synchronously and executes the recursive equations in parallel by applying the proper input. In this paper, the systolic array for the SL0 is designed and simulated. Simulation results showed that the implementation of this algorithm with a single processor, assuming 4 clocks for executing each recursive equation, requires 4N ^ 3 + 9.7N ^ 2 + 3.2N + 18 clocks, while doing it with a systolic array requires 48n + 32 clocks due to parallel computing and pipelines.
خلاصه ماشینی:
نتایج حاکی از آن است که اجرای الگوریتم مذکور با تک پردازنده با فرض 4 کلاک برای انجام هر بار معادله بازگشتی تعداد کلاکی معادل 4N^3+9.
حاصلضرب این دو ماتریس، یک ماتریس با ابعاد N×N به نام C است که بهصورت زیر خواهد بود: (رجوع شود به تصوير صفحه) برای محاسبه هر درایه ماتریس C، باید حاصل جمع تجمعی رابطه (۷) محاسبه شود که ترکیبی از عملیات جمع و ضرب است.
شکل (۲): آرایه سیستولیکی دوبعدی با توجه به رابطه (۷)، هر عنصر پردازشی آرایه باید توانایی انجام دو عمل زیر را داشته باشد: محاسبه حاصلضرب دو عملوند باینری ورودی (A_ik و B_kj) محاسبه حاصل جمع تجمعی حاصلضربها بنابراین برای انجام این ضرب توسط آرایه سیستولیکی، هر عنصر پردازشی باید حاوی یک جمعکننده و ضربکننده با تعداد بیت ورودی موردنیاز باشد.
شکل (3): یک واحد پردازشی آرایه سیستولیکی برای ضرب ماتریس همانطور که در شکل (۳) مشاهده میشود در لبه کلاک، دادههای ورودی (که شامل درایههای ماتریس A و B یعنی A Input و B Input است) با تعداد بیتهای معین، به داخل عنصر پردازشی (PE) پمپ میشوند.
شکل (۵): ترتیب انتقال درایههای ماتریسهای A و B به داخل آرایه سیستولیک بهعنوان دادههای ورودی برای تبیین موضوع و درک بهتر از عملکرد این ساختار، در جدول ۱ عملیات پردازشی برای ضرب دو ماتریس "3"×"3" در هر کلاک آورده شده است.
نتیجه بازیابی تکرار آخر برای این حالت را در شکل (۱۵) مشاهده میشود؛ بنابراین، معماری مبتنیبر آرایه سیستولیکی طراحیشده میتواند موجب تسریع چشمگیر الگوریتم SL0 در نمایش تنک، با دقت قابلقبول شود.
(رجوع شود به تصوير صفحه) شکل (۱۴): اجرای الگوریتم SL0 با استفاده از آرایه سیستولیکی بهازای σ=8,4,2,1,0.