Manuscript ID : 1400092132627 Visit : 3600 Page: 319 - 326

Article Type: Original Research

High Level Synthesis of Decimal Arithmetic on Coarse Grain Reconfigurable Architectures

Subject Areas : electrical and computer engineering

1 - Semnan University

Received: 2021-12-12 Accepted : 2023-01-18 Published : 2023-02-15

Keywords: High-level synthesis, decimal arithmetic, coarse grain reconfigurable architecture, hardware mapping, resource allocation,

Abstract :

The increasing capabilities of integrated circuits and the complexity of applications have led hardware design methods and tools to higher levels of abstraction and high-level synthesis is one of the key steps in increasing the level of abstraction. In recent years, extensive research has been conducted on the design of decimal arithmetic reconfigurable architectures. Since, on the one hand, the effective use of these architectures depends on the existence of appropriate algorithms and tools to implement the design on the hardware, and on the other hand, research on the development of these algorithms has been very limited, this paper will present methods for the automated synthesis of decimal arithmetic circuits on a coarse-grained reconfigurable architecture. The platform chosen to execute the proposed algorithms is the DARA coarse-grained reconfigurable architecture, which is optimized for decimal arithmetic. The algorithms proposed for resource allocation of synthesis include a heuristic method and an ILP algorithm. The results show that, as expected, for the limited architectural dimensions used, the ILP algorithm performs significantly (about 30%) better than the heuristic algorithm.

References:

[1] M. Sedighi, F. Haddadi, S. Emami, and M. Saffarpour, "A heuristic algorithm for high level synthesis of decimal arithmetic circuits using systemC," in Proc. 10th Int. Conf. on Design & Technology of Integrated Systems in Nanoscale Era, DTIS'15, 6 pp., Napoli, Italy, 21-23 Apr. 2015.
[2] D. D. Gajski and L. Ramachandran, "Introduction to high-level synthesis," IEEE Design & Test of Computers, vol. 11, no. 4, pp. 44-54, Winter 1994.
[3] P. Coussy, D. D. Gajski, M. Meredith, and A. Takach, "An introduction to high-level synthesis," IEEE Design & Test of Computers, vol. 26, no. 4, pp. 8-17, Aug. 2009.
[4] R. Nane, V. M. Sima, C. Pilato, J. Choi, B. Fort, A. Canis, Y. T. Chen, H. Hsiao, S. Brown, F. Ferrandi, J. Anderson, and K. Bertels, "A survey and evaluation of FPGA high-level synthesis tools," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 10, pp. 1591-1604, Oct. 2016.
[5] L. K. Wang, M. A. Erle, C. Tsen, E. M. Schwarz, and M. J. Schulte, "A survey of hardware designs for decimal arithmetic," IBM J. of Research and Development, vol. 54, no. 2, pp. 8:1-8:15, Mar./Apr. 2010.
[6] A. Nannarelli, "FPGA based acceleration of decimal operations," in Proc. Int. Conf. on Reconfigurable Computing and FPGAs, ReConFig'11, Cancun, pp. 146-151, Cancun, Mexico, 30-30 Nov. 2011.
[7] J. Cong, B. Liu, S. Neuendorffer, J. Noguera, K. Vissers, and Z. Zhang, "High-level synthesis for FPGAs: from prototyping to deployment," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 4, pp. 473-491, Apr. 2011.
[8] M. A. Shami, Dynamically Reconfigurable Resource Array, Ph.D. Dissertation, KTH Sch. Inf. Tech. Sweden, Kista, 2012.
[9] Y. Kim, R. N. Mahapatra, and K. Choi, "Design space exploration for efficient resource utilization in coarse-grained reconfigurable architecture," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 18, no. 10, pp. 1471-1482, Oct. 2010.
[10] S. Emami and M. Sedighi, "An optimized reconfigurable architecture for hardware implementation of decimal arithmetic," Computers & Electrical Engineering, vol. 63, pp. 18-29, Oct. 2017.
[11] M. Vladutiu, "Functional analysis and synthesis of binary and decimal adding and subtracting devices," in Computer Arithmetic Algorithms and Hardware Implementations, Springer Berlin Heidelberg, 2012.
[12] I. D. Castellanos, Analysis and Implementation of Decimal Arithmetic Hardware in Nanometer CMOS technology, Ph.D. Dissertation, Oklahoma State University, USA, 2008.
[13] J. P. Deschamps, G. J. A. Bioul, and G. D. Sutter, Synthesis of Arithmetic Circuits-FPGA, ASIC and Embedded Systems, Wiley-Interscience, 2006.
[14] M. A. Gladshtein, "Algorithmic synthesis of a combinational adder of decimal digits encoded by the Johnson-Mobius code," Automatic Control and Computer Sciences, vol. 43, no. 5, pp. 233-240, 2009.
[15] R. Zimmermann, "Datapath synthesis for standard-cell design," in Proc. of the 19th IEEE Symposium on Computer Arithmetic, pp. 207-211, Portland, OR, USA, 08-10 Jun. 2009.
[16] C. K. Cheng, "Design space exploration for power-efficient mixed-radix ling adders," in Proc. of the 19th IEEE Symp. on Computer Arithmetic, pp. 212-212, Portland, OR, USA, 8-10 Jun. 2009.
[17] A. K. Verma, P. Brisk, and P. Ienne, "Challenges in automatic optimization of arithmetic circuits," in Proc. of the 16th IEEE Symposium on Computer Arithmetic, pp. 213-218, Portland, OR, USA, 8-10 Jun. 2009.
[18] Zimpl, Zuse Institute Mathematical Programming Language, Available at: http://zimpl.zib.de.
[19] SCIP, Solving Constraint Integer Programs, Available at: http://scip.zib.de.
[20] IBM Corporation, The Telco Benchmark, Retrieved May 10, 2022, from: http://speleotrove.com/decimal/telcoSpec.html.

Full-Text:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

ﺳﻨﺘﺰ ﺳﻄﺢ ﺑﺎﻻي ﻣﺪارﻫﺎي ﺣﺴﺎﺑﯽ دﻫﺪﻫﯽ ﺑﺮ روي
ﻣﻌﻤﺎريﻫﺎي ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ

سمانه امامی

چكیده: اﻓﺰاﯾﺶ ﻗﺎﺑﻠﯿﺖﻫﺎي ﻣﺪارﻫﺎي ﻣﺠﺘﻤﻊ و ﭘﯿﭽﯿﺪﮔﯽ ﺑﺮﻧﺎﻣﻪﻫﺎي ﮐﺎرﺑﺮدي، روشﻫﺎ و اﺑﺰارﻫﺎي ﻃﺮاﺣﯽ ﺳﺨﺖ‌اﻓﺰار را ﺑﻪ ﺳﻤﺖ ﺳﻄﻮح ﺑﺎﻻﺗﺮي از اﻧﺘﺰاع ﺳﻮق داده و ﺳﻨﺘﺰ ﺳﻄﺢ ﺑﺎﻻ، ﯾﮑﯽ از ﮐﻠﯿﺪيﺗﺮﯾﻦ ﮔﺎمﻫﺎ در اﻓﺰاﯾﺶ ﺳﻄﺢ اﻧﺘﺰاع می‌باشد. در ﺳﺎل‌های اﺧﯿﺮ، ﺗﺤﻘﯿﻘﺎت ﮔﺴﺘﺮده‌اي ﺑﺮاي ﻃﺮاﺣﯽ ﺳﺎﺧﺘﺎرﻫﺎي ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي ﺑﺎ ﻫﺪف ﺣﺴﺎب دﻫﺪﻫﯽ ﺻﻮرت ﮔﺮﻓﺘﻪ اﺳﺖ. از آنجا که از یک سو، اﺳﺘﻔﺎده ﻣؤﺛﺮ از اﯾﻦ ﺳﺎﺧﺘﺎرﻫﺎ وابسته ﺑﻪ وﺟﻮد اﻟﮕﻮریتم‌ها و اﺑﺰارﻫﺎي ﻣﻨﺎﺳﺐ ﺟﻬﺖ ﭘﯿﺎدهﺳﺎزي ﻃﺮاﺣﯽ ﺑﺮ روي ﺳﺨﺖاﻓﺰار بوده و از سوی دیگر، ﭘﮋوﻫﺶ در زﻣﯿﻨﻪ ﺗﻮﺳﻌﻪ اﯾﻦ دﺳﺘﻪ از اﻟﮕﻮرﯾﺘﻢ‌ﻫﺎ بسیار اندک و محدود بوده است، در این مقاله روش‌هایی ﺑﺮاي ﺳﻨﺘﺰ ﺧﻮدﮐﺎر ﺗﻮﺻﯿﻒ ﺳﻄﺢ ﺑﺎﻻ از ﻣﺪارﻫﺎي ﺣﺴﺎﺑﯽ دﻫﺪﻫﯽ بر روي ﯾﮏ ﻣﻌﻤﺎري ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ اراﺋﻪ خواهد شد. بستر سخت‌افزاری انتخاب‌شده، معماری قابل بازپیکربندی درشت‌دانه DARA بوده و روش‌های پیشنهادشده برای اختصاص منابع در جریان سنتز، شامل دو الگوریتم مکاشفه‌ای و ILP می‌باشند. نتایج به دست آمده نشان می‌دهند که مطابق انتظار، برای ابعاد محدود معماری مورد استفاده، الگوریتم ILP به میزان قابل توجهی (حدود 30%) بهتر از الگوریتم مکاشفه‌ای عمل می‌نماید.

کلیدواژه: ﺳﻨﺘﺰ ﺳﻄﺢ ﺑﺎﻻ، ﺣﺴﺎب دﻫﺪﻫﯽ، ﻣﻌﻤﺎريﻫﺎي ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ، نگاشت روی سخت‌افزار، اختصاص منابع.

1- مقدمه

از آنجا که طراحی سامانه‌های دیجیتال بسیار پیچیده شده‌اند، توصیف ﺳﻄﺢ اﻧﺘﻘﺎل ثبات ²(RTL) دیگر برای حل چالش‌های پیش روی طراحان کافی نیست. ﺑﻨﺎﺑﺮاﯾﻦ در ﺳﺎل‌های اﺧﯿﺮ، ﺗﻼشﻫﺎي ﻗﺎﺑﻞ ﻣﻼﺣﻈﻪاي ﺑﺮاي اﻓﺰاﯾﺶ ﺳﻄﺢ اﻧﺘﺰاع ﻣﺪلﺳﺎزي و ﻃﺮاﺣﯽ ﺳﯿﺴﺘﻢﻫﺎي دﯾﺠﯿﺘﺎل اﻧﺠﺎم ﺷﺪه اﺳﺖ و روش‌های طراحی دیجیتال به ﺳﻨﺘﺰ ﺳﻄﺢ ﺑﺎﻻ ³(HLS) تکامل یافته‌اند [1].

ﺳﻨﺘﺰ ﺳﻄﺢ ﺑﺎﻻ به مجموعه‌ای از ﻋﻤﻠﯿﺎت گفته می‌شود ﮐﻪ ﯾﮏ ﺗﻮﺻﯿﻒ ﺳﻄﺢ ﺑﺎﻻ از ﻋﻤﻠﮑﺮد ﻣﺪار را ﺑﻪ ﺗﻮﺻﯿﻒ ﺳﻄﺢ اﻧﺘﻘﺎل ثبات آن ﺗﺒﺪﯾﻞ ﻣﯽﮐﻨﺪ [2]. اﻓﺰاﯾﺶ ﺳﻄﺢ اﻧﺘﺰاع، ﺗﻮﻟﯿﺪ ﺳﺮﯾﻊ ﯾﮏ ﺳﺨﺖاﻓﺰار در سطح RTL را با ﺳﺮﻋﺖ، ﻣﺴﺎﺣﺖ یا ﺗﻮان مصرفی بهینه اﻣﮑﺎنﭘﺬﯾﺮ ﻣﯽنماید [3]. با توجه به این که سنتز سطح بالا، ﻃﺮاﺣﯽ ﺳﯿﺴﺘﻢﻫﺎي ﭘﯿﭽﯿﺪه اﻣﺮوزي را تسهیل کرده و زﻣﺎن رﺳﯿﺪن ﻣﺤﺼﻮل ﺑﻪ ﺑﺎزار را ﮐﺎﻫﺶ داده است، به سرعت مورد توجه و گسترش قرار گرفت [4].

با توجه به مباحث مطرح‌شده، سنتز سطح بالا ﻣﯽﺗﻮاﻧﺪ در ﻫﻤﻪ ﮐﺎرﺑﺮدﻫﺎ ﻣﻔﯿﺪ واﻗﻊ ﺷﻮد، اﻣﺎ ﻫﺮﭼﻪ ﺗﻮﺻﯿﻒ اوﻟﯿﻪ ﭼﮑﯿﺪهﺗﺮ ﺑﺎﺷﺪ، کارایی جریان سنتز در ﮐﺎرﺑﺮد ﻣﻮرد ﻧﻈﺮ ﻧﻤﻮد ﺑﯿﺸﺘﺮي ﺧﻮاﻫﺪ داﺷﺖ. از ﺟﻤﻠﻪ ﮐﺎرﺑﺮدﻫﺎﯾﯽ ﮐﻪ ورودي اوﻟﯿﻪ در آﻧﻬﺎ ﺑﺴﯿﺎر ﭼﮑﯿﺪه اﺳﺖ، ﮐﺎرﺑﺮدﻫﺎي ﺣﺴﺎﺑﯽ اﺳﺖ. زیرا ﮐﺎرﺑﺮ ﺗﻨﻬﺎ ﯾﮏ ﻋﺒﺎرت ﺣﺴﺎﺑﯽ را وارد ﻣﯽﮐﻨﺪ و از ﻧﺤﻮه ﭘﯿﺎدهﺳﺎزي آن ﺑﺮ ﺑﺴﺘﺮ ﺳﺨﺖاﻓﺰار ﺑﯽاﻃﻼع اﺳﺖ. از ﻣﯿﺎن ﮐﺎرﺑﺮدﻫﺎي ﺣﺴﺎﺑﯽ ﮐﻪ اغلب ﻧﯿﺎز ﺑﻪ دﻗﺖ ﺑﺎﻻﯾﯽ دارﻧﺪ، ﺣﺴﺎب دﻫﺪﻫﯽ از اﻫﻤﯿﺖ وﯾﮋه‌اي ﺑﺮﺧﻮردار اﺳﺖ. زیرا از یک سو، بیشتر عملیات حسابی در زندگی امروز بشر (مانند کاربردهای مالی و تجاری) با داده‌های دهدهی انجام می‌شوند و از سوی دیگر، بسیاری از اعداد اعشاری دهدهی مانند 1/0 نمی‌توانند نمایش دقیقی در مبنای دو داشته باشند [5]. برای حفظ دقت در این ﮐﺎرﺑﺮدﻫﺎ، ﯾﺎ ﺑﺎﯾﺪ آنها را ﺑﺎ اﺳﺘﻔﺎده از ﮐﺘﺎﺑﺨﺎﻧﻪﻫﺎي ﺣﺴﺎب دﻫﺪﻫﯽ ﻣﺒﺘﻨﯽ ﺑﺮ ﻧﺮم‌اﻓﺰار اﺟﺮا نمود و یا از ﻣﺪارﻫﺎي ﺳﺨﺖاﻓﺰاري ﻣﻨﺎﺳﺐ ﺑﺮاي ﻋﻤﻠﯿﺎت دﻫﺪﻫﯽ ﭘﺎﯾﻪ اﺳﺘﻔﺎده کرد. از آنجا که پیاده‌سازی نرم‌افزاری حساب دهدهی بین 100 تا 1000 برابر کندتر از پیاده‌سازی دودویی در سخت‌افزار است، گرایش به پیاده‌سازی سخت‌افزاری حساب دهدهی در سال‌های اخیر افزایش یافته است [6]. در پیاده‌سازی‌های سخت‌افزاری، طراحی به روش ⁴ASIC و استفاده از ⁵FPGAها، دو سر طیف انواع پیاده‌سازی و نقطه مقابل یکدیگر از نظر مساحت، توان، تأخیر، انعطاف‌پذیری، هزینه ساخت و زمان آماده‌شدن محصول هستند [7] تا [9]. ﻫﺪف ﯾﮏ ﻃﺮاﺣﯽ ﺧﻮب، رﺳﯿﺪن ﺑﻪ ﺳﺮﻋﺘﯽ ﺷﺒﯿﻪ ﺑﻪ ASIC و ﻗﺪرت اﻧﻌﻄﺎف، ﺻﺮف زﻣﺎن و هزینه‌ای مشابه FPGA است. اﻓﺰاﯾﺶ ﻫﺰﯾﻨﻪﻫﺎي ﻃﺮاﺣﯽ و ﺻﺮف زﻣﺎن زﯾﺎد ﺑﺮاي ASIC و کارایی پایین محاسباتی و سربار بالای مساحت در FPGAها، طراحان معماری را وادار به جستجوی جایگزینی برای این معماری‌ها کرده
است. ﻣﻌﻤﺎريﻫﺎي ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ ⁶(CGRA) داراي ﮐﺎراﯾﯽ ﻣﺤﺎﺳﺒﺎﺗﯽ ﺑﺎﻻ، ﻫﺰینه و ﺻﺮف زﻣﺎن ﭘﺎﯾﯿﻨﯽ ﺑﺮاي ﻃﺮاﺣﯽ ﻫﺴﺘﻨﺪ و ﺑﻪ ﻫﻤﯿﻦ دﻟﯿﻞ، ﺟﺎﯾﮕﺰینی ﺟﺬاب و ﻣﻨﺎسب ﺑﺮاي ﻃﺮاﺣﯽ در ﺣﻮزه‌ ﮐﺎرﺑﺮدﻫﺎي ﺧﺎصﻣﻨﻈﻮره ﻫﺴﺘﻨﺪ. در واﻗﻊ ﻣﻌﻤﺎريﻫﺎي ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ، مصالحه‌ای⁷ بین ASIC و FPGAها به شمار می‌روند، زیرا نسبت به FPGAها، ﺑﺎزده ﻣﺤﺎﺳﺒﺎﺗﯽ ﺑﻬﺘﺮ و در ﻣﻘﺎﯾﺴﻪ ﺑﺎ ASIC، بازده ﻣﻬﻨﺪﺳﯽ ﺑﻬﺘﺮي دارﻧﺪ [8].

این مقاله به اراﺋﻪ ﯾﮏ روش ﺳﻨﺘﺰ ﺧﻮدﮐﺎر ﺗﻮﺻﯿﻒ ﺳﻄﺢ ﺑﺎﻻ از ﻣﺪارﻫﺎي حسابی دهدهی روي ﯾﮏ ﻣﻌﻤﺎري ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ از این کاربرد می‌پردازد. معماری انتخاب‌شده برای این منظور، ⁸DARA نام دارد [10] که در بخش دوم معرفی گردیده و روش‌های پیشنهادشده برای اختصاص منابع در جریان سنتز، شامل دو الگوریتم مکاشفه‌ای و برنامه‌نویسی خطی صحیح ⁹(ILP) می‌باشند.

ساختار مقاله به این شرح است که در بخش دوم به مرور کارهای انجام‌شده در زمینه سنتز مدارهای حسابی پرداخته می‌شود. در بخش سوم، روش پیشنهادی برای سنتز سطح بالای مدارهای حسابی دهدهی ارائه می‌گردد. مقایسه نتایج حاصل از روش‌های پیشنهادی در بخش چهارم بیان می‌شود و در بخش پنجم، نتیجه‌گیری و پیشنهادهایی برای کارهای آینده ارائه خواهد گردید.

2- مروری بر کارهای گذشته

در پژوهش‌های مختلف، نگاه متفاوتی به تعریف سنتز مدارهای حسابی وجود دارد. در برخی منابع مانند [11]، مفهوم سنتز در معنای عام تبدیل الگوریتم به مدار و معادل با طراحی مدار با استفاده از عبارات منطقی، جدول کارنو و جدول درستی¹⁰ در نظر گرفته شده است. در [12]، سنتز فرایندی است که یک توصیف سطح بالای سخت‌افزار را با در نظر گرفتن زمان‌بندی سلول‌ها و محدودیت‌های دیگر، به netlist تبدیل می‌نماید. در [13]، اصطلاح سنتز به معنای عام طراحی با در نظر گرفتن انتخاب‌های مختلف در فضای جواب به کار می‌رود. در [14] منظور از سنتز الگوریتمی، ارائه یک الگوریتم برای تبدیل داده‌های ورودی به خروجی است که به سادگی با استفاده از یک مدار ترکیبی پیاده‌سازی شده است. در [15] تنها به بیان معماری‌ها و روش‌های به کار رفته در ابزارهای سنتز تجاری برای بهبود طراحی مبتنی بر سلول¹¹ از نظر زمان، مساحت و توان پرداخته شده است. در این منبع به بیان کلیات روند سنتز به کار گرفته شده در این ابزارها، شامل استخراج عملیات حسابی از توصیف انجام‌شده و خوشه‌بندی آنها در دسته‌های بزرگ‌تر، بهینه‌سازی مسیر داده با الگوریتم‌های مختلف حسابی، تولید netlist با استفاده از روش‌های مختلف پیاده‌سازی عملگرها و الگوریتم‌هایی برای کاهش توان مصرفی ناشی از بزرگ‌بودن اندازه مدارها و فعالیت بالای سوئیچ‌ها پرداخته شده است.

بعضی منابع، در تعریف سنتز فقط بر روی بهینه‌سازی مدار متمرکز شده‌اند. به عنوان نمونه در [16] با استفاده از ILP، روشی بهینه‌ برای پیاده‌سازی جمع‌کننده Ling ارائه گردیده است. نویسنده این مقاله ادعا کرده که یک فرمول‌بندی ILP بر اساس مدل‌های تلاش منطقی¹² ارائه نموده که با کوچک‌سازی فضای جستجو، زمان اجرای الگوریتم را کاهش می‌دهد. منبع دیگری که به جنبه بهینه‌سازی در سنتز پرداخته است، [17] بوده که 3 روش مختلف برای بهینه‌سازی مدارهای حسابی ارائه می‌نماید.

مقاله [1]، سنتز سطح بالا را بر 3 بخش اصلی استوار می‌داند: 1) کتابخانه گسترش‌یافته از مؤلفه‌های سطح بالا که ویژگی‌های دقیق آنها مانند تأخیر، مساحت و توان، برای الگوریتم سنتزی که می‌خواهد از آنها استفاده کند، مشخص شده باشد. 2) یک زبان سطح بالا که از توصیف و مدل‌سازی مداری که باید سنتز شود، پشتیبانی نماید. 3) یک یا چند الگوریتم که فضای طراحی را به منظور یافتن راه حل بهینه یا نزدیک به بهینه جستجو کند.

معماری DARA که در این مقاله از آن به عنوان بستر سخت‌افزاری الگوریتم‌های پیشنهادی استفاده می‌شود، در شکل 1 آمده است. این معماری از تکرار منظم 5 نوع بلوک مختلف، تشکیل و برای پیاده‌سازی عملیات پایه حساب دهدهی بهینه شده است. با توجه به درشت‌دانه‌بودن معماری DARA و دنبال‌کردن رویکرد [1]، از خود بلوک‌های سازنده آن به عنوان مؤلفه‌های موجود در کتابخانه استفاده گردیده و زبان توصیف مدار دهدهی ورودی نیز SystemC در نظر گرفته شده است. در این مقاله بر روی عنصر سوم جریان سنتز، یعنی الگوریتم نگاشت بر روی سخت‌افزار تمرکز شده و یک روش مکاشفه‌ای¹³ یک الگوریتم ILP برای سنتز یک مدار دهدهی ورودی بر روی یک سخت‌افزار قابل بازپیکربندی درشت‌دانه (DARA) پیشنهاد می‌گردد.

3- روش‌های سنتز پیشنهادی

از آنجا که الگوریتم‌های پیشنهادی بر روی یک ¹⁴DFG ورودی عمل می‌کنند، گام اول در جریان سنتز، تبدیل توصیف اولیه مدار حسابی به DFG می‌باشد. برای تولید این DFG که در ادامه آن را DFG سطح بالا ¹⁵(HLDFG) می‌نامیم، از همان الگوریتم ارائه‌شده در [1] استفاده می‌شود. بعد از تولید DFG سطح بالا، جستجو برای یافتن بهترین نگاشت گره‌های DFG بر روی معماری آغاز خواهد گردید.

گام دوم و مشترک در هر دو الگوریتم پیشنهادی، بررسی وجود راه حل برای نگاشت یا همان امکان‌سنجی مسئله می‌باشد. اگر هدف، رسیدن به یک تأخیر یا فرکانس مشخص در مدار باشد، باید ابتدا تمام گره‌ها به سریع‌ترین پیاده‌سازی‌های جمع، تفریق و ضرب نگاشت شوند. در این حالت اگر مسیر بحرانی یافت‌شده، بزرگ‌تر از محدودیت تأخیر داده‌شده باشد، راه حلی برای مسئله وجود ندارد. در غیر این صورت، تمام گره‌ها
به کندترین یا کوچک‌ترین پیاده‌سازی‌ها (یعنی با کمترین تعداد بلاک) نگاشت می‌شوند. در این صورت نیز اگر منابع موجود در معماری پیشنهادی (شامل بلاک‌ها، سوئیچ‌ها، مسیرهای ارتباطی و I/O) برای پیاده‌سازی مدار کافی نباشد، راه حلی برای مسئله وجود ندارد. اگر هیچ یک از شرایط بالا برقرار نباشد، یعنی باید الگوریتمی برای نگاشت بهینه یا نزدیک به بهینه مدار بر روی معماری اجرا شود.

گام سوم، تبدیل DFG سطح بالای به دست آمده از توصیف ورودی به DFG سطح پایین ¹⁶(LLDFG) می‌باشد. به این معنا که برای هر گره که نشان‌دهنده یک عملیات حسابی دهدهی است، یکی از پیاده‌سازی‌های ممکن آن با استفاده از مجموعه بلاک‌های موجود در معماری، جایگزین گره مربوط در DFG سطح بالا گردد. با توجه به این که برای هر عملیات حسابی دهدهی، پیاده‌سازی‌های مختلفی از نظر تأخیر مدار و بلاک‌های استفاده‌شده وجود دارد، بنابراین برای هر DFG سطح بالا، چندین DFG سطح پایین وجود خواهد داشت و ایجاد DFG سطح پایین مناسب، حائز اهمیت است.

برای ایجاد DFG سطح پایین مناسب، ابتدا باید با توجه به حداقل و حداکثر کلاک‌های مورد نیاز برای پیاده‌سازی‌های مختلف هر عملیات حسابی دهدهی، مسیر بحرانی را در DFG سطح بالا یافته و سپس

[1] این مقاله در تاریخ 21 آذر ماه 1400 دریافت و در تاریخ 28 اردیبهشت ماه 1401 بازنگری شد.

سمانه امامی، دانشكده مهندسي برق و كامپيوتر، دانشگاه سمنان، سمنان، ایران، (email: s_emami@semnan.ac.ir).

[2] . Register Transfer Level

[3] . High Level Synthesis

[4] . Application Specific Integrated Circuit

[5] . Field Programmable Gate Array

[6] . Coarse Grain Reconfigurable Architecture

[7] . Trade-off

[8] . Decimal Arithmetic Reconfigurable Architecture

[9] . Integer Linear Programming

[10] . Truth Table

[11] . Cell-Based Design

[12] . Logical Effort

[13] . Heuristic

[14] . Data Flow Graph

[15] . High Level DFG

[16] . Low Level DFG

شکل 1: معماری DARA [10].

عملیات روی مسیر بحرانی را با سریع‌ترین پیاده‌سازی ممکن و سایر عملیات‌ها را با پیاده‌سازی‌های کندتر و کوچک‌تر (تعداد بلاک کمتر) جایگزین نمود. شبه‌کد مربوط به الگوریتم تبدیل DFG سطح بالا به DFG سطح پایین در شکل 2 نشان داده شده است.

بدیهی است که اگر با DFG سطح پایین به دست آمده، پس از اجرای الگوریتم نگاشت، نتیجه مطلوب حاصل نشد، می‌توان DFG سطح پایین را با تغییر پیاده‌سازی‌های موجود، اصلاح نمود.

در گام آخر برای نگاشت DFG سطح پایین بر روی معماری DARA، دو روش پیشنهاد می‌گردد.

3-1 الگوریتم نگاشت مکاشفه‌ای

اساس کار این الگوریتم بر مبنای یکی از انواع الگوریتم‌های یافتن کوتاه‌ترین مسیر در گراف‌ها مانند الگوریتم Dijkstra می‌باشد. در این روش، بلاک‌های موجود در معماری (شامل بلاک‌های I/O و عملیات) به

Algorithm (HLDFG, delay_const, available_resources)

{

Set all nodes to the fastest/biggest implementations of adder, subtractor and multiplier;

if (delay_const < delay)

There is no solution for this problem!

else

Set all nodes to the smallest/slowest implementations of adder,

subtractor and multiplier;

if (available_resources < needed resources)

There is no solution for this problem!

else

findCritical (path_1, path_2,..., path_n);

replaceCritical (fastest implementations);

replaceNonCritical (smaller implementations);

until their delay does not exceed the critical path delay;

}

شکل 2: شبه‌کد الگوریتم تبدیل HLDFG به LLDFG.

عنوان گره‌های گراف و کانال‌های ارتباطی بین بلاک‌ها به عنوان یال‌های گراف در نظر گرفته شده و وزن هر یال، معادل تعداد سوئیچ‌های بین 2 بلاک می‌باشد. با توجه به این که در معماری DARA، جریان داده‌ها در مسیرهای افقی فقط از سمت چپ به راست و در مسیرهای عمودی فقط از پایین به بالا بوده و ورودی بلاک‌های سازنده از مسیرهای افقی بالای آنها تأمین شده و خروجی به مسیر‌های عمودی سمت راست آنها داده می‌شود، وزن یال‌ها (یا همان فاصله هر بلاک از بلاک‌های اطراف خود بر حسب تعداد سوئیچ‌های بین آنها) مطابق شکل 3 به دست می‌آید.

از آنجا که در تقاطع هر سطر و ستون در معماری DARA یک سوئیچ وجود دارد و فاصله بین بلاک‌ها با تعداد سوئیچ‌ها محاسبه می‌شود و ورودی بلاک‌ها از سمت بالای بلاک تأمین گردیده و خروجی آنها به سمت راست داده می‌شود (با توجه به شکل 3)، فاصله بلاک‌های و از (1) به دست می‌آید که در آن و به ترتیب شماره ستون و سطر مربوط به بلاک هستند

(1)

پس به ترتیب با شروع از بلاک‌های موجود در مسیر بحرانی LLDFG، الگوریتم یافتن کوتاه‌ترین مسیر بین هر دو بلاک اجرا شده و بلاک‌های انتخاب‌شده از لیست منابع موجود در معماری حذف می‌گردند. با توجه
به این که بعضی از بلاک‌ها در LLDFG به بیش از یک بلاک دیگر وابستگی داده‌ای دارند، در این شرایط، الگوریتم تلاش می‌کند که بلاکی را بیابد که مجموع فواصل آن از بلاک‌های وابسته حداقل باشد. این کار تا نگاشت کامل LLDFG بر روی معماری DARA ادامه دارد.

3-2 الگوریتم نگاشت ILP

در این روش، جستجویی خطی و جامع¹ برای یافتن جواب بهینه انجام می‌شود و به همین دلیل در صورت بزرگ‌بودن فضای مسئله، زمان‌بر و پیچیده خواهد بود. برای ارائه الگوریتم پیشنهادی، نگاشت‌های مختلف هر عملیات، ابتدا بر روی معماری DARA (در قالب درخت‌های تشکیل‌شده

شکل 3: فاصله بلاک‌ها در معماری DARA بر حسب تعداد سوئیچ بین آنها.

از بلاک‌های مورد نیاز) در نظر گرفته شده و به هر نگاشت، وزنی معادل تعداد سوئیچ‌های مسیر بحرانی آن نسبت داده می‌شود. بدیهی است که هر یک از انواع درخت‌ها می‌توانند در چندین نقطه مختلف از معماری نگاشت شوند. جدول 1، نمونه‌هایی از پیاده‌سازی‌های مختلف عملیات حسابی دهدهی را روی معماری DARA نشان می‌دهد. بلاک‌های استفاده‌شده در پیاده‌سازی هر درخت، همان بلاک‌های پیشنهادشده در [10] است که با چیدمان‌های مختلف کنار هم قرار گرفته‌اند.

تابع هدف در این الگوریتم، کم‌کردن پریود کلاک و در نتیجه تأخیر مدار می‌باشد. اگر فرض کنیم پریود کلاک برابر باشد که در آن، و به ترتیب تأخیر مربوط به بلاک و سوئیچ بوده و برابر تعداد سوئیچ‌های مسیر بحرانی است، دو پارامتر اول مقداری ثابت هستند. در نتیجه کاهش تأثیر مستقیمی در کم‌کردن پریود کلاک دارد و این در حالی است که مقدار هم به وزن درخت‌های انتخاب‌شده و هم به فاصله آنها از یکدیگر وابسته است.

عناصر و مجموعه‌های مورد نیاز برای پیاده‌سازی الگوریتم پیشنهادی عبارتند از:

: مجموعه گره‌های گراف ورودی با در نظر گرفتن بلاک‌های I/O

: مجموعه وابستگی داده‌ای بین عملیات (یال‌های گراف)

: مجموعه عملیات موجود در گراف ورودی مانند جمع، تفریق و ضرب

: مجموعه تمام درخت‌های ممکن برای نگاشت عملیات در معماری DARA

: مجموعه درخت‌های ممکن برای پیاده‌سازی عملیات مورد نظر

: مجموعه تمام زوج‌مرتب‌های ممکن از درخت‌ها

: پارامتر مشخص‌کننده نوع عملیات گره از DFG ورودی

: متغیر دودویی نشان‌دهنده انتخاب‌شدن یا نشدن درخت

: متغیر دودویی برای دخالت‌دادن یا ندادن نزدیکی درخت‌های وابسته مشخص‌شده در در میزان هزینه

: پارامتر نشان‌دهنده تعداد درخت مورد نیاز از عملیات نوع

: پارامتر نشان‌دهنده وزن درخت

: پارامتر نشان‌دهنده بلاک آغازین درخت

: پارامتر نشان‌دهنده بلاک پایانی درخت

: مجموعه نشان‌دهنده درخت‌های دارای بلاک مشترک از مجموعه برای بررسی عدم استفاده هم‌زمان از آنها

: تابع محاسبه‌کننده فاصله درخت‌های و

[1] . Exhaustive

جدول 1: مثال‌هایی از پیاده‌سازی‌های مختلف عملیات حسابی دهدهی بر روی معماری DARA.

درخت‌های مختلف پیاده‌سازی			عملیات
			جمع‌کننده مستقیم1
			جمع‌کننده 2CSl
			جمع‌کننده 3CSk
			تفریق‌کننده
			ضرب‌کننده

1. Direct Adder

2. Carry Select

3. Carry Skip

(الف) (ب)

شکل 4: (الف) LLDFG و (ب) HLDFG مربوط به (2).

با توجه به این که هدف الگوریتم، کاهش تأخیر مدار با استفاده از به حداقل رساندن پریود کلاک بوده و همان طور که بیان شد، پریود کلاک وابستگی مستقیمی با تعداد سوئیچ‌های مسیر بحرانی دارد، بنابراین تابع هدف به صورت زیر تعریف می‌شود

یعنی از میان تمام پیاده‌سازی‌های ممکن، درخت‌هایی انتخاب شوند که حداکثر مقدار میان وزن درخت (تعداد سوئیچ‌های مسیر بحرانی در پیاده‌سازی یک عملیات) و فاصله بین خروجی یک درخت تا ورودی درخت بعدی (تعداد سوئیچ‌ها در مسیر وابستگی داده‌ای عملیات مختلف) به حداقل برسد.

همچنین برای انتخاب درخت‌های ممکن برای پیاده‌سازی عملیات، محدودیت‌هایی وجود دارد که عبارت هستند از:

- هیچ درختی بیش از یک بار انتخاب نشود، یعنی

به عنوان مثال، برای پیاده‌سازی دو عمل جمع موازی، از یک شماره درخت ثابت استفاده نشود.

- تعداد درخت‌های انتخاب‌شده از یک نوع عملیات، برابر با تعداد گره‌های آن عملیات در DFG ورودی باشد، یعنی

مثلاً مجموع تعداد درخت‌های جمع‌کننده انتخاب‌شده با پیاده‌سازی‌های مختلف برابر با تعداد عملیات جمع مدار توصیف‌شده ورودی باشد.

- درخت‌هایی که از بلاک‌های مشترک استفاده می‌کنند، هم‌زمان انتخاب نشوند، یعنی

به عنوان مثال، یک بلاک MSG مشترک میان درخت‌های انتخاب‌شده برای پیاده‌سازی جمع و ضرب قرار نگیرد.

4- پیاده‌سازی و مقایسه نتایج

برای مقایسه الگوریتم‌های پیشنهادی و نتایج حاصل از آنها، ابتدا از مدار حسابی توصیف‌شده در (2) به عنوان مثال کمک گرفته می‌شود و در مرحله نخست، مدار ورودی به HLDFG و سپس به LLDFG تبدیل می‌گردد. خروجی این مرحله در شکل 4 قابل مشاهده است

(2)

برای پیاده‌سازی الگوریتم مکاشفه‌ای از زبان C استفاده گردیده و برای پیاده‌سازی الگوریتم ILP، روابط بیان‌شده در بخش قبل به زبان zimpl [18] توصیف و برای حل به ابزار SCIP [19] داده شده است. خروجی این ابزار برای مسئله توصیف‌شده، شماره درخت‌های انتخابی از معماری DARA می‌باشد. نگاشت نهایی حاصل از اجرای روش مکاشفه‌ای و ILP به ترتیب در شکل‌های 5 و 6 نمایش داده شده است. رنگ بلوک‌ها در این دو شکل‌، مطابق با رنگ گره متناظر در LLDFG در شکل 4 و نشان‌دهنده بلوک‌های شرکت‌کننده در اجرای آن عملیات می‌باشد.

مقایسه پیاده‌سازی‌های انجام‌شده نشان می‌دهد که مطابق آنچه انتظار می‌رفت، الگوریتم ILP نگاشت بهتری نسبت به روش مکاشفه‌ای انجام داده است. به طوری که تعداد سوئیچ‌های مسیر بحرانی در نگاشت انجام‌شده توسط الگوریتم مکاشفه‌ای برابر 7 می‌باشد، در حالی که تعداد این سوئیچ‌ها در نگاشت صورت‌گرفته توسط ILP، 4 است. بنابراین پریود کلاک در پیاده‌سازی انجام‌شده توسط ILP کمتر، فرکانس کلاک بیشتر و در نتیجه، تأخیر مدار ورودی کمتر خواهد بود.

برای ارزیابی دقیق‌تر الگوریتم‌های ارائه‌شده در هر حوزه، بهتر است که از برنامه‌های محک¹ موجود برای آنها استفاده گردد. اما متأسفانه برای ارزیابی عملکرد مدارهای حسابی دهدهی با ورودی اعداد صحیح، هیچ برنامه محکی در دسترس نیست. تنها محک موجود، برنامه TELCO [20] است که برای مدارهای حسابی دهدهی ممیز شناور مورد استفاده قرار می‌گیرد. شبه‌کد و DFG ساده‌شده این برنامه در شکل 7 نشان داده شده است. همان طور که از این شکل مشخص می‌شود، این برنامه محک از دو عملیات جمع و دو عملیات ضرب تشکیل شده است. با فرض این که ورودی‌های برنامه، اعداد صحیح دهدهی باشند، نگاشت این مدار بر روی معماری با استفاده از الگوریتم مکاشفه‌ای، شامل 6 سوئیچ و با الگوریتم ILP شامل 4 سوئیچ در مسیر بحرانی خواهد بود.

با توجه به این که الگوریتم مکاشفه‌ای بر اساس هوشمندی محدود تعریف‌شده برای آن عمل می‌کند و الگوریتم ILP، بررسی جامعی از تمام

[1] . Benchmark

شکل 5: نگاشت LLDFG (2) بر روی DARA با استفاده از روش مکاشفه‌ای.

حالات ممکن نگاشت مدار بر روی معماری انجام می‌دهد، پیش‌بینی اولیه در مورد عملکرد بهتر الگوریتم ILP در مقابل الگوریتم مکاشفه‌ای بود که نتایج به دست آمده نیز آن را تأیید نموده است.

5- نتیجه‌گیری و کارهای آینده

در این مقاله، روش‌هایی ﺑﺮاي ﺳﻨﺘﺰ ﺧﻮدﮐﺎر ﺗﻮﺻﯿﻒ ﺳﻄﺢ ﺑﺎﻻی ﻣﺪارﻫﺎي ﺣﺴﺎﺑﯽ دﻫﺪﻫﯽ روي ﯾﮏ ﻣﻌﻤﺎري ﻗﺎﺑﻞ ﺑﺎزﭘﯿﮑﺮﺑﻨﺪي درﺷﺖداﻧﻪ اراﺋﻪ گردید. معماری قابل بازپیکربندی درشت‌دانه DARA به عنوان
بستر سخت‌افزاری آزمایش انتخاب شده و دو الگوریتم مکاشفه‌ای و ILP برای اختصاص منابع در جریان سنتز ارائه گردید. بررسی‌های انجام‌شده مشخص نمود که برای ابعاد محدود معماری مورد استفاده، نگاشت انجام‌شده توسط الگوریتم ILP نسبت به الگوریتم مکاشفه‌ای حدود 30% در پریود کلاک، کاهش نشان می‌دهد. در ادامه این پژوهش برای بهبود نتایج الگوریتم‌ها، می‌توان پارامترهای دخیل در محاسبه فاصله بلاک‌ها را دقیق‌تر کرد. به علاوه می‌توان در الگوریتم ILP درخت‌های متنوع‌تری را برای پیاده‌سازی عملیات مختلف در نظر گرفت.

مراجع

[1] M. Sedighi, F. Haddadi, S. Emami, and M. Saffarpour, "A heuristic algorithm for high level synthesis of decimal arithmetic circuits using systemC," in Proc. 10th Int. Conf. on Design & Technology of Integrated Systems in Nanoscale Era, DTIS'15, 6 pp., Napoli, Italy, 21-23 Apr. 2015.

[2] D. D. Gajski and L. Ramachandran, "Introduction to high-level synthesis," IEEE Design & Test of Computers, vol. 11, no. 4, pp.
44-54, Winter 1994.

[3] P. Coussy, D. D. Gajski, M. Meredith, and A. Takach, "An introduction to high-level synthesis," IEEE Design & Test of Computers, vol. 26, no. 4, pp. 8-17, Aug. 2009.

[4] R. Nane, V. M. Sima, C. Pilato, J. Choi, B. Fort, A. Canis, Y. T. Chen, H. Hsiao, S. Brown, F. Ferrandi, J. Anderson, and K. Bertels, "A survey and evaluation of FPGA high-level synthesis tools," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 10, pp. 1591-1604, Oct. 2016.

[5] L. K. Wang, M. A. Erle, C. Tsen, E. M. Schwarz, and M. J. Schulte, "A survey of hardware designs for decimal arithmetic," IBM J. of Research and Development, vol. 54, no. 2, pp. 8:1-8:15, Mar./Apr. 2010.

[6] A. Nannarelli, "FPGA based acceleration of decimal operations," in Proc. Int. Conf. on Reconfigurable Computing and FPGAs, ReConFig'11, Cancun, pp. 146-151, Cancun, Mexico, 30-30 Nov. 2011.

[7] J. Cong, B. Liu, S. Neuendorffer, J. Noguera, K. Vissers, and Z. Zhang, "High-level synthesis for FPGAs: from prototyping to deployment," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 4, pp. 473-491, Apr. 2011.

[8] M. A. Shami, Dynamically Reconfigurable Resource Array, Ph.D. Dissertation, KTH Sch. Inf. Tech. Sweden, Kista, 2012.

[9] Y. Kim, R. N. Mahapatra, and K. Choi, "Design space exploration for efficient resource utilization in coarse-grained reconfigurable architecture," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 18, no. 10, pp. 1471-1482, Oct. 2010.

[10] S. Emami and M. Sedighi, "An optimized reconfigurable architecture for hardware implementation of decimal arithmetic," Computers & Electrical Engineering, vol. 63, pp. 18-29, Oct. 2017.

[11] M. Vladutiu, "Functional analysis and synthesis of binary and decimal adding and subtracting devices," in Computer Arithmetic Algorithms and Hardware Implementations, Springer Berlin Heidelberg, 2012.

شکل 6: نگاشت LLDFG (2) بر روی DARA با استفاده از روش ILP.

(الف)

(ب)

شکل 7: (الف) شبه‌کد و (ب) DFG ساده‌شده برنامه TELCO.

[12] I. D. Castellanos, Analysis and Implementation of Decimal Arithmetic Hardware in Nanometer CMOS technology, Ph.D. Dissertation, Oklahoma State University, USA, 2008.

[13] J. P. Deschamps, G. J. A. Bioul, and G. D. Sutter, Synthesis of Arithmetic Circuits-FPGA, ASIC and Embedded Systems, Wiley-Interscience, 2006.

[14] M. A. Gladshtein, "Algorithmic synthesis of a combinational adder of decimal digits encoded by the Johnson-Mobius code," Automatic Control and Computer Sciences, vol. 43, no. 5, pp. 233-240, 2009.

[15] R. Zimmermann, "Datapath synthesis for standard-cell design," in Proc. of the 19th IEEE Symposium on Computer Arithmetic, pp. 207-211, Portland, OR, USA, 08-10 Jun. 2009.

[16] C. K. Cheng, "Design space exploration for power-efficient mixed-radix ling adders," in Proc. of the 19th IEEE Symp. on Computer Arithmetic, pp. 212-212, Portland, OR, USA, 8-10 Jun. 2009.

[17] A. K. Verma, P. Brisk, and P. Ienne, "Challenges in automatic optimization of arithmetic circuits," in Proc. of the 16th IEEE Symposium on Computer Arithmetic, pp. 213-218, Portland, OR, USA, 8-10 Jun. 2009.

[18] Zimpl, Zuse Institute Mathematical Programming Language, Available at: http://zimpl.zib.de.

[19] SCIP, Solving Constraint Integer Programs, Available at: http://scip.zib.de.

[20] IBM Corporation, The Telco Benchmark, Retrieved May 10, 2022, from: http://speleotrove.com/decimal/telcoSpec.html.

سمانه امامی تحصیلات خود در مقاطع کارشناسی و کارشناسی‌ ارشد را در گرایش نرم‌افزار دانشگاه شهید بهشتی به ترتیب در سال‌های 1387 و 1389 و در مقطع دکتری در گرایش معماری کامپیوتر دانشگاه صنعتی امیرکبیر در سال 96 با درجه عالی به پایان رسانده است. وی هم‌اکنون استادیار دانشکده مهندسی برق و کامپیوتر دانشگاه سمنان می‌باشد. زمینه‌های پژوهشی مورد علاقه ایشان عبارتند از: حساب کامپیوتری دهدهی، سنتز سطح بالا و معماری‌های قابل بازپیکربندی.

Automatic Change Detection by Intelligent Backgrounding Method
Print Date : 2003-03-21
Speed Estimation and Sensorless Torque Optimization of Single Phase Induction Motor
Print Date : 2003-06-21
Optimal Design of Three-Phase Squirrel-Cage Induction Motor for Electric Vehicle
Print Date : 2003-06-21
A New Method in Design and Implementation of Electronic Synchronizer Based on Phase Locked Loop for Fast Paralleling of Diesel–Generators
Print Date : 2003-06-21
A New Circuit for Protecting of Series Connected Power Thyristors
Print Date : 2003-06-21
Cooperation in Multi-Agent Systems Using Learning Automata
Print Date : 2003-06-21

Share To

Article Url

High Level Synthesis of Decimal Arithmetic on Coarse Grain Reconfigurable Architectures